[LLVMdev] region pass - new pass for llvm
ether zhhb
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(gro...@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
Evan Cheng
ether <region.7z>_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Jim Grosbach
-Jim
Török Edwin
> 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!
>
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
better!
25020 region.7z
24871 region.patch.bz2
27507 region.gz
Best regards,
--Edwin
Anton Korobeynikov
> ported to the Mac).
In any case - .bz2 attached.
--
With best regards, Anton Korobeynikov
Faculty of Mathematics and Mechanics, Saint Petersburg State University
Tobias Grosser
> hi all,
Hi ether,
sorry that it took so long to reply and thanks for your work on the
regions stuff.
Concerning this patch there are still some small things I would have
liked to improve, before before people spend time reviewing this
patchset in detail.
However as the topic is now on the mailing list maybe we get some
feedback on the general idea.
As ether already wrote in his mail this patchset is about detecting
single entry single exit regions in the CFG. These regions can be used
to structure the CFG of a method and to write passes/analysis that take
a region as a working unit instead of the whole function body or just a
loop. This is useful if you want to restrict an analysis&transformation
e.g. to side effect free code, code without loops, code without
irregular control flow, ...
We will use it to extract regions with regular control flow that contain
only loops and branches with affine linear expressions in the loop
bounds or branch conditions. These are the regions that Polly
(polyhedral optimizations for LLVM) should work on.
Regions can also be used to solve a problem in a divide and conquer style.
Some information about the algorithm itself:
------------------------------------------------------------------------
The basic ideas are taken from "The Program Structure Tree - Richard
Johnson, David Pearson, Keshav Pingali - 1994", however enriched with
ideas from "The Refined Process Structure Tree - Jussi Vanhatalo, Hagen
Voelyer, Jana Koehler - 2009".
The algorithm to calculate these data structures however is completely
different, as it takes advantage of existing information already
available in (Post)dominace tree and dominance frontier passes. This
leads to a simpler and in practice hopefully better performing
algorithm. The runtime of the algorithms described in the paper above
are both linear in graph size, O(V+E), whereas this algorithm is
probably in O(V+E^2) in the worst case, as the dominance frontier
information itself is quadratic. In practice runtime seems to be in the
order of dominance tree calculation (tested on the polyhedron.com
benchmarks)
------------------------------------------------------------------------
For us it would be useful to have the RegionPass interface in LLVM mainline.
Here what I found at the first glance:
* cmake/modules/LLVMLibDeps.cmake:
> set(MSVC_LIB_DEPS_LLVMipa LLVMAnalysis LLVMCore LLVMSupport
> LLVMSystem)
> +set(MSVC_LIB_DEPS_LLVMregion LLVMAnalysis LLVMCore LLVMSupport
> LLVMSystem)
Call the library LLVMRegion instead of LLVMregion?
* docs/Passes.html:
> -<tr><td><a href="#constprop">-constprop</a></td><td>Simple constant
> propagation</td></tr>
> +<tr><td><a href="#cr-filter">-cr-filter</a></td><td>Cyclic Region
> Filter</td></tr>
Do not remove -constprop
- "The pass detectS ... and buildS ..."
- "The pass removeS ..." & Missing point at the end of the sentence.
* docs/WritingAnLLVMPass.html
- Why do you change "-help" to "--help"?
- "... but it executeS ..."
- "... instead of EACH loop"
- "->A<- region pass processes ... in nestED order ... that THE outer
..."
- "... update THE region tree BY using THE RGPassManager ..."
- "didn't" -> "did not"
- "a true value should be returned if the REGION is modified"
- More changes of "-help" to "--help"?
- Do not change the documentation of -regalloc in this patch
* include/llvm/Analysis/Passes.h
- "This pass findS ..."
- "This pass printS ..."
- "This pass simple removeS ..."
* include/llvm/LinkAllPasses.h
- PMT_ModulePassManager = 1, ///< MPPassManager
- PMT_CallGraphPassManager, ///< CGPassManager
- PMT_FunctionPassManager, ///< FPPassManager
- PMT_LoopPassManager, ///< LPPassManager
- PMT_BasicBlockPassManager, ///< BBPassManager
+ PMT_ModulePassManager = 1, /// MPPassManager
+ PMT_CallGraphPassManager, /// CGPassManager
+ PMT_FunctionPassManager, /// FPPassManager
Why do you remove the "<"? Does not seem to be related to the Region
stuff, so please submit this as a separate patch.
- virtual void *getAdjustedAnalysisPointer(const PassInfo *) {
+ virtual void *getAdjustedAnalysisPointer(const PassInfo *PI) {
The same here. If not required for the region stuff please submit it as
a separate patch.
* include/llvm/PassManagers.h
- // pass. If a pass requires an analysis which is not available then
- // the required analysis pass is scheduled to run before the pass
itself is
+ // pass. If a pass requires an analysis which is not not available then
+ // equired analysis pass is scheduled to run before the pass itself is
This change seems to not be necessary for the Region stuff. I can also
not see any improvement. You added a redundant "not" and removed "the
r" what seems to be useful.
* lib/Analysis/Region/Makefile
- LLVMregion -> LLVMRegion?
* There are several comments like this:
//preform difference comparison on difference mode, because we only
//increase one kind of iterator on each mode
Please format them like this:
// Preform difference comparison on difference mode, because we only
// increase one kind of iterator on each mode.
Thus add a point at the end of the sentence, start with capital letter
and put a space between "//" and the first word.
* tools/opt/opt.c
- PassKind Kind = P->getPassKind();
addPass(Passes, P);
if (AnalyzeOnly) {
- switch (Kind) {
+ switch (P->getPassKind()) {
This change is not related to the region stuff. Please submit it separately.
* Did you test the build with autoconf?
* Is this what currently is committed to the regioninfo git branch?
It is already late, so I will review this in more detail tomorrow. It
looks nice in general, but I had not the time to check all the details.
Thanks again for working on this
Tobias
Renato Golin
> This is useful if you want to restrict an analysis&transformation
> e.g. to side effect free code, code without loops, code without
> irregular control flow, ...
I'm confused...
I thought that loop optimization was one of the benefits of separating
a region from the rest of the code... Also, you can only guarantee
side effect free code if there is no function calls or the whole
program is running single threaded. SSA would guarantee all the other
cases.
I guess that the CFG would not be closed if there was a function call
(or a jump for that matter), but multi-threaded load/stores can't be
guaranteed. Even if you have locks, LLVM wouldn't be able to tell it's
a lock and for that particular variable. Or maybe we should just
ignore the case and let the programmer hang himself... ;)
> We will use it to extract regions with regular control flow that contain
> only loops and branches with affine linear expressions in the loop
> bounds or branch conditions. These are the regions that Polly
> (polyhedral optimizations for LLVM) should work on.
Ok, so this means you meant "code without non-affine loops", right?
Still, non-affine loops can be converted to affine loops in many ways
and would be easier to do so in a closed region rather than looking
again the same code poly has just seen, and converting loops to affine
could be easier if the region was closed (simpler dependency
analysis).
So, I wouldn't rule out any kind of loop in the poly pass, and keep a
flag to assert the region is "clean". The passes that need a clean
region should only pass after all "cleaning" passes (such as
'affine-zising' loops) had run and skip if the region is not clean.
cheers,
--renato
Reclaim your digital rights, eliminate DRM, learn more at
http://www.defectivebydesign.org/what_is_drm
Tobias Grosser
> On 6 March 2010 02:05, Tobias Grosser<gro...@fim.uni-passau.de> wrote:
>> e.g. to side effect free code, code without loops, code without
>> irregular control flow, ...
>
>
> I thought that loop optimization was one of the benefits of separating
> a region from the rest of the code... Also, you can only guarantee
> side effect free code if there is no function calls or the whole
> program is running single threaded. SSA would guarantee all the other
> cases.
Hi Renato,
these are just examples for what regions could be used for. The idea is
in a first step to create a region tree that contains all regions in the
CFG, where a region is a subgraph of the CFG that has just one entry and
on exit edge (or can be transformed to such a region). These regions can
easily be extracted or separately analyzed/optimized.
However the actual analysis of the content of the region is done in a
later pass.
E.g. if your optimization only works on side effect free code it could
be checked, that in a specific region only pure/const function calls
appear. As you said you would also need restrictions on the load/stores
and probably several more. However this is not the problem of the region
framework. The region framework only gives you the units of the CFG that
you can work on (or decide it is too difficult to work on these).
Using the region framework gives you can easily describe a part of the
CFG, by just saying "this region will be optimized", "this region does
not change any memory".
> I guess that the CFG would not be closed if there was a function call
> (or a jump for that matter), but multi-threaded load/stores can't be
> guaranteed. Even if you have locks, LLVM wouldn't be able to tell it's
> a lock and for that particular variable. Or maybe we should just
> ignore the case and let the programmer hang himself... ;)
What do you mean with a closed CFG? In terms of the CFG of a function a
region is closed as there is just one entry and one exit edge. So there
are no other ways to get into or out of the region except these two
edges. A function call does not leave the region, as it either will
return and finally leave the region using the exit edge or it will never
return and therefore also never leave the region using a wrong edge. :-)
>> We will use it to extract regions with regular control flow that contain
>> only loops and branches with affine linear expressions in the loop
>> bounds or branch conditions. These are the regions that Polly
>> (polyhedral optimizations for LLVM) should work on.
>
> Ok, so this means you meant "code without non-affine loops", right?
Where did I say this? A region can have any content you want.
In Polly we want code without non-affine loops. Also there is a lot of
other stuff we do not want. Either as it can technically not be handled
or we just did not write code to support it.
> Still, non-affine loops can be converted to affine loops in many ways
How would you do this? As we use the scalar evolution analysis to
analyze the loops, we do not depend on any syntactic form. Therefore to
change non-affine loops to affine loops, I believe it takes some heavier
transformations.
> and would be easier to do so in a closed region rather than looking
> again the same code poly has just seen, and converting loops to affine
> could be easier if the region was closed (simpler dependency
> analysis).
Again, what do you mean by closed region? And why would something look
again at code polly hast just seen?
> So, I wouldn't rule out any kind of loop in the poly pass, and keep a
> flag to assert the region is "clean". The passes that need a clean
> region should only pass after all "cleaning" passes (such as
> 'affine-zising' loops) had run and skip if the region is not clean.
Yes. This is more or less how it should work.
At first I would start with a pass that detects if regions are clean and
a polly pass that skips non clean regions. Later on I would like to
schedule several cleanup passes before polly to make more regions
"clean", so that the can be optimized by polly.
Cheers,
Renato Golin
> What do you mean with a closed CFG?
Closed region, one entry/one exit.
>> Still, non-affine loops can be converted to affine loops in many ways
> How would you do this? As we use the scalar evolution analysis to analyze
> the loops, we do not depend on any syntactic form. Therefore to change
> non-affine loops to affine loops, I believe it takes some heavier
> transformations.
Which can be added to Poly in a later stage, right? Instead of going
through all loops again, it could use the "is not affine" flag of poly
and try to optimize only the needed ones.
> And why would something look again at code polly hast just seen?
Poly simplifies the region's analysis by ruling out some things, like
"this region is const" or "this loop is affine". Other passes could
benefit from such analysis to simplify their code and reduce their
footprint.
> At first I would start with a pass that detects if regions are clean and a
> polly pass that skips non clean regions. Later on I would like to schedule
> several cleanup passes before polly to make more regions "clean", so that
> the can be optimized by polly.
Could that be a property of Polly? To get regions even if they aren't
clean and clean them? That would save one extra pass...
Maybe I'm completely wrong on assuming that Poly will generate (and
keep) all these metadata on the regions that could be used by other
passes, and that is where the confusion started...
--
cheers,
--renato
Reclaim your digital rights, eliminate DRM, learn more at
http://www.defectivebydesign.org/what_is_drm
Tobias Grosser
> Hi Tobias,
>
>
>> What do you mean with a closed CFG?
>
>
>
>> How would you do this? As we use the scalar evolution analysis to analyze
>> the loops, we do not depend on any syntactic form. Therefore to change
>> non-affine loops to affine loops, I believe it takes some heavier
>> transformations.
>
There are already several passes that canonicalize loops in LLVM. And
there can be even more, also some Polly might benefit from. So I would
prefer to add passes that can be generally useful directly to LLVM and
not to Polly.
> Instead of going
> through all loops again, it could use the "is not affine" flag of poly
> and try to optimize only the needed ones.
Going through all loops is not too expensive. I would prefer to keep
passes separately. This way they can be reused easily by other passes
and the code will be easier to understand.
>> And why would something look again at code polly hast just seen?
>
> Poly simplifies the region's analysis by ruling out some things, like
> "this region is const" or "this loop is affine". Other passes could
> benefit from such analysis to simplify their code and reduce their
> footprint.
Polly simplifies the region's analysis? I do not get this.
Polly just uses the region's analysis to get the regions. Which will be
analyzed and if they cannot be handled by polly they will be skipped.
>> At first I would start with a pass that detects if regions are clean and a
>> polly pass that skips non clean regions. Later on I would like to schedule
>> several cleanup passes before polly to make more regions "clean", so that
>> the can be optimized by polly.
>
> Could that be a property of Polly? To get regions even if they aren't
> clean and clean them? That would save one extra pass...
Passes are cheap. I would like to keep anything that is not required in
a separate pass. E.g. the scalar evolution analysis also only works well
if a specific set of loop transformations was done upfront. However
these transformations are separate passes that have to be scheduled
explicitly to enable scalar evolution to calculate anything.
> Maybe I'm completely wrong on assuming that Poly will generate (and
> keep) all these metadata on the regions that could be used by other
> passes, and that is where the confusion started...
Polly does not generate metadata itself. However on the way to Polly
(which is yet in an early stage) several passes have to be written. Some
of them will collect this metadata. Some of them will prepare regions
for polly. Some might create the polyhedral information. Some will
optimize this information. And some will generate optimized code /
parallel code. ...
Tobi
Renato Golin
> Polly does not generate metadata itself. However on the way to Polly (which
> is yet in an early stage) several passes have to be written. Some of them
> will collect this metadata. Some of them will prepare regions for polly.
> Some might create the polyhedral information. Some will optimize this
> information. And some will generate optimized code / parallel code. ...
Ok, now I'm beginning to understand... ;)
Thanks!
--
cheers,
--renato
Reclaim your digital rights, eliminate DRM, learn more at
http://www.defectivebydesign.org/what_is_drm
ether
thanks for the advice.
best regards
--ether