Fast condensation of the program dependence graph

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

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)
Title of host publicationPLDI 2013 - Proceedings of the 2013 ACM SIGPLAN Conference on Programming Language Design and Implementation
Pages39-49
Number of pages11
DOIs
StatePublished - 2013
Event34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2013 - Seattle, WA, United States
Duration: Jun 16 2013Jun 19 2013

Publication series

NameProceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

Other

Other34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2013
Country/TerritoryUnited States
CitySeattle, WA
Period6/16/136/19/13

All Science Journal Classification (ASJC) codes

  • Software

Keywords

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

Fingerprint

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

Cite this