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

[Paul Vario]

Hi Tobi,

       I have one additional question about the RegionInfo::isRegion
function. In the second case (i.e. Entry dominates Exit),  why is checking
the following two conditions are equivalent to checking it's a refined
region:

For any BB in DF(exit), 1)  BB should be in DF(entry)
                                   2)  BB reachable only from entry through
a path passing exit.

       I.e., why is checking these two conditions is equivalent to ensure
single-entry, single-exit in the sense of Refined Region.

Best Regards,
Paul


On Thu, Feb 6, 2014 at 3:40 PM, Tobias Grosser <tobias at grosser.es> wrote:

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140627/b93f2155/attachment.html>