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

[Tobias Grosser]

On 02/06/2014 09:14 PM, Paul Vario wrote:
> Hi Tobias,
>
>           Thanks a lot for the detailed reply. I am working on several new
> optimizations for OpenCL kernels for a DSP architecture. The project itself
> has an NDA associated with it, so I cannot go into more details, but the
> source will be open to public after completion. One of the first steps is
> to serialize the work-items in a work-group (e.g., insert nested loops
> around REGIONs in between barriers). At this point, I thought I should
> implement a full-featured structural analysis, but some one in my team
> suggested to first explore what was already in the LLVM. That's what lead
> me to the RegionInfo class. If it's not much trouble, could you send the
> draft to my forum email? Also, are you aware of any plan on having the
> interval/structural analysis supported in LLVM. Thanks again.

Maybe this is interesting to you:

lib/Transforms/Scalar/StructurizeCFG.cpp

> P.S. One thing I need to find out from reading the implementation is why a
> sequence of basic blocks do not get to form a region as a whole.

A sequence of basic blocks can form a region. The reason the RegionInfo 
does not form such reason is that there is no canonical way to form such 
regions. Hence, RegionInfo is only forming minimal regions, which can 
then be easily joined to larger reasons by connecting sequences of them 
(e.g. using the expandRegion()).

Btw, depending how complex your transformations will be, you might also 
be interested in polly.llvm.org or other automatic transformation in the 
area of automatic GPU/accelerator code generation. Those won't be 
finished solutions, but the frameworks/algorithms that exist there may 
allow to develop optimizations for your hardware a lot faster.

Tobi