2016 LLVM Developers’ Meeting: N.Singhal “Reducing the Computational Complexity of RegionInfo”

—
Reducing the Computational Complexity of RegionInfo - Nandini Singhal

—
The LLVM RegionInfo pass provides a convenient abstraction to reason about independent single-entry-single-exit regions of the control flow graph. RegionInfo has proven useful in the context of Polly and the AMD GPU backend, but the quadratic complexity of RegionInfo construction due to the use of DominanceFrontier makes the use of control flow regions costly and consequently prevents the use of this convenient abstraction. In this work, we present a new approach for RegionInfo construction that replaces the use of DominanceFrontier with a clever combination of LoopInfo, DominanceInfo, and PostDominanceInfo. As these three analysis are (or will soon be) preserved by LLVM and consequently come at zero cost while the quadratic cost of DominanceFrontier construction is avoided, the overall cost of using RegionInfo has been largely reduced, which makes it practical in a lot more cases. Several other problems in the context of RegionInfo still need to be addressed. These include how to remove the RegionPass framework which makes little sense in the new pass manager, how to connect Regions and Loops better, and how we can move from a built-upfront-everything analysis to an on-demand analysis, which step-by-step builds only the needed regions. We hope to discuss some of these topics with the relevant people of the LLVM community as part of the poster session.

—