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@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 (24.4 KB)