[LLVMdev] Make LoopBase inherit from "RegionBase"?

[Jan Sjodin]

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