TY - GEN
T1 - Fast condensation of the program dependence graph
AU - Johnson, Nick P.
AU - Oh, Taewook
AU - Zaks, Ayal
AU - August, David I.
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
KW - Demand-driven analysis
KW - Dependence analysis
KW - Program Dependence Graph
KW - Strongly connected components
UR - http://www.scopus.com/inward/record.url?scp=84883126126&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84883126126&partnerID=8YFLogxK
U2 - 10.1145/2491956.2491960
DO - 10.1145/2491956.2491960
M3 - Conference contribution
AN - SCOPUS:84883126126
SN - 9781450320146
T3 - Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)
SP - 39
EP - 49
BT - PLDI 2013 - Proceedings of the 2013 ACM SIGPLAN Conference on Programming Language Design and Implementation
T2 - 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2013
Y2 - 16 June 2013 through 19 June 2013
ER -