[LLVMdev] Make LoopBase inherit from "RegionBase"?
jan_sjodin at yahoo.com
Tue Jan 12 15:56:57 PST 2010
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
----- 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,
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
>> I think this is the best way to add region analysis. I must admit this
>> 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?
> i just implementing the skeleton of Region/RegionInfo like LoopBase and
> LoopInfoBase 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
> 2. both of them have some kind of nested structures, so both a loop and
> a region could have parent or childrens
> 3. both of them have a BasicBlocks(header of a loop and "entry" of a
> region) that dominates all others
> and the Region class will have the most stuffs very similar in LoopBase,
> like: ParentRegion, SubRegions, Blocks, getRegionDepth(),
> 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:
Detect the regions and print the regions tree. Try it with:
opt -regions -analyze file.bc
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.
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
More information about the llvm-dev