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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100228/ef880b62/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: region.7z
Type: application/octet-stream
Size: 25020 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100228/ef880b62/attachment.obj>
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-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100304/8e624870/attachment.html>
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