region pass - new pass for llvm

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( 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(, 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
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

  • 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


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

region.7z (24.4 KB)

How is the patch compressed? I don’t know how to open the file with .7z suffix.


That looks like something from 7-zip ( 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!


There is p7zip which can extract this on Linux (and its probably been
ported to the Mac).

However for this particular patch 7z is a bad choice, even bzip2 works

25020 region.7z
24871 region.patch.bz2
27507 region.gz

Best regards,

There is p7zip which can extract this on Linux (and its probably been
ported to the Mac).

Yeah, there is one available from macports.

In any case - .bz2 attached.

region.patch.bz2 (24.3 KB)

hi Edwin,

thanks for the advice.

best regards