The program dependence graph (PDG) is a program representation that combines control flow and data flow information into a single structure. The authors cite previous work on control dependence graphs, which represent control flow without data flow, and on data dependence graphs, which show data flow without control flow. The PDG combines data flow and control flow information into a single structure that is useful for a variety of program transformations and optimizations. Nodes in the PDG represent statements, expressions, and predicates, and edges represent data values passed from one expression to another and control conditions that influence the order of execution.
The authors start by showing how to construct a PDG from the control and data flow information in the original program. They then describe some variants of the PDG that may be more convenient for different source languages or various applications. The next section shows some applications of the PDG. The authors show how it can be used to find parts of a program that can be made parallel, to do code motion and loop fusion optimizations, and to find the parts of a program that can affect a given variable, which is useful in debugging.
Finally, they discuss incremental optimization, which involves updating the PDG as an optimization is made, rather than having to examine the whole program again. For example, if an optimization removes some dead code, the data dependencies for that dead code can be removed directly. They claim that this procedure is much faster than the conventional equivalent.
The PDG certainly appears to be a powerful mechanism that unifies a broad class of program analyses and transformations. My primary concern is that it also appears to be too complicated to construct and very large; the authors’ estimate is 50 percent larger than the equivalent triples although it seems to me that their estimate is conservative. Nonetheless, they sketch out some impressive results, and we will probably be seeing many more PDG applications in the near future.
