The program dependence graph and its use in optimization

Analysis

Why This Paper Matters

This paper introduced the program dependence graph (PDG), a seminal intermediate representation that unified data and control dependences. Before the PDG, compilers treated data flow and control flow separately, making optimizations like vectorization cumbersome and error-prone. By making control dependences explicit and symmetric to data dependences, the PDG allowed a single graph traversal to perform many optimizations, dramatically simplifying compiler design.

The PDG also pioneered incremental optimization, where transformations update only the affected dependences rather than reanalyzing the entire program. This concept is crucial for modern just-in-time compilers and interactive development environments where rapid feedback is needed. The paper's ideas directly influenced later work on static single assignment (SSA) form, dependence-based program slicing, and automatic parallelization.

Technical Contributions

• Control dependence formalization: Derives control dependences from the control flow graph, capturing essential control relationships without extraneous flow information.
• Unified dependence graph: Combines data and control dependences into a single PDG, enabling uniform handling of transformations.
• Single-walk optimization: Demonstrates that a single traversal of PDG dependences suffices for many optimizations, reducing algorithmic complexity.
• Incremental optimization: Introduces a method to update dependences incrementally after transformations like branch deletion or loop unrolling, avoiding full reanalysis.
• Vectorization via PDG: Shows that vectorization can be performed uniformly on both control and data dependences, simplifying a previously complex transformation.

Results

The paper does not present quantitative performance results or benchmarks. Instead, it provides conceptual and algorithmic contributions, showing that the PDG can express optimizations more naturally and efficiently than prior representations. The key result is that a single walk of the PDG suffices for optimizations that previously required separate passes for data and control flow. The incremental approach is illustrated with examples of branch deletion and loop unrolling, demonstrating reduced reanalysis scope.

Significance

The PDG became a cornerstone of compiler research and practice. It directly influenced the development of program slicing, where dependence graphs are used to extract program fragments relevant to a given computation. The concept of explicit control dependences is now standard in modern compilers (e.g., LLVM's use of dependence analysis). The paper's ideas on incremental optimization anticipate modern just-in-time compilation techniques. With over 3000 citations, it remains a highly influential work in programming languages and compiler optimization.