Fast condensation of the program dependence graph

Nick P. Johnson, Taewook Oh, Ayal Zaks, David I. August

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


Aggressive compiler optimizations are formulated around the Program Dependence Graph (PDG). Many techniques, including loop fission and parallelization are concerned primarily with dependence cycles in the PDG. The Directed Acyclic Graph of Strongly Connected Components (DAGSCC) represents these cycles directly. The naïve method to construct the DAGSCC first computes the full PDG. This approach limits adoption of aggressive optimizations because the number of analysis queries grows quadratically with program size, making DAGSCC construction expensive. Consequently, compilers optimize small scopes with weaker but faster analyses. We observe that many PDG edges do not affect the DAGSCC and that ignoring them cannot affect clients of the DAGSCC. Exploiting this insight, we present an algorithm to omit those analysis queries to compute the DAGSCC efficiently. Across 366 hot loops from 20 SPEC2006 benchmarks, this method computes the DAGSCC in half of the time using half as many queries.

Original languageEnglish (US)
Pages (from-to)39-49
Number of pages11
JournalACM SIGPLAN Notices
Issue number6
StatePublished - Jun 2013

All Science Journal Classification (ASJC) codes

  • General Computer Science


  • Demand-driven analysis
  • Dependence analysis
  • Program Dependence Graph
  • Strongly connected components


Dive into the research topics of 'Fast condensation of the program dependence graph'. Together they form a unique fingerprint.

Cite this