[LLVMdev] The implementation algorithm behind LLVM's RegionInfo class

[Tobias Grosser]

On 02/06/2014 04:28 PM, Paul Vario wrote:
> Hi fellows,
>
>       I am writing to ask what is the algorithm implemented in LLVM's
> RegionInfo.h/cpp. In the header file "RegionInfo.h", it says "Calculates a
> program structure tree built out of single entry single exit regions
> (defined in a 1994 paper called "The Program Structure Tree"). ... ... The
> algorithm to calculate these data structures however is COMPLETELY
> DIFFERENT, as it takes advantage of existing information already available
> ... ...". Does anyone know any papers talking about the exact
> implementation? Also, how is the RegionInfo class related to a general
> interval analysis? Thanks a lot.

Hi Paul,

I should probably reply. I implemented this algorithm four years ago.

Yes, this algorithm is on purpose different. I implemented it after 
investigating previous approaches. There are two main reasons for the 
difference:

1) The Program Structure Tree does not access so-called refined regions

Refined regions are program regions that do not have a single entry and 
a single exit edge, but can be transformed into such a region very 
easily. My experience was, that most programs have a large number of 
refined regions which we want to detect.

2) Use of the dominator tree

When I first came to the mailing list and asked for advice people 
(including Chris) strongly suggested to rely on existing analysis as 
much as possible. The RegionInfo pass does this by using the 
DominatorTree as well as a couple of other analysis. My measurements
at that time have shown that building the RegionTree itself is in 
average twice as fast as building the dominator tree. The other 
necessary analysis have taken time comparable to a dominator tree 
construction. The use of DominanceFrontier in the RegionInfo tree has
been a point criticized because this analysis is normally not used in 
LLVM (and needs to be built just for RegionInfo). Also the dominance 
frontier is in exceptional cases expensive to construct. On the other 
side, the analysis has shown useful not only for Polly, but a couple of 
other projects (R600 backend?, some OpenCL vectorizers?). Still, if we 
find a way to remove the reliance on the DomFrontier while still being 
able to detect refined regions, this would be very valuable.

I never bothered to publish the Region Info paper, but I have an 
unfinished draft that I am happy to send you. Also, if the documentation
in the source code is too sparse, please let me know and I add the 
missing information.

Out of interest, why are you interested in the RegionInfo implementation?

Cheers,
Tobias