1st Edition

Data Flow Analysis Theory and Practice

    395 Pages 154 B/W Illustrations
    by CRC Press

    Data flow analysis is used to discover information for a wide variety of useful applications, ranging from compiler optimizations to software engineering and verification. Modern compilers apply it to produce performance-maximizing code, and software engineers use it to re-engineer or reverse engineer programs and verify the integrity of their programs.

     

    Supplementary Online Materials to Strengthen Understanding

     

    Unlike most comparable books, many of which are limited to bit vector frameworks and classical constant propagation, Data Flow Analysis: Theory and Practice offers comprehensive coverage of both classical and contemporary data flow analysis. It prepares foundations useful for both researchers and students in the field by standardizing and unifying various existing research, concepts, and notations. It also presents mathematical foundations of data flow analysis and includes study of data flow analysis implantation through use of the GNU Compiler Collection (GCC). Divided into three parts, this unique text combines discussions of inter- and intraprocedural analysis and then describes implementation of a generic data flow analyzer (gdfa) for bit vector frameworks in GCC.

    Through the inclusion of case studies and examples to reinforce material, this text equips readers with a combination of mutually supportive theory and practice, and they will be able to access the author’s accompanying Web page. Here they can experiment with the analyses described in the book, and can make use of updated features, including:

    • Slides used in the authors’ courses
    • The source of the generic data flow analyzer (gdfa)
    • An errata that features errors as they are discovered
    • Additional updated relevant material discovered in the course of research

    PREFACE:

    An Introduction to Data Flow Analysis

    A Motivating Example

    Program Analysis: The Larger Perspective

    Characteristics of Data Flow Analysis

    Summary and Concluding Remarks

    SECTION I: Intraprocedural Data Flow Analysis

    Classical Bit Vector Data Flow Analysis

    Basic Concepts and Notations

    Discovering Local Data Flow Information

    Discovering Global Properties of Variables

    Discovering Global Properties of Expressions

    Combined May-Must Analyses

    Summary and Concluding Remarks

     

    Theoretical Abstractions in Data Flow Analysis

    Graph Properties Relevant to Data Flow Analysis

    Data Flow Framework

    Data Flow Assignments

    Computing Data Flow Assignments

    Complexity of Data Flow Analysis for Rapid Frameworks

    Summary and Concluding Remarks

     

    General Data Flow Frameworks

    Non-Separable Flow Functions

    Discovering Properties of Variables

    Discovering Properties of Pointers

    Liveness Analysis of Heap Data

    Modeling Entity Dependence

    Summary and Concluding Remarks

     

    Complexity of Iterative Data Flow Analysis

    Generic Flow Functions and Data Flow Equations

    Generic Round Robin Iterative Algorithm

    Complexity of Round Robin Iterative Algorithm

    Summary and Concluding Remarks

     

    Single Static Assignment Form as Intermediate Representation

    Introduction

    Construction of SSA Form Programs

    Destruction of SSA

    Summary and Concluding Remarks

     

    SECTION II: Interprocedural Data Flow Analysis

    Introduction to Interprocedural Data Flow Analysis

    A Motivating Example

    Program Representations for Interprocedural Analysis

    Modeling Interprocedural Data Flow Analysis

    Compromising Precision for Scalability

    Language Features Influencing Interprocedural Analysis

    Common Variants of Interprocedural Data Flow Analysis

    An Aside on Interprocedural Optimizations

    Summary and Concluding Remarks

     

    Functional Approach to Interprocedural Data Flow Analysis

    Side Effects Analysis of Procedure Calls

    Handling the Effects of Parameters

    Whole Program Analysis

    Summary and Concluding Remarks

     

    Value Based Approach to Interprocedural Data Flow Analysis

    Program Model for Value Based Approaches to Interprocedural Data Flow Analysis

    Interprocedural Analysis Using Restricted Contexts

    Interprocedural Analysis Using Unrestricted Contexts

    Bounding Unrestricted Contexts Using Data Flow Values

    The Motivating Example Revisited

    Summary and Concluding Remarks

     

    SECTION III: Implementing Data Flow Analysis

    Implementing Data Flow Analysis in GCC

    Specifying a Data Flow Analysis

    An Example of Data Flow Analysis

    Implementing the Generic Data Flow Analyzer gdfa

    Extending the Generic Data Flow Analyzer gdfa

     

    APPENDICES:

    An Introduction to GCC

    About GCC

    Building GCC

    Further Readings in GCC

    Biography

    Uday Khedker, Amitabha Sanyal, Bageshri Sathe

    …provides a very decent and quite balanced coverage of the topic from a formal perspective. It is well written and nicely organized, containing many examples which definitely help to clarify the rather technical content. All the chapters end with a summary and concluding remarks, as well as bibliographic notes, pointing to further readings. This book also comes with a live web page…that contains slides with some additional material, [an updated] Errata section… and the analyzer software. This book includes an introduction to GCC, a rich list of references, and an index.

    --Zhjzhang Shen, Plymouth State University