 |
The Value Evolution Graph and Its Uses in Memory Reference Analysis
Silvius Rus Dongmin Zhang, Lawrence Rauchwerger
The Value Evolution Graph (VEG) is a symbolic representation of the flow of scalar and array values within a program. These values, and the relations among them are used to compare memory reference indices and prove predicate implications, which leads to solutions of symbolic data dependence equations. For instance, when we intersect two memory location sets, we compare their values using VEG information. If they belong to disjoint ranges, the result of the intersection is the empty set.
Example of control flow disambiguation using the Value Evolution Graph.
The scope of a Value Evolution Graph is either a loop or a supbrogram. Inner scopes are represented as separate value evolution graphs and abstracted into edges at the outer scope levels. This makes the representation scalable to very large programs.
Value Evolution Graphs provide the necessary infrastructure for solving queries on symbolic value ranges and for symbolic predicate inference. The Value Evolution Graphs can be pruned based on assumptions, which leads to tighter ranges (thus more accurate information) than abstract interpretation methods.
For more details you can read the papers listed below or follow the presentation given in Juan-les-Pins, France, at PACT 2004. You can also view (Encapsulated PostScript files) partial VEGs following variable LSTTRK for loops EXTEND_do400 and EXTEND_do300 in program TRACK from the PERFECT benchmark suite.
Publications
Silvius Rus, Dongmin Zhang, Lawrence Rauchwerger, "The Value Evolution Graph and its Use in Memory Reference Analysis," In Proc. IEEE Int.Conf. on Parallel Architectures and Compilation Techniques (PACT), pp. 243-254, Antibes Juan-les-Pins, France, Sep 2004.
Proceedings(ps, pdf, abstract)
Silvius Rus, Dongmin Zhang, Lawrence Rauchwerger, "Automatic Parallelization Using the Value Evolution Graph," In Wkshp. on Lang. and Comp.
for Par. Comp. (LCPC), West Lafayette, Indiana, Sep 2004.
Proceedings(ps, pdf, abstract)