[LLVMdev] region pass - new pass for llvm

[Evan Cheng]

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>