Page MenuHomePhabricator

Control Structure Analysis
Needs ReviewPublic

Authored by vaivaswatha on Feb 9 2016, 8:34 AM.

Details

Reviewers
hfinkel
Summary

This experimental patch 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.

Diff Detail

Event Timeline

vaivaswatha updated this revision to Diff 47323.Feb 9 2016, 8:34 AM
vaivaswatha retitled this revision from to Control Structure Analysis.
vaivaswatha updated this object.
vaivaswatha added a reviewer: hfinkel.
vaivaswatha added a subscriber: llvm-commits.

I just skimmed through it and made very quick comments, I haven't tried it yet.
Also, can you unittest this?

include/llvm/Analysis/ControlStructureAnalysis.h
1

This line looks to long, I guess you should run clang-format on the rest of the code as well.

Also please adapt the naming for the the LLVM coding conventions.

lib/Analysis/ControlStructureAnalysis.cpp
582

I'm not just what is the justification for the goats here, refactoring / restructuring shouldn't be out-of-reach.

603

s/lexicogrphaically/lexicographically/

1145

I think adding a continue just before this line would save the else and reduce the indentation level.

@joker.eph Thank you for the comments. I'll be happy to work on them (and take the patch to a good state for committing). However at the moment I'm looking for a broader approval that the code would be useful to the community and it would get in after its taken to a good state. I don't want to spend a lot of time reworking it and finally finding it to be not-useful and it not going in.