Table of Contents
Tutorial Techniques to Improve the Scalability and Precision of Data Flow Analysis
Data Flow Analysis
Extensions and improvements
Components of data flow
Outline: Scalability and Precision
Interaction: Scalability and Precision
How to Scale
Equation System Sparse: reducing the number of points - N
PPT Slide
Def-Use chains - first sparse [Reif & Tarjan, SIAM JC’81]
SSA (SSA Based def use chains) [Cytron,Ferrante, Rosen, Wegman, Zadeck, TOPLS’91]
Sparse Evaluation Graphs [Choi, Cytron, Ferrante, POPL’91]
Dependence Flow Graph [Johnson & Pingali, PLDI’93]
Interprocedural Analysis
Outline: Scalability and Precision
Scalability: solver
Slotwise - Sparse scheduling [Dhamdhere, Rosen, Zadeck, PLDI’92]
Slotwise - example
Demand Driven - goal directed
Demand driven approaches
Function Reversal Framework [Duesterwald, Gupta, Soffa, POPL’95,TOPLS’97]
Example: Copy Constant Propagation (CCP)
Reversal Framework
Experimental Results
Demand driven through graph reachability [Horwitz, Reps, Sagiv, FSE’95]
Possibly uninitialized variables
Experimental results
Parititioning
Partitioning approaches
Partitioning by types [Ruf, POPL’97]
Types - points-to analysis
Experiments - C programs
Partitioning by related statements [Zhang, Ryder, Landi, FSE’96]
PE - based on equality, *, ptr struct fields
Experiments - using components
Interprocedural Partitioning: Points-to
Relevant Context Inference: points-to [Chatterjee, Ryder, Landi, POPL’99]
Example
Efficient Points-to [Liang & Harrold, FSE’99]
Experiments to evaluate precision
Outline: Scalability and Precision
Precision - paths and names
Improve precision - paths
How to exclude infeasible paths?
Qualified Data Flow [Holly & Rosen, TSE’81]
Qualified Data Flow
Example
Final graph - D
Evaluation
Demand driven to mark infeasible paths [Bodik, Gupta, Soffa, FSE’97]
Feasible reaching definitions
Example:
Evaluation
Path sensitivity
Diluted Path Sensitivity
Path separation [Ammons & Larus, PLDI’98]
Evaluation: constant propagation
Outline: Scalability and Precision
Improved precision: name space
Naming the value
VNG: example
Constructing the VNG
Evaluation
Interprocedural Analysis
Future Directions
|