[LLVMdev] region pass - new pass for llvm

[Jim Grosbach]

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