Data Flow Analysis Theory and Practice

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