[LLVMdev] region pass - new pass for llvm

Jim Grosbach
2010-03-04T19:38:31Z

That looks like something from 7-zip (http://www.7-zip.org/). Ether, can you
re-send either as a plain-text attachment, or if you need to use an archive,
.zip or .tar.gz so it's a bit more standard for those of us not working on a
Windows platform? Thanks!

-Jim


On Mar 4, 2010, at 11:15 AM, Evan Cheng wrote:

> How is the patch compressed? I don't know how to open the file with .7z
suffix.
>
> Evan
> On Feb 27, 2010, at 10:12 PM, ether zhhb wrote:
>
>> hi all,
>>
>> The patch in the attachment add a new pass - region pass to the llvm
system. A region pass is similar to a loop pass, all of them execute on a group
of BasicBlocks at one time, but it operate on a single entry single exit region,
not the nature loop.
>>
>> The original purpose to add such a pass to llvm system is to allow us
find out the static control part (SCoP) for the polyhedral optimization
framework(http://wiki.llvm.org/Polyhedral_optimization_framework) for llvm, but
we think the region pass may help for others llvm developer, so we try to commit
these code to llvm. hope it is not too late.
>>
>> here is some introduction to "region" class written by
grosser(grosser at fim.uni-passau.de), the author of the region detection pass.
>>
>>
>>  A region is a connected subgraph of a control flow graph that has
exactly
>>  two connections to the rest of the graph.
>>  The easiest definition of a region is a region connected with the CFG
>>  by two edges, an entry edge and an exit edge. Such a region is called
>>  simple.
>>  However there also exist regions, that have several entry and exit
edges,
>>  but that can be transformed to a region with a single entry and exit
edge by
>>  inserting merge basic blocks. These regions are called refined
regions.
>>
>>  A region R (simple or refined) has these attributes:
>>
>>  * One entry basic block "entry" (part of the region)
>>  * One exit basic block "exit" (not part of the region)
>>
>>  There exists always one entry basic block, where all edges entering
the
>>  region end. This entry basic block is always part of the region. By
>>  inserting a basic block merging all entry edges before the entry basic
>>  block, a single entry edge can be created.
>>  There also exists always one exit basic block, where all edges leaving
the
>>  region end. This basic block is never part of the region. By inserting
a
>>  merge basic block before the exit basic block, a single exit edge can
be
>>  created.
>>
>>  * Every basic block BB in R:
>>    * is dominated by "entry"
>>    * is postdominated by "exit"
>>    (Not enough to check, if BB is part of R)
>>
>>  * "exit" always postdominates "entry"
>>  * "entry" may dominate "exit"
>>
>>  * An edge (a,b) is part of the region if both a and b are part of the
region
>>    or if a is part of the region and b is the exit node.
>>
>>  * A region is canonical, if it cannot be constructed by combining
smaller
>>    regions.
>>
>>  Example:
>>
>>  CFG:   1
>>        / |
>>       2   |
>>      / \   3
>>     4   5  |
>>     |   |  |
>>     6   7  8
>>      \  | /
>>       \ |/       region A: 1 -> 9 {1,2,3,4,5,6,7,8}
>>         9        region B: 2 -> 9 {2,4,5,6,7}
>>
>>  One region A is the parent of B is B is completely contained in A (as
in the
>>  example), whereas canonical regions either do not intersect at all or
one is
>>  the parent of the other.
>>  Therefore a tree, called program structure tree, can be built out of
the
>>  regions by using this relation.
>>
>> --best regards
>> ether <region.7z>_______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev