[LLVMdev] region pass - new pass for llvm

[ether zhhb]

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>