Data Flow Analysis

Data Flow Analysis: Theory and Practice

Published:
Content:
Author(s):
Free Standard Shipping

Purchasing Options

Hardback
$119.95 $95.96
ISBN 9780849328800
Cat# 2880
Add to cart
SAVE 20%
eBook (VitalSource)
$119.95 $83.97
ISBN 9780849332517
Cat# E2880
Add to cart
SAVE 30%
eBook Rentals
Other eBook Options:
 
 

Features

  • Addresses specification of data flow frameworks and the solution process
  • Presents generalizations of constant and dependent parts in flow functions, apart from the lattice theoretic modeling of data flow frameworks
  • Includes intermediate SSA representation of programs, which directly relate definition and use points of data for increased performance efficiency
  • Focuses on generic functional and value-based approaches, instead of presenting interprocedural methods specific to particular applications or frameworks
  • Builds suitable abstractions by emphasizing evolution of concepts
  • Provides bibliographic notes at the end of each chapter

Summary

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

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

Editorial Reviews

…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

Downloads / Updates

Resource OS Platform Updated Description Instructions
2880 Link.docx Cross Platform August 04, 2009 Author web site with additional materials click on http://www.cse.iitb.ac.in/~uday/dfaBook-web

 
Textbooks
Other CRC Press Sites
Featured Authors
STAY CONNECTED
Facebook Page for CRC Press Twitter Page for CRC Press You Tube Channel for CRC Press LinkedIn Page for CRC Press Google Plus Page for CRC Press Pinterest Page for CRC Press
Sign Up for Email Alerts
© 2014 Taylor & Francis Group, LLC. All Rights Reserved. Privacy Policy | Cookie Use | Shipping Policy | Contact Us