On 02/28/2010 07:12 AM, ether zhhb wrote:> 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