Fast Condensation of the Program Dependence Graph [abstract] (ACM DL, PDF)
Nick P. Johnson, Taewook Oh, Ayal Zaks, and David I. August
Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), June 2013.
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 naive 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.