Data Flow Analysis : Theory and Practice book cover
1st Edition

Data Flow Analysis
Theory and Practice

ISBN 9780849328800
Published March 27, 2009 by CRC Press
395 Pages 154 B/W Illustrations

SAVE ~ $30.00
was $150.00
USD $120.00

Prices & shipping based on shipping country


Book Description

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

Table of Contents


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


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



An Introduction to GCC

About GCC

Building GCC

Further Readings in GCC

View More


…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