This paper introduces a fast algorithm for Static Control Part (SCoP) detection in industrial compilers, specifically implemented in GCC 6.0. SCoP detection identifies regions of code suitable for optimization within the polyhedral model. Addressing the performance overhead of previous methods that operate on low-level Control Flow Graph (CFG) representations, the proposed algorithm leverages the "natural loops tree," a higher-level abstraction. This approach significantly reduces overall compilation time; on a large C++ application, SCoP detection overhead dropped from 7% to 0.3%. Additionally, the new algorithm identifies larger SCoPs (averaging 6.09 loops per SCoP on Polybench, up from 2.59), allowing for more comprehensive polyhedral transformations. These improvements enable polyhedral optimizations to be turned on by default in compilers without incurring significant performance penalties.
Summarizing the Transcript: SCoP Detection in Industrial Compilers
The Challenge of Loop Optimization (Introduction): While languages like Fortran simplify loop optimization, low-level languages like C/C++ present difficulties due to their low-level Intermediate Representation (IR), requiring compilers to spend extra time recognizing high-level loop constructs for optimization.
Static Control Parts (SCoPs): SCoPs are code regions suitable for polyhedral model optimization. They typically exclude complex control flow like exceptions or data-dependent conditionals and require affine memory access patterns. The goal is fast SCoP detection for default optimization levels (e.g., -O2, -O3), aiming for minimal overhead on functions without relevant loops.
Limitations of Previous Algorithms:
Graphite: Operated on low-level CFG and dominators, limiting SCoP size and preventing the combination of adjacent loops into a single SCoP.
Polly: Based on Single Entry Single Exit (SESE) regions, which could lead to quadratic time complexity in some cases due to reliance on iterated dominance frontiers.
"Maximal SCoPs" Issue: Attempts to find the absolute largest SCoP often included non-loop code, adding unnecessary compilation overhead without significant optimization benefits.
The New, Faster SCoP Detection Algorithm:
Higher-Level Abstraction: The core improvement is operating on the "natural loops tree" representation of the CFG, combined with dominance information. This representation is efficiently maintained by GCC's middle-end, incurring zero initial cost.
Inductive Traversal: The algorithm traverses the loop tree by induction, recursively analyzing and merging valid loop nests and adjacent loops.
Early Pruning: It quickly discards invalid or unprofitable loop structures early in the process, focusing analysis only on potentially optimizable regions.
Targeted SCoPs: Unlike previous "maximal" approaches, this algorithm deliberately excludes regions without loops, even if they could be part of a larger SCoP, to reduce overhead.
SCoP Validity Conditions: For a region to be a valid SCoP, it must meet several criteria, including single entry/exit, specific dominance/post-dominance relationships, single exits for all internal loops, affine scalar evolution for memory accesses, representable statements (e.g., integer operations, pure function calls), and signed integer induction variables.
Significant Performance Gains:
Compilation Time: On a large C++ application (Tramp3d-v4), the SCoP detection overhead was reduced from 7.0% to 0.3% of total compilation time.
Industrial Compiler Impact: For the entire GCC 6.0 source code, the cumulative overhead of SCoP detection dropped from 0.24% to 0.01%, representing a 22.6x speedup.
Larger SCoPs: On the Polybench suite, the new algorithm detected an average of 6.09 loops per SCoP, significantly more than the old algorithm's 2.59, enabling more extensive polyhedral optimizations. While some individual benchmarks showed a slight increase in SCoP detection time (due to analyzing larger SCoPs), the overall benefit is substantial.
Conclusion and Future Work: The new algorithm's speed and ability to detect larger SCoPs, by leveraging higher-level program representations, make it feasible to enable polyhedral optimizations by default in industrial compilers. Future work includes developing heuristics to further limit SCoP size for optimal compilation time/performance and using profile information to focus optimizations on "hot paths" of the program.