[llvm-dev] Control Structure Analysis

[Tobias Grosser via llvm-dev]

On 02/09/2016 05:40 PM, Vaivaswatha Nagaraj via llvm-dev wrote:
> Hi,
>
> I have an experimental patch that implements an algorithm to detect
> control structures in the CFG, such as If-Then, If-Then-Else, Self-Loop
> etc. This analysis is kind of an extension of interval/region analysis
> to detect more than just loops. The algorithm and data structures used
> in this implementation are based on the description given in "Advanced
> Compiler Design and Implementation" -- Steven. S. Muchnik (Section 7.7
> "Structural Analysis"). The result of the analysis is a tree called the
> control-structure-tree of the control flow graph of the function begin
> analysis.
>
> Typical uses for this analysis are:
> 1. Perform control flow transformations based on the control structure
> tree. Some control transformations are easier to reason about using this
> tree.
> 2. IR to source transformations. Detecting source level constructs in
> the CFG is usually useful in generating high level code from an already
> reduced IR.
> 3. Similar to the uses of interval/region analysis, control structure
> analysis also can be used to speed up data flow analyses.
>
> The code, although tested and used internally, needs further work:
> 1. Make it an actual LLVM analysis.
> 2. Provide a richer set of APIs for updates.
> 3. Improve analysis time.
>
> I'm not sure how useful such an analysis would be to the community. If
> people find it to be useful, I'm open to working on it further and
> submitting it. Any feedback will be appreciated.
>
> http://reviews.llvm.org/D17031

You might also have a look at RegionInfo, which provides similar 
information.

Best,
Tobias