[LLVMdev] Make LoopBase inherit from "RegionBase"?

[ether]

hi,

about region class, i think provide some method to extract the top level 
loop from a given region is useful in polly(our polyhedral optimization 
framework), because the we are only doing optimization on the region 
with loop.

and a long term consideration about "region pass":

if we want to integrate region analysis and optimization framework into 
llvm,  i think we can use an approach that similar to loop analysis and 
optimization: write a class "regionpass" inherit from "pass", and the 
corresponding pass manger "RegionPassManager". (a kind of function pass)
if we follow this approach, we need to push the region pass manager into 
the llvm pass manager stack.
the first question of this approach is, whats the relationship between 
"loop pass manager" and "region pass manager"?

way 1: make region pass manager below loop pass manager in the stack

pass manager stack:

bb pass manager <---top
loop pass manager
region pass manager
function pass manager
... <---bottom

in this way the region hierarchy need to be reconstruct when a loop 
transform change it.

way 2: make region pass manager above loop pass manager in the stack

pass manager stack:

bb pass manager <---top
region pass manager
loop pass manager
function pass manager
     ... <---bottom

in this way the loop hierarchy need to be reconstruct when a region pass 
change it.

now we need to choose a way to minimize the loop reconstruction or 
region reconstruction. i think that the chance that a region transform 
affect the loop structure is smaller, so maybe way 2 is better.


at last, i have some idea about finding a interesting region: (maybe 
make the region analysis too complex)

we can introduce some thing like "region filter" that determine the 
property of a region, the region filter will like a "pass", which can 
run on an instruction at a time, a basic block at a time, or even a sub 
region at a time, then we can write a "filter manager" like "pass 
manager " to stream the filtering process, so that we can promote the 
the performance of the region finding process.

comment and suggestion is appreciate.

best regards
--ether


On 2010-1-13 7:56, Jan Sjodin wrote:
> Why not use the "standard" algorithm for detecting SESE-regions and building a program structure tree?
> It should handle everything you want. It also becomes much simpler to specify a connected SESE-region
> by entry/exit edges, while a disconnected region is specified by entry/exit blocks. Only defining regions on
> blocks is not enough to be able to quickly determine how to replace/move a region in a CFG.
>
> The algorithm can be found in this paper:
> The Program Structure Tree: Computing Control Regions in Linear Time
> by Richard Johnson ,  David Pearson , KeshavPingali
>
> - Jan
>
> ----- Original Message ----
> From: Tobias Grosser<grosser at fim.uni-passau.de>
> To: ether<etherzhhb at gmail.com>
> Cc: LLVM Developers Mailing List<llvmdev at cs.uiuc.edu>
> Sent: Tue, January 12, 2010 12:59:45 PM
> Subject: Re: [LLVMdev] Make LoopBase inherit from "RegionBase"?
>
> On 01/08/10 14:20, ether wrote:
>    
>> sorry that i forgot to change the subjuect
>>
>>
>> hi all,
>>      
> Hi ether,
>
> now a kind of more complete answer.
>
>    
>> On 2010-1-7 0:11, John Mosby wrote:
>>      
>>> In LLVM we could add support for generalized CFG regions and
>>> RegionPasses. A region is a part of the CFG. The only information we
>>> have is, that it has one entry and one exit, this it can be optimized
>>> separately.
>>> I think this is the best way to add region analysis. I must admit this
>>> approach
>>> helps me on another, similar project I'm working on in parallel (no
>>> pun intended).
>>> Tobias, is this how you are architecting your region analysis already?
>>>
>>> John
>>>
>>>        
>> i just implementing the skeleton of Region/RegionInfo like LoopBase and
>> LoopInfoBase[1] in the llvm existing codes, and found that theres lots
>> of common between "Region" and "Loop":
>>
>> 1. both of them are consist of several BasicBlocks
>>      
> Correct.
>
>    
>> 2. both of them have some kind of nested structures, so both a loop and
>> a region could have parent or childrens
>>      
> Correct.
>
>    
>> 3. both of them have a BasicBlocks(header of a loop and "entry" of  a
>> region) that dominates all others
>>      
> Correct.
>
>
>    
>> and the Region class will have the most stuffs very similar in LoopBase,
>> like: ParentRegion, SubRegions, Blocks, getRegionDepth(),
>>      
> Correct.
>
>    
>> getExitBlock(), getExitingBlock() ......
>>      
> This might need some thoughts,
>
>
>    
>> so, could us just treat "Loop" as some kind of general "Region" of
>> BasicBlocks, and make Loop and Region inherit from "RegionBase"?
>>      
> I would like to do so, as I like the structure of this approach.
> However until now my pass was written on the side, as a proof of concept.
>
> I wrote two Passes:
>
> 1. Regions
> Detect the regions and print the regions tree. Try it with:
> opt -regions -analyze file.bc
>
> 2. RegionsWithoutLoops
> Find the maximal regions that do not contain any loops. Try it with:
> opt -regions-without-loops file.bc
> opt -view-regions-without-loops file.bc (needs graphviz)
>
> Both ATM only work on BasicBlocks. However I have seen the patches in
> your sandbox and I really like the idea to keep the analysis general.
>
> If you are interested you could have a look at my sandbox (not yet well
> documented and cleanly formatted).
>
> We might want to think about, how to merge our work.
>
> Tobi
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu          http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>