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 BasicBlocksCorrect.> 2. both of them have some kind of nested structures, so both a loop and > a region could have parent or childrensCorrect.> 3. both of them have a BasicBlocks(header of a loop and "entry" of a > region) that dominates all othersCorrect.> 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
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 BasicBlocksCorrect.> 2. both of them have some kind of nested structures, so both a loop and > a region could have parent or childrensCorrect.> 3. both of them have a BasicBlocks(header of a loop and "entry" of a > region) that dominates all othersCorrect.> 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
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
>
>
>
On 01/15/10 03:03, ether wrote:> hi,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.Hi ether, I think this should be implemented as a RegionFilter, that checks if a region contains a loop, and that can be asked for further information. In general I do not think this kind of analysis belongs to a region, but as you proposed some kind of filter could be applied. In the short term the passes who need this information could get it on their own.> 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.This would need some thoughts. Ideal I think we would not order them, but if a region changed, just reconstruct the loops that are in this region and if a loop changed just reconstruct the regions in this loop.> 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.Yes, I like this idea. So the basic design would be that we have some passes like: Maximal Region regarding an Analysis/Filter Minimal Region regarding an Analysis/Filter All Regions regarding an Analysis/Filter So a pass can ask the regionpass manager for a specific kind of regions. It is than just invoked for regions, that fulfill this requirement. Tobias
> I think this should be implemented as a RegionFilter, that checks if a> region contains a loop, and that can be asked for further information. > In general I do not think this kind of analysis belongs to a region, but > as you proposed some kind of filter could be applied. In the short term > the passes who need this information could get it on their own. > >> 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. > This would need some thoughts. Ideal I think we would not order them, but if > a region changed, just reconstruct the loops that are in this region and > if a > loop changed just reconstruct the regions in this loop.Imo, a loop is simply a special kind of region, so a "filter" is perhaps the way to go if you are interested in loops. Regions containing loops will have to be inspected using the PST.>> 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. > Yes, I like this idea. > So the basic design would be that we have some passes like: > Maximal Region regarding an Analysis/Filter > Minimal Region regarding an Analysis/Filter > All Regions regarding an Analysis/Filter > So a pass can ask the regionpass manager for a specific kind of regions. > It is than just invoked for regions, that fulfill this requirement.If you want to be able to manipulate specific regions you can have a generic region class, and then sub classes for loop, if, unstructured etc. That way it is easy to ask for the body of a loop or the true or false regions of an if-region. It will also allow you to have different kinds of loops for/do-while, but still treat them in a uniform way in some cases. - Jan
On 01/20/10 18:16, Jan Sjodin wrote:>> I think this should be implemented as a RegionFilter, that checks if a > >> region contains a loop, and that can be asked for further information. >> In general I do not think this kind of analysis belongs to a region, but >> as you proposed some kind of filter could be applied. In the short term >> the passes who need this information could get it on their own. >> >>> 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. >> This would need some thoughts. Ideal I think we would not order them, but if >> a region changed, just reconstruct the loops that are in this region and >> if a >> loop changed just reconstruct the regions in this loop. > > Imo, a loop is simply a special kind of region, so a "filter" is perhaps the way to > go if you are interested in loops. Regions containing loops will have to be inspected > using the PST.Except loops that have multiple exits. they are not necessarily (single entry single exit) region, if the exists do not jump to the same exit bb.
>> Imo, a loop is simply a special kind of region, so a "filter" is perhaps the way to >> go if you are interested in loops. Regions containing loops will have to be inspected >> using the PST. > > Except loops that have multiple exits. they are not necessarily (single > entry single exit) region, if the exists do not jump to the same exit bb.Yes, my assumption was to classify structured loops, but that does not exclude unstructured regions that contain unstructured loops.
On 01/21/10 20:42, Jan Sjodin wrote:>>> Imo, a loop is simply a special kind of region, so a "filter" is perhaps the way to >>> go if you are interested in loops. Regions containing loops will have to be inspected >>> using the PST. >> >> Except loops that have multiple exits. they are not necessarily (single >> entry single exit) region, if the exists do not jump to the same exit bb. > > Yes, my assumption was to classify structured loops, but that does not exclude unstructured > regions that contain unstructured loops.Can you explain your definition of structured/unstructured loops/regions. A structured loop does have just one exit? Does a unstructured region have multiple exits, or it just contains unstructured code? Tobi
On 01/21/10 20:42, Jan Sjodin wrote:>>>> Imo, a loop is simply a special kind of region, so a "filter" is perhaps the way to >>>> go if you are interested in loops. Regions containing loops will have to be inspected >>>> using the PST. >>> >>> Except loops that have multiple exits. they are not necessarily (single >>> entry single exit) region, if the exists do not jump to the same exit bb. >> >> Yes, my assumption was to classify structured loops, but that does not exclude unstructured >> regions that contain unstructured loops. > > Can you explain your definition of structured/unstructured loops/regions.Unstructured regions in this case means there is control flow in the region that is not interesting to look into or classify any further.> A structured loop does have just one exit?When you say "structured loop" I believe that means it has a single exit and does not use break or goto to exit the loop. A loop contained within a region may have multiple exits. If you need to reason about these kinds of loops, you can create a special kind of region for them. If they are not interesting, then you would simply treat them as unstructured SESE-regions. This mostly relates to creating convenience functions around regions so that you can easily extract the body, exit-edge[s], then/else portions of contitionals etc.> Does a unstructured region have multiple exits, or it just contains > unstructured code?It just contains unstructured code, that cannot be decomposed into smaller SESE-regions. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100122/3adb063d/attachment.html>