TY - JOUR
T1 - Fast condensation of the program dependence graph
AU - Johnson, Nick P.
AU - Oh, Taewook
AU - Zaks, Ayal
AU - August, David I.
PY - 2013/6
Y1 - 2013/6
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=84880124492&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84880124492&partnerID=8YFLogxK
U2 - 10.1145/2499370.2491960
DO - 10.1145/2499370.2491960
M3 - Article
AN - SCOPUS:84880124492
SN - 1523-2867
VL - 48
SP - 39
EP - 49
JO - SIGPLAN Notices (ACM Special Interest Group on Programming Languages)
JF - SIGPLAN Notices (ACM Special Interest Group on Programming Languages)
IS - 6
ER -