This paper presents a novel and faster algorithm for Static Control Part (SCoP) detection, a crucial step for compilers utilizing the polyhedral model to optimize imperative programming languages. The improved algorithm operates on the natural loops tree, a higher-level abstraction of the Control Flow Graph (CFG), to significantly reduce overall compilation time. Implemented in GCC 6.0, this algorithm was a prerequisite for enabling the isl schedule optimizer by default at optimization levels like -O3 -fprofile-use. Experimental results demonstrate a substantial reduction in compilation time for SCoP detection (e.g., from 7% to 0.3% on a large C++ application) and an increased ability to detect larger SCoPs (an average of 6.09 loops per SCoP compared to 2.59 previously), thus broadening the applicability and efficiency of polyhedral optimizations in industrial compilers without introducing prohibitive overheads.
Summarizing "SCoP Detection: A Fast Algorithm for Industrial Compilers"
Introduction to SCoPs (Static Control Parts): SCoPs are regions of code that can be effectively handled and optimized by polyhedral compilers. They typically contain regular control flow without exceptions, data-dependent conditionals, or side effects from function calls.
Challenges with Low-Level Languages: Compilers for low-level languages like C/C++ represent code using basic blocks and jumps, making it difficult to recognize high-level loop constructs for polyhedral optimization without incurring significant compilation time overhead.
Limitations of Previous SCoP Detection Algorithms:
Graphite's Original Algorithm: Operated on a very low-level CFG and dominator tree, leading to restrictive SCoP detection, often splitting sequences of loops into distinct SCoPs.
Polly's SESE Regions: While an improvement, its reliance on iterated dominance frontiers for Single Entry Single Exit (SESE) region discovery could lead to computationally expensive quadratic behavior in certain cases.
The New Faster SCoP Detection Algorithm:
Higher-Level Abstraction: The core improvement is operating on the "natural loops tree," a more abstract representation of the CFG, combined with dominance information. This representation is maintained with minimal cost between GCC's optimization passes.
Early Discarding: The algorithm quickly identifies and discards parts of the code that cannot be translated into the polyhedral model or cannot be profitably transformed, focusing analysis on relevant loop structures.
Focus on Loops: It prioritizes detecting SCoPs that contain loops, even if they are not "maximal" (the largest possible SCoP), as non-loop code within a maximal SCoP adds overhead without significant optimization benefits.
Conditions for a Valid SCoP: An SESE region is considered a valid SCoP if it meets strict criteria, including single entry/exit points, dominance properties, single-exit loops, affine scalar evolution for memory accesses and conditional expressions, representable statements, and signed integer induction variables.
SCoP Merging Capability: The algorithm can intelligently merge smaller SCoPs (e.g., adjacent loop nests) into larger, valid combined SCoPs, re-analyzing scalar evolutions within the new, extended region.
Implementation and Integration: The new algorithm has been implemented and integrated into GCC 6.0. Its efficiency was critical for enabling the isl schedule optimizer, a polyhedral optimization component, by default at common optimization levels (like -O3 -fprofile-use).
Experimental Results (Compilation Time):
On a large C++ application (Tramp3d-v4), the time spent in SCoP detection was drastically reduced from 7.0% to 0.3% of the overall compilation time.
When compiling GCC 6.0's source code, the total instruction count for SCoP detection dropped by an order of magnitude, from 1.5e10 to 6.7e8, demonstrating a 22.6x speedup.
The authors highlight that this near-zero overhead for SCoP detection is crucial for industrial compilers, as it's the only part of a polyhedral compiler that must scan the complete program.
Experimental Results (SCoP Size and Detection):
The new algorithm detects larger SCoPs on average, increasing from 2.59 loops per SCoP with the old Graphite algorithm to 6.09 loops per SCoP.
It now allows for the detection of SCoPs comprising adjacent outermost loops, which was not possible with the previous algorithm.
While the algorithm can detect single-loop SCoPs, the current implementation deliberately discards SCoPs with fewer than two loops, a choice that may be revisited in the future.
Key Takeaways: The new SCoP detection algorithm significantly improves compilation time and detects larger, more effective SCoPs by leveraging higher-level program representations. This enables the widespread and default use of polyhedral optimizations in industrial compilers without introducing undue performance overhead.
Future Work: Research avenues include developing heuristics to analyze SCoP shape for better polyhedral optimization selection and using profile information to focus SCoP detection on "hot paths" within a program.