llvm dev - Feb 2016 - Control Structure Analysis

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

  - Vaivaswatha
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160209/cf1d8b02/attachment.html>

On 09.02.2016 11:40, 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.
Do you know the StructurizeCFGPass? We use it in AMDGPU to simplify the 
control flow which allows a simpler lowering pass. GPUs run "waves" of
"threads", where the physical instruction pointer is shared by all 
threads of a wave, even though threads can take different paths through 
control structures. An exec mask is used to disable threads that should 
currently be inactive (e.g. while running through the "wrong" half of
an
if-else).

I haven't thought about it at all, but it's conceivable that a thorough 
analysis could help produce better code in some complicated cases.

Cheers,
Nicolai
> http://reviews.llvm.org/D17031
>
>    - Vaivaswatha
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/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