[LLVMdev] region pass - new pass for llvm

[Tobias Grosser]

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