Comment on the innermost loop analysis pass.

[ether]

> From ebb873dc6b64ec2ba22107e5f01bc705d2e11099 Mon Sep 17 00:00:00 2001
> From: TangKK <dengjunq...@hotmail.com>
> Date: Wed, 18 Jul 2012 16:37:26 +0800
> Subject: [PATCH 1/2] Add Innermostloop Analysis Pass - Analysis the
> innermost
> loops within a scop
>
> Signed-off-by: TangKK <dengjunq...@hotmail.com>
> ---
> include/polly/InnermostLoop.h | 60 ++++++++++++++
> include/polly/LinkAllPasses.h | 2 +
> lib/Analysis/CMakeLists.txt | 1 +
> lib/Analysis/InnermostLoop.cpp | 173
> ++++++++++++++++++++++++++++++++++++++++
> lib/RegisterPasses.cpp | 2 +
> test/CMakeLists.txt | 1 +
> 6 files changed, 239 insertions(+), 0 deletions(-)
> create mode 100755 include/polly/InnermostLoop.h
> create mode 100755 lib/Analysis/InnermostLoop.cpp
>
> diff --git a/include/polly/InnermostLoop.h b/include/polly/InnermostLoop.h
> new file mode 100755
> index 0000000..e4fb77b
> --- /dev/null
> +++ b/include/polly/InnermostLoop.h
> @@ -0,0 +1,60 @@
> +//===----- InnermostLoop.h - Analysis the innermost loops within a
> scop------===//
> +//
> +// The LLVM Compiler Infrastructure
> +//
> +// This file is distributed under the University of Illinois Open Source
> +// License. See LICENSE.TXT for details.
> +//
> +//===----------------------------------------------------------------------------===//
> +//
> +// The pass implements the following algorithm for determining
> innermost loop in
> +// the context of Polly:
> +// We scan their scattering dimension pos by pos. When we encounter
> different constant
> +// dimensions, we branch the original group into several groups
> according to the number
> +// of different constants, then we look ahead one dimension of each
> scopstmt, if that is a
> +// zero dimension, we delete that scopstmt in the group, and if the
> group has no
> +// scopstmt, we delete that group. Go on scanning and branching until
> each group only
> +// has one valid scopstmt, then all these scopstmts are innermost.
> +//===----------------------------------------------------------------------===//
> +
> +#ifndef POLLY_INNERMOST_H
> +#define POLLY_INNERMOST_H
> +
> +#include "polly/ScopPass.h"
> +
> +using namespace llvm;
> +
> +namespace polly {
> + class Scop;
> + class ScopStmt;
> +
> + class InnermostStmts : public ScopPass {
> + /// The Innermost scopstmts
> + SmallVector<const char*, 8> InnermostStmtSet;
> +
> + public:
> + static char ID;
> + InnermostStmts() : ScopPass(ID){}
> +
> + /// print out the innermost scopstmts
> + void dump() const;
> +
> + /// print the class to the OS specified
> + void printScop(llvm::raw_ostream &OS) const;
> + virtual void releaseMemory();
> +
> + bool runOnScop(Scop &S);
> +
> + /// This is for those who need to use the analyze result of this pass
> + std::set<const char*> getInnermostStmts() const;
Instead of returing a set, I suggest we require the user pass a set to
the function, then the function fill the set with the results.
By doing this, the set copying operation can be avoid when the function
return. Hence the function should looks like this:
void getInnermostStmts(std::set<const char*> &<Some meaningful name>) const;
> +
> + };
> +
> +}//end namespace polly
> +
> +namespace llvm {
> + class PassRegistry;
> + void initializeInnermostStmtsPass(llvm::PassRegistry&);
> +}
> +
> +#endif
> diff --git a/include/polly/LinkAllPasses.h b/include/polly/LinkAllPasses.h
> index ed2442b..19678c5 100644
> --- a/include/polly/LinkAllPasses.h
> +++ b/include/polly/LinkAllPasses.h
> @@ -43,6 +43,7 @@ namespace polly {
> Pass *createDOTViewerPass();
> Pass *createIndependentBlocksPass();
> Pass *createIndVarSimplifyPass();
> + Pass *createInnermostStmtsPass();
> Pass *createJSONExporterPass();
> Pass *createJSONImporterPass();
> Pass *createPipforPass();
> @@ -94,6 +95,7 @@ namespace {
> createDOTViewerPass();
> createIndependentBlocksPass();
> createIndVarSimplifyPass();
> + createInnermostStmtsPass();
> createJSONExporterPass();
> createJSONImporterPass();
> createPipforPass();
> diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt
> index 4a2298f..a0fe5be 100644
> --- a/lib/Analysis/CMakeLists.txt
> +++ b/lib/Analysis/CMakeLists.txt
> @@ -6,4 +6,5 @@ add_polly_library(PollyAnalysis
> ScopPass.cpp
> TempScopInfo.cpp
> Pipfor.cpp
> + InnermostLoop.cpp
> )
> diff --git a/lib/Analysis/InnermostLoop.cpp
> b/lib/Analysis/InnermostLoop.cpp
> new file mode 100755
> index 0000000..f51cc33
> --- /dev/null
> +++ b/lib/Analysis/InnermostLoop.cpp
> @@ -0,0 +1,173 @@
> +//===----- InnermostLoop.cpp - Analysis the innermost loops within a
> scop------===//
> +//
> +// The LLVM Compiler Infrastructure
> +//
> +// This file is distributed under the University of Illinois Open Source
> +// License. See LICENSE.TXT for details.
> +//
> +//===----------------------------------------------------------------------------===//
> +//
> +// The pass implements the following algorithm for determining
> innermost loop in
> +// the context of Polly:
> +// We scan their scattering dimension pos by pos. When we encounter
> different constant
> +// dimensions, we branch the original group into several groups
> according to the number
> +// of different constants, then we look ahead one dimension of each
> scopstmt, if that is a
> +// zero dimension, we delete that scopstmt in the group, and if the
> group has no
> +// scopstmt, we delete that group. Go on scanning and branching until
> each group only
> +// has one valid scopstmt, then all these scopstmts are innermost.
> +//===----------------------------------------------------------------------===//
> +
> +#include "polly/InnermostLoop.h"
> +#include "polly/LinkAllPasses.h"
> +
> +#define DEBUG_TYPE "polly-innermost"
> +
> +#include "polly/ScopInfo.h"
> +#include "polly/Support/GICHelper.h"
> +
> +#include "llvm/Support/Debug.h"
> +#include "llvm/ADT/SmallVector.h"
> +
> +#include "isl/map.h"
> +#include "isl/set.h"
> +
> +#include <set>
> +#include <gmp.h>
> +
> +using namespace llvm;
> +using namespace polly;
> +
Please add the comment detailing:
1. What this function do.
2. What the parameters are holding when they are passed in if they are
inputs parameters,
3 What the parameters are supposed to hold when the function return if
they are output parameters.
> +static void InnermostScan(std::map<int, SmallVector<ScopStmt*, 8> >
> Gs, unsigned pos,
Can the 'Gs' be passed as reference? Like std::map<int,
SmallVector<ScopStmt*, 8> > &Gs.
> + SmallVector<const char*, 8> &InnermostStmtSet) {
Instead of using SmallVector<SomeType, Number> as the type of
parameters, I suggest use SmallVectorImpl<SomeType> instead.
> + DEBUG(dbgs() << "*****Pos*****:" << pos << "\n";);
> + DEBUG(dbgs() << "****Gs Size****:" << Gs.size() << "\n";);
> + for (std::map<int, SmallVector<ScopStmt*, 8> >::iterator GI =
> Gs.begin(), GE = Gs.end();
> + GI != GE; ++GI) {
> + SmallVector<ScopStmt*, 8> G = (*GI).second;
I suggest we use reference here, i.e.
SmallVector<ScopStmt*, 8> &G = (*GI).second;
And if you do not change the G, we should use constant reference, i.e.
const SmallVector<ScopStmt*, 8> &G = (*GI).second;
> + int condim = (*GI).first;
You can use GI->first instead of (*GI).first.
> +
> + /// If there is only one statement left, this is the innermost. Exit
> this iteration right away.
> + if(G.size() == 1) {
> + DEBUG(dbgs() << "Innermost:\n";);
> + isl_map *scattering = (*G.begin())->getScattering();
> + const char *Name = isl_map_get_tuple_name(scattering, isl_dim_in);
> + InnermostStmtSet.push_back(Name);
> + DEBUG(dbgs() << Name << "\n";);
> + isl_map_free(scattering);
> + continue;
> + }
> +
> + /// If there are more than one statement left, there must be at
> least one
> + /// that is not innermost.
> + std::map<int, SmallVector<ScopStmt*, 8> > NewGs;
> + for(SmallVector<ScopStmt*, 8>::iterator GII = G.begin(), GEE = G.end();
> + GII != GEE; ++GII) {
> + ScopStmt *stmt = *GII;
> + isl_map *scattering = stmt->getScattering();
> + isl_int con;
> + isl_int_init(con);
> +
> + if(isl_map_plain_is_fixed(scattering, isl_dim_out, pos, &con)) {
> + mpz_t intMPZ;
> + mpz_init(intMPZ);
> + isl_int_get_gmp(con, intMPZ);
> +
> + int intcon = mpz_get_si(intMPZ);
> + DEBUG(dbgs() << "pos =" << pos << ":\n" << "intcon: " << intcon <<
> "\n";);
> +
> + isl_int lookahead;
> + isl_int_init(lookahead);
> +
> + /// look ahead to see if the dim value in next pos is zero, and if
> true, delete this stmt
> + /// And if this pos is the last pos of this map, no need for look ahead
> + if(pos < isl_map_dim(scattering, isl_dim_out) - 1) {
> + if(isl_map_plain_is_fixed(scattering, isl_dim_out, pos+1, &lookahead)) {
> + if(isl_int_is_zero(lookahead)) {
> + mpz_clear(intMPZ);
> + isl_int_clear(lookahead);
> + isl_map_free(scattering);
> + continue;
> + }
> + }
> + }
> +
> + NewGs[intcon].push_back(stmt);
> + mpz_clear(intMPZ);
> +
> + } else {
> + DEBUG(dbgs() << "pos =" << pos << ":\n" << "not a constant\n";);
> + /// Keep the stmt to the next iteration
> + NewGs[condim].push_back(stmt);
> + }
> +
> + isl_int_clear(con);
> + isl_map_free(scattering);
> + }
> +
> + InnermostScan(NewGs, pos+1, InnermostStmtSet);
> +
> + }
> +}
> +
> +void InnermostStmts::releaseMemory() {
> + InnermostStmtSet.clear();
> +}
> +
> +void InnermostStmts::dump() const {
> + printScop(dbgs());
> +}
> +
> +void InnermostStmts::printScop(llvm::raw_ostream &OS) const {
> + OS << "Innermost Loop(s):\n";
> +
> + for(SmallVector<const char*, 8>::const_iterator I =
> InnermostStmtSet.begin(),
> + E = InnermostStmtSet.end(); I != E; ++I) {
> + OS << *I << "\n";
> + }
> +
> + OS << "End of Innermost Loop(s).\n";
> +}
> +
> +std::set<const char*> InnermostStmts::getInnermostStmts() const {
> + std::set<const char*> S;
> + for(SmallVector<const char*, 8>::const_iterator I =
> InnermostStmtSet.begin(),
> + E = InnermostStmtSet.end(); I != E; ++I) {
> + S.insert(*I);
> + }
> + return S;
> +}
> +
> +bool InnermostStmts::runOnScop(Scop &S) {
> + /// A type to represent one scopstmt group
> + typedef SmallVector<ScopStmt*, 8> StmtGrp;
> + /// A type to represent several groups of scopstmts
> + typedef std::map<int, StmtGrp> StmtGrps;
I suggest expose these typedefs in the header file, so the functions
outside can use the typedefed types.
> +
> + StmtGrp G;
> + StmtGrps Gs;
> +
> + /// First, we let all the scopstmts belongs to one group(StmtGrp).
> + for (Scop::iterator SI = S.begin(), SE = S.end(); SI != SE; ++SI) {
> + ScopStmt *stmt = *SI;
> + G.push_back(stmt);
> + }
> + Gs[0]=G;
> +
> + DEBUG(dbgs() << "Looking for Innermost Loop...\n";);
> + InnermostScan(Gs, 0, InnermostStmtSet);
> + DEBUG(dbgs() << "Finish Looking for Innermost Loop.\n";);
> +
> + return false;
> +}
> +
> +char InnermostStmts::ID = 0;
> +
> +INITIALIZE_PASS_BEGIN(InnermostStmts, "polly-innermost",
> +"Polly - Analysis the Innermost Loops", false, false)
> +INITIALIZE_PASS_DEPENDENCY(ScopInfo)
> +INITIALIZE_PASS_END(InnermostStmts, "polly-innermost",
> +"Polly - Analysis the Innermost Loops", false, false)
> +
> +Pass* polly::createInnermostStmtsPass() {
> + return new InnermostStmts();
> +}
> diff --git a/lib/RegisterPasses.cpp b/lib/RegisterPasses.cpp
> index 3423e90..7358795 100644
> --- a/lib/RegisterPasses.cpp
> +++ b/lib/RegisterPasses.cpp
> @@ -20,6 +20,7 @@
> #include "polly/TempScopInfo.h"
> #include "polly/CodeGen/CodeGeneration.h"
> #include "polly/Pipfor.h"
> +#include "polly/InnermostLoop.h"
>
> #include "llvm/Analysis/Passes.h"
> #include "llvm/Analysis/CFGPrinter.h"
> @@ -141,6 +142,7 @@ static void initializePollyPasses(PassRegistry
> &Registry) {
> initializeJSONExporterPass(Registry);
> initializeJSONImporterPass(Registry);
> initializeIslScheduleOptimizerPass(Registry);
> + initializeInnermostStmtsPass(Registry);
> initializePipforPass(Registry);
> #ifdef SCOPLIB_FOUND
> initializePoccPass(Registry);
> diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
> index 2b531c2..d55f022 100644
> --- a/test/CMakeLists.txt
> +++ b/test/CMakeLists.txt
> @@ -4,6 +4,7 @@ set(POLLY_TEST_DIRECTORIES
> "ScheduleOptimizer"
> "CodeGen"
> "Cloog"
> + "Innermost"
> "OpenMP"
> "Pipfor"
> "polybench"
> --
> 1.7.5.1
>
Looks like your pass can not only finding the innermost loops, but also
recover the entire loop nest tree(s) of the SCoP. So Instead of storing
the results in a map, I suggest storing the results in a tree structure,
so the InnermostLoops analysis becomes the LoopNestTree analysis. This
analysis will be very helpful to the GPGPU codegeneration, and the data
locality optimization (At least for Armin's approach).

best regards
ether

[Jun-qi Deng]

Hi ether, here is the patch fixed according to your comments. And as for achieving the "LoopNestTree analysis" you mentioned, I think this pass still need some improvement. I will do it right away.

best regards,

tangkk

2012/7/31 ether <ethe...@gmail.com>

[Hongbin Zheng]

First of all, what about rename the name of the pass to "LoopNestTreeAnalysis"?

[Jun-qi Deng]

2012/8/1 Hongbin Zheng <ethe...@gmail.com>

First of all, what about rename the name of the pass to "LoopNestTreeAnalysis"?

In this patch I just fix those things other than LoopNestTree. Therefore this is not the ultimate patch I can give. I will rename the pass when I implement the LoopNestTree Analysis. 

regards,

tangkk 

[Jun-qi Deng]

Hi all! This is the algorithm I give to be implemented into the LoopNestTree Analysis Pass:

//===----------------------------------------------------------------------------===//

//

// This pass implements the following algorithm for creating a loop nest tree in

// the context of Polly:

// First, we creat a "NONE" node to be the ultimate parent of all nodes

// Then we scan pos by pos the scatterings of all the scopstmts. During the scanning:

// If we encounter a new constant dimension, we add a new node(child);

// If we encounter a different (value) constant dimensions of the same pos,

// we add a new branch(new node(sibling) at the branch too); Meanwhile,

// we look ahead one pos, if it is a "zero" dimension, mark the node as "SCOPSTMT",

// else, mark it as "FOR"; a scattering will not be got rid of until a "SCOPSTMT"

// node is produced.

// After such process, the loop nest tree is created, and those "SCOPSTMT" nodes

// without siblings(no matter "FOR" or "SCOPSTMT") are innermost.

//===----------------------------------------------------------------------===//

regards,

tangkk

2012/8/1 Jun-qi Deng <dengjunq...@gmail.com>

[Jun-qi Deng]

Hi ether and Tobi, I've alreay implemented the loop nest tree analysis pass. The details is as follows:

The goal of this pass is to recover the loop nest tree structure of a polly scop.

This pass implements the following algorithm:

+//===----------------------------------------------------------------------------===//

+//

+// This pass implements the following algorithm for creating a loop nest tree in

+// the context of Polly:

+// First, we creat a "Root" node to be the ultimate parent of all nodes

+// Then we scan pos by pos the scatterings of all the scopstmts. During the scanning:

+// If we encounter a new constant dimension, we add a new node(child);

+// If we encounter a different (value) constant dimensions of the same pos,

+// we add a new branch(new node(sibling) at the branch too),

+// while same constants of the same pos only means one node; Meanwhile,

+// we look ahead one pos, if it is a "zero" dimension, mark the node as "SCOPSTMT",

+// else, mark it as "FOR"; we separate scopstmts into different groups according to

+// the above mentioned different constants;

+// a scattering will not be got rid of until a "SCOPSTMT" node is produced.

+// After such process, the loop nest tree is created, and those "SCOPSTMT" nodes

+// without siblings(no matter "FOR" or "SCOPSTMT") are innermost.

+//===----------------------------------------------------------------------===//

For example(which is also shown in the test case patch), if the input is:

  for(i=0; i<N; i++) {

    for(j=0; j<N; j++) {

      C[i][j] = 0;

      for(k=0; k<N; k++)

   C[i][j] = C[i][j] + A[i][k] * B[k][j];

    }

  }

Then the recovered loop nest tree is:

Loop Nest Tree:

-----------------------------

  for

    for

      Stmt_for_body3

      for

        Stmt_for_body7

-----------------------------

End of Loop Nest Tree.

Innermost Loop(s):

*****************************

Stmt_for_body7

*****************************

End of Innermost Loop(s).

where the innermost loop(s) of this scop is(are) also found.

Please review the attached patches. Many thanks!

regards,

tangkk

[Jun-qi Deng]

The patches are pasted here:

From d4c789ec0e79aa6fd4820cf5f3602e90e156a906 Mon Sep 17 00:00:00 2001

From: TangKK <dengjunq...@hotmail.com>

Date: Wed, 18 Jul 2012 16:37:26 +0800

Subject: [PATCH 1/7] Add LoopNestTree Analysis Pass - Analysis the Loop Nest

 Tree

Signed-off-by: TangKK <dengjunq...@hotmail.com>

---

 include/polly/LinkAllPasses.h         |    2 +

 include/polly/LoopNestTreeAnalysis.h  |  161 +++++++++++++++++++

 lib/Analysis/CMakeLists.txt           |    1 +

 lib/Analysis/LoopNestTreeAnalysis.cpp |  275 +++++++++++++++++++++++++++++++++

 lib/RegisterPasses.cpp                |    2 +

 test/CMakeLists.txt                   |    1 +

 6 files changed, 442 insertions(+), 0 deletions(-)

 create mode 100755 include/polly/LoopNestTreeAnalysis.h

 create mode 100755 lib/Analysis/LoopNestTreeAnalysis.cpp

diff --git a/include/polly/LinkAllPasses.h b/include/polly/LinkAllPasses.h

index ed2442b..38748a6 100644

--- a/include/polly/LinkAllPasses.h

+++ b/include/polly/LinkAllPasses.h

@@ -43,6 +43,7 @@ namespace polly {

   Pass *createDOTViewerPass();

   Pass *createIndependentBlocksPass();

   Pass *createIndVarSimplifyPass();

+  Pass *createLoopNestTreePass();

   Pass *createJSONExporterPass();

   Pass *createJSONImporterPass();

   Pass *createPipforPass();

@@ -94,6 +95,7 @@ namespace {

        createDOTViewerPass();

        createIndependentBlocksPass();

        createIndVarSimplifyPass();

+       createLoopNestTreePass();

        createJSONExporterPass();

        createJSONImporterPass();

        createPipforPass();

diff --git a/include/polly/LoopNestTreeAnalysis.h b/include/polly/LoopNestTreeAnalysis.h

new file mode 100755

index 0000000..d343e67

--- /dev/null

+++ b/include/polly/LoopNestTreeAnalysis.h

@@ -0,0 +1,161 @@

+//===---------- LoopNestTreeAnalysis.h  - Analysis the Loop Nest Tree-------===//

+//

+//                     The LLVM Compiler Infrastructure

+//

+// This file is distributed under the University of Illinois Open Source

+// License. See LICENSE.TXT for details.

+//

+//===----------------------------------------------------------------------------===//

+//

+// This pass implements the following algorithm for creating a loop nest tree in

+// the context of Polly:

+// First, we creat a "Root" node to be the ultimate parent of all nodes

+// Then we scan pos by pos the scatterings of all the scopstmts. During the scanning:

+// If we encounter a new constant dimension, we add a new node(child);

+// If we encounter a different (value) constant dimensions of the same pos,

+// we add a new branch(new node(sibling) at the branch too),

+// while same constants of the same pos only means one node; Meanwhile,

+// we look ahead one pos, if it is a "zero" dimension, mark the node as "SCOPSTMT",

+// else, mark it as "FOR"; we separate scopstmts into different groups according to

+// the above mentioned different constants;

+// a scattering will not be got rid of until a "SCOPSTMT" node is produced.

+// After such process, the loop nest tree is created, and those "SCOPSTMT" nodes

+// without siblings(no matter "FOR" or "SCOPSTMT") are innermost.

+//===----------------------------------------------------------------------===//

+

+#ifndef  POLLY_INNERMOST_H

+#define POLLY_INNERMOST_H

+

+#include "polly/ScopPass.h"

+

+using namespace llvm;

+

+namespace polly {

+  class Scop;

+  class ScopStmt;

+

+  //===---------------------------------------------------------------------===//

+  /// @brief The Base Class of the Node of the Loop Nest Tree

+  ///

+  class LoopNestTreeBase {

+    // DO NOT IMPLEMENT

+    LoopNestTreeBase(const LoopNestTreeBase &);

+    // DO NOT IMPLEMENT

+    const LoopNestTreeBase &operator=(const LoopNestTreeBase &);

+

+  public:

+    enum LoopNestNodeType {

+      // The Node may be of only two types: "for" statement and "scopstmt"

+      FOR,

+      SCOPSTMT

+    };

+

+  private:    

+    LoopNestTreeBase *Parent;

+    enum LoopNestNodeType NodeType;

+

+  protected:

+    LoopNestTreeBase(enum LoopNestNodeType Type) : Parent(0), NodeType(Type) {}

+

+  public: 

+

+    enum LoopNestNodeType getNodeType() const { return NodeType; }

+    void setNodeType(enum LoopNestNodeType T) { NodeType = T; }

+

+    LoopNestTreeBase *getParent() const { return Parent; }

+    void setParent(LoopNestTreeBase *P) { Parent = P; }

+

+    virtual void print(llvm::raw_ostream &OS, unsigned indent) const;

+};

+

+  //===---------------------------------------------------------------------===//

+  /// @brief A derived class standing for the "for" statement node of the tree

+  ///

+  class LoopNestTreeFor : public LoopNestTreeBase {

+    SmallVector<LoopNestTreeBase*, 8> Children;

+

+  public:

+    LoopNestTreeFor() : LoopNestTreeBase(FOR) {}

+    ~LoopNestTreeFor() { Children.clear(); }

+

+    void addChild(LoopNestTreeBase *Child) { Children.push_back(Child); }

+    

+    // DFS the LoopNestTree and print out all the nodes

+    void printTree(llvm::raw_ostream &OS, unsigned indent) const;

+

+    // DFS the LoopNestTree and delete all the nodes.

+    LoopNestTreeFor *deleteTree();

+

+    /// Methods for support type inquiry through isa, cast, and dyn_cast:

+    static inline bool classof(const LoopNestTreeFor *N) { return true; }

+    static inline bool classof(const LoopNestTreeBase *N) {

+      return N->getNodeType() == FOR;

+    }

+  };

+

+  //===---------------------------------------------------------------------===//

+  /// @brief A derived class standing for the scopstmt node of the tree

+  ///

+  class LoopNestTreeStmt : public LoopNestTreeBase {

+    ScopStmt  *stmt;

+

+  public:

+    LoopNestTreeStmt() : LoopNestTreeBase(SCOPSTMT) {}

+

+    void setScopStmt(ScopStmt *S) { stmt = S; }

+    void print(llvm::raw_ostream &OS, unsigned indent) const;

+

+    /// Methods for support type inquiry through isa, cast, and dyn_cast:

+    static inline bool classof(const LoopNestTreeStmt *N) { return true; }

+    static inline bool classof(const LoopNestTreeBase *N) {

+      return N->getNodeType() == SCOPSTMT;

+    }

+  };

+

+  class LoopNestTree : public ScopPass {

+    /// The Innermost scopstmts

+    SmallVector<const char*, 8> InnermostStmtSet;

+

+    /// The Root of the LoopNestTree

+    LoopNestTreeFor *Root;

+

+  public:

+    static char ID;

+    LoopNestTree() : ScopPass(ID) {}

+

+    /// A type to represent one scopstmt group

+    typedef SmallVector<ScopStmt*, 8> StmtGrp;

+    /// A type to represent several scopstmt groups

+    typedef std::map<int, StmtGrp> StmtGrps;

+

+    /// A type to represent a group of parent nodes

+    typedef std::map<int, LoopNestTreeFor*>ParentGrp;

+

+    /// print out the innermost scopstmts

+    void dump() const;

+  

+    /// print the class to the OS specified

+    void printScop(llvm::raw_ostream &OS) const;

+    virtual void releaseMemory();

+

+    bool runOnScop(Scop &S);

+

+    void getInnermostStmts(std::set<const char*> &InnermostStmtNames) const;

+

+    // @brief This function, called iteratively, implements the main part of the algorithm

+    //             described at the beginning of this file.

+    // @param Gs is the input scopstmt group(s)

+    // @param pos is the scattering position scanned

+    // @param InnermostStmtSet is the return param that holds the innmermost scopstmts

+    void LoopNestScan(const StmtGrps &Gs, unsigned pos, ParentGrp &Ps);

+

+  };

+

+}//end namespace polly

+

+namespace llvm {

+  class PassRegistry;

+  void initializeLoopNestTreePass(llvm::PassRegistry&);

+}

+

+#endif

diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt

index 4a2298f..0f583c2 100644

--- a/lib/Analysis/CMakeLists.txt

+++ b/lib/Analysis/CMakeLists.txt

@@ -6,4 +6,5 @@ add_polly_library(PollyAnalysis

   ScopPass.cpp

   TempScopInfo.cpp

   Pipfor.cpp

+  LoopNestTreeAnalysis.cpp

 )

diff --git a/lib/Analysis/LoopNestTreeAnalysis.cpp b/lib/Analysis/LoopNestTreeAnalysis.cpp

new file mode 100755

index 0000000..76c9386

--- /dev/null

+++ b/lib/Analysis/LoopNestTreeAnalysis.cpp

@@ -0,0 +1,275 @@

+//===---------- LoopNestTreeAnalysis.cpp  - Analysis the Loop Nest Tree-------===//

+//

+//                     The LLVM Compiler Infrastructure

+//

+// This file is distributed under the University of Illinois Open Source

+// License. See LICENSE.TXT for details.

+//

+//===----------------------------------------------------------------------------===//

+//

+// This pass implements the following algorithm for creating a loop nest tree in

+// the context of Polly:

+// First, we creat a "Root" node to be the ultimate parent of all nodes

+// Then we scan pos by pos the scatterings of all the scopstmts. During the scanning:

+// If we encounter a new constant dimension, we add a new node(child);

+// If we encounter a different (value) constant dimensions of the same pos,

+// we add a new branch(new node(sibling) at the branch too),

+// while same constants of the same pos only means one node; Meanwhile,

+// we look ahead one pos, if it is a "zero" dimension, mark the node as "SCOPSTMT",

+// else, mark it as "FOR"; we separate scopstmts into different groups according to

+// the above mentioned different constants;

+// a scattering will not be got rid of until a "SCOPSTMT" node is produced.

+// After such process, the loop nest tree is created, and those "SCOPSTMT" nodes

+// without siblings(no matter "FOR" or "SCOPSTMT") are innermost.

+//===----------------------------------------------------------------------===//

+

+#include "polly/LoopNestTreeAnalysis.h"

+#include "polly/LinkAllPasses.h"

+

+#define DEBUG_TYPE "polly-loopnesttree"

+

+#include "polly/ScopInfo.h"

+#include "polly/Support/GICHelper.h"

+

+#include "llvm/Support/Debug.h"

+#include "llvm/ADT/SmallVector.h"

+

+#include "isl/map.h"

+#include "isl/set.h"

+

+#include <set>

+#include <gmp.h>

+

+using namespace llvm;

+using namespace polly;

+

+static void printIndent(llvm::raw_ostream &OS, unsigned indent) {

+  for (unsigned i =0; i < indent; i++) {

+    OS << " ";

+  }

+}

+

+void LoopNestTreeBase::print(llvm::raw_ostream &OS, unsigned indent) const {

+  printIndent(OS, indent);

+

+  switch (NodeType) {

+  case FOR:

+    { OS << "for\n"; break; }

+  case SCOPSTMT:

+    { OS << "stmt\n"; break; }

+  default:

+    { OS << "unknown\n"; break; }

+  };

+}

+

+void LoopNestTreeStmt::print(llvm::raw_ostream &OS, unsigned indent) const {

+  printIndent(OS, indent);

+  isl_map *scattering = stmt->getScattering();

+  const char *Name = isl_map_get_tuple_name(scattering, isl_dim_in);

+  OS << Name << "\n";

+  isl_map_free(scattering);

+}

+

+void LoopNestTreeFor::printTree(llvm::raw_ostream &OS, unsigned indent) const {

+  if(indent > 0)

+    this->print(OS, indent);

+  for(SmallVectorImpl<LoopNestTreeBase*>::const_iterator BI = Children.begin(),

+    BE = Children.end(); BI != BE; ++BI) {

+      if (isa<LoopNestTreeStmt>(*BI))

+        cast<LoopNestTreeStmt>(*BI)->print(OS, indent+2);

+      else

+        cast<LoopNestTreeFor>(*BI)->printTree(OS, indent+2);

+  }

+}

+

+LoopNestTreeFor *LoopNestTreeFor::deleteTree() {

+  for(SmallVectorImpl<LoopNestTreeBase*>::iterator BI = Children.begin(),

+    BE = Children.end(); BI != BE; ++BI) {

+      if (isa<LoopNestTreeStmt>(*BI)) {

+        LoopNestTreeStmt *LNTS = cast<LoopNestTreeStmt>(*BI);        

+        delete LNTS;

+      }

+      else {

+        LoopNestTreeFor *LNTF = cast<LoopNestTreeFor>(*BI);

+        delete LNTF->deleteTree();

+      }

+  }

+  return this;

+}

+

+void LoopNestTree::LoopNestScan(const StmtGrps &Gs, unsigned pos, ParentGrp &Ps) {

+  DEBUG(dbgs() << "*****Pos*****:" << pos << "\n";);

+  DEBUG(dbgs() << "****Gs Size****:" <<  Gs.size() << "\n";);

+  for (std::map<int, SmallVector<ScopStmt*, 8> >::const_iterator GI = Gs.begin(),

+                                         GE = Gs.end(); GI != GE; ++GI) {

+    const SmallVector<ScopStmt*, 8> &G = GI->second;

+    int condim = GI->first;

+    DEBUG(dbgs() << "condim =: " << condim << "\n";);

+    

+    StmtGrps NewGs;

+    ParentGrp NewPs;    

+    std::set<int> Conset;

+    for(SmallVector<ScopStmt*, 8>::const_iterator GII = G.begin(), GEE = G.end();

+                                                  GII != GEE; ++GII) {

+      ScopStmt *stmt = *GII;

+      isl_map *scattering = stmt->getScattering();

+      isl_int con;

+      isl_int_init(con);

+

+      // If we encounter a new constant dimension, we add a new node(child);

+      if(isl_map_plain_is_fixed(scattering, isl_dim_out, pos, &con)) {

+        mpz_t intMPZ;

+        mpz_init(intMPZ);

+        isl_int_get_gmp(con, intMPZ);

+

+        int intcon = mpz_get_si(intMPZ);

+        DEBUG(dbgs() << "intcon: " << intcon << "\n";);

+

+        // If we encounter a different (value) constant dimensions of the same pos,

+        // we add a new branch(new node(sibling) at the branch too),

+        // while same constants of the same pos only means one node;

+        if(Conset.count(intcon)) {

+          isl_map_free(scattering);

+          isl_int_clear(con);

+          mpz_clear(intMPZ);

+          NewGs[intcon].push_back(stmt);

+          continue;

+        } else {

+          Conset.insert(intcon);

+        }

+

+        isl_int lookahead;

+        isl_int_init(lookahead);

+

+        // we look ahead one pos, if it is a "zero" dimension, mark the node as "SCOPSTMT",

+        // else, mark it as "FOR";

+        if(pos <= isl_map_dim(scattering, isl_dim_out) - 1) {

+          if(isl_map_plain_is_fixed(scattering, isl_dim_out, pos+1, &lookahead)) {

+            DEBUG(dbgs() << "lookahead is fixed.\n";);

+            if(isl_int_is_zero(lookahead)) {

+              LoopNestTreeStmt *LNTS = new LoopNestTreeStmt;

+              LoopNestTreeFor *P = Ps[condim];

+              LNTS->setParent(P);

+              P->addChild(LNTS);

+              LNTS->setScopStmt(stmt);

+

+              DEBUG(dbgs() << "addChild: "; LNTS->print(dbgs(), 2););

+

+              //those "SCOPSTMT" nodes without siblings(no matter "FOR" or "SCOPSTMT")

+              // are innermost.

+              if(G.size() == 1) {

+                const char *Name = isl_map_get_tuple_name(scattering, isl_dim_in);

+                InnermostStmtSet.push_back(Name);

+                DEBUG(dbgs() << "Innermost: " << Name << "\n";);

+              }

+

+              // We don't keep the stmt in NewGs any more because the stmt

+              // has already been reached.

+            } else {

+              errs() << "Warning! Lookahead is fixed but not zero!\n";

+            }

+          } else {

+            DEBUG(dbgs() << "lookahead is var.\n";);

+            LoopNestTreeFor *LNTF = new LoopNestTreeFor;

+            LoopNestTreeFor *P = Ps[condim];

+            P->addChild(LNTF);

+            LNTF->setParent(P);

+

+            DEBUG(dbgs() << "addChild: "; LNTF->print(dbgs(), 2););

+

+            NewPs[intcon] = LNTF;

+            // we separate scopstmts into different groups according to

+            // the above mentioned different constants;

+            NewGs[intcon].push_back(stmt);

+          }

+        }

+        mpz_clear(intMPZ);

+      } else {

+        DEBUG(dbgs() << "pos =" << pos << ":\n" << "not a constant\n";);

+        /// Keep the stmt to the next iteration

+        NewGs[condim].push_back(stmt);

+        NewPs[condim] = Ps[condim];

+      }

+      isl_int_clear(con);

+      isl_map_free(scattering);

+    }

+    LoopNestScan(NewGs, pos+1, NewPs);

+  }

+}

+

+void LoopNestTree::releaseMemory() {

+  InnermostStmtSet.clear();

+  if(Root)

+    Root->deleteTree();

+  delete Root;

+  Root = 0;

+}

+

+void LoopNestTree::dump() const {

+  printScop(dbgs());

+}

+

+void LoopNestTree::printScop(llvm::raw_ostream &OS) const {

+  OS << "Loop Nest Tree:\n";

+  OS << "-----------------------------\n";

+

+  /// DFS the LNT, print it out according to the nodetype

+  Root->printTree(OS, 0);

+

+  OS << "-----------------------------\n";

+  OS << "End of Loop Nest Tree.\n";

+

+  OS << "Innermost Loop(s):\n";

+  OS << "*****************************\n";

+  for(SmallVector<const char*, 8>::const_iterator I = InnermostStmtSet.begin(),

+                   E = InnermostStmtSet.end(); I != E; ++I) {

+     OS << *I << "\n";

+  }

+  OS << "*****************************\n";

+  OS << "End of Innermost Loop(s).\n";

+}

+

+void LoopNestTree::getInnermostStmts(std::set<const char*> &InnermostStmtNames) const {

+  for(SmallVectorImpl<const char*>::const_iterator I = InnermostStmtSet.begin(),

+    E = InnermostStmtSet.end(); I != E; ++I) {

+      InnermostStmtNames.insert(*I);

+  }

+}

+

+bool LoopNestTree::runOnScop(Scop &S) {

+  StmtGrp G;

+  StmtGrps Gs;

+

+  ParentGrp Ps;

+  Root = new LoopNestTreeFor;

+

+  // First, we creat a "Root" node to be the ultimate parent of all nodes

+  Ps[0] = Root;

+

+  ///we let all the scopstmts belongs to one group(StmtGrp).

+  for (Scop::const_iterator SI = S.begin(), SE = S.end(); SI != SE; ++SI) {

+    G.push_back(*SI);

+  }

+  Gs[0]=G;

+

+  DEBUG(dbgs() << "Begin Scanning...\n";);

+

+  // Then we scan pos by pos the scatterings of all the scopstmts.

+  LoopNestScan(Gs, 0, Ps);

+

+  DEBUG(dbgs() << "Finish Scanning.\n";);

+

+  return false;

+}

+

+char LoopNestTree::ID = 0;

+

+INITIALIZE_PASS_BEGIN(LoopNestTree, "polly-loopnesttree",

+"Polly - Analysis the Loop Nest Tree", false, false)

+INITIALIZE_PASS_DEPENDENCY(ScopInfo)

+INITIALIZE_PASS_END(LoopNestTree, "polly-loopnesttree",

+"Polly - Analysis the Loop Nest Tree", false, false)

+

+Pass* polly::createLoopNestTreePass() {

+    return new LoopNestTree();

+}

diff --git a/lib/RegisterPasses.cpp b/lib/RegisterPasses.cpp

index 3423e90..eeeb1f1 100644

--- a/lib/RegisterPasses.cpp

+++ b/lib/RegisterPasses.cpp

@@ -20,6 +20,7 @@

 #include "polly/TempScopInfo.h"

 #include "polly/CodeGen/CodeGeneration.h"

 #include "polly/Pipfor.h"

+#include "polly/LoopNestTreeAnalysis.h"

 

 #include "llvm/Analysis/Passes.h"

 #include "llvm/Analysis/CFGPrinter.h"

@@ -141,6 +142,7 @@ static void initializePollyPasses(PassRegistry &Registry) {

   initializeJSONExporterPass(Registry);

   initializeJSONImporterPass(Registry);

   initializeIslScheduleOptimizerPass(Registry);

+  initializeLoopNestTreePass(Registry);

   initializePipforPass(Registry);

 #ifdef SCOPLIB_FOUND

   initializePoccPass(Registry);

diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt

index 2b531c2..f86afe6 100644

--- a/test/CMakeLists.txt

+++ b/test/CMakeLists.txt

@@ -4,6 +4,7 @@ set(POLLY_TEST_DIRECTORIES

   "ScheduleOptimizer"

   "CodeGen"

   "Cloog"

+  "LoopNestTree"

   "OpenMP"

   "Pipfor"

   "polybench"

-- 

1.7.5.1

From 7ab58d8bb8d930f6e734b093ad4617317a5c7542 Mon Sep 17 00:00:00 2001

From: TangKK <dengjunq...@hotmail.com>

Date: Wed, 18 Jul 2012 16:38:02 +0800

Subject: [PATCH 2/7] Add testcases to test polly-loopnesttree pass

---

 test/LoopNestTree/matmul.c       |   52 ++++++++++

 test/LoopNestTree/matmul.ll      |  207 ++++++++++++++++++++++++++++++++++++++

 test/LoopNestTree/simatax.c      |   36 +++++++

 test/LoopNestTree/simatax.ll     |  184 +++++++++++++++++++++++++++++++++

 test/LoopNestTree/simple_loop.c  |   20 ++++

 test/LoopNestTree/simple_loop.ll |   67 ++++++++++++

 6 files changed, 566 insertions(+), 0 deletions(-)

 create mode 100755 test/LoopNestTree/matmul.c

 create mode 100755 test/LoopNestTree/matmul.ll

 create mode 100755 test/LoopNestTree/simatax.c

 create mode 100755 test/LoopNestTree/simatax.ll

 create mode 100755 test/LoopNestTree/simple_loop.c

 create mode 100644 test/LoopNestTree/simple_loop.ll

diff --git a/test/LoopNestTree/matmul.c b/test/LoopNestTree/matmul.c

new file mode 100755

index 0000000..d53db35

--- /dev/null

+++ b/test/LoopNestTree/matmul.c

@@ -0,0 +1,52 @@

+#include <stdio.h>

+

+#define TEST

+#define N 1536

+float A[N][N];

+float B[N][N];

+float C[N][N];

+

+void init_array()

+{

+  int i, j;

+

+  for (i=0; i<N; i++) {

+    for (j=0; j<N; j++) {

+      A[i][j] = (1+(i*j)%1024)/2.0;

+      B[i][j] = (1+(i*j)%1024)/2.0;

+    }

+  }

+}

+

+void print_array()

+{

+  int i, j;

+

+  for (i=0; i<N; i++) {

+    for (j=0; j<N; j++) {

+      fprintf(stdout, "%lf ", C[i][j]);

+      if (j%80 == 79) fprintf(stdout, "\n");

+    }

+    fprintf(stdout, "\n");

+  }

+}

+

+int main()

+{

+  int i, j, k;

+  double t_start, t_end;

+  init_array();

+

+  for(i=0; i<N; i++) {

+    for(j=0; j<N; j++) {

+      C[i][j] = 0;

+      for(k=0; k<N; k++)

+    C[i][j] = C[i][j] + A[i][k] * B[k][j];

+    }

+  }

+

+#ifdef TEST

+  print_array();

+#endif

+  return 0;

+}

diff --git a/test/LoopNestTree/matmul.ll b/test/LoopNestTree/matmul.ll

new file mode 100755

index 0000000..7c7e630

--- /dev/null

+++ b/test/LoopNestTree/matmul.ll

@@ -0,0 +1,207 @@

+; RUN: opt %loadPolly %defaultOpts -polly-loopnesttree -analyze %s | FileCheck %s

+; ModuleID = 'matmul.s'

+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"

+target triple = "i386-pc-linux-gnu"

+

+%struct._IO_FILE = type { i32, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, i8*, %struct._IO_marker*, %struct._IO_FILE*, i32, i32, i32, i16, i8, [1 x i8], i8*, i64, i8*, i8*, i8*, i8*, i32, i32, [40 x i8] }

+%struct._IO_marker = type { %struct._IO_marker*, %struct._IO_FILE*, i32 }

+

+@A = common global [1536 x [1536 x float]] zeroinitializer, align 4

+@B = common global [1536 x [1536 x float]] zeroinitializer, align 4

+@stdout = external global %struct._IO_FILE*

+@.str = private unnamed_addr constant [5 x i8] c"%lf \00", align 1

+@C = common global [1536 x [1536 x float]] zeroinitializer, align 4

+@.str1 = private unnamed_addr constant [2 x i8] c"\0A\00", align 1

+

+define void @init_array() nounwind {

+entry:

+  br label %for.cond

+

+for.cond:                                         ; preds = %for.inc14, %entry

+  %i.0 = phi i32 [ 0, %entry ], [ %inc15, %for.inc14 ]

+  %exitcond1 = icmp ne i32 %i.0, 1536

+  br i1 %exitcond1, label %for.body, label %for.end16

+

+for.body:                                         ; preds = %for.cond

+  br label %for.cond1

+

+for.cond1:                                        ; preds = %for.inc, %for.body

+  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]

+  %exitcond = icmp ne i32 %j.0, 1536

+  br i1 %exitcond, label %for.body3, label %for.end

+

+for.body3:                                        ; preds = %for.cond1

+  %mul = mul nsw i32 %i.0, %j.0

+  %rem = srem i32 %mul, 1024

+  %add = add nsw i32 1, %rem

+  %conv = sitofp i32 %add to double

+  %div = fdiv double %conv, 2.000000e+00

+  %conv4 = fptrunc double %div to float

+  %arrayidx = getelementptr inbounds [1536 x [1536 x float]]* @A, i32 0, i32 %i.0

+  %arrayidx5 = getelementptr inbounds [1536 x float]* %arrayidx, i32 0, i32 %j.0

+  store float %conv4, float* %arrayidx5, align 4

+  %mul6 = mul nsw i32 %i.0, %j.0

+  %rem7 = srem i32 %mul6, 1024

+  %add8 = add nsw i32 1, %rem7

+  %conv9 = sitofp i32 %add8 to double

+  %div10 = fdiv double %conv9, 2.000000e+00

+  %conv11 = fptrunc double %div10 to float

+  %arrayidx12 = getelementptr inbounds [1536 x [1536 x float]]* @B, i32 0, i32 %i.0

+  %arrayidx13 = getelementptr inbounds [1536 x float]* %arrayidx12, i32 0, i32 %j.0

+  store float %conv11, float* %arrayidx13, align 4

+  br label %for.inc

+

+for.inc:                                          ; preds = %for.body3

+  %inc = add nsw i32 %j.0, 1

+  br label %for.cond1

+

+for.end:                                          ; preds = %for.cond1

+  br label %for.inc14

+

+for.inc14:                                        ; preds = %for.end

+  %inc15 = add nsw i32 %i.0, 1

+  br label %for.cond

+

+for.end16:                                        ; preds = %for.cond

+  ret void

+}

+

+define void @print_array() nounwind {

+entry:

+  br label %for.cond

+

+for.cond:                                         ; preds = %for.inc9, %entry

+  %i.0 = phi i32 [ 0, %entry ], [ %inc10, %for.inc9 ]

+  %exitcond1 = icmp ne i32 %i.0, 1536

+  br i1 %exitcond1, label %for.body, label %for.end11

+

+for.body:                                         ; preds = %for.cond

+  br label %for.cond1

+

+for.cond1:                                        ; preds = %for.inc, %for.body

+  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]

+  %exitcond = icmp ne i32 %j.0, 1536

+  br i1 %exitcond, label %for.body3, label %for.end

+

+for.body3:                                        ; preds = %for.cond1

+  %0 = load %struct._IO_FILE** @stdout, align 4

+  %arrayidx = getelementptr inbounds [1536 x [1536 x float]]* @C, i32 0, i32 %i.0

+  %arrayidx4 = getelementptr inbounds [1536 x float]* %arrayidx, i32 0, i32 %j.0

+  %1 = load float* %arrayidx4, align 4

+  %conv = fpext float %1 to double

+  %call = call i32 (%struct._IO_FILE*, i8*, ...)* @fprintf(%struct._IO_FILE* %0, i8* getelementptr inbounds ([5 x i8]* @.str, i32 0, i32 0), double %conv)

+  %rem = srem i32 %j.0, 80

+  %cmp5 = icmp eq i32 %rem, 79

+  br i1 %cmp5, label %if.then, label %if.end

+

+if.then:                                          ; preds = %for.body3

+  %2 = load %struct._IO_FILE** @stdout, align 4

+  %call7 = call i32 (%struct._IO_FILE*, i8*, ...)* @fprintf(%struct._IO_FILE* %2, i8* getelementptr inbounds ([2 x i8]* @.str1, i32 0, i32 0))

+  br label %if.end

+

+if.end:                                           ; preds = %if.then, %for.body3

+  br label %for.inc

+

+for.inc:                                          ; preds = %if.end

+  %inc = add nsw i32 %j.0, 1

+  br label %for.cond1

+

+for.end:                                          ; preds = %for.cond1

+  %3 = load %struct._IO_FILE** @stdout, align 4

+  %call8 = call i32 (%struct._IO_FILE*, i8*, ...)* @fprintf(%struct._IO_FILE* %3, i8* getelementptr inbounds ([2 x i8]* @.str1, i32 0, i32 0))

+  br label %for.inc9

+

+for.inc9:                                         ; preds = %for.end

+  %inc10 = add nsw i32 %i.0, 1

+  br label %for.cond

+

+for.end11:                                        ; preds = %for.cond

+  ret void

+}

+

+declare i32 @fprintf(%struct._IO_FILE*, i8*, ...)

+

+define i32 @main() nounwind {

+entry:

+  call void @init_array()

+  br label %for.cond

+

+for.cond:                                         ; preds = %for.inc19, %entry

+  %i.0 = phi i32 [ 0, %entry ], [ %inc20, %for.inc19 ]

+  %exitcond2 = icmp ne i32 %i.0, 1536

+  br i1 %exitcond2, label %for.body, label %for.end21

+

+for.body:                                         ; preds = %for.cond

+  br label %for.cond1

+

+for.cond1:                                        ; preds = %for.inc16, %for.body

+  %j.0 = phi i32 [ 0, %for.body ], [ %inc17, %for.inc16 ]

+  %exitcond1 = icmp ne i32 %j.0, 1536

+  br i1 %exitcond1, label %for.body3, label %for.end18

+

+for.body3:                                        ; preds = %for.cond1

+  %arrayidx = getelementptr inbounds [1536 x [1536 x float]]* @C, i32 0, i32 %i.0

+  %arrayidx4 = getelementptr inbounds [1536 x float]* %arrayidx, i32 0, i32 %j.0

+  store float 0.000000e+00, float* %arrayidx4, align 4

+  br label %for.cond5

+

+for.cond5:                                        ; preds = %for.inc, %for.body3

+  %k.0 = phi i32 [ 0, %for.body3 ], [ %inc, %for.inc ]

+  %exitcond = icmp ne i32 %k.0, 1536

+  br i1 %exitcond, label %for.body7, label %for.end

+

+for.body7:                                        ; preds = %for.cond5

+  %arrayidx8 = getelementptr inbounds [1536 x [1536 x float]]* @C, i32 0, i32 %i.0

+  %arrayidx9 = getelementptr inbounds [1536 x float]* %arrayidx8, i32 0, i32 %j.0

+  %0 = load float* %arrayidx9, align 4

+  %arrayidx10 = getelementptr inbounds [1536 x [1536 x float]]* @A, i32 0, i32 %i.0

+  %arrayidx11 = getelementptr inbounds [1536 x float]* %arrayidx10, i32 0, i32 %k.0

+  %1 = load float* %arrayidx11, align 4

+  %arrayidx12 = getelementptr inbounds [1536 x [1536 x float]]* @B, i32 0, i32 %k.0

+  %arrayidx13 = getelementptr inbounds [1536 x float]* %arrayidx12, i32 0, i32 %j.0

+  %2 = load float* %arrayidx13, align 4

+  %mul = fmul float %1, %2

+  %add = fadd float %0, %mul

+  %arrayidx14 = getelementptr inbounds [1536 x [1536 x float]]* @C, i32 0, i32 %i.0

+  %arrayidx15 = getelementptr inbounds [1536 x float]* %arrayidx14, i32 0, i32 %j.0

+  store float %add, float* %arrayidx15, align 4

+  br label %for.inc

+

+for.inc:                                          ; preds = %for.body7

+  %inc = add nsw i32 %k.0, 1

+  br label %for.cond5

+

+for.end:                                          ; preds = %for.cond5

+  br label %for.inc16

+

+for.inc16:                                        ; preds = %for.end

+  %inc17 = add nsw i32 %j.0, 1

+  br label %for.cond1

+

+for.end18:                                        ; preds = %for.cond1

+  br label %for.inc19

+

+for.inc19:                                        ; preds = %for.end18

+  %inc20 = add nsw i32 %i.0, 1

+  br label %for.cond

+

+for.end21:                                        ; preds = %for.cond

+  call void @print_array()

+  ret i32 0

+}

+

+;CHECK: Printing analysis 'Polly - Analysis the Loop Nest Tree' for region: 'for.cond => for.end21' in function 'main':

+;CHECK: Loop Nest Tree:

+;CHECK: -----------------------------

+;CHECK:   for

+;CHECK:     for

+;CHECK:       Stmt_for_body3

+;CHECK:       for

+;CHECK:         Stmt_for_body7

+;CHECK: -----------------------------

+;CHECK: End of Loop Nest Tree.

+;CHECK: Innermost Loop(s):

+;CHECK: *****************************

+;CHECK: Stmt_for_body7

+;CHECK: *****************************

+;CHECK: End of Innermost Loop(s).

diff --git a/test/LoopNestTree/simatax.c b/test/LoopNestTree/simatax.c

new file mode 100755

index 0000000..9f5da6e

--- /dev/null

+++ b/test/LoopNestTree/simatax.c

@@ -0,0 +1,36 @@

+#include <math.h>

+

+#define nx 1024

+#define ny 1024

+

+#define DATA_TYPE double

+

+double A[1024][1024], x[1024], y[1024], tmp[1024];

+

+void init_array() {

+  int i, j;

+

+  for (i = 0; i < ny; i++)

+      x[i] = i * M_PI;

+  for (i = 0; i < nx; i++)

+    for (j = 0; j < ny; j++)

+      A[i][j] = ((DATA_TYPE) i*(j+1)) / nx;

+}

+  

+int main() {

+  init_array();

+  int i, j;

+  

+  for (i = 0; i < nx; i++)

+    y[i] = 0;

+  for (i = 0; i < nx; i++){

+      tmp[i] = 0;

+      for (j = 0; j < ny; j++)

+    tmp[i] = tmp[i] + A[i][j] * x[j];

+      for (j = 0; j < ny; j++)

+    y[j] = y[j] + A[i][j] * tmp[i];

+  }

+

+  return 0;

+  

+}

\ No newline at end of file

diff --git a/test/LoopNestTree/simatax.ll b/test/LoopNestTree/simatax.ll

new file mode 100755

index 0000000..9da51d4

--- /dev/null

+++ b/test/LoopNestTree/simatax.ll

@@ -0,0 +1,184 @@

+; RUN: opt %loadPolly %defaultOpts -polly-loopnesttree -analyze %s | FileCheck %s

+; ModuleID = 'simatax.s'

+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"

+target triple = "i386-pc-linux-gnu"

+

+@x = common global [1024 x double] zeroinitializer, align 4

+@A = common global [1024 x [1024 x double]] zeroinitializer, align 4

+@y = common global [1024 x double] zeroinitializer, align 4

+@tmp = common global [1024 x double] zeroinitializer, align 4

+

+define void @init_array() nounwind {

+entry:

+  br label %for.cond

+

+for.cond:                                         ; preds = %for.inc, %entry

+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]

+  %exitcond2 = icmp ne i32 %i.0, 1024

+  br i1 %exitcond2, label %for.body, label %for.end

+

+for.body:                                         ; preds = %for.cond

+  %conv = sitofp i32 %i.0 to double

+  %mul = fmul double %conv, 0x400921FB54442D18

+  %arrayidx = getelementptr inbounds [1024 x double]* @x, i32 0, i32 %i.0

+  store double %mul, double* %arrayidx, align 4

+  br label %for.inc

+

+for.inc:                                          ; preds = %for.body

+  %inc = add nsw i32 %i.0, 1

+  br label %for.cond

+

+for.end:                                          ; preds = %for.cond

+  br label %for.cond1

+

+for.cond1:                                        ; preds = %for.inc17, %for.end

+  %i.1 = phi i32 [ 0, %for.end ], [ %inc18, %for.inc17 ]

+  %exitcond1 = icmp ne i32 %i.1, 1024

+  br i1 %exitcond1, label %for.body4, label %for.end19

+

+for.body4:                                        ; preds = %for.cond1

+  br label %for.cond5

+

+for.cond5:                                        ; preds = %for.inc14, %for.body4

+  %j.0 = phi i32 [ 0, %for.body4 ], [ %inc15, %for.inc14 ]

+  %exitcond = icmp ne i32 %j.0, 1024

+  br i1 %exitcond, label %for.body8, label %for.end16

+

+for.body8:                                        ; preds = %for.cond5

+  %conv9 = sitofp i32 %i.1 to double

+  %add = add nsw i32 %j.0, 1

+  %conv10 = sitofp i32 %add to double

+  %mul11 = fmul double %conv9, %conv10

+  %div = fdiv double %mul11, 1.024000e+03

+  %arrayidx12 = getelementptr inbounds [1024 x [1024 x double]]* @A, i32 0, i32 %i.1

+  %arrayidx13 = getelementptr inbounds [1024 x double]* %arrayidx12, i32 0, i32 %j.0

+  store double %div, double* %arrayidx13, align 4

+  br label %for.inc14

+

+for.inc14:                                        ; preds = %for.body8

+  %inc15 = add nsw i32 %j.0, 1

+  br label %for.cond5

+

+for.end16:                                        ; preds = %for.cond5

+  br label %for.inc17

+

+for.inc17:                                        ; preds = %for.end16

+  %inc18 = add nsw i32 %i.1, 1

+  br label %for.cond1

+

+for.end19:                                        ; preds = %for.cond1

+  ret void

+}

+

+define i32 @main() nounwind {

+entry:

+  call void @init_array()

+  br label %for.cond

+

+for.cond:                                         ; preds = %for.inc, %entry

+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]

+  %exitcond3 = icmp ne i32 %i.0, 1024

+  br i1 %exitcond3, label %for.body, label %for.end

+

+for.body:                                         ; preds = %for.cond

+  %arrayidx = getelementptr inbounds [1024 x double]* @y, i32 0, i32 %i.0

+  store double 0.000000e+00, double* %arrayidx, align 4

+  br label %for.inc

+

+for.inc:                                          ; preds = %for.body

+  %inc = add nsw i32 %i.0, 1

+  br label %for.cond

+

+for.end:                                          ; preds = %for.cond

+  br label %for.cond1

+

+for.cond1:                                        ; preds = %for.inc29, %for.end

+  %i.1 = phi i32 [ 0, %for.end ], [ %inc30, %for.inc29 ]

+  %exitcond2 = icmp ne i32 %i.1, 1024

+  br i1 %exitcond2, label %for.body3, label %for.end31

+

+for.body3:                                        ; preds = %for.cond1

+  %arrayidx4 = getelementptr inbounds [1024 x double]* @tmp, i32 0, i32 %i.1

+  store double 0.000000e+00, double* %arrayidx4, align 4

+  br label %for.cond5

+

+for.cond5:                                        ; preds = %for.inc13, %for.body3

+  %j.0 = phi i32 [ 0, %for.body3 ], [ %inc14, %for.inc13 ]

+  %exitcond = icmp ne i32 %j.0, 1024

+  br i1 %exitcond, label %for.body7, label %for.end15

+

+for.body7:                                        ; preds = %for.cond5

+  %arrayidx8 = getelementptr inbounds [1024 x double]* @tmp, i32 0, i32 %i.1

+  %0 = load double* %arrayidx8, align 4

+  %arrayidx9 = getelementptr inbounds [1024 x [1024 x double]]* @A, i32 0, i32 %i.1

+  %arrayidx10 = getelementptr inbounds [1024 x double]* %arrayidx9, i32 0, i32 %j.0

+  %1 = load double* %arrayidx10, align 4

+  %arrayidx11 = getelementptr inbounds [1024 x double]* @x, i32 0, i32 %j.0

+  %2 = load double* %arrayidx11, align 4

+  %mul = fmul double %1, %2

+  %add = fadd double %0, %mul

+  %arrayidx12 = getelementptr inbounds [1024 x double]* @tmp, i32 0, i32 %i.1

+  store double %add, double* %arrayidx12, align 4

+  br label %for.inc13

+

+for.inc13:                                        ; preds = %for.body7

+  %inc14 = add nsw i32 %j.0, 1

+  br label %for.cond5

+

+for.end15:                                        ; preds = %for.cond5

+  br label %for.cond16

+

+for.cond16:                                       ; preds = %for.inc26, %for.end15

+  %j.1 = phi i32 [ 0, %for.end15 ], [ %inc27, %for.inc26 ]

+  %exitcond1 = icmp ne i32 %j.1, 1024

+  br i1 %exitcond1, label %for.body18, label %for.end28

+

+for.body18:                                       ; preds = %for.cond16

+  %arrayidx19 = getelementptr inbounds [1024 x double]* @y, i32 0, i32 %j.1

+  %3 = load double* %arrayidx19, align 4

+  %arrayidx20 = getelementptr inbounds [1024 x [1024 x double]]* @A, i32 0, i32 %i.1

+  %arrayidx21 = getelementptr inbounds [1024 x double]* %arrayidx20, i32 0, i32 %j.1

+  %4 = load double* %arrayidx21, align 4

+  %arrayidx22 = getelementptr inbounds [1024 x double]* @tmp, i32 0, i32 %i.1

+  %5 = load double* %arrayidx22, align 4

+  %mul23 = fmul double %4, %5

+  %add24 = fadd double %3, %mul23

+  %arrayidx25 = getelementptr inbounds [1024 x double]* @y, i32 0, i32 %j.1

+  store double %add24, double* %arrayidx25, align 4

+  br label %for.inc26

+

+for.inc26:                                        ; preds = %for.body18

+  %inc27 = add nsw i32 %j.1, 1

+  br label %for.cond16

+

+for.end28:                                        ; preds = %for.cond16

+  br label %for.inc29

+

+for.inc29:                                        ; preds = %for.end28

+  %inc30 = add nsw i32 %i.1, 1

+  br label %for.cond1

+

+for.end31:                                        ; preds = %for.cond1

+  ret i32 0

+}

+

+;CHECK: Printing analysis 'Polly - Analysis the Loop Nest Tree' for region: 'for.cond => for.end31' in function 'main':

+;CHECK: Loop Nest Tree:

+;CHECK: -----------------------------

+;CHECK:   for

+;CHECK:     Stmt_for_body

+;CHECK:   for

+;CHECK:     Stmt_for_body3

+;CHECK:     for

+;CHECK:       Stmt_for_body7

+;CHECK:     for

+;CHECK:       Stmt_for_body18

+;CHECK: -----------------------------

+;CHECK: End of Loop Nest Tree.

+;CHECK: Innermost Loop(s):

+;CHECK: *****************************

+;CHECK: Stmt_for_body

+;CHECK: Stmt_for_body7

+;CHECK: Stmt_for_body18

+;CHECK: *****************************

+;CHECK: End of Innermost Loop(s).

\ No newline at end of file

diff --git a/test/LoopNestTree/simple_loop.c b/test/LoopNestTree/simple_loop.c

new file mode 100755

index 0000000..0e5905e

--- /dev/null

+++ b/test/LoopNestTree/simple_loop.c

@@ -0,0 +1,20 @@

+#define N 100

+int A[N];

+

+void init_array() {

+  int i=0;

+  for(i=0; i<N; i++) {

+    A[i] = i;

+  }

+}

+

+

+int main() {

+  int i = 0;

+  

+  init_array();

+  for (i=0; i<N;i++) {

+    A[i] = A[i] + i;

+  }

+return 0;

+}

diff --git a/test/LoopNestTree/simple_loop.ll b/test/LoopNestTree/simple_loop.ll

new file mode 100644

index 0000000..06274a8

--- /dev/null

+++ b/test/LoopNestTree/simple_loop.ll

@@ -0,0 +1,67 @@

+; RUN: opt %loadPolly %defaultOpts -polly-loopnesttree -analyze %s | FileCheck %s

+; ModuleID = 'simple_loop.s'

+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"

+target triple = "i386-pc-linux-gnu"

+

+@A = common global [100 x i32] zeroinitializer, align 4

+

+define void @init_array() nounwind {

+entry:

+  br label %for.cond

+

+for.cond:                                         ; preds = %for.inc, %entry

+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]

+  %exitcond = icmp ne i32 %i.0, 100

+  br i1 %exitcond, label %for.body, label %for.end

+

+for.body:                                         ; preds = %for.cond

+  %arrayidx = getelementptr inbounds [100 x i32]* @A, i32 0, i32 %i.0

+  store i32 %i.0, i32* %arrayidx, align 4

+  br label %for.inc

+

+for.inc:                                          ; preds = %for.body

+  %inc = add nsw i32 %i.0, 1

+  br label %for.cond

+

+for.end:                                          ; preds = %for.cond

+  ret void

+}

+

+define i32 @main() nounwind {

+entry:

+  call void @init_array()

+  br label %for.cond

+

+for.cond:                                         ; preds = %for.inc, %entry

+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]

+  %exitcond = icmp ne i32 %i.0, 100

+  br i1 %exitcond, label %for.body, label %for.end

+

+for.body:                                         ; preds = %for.cond

+  %arrayidx = getelementptr inbounds [100 x i32]* @A, i32 0, i32 %i.0

+  %0 = load i32* %arrayidx, align 4

+  %add = add nsw i32 %0, %i.0

+  %arrayidx1 = getelementptr inbounds [100 x i32]* @A, i32 0, i32 %i.0

+  store i32 %add, i32* %arrayidx1, align 4

+  br label %for.inc

+

+for.inc:                                          ; preds = %for.body

+  %inc = add nsw i32 %i.0, 1

+  br label %for.cond

+

+for.end:                                          ; preds = %for.cond

+  ret i32 0

+}

+

+;CHECK: Printing analysis 'Polly - Analysis the Loop Nest Tree' for region: 'for.cond => for.end' in function 'main':

+;CHECK: Loop Nest Tree:

+;CHECK: -----------------------------

+;CHECK:   for

+;CHECK:     Stmt_for_body

+;CHECK: -----------------------------

+;CHECK: End of Loop Nest Tree.

+;CHECK: Innermost Loop(s):

+;CHECK: *****************************

+;CHECK: Stmt_for_body

+;CHECK: *****************************

+;CHECK: End of Innermost Loop(s).

-- 

1.7.5.1

[Jun-qi Deng]

And Here is another testcase for the pass

From ab08f2b2912aa118b783863ab9b084a9782d6457 Mon Sep 17 00:00:00 2001

From: TangKK <dengjunq...@hotmail.com>

Date: Wed, 8 Aug 2012 17:03:45 +0800

Subject: [PATCH] Another LoopNestTree Analysis Testcase

---

 .../kernels/2mm/2mm_without_param.ll               |   29 ++++++++++++++++++-

 1 files changed, 27 insertions(+), 2 deletions(-)

diff --git a/test/polybench/linear-algebra/kernels/2mm/2mm_without_param.ll b/test/polybench/linear-algebra/kernels/2mm/2mm_without_param.ll

index eef2b63..7dc4ddd 100644

--- a/test/polybench/linear-algebra/kernels/2mm/2mm_without_param.ll

+++ b/test/polybench/linear-algebra/kernels/2mm/2mm_without_param.ll

@@ -1,4 +1,5 @@

-; RUN: opt %loadPolly  %defaultOpts -polly-detect -analyze  %s | FileCheck %s

+; RUN: opt %loadPolly  %defaultOpts -polly-detect -analyze  %s | FileCheck %s -check-prefix=NORMAL

+; RUN: opt %loadPolly %defaultOpts -polly-loopnesttree -analyze %s | FileCheck %s -check-prefix=LNT

 ; ModuleID = './linear-algebra/kernels/2mm/2mm_without_param.ll'

 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"

 target triple = "x86_64-unknown-linux-gnu"

@@ -98,4 +99,28 @@ bb14.preheader:                                   ; preds = %bb14.preheader.preh

 return:                                           ; preds = %bb15

   ret void

 }

-; CHECK: Valid Region for Scop: bb5.preheader => return

+; NORMAL: Valid Region for Scop: bb5.preheader => return

+

+; LNT: Printing analysis 'Polly - Analysis the Loop Nest Tree' for region: 'bb5.preheader => return' in function 'scop_func':

+; LNT: Loop Nest Tree:

+; LNT: -----------------------------

+; LNT:   for

+; LNT:     for

+; LNT:       Stmt_bb_nph27_us

+; LNT:       for

+; LNT:         Stmt_bb2_us

+; LNT:       Stmt_bb4_us

+; LNT:   for

+; LNT:     for

+; LNT:       Stmt_bb_nph_us

+; LNT:       for

+; LNT:         Stmt_bb11_us

+; LNT:       Stmt_bb13_us

+; LNT: -----------------------------

+; LNT: End of Loop Nest Tree.

+; LNT: Innermost Loop(s):

+; LNT: *****************************

+; LNT: Stmt_bb2_us

+; LNT: Stmt_bb11_us

+; LNT: *****************************

+; LNT: End of Innermost Loop(s).

-- 

1.7.5.1

[Hongbin Zheng]

Hi Junqi,

Why we need to change the type of a node?

> +
> + LoopNestTreeBase *getParent() const { return Parent; }
> + void setParent(LoopNestTreeBase *P) { Parent = P; }

This looks ok, but, could us avoid changing the parent of the Node, or
if it is use by the tree builder only, could us mark this function as
private, and claim the builder class as friend of the the current
class, like:

friend class LoopNestTree.

By doing this, we can prevent the users from changing the node's parent.

> +
> + virtual void print(llvm::raw_ostream &OS, unsigned indent) const;
> +};
> +
> +
> //===---------------------------------------------------------------------===//
> + /// @brief A derived class standing for the "for" statement node of the
> tree
> + ///
> + class LoopNestTreeFor : public LoopNestTreeBase {
> + SmallVector<LoopNestTreeBase*, 8> Children;
> +
> + public:
> + LoopNestTreeFor() : LoopNestTreeBase(FOR) {}
> + ~LoopNestTreeFor() { Children.clear(); }
> +
> + void addChild(LoopNestTreeBase *Child) { Children.push_back(Child); }
> +
> + // DFS the LoopNestTree and print out all the nodes
> + void printTree(llvm::raw_ostream &OS, unsigned indent) const;
> +
> + // DFS the LoopNestTree and delete all the nodes.
> + LoopNestTreeFor *deleteTree();

This is not needed, we can simply delete all children of the current
node in the destructor, like:
DeleteContainerPointers(Children);

For more detail, please have a look at the definition of the function
DeleteContainerPointers in STLExtra.h

I think the "llvm::" is not needed.

> +static void printIndent(llvm::raw_ostream &OS, unsigned indent) {
> + for (unsigned i =0; i < indent; i++) {
> + OS << " ";
> + }
> +}
> +
> +void LoopNestTreeBase::print(llvm::raw_ostream &OS, unsigned indent) const
> {
> + printIndent(OS, indent);

The ostream class have a function named "indent", doing exactly the same thing.

> +
> + switch (NodeType) {
> + case FOR:
> + { OS << "for\n"; break; }

The { } are not needed.

> + case SCOPSTMT:
> + { OS << "stmt\n"; break; }

The { } are not needed.

> + default:
> + { OS << "unknown\n"; break; }

The { } are not needed.

> + };
> +}
> +
> +void LoopNestTreeStmt::print(llvm::raw_ostream &OS, unsigned indent) const
> {
> + printIndent(OS, indent);
> + isl_map *scattering = stmt->getScattering();
> + const char *Name = isl_map_get_tuple_name(scattering, isl_dim_in);
> + OS << Name << "\n";
> + isl_map_free(scattering);
> +}
> +
> +void LoopNestTreeFor::printTree(llvm::raw_ostream &OS, unsigned indent)
> const {
> + if(indent > 0)
> + this->print(OS, indent);
> + for(SmallVectorImpl<LoopNestTreeBase*>::const_iterator BI =
> Children.begin(),
> + BE = Children.end(); BI != BE; ++BI) {
> + if (isa<LoopNestTreeStmt>(*BI))
> + cast<LoopNestTreeStmt>(*BI)->print(OS, indent+2);

Why the cast is needed? The BaseClass already has the print function.

The insert function will return if the inserttion is successed, so we
can simply try to insert intcont into Conset, and if the insertion is
success, it means the value already existed, otherwise the value is a
new value.

We should add an assertion instead of a warning.
Or, refuse to build the the LoopNestTree.

Please add a (), like
Root = new LoopNestTreeFor();

[Tobias Grosser]

On 08/08/2012 10:38 AM, Jun-qi Deng wrote:
> The patches are pasted here:

Hi Jun-qi Deng,

could you please add the patches as attachments or use git send-email.
Otherwise, they do not apply cleanly. (At a previous point I asked ether
to also past them into the email, but this is actually not necessary).

To this patch itself. Unfortunately, I did not follow the discussion
previously. I am still catching up. As far as I understand, the reason
you looked into building the loop tree from the original code was:

> Hello! Now I understand how to find innermost loop using isl_band
> forest which is generated by computing isl_schedule. So there is no
> problem to find the innermost loop after the isl optimizer. But what
> if I want to find the original untransformed code's innermost loop? Is
> it possible that I use the scattering information of each scopstmt
> within a scop to find the innermost loop? Or are there any ways that I
> can build a schedule of the original code(which does not re-reschedule
> anything at all, but just a description of the original schedule)
> which is similar to the isl_schedule computed by
> isl_union_set_compute_schedule, so that I can use a similar method as
> the isl_band forest to locate the innermost loop? Thank you!

It seems the problem you have been solving is that your optimization
works on the band tree, but you cannot get a band tree from the original
schedule. So now you want to build something similar from the original
schedule.

I am a little bit afraid that we now have two kind of loop/band trees
and transformations need to pick the one that is able to derive bands
depending where the schedule comes from. This seems to add complexity.
How do you determine which tree to build/which analysis to run? I think
it would be good to have your transformation just depend on one input
data structure. The band tree, the innermost loop analysis or even
another data structure.

What was the reason the band tree did not work for you? What is the
exact reason you want to apply your analysis on the original schedule?
Can the very same thing be achieved by using the isl_scheduler, but
restricting it in a way that only certain transformations (or none) are
allowed? You can e.g. set --isl-schedule-max-coefficient=1 to disable
scaling of the loops. So, could the band tree be used, if the isl
scheduler is restricted sufficiently (we could even contribute patches
to isl).

In case you want to use the innermost loop analysis, does this analysis
work on every possible schedule. I am asking here, as I have the feeling
the analysis is currently pattern matching the schedules in a way that
is specific to the schedules built by our front-end. Would the analysis
work with arbitrary schedules (e.g. provided by users?) or created by
the isl scheduler?

Cheers
Tobi

>
> From d4c789ec0e79aa6fd4820cf5f3602e90e156a906 Mon Sep 17 00:00:00 2001
> From: TangKK <dengjunq...@hotmail.com

> <mailto:dengjunq...@hotmail.com>>

> Date: Wed, 18 Jul 2012 16:37:26 +0800
> Subject: [PATCH 1/7] Add LoopNestTree Analysis Pass - Analysis the Loop Nest
> Tree
>
> Signed-off-by: TangKK <dengjunq...@hotmail.com

> <mailto:dengjunq...@hotmail.com>>

> <mailto:dengjunq...@hotmail.com>>

[Jun-qi Deng]

Hello ether! I agree with all of your comments. I'll fix them very soon and upload a fixed patch here.

regards,

tangkk

2012/8/8 Hongbin Zheng <ethe...@gmail.com>

[Jun-qi Deng]

could you please add the patches as attachments or use git send-email. Otherwise, they do not apply cleanly. (At a previous point I asked ether to also past them into the email, but this is actually not necessary).

Yes, I'll do that next time I upload the patches. 

To this patch itself. Unfortunately, I did not follow the discussion previously. I am still catching up. As far as I understand, the reason you looked into building the loop tree from the original code was:

Hello! Now I understand how to find innermost loop using isl_band
forest which is generated by computing isl_schedule. So there is no
problem to find the innermost loop after the isl optimizer. But what
if I want to find the original untransformed code's innermost loop? Is
it possible that I use the scattering information of each scopstmt
within a scop to find the innermost loop? Or are there any ways that I
can build a schedule of the original code(which does not re-reschedule
anything at all, but just a description of the original schedule)
which is similar to the isl_schedule computed by
isl_union_set_compute_schedule, so that I can use a similar method as
the isl_band forest to locate the innermost loop? Thank you!

It seems the problem you have been solving is that your optimization works on the band tree, but you cannot get a band tree from the original schedule. So now you want to build something similar from the original schedule.

Yes, it is. But now I find out a way to analysis the band tree(or is it similar to loop nest tree?)  of both the original schedule and the isl opt transformed schedule. The pass I presented in the previous posts is an implementation of such a way.

I am a little bit afraid that we now have two kind of loop/band trees and transformations need to pick the one that is able to derive bands
depending where the schedule comes from. This seems to add complexity.
How do you determine which tree to build/which analysis to run? I think
it would be good to have your transformation just depend on one input data structure. The band tree, the innermost loop analysis or even another data structure.

What was the reason the band tree did not work for you? What is the exact reason you want to apply your analysis on the original schedule? Can the very same thing be achieved by using the isl_scheduler, but restricting it in a way that only certain transformations (or none) are allowed? You can e.g. set --isl-schedule-max-coefficient=1 to disable scaling of the loops. So, could the band tree be used, if the isl scheduler is restricted sufficiently (we could even contribute patches to isl).

What I want to do is, to find a general way to get the loop/band tree of the code, no matter where the code comes from, before or after the isl optimizer. So I think the pass I implemented has already solved the problem you mentioned above. I think this won't add complexity because my pass can work in both cases(I mean it can give a correct result of both the original schedule and the transformed schedule).

In case you want to use the innermost loop analysis, does this analysis
work on every possible schedule. I am asking here, as I have the feeling the analysis is currently pattern matching the schedules in a way that is specific to the schedules built by our front-end. Would the analysis work with arbitrary schedules (e.g. provided by users?) or created by the isl scheduler?

It works with the the schedules created by the isl scheduler. As for those provided by users,  I never consider this before. Will such schedules obey certain rules as those built by polly's front-end?

regards,

tangkk

[Jun-qi Deng]

Hi Tobi, I'm sorry but I made a mistake in this previous post. For the compatibility of isl scheduler, some improvements are still needed, and I'm working on it for the moment.

regards,

tangkk

[Jun-qi Deng]

Hello! Here attached are the new patches of LoopNestTree Analysis. I accept all the comments ether raised in the last mail and also according to both ether and tobi's suggestion, this new implementation is also compatible with the scop transformed by isl scheduler. My algorithm was changed a little compared with the former one:

//===----------------------------------------------------------------------------==//

//

// This pass implements the following algorithm for creating a loop nest tree in

// the context of Polly:

// First, we creat a "Root" node to be the ultimate parent of all nodes

// Then we scan pos by pos the scatterings of all the scopstmts. During the scanning:

// If we encounter different (value) constant dimensions of the same pos,

// we add new branches(same constants of the same pos only means one node);

// If we encounter a new variable dimension, we add a new "FOR" node(child);

// If within a variable dimension there is "zero" dimensions, add "SCOPSTMT" nodes,

// for these dimensions; we separate scopstmts into different

// groups according to the above mentioned different constants;

// a scattering will not be got rid of until a "SCOPSTMT" node is produced.

// After such process, the loop nest tree is created, and those "SCOPSTMT" nodes

// without siblings(no matter "FOR" or "SCOPSTMT") are innermost.

//===----------------------------------------------------------------------===//

Note that for compatibility of polly-opt-isl, this time I add a testcase "sim2mm.ll" which runs: "; RUN: opt %loadPolly %defaultOpts -polly-opt-isl -polly-loopnesttree -analyze %s | FileCheck %s"

The optimized scop of "sim2mm" is

    Context:

    {  :  }

    Statements {

        Stmt_for_body3

            Domain :=

                { Stmt_for_body3[i0, i1] : i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023 };

            Scattering :=

                { Stmt_for_body3[i0, i1] -> [0, o1, o2, i0, i1] : exists (e0 = [(o1)/32], e1 = [(o2)/32]: 32e0 = o1 and 32e1 = o2 and o1 <= i0 and o1 >= -31 + i0 and o2 <= i1 and o2 >= -31 + i1 and i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023) };

            WriteAccess :=

                { Stmt_for_body3[i0, i1] -> MemRef_tmp[1024i0 + i1] };

        Stmt_for_body7

            Domain :=

                { Stmt_for_body7[i0, i1, i2] : i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023 and i2 >= 0 and i2 <= 1023 };

            Scattering :=

                { Stmt_for_body7[i0, i1, i2] -> [1, o1, o2, o3, i0, i1, i2] : exists (e0 = [(o1)/32], e1 = [(o2)/32], e2 = [(o3)/32]: 32e0 = o1 and 32e1 = o2 and 32e2 = o3 and o1 <= i0 and o1 >= -31 + i0 and o2 <= i1 and o2 >= -31 + i1 and o3 <= i2 and o3 >= -31 + i2 and i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023 and i2 >= 0 and i2 <= 1023) };

            ReadAccess :=

                { Stmt_for_body7[i0, i1, i2] -> MemRef_A[1024i0 + i2] };

            ReadAccess :=

                { Stmt_for_body7[i0, i1, i2] -> MemRef_B[i1 + 1024i2] };

            ReadAccess :=

                { Stmt_for_body7[i0, i1, i2] -> MemRef_tmp[1024i0 + i1] };

            WriteAccess :=

                { Stmt_for_body7[i0, i1, i2] -> MemRef_tmp[1024i0 + i1] };

        Stmt_for_body26

            Domain :=

                { Stmt_for_body26[i0, i1] : i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023 };

            Scattering :=

                { Stmt_for_body26[i0, i1] -> [2, o1, o2, i0, i1] : exists (e0 = [(o1)/32], e1 = [(o2)/32]: 32e0 = o1 and 32e1 = o2 and o1 <= i0 and o1 >= -31 + i0 and o2 <= i1 and o2 >= -31 + i1 and i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023) };

            ReadAccess :=

                { Stmt_for_body26[i0, i1] -> MemRef_D[1024i0 + i1] };

            WriteAccess :=

                { Stmt_for_body26[i0, i1] -> MemRef_D[1024i0 + i1] };

        Stmt_for_body32

            Domain :=

                { Stmt_for_body32[i0, i1, i2] : i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023 and i2 >= 0 and i2 <= 1023 };

            Scattering :=

                { Stmt_for_body32[i0, i1, i2] -> [3, o1, o2, o3, i0, i1, i2] : exists (e0 = [(o1)/32], e1 = [(o2)/32], e2 = [(o3)/32]: 32e0 = o1 and 32e1 = o2 and 32e2 = o3 and o1 <= i0 and o1 >= -31 + i0 and o2 <= i1 and o2 >= -31 + i1 and o3 <= i2 and o3 >= -31 + i2 and i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023 and i2 >= 0 and i2 <= 1023) };

            ReadAccess :=

                { Stmt_for_body32[i0, i1, i2] -> MemRef_tmp[1024i0 + i2] };

            ReadAccess :=

                { Stmt_for_body32[i0, i1, i2] -> MemRef_C[i1 + 1024i2] };

            ReadAccess :=

                { Stmt_for_body32[i0, i1, i2] -> MemRef_D[1024i0 + i1] };

            WriteAccess :=

                { Stmt_for_body32[i0, i1, i2] -> MemRef_D[1024i0 + i1] };

    }

Printing analysis 'Polly - Optimize schedule of SCoP' for region: 'for.cond => for.end49' in function 'main':

and the Cloog of the optimized "sim2mm" is 

Printing analysis 'Execute Cloog code generation' for region: 'for.cond => for.end49' in function 'main':

main():

for (c2=0;c2<=1023;c2+=32) {

  for (c3=0;c3<=1023;c3+=32) {

    for (c4=c2;c4<=c2+31;c4++) {

      for (c5=c3;c5<=c3+31;c5++) {

        Stmt_for_body3(c4,c5);

      }

    }

  }

}

for (c2=0;c2<=1023;c2+=32) {

  for (c3=0;c3<=1023;c3+=32) {

    for (c4=0;c4<=1023;c4+=32) {

      for (c5=c2;c5<=c2+31;c5++) {

        for (c6=c3;c6<=c3+31;c6++) {

          for (c7=c4;c7<=c4+31;c7++) {

            Stmt_for_body7(c5,c6,c7);

          }

        }

      }

    }

  }

}

for (c2=0;c2<=1023;c2+=32) {

  for (c3=0;c3<=1023;c3+=32) {

    for (c4=c2;c4<=c2+31;c4++) {

      for (c5=c3;c5<=c3+31;c5++) {

        Stmt_for_body26(c4,c5);

      }

    }

  }

}

for (c2=0;c2<=1023;c2+=32) {

  for (c3=0;c3<=1023;c3+=32) {

    for (c4=0;c4<=1023;c4+=32) {

      for (c5=c2;c5<=c2+31;c5++) {

        for (c6=c3;c6<=c3+31;c6++) {

          for (c7=c4;c7<=c4+31;c7++) {

            Stmt_for_body32(c5,c6,c7);

          }

        }

      }

    }

  }

}

and the analysis result of LoopNestTree of the optimized "sim2mm" is:

;CHECK: Printing analysis 'Polly - Analysis the Loop Nest Tree' for region: 'for.cond => for.end49' in function 'main':

;CHECK: Loop Nest Tree:

;CHECK: -----------------------------

;CHECK:   for

;CHECK:     for

;CHECK:       for

;CHECK:         for

;CHECK:           Stmt_for_body3

;CHECK:   for

;CHECK:     for

;CHECK:       for

;CHECK:         for

;CHECK:           for

;CHECK:             for

;CHECK:               Stmt_for_body7

;CHECK:   for

;CHECK:     for

;CHECK:       for

;CHECK:         for

;CHECK:           Stmt_for_body26

;CHECK:   for

;CHECK:     for

;CHECK:       for

;CHECK:         for

;CHECK:           for

;CHECK:             for

;CHECK:               Stmt_for_body32

;CHECK: -----------------------------

;CHECK: End of Loop Nest Tree.

;CHECK: Innermost Loop(s):

;CHECK: *****************************

;CHECK: Stmt_for_body3

;CHECK: Stmt_for_body7

;CHECK: Stmt_for_body26

;CHECK: Stmt_for_body32

;CHECK: *****************************

;CHECK: End of Innermost Loop(s).

And here pasted the patches.

From 854d303fb4110adf775f4226932c21a07af0a603 Mon Sep 17 00:00:00 2001

From: TangKK <dengjunq...@hotmail.com>

Date: Wed, 18 Jul 2012 16:37:26 +0800

Subject: [PATCH 1/7] Add LoopNestTree Analysis Pass - Analysis the Loop Nest

 Tree

Signed-off-by: TangKK <dengjunq...@hotmail.com>

---

 include/polly/LinkAllPasses.h         |    2 +

 include/polly/LoopNestTreeAnalysis.h  |  174 ++++++++++++++++++++

 lib/Analysis/CMakeLists.txt           |    1 +

 lib/Analysis/LoopNestTreeAnalysis.cpp |  288 +++++++++++++++++++++++++++++++++

 lib/RegisterPasses.cpp                |    2 +

 test/CMakeLists.txt                   |    1 +

 6 files changed, 468 insertions(+), 0 deletions(-)

 create mode 100755 include/polly/LoopNestTreeAnalysis.h

 create mode 100755 lib/Analysis/LoopNestTreeAnalysis.cpp

diff --git a/include/polly/LinkAllPasses.h b/include/polly/LinkAllPasses.h

index ed2442b..38748a6 100644

--- a/include/polly/LinkAllPasses.h

+++ b/include/polly/LinkAllPasses.h

@@ -43,6 +43,7 @@ namespace polly {

   Pass *createDOTViewerPass();

   Pass *createIndependentBlocksPass();

   Pass *createIndVarSimplifyPass();

+  Pass *createLoopNestTreePass();

   Pass *createJSONExporterPass();

   Pass *createJSONImporterPass();

   Pass *createPipforPass();

@@ -94,6 +95,7 @@ namespace {

        createDOTViewerPass();

        createIndependentBlocksPass();

        createIndVarSimplifyPass();

+       createLoopNestTreePass();

        createJSONExporterPass();

        createJSONImporterPass();

        createPipforPass();

diff --git a/include/polly/LoopNestTreeAnalysis.h b/include/polly/LoopNestTreeAnalysis.h

new file mode 100755

index 0000000..6348275

--- /dev/null

+++ b/include/polly/LoopNestTreeAnalysis.h

@@ -0,0 +1,174 @@

+//===---------- LoopNestTreeAnalysis.h  - Analysis the Loop Nest Tree-------===//

+//

+//                     The LLVM Compiler Infrastructure

+//

+// This file is distributed under the University of Illinois Open Source

+// License. See LICENSE.TXT for details.

+//

+//===----------------------------------------------------------------------------==//

+//

+// This pass implements the following algorithm for creating a loop nest tree in

+// the context of Polly:

+// First, we creat a "Root" node to be the ultimate parent of all nodes

+// Then we scan pos by pos the scatterings of all the scopstmts. During the scanning:

+// If we encounter different (value) constant dimensions of the same pos,

+// we add new branches(same constants of the same pos only means one node);

+// If we encounter a new variable dimension, we add a new "FOR" node(child);

+// If within a variable dimension there is "zero" dimensions, add "SCOPSTMT" nodes,

+// for these dimensions; we separate scopstmts into different

+// groups according to the above mentioned different constants;

+    virtual void print(raw_ostream &OS, unsigned indent) const;

+

+    LoopNestTreeBase *getParent() const { return Parent; }

+

+  private:

+    void setParent(LoopNestTreeBase *P) { Parent = P; }

+

+    friend class LoopNestTree;

+  };

+

+  //===---------------------------------------------------------------------===//

+  /// @brief A derived class standing for the "for" statement node of the tree

+  ///

+  class LoopNestTreeFor : public LoopNestTreeBase {

+    SmallVector<LoopNestTreeBase*, 8> Children;

+

+    void addChild(LoopNestTreeBase *Child) { Children.push_back(Child); }

+

+    friend class LoopNestTree;

+  public:

+    LoopNestTreeFor() : LoopNestTreeBase(FOR) {}

+

+    ~LoopNestTreeFor();

+

+    // @brief fill the Container with "Children"

+    void getChildren(SmallVectorImpl<LoopNestTreeBase*> &Container) const {

+      Container = Children;

+    }

+    

+    // DFS the LoopNestTree and print out all the nodes

+    void printTree(raw_ostream &OS, unsigned indent) const;

+

+    /// Methods for support type inquiry through isa, cast, and dyn_cast:

+    static inline bool classof(const LoopNestTreeFor *N) { return true; }

+    static inline bool classof(const LoopNestTreeBase *N) {

+      return N->getNodeType() == FOR;

+    }

+  };

+

+  //===---------------------------------------------------------------------===//

+  /// @brief A derived class standing for the scopstmt node of the tree

+  ///

+  class LoopNestTreeStmt : public LoopNestTreeBase {

+    ScopStmt  *stmt;

+

+    void setScopStmt(ScopStmt *S) { stmt = S; }

+

+    friend class LoopNestTree;

+

+  public:

+    LoopNestTreeStmt() : LoopNestTreeBase(SCOPSTMT) {}

+

+    ScopStmt *getScopStmt() const { return stmt; }

+

+    void print(raw_ostream &OS, unsigned indent) const;

+    void printScop(raw_ostream &OS) const;

+    virtual void releaseMemory();

+

+    bool runOnScop(Scop &S);

+

+    // @brief To get the innermost stmts' names

+    // @param InnermostStmtNames is an input container passed by the user

+    // @param InnermostStmtNames is also filled with the output of this function

+    void getInnermostStmts(std::set<const char*> &InnermostStmtNames) const;

+

+  private:

index 0000000..43cd505

--- /dev/null

+++ b/lib/Analysis/LoopNestTreeAnalysis.cpp

@@ -0,0 +1,288 @@

+//===---------- LoopNestTreeAnalysis.cpp  - Analysis the Loop Nest Tree-------===//

+//

+//                     The LLVM Compiler Infrastructure

+//

+// This file is distributed under the University of Illinois Open Source

+// License. See LICENSE.TXT for details.

+//

+//===----------------------------------------------------------------------------==//

+//

+// This pass implements the following algorithm for creating a loop nest tree in

+// the context of Polly:

+// First, we creat a "Root" node to be the ultimate parent of all nodes

+// Then we scan pos by pos the scatterings of all the scopstmts. During the scanning:

+// If we encounter different (value) constant dimensions of the same pos,

+// we add new branches(same constants of the same pos only means one node);

+// If we encounter a new variable dimension, we add a new "FOR" node(child);

+// If within a variable dimension there is "zero" dimensions, add "SCOPSTMT" nodes,

+// for these dimensions; we separate scopstmts into different

+// groups according to the above mentioned different constants;

+void LoopNestTreeBase::print(raw_ostream &OS, unsigned indent) const {

+  OS.indent(indent);

+  switch (NodeType) {

+  case FOR:

+    OS << "for\n"; break;

+  case SCOPSTMT:

+    OS << "stmt\n"; break;

+  default:

+    OS << "unknown\n"; break;

+  };

+}

+

+void LoopNestTreeStmt::print(raw_ostream &OS, unsigned indent) const {

+  OS.indent(indent);

+  isl_map *scattering = stmt->getScattering();

+  const char *Name = isl_map_get_tuple_name(scattering, isl_dim_in);

+  OS << Name << "\n";

+  isl_map_free(scattering);

+}

+

+void LoopNestTreeFor::printTree(raw_ostream &OS, unsigned indent) const {

+  if (indent > 0)

+    this->print(OS, indent);

+  for (SmallVectorImpl<LoopNestTreeBase*>::const_iterator BI = Children.begin(),

+    BE = Children.end(); BI != BE; ++BI) {

+      if (isa<LoopNestTreeStmt>(*BI))

+        (*BI)->print(OS, indent+2);

+      else

+        cast<LoopNestTreeFor>(*BI)->printTree(OS, indent+2);

+  }

+}

+

+LoopNestTreeFor::~LoopNestTreeFor()  {

+  for (SmallVectorImpl<LoopNestTreeBase*>::iterator I = Children.begin(),

+    E = Children.end(); I != E; ++I) {

+      if (isa<LoopNestTreeStmt>(*I)) {

+        LoopNestTreeStmt *LNTS = cast<LoopNestTreeStmt>(*I);

+        delete LNTS;

+      } else {

+        LoopNestTreeFor *LNTF = cast<LoopNestTreeFor>(*I);

+        delete LNTF;

+      }

+  }

+  Children.clear();

+}

+

+static bool isVardim(const std::map<int, SmallVector<ScopStmt*, 8> > &Gs, unsigned pos) {

+  bool ret = false;

+  for (std::map<int, SmallVector<ScopStmt*, 8> >::const_iterator GSI = Gs.begin(),

+    GSE = Gs.end(); GSI != GSE; ++GSI) {

+    const SmallVector<ScopStmt*, 8> &G = GSI->second;

+    for (SmallVectorImpl<ScopStmt*>::const_iterator GI = G.begin(), GE = G.end();

+      GI != GE; ++GI) {

+        isl_map *scattering = (*GI)->getScattering();

+        isl_int con;

+        isl_int_init(con);

+        // Only when all dimensions are constants could this be false

+        if (!isl_map_plain_is_fixed(scattering, isl_dim_out, pos, &con))

+          ret |= true;

+        isl_int_clear(con);

+        isl_map_free(scattering);

+    }

+  }

+  if (ret)

+    DEBUG(dbgs() << "is Vardim.\n";);

+  return ret;

+}

+

+static int intFromislint(isl_int &con) {

+  mpz_t intMPZ;

+  mpz_init(intMPZ);

+  isl_int_get_gmp(con, intMPZ);

+  int intcon = mpz_get_si(intMPZ);

+  mpz_clear(intMPZ);

+  return intcon;

+}

+

+void LoopNestTree::LoopNestScan(const StmtGrps &Gs, unsigned pos, ParentGrp &Ps) {

+  DEBUG(dbgs() << "*****Pos*****:" << pos << "\n";);

+  DEBUG(dbgs() << (Gs.empty() ? "Gs Empty, return..." : "****Gs Size****:") <<  Gs.size() << "\n";);

+

+  bool hasVar = isVardim(Gs, pos);

+

+  for (std::map<int, SmallVector<ScopStmt*, 8> >::const_iterator GSI = Gs.begin(),

+                                         GSE = Gs.end(); GSI != GSE; ++GSI) {

+    int condim = GSI->first;

+    const SmallVector<ScopStmt*, 8> &G = GSI->second;

+    DEBUG(dbgs() << "condim =: " << condim << "\n";);

+    DEBUG(dbgs() << "G Size: " <<  G.size() << "\n";);

+    StmtGrps NewGs;

+    ParentGrp NewPs;

+    bool EnterVar = true;

+

+    for (SmallVectorImpl<ScopStmt*>::const_iterator GI = G.begin(), GE = G.end();

+                                                  GI != GE; ++GI) {

+      ScopStmt *stmt = *GI;

+      isl_map *scattering = stmt->getScattering();

+      bool Innermost = (G.size() == 1) && (Gs.size() == 1) &&

+        (pos == isl_map_dim(scattering, isl_dim_out) - 1);

+

+      if (Innermost) {

+        const char *Name = isl_map_get_tuple_name(scattering, isl_dim_in);

+        InnermostStmtSet.push_back(Name);

+        DEBUG(dbgs() << "Innermost: " << Name << "\n";);

+        if (hasVar) {

+          DEBUG(dbgs() << "a new variable\n";);

+          LoopNestTreeFor *LNTF = new LoopNestTreeFor();

+          LoopNestTreeFor *P = Ps[condim];

+          P->addChild(LNTF);

+          LNTF->setParent(P);

+          NewPs[condim] = LNTF;

+          LoopNestTreeStmt *LNTS = new LoopNestTreeStmt();

+          LNTS->setParent(LNTF);

+          LNTS->setScopStmt(stmt);

+          LNTF->addChild(LNTS);

+        } else {

+          DEBUG(dbgs() << "ScopStmt.\n";);

+          LoopNestTreeStmt *LNTS = new LoopNestTreeStmt();

+          LoopNestTreeFor *P = Ps[condim];

+          LNTS->setParent(P);

+          LNTS->setScopStmt(stmt);

+          P->addChild(LNTS);

+        }

+      } else {

+        // If we encounter different (value) constant dimensions of the same pos,

+        // we add new branches(same constants of the same pos only means one node);

+        isl_int con;

+        isl_int_init(con);

+        if (isl_map_plain_is_fixed(scattering, isl_dim_out, pos, &con)) {

+          DEBUG(dbgs() << "a new constant\n";);

+          int intcon = intFromislint(con);

+          EnterVar = true;

+          DEBUG(dbgs() << "intcon: " << intcon << "\n";);

+

+          // If within a variable dimension there is "zero" dimensions, add "SCOPSTMT" nodes

+          // those "SCOPSTMT" nodes without siblings(no matter "FOR" or "SCOPSTMT")

+          // are innermost.

+          if (hasVar) {

+            assert((intcon == 0) && "The constant dimension is not zero!");

+            DEBUG(dbgs() << "ScopStmt.\n";);

+            LoopNestTreeStmt *LNTS = new LoopNestTreeStmt();

+            LoopNestTreeFor *P = Ps[condim];

+            LNTS->setParent(P);

+            LNTS->setScopStmt(stmt);

+            P->addChild(LNTS);

+          } else {

+            NewGs[intcon].push_back(stmt);

+            NewPs[intcon] = Ps[condim];

+          }

+        } else {

+          NewGs[condim].push_back(stmt);

+          if (EnterVar) {

+            EnterVar = false;

+            // If we encounter a new variable dimension, we add a new "FOR" node(child);

+            DEBUG(dbgs() << "a new variable\n";);

+            LoopNestTreeFor *LNTF = new LoopNestTreeFor();

+            LoopNestTreeFor *P = Ps[condim];

+            P->addChild(LNTF);

+            LNTF->setParent(P);

+            NewPs[condim] = LNTF;

+          }

+        }

+        isl_int_clear(con);

+      }

+      isl_map_free(scattering);

+    }

+    LoopNestScan(NewGs, pos+1, NewPs);

+  }

+}

+

+void LoopNestTree::releaseMemory() {

+  InnermostStmtSet.clear();

+  if (Root) {

+    delete Root;

+    Root = 0;

+  }

+}

+

+void LoopNestTree::dump() const {

+  printScop(dbgs());

+}

+

+void LoopNestTree::printScop(raw_ostream &OS) const {

+  OS << "Loop Nest Tree:\n";

+  OS << "-----------------------------\n";

+

+  /// DFS the LNT, print it out according to the nodetype

+  Root->printTree(OS, 0);

+

+  OS << "-----------------------------\n";

+  OS << "End of Loop Nest Tree.\n\n";

+

+  OS << "Innermost Loop(s):\n";

+  OS << "*****************************\n";

+  for (SmallVector<const char*, 8>::const_iterator I = InnermostStmtSet.begin(),

+                   E = InnermostStmtSet.end(); I != E; ++I) {

+     OS << *I << "\n";

+  }

+  OS << "*****************************\n";

+  OS << "End of Innermost Loop(s).\n";

+}

+

+void LoopNestTree::getInnermostStmts(std::set<const char*> &InnermostStmtNames) const {

+  for (SmallVectorImpl<const char*>::const_iterator I = InnermostStmtSet.begin(),

+    E = InnermostStmtSet.end(); I != E; ++I) {

+      InnermostStmtNames.insert(*I);

+  }

+}

+

+bool LoopNestTree::runOnScop(Scop &S) {

+  StmtGrps Gs;

+

+  ParentGrp Ps;

+  Root = new LoopNestTreeFor();

+

+  // First, we creat a "Root" node to be the ultimate parent of all nodes

+  Ps[0] = Root;

+

+  // we let all the scopstmts belongs to one group(StmtGrp).

+  for (Scop::const_iterator SI = S.begin(), SE = S.end(); SI != SE; ++SI) {

+    Gs[0].push_back(*SI);

+  }

From 6d7fc089322aa33025d51130f74b0411354e11b9 Mon Sep 17 00:00:00 2001

From: TangKK <dengjunq...@hotmail.com>

Date: Wed, 18 Jul 2012 16:38:02 +0800

Subject: [PATCH 2/7] Add testcases to test polly-loopnesttree pass

---

 test/LoopNestTree/matmul.c                         |   52 +++

 test/LoopNestTree/matmul.ll                        |  207 ++++++++++++

 test/LoopNestTree/sim2mm.c                         |   50 +++

 test/LoopNestTree/sim2mm.ll                        |  333 ++++++++++++++++++++

 test/LoopNestTree/simatax.c                        |   36 +++

 test/LoopNestTree/simatax.ll                       |  184 +++++++++++

 test/LoopNestTree/simple_loop.c                    |   20 ++

 test/LoopNestTree/simple_loop.ll                   |   67 ++++

 .../kernels/2mm/2mm_without_param.ll               |   29 ++-

 9 files changed, 976 insertions(+), 2 deletions(-)

 create mode 100755 test/LoopNestTree/matmul.c

 create mode 100755 test/LoopNestTree/matmul.ll

 create mode 100755 test/LoopNestTree/sim2mm.c

 create mode 100644 test/LoopNestTree/sim2mm.ll

 create mode 100755 test/LoopNestTree/simatax.c

 create mode 100755 test/LoopNestTree/simatax.ll

 create mode 100755 test/LoopNestTree/simple_loop.c

 create mode 100644 test/LoopNestTree/simple_loop.ll

diff --git a/test/LoopNestTree/matmul.c b/test/LoopNestTree/matmul.c

new file mode 100755

+    fprintf(stdout, "\n");

+  }

+}

+

+int main()

+{

+  int i, j, k;

+  double t_start, t_end;

+  init_array();

+

+  for(i=0; i<N; i++) {

+    for(j=0; j<N; j++) {

+      C[i][j] = 0;

+      for(k=0; k<N; k++)

+    C[i][j] = C[i][j] + A[i][k] * B[k][j];

+    }

+  }

+

+#ifdef TEST

+  print_array();

+#endif

+  return 0;

+}

diff --git a/test/LoopNestTree/matmul.ll b/test/LoopNestTree/matmul.ll

new file mode 100755

diff --git a/test/LoopNestTree/sim2mm.c b/test/LoopNestTree/sim2mm.c

new file mode 100755

index 0000000..b4243f9

--- /dev/null

+++ b/test/LoopNestTree/sim2mm.c

@@ -0,0 +1,50 @@

+#define ni 1024

+#define nj 1024

+#define nk 1024

+#define nl 1024

+#define alpha 32412

+#define beta 2123

+

+#define DATA_TYPE double

+

+double A[1024][1024], B[1024][1024], C[1024][1024], D[1024][1024], tmp[1024][1024];

+

+void init_array() {

+  int i, j;

+  for (i = 0; i < ni; i++)

+    for (j = 0; j < nk; j++)

+      A[i][j] = ((DATA_TYPE) i*j) / ni;

+  for (i = 0; i < nk; i++)

+    for (j = 0; j < nj; j++)

+      B[i][j] = ((DATA_TYPE) i*(j+1)) / nj;

+  for (i = 0; i < nl; i++)

+    for (j = 0; j < nj; j++)

+      C[i][j] = ((DATA_TYPE) i*(j+3)) / nl;

+  for (i = 0; i < ni; i++)

+    for (j = 0; j < nl; j++)

+      D[i][j] = ((DATA_TYPE) i*(j+2)) / nk;

+}

+

+int main() {

+  init_array();

+  int i, j, k;

+

+  /* D := alpha*A*B*C + beta*D */

+  for (i = 0; i < ni; i++) {

+    for (j = 0; j < nj; j++) {

+  tmp[i][j] = 0;

+  for (k = 0; k < nk; ++k)

+    tmp[i][j] += alpha * A[i][k] * B[k][j];

+    }

+  }

+  for (i = 0; i < ni; i++) {

+    for (j = 0; j < nl; j++) {

+  D[i][j] *= beta;

+  for (k = 0; k < nj; ++k)

+    D[i][j] += tmp[i][k] * C[k][j];

+    }

+  }

+  

+  return 0;

+  

+}

diff --git a/test/LoopNestTree/sim2mm.ll b/test/LoopNestTree/sim2mm.ll

new file mode 100644

index 0000000..f80bf3d

--- /dev/null

+++ b/test/LoopNestTree/sim2mm.ll

@@ -0,0 +1,333 @@

+; RUN: opt %loadPolly %defaultOpts -polly-opt-isl -polly-loopnesttree -analyze %s | FileCheck %s

+; ModuleID = 'sim2mm.s'

+target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"

+target triple = "i386-pc-linux-gnu"

+

+@A = common global [1024 x [1024 x double]] zeroinitializer, align 4

+@B = common global [1024 x [1024 x double]] zeroinitializer, align 4

+@C = common global [1024 x [1024 x double]] zeroinitializer, align 4

+@D = common global [1024 x [1024 x double]] zeroinitializer, align 4

+@tmp = common global [1024 x [1024 x double]] zeroinitializer, align 4

+

+define void @init_array() nounwind {

+entry:

+  br label %for.cond

+

+for.cond:                                         ; preds = %for.inc6, %entry

+  %i.0 = phi i32 [ 0, %entry ], [ %inc7, %for.inc6 ]

+  %exitcond7 = icmp ne i32 %i.0, 1024

+  br i1 %exitcond7, label %for.body, label %for.end8

+

+for.body:                                         ; preds = %for.cond

+  br label %for.cond1

+

+for.cond1:                                        ; preds = %for.inc, %for.body

+  %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]

+  %exitcond6 = icmp ne i32 %j.0, 1024

+  br i1 %exitcond6, label %for.body3, label %for.end

+

+for.body3:                                        ; preds = %for.cond1

+  %conv = sitofp i32 %i.0 to double

+  %conv4 = sitofp i32 %j.0 to double

+  %mul = fmul double %conv, %conv4

+  %div = fdiv double %mul, 1.024000e+03

+  %arrayidx = getelementptr inbounds [1024 x [1024 x double]]* @A, i32 0, i32 %i.0

+  %arrayidx5 = getelementptr inbounds [1024 x double]* %arrayidx, i32 0, i32 %j.0

+  store double %div, double* %arrayidx5, align 4

+  br label %for.inc

+

+for.inc:                                          ; preds = %for.body3

+  %inc = add nsw i32 %j.0, 1

+  br label %for.cond1

+

+for.end:                                          ; preds = %for.cond1

+  br label %for.inc6

+

+for.inc6:                                         ; preds = %for.end

+  %inc7 = add nsw i32 %i.0, 1

+  br label %for.cond

+

+for.end8:                                         ; preds = %for.cond

+  br label %for.cond9

+

+for.cond9:                                        ; preds = %for.inc26, %for.end8

+  %i.1 = phi i32 [ 0, %for.end8 ], [ %inc27, %for.inc26 ]

+  %exitcond5 = icmp ne i32 %i.1, 1024

+  br i1 %exitcond5, label %for.body12, label %for.end28

+

+for.body12:                                       ; preds = %for.cond9

+  br label %for.cond13

+

+for.cond13:                                       ; preds = %for.inc23, %for.body12

+  %j.1 = phi i32 [ 0, %for.body12 ], [ %inc24, %for.inc23 ]

+  %exitcond4 = icmp ne i32 %j.1, 1024

+  br i1 %exitcond4, label %for.body16, label %for.end25

+

+for.body16:                                       ; preds = %for.cond13

+  %conv17 = sitofp i32 %i.1 to double

+  %add = add nsw i32 %j.1, 1

+  %conv18 = sitofp i32 %add to double

+  %mul19 = fmul double %conv17, %conv18

+  %div20 = fdiv double %mul19, 1.024000e+03

+  %arrayidx21 = getelementptr inbounds [1024 x [1024 x double]]* @B, i32 0, i32 %i.1

+  %arrayidx22 = getelementptr inbounds [1024 x double]* %arrayidx21, i32 0, i32 %j.1

+  store double %div20, double* %arrayidx22, align 4

+  br label %for.inc23

+

+for.inc23:                                        ; preds = %for.body16

+  %inc24 = add nsw i32 %j.1, 1

+  br label %for.cond13

+

+for.end25:                                        ; preds = %for.cond13

+  br label %for.inc26

+

+for.inc26:                                        ; preds = %for.end25

+  %inc27 = add nsw i32 %i.1, 1

+  br label %for.cond9

+

+for.end28:                                        ; preds = %for.cond9

+  br label %for.cond29

+

+for.cond29:                                       ; preds = %for.inc47, %for.end28

+  %i.2 = phi i32 [ 0, %for.end28 ], [ %inc48, %for.inc47 ]

+  %exitcond3 = icmp ne i32 %i.2, 1024

+  br i1 %exitcond3, label %for.body32, label %for.end49

+

+for.body32:                                       ; preds = %for.cond29

+  br label %for.cond33

+

+for.cond33:                                       ; preds = %for.inc44, %for.body32

+  %j.2 = phi i32 [ 0, %for.body32 ], [ %inc45, %for.inc44 ]

+  %exitcond2 = icmp ne i32 %j.2, 1024

+  br i1 %exitcond2, label %for.body36, label %for.end46

+

+for.body36:                                       ; preds = %for.cond33

+  %conv37 = sitofp i32 %i.2 to double

+  %add38 = add nsw i32 %j.2, 3

+  %conv39 = sitofp i32 %add38 to double

+  %mul40 = fmul double %conv37, %conv39

+  %div41 = fdiv double %mul40, 1.024000e+03

+  %arrayidx42 = getelementptr inbounds [1024 x [1024 x double]]* @C, i32 0, i32 %i.2

+  %arrayidx43 = getelementptr inbounds [1024 x double]* %arrayidx42, i32 0, i32 %j.2

+  store double %div41, double* %arrayidx43, align 4

+  br label %for.inc44

+

+for.inc44:                                        ; preds = %for.body36

+  %inc45 = add nsw i32 %j.2, 1

+  br label %for.cond33

+

+for.end46:                                        ; preds = %for.cond33

+  br label %for.inc47

+

+for.inc47:                                        ; preds = %for.end46

+  %inc48 = add nsw i32 %i.2, 1

+  br label %for.cond29

+

+for.end49:                                        ; preds = %for.cond29

+  br label %for.cond50

+

+for.cond50:                                       ; preds = %for.inc68, %for.end49

+  %i.3 = phi i32 [ 0, %for.end49 ], [ %inc69, %for.inc68 ]

+  %exitcond1 = icmp ne i32 %i.3, 1024

+  br i1 %exitcond1, label %for.body53, label %for.end70

+

+for.body53:                                       ; preds = %for.cond50

+  br label %for.cond54

+

+for.cond54:                                       ; preds = %for.inc65, %for.body53

+  %j.3 = phi i32 [ 0, %for.body53 ], [ %inc66, %for.inc65 ]

+  %exitcond = icmp ne i32 %j.3, 1024

+  br i1 %exitcond, label %for.body57, label %for.end67

+

+for.body57:                                       ; preds = %for.cond54

+  %conv58 = sitofp i32 %i.3 to double

+  %add59 = add nsw i32 %j.3, 2

+  %conv60 = sitofp i32 %add59 to double

+  %mul61 = fmul double %conv58, %conv60

+  %div62 = fdiv double %mul61, 1.024000e+03

+  %arrayidx63 = getelementptr inbounds [1024 x [1024 x double]]* @D, i32 0, i32 %i.3

+  %arrayidx64 = getelementptr inbounds [1024 x double]* %arrayidx63, i32 0, i32 %j.3

+  store double %div62, double* %arrayidx64, align 4

+  br label %for.inc65

+

+for.inc65:                                        ; preds = %for.body57

+  %inc66 = add nsw i32 %j.3, 1

+  br label %for.cond54

+

+for.end67:                                        ; preds = %for.cond54

+  br label %for.inc68

+

+for.inc68:                                        ; preds = %for.end67

+  %inc69 = add nsw i32 %i.3, 1

+  br label %for.cond50

+

+for.end70:                                        ; preds = %for.cond50

+  ret void

+}

+

+define i32 @main() nounwind {

+entry:

+  call void @init_array()

+  br label %for.cond

+

+for.cond:                                         ; preds = %for.inc18, %entry

+  %i.0 = phi i32 [ 0, %entry ], [ %inc19, %for.inc18 ]

+  %exitcond5 = icmp ne i32 %i.0, 1024

+  br i1 %exitcond5, label %for.body, label %for.end20

+

+for.body:                                         ; preds = %for.cond

+  br label %for.cond1

+

+for.cond1:                                        ; preds = %for.inc15, %for.body

+  %j.0 = phi i32 [ 0, %for.body ], [ %inc16, %for.inc15 ]

+  %exitcond4 = icmp ne i32 %j.0, 1024

+  br i1 %exitcond4, label %for.body3, label %for.end17

+

+for.body3:                                        ; preds = %for.cond1

+  %arrayidx = getelementptr inbounds [1024 x [1024 x double]]* @tmp, i32 0, i32 %i.0

+  %arrayidx4 = getelementptr inbounds [1024 x double]* %arrayidx, i32 0, i32 %j.0

+  store double 0.000000e+00, double* %arrayidx4, align 4

+  br label %for.cond5

+

+for.cond5:                                        ; preds = %for.inc, %for.body3

+  %k.0 = phi i32 [ 0, %for.body3 ], [ %inc, %for.inc ]

+  %exitcond3 = icmp ne i32 %k.0, 1024

+  br i1 %exitcond3, label %for.body7, label %for.end

+

+for.body7:                                        ; preds = %for.cond5

+  %arrayidx8 = getelementptr inbounds [1024 x [1024 x double]]* @A, i32 0, i32 %i.0

+  %arrayidx9 = getelementptr inbounds [1024 x double]* %arrayidx8, i32 0, i32 %k.0

+  %0 = load double* %arrayidx9, align 4

+  %mul = fmul double 3.241200e+04, %0

+  %arrayidx10 = getelementptr inbounds [1024 x [1024 x double]]* @B, i32 0, i32 %k.0

+  %arrayidx11 = getelementptr inbounds [1024 x double]* %arrayidx10, i32 0, i32 %j.0

+  %1 = load double* %arrayidx11, align 4

+  %mul12 = fmul double %mul, %1

+  %arrayidx13 = getelementptr inbounds [1024 x [1024 x double]]* @tmp, i32 0, i32 %i.0

+  %arrayidx14 = getelementptr inbounds [1024 x double]* %arrayidx13, i32 0, i32 %j.0

+  %2 = load double* %arrayidx14, align 4

+  %add = fadd double %2, %mul12

+  store double %add, double* %arrayidx14, align 4

+  br label %for.inc

+

+for.inc:                                          ; preds = %for.body7

+  %inc = add nsw i32 %k.0, 1

+  br label %for.cond5

+

+for.end:                                          ; preds = %for.cond5

+  br label %for.inc15

+

+for.inc15:                                        ; preds = %for.end

+  %inc16 = add nsw i32 %j.0, 1

+  br label %for.cond1

+

+for.end17:                                        ; preds = %for.cond1

+  br label %for.inc18

+

+for.inc18:                                        ; preds = %for.end17

+  %inc19 = add nsw i32 %i.0, 1

+  br label %for.cond

+

+for.end20:                                        ; preds = %for.cond

+  br label %for.cond21

+

+for.cond21:                                       ; preds = %for.inc47, %for.end20

+  %i.1 = phi i32 [ 0, %for.end20 ], [ %inc48, %for.inc47 ]

+  %exitcond2 = icmp ne i32 %i.1, 1024

+  br i1 %exitcond2, label %for.body23, label %for.end49

+

+for.body23:                                       ; preds = %for.cond21

+  br label %for.cond24

+

+for.cond24:                                       ; preds = %for.inc44, %for.body23

+  %j.1 = phi i32 [ 0, %for.body23 ], [ %inc45, %for.inc44 ]

+  %exitcond1 = icmp ne i32 %j.1, 1024

+  br i1 %exitcond1, label %for.body26, label %for.end46

+

+for.body26:                                       ; preds = %for.cond24

+  %arrayidx27 = getelementptr inbounds [1024 x [1024 x double]]* @D, i32 0, i32 %i.1

+  %arrayidx28 = getelementptr inbounds [1024 x double]* %arrayidx27, i32 0, i32 %j.1

+  %3 = load double* %arrayidx28, align 4

+  %mul29 = fmul double %3, 2.123000e+03

+  store double %mul29, double* %arrayidx28, align 4

+  br label %for.cond30

+

+for.cond30:                                       ; preds = %for.inc41, %for.body26

+  %k.1 = phi i32 [ 0, %for.body26 ], [ %inc42, %for.inc41 ]

+  %exitcond = icmp ne i32 %k.1, 1024

+  br i1 %exitcond, label %for.body32, label %for.end43

+

+for.body32:                                       ; preds = %for.cond30

+  %arrayidx33 = getelementptr inbounds [1024 x [1024 x double]]* @tmp, i32 0, i32 %i.1

+  %arrayidx34 = getelementptr inbounds [1024 x double]* %arrayidx33, i32 0, i32 %k.1

+  %4 = load double* %arrayidx34, align 4

+  %arrayidx35 = getelementptr inbounds [1024 x [1024 x double]]* @C, i32 0, i32 %k.1

+  %arrayidx36 = getelementptr inbounds [1024 x double]* %arrayidx35, i32 0, i32 %j.1

+  %5 = load double* %arrayidx36, align 4

+  %mul37 = fmul double %4, %5

+  %arrayidx38 = getelementptr inbounds [1024 x [1024 x double]]* @D, i32 0, i32 %i.1

+  %arrayidx39 = getelementptr inbounds [1024 x double]* %arrayidx38, i32 0, i32 %j.1

+  %6 = load double* %arrayidx39, align 4

+  %add40 = fadd double %6, %mul37

+  store double %add40, double* %arrayidx39, align 4

+  br label %for.inc41

+

+for.inc41:                                        ; preds = %for.body32

+  %inc42 = add nsw i32 %k.1, 1

+  br label %for.cond30

+

+for.end43:                                        ; preds = %for.cond30

+  br label %for.inc44

+

+for.inc44:                                        ; preds = %for.end43

+  %inc45 = add nsw i32 %j.1, 1

+  br label %for.cond24

+

+for.end46:                                        ; preds = %for.cond24

+  br label %for.inc47

+

+for.inc47:                                        ; preds = %for.end46

+  %inc48 = add nsw i32 %i.1, 1

+  br label %for.cond21

+

+for.end49:                                        ; preds = %for.cond21

+  ret i32 0

+}

+

+;CHECK: Printing analysis 'Polly - Analysis the Loop Nest Tree' for region: 'for.cond => for.end49' in function 'main':

+;CHECK: Loop Nest Tree:

+;CHECK: -----------------------------

+;CHECK:   for

+;CHECK:     for

+;CHECK:       for

+;CHECK:         for

+;CHECK:           Stmt_for_body3

+;CHECK:   for

+;CHECK:     for

+;CHECK:       for

+;CHECK:         for

+;CHECK:           for

+;CHECK:             for

+;CHECK:               Stmt_for_body7

+;CHECK:   for

+;CHECK:     for

+;CHECK:       for

+;CHECK:         for

+;CHECK:           Stmt_for_body26

+;CHECK:   for

+;CHECK:     for

+;CHECK:       for

+;CHECK:         for

+;CHECK:           for

+;CHECK:             for

+;CHECK:               Stmt_for_body32

+;CHECK: -----------------------------

+;CHECK: End of Loop Nest Tree.

+;CHECK: Innermost Loop(s):

+;CHECK: *****************************

+;CHECK: Stmt_for_body3

+;CHECK: Stmt_for_body7

+;CHECK: Stmt_for_body26

+;CHECK: Stmt_for_body32

+;CHECK: *****************************

+;CHECK: End of Innermost Loop(s).

diff --git a/test/LoopNestTree/simatax.c b/test/LoopNestTree/simatax.c

new file mode 100755

new file mode 100755

new file mode 100755

+; LNT: End of Innermost Loop(s).

-- 

1.7.5.1

[ether]

锟斤拷 2012/8/13 15:07, Jun-qi Deng 写锟斤拷:

This example looks good to me.

We can add a "const" modifier ahead of NodeType because chaning the type of a Node is not allowed:
const enum LoopNestNodeType NodeType;

+

+  protected:

+    LoopNestTreeBase(enum LoopNestNodeType Type) : Parent(0), NodeType(Type) {}

Please add the keywork "explicit" to avoid LoopNestTreeBase being implicitly converted from LoopNestNodeType:
explicit  LoopNestTreeBase(enum LoopNestNodeType Type) : Parent(0), NodeType(Type) {}

Besides, we can also initialize the Parent in the constructor:

explicit  LoopNestTreeBase(enum LoopNestNodeType Type, LoopNestTreeBase *Parent) : Parent(Parent), NodeType(Type) {}

And please also add a virtual destructor:
~LoopNestTreeBase() {}

+

+  public: 

+    enum LoopNestNodeType getNodeType() const { return NodeType; }

+

+    virtual void print(raw_ostream &OS, unsigned indent) const;

We can leave this function as a pure virtual function, and require the subclasses to implement it:
virtual void print(raw_ostream &OS, unsigned indent) const = 0;

I don't think this is a good idea, instead, we can simply return the reference:
SmallVectorImpl<LoopNestTreeBase*> &getChildren() {
  return Children;
}

const SmallVectorImpl<LoopNestTreeBase*> &getChildren() const {
  return Children;

}

+    }

+    

+    // DFS the LoopNestTree and print out all the nodes

+    void printTree(raw_ostream &OS, unsigned indent) const;

No need to add a new function, we can just override the virtual function "print" of LoopNestTreeBase.

+

+    /// Methods for support type inquiry through isa, cast, and dyn_cast:

+    static inline bool classof(const LoopNestTreeFor *N) { return true; }

+    static inline bool classof(const LoopNestTreeBase *N) {

+      return N->getNodeType() == FOR;

+    }

+  };

+

+  //===---------------------------------------------------------------------===//

+  /// @brief A derived class standing for the scopstmt node of the tree

+  ///

+  class LoopNestTreeStmt : public LoopNestTreeBase {

+    ScopStmt  *stmt;

+

+    void setScopStmt(ScopStmt *S) { stmt = S; }

+

+    friend class LoopNestTree;

+

+  public:

+    LoopNestTreeStmt() : LoopNestTreeBase(SCOPSTMT) {}

We can also initialize the Stmt while constructing the LoopNestTreeStmt:
explicit LoopNestTreeStmt(ScopStmt *S) : LoopNestTreeBase(SCOPSTMT), Stmt(S) {}

We should assert we will never reach here, otherwise something went wrong.

+  };

+}

+

+void LoopNestTreeStmt::print(raw_ostream &OS, unsigned indent) const {

+  OS.indent(indent);

+  isl_map *scattering = stmt->getScattering();

+  const char *Name = isl_map_get_tuple_name(scattering, isl_dim_in);

+  OS << Name << "\n";

+  isl_map_free(scattering);

Can we get the name of the Stmt without creating the Scarttering?

+}

+

+void LoopNestTreeFor::printTree(raw_ostream &OS, unsigned indent) const {

+  if (indent > 0)

+    this->print(OS, indent);

+  for (SmallVectorImpl<LoopNestTreeBase*>::const_iterator BI = Children.begin(),

+    BE = Children.end(); BI != BE; ++BI) {

As stated above, if the function 'print' is virtual, the cast is not needed.

+      if (isa<LoopNestTreeStmt>(*BI))

+        (*BI)->print(OS, indent+2);

+      else

+        cast<LoopNestTreeFor>(*BI)->printTree(OS, indent+2);

+  }

+}

+

+LoopNestTreeFor::~LoopNestTreeFor()  {

+  for (SmallVectorImpl<LoopNestTreeBase*>::iterator I = Children.begin(),

+    E = Children.end(); I != E; ++I) {

If we have a virtual destructor, the cast can also be avoided, and please have a look at the function 'DeleteContainerPointers' in STLExtras.h

+      if (isa<LoopNestTreeStmt>(*I)) {

+        LoopNestTreeStmt *LNTS = cast<LoopNestTreeStmt>(*I);

+        delete LNTS;

+      } else {

+        LoopNestTreeFor *LNTF = cast<LoopNestTreeFor>(*I);

+        delete LNTF;

+      }

+  }

+  Children.clear();

+}

+

+static bool isVardim(const std::map<int, SmallVector<ScopStmt*, 8> > &Gs, unsigned pos) {

+  bool ret = false;

+  for (std::map<int, SmallVector<ScopStmt*, 8> >::const_iterator GSI = Gs.begin(),

Please use StmtGrps instead of std::map<int, SmallVector<ScopStmt*, 8> >.

+    GSE = Gs.end(); GSI != GSE; ++GSI) {

+    const SmallVector<ScopStmt*, 8> &G = GSI->second;

+    for (SmallVectorImpl<ScopStmt*>::const_iterator GI = G.begin(), GE = G.end();

+      GI != GE; ++GI) {

+        isl_map *scattering = (*GI)->getScattering();

+        isl_int con;

+        isl_int_init(con);

+        // Only when all dimensions are constants could this be false

+        if (!isl_map_plain_is_fixed(scattering, isl_dim_out, pos, &con))

+          ret |= true;

+        isl_int_clear(con);

+        isl_map_free(scattering);

+    }

+  }

+  if (ret)

+    DEBUG(dbgs() << "is Vardim.\n";);

It is better if we can embedded the "if (ret)" into the DEBUG marco:
DEBUG(if (ret) dbgs() << "is Vardim.\n";);

+  return ret;

+}

+

+static int intFromislint(isl_int &con) {

+  mpz_t intMPZ;

+  mpz_init(intMPZ);

+  isl_int_get_gmp(con, intMPZ);

+  int intcon = mpz_get_si(intMPZ);

+  mpz_clear(intMPZ);

+  return intcon;

+}

+

+void LoopNestTree::LoopNestScan(const StmtGrps &Gs, unsigned pos, ParentGrp &Ps) {

+  DEBUG(dbgs() << "*****Pos*****:" << pos << "\n";);

+  DEBUG(dbgs() << (Gs.empty() ? "Gs Empty, return..." : "****Gs Size****:") <<  Gs.size() << "\n";);

+

+  bool hasVar = isVardim(Gs, pos);

+

+  for (std::map<int, SmallVector<ScopStmt*, 8> >::const_iterator GSI = Gs.begin(),

+                                         GSE = Gs.end(); GSI != GSE; ++GSI) {

Please use StmtGrps instead of std::map<int, SmallVector<ScopStmt*, 8> >

+    int condim = GSI->first;

+    const SmallVector<ScopStmt*, 8> &G = GSI->second;

Please use StmtGrp instead of SmallVector<ScopStmt*, 8>

+    DEBUG(dbgs() << "condim =: " << condim << "\n";);

+    DEBUG(dbgs() << "G Size: " <<  G.size() << "\n";);

+    StmtGrps NewGs;

+    ParentGrp NewPs;

+    bool EnterVar = true;

+

+    for (SmallVectorImpl<ScopStmt*>::const_iterator GI = G.begin(), GE = G.end();

+                                                  GI != GE; ++GI) {

Please use StmtGrp instead of SmallVectorImpl<ScopStmt*>

We can reduce the hierarchy of the if-else blocks by extracting the code for different condition to standalone functions.

Since this is only 1 statement, the { } are not needed.

Can we merge the cases above into the existing testcase in PolyBench?

[Jun-qi Deng]

Hi ether! Here is the fixed patch according to your comments. Not all of the testcases can be merged into Polybench, while most of them can. I'll upload a patch for the testcase when I'm done.

regards,

tangkk

[Jun-qi Deng]

Hi ether, here is the fixed two patches according to your comments. Not all of the testcases can be merged into Polybench, while most of them can.

From e93df5f615aac72c2ac62bde320a457cb26aa4e3 Mon Sep 17 00:00:00 2001

From: TangKK <dengjunq...@hotmail.com>

Date: Wed, 18 Jul 2012 16:37:26 +0800

Subject: [PATCH 1/7] Add LoopNestTree Analysis Pass - Analysis the Loop Nest

 Tree

Signed-off-by: TangKK <dengjunq...@hotmail.com>

---

 include/polly/LinkAllPasses.h         |    2 +

 include/polly/LoopNestTreeAnalysis.h  |  175 +++++++++++++++++++++++

 lib/Analysis/CMakeLists.txt           |    1 +

 lib/Analysis/LoopNestTreeAnalysis.cpp |  252 +++++++++++++++++++++++++++++++++

 lib/RegisterPasses.cpp                |    2 +

 test/CMakeLists.txt                   |    1 +

 6 files changed, 433 insertions(+), 0 deletions(-)

 create mode 100755 include/polly/LoopNestTreeAnalysis.h

 create mode 100755 lib/Analysis/LoopNestTreeAnalysis.cpp

diff --git a/include/polly/LinkAllPasses.h b/include/polly/LinkAllPasses.h

index ed2442b..38748a6 100644

--- a/include/polly/LinkAllPasses.h

+++ b/include/polly/LinkAllPasses.h

@@ -43,6 +43,7 @@ namespace polly {

   Pass *createDOTViewerPass();

   Pass *createIndependentBlocksPass();

   Pass *createIndVarSimplifyPass();

+  Pass *createLoopNestTreePass();

   Pass *createJSONExporterPass();

   Pass *createJSONImporterPass();

   Pass *createPipforPass();

@@ -94,6 +95,7 @@ namespace {

        createDOTViewerPass();

        createIndependentBlocksPass();

        createIndVarSimplifyPass();

+       createLoopNestTreePass();

        createJSONExporterPass();

        createJSONImporterPass();

        createPipforPass();

diff --git a/include/polly/LoopNestTreeAnalysis.h b/include/polly/LoopNestTreeAnalysis.h

new file mode 100755

index 0000000..4a57355

--- /dev/null

+++ b/include/polly/LoopNestTreeAnalysis.h

@@ -0,0 +1,175 @@

+  public:

+    enum LoopNestNodeType {

+      // The Node may be of only two types: "for" statement and "scopstmt"

+      FOR,

+      SCOPSTMT

+    };

+

+  private:    

+    LoopNestTreeBase *Parent;

+    const enum LoopNestNodeType NodeType;

+

+  protected:

+    explicit LoopNestTreeBase(LoopNestTreeBase *Parent, enum LoopNestNodeType Type) :

+      Parent(Parent), NodeType(Type) {}

+

+  public: 

+    inline enum LoopNestNodeType getNodeType() const { return NodeType; }

+

+    virtual void print(raw_ostream &OS, unsigned indent) const = 0;

+

+    LoopNestTreeBase *getParent() const { return Parent; }

+

+    virtual ~LoopNestTreeBase() {}

+

+    friend class LoopNestTree;

+  };

+

+  //===---------------------------------------------------------------------===//

+  /// @brief A derived class standing for the "for" statement node of the tree

+  ///

+  class LoopNestTreeFor : public LoopNestTreeBase {

+    SmallVector<LoopNestTreeBase*, 8> Children;

+

+    inline void addChild(LoopNestTreeBase *Child) { Children.push_back(Child); }

+

+    friend class LoopNestTree;

+  public:

+    explicit LoopNestTreeFor(LoopNestTreeBase *Parent) : LoopNestTreeBase(Parent, FOR) {}

+

+    ~LoopNestTreeFor();

+

+    // @brief fill the Container with "Children"

+    inline const SmallVectorImpl<LoopNestTreeBase*> &getChildren() const {

+      return Children;

+    }

+    

+    // DFS the LoopNestTree and print out all the nodes

+    void print(raw_ostream &OS, unsigned indent) const;

+

+    /// Methods for support type inquiry through isa, cast, and dyn_cast:

+    static inline bool classof(const LoopNestTreeFor *N) { return true; }

+    static inline bool classof(const LoopNestTreeBase *N) {

+      return N->getNodeType() == FOR;

+    }

+  };

+

+  //===---------------------------------------------------------------------===//

+  /// @brief A derived class standing for the scopstmt node of the tree

+  ///

+  class LoopNestTreeStmt : public LoopNestTreeBase {

+    ScopStmt  *stmt;

+

+    inline void setScopStmt(ScopStmt *S) { stmt = S; }

+

+    friend class LoopNestTree;

+

+  public:

+    explicit LoopNestTreeStmt(LoopNestTreeBase *Parent) : LoopNestTreeBase(Parent, SCOPSTMT) {}

+

+    inline ScopStmt *getScopStmt() const { return stmt; }

+    // @brief This function decides whether a given pos has at least a variable dimension

+    // @param Gs is the input scopstmt group(s)

+    // @param pos is the scattering position

+    bool isVardim(const StmtGrps &Gs, unsigned pos);

+

index 0000000..ba8df5b

--- /dev/null

+++ b/lib/Analysis/LoopNestTreeAnalysis.cpp

@@ -0,0 +1,252 @@

+#include "llvm/ADT/STLExtras.h"

+

+#include "isl/map.h"

+#include "isl/set.h"

+

+#include <set>

+#include <gmp.h>

+

+using namespace llvm;

+using namespace polly;

+

+void LoopNestTreeStmt::print(raw_ostream &OS, unsigned indent) const {

+  OS.indent(indent);

+  OS << stmt->getBaseName() << "\n";

+}

+

+void LoopNestTreeFor::print(raw_ostream &OS, unsigned indent) const {

+  if (indent > 0) {

+    OS.indent(indent);

+    OS << "for\n";

+  }

+  for (SmallVectorImpl<LoopNestTreeBase*>::const_iterator BI = Children.begin(),

+    BE = Children.end(); BI != BE; ++BI) {

+      (*BI)->print(OS, indent + 2);

+  }

+}

+

+LoopNestTreeFor::~LoopNestTreeFor()  {

+  DeleteContainerPointers(Children);

+}

+

+bool LoopNestTree::isVardim(const StmtGrps &Gs, unsigned pos) {

+  bool ret = false;

+  for (StmtGrps::const_iterator GSI = Gs.begin(), GSE = Gs.end(); GSI != GSE; ++GSI) {

+    const StmtGrp &G = GSI->second;

+    for (StmtGrp::const_iterator GI = G.begin(), GE = G.end(); GI != GE; ++GI) {

+      isl_map *scattering = (*GI)->getScattering();

+      isl_int con;

+      isl_int_init(con);

+      // Only when all dimensions are constants could this be false

+      if (!isl_map_plain_is_fixed(scattering, isl_dim_out, pos, &con))

+        ret |= true;

+      isl_int_clear(con);

+      isl_map_free(scattering);

+    }

+  }

+  DEBUG(if (ret) dbgs() << "is Vardim.\n";);

+  return ret;

+}

+

+static int intFromislint(isl_int &con) {

+  mpz_t intMPZ;

+  mpz_init(intMPZ);

+  isl_int_get_gmp(con, intMPZ);

+  int intcon = mpz_get_si(intMPZ);

+  mpz_clear(intMPZ);

+  return intcon;

+}

+

+void LoopNestTree::LoopNestScan(const StmtGrps &Gs, unsigned pos, ParentGrp &Ps) {

+  DEBUG(dbgs() << "*****Pos*****:" << pos << "\n";);

+  DEBUG(dbgs() << (Gs.empty() ? "Gs Empty, return..." : "****Gs Size****:") <<  Gs.size() << "\n";);

+

+  bool hasVar = isVardim(Gs, pos);

+

+  for (StmtGrps::const_iterator GSI = Gs.begin(), GSE = Gs.end(); GSI != GSE; ++GSI) {

+    int condim = GSI->first;

+    const StmtGrp &G = GSI->second;

+    DEBUG(dbgs() << "condim =: " << condim << "\n";);

+    DEBUG(dbgs() << "G Size: " <<  G.size() << "\n";);

+    StmtGrps NewGs;

+    ParentGrp NewPs;

+    bool EnterVar = true;

+

+    for (StmtGrp::const_iterator GI = G.begin(), GE = G.end(); GI != GE; ++GI) {

+      ScopStmt *stmt = *GI;

+      isl_map *scattering = stmt->getScattering();

+      bool Innermost = (G.size() == 1) && (Gs.size() == 1) &&

+        (pos >= isl_map_dim(scattering, isl_dim_out) - 1);

+

+      if (Innermost) {

+        const char *Name = stmt->getBaseName();

+        InnermostStmtSet.push_back(Name);

+        DEBUG(dbgs() << "Innermost: " << Name << "\n";);

+        if (hasVar) {

+          DEBUG(dbgs() << "a new variable\n";);          

+          LoopNestTreeFor *P = Ps[condim];

+          LoopNestTreeFor *LNTF = new LoopNestTreeFor(P);

+          P->addChild(LNTF);

+          NewPs[condim] = LNTF;

+          LoopNestTreeStmt *LNTS = new LoopNestTreeStmt(LNTF);

+          LNTS->setScopStmt(stmt);

+          LNTF->addChild(LNTS);

+        } else {

+          DEBUG(dbgs() << "ScopStmt.\n";);

+          LoopNestTreeFor *P = Ps[condim];

+          LoopNestTreeStmt *LNTS = new LoopNestTreeStmt(P);

+          LNTS->setScopStmt(stmt);

+          P->addChild(LNTS);

+        }

+      } else {

+        // If we encounter different (value) constant dimensions of the same pos,

+        // we add new branches(same constants of the same pos only means one node);

+        isl_int con;

+        isl_int_init(con);

+        if (isl_map_plain_is_fixed(scattering, isl_dim_out, pos, &con)) {

+          DEBUG(dbgs() << "a new constant\n";);

+          int intcon = intFromislint(con);

+          EnterVar = true;

+          DEBUG(dbgs() << "intcon: " << intcon << "\n";);

+

+          // If within a variable dimension there is "zero" dimensions, add "SCOPSTMT" nodes

+          // those "SCOPSTMT" nodes without siblings(no matter "FOR" or "SCOPSTMT")

+          // are innermost.

+          if (hasVar) {

+            assert((intcon == 0) && "The constant dimension is not zero!");

+            DEBUG(dbgs() << "ScopStmt.\n";);            

+            LoopNestTreeFor *P = Ps[condim];

+            LoopNestTreeStmt *LNTS = new LoopNestTreeStmt(P);

+            LNTS->setScopStmt(stmt);

+            P->addChild(LNTS);

+          } else {

+            NewGs[intcon].push_back(stmt);

+            NewPs[intcon] = Ps[condim];

+          }

+        } else {

+          NewGs[condim].push_back(stmt);

+          if (EnterVar) {

+            EnterVar = false;

+            // If we encounter a new variable dimension, we add a new "FOR" node(child);

+            DEBUG(dbgs() << "a new variable\n";);            

+            LoopNestTreeFor *P = Ps[condim];

+            LoopNestTreeFor *LNTF = new LoopNestTreeFor(P);

+            P->addChild(LNTF);

+            NewPs[condim] = LNTF;

+          }

+        }

+        isl_int_clear(con);

+      }

+      isl_map_free(scattering);

+    }

+    LoopNestScan(NewGs, pos+1, NewPs);

+  }

+}

+

+void LoopNestTree::releaseMemory() {

+  InnermostStmtSet.clear();

+  if (Root) {

+    delete Root;

+    Root = 0;

+  }

+}

+

+void LoopNestTree::dump() const {

+  printScop(dbgs());

+}

+

+void LoopNestTree::printScop(raw_ostream &OS) const {

+  OS << "Loop Nest Tree:\n";

+  OS << "-----------------------------\n";

+

+  /// DFS the LNT, print it out according to the nodetype

+  Root->print(OS, 0);

+  Root = new LoopNestTreeFor(0);

+

+  // First, we creat a "Root" node to be the ultimate parent of all nodes

+  Ps[0] = Root;

+

+  // we let all the scopstmts belongs to one group(StmtGrp).

+  for (Scop::const_iterator SI = S.begin(), SE = S.end(); SI != SE; ++SI)

+    Gs[0].push_back(*SI);

+

From 223f4a01cb596e90e99aeb3492ea94e6d9874404 Mon Sep 17 00:00:00 2001

From: TangKK <dengjunq...@hotmail.com>

Date: Wed, 18 Jul 2012 16:38:02 +0800

Subject: [PATCH 2/7] Add testcases to test polly-loopnesttree pass

---

 test/LoopNestTree/matmul.c                         |   52 +++

 test/LoopNestTree/matmul.ll                        |  207 ++++++++++++

 test/LoopNestTree/sim2mm.c                         |   50 +++

 test/LoopNestTree/sim2mm.ll                        |  333 ++++++++++++++++++++

 test/LoopNestTree/simple_loop.c                    |   20 ++

 test/LoopNestTree/simple_loop.ll                   |   67 ++++

 .../kernels/2mm/2mm_without_param.ll               |   25 ++

 .../kernels/3mm/3mm_without_param.ll               |   33 ++

 .../kernels/atax/atax_without_param.ll             |   24 ++

 .../kernels/bicg/bicg_without_param.ll             |   21 ++

 .../kernels/doitgen/doitgen_without_param.ll       |   23 ++

 11 files changed, 855 insertions(+), 0 deletions(-)

 create mode 100755 test/LoopNestTree/matmul.c

 create mode 100755 test/LoopNestTree/matmul.ll

 create mode 100755 test/LoopNestTree/sim2mm.c

 create mode 100644 test/LoopNestTree/sim2mm.ll

index eef2b63..2d5a9cf 100644

--- a/test/polybench/linear-algebra/kernels/2mm/2mm_without_param.ll

+++ b/test/polybench/linear-algebra/kernels/2mm/2mm_without_param.ll

@@ -1,4 +1,5 @@

 ; RUN: opt %loadPolly  %defaultOpts -polly-detect -analyze  %s | FileCheck %s

+; RUN: opt %loadPolly %defaultOpts -polly-loopnesttree -analyze %s | FileCheck %s -check-prefix=LNT

 ; ModuleID = './linear-algebra/kernels/2mm/2mm_without_param.ll'

 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"

 target triple = "x86_64-unknown-linux-gnu"

@@ -99,3 +100,27 @@ return:                                           ; preds = %bb15

   ret void

 }

 ; CHECK: Valid Region for Scop: bb5.preheader => return

+

+; LNT: Printing analysis 'Polly - Analysis the Loop Nest Tree' for region: 'bb5.preheader => return' in function 'scop_func':

+; LNT: Loop Nest Tree:

+; LNT: -----------------------------

+; LNT:   for

+; LNT:     for

+; LNT:       Stmt_bb_nph27_us

+; LNT:       for

+; LNT:         Stmt_bb2_us

+; LNT:       Stmt_bb4_us

+; LNT:   for

+; LNT:     for

+; LNT:       Stmt_bb_nph_us

+; LNT:       for

+; LNT:         Stmt_bb11_us

+; LNT:       Stmt_bb13_us

+; LNT: -----------------------------

+; LNT: End of Loop Nest Tree.

+; LNT: Innermost Loop(s):

+; LNT: *****************************

+; LNT: Stmt_bb2_us

+; LNT: Stmt_bb11_us

+; LNT: *****************************

+; LNT: End of Innermost Loop(s).

diff --git a/test/polybench/linear-algebra/kernels/3mm/3mm_without_param.ll b/test/polybench/linear-algebra/kernels/3mm/3mm_without_param.ll

index 25902dd..6f60685 100644

--- a/test/polybench/linear-algebra/kernels/3mm/3mm_without_param.ll

+++ b/test/polybench/linear-algebra/kernels/3mm/3mm_without_param.ll

@@ -1,4 +1,5 @@

 ; RUN: opt %loadPolly  %defaultOpts -polly-detect -analyze  %s | FileCheck %s

+; RUN: opt %loadPolly %defaultOpts -polly-loopnesttree -analyze %s | FileCheck %s -check-prefix=LNT

 ; ModuleID = './linear-algebra/kernels/3mm/3mm_without_param.ll'

 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"

 target triple = "x86_64-unknown-linux-gnu"

@@ -135,3 +136,35 @@ return:                                           ; preds = %bb24

   ret void

 }

 ; CHECK: Valid Region for Scop: bb5.preheader => return

+

+; LNT: Printing analysis 'Polly - Analysis the Loop Nest Tree' for region: 'bb5.preheader => return' in function 'scop_func':

+; LNT: Loop Nest Tree:

+; LNT: -----------------------------

+; LNT:   for

+; LNT:     for

+; LNT:       Stmt_bb_nph54_us

+; LNT:       for

+; LNT:         Stmt_bb2_us

+; LNT:       Stmt_bb4_us

+; LNT:   for

+; LNT:     for

+; LNT:       Stmt_bb_nph30_us

+; LNT:       for

+; LNT:         Stmt_bb11_us

+; LNT:       Stmt_bb13_us

+; LNT:   for

+; LNT:     for

+; LNT:       Stmt_bb_nph_us

+; LNT:       for

+; LNT:         Stmt_bb20_us

+; LNT:       Stmt_bb22_us

+; LNT: -----------------------------

+; LNT: End of Loop Nest Tree.

+

+; LNT: Innermost Loop(s):

+; LNT: *****************************

+; LNT: Stmt_bb2_us

+; LNT: Stmt_bb11_us

+; LNT: Stmt_bb20_us

+; LNT: *****************************

+; LNT: End of Innermost Loop(s).

\ No newline at end of file

diff --git a/test/polybench/linear-algebra/kernels/atax/atax_without_param.ll b/test/polybench/linear-algebra/kernels/atax/atax_without_param.ll

index c493a9e..09fe1dc 100644

--- a/test/polybench/linear-algebra/kernels/atax/atax_without_param.ll

+++ b/test/polybench/linear-algebra/kernels/atax/atax_without_param.ll

@@ -1,4 +1,5 @@

 ; RUN: opt %loadPolly  %defaultOpts -polly-cloog -analyze  %s | FileCheck %s

+; RUN: opt %loadPolly %defaultOpts -polly-loopnesttree -analyze %s | FileCheck %s -check-prefix=LNT

 ; ModuleID = './linear-algebra/kernels/atax/atax_without_param.ll'

 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"

 target triple = "x86_64-unknown-linux-gnu"

@@ -75,3 +76,26 @@ return:                                           ; preds = %bb9

 }

 ; CHECK:      for region: 'bb => return' in function 'scop_func':

 ; CHECK-NEXT: scop_func(): 

+

+; LNT: Printing analysis 'Polly - Analysis the Loop Nest Tree' for region: 'bb => return' in function 'scop_func':

+; LNT: Loop Nest Tree:

+; LNT: -----------------------------

+; LNT:   for

+; LNT:     Stmt_bb

+; LNT:   for

+; LNT:     Stmt_bb_nph

+; LNT:     for

+; LNT:       Stmt_bb4

+; LNT:     Stmt_bb8_loopexit

+; LNT:     for

+; LNT:       Stmt_bb7

+; LNT: -----------------------------

+; LNT: End of Loop Nest Tree.

+

+; LNT: Innermost Loop(s):

+; LNT: *****************************

+; LNT: Stmt_bb

+; LNT: Stmt_bb4

+; LNT: Stmt_bb7

+; LNT: *****************************

+; LNT: End of Innermost Loop(s).

diff --git a/test/polybench/linear-algebra/kernels/bicg/bicg_without_param.ll b/test/polybench/linear-algebra/kernels/bicg/bicg_without_param.ll

index d414d1f..45b5ca6 100644

--- a/test/polybench/linear-algebra/kernels/bicg/bicg_without_param.ll

+++ b/test/polybench/linear-algebra/kernels/bicg/bicg_without_param.ll

@@ -1,4 +1,5 @@

 ; RUN: opt %loadPolly  %defaultOpts -polly-cloog -analyze  %s | FileCheck %s

+; RUN: opt %loadPolly %defaultOpts -polly-loopnesttree -analyze %s | FileCheck %s -check-prefix=LNT

 ; ModuleID = './linear-algebra/kernels/bicg/bicg_without_param.ll'

 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"

 target triple = "x86_64-unknown-linux-gnu"

@@ -67,3 +68,23 @@ return:                                           ; preds = %bb6.us

 }

 ; CHECK:      for region: 'bb => return' in function 'scop_func':

 ; CHECK-NEXT: scop_func():

+

+; LNT: Printing analysis 'Polly - Analysis the Loop Nest Tree' for region: 'bb => return' in function 'scop_func':

+; LNT: Loop Nest Tree:

+; LNT: -----------------------------

+; LNT:   for

+; LNT:     Stmt_bb

+; LNT:   for

+; LNT:     Stmt_bb_nph_us

+; LNT:     for

+; LNT:       Stmt_bb4_us

+; LNT:     Stmt_bb6_us

+; LNT: -----------------------------

+; LNT: End of Loop Nest Tree.

+ 

+; LNT: Innermost Loop(s):

+; LNT: *****************************

+; LNT: Stmt_bb

+; LNT: Stmt_bb4_us

+; LNT: *****************************

+; LNT: End of Innermost Loop(s).

diff --git a/test/polybench/linear-algebra/kernels/doitgen/doitgen_without_param.ll b/test/polybench/linear-algebra/kernels/doitgen/doitgen_without_param.ll

index 19247e9..a9603bc 100644

--- a/test/polybench/linear-algebra/kernels/doitgen/doitgen_without_param.ll

+++ b/test/polybench/linear-algebra/kernels/doitgen/doitgen_without_param.ll

@@ -1,4 +1,5 @@

 ; RUN: opt %loadPolly  %defaultOpts -polly-detect -analyze  %s | FileCheck %s

+; RUN: opt %loadPolly %defaultOpts -polly-loopnesttree -analyze %s | FileCheck %s -check-prefix=LNT

 ; ModuleID = './linear-algebra/kernels/doitgen/doitgen_without_param.ll'

 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"

 target triple = "x86_64-unknown-linux-gnu"

@@ -77,3 +78,25 @@ return:                                           ; preds = %bb12

   ret void

 }

 ; CHECK: Valid Region for Scop: bb11.preheader => return 

+

+; LNT: Printing analysis 'Polly - Analysis the Loop Nest Tree' for region: 'bb11.preheader => return' in function 'scop_func':

+; LNT: Loop Nest Tree:

+; LNT: -----------------------------

+; LNT:   for

+; LNT:     for

+; LNT:       for

+; LNT:         Stmt_bb_nph_us

+; LNT:         for

+; LNT:           Stmt_bb3_us

+; LNT:         Stmt_bb5_us

+; LNT:       for

+; LNT:         Stmt_bb8

+; LNT: -----------------------------

+; LNT: End of Loop Nest Tree.

+

+; LNT: Innermost Loop(s):

+; LNT: *****************************

+; LNT: Stmt_bb3_us

+; LNT: Stmt_bb8

+; LNT: *****************************

+; LNT: End of Innermost Loop(s).

-- 

1.7.5.1

regards,

tangkk

[ether]

Can we also initialize the stmt in the constructor?

Please leave an empty line here to sperate the if block and the for block.

What about add some comments for the above variables? We should also move NewGs and NewPs out of the loop, and clear them at the begining of the loop body.

+

+    for (StmtGrp::const_iterator GI = G.begin(), GE = G.end(); GI != GE; ++GI) {

+      ScopStmt *stmt = *GI;

+      isl_map *scattering = stmt->getScattering();

+      bool Innermost = (G.size() == 1) && (Gs.size() == 1) &&

+        (pos >= isl_map_dim(scattering, isl_dim_out) - 1);

Please align the second line of the expression to the '=':

      bool Innermost = (G.size() == 1) && (Gs.size() == 1) &&

Otherwise it look good to me.

best regards
ether

[Jun-qi Deng]

Hi ether! This is a new patch according to your comments. Thank you!! And I also attach some other patches before this patch in my workspace for convenience.

From f07273b788c2adb4125d303f97eb34b9fcabbaf3 Mon Sep 17 00:00:00 2001

From: TangKK <dengjunq...@hotmail.com>

Date: Wed, 18 Jul 2012 16:37:26 +0800

Subject: [PATCH 1/7] Add LoopNestTree Analysis Pass - Analysis the Loop Nest

 Tree

Signed-off-by: TangKK <dengjunq...@hotmail.com>

---

 include/polly/LinkAllPasses.h         |    2 +

 include/polly/LoopNestTreeAnalysis.h  |  174 ++++++++++++++++++++++

 lib/Analysis/CMakeLists.txt           |    1 +

 lib/Analysis/LoopNestTreeAnalysis.cpp |  262 +++++++++++++++++++++++++++++++++

 lib/RegisterPasses.cpp                |    2 +

 test/CMakeLists.txt                   |    1 +

 6 files changed, 442 insertions(+), 0 deletions(-)

 create mode 100755 include/polly/LoopNestTreeAnalysis.h

 create mode 100755 lib/Analysis/LoopNestTreeAnalysis.cpp

diff --git a/include/polly/LinkAllPasses.h b/include/polly/LinkAllPasses.h

index 61721f4..b96756a 100644

--- a/include/polly/LinkAllPasses.h

+++ b/include/polly/LinkAllPasses.h

@@ -39,6 +39,7 @@ namespace polly {

   llvm::Pass *createDOTPrinterPass();

   llvm::Pass *createDOTViewerPass();

   llvm::Pass *createIndependentBlocksPass();

+  llvm::Pass *createLoopNestTreePass();

   llvm::Pass *createIndVarSimplifyPass();

   llvm::Pass *createJSONExporterPass();

   llvm::Pass *createJSONImporterPass();

@@ -93,6 +94,7 @@ namespace {

        createDOTViewerPass();

        createIndependentBlocksPass();

        createIndVarSimplifyPass();

+       createLoopNestTreePass();

        createJSONExporterPass();

        createJSONImporterPass();

        createPipforPass();

diff --git a/include/polly/LoopNestTreeAnalysis.h b/include/polly/LoopNestTreeAnalysis.h

new file mode 100755

index 0000000..771511c

--- /dev/null

+++ b/include/polly/LoopNestTreeAnalysis.h

@@ -0,0 +1,174 @@

+    friend class LoopNestTree;

+

+  public:

+    explicit LoopNestTreeStmt(LoopNestTreeBase *Parent, ScopStmt  *stmt) :

+      LoopNestTreeBase(Parent, SCOPSTMT), stmt(stmt) {}

index 0000000..5e97c3d

--- /dev/null

+++ b/lib/Analysis/LoopNestTreeAnalysis.cpp

@@ -0,0 +1,262 @@

+

+  // Gs.size() indicates how many stmt groups are there in this StmtGrps

+  DEBUG(dbgs() << (Gs.empty() ? "Gs Empty, return..." : "****Gs Size****:") <<  Gs.size() << "\n";);

+

+  bool hasVar = isVardim(Gs, pos);

+

+  // NewGs is a new Gs, storing a newly partitioned stmt groups

+  // NewPs is a new Ps, storing a newly assigned parent groups

+  StmtGrps NewGs;

+  ParentGrp NewPs;

+  for (StmtGrps::const_iterator GSI = Gs.begin(), GSE = Gs.end(); GSI != GSE; ++GSI) {

+    // condim is the number of the current Gs iteration (or condim is the stmt group number)

+    // G is the current stmt group, and G.size() indicates how many stmts are there in this StmtGrp

+    int condim = GSI->first;

+    const StmtGrp &G = GSI->second;

+    DEBUG(dbgs() << "condim =: " << condim << "\n";);

+    DEBUG(dbgs() << "G Size: " <<  G.size() << "\n";);

+

+    NewGs.clear();

+    NewPs.clear();

+

+    // EnterVar indicates whether "a new variable dimension" process can be executed,

+    // because for the same variable dimension encountered by consecutive stmts within the

+    // same StmtGrp, only one "FOR" node should be generated.

+    bool EnterVar = true;

+

+    for (StmtGrp::const_iterator GI = G.begin(), GE = G.end(); GI != GE; ++GI) {

+      ScopStmt *stmt = *GI;

+      isl_map *scattering = stmt->getScattering();

+      bool Innermost = (G.size() == 1) && (Gs.size() == 1) &&

+                              (pos >= isl_map_dim(scattering, isl_dim_out) - 1);

+

+      if (Innermost) {

+        const char *Name = stmt->getBaseName();

+        InnermostStmtSet.push_back(Name);

+        DEBUG(dbgs() << "Innermost: " << Name << "\n";);

+        if (hasVar) {

+          DEBUG(dbgs() << "a new variable\n";);          

+          LoopNestTreeFor *P = Ps[condim];

+          LoopNestTreeFor *LNTF = new LoopNestTreeFor(P);

+          P->addChild(LNTF);

+          NewPs[condim] = LNTF;

+          LoopNestTreeStmt *LNTS = new LoopNestTreeStmt(LNTF, stmt);

+          LNTF->addChild(LNTS);

+        } else {

+          DEBUG(dbgs() << "ScopStmt.\n";);

+          LoopNestTreeFor *P = Ps[condim];

+          LoopNestTreeStmt *LNTS = new LoopNestTreeStmt(P, stmt);

+          P->addChild(LNTS);

+        }

+      } else {

+        // If we encounter different (value) constant dimensions of the same pos,

+        // we add new branches(same constants of the same pos only means one node);

+        isl_int con;

+        isl_int_init(con);

+        if (isl_map_plain_is_fixed(scattering, isl_dim_out, pos, &con)) {

+          DEBUG(dbgs() << "a new constant\n";);

+          int intcon = intFromislint(con);

+          EnterVar = true;

+          DEBUG(dbgs() << "intcon: " << intcon << "\n";);

+

+          // If within a variable dimension there is "zero" dimensions, add "SCOPSTMT" nodes

+          // those "SCOPSTMT" nodes without siblings(no matter "FOR" or "SCOPSTMT")

+          // are innermost.

+          if (hasVar) {

+            assert((intcon == 0) && "The constant dimension is not zero!");

+            DEBUG(dbgs() << "ScopStmt.\n";);            

+            LoopNestTreeFor *P = Ps[condim];

+            LoopNestTreeStmt *LNTS = new LoopNestTreeStmt(P, stmt);

index 15637a7..5c2db79 100644

--- a/lib/RegisterPasses.cpp

+++ b/lib/RegisterPasses.cpp

@@ -20,6 +20,7 @@

 #include "polly/TempScopInfo.h"

 #include "polly/CodeGen/CodeGeneration.h"

 #include "polly/Pipfor.h"

+#include "polly/LoopNestTreeAnalysis.h"

 

 #include "llvm/Analysis/Passes.h"

 #include "llvm/Analysis/CFGPrinter.h"

@@ -147,6 +148,7 @@ static void initializePollyPasses(PassRegistry &Registry) {

   initializeJSONExporterPass(Registry);

   initializeJSONImporterPass(Registry);

   initializeIslScheduleOptimizerPass(Registry);

+  initializeLoopNestTreePass(Registry);

   initializePipforPass(Registry);

 #ifdef SCOPLIB_FOUND

   initializePoccPass(Registry);

diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt

index 2b531c2..f86afe6 100644

--- a/test/CMakeLists.txt

+++ b/test/CMakeLists.txt

@@ -4,6 +4,7 @@ set(POLLY_TEST_DIRECTORIES

   "ScheduleOptimizer"

   "CodeGen"

   "Cloog"

+  "LoopNestTree"

   "OpenMP"

   "Pipfor"

   "polybench"

-- 

1.7.5.1

regards,

tangkk

[Jun-qi Deng]

And here is a document patch! Please review.

From 2df2a4bf5f413bedec3cae7adaa05cf7236ef1de Mon Sep 17 00:00:00 2001

From: TangKK <dengjunq...@hotmail.com>

Date: Mon, 9 Jul 2012 15:24:18 +0800

Subject: [PATCH 03/13] www: add documentation for Pipfor and LoopNestTree

 Analysis

---

 www/documentation/LoopNestTreeAnalysis.html |  325 +++++++++++++++++++++++++++

 www/documentation/dataprefetching.html      |  213 ++++++++++++++++++

 www/todo.html                               |    7 +

 3 files changed, 545 insertions(+), 0 deletions(-)

 create mode 100755 www/documentation/LoopNestTreeAnalysis.html

 create mode 100755 www/documentation/dataprefetching.html

diff --git a/www/documentation/LoopNestTreeAnalysis.html b/www/documentation/LoopNestTreeAnalysis.html

new file mode 100755

index 0000000..f923332

--- /dev/null

+++ b/www/documentation/LoopNestTreeAnalysis.html

@@ -0,0 +1,325 @@

+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"

+        "http://www.w3.org/TR/html4/strict.dtd">

+<!-- Material used from: HTML 4.01 specs: http://www.w3.org/TR/html401/ -->

+<html>

+<head>

+  <META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">

+  <title>Loop Nest Tree Analysis</title>

+  <style>a{TEXT-DECORATION:none}</style>

+  <link type="text/css" rel="stylesheet" href="../menu.css">

+  <link type="text/css" rel="stylesheet" href="../content.css">

+  

+</head>

+

+<body>

+<div id="content">

+  <!--*********************************************************************-->

+  <h1>LoopNestTreeAnalysis  - Analyze the Loop Nest Tree</h1>

+  <!--*********************************************************************-->

+  

+<h2>Abstract</h2>

+<p>

+What I want to do is to find a general way to get the <u>loop/band tree</u> out

+of the scop, no matter where the scop comes from (before or after the isl

+optimizer), and afterwards get the <u>innmermost loop(s)</u>.

+</p>

+  

+<h2>Algorithm</h2>

+<p>

+This pass implements the following algorithm for creating a loop nest tree in

+the context of Polly:

+First, we creat a "Root" node to be the ultimate parent of all nodes.

+Then we scan pos by pos the scatterings of all the scopstmts. During the scanning:

+<li>If we encounter different (value) constant dimensions of the same pos,

+we add new branches(same constants of the same pos only means one node);</li>

+<li>If we encounter a new variable dimension, we add a new "FOR" node(child);</li>

+<li>If within a variable dimension there is "zero" dimension(s), add "SCOPSTMT"

+nodes, for this(these) dimension(s);</li>

+<li>we separate scopstmts into different

+groups according to the above mentioned different branches;</li>

+<li>a scattering will not be got rid of until a "SCOPSTMT" node is produced.</li>

+After such process, the loop nest tree is created, and those "SCOPSTMT" nodes

+without siblings(no matter "FOR" or "SCOPSTMT") are innermost.

+</p>

+

+<h2>Run the Pass</h2>

+<p>

+To run this pass, simply add -polly-loopnesttree option to the command line,

+such as:

+<pre>

+opt -basicaa -polly-prepare -polly-region-simplify -polly-detect -polly-scops

+-polly-show -polly-loopnesttree -polly-cloog -analyze $LLVMIR

+</pre> or

+<pre>

+opt -basicaa -polly-prepare -polly-region-simplify -polly-detect -polly-scops

+-polly-show -polly-opt-isl -polly-loopnesttree -polly-cloog -analyze $LLVMIR

+</pre> or

+<pre>

+opt_test -basicaa -polly-prepare -polly-region-simplify -polly-detect -polly-scops

+-polly-show -polly-loopnesttree -polly-cloog -analyze $LLVMIR -debug-only=polly-loopnesttree

+</pre> for debugging

+</p>

+

+<h2>Example</h2>

+<h3>Example 1</h3>

+<p>If the input source code is:

+<pre>

+for(i = 0; i < N; i++) {

+  for(j = 0; j < N; j++) {

+    C[i][j] = 0;

+    for(k = 0; k < N; k++) {

+      C[i][j] = C[i][j] + A[i][k] * B[k][j];

+    }

+  }

+}

+</pre>

+whose scop representation and cloog is:

+<pre>

+Printing analysis 'Polly - Create polyhedral description of Scops' for region: 'for.cond => for.end21' in function 'main':

+    Context:

+    {  :  }

+    Statements {

+        Stmt_for_body3

+            Domain :=

+                { Stmt_for_body3[i0, i1] : i0 >= 0 and i0 <= 1535 and i1 >= 0 and i1 <= 1535 };

+            Scattering :=

+                { Stmt_for_body3[i0, i1] -> scattering[0, i0, 0, i1, 0, 0, 0] };

+            WriteAccess :=

+                { Stmt_for_body3[i0, i1] -> MemRef_C[1536i0 + i1] };

+        Stmt_for_body7

+            Domain :=

+                { Stmt_for_body7[i0, i1, i2] : i0 >= 0 and i0 <= 1535 and i1 >= 0 and i1 <= 1535 and i2 >= 0 and i2 <= 1535 };

+            Scattering :=

+                { Stmt_for_body7[i0, i1, i2] -> scattering[0, i0, 0, i1, 1, i2, 0] };

+            ReadAccess :=

+                { Stmt_for_body7[i0, i1, i2] -> MemRef_C[1536i0 + i1] };

+            ReadAccess :=

+                { Stmt_for_body7[i0, i1, i2] -> MemRef_A[1536i0 + i2] };

+            ReadAccess :=

+                { Stmt_for_body7[i0, i1, i2] -> MemRef_B[i1 + 1536i2] };

+            WriteAccess :=

+                { Stmt_for_body7[i0, i1, i2] -> MemRef_C[1536i0 + i1] };

+    }

+Printing analysis 'Execute Cloog code generation' for region: 'for.cond => for.end21' in function 'main':

+main():

+for (c2=0;c2<=1535;c2++) {

+  for (c4=0;c4<=1535;c4++) {

+    Stmt_for_body3(c2,c4);

+    for (c6=0;c6<=1535;c6++) {

+      Stmt_for_body7(c2,c4,c6);

+    }

+  }

+}

+</pre>

+Then the recovered loop nest tree is:

+<pre>

+Loop Nest Tree:

+-----------------------------

+  for

+    for

+      Stmt_for_body3

+      for

+        Stmt_for_body7

+-----------------------------

+End of Loop Nest Tree.

+

+Innermost Loop(s):

+*****************************

+Stmt_for_body7

+*****************************

+End of Innermost Loop(s).

+</pre>

+where the innermost loop(s) of this scop is(are) also found.

+</p>

+

+<h3>Example 2</h3>

+<p>Here is another example analyzing the code after isl optimizer

+<pre>

+Kernel:

+  /* D := alpha*A*B*C + beta*D */

+  for (i = 0; i < ni; i++) {

+    for (j = 0; j < nj; j++) {

+  tmp[i][j] = 0;

+  for (k = 0; k < nk; ++k)

+    tmp[i][j] += alpha * A[i][k] * B[k][j];

+    }

+  }

+  for (i = 0; i < ni; i++) {

+    for (j = 0; j < nl; j++) {

+  D[i][j] *= beta;

+  for (k = 0; k < nj; ++k)

+    D[i][j] += tmp[i][k] * C[k][j];

+    }

+  }

+</pre>

+The after isl optimizer scop representation and cloog are:

+<pre>

+    Context:

+    {  :  }

+    Statements {

+        Stmt_for_body3

+            Domain :=

+                { Stmt_for_body3[i0, i1] : i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023 };

+            Scattering :=

+                { Stmt_for_body3[i0, i1] -> [0, o1, o2, i0, i1] : exists (e0 = [(o1)/32], e1 = [(o2)/32]: 32e0 = o1 and 32e1 = o2 and o1 <= i0 and o1 >= -31 + i0 and o2 <= i1 and o2 >= -31 + i1 and i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023) };

+            WriteAccess :=

+                { Stmt_for_body3[i0, i1] -> MemRef_tmp[1024i0 + i1] };

+        Stmt_for_body7

+            Domain :=

+                { Stmt_for_body7[i0, i1, i2] : i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023 and i2 >= 0 and i2 <= 1023 };

+            Scattering :=

+                { Stmt_for_body7[i0, i1, i2] -> [1, o1, o2, o3, i0, i1, i2] : exists (e0 = [(o1)/32], e1 = [(o2)/32], e2 = [(o3)/32]: 32e0 = o1 and 32e1 = o2 and 32e2 = o3 and o1 <= i0 and o1 >= -31 + i0 and o2 <= i1 and o2 >= -31 + i1 and o3 <= i2 and o3 >= -31 + i2 and i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023 and i2 >= 0 and i2 <= 1023) };

+            ReadAccess :=

+                { Stmt_for_body7[i0, i1, i2] -> MemRef_A[1024i0 + i2] };

+            ReadAccess :=

+                { Stmt_for_body7[i0, i1, i2] -> MemRef_B[i1 + 1024i2] };

+            ReadAccess :=

+                { Stmt_for_body7[i0, i1, i2] -> MemRef_tmp[1024i0 + i1] };

+            WriteAccess :=

+                { Stmt_for_body7[i0, i1, i2] -> MemRef_tmp[1024i0 + i1] };

+        Stmt_for_body26

+            Domain :=

+                { Stmt_for_body26[i0, i1] : i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023 };

+            Scattering :=

+                { Stmt_for_body26[i0, i1] -> [2, o1, o2, i0, i1] : exists (e0 = [(o1)/32], e1 = [(o2)/32]: 32e0 = o1 and 32e1 = o2 and o1 <= i0 and o1 >= -31 + i0 and o2 <= i1 and o2 >= -31 + i1 and i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023) };

+            ReadAccess :=

+                { Stmt_for_body26[i0, i1] -> MemRef_D[1024i0 + i1] };

+            WriteAccess :=

+                { Stmt_for_body26[i0, i1] -> MemRef_D[1024i0 + i1] };

+        Stmt_for_body32

+            Domain :=

+                { Stmt_for_body32[i0, i1, i2] : i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023 and i2 >= 0 and i2 <= 1023 };

+            Scattering :=

+                { Stmt_for_body32[i0, i1, i2] -> [3, o1, o2, o3, i0, i1, i2] : exists (e0 = [(o1)/32], e1 = [(o2)/32], e2 = [(o3)/32]: 32e0 = o1 and 32e1 = o2 and 32e2 = o3 and o1 <= i0 and o1 >= -31 + i0 and o2 <= i1 and o2 >= -31 + i1 and o3 <= i2 and o3 >= -31 + i2 and i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023 and i2 >= 0 and i2 <= 1023) };

+            ReadAccess :=

+                { Stmt_for_body32[i0, i1, i2] -> MemRef_tmp[1024i0 + i2] };

+            ReadAccess :=

+                { Stmt_for_body32[i0, i1, i2] -> MemRef_C[i1 + 1024i2] };

+            ReadAccess :=

+                { Stmt_for_body32[i0, i1, i2] -> MemRef_D[1024i0 + i1] };

+            WriteAccess :=

+                { Stmt_for_body32[i0, i1, i2] -> MemRef_D[1024i0 + i1] };

+    }

+Printing analysis 'Polly - Optimize schedule of SCoP' for region: 'for.cond => for.end49' in function 'main':

+Printing analysis 'Execute Cloog code generation' for region: 'for.cond => for.end49' in function 'main':

+main():

+for (c2=0;c2<=1023;c2+=32) {

+  for (c3=0;c3<=1023;c3+=32) {

+    for (c4=c2;c4<=c2+31;c4++) {

+      for (c5=c3;c5<=c3+31;c5++) {

+        Stmt_for_body3(c4,c5);

+      }

+    }

+  }

+}

+for (c2=0;c2<=1023;c2+=32) {

+  for (c3=0;c3<=1023;c3+=32) {

+    for (c4=0;c4<=1023;c4+=32) {

+      for (c5=c2;c5<=c2+31;c5++) {

+        for (c6=c3;c6<=c3+31;c6++) {

+          for (c7=c4;c7<=c4+31;c7++) {

+            Stmt_for_body7(c5,c6,c7);

+          }

+        }

+      }

+    }

+  }

+}

+for (c2=0;c2<=1023;c2+=32) {

+  for (c3=0;c3<=1023;c3+=32) {

+    for (c4=c2;c4<=c2+31;c4++) {

+      for (c5=c3;c5<=c3+31;c5++) {

+        Stmt_for_body26(c4,c5);

+      }

+    }

+  }

+}

+for (c2=0;c2<=1023;c2+=32) {

+  for (c3=0;c3<=1023;c3+=32) {

+    for (c4=0;c4<=1023;c4+=32) {

+      for (c5=c2;c5<=c2+31;c5++) {

+        for (c6=c3;c6<=c3+31;c6++) {

+          for (c7=c4;c7<=c4+31;c7++) {

+            Stmt_for_body32(c5,c6,c7);

+          }

+        }

+      }

+    }

+  }

+}

+</pre>

+This pass can recover the loop nest tree as:

+<pre>

+Printing analysis 'Polly - Analysis the Loop Nest Tree' for region: 'for.cond => for.end49' in function 'main':

+Loop Nest Tree:

+-----------------------------

+  for

+    for

+      for

+        for

+          Stmt_for_body3

+  for

+    for

+      for

+        for

+          for

+            for

+              Stmt_for_body7

+  for

+    for

+      for

+        for

+          Stmt_for_body26

+  for

+    for

+      for

+        for

+          for

+            for

+              Stmt_for_body32

+-----------------------------

+End of Loop Nest Tree.

+

+Innermost Loop(s):

+*****************************

+Stmt_for_body3

+Stmt_for_body7

+Stmt_for_body26

+Stmt_for_body32

+*****************************

+End of Innermost Loop(s).

+</pre>

+</p>

+

+<h2>Done and Todo</h2>

+

+<h3>Initially Implementing the LoopNestTree Analysis</h3>

+<table class="wikitable" cellpadding="2">

+<tbody>

+<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Analysis </th></tr>

+<tr style="background: rgb(239, 239, 239)">

+  <th width="400px"> Tasks</th>

+  <th width="150px"> Status </th>

+  <th> Owner </th>

+</tr>

+<tr>

+<th align="left">Implement the LoopNestTree Algorithm</th>

+<td align="center" class='done'>Done, under review</td>

+<td>Junqi</td>

+</tr>

+<tr>

+<th align="left">Compatibility with isl scheduler's schedule</th>

+<td align="center" class='done'>Done, under review</td>

+<td>Junqi</td>

+</tr>

+<tr>

+<th align="left">Arbitrary Schedule</th>

+<td align="center" class='open'>Todo</td>

+<td>Junqi</td>

+</tr>

+

+

+</tbody></table>

+     

+</body>

+</html>

\ No newline at end of file

diff --git a/www/documentation/dataprefetching.html b/www/documentation/dataprefetching.html

new file mode 100755

index 0000000..b295d02

--- /dev/null

+++ b/www/documentation/dataprefetching.html

@@ -0,0 +1,213 @@

+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"

+        "http://www.w3.org/TR/html4/strict.dtd">

+<!-- Material used from: HTML 4.01 specs: http://www.w3.org/TR/html401/ -->

+<html>

+<head>

+  <META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">

+  <title>Adding a data prefetching transformation to LLVM Polly</title>

+  <style>a{TEXT-DECORATION:none}</style>

+  <link type="text/css" rel="stylesheet" href="../menu.css">

+  <link type="text/css" rel="stylesheet" href="../content.css">

+  

+</head>

+

+<body>

+<div id="content">

+  <!--*********************************************************************-->

+  <h1>Locality Optimization - Adding a Data Prefetching Transformation to LLVM Polly</h1>

+  <!--*********************************************************************-->

+<h2>Abstract</h2>

+<p>Briefly speaking, such transformation splits the innermost loop into three

+task level pipelinable parts. They are head, which prefetches data, body,

+which performs calculation, and foot, which stores back data, and their loads

+(execution time) are balanced. The transformed code in some sense mimics the

+behavior of cache, but it is much more than cache because it is timely,

+accurate and simple. This transformation can well benefit those architectures

+with on-chip scratch-pad memory and capable of task level parallelism, such

+as GPU and FPGA. It will also work on multi-core CPU with non-blocking data

+cache prefetch instruction. Therefore, it will enable LLVM Polly to perform a

+much larger range of locality optimization.

+</p>

+<p>For example, a simple 1-D loop without inter-iteration dependency

+<pre>

+for (i = 0; i < N; i ++) {

+  A[i] += i;

+}

+</pre>

+What's on my mind is to split the body of the loop into the three parts, then

+it will look like

+<pre>

+pipfor (i = 0; i < N; i += PI) {

+ for (pi = 0; pi < min(PI, N-i); pi ++) //stmt.for.body.head

+   Aloc[pi] = A[i + pi];

+ for (pi = 0; pi < min(PI, N-i); pi ++) //stmt.for.body.body

+   Aloc[pi] = Aloc[pi] + i;

+ for (pi = 0; pi < min(PI, N-i); pi++) //stmt.for.body.foot

+   A[i + pi] = Aloc[pi];

+}

+</pre>

+where Aloc is a local memory address, and pipfor means piplinable for loop.

+</p>

+<p>Here is another example doing a more agressive job

+<pre>

+for (i = dist; i < N; i ++) {

+  A[i] = A[i] * pow(A[i - dist], 10);

+}

+</pre>

+In this case, the inter-iteration dependency within array A is RAW with a

+distance of dist iteration. The transformed version should be:

+<pre>

+for (i = 0; i < dist; i++) { //dep_buf_init

+  dep_buf [i] = A[i];

+}

+pipfor (i = dist; i < N; i+=PI) {

+  for (pi = 0; pi < min(PI, N-i); pi ++) { //head

+    Hloc[pi] = A[i + pi];

+    Hloc_dist[pi] = dep_buf[pi];

+  }

+  reorganize(dep_buf, PI); //left shift dep_buf by PI words.

+  copy(Bloc, Hloc, min(PI, N-i));

+  copy(Bloc_dist, Hloc_dist, min(PI, N-i));

+ 

+  for (pi = 0; pi < min(PI, N-i); pi ++) { //body

+    Bloc [pi] = Bloc[pi] * pow(Bloc_dist[pi],10);

+  }

+  update(dep_buf, PI);

+  copy(Floc, Bloc, min(PI, N-i));

+ 

+  for (pi = 0; pi < min(PI, N-i); pi++) { //foot

+     A[i + pi] = Floc[pi];

+  }

+}

+</pre>

+Depending on PI and dist, the dependency will be legal or illegal.

+</p>

+<p>

+Note that only the innermost loop(s) of the original program are analyzed.

+For how to find such loop(s), please refer to

+ <a href=LoopNestTreeAnalysis.html>LoopNestTreeAnalysis</a>.

+</p>

+

+<h2>Detail</h2>

+<p>

+<ul>

+<li>For a complete description of this project, you can refer to

+   <a href=

+   "http://www.google-melange.com/gsoc/proposal/review/google/gsoc2012/tangkk/1">

+   here</a>.</li>

+<li>Or if you are blocked by the firewall, please refer to <a href=

+   "http://www.tangkk.net/adding-a-data-prefetching-transformation-to-llvm-polly">

+   here</a>.</li>

+<li>For a more illustrative description, please refer to

+   <a href="#additional">Addtional Info</a>.</li>

+</ul>

+</p>

+

+<h2>Done</h2>

+<p><b>1)</b> 

+   Add to polly a polly-pipfor pass, which initially implements most of the 

+   analysis part of the Google Summer of Code 2012 proposal: Adding a data 

+   prefetching transformation to LLVM Polly - generating load-balanced and 

+   coarse-grain loop pipelinable code for more task level parallelism and 

+   data locality</p>

+<p>For the moment, this pass can

+<ol>

+  <li> 

+  Extract the LoadRegion(which is a vector of those read memory accesses),

+  StoreRegion(which is a vector of those write memory accesses) and ComputeRegion

+  (which is a vector of those instructions occur between a pair of load and store);

+  </li>

+  <li>Tell the RAW or WAR dependence distances of those 

+  read or write memory accesses within the same scopstmt;</li>

+</ol>

+</p>

+<p><b>2)</b> 

+   This analyzed pass is invoked through "-polly-pipfor" option when 

+   individually scheduling the polly passes, for example:<br>

+<pre>

+opt -S -mem2reg -loop-simplify -indvars $LLVMASM &gt; $LLVMIR<br>

+opt -basicaa -polly-prepare -polly-region-simplify -polly-detect -polly-pipfor -analyze $LLVMIR

+</pre></p>

+<p>And it is invoked through "-polly-piploop" option when loading polly into 

+   clang and automatically run it at -O3,for example:<br>

+<pre>

+pollycc -O3 -mllvm -polly $SOURCE -mllvm -polly-piploop (-mllvm -debug-only=your-pass)

+</pre></p>

+

+<h3>Phase 1 - Initially Implementing the Analysis Part</h3>

+<table class="wikitable" cellpadding="2">

+<tbody>

+<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Analysis </th></tr>

+<tr style="background: rgb(239, 239, 239)">

+  <th width="400px"> Tasks</th>

+  <th width="150px"> Status </th>

+  <th> Owner </th>

+</tr>

+<tr>

+<th align="left">Initial implementation, extract the three regions</th>

+<td align="center" class='done'>Done, need reviewing</td>

+<td>Junqi</td>

+</tr>

+<tr>

+<th align="left">Tell dependence distances of each access</th>

+<td align="center" class='done'>Done, need more tests</td>

+<td>Junqi</td>

+</tr>

+

+

+</tbody></table>

+

+<h2>Todo</h2>

+

+<h3>Phase 2 - Improving Analysis</h3>

+<table class="wikitable" cellpadding="2">

+<tbody>

+<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Analysis </th><tr>

+<tr style="background: rgb(239, 239, 239)">

+  <th width="400px"> Tasks</th>

+  <th width="150px"> Status </th>

+  <th> Owner </th>

+</tr>

+<tr>

+<th align="left">More different types of testcases</th>

+<td align="center" class='inprogress'>In Design</td>

+<td>Junqi</td>

+</tr>

+<tr>

+<th align="left">Indirect dependence analysis</th>

+<td align="center" class='inprogress'>In design</td>

+<td>Junqi</td>

+</tr>

+</tbody></table>

+

+<h3>Phase 3 - Codegen</h3>

+<table class="wikitable" cellpadding="2">

+<tbody>

+<tr><th colspan="3" style="background: rgb(239, 239, 239);"> Codegen - to be detailed </th><tr>

+<tr style="background: rgb(239, 239, 239)">

+  <th width="400px"> Tasks</th>

+  <th width="150px"> Status </th>

+  <th> Owner </th>

+</tr>

+<tr>

+<th align="left">Codegen of Pipfor code</th>

+<td align="center" class='open'>Open</td>

+<td>Junqi, ether</td>

+</tr>

+</tbody></table>

+

+<h2><a name="additional"></a>Additional Info</h2>

+<p>For an illustration about this project, please refer to

+<a href=

+"https://docs.google.com/open?id=0B1i5x1YLBRrkdlBTa3htdy1TZHF0MWxuNFN3cllKUQ">

+illustration</a></p>

+<p>For a systemC TLM description of this work, please refer to

+<a href=

+"https://docs.google.com/open?id=0B1i5x1YLBRrkU1lXczljUFdUSHk1a2trd1p6RXFxQQ">

+SystemC TLM</a> and for this SystemC model's simulation results, please refer to 

+<a href=

+"https://docs.google.com/open?id=0B1i5x1YLBRrkS1RWQXktLUtUSzJyUW9XSGJ0Y0ZrQQ">

+simulation results</a></p>

+     

+</body>

+</html>

\ No newline at end of file

diff --git a/www/todo.html b/www/todo.html

index 782181d..8357a49 100644

--- a/www/todo.html

+++ b/www/todo.html

@@ -81,12 +81,19 @@ dead code elimination</a>

 </th><td class="open">Open

 </td><td>

 </td></tr>

+<tr>

 <th align="left"> <a

 href="http://llvm.org/bugs/show_bug.cgi?id=10229">OpenSCoP Import/Export - Update to

 current version</a>

 </th><td class="open">Open

 </td><td>

 </td></tr>

+<tr>

+<th align="left"> <a href="http://polly.llvm.org/documentation/dataprefetching.html">

+Data Prefetching</a>

+</th><td class="inprogress">In Progress

+</td><td>

+</td></tr>

 

 <tr><td colspan='4'>&nbsp;</td></tr>

 <tr><th colspan="3" style="background: rgb(239, 239, 239);"> Back End</th></tr>

-- 

1.7.5.1

regards,

tangkk

[ether]

This patch look good to me, may be tobi can say something. Otherwise we can push this single patch (with the corresponding testcases patch) first.

best regards
ether

regards,

tangkk

[Hongbin Zheng]

Hi tobi,

What do you think about the LoopNestTree analysis? We may push it to
trunk first if it looks ok.

And Hi Sven, I also appreciate your comment if you have time :)

best regards
ether

The documentation by Junqi:

diff --git a/www/documentation/LoopNestTreeAnalysis.html
b/www/documentation/LoopNestTreeAnalysis.html
new file mode 100755

+This pass implements the following algorithm for creating a loop nest tree in
+the context of Polly:
+First, we creat a "Root" node to be the ultimate parent of all nodes.
+Then we scan pos by pos the scatterings of all the scopstmts. During
the scanning:
+<li>If we encounter different (value) constant dimensions of the same pos,

+we add new branches(same constants of the same pos only means one node);</li>
+<li>If we encounter a new variable dimension, we add a new "FOR"
node(child);</li>
+<li>If within a variable dimension there is "zero" dimension(s), add "SCOPSTMT"
+nodes, for this(these) dimension(s);</li>

+<li>we separate scopstmts into different
+groups according to the above mentioned different branches;</li>
+<li>a scattering will not be got rid of until a "SCOPSTMT" node is
produced.</li>
+After such process, the loop nest tree is created, and those "SCOPSTMT" nodes
+without siblings(no matter "FOR" or "SCOPSTMT") are innermost.

+ for(j = 0; j < N; j++) {

+ C[i][j] = 0;

+ for(k = 0; k < N; k++) {

+ C[i][j] = C[i][j] + A[i][k] * B[k][j];
+ }
+ }
+}

+</pre>
+whose scop representation and cloog is:
+<pre>
+Printing analysis 'Polly - Create polyhedral description of Scops'

for region: 'for.cond => for.end21' in function 'main':

+ Context:
+ { : }
+ Statements {
+ Stmt_for_body3
+ Domain :=
+ { Stmt_for_body3[i0, i1] : i0 >= 0 and i0 <= 1535 and
i1 >= 0 and i1 <= 1535 };
+ Scattering :=
+ { Stmt_for_body3[i0, i1] -> scattering[0, i0, 0, i1,
0, 0, 0] };
+ WriteAccess :=
+ { Stmt_for_body3[i0, i1] -> MemRef_C[1536i0 + i1] };
+ Stmt_for_body7
+ Domain :=

+ { Stmt_for_body7[i0, i1, i2] : i0 >= 0 and i0 <= 1535
and i1 >= 0 and i1 <= 1535 and i2 >= 0 and i2 <= 1535 };
+ Scattering :=

+ { Stmt_for_body7[i0, i1, i2] -> scattering[0, i0, 0,
i1, 1, i2, 0] };
+ ReadAccess :=
+ { Stmt_for_body7[i0, i1, i2] -> MemRef_C[1536i0 + i1] };
+ ReadAccess :=
+ { Stmt_for_body7[i0, i1, i2] -> MemRef_A[1536i0 + i2] };
+ ReadAccess :=
+ { Stmt_for_body7[i0, i1, i2] -> MemRef_B[i1 + 1536i2] };
+ WriteAccess :=
+ { Stmt_for_body7[i0, i1, i2] -> MemRef_C[1536i0 + i1] };
+ }

+Printing analysis 'Execute Cloog code generation' for region:

'for.cond => for.end21' in function 'main':

+main():
+for (c2=0;c2<=1535;c2++) {
+ for (c4=0;c4<=1535;c4++) {
+ Stmt_for_body3(c2,c4);
+ for (c6=0;c6<=1535;c6++) {
+ Stmt_for_body7(c2,c4,c6);
+ }
+ }
+}
+</pre>

+Then the recovered loop nest tree is:

+<pre>
+Loop Nest Tree:
+-----------------------------
+ for
+ for
+ Stmt_for_body3
+ for
+ Stmt_for_body7
+-----------------------------

+End of Loop Nest Tree.
+

+Innermost Loop(s):
+*****************************
+Stmt_for_body7
+*****************************
+End of Innermost Loop(s).
+</pre>

+where the innermost loop(s) of this scop is(are) also found.

+</p>
+
+<h3>Example 2</h3>
+<p>Here is another example analyzing the code after isl optimizer
+<pre>
+Kernel:

+ /* D := alpha*A*B*C + beta*D */
+ for (i = 0; i < ni; i++) {
+ for (j = 0; j < nj; j++) {
+ tmp[i][j] = 0;
+ for (k = 0; k < nk; ++k)
+ tmp[i][j] += alpha * A[i][k] * B[k][j];
+ }
+ }
+ for (i = 0; i < ni; i++) {
+ for (j = 0; j < nl; j++) {
+ D[i][j] *= beta;
+ for (k = 0; k < nj; ++k)
+ D[i][j] += tmp[i][k] * C[k][j];
+ }
+ }

+</pre>
+The after isl optimizer scop representation and cloog are:
+<pre>
+ Context:
+ { : }
+ Statements {
+ Stmt_for_body3
+ Domain :=

+ { Stmt_for_body3[i0, i1] : i0 >= 0 and i0 <= 1023 and

i1 >= 0 and i1 <= 1023 };

+ Scattering :=
+ { Stmt_for_body3[i0, i1] -> [0, o1, o2, i0, i1] :

exists (e0 = [(o1)/32], e1 = [(o2)/32]: 32e0 = o1 and 32e1 = o2 and o1
<= i0 and o1 >= -31 + i0 and o2 <= i1 and o2 >= -31 + i1 and i0 >= 0
and i0 <= 1023 and i1 >= 0 and i1 <= 1023) };

+ WriteAccess :=
+ { Stmt_for_body3[i0, i1] -> MemRef_tmp[1024i0 + i1] };

+ Stmt_for_body7
+ Domain :=

+ { Stmt_for_body7[i0, i1, i2] : i0 >= 0 and i0 <= 1023

and i1 >= 0 and i1 <= 1023 and i2 >= 0 and i2 <= 1023 };

+ Scattering :=
+ { Stmt_for_body7[i0, i1, i2] -> [1, o1, o2, o3, i0,

i1, i2] : exists (e0 = [(o1)/32], e1 = [(o2)/32], e2 = [(o3)/32]: 32e0
= o1 and 32e1 = o2 and 32e2 = o3 and o1 <= i0 and o1 >= -31 + i0 and
o2 <= i1 and o2 >= -31 + i1 and o3 <= i2 and o3 >= -31 + i2 and i0 >=
0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023 and i2 >= 0 and i2 <=
1023) };

+ ReadAccess :=
+ { Stmt_for_body7[i0, i1, i2] -> MemRef_A[1024i0 + i2] };
+ ReadAccess :=
+ { Stmt_for_body7[i0, i1, i2] -> MemRef_B[i1 + 1024i2] };
+ ReadAccess :=
+ { Stmt_for_body7[i0, i1, i2] -> MemRef_tmp[1024i0 + i1] };
+ WriteAccess :=
+ { Stmt_for_body7[i0, i1, i2] -> MemRef_tmp[1024i0 + i1] };

+ Stmt_for_body26
+ Domain :=

+ { Stmt_for_body26[i0, i1] : i0 >= 0 and i0 <= 1023

and i1 >= 0 and i1 <= 1023 };

+ Scattering :=
+ { Stmt_for_body26[i0, i1] -> [2, o1, o2, i0, i1] :

exists (e0 = [(o1)/32], e1 = [(o2)/32]: 32e0 = o1 and 32e1 = o2 and o1
<= i0 and o1 >= -31 + i0 and o2 <= i1 and o2 >= -31 + i1 and i0 >= 0
and i0 <= 1023 and i1 >= 0 and i1 <= 1023) };

+ ReadAccess :=
+ { Stmt_for_body26[i0, i1] -> MemRef_D[1024i0 + i1] };
+ WriteAccess :=
+ { Stmt_for_body26[i0, i1] -> MemRef_D[1024i0 + i1] };

+ Stmt_for_body32
+ Domain :=

+ { Stmt_for_body32[i0, i1, i2] : i0 >= 0 and i0 <=

1023 and i1 >= 0 and i1 <= 1023 and i2 >= 0 and i2 <= 1023 };

+ Scattering :=
+ { Stmt_for_body32[i0, i1, i2] -> [3, o1, o2, o3, i0,

i1, i2] : exists (e0 = [(o1)/32], e1 = [(o2)/32], e2 = [(o3)/32]: 32e0
= o1 and 32e1 = o2 and 32e2 = o3 and o1 <= i0 and o1 >= -31 + i0 and
o2 <= i1 and o2 >= -31 + i1 and o3 <= i2 and o3 >= -31 + i2 and i0 >=
0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023 and i2 >= 0 and i2 <=
1023) };

+ ReadAccess :=
+ { Stmt_for_body32[i0, i1, i2] -> MemRef_tmp[1024i0 + i2] };
+ ReadAccess :=
+ { Stmt_for_body32[i0, i1, i2] -> MemRef_C[i1 + 1024i2] };
+ ReadAccess :=
+ { Stmt_for_body32[i0, i1, i2] -> MemRef_D[1024i0 + i1] };
+ WriteAccess :=
+ { Stmt_for_body32[i0, i1, i2] -> MemRef_D[1024i0 + i1] };
+ }
+Printing analysis 'Polly - Optimize schedule of SCoP' for region:

'for.cond => for.end49' in function 'main':

+Printing analysis 'Execute Cloog code generation' for region:

'for.cond => for.end49' in function 'main':

+main():
+for (c2=0;c2<=1023;c2+=32) {

+ for (c3=0;c3<=1023;c3+=32) {
+ for (c4=c2;c4<=c2+31;c4++) {
+ for (c5=c3;c5<=c3+31;c5++) {

+ Stmt_for_body3(c4,c5);
+ }
+ }
+ }
+}
+for (c2=0;c2<=1023;c2+=32) {

+ for (c3=0;c3<=1023;c3+=32) {
+ for (c4=0;c4<=1023;c4+=32) {
+ for (c5=c2;c5<=c2+31;c5++) {
+ for (c6=c3;c6<=c3+31;c6++) {
+ for (c7=c4;c7<=c4+31;c7++) {
+ Stmt_for_body7(c5,c6,c7);

+ }
+ }
+ }
+ }
+ }

+}
+for (c2=0;c2<=1023;c2+=32) {

+ for (c3=0;c3<=1023;c3+=32) {
+ for (c4=c2;c4<=c2+31;c4++) {
+ for (c5=c3;c5<=c3+31;c5++) {

+ Stmt_for_body26(c4,c5);
+ }
+ }
+ }
+}
+for (c2=0;c2<=1023;c2+=32) {

+ for (c3=0;c3<=1023;c3+=32) {
+ for (c4=0;c4<=1023;c4+=32) {
+ for (c5=c2;c5<=c2+31;c5++) {
+ for (c6=c3;c6<=c3+31;c6++) {
+ for (c7=c4;c7<=c4+31;c7++) {
+ Stmt_for_body32(c5,c6,c7);

+ }
+ }
+ }
+ }
+ }

+}
+</pre>
+This pass can recover the loop nest tree as:
+<pre>

+Printing analysis 'Polly - Analysis the Loop Nest Tree' for region:

'for.cond => for.end49' in function 'main':

+End of Loop Nest Tree.
+

[Tobias Grosser]

On 08/21/2012 04:05 PM, Hongbin Zheng wrote:
> Hi tobi,
>
> What do you think about the LoopNestTree analysis? We may push it to
> trunk first if it looks ok.

Hi ether,

sorry for not coming pack to you earlier. I finally cached up with my
emails.

Regarding the LoopNestTree description again and some of your answers, I
am not yet sure where you are aiming for. Especially this TODO item:

> +<th align="left">Arbitrary Schedule</th>
> +<td align="center" class='open'>Todo</td>
> +<td>Junqi</td>

means, you plan to support arbitrary schedules. I know I talked about
that, but my comment was not really meant as a suggestion to do so, but
as a question if this is your goal. The question I ask myself is: If you
are aiming for generating a loop tree from an arbitrary schedule, how is
this different from the code generation problem. And if this is
identical to code generation, why don't you use cloog (or the upcoming
isl code generation) yourself? I am afraid the LoopNestTree will either
remain an incomplete code generation (which fails as soon as an external
scheduler provides unexpected input), or it will evolve into a full
blown code generator (we already have two?). What are you aiming for?

I understand that you want to work on user input schedules, original
schedules and on schedules provided from within the isl schedule
optimizer. To apply your analysis on all of them it may make sense to
temporarily build a loop tree. You could use normal code generation for
this. Calling the code generation as an intermediate step is a known
technique, called re-entrance. We try to avoid this as much as possible
as it adds on compile time, but if there is a need for it I am not
opposed to such a thing.

In Polly transformations such as vectorization work directly on the isl
band list, and do not work with externally provided schedules or the
original schedule. There are two reasons:

1) We avoid re-entrance and the added complexity.

2) I see the different optimizations as part of generating an 'optimal'
polyhedral schedule. To me it makes sense to do this in a single step.
Trying to take previous schedules (the original one or externally ones)
and fixing them up incrementally brings us back to the old path ordering
issues.

3) Staying within the isl_band system allows you to apply
vectorization/localization at the same time.

Please don't understand this as me asking you to move everything to the
isl band system. I describe this from my perspective, but there may very
well be reasons you want to take different approach for your
data-locality stuff.

Also, how much depends your data-locality stuff on the way to find
innermost loops? What is the information you get from this analysis? Is
it a set of innermost loops, where each loop is basically described by
the subset of the scattering space that it enumerates?

Cheers
Tobi

P.S.: Sorry again for the delay.

[Hongbin Zheng]

Hi tobi,


To my knowledge

On Wed, Aug 22, 2012 at 5:54 PM, Tobias Grosser <tob...@grosser.es> wrote:
> On 08/21/2012 04:05 PM, Hongbin Zheng wrote:
>>
>> Hi tobi,
>>
>> What do you think about the LoopNestTree analysis? We may push it to
>> trunk first if it looks ok.
>
>
> Hi ether,
>
> sorry for not coming pack to you earlier. I finally cached up with my
> emails.
>
> Regarding the LoopNestTree description again and some of your answers, I am
> not yet sure where you are aiming for. Especially this TODO item:

When performing optimization, we want to avoid appling the
optimizations to the statement in a non-innermost loops:
for ---not inner most loop {
for -- this is the inner most loop {
statement in inner most loop
}

statement not in inner most loop
}

And the LoopNestTree analysis is the analysis which recover the loop
nest information from the scartting.
With the tree, we can find the statements whose immediate parent loop
are innermost loop, and only optimze those statements.

>
>
>> +<th align="left">Arbitrary Schedule</th>
>> +<td align="center" class='open'>Todo</td>
>> +<td>Junqi</td>
>
> means, you plan to support arbitrary schedules.

Just want the analysis to be able to analyze the SCoP which is
processed by isl optimizer.

> I know I talked about that,
> but my comment was not really meant as a suggestion to do so, but as a
> question if this is your goal. The question I ask myself is: If you are
> aiming for generating a loop tree from an arbitrary schedule, how is this
> different from the code generation problem.
> And if this is identical to code
> generation, why don't you use cloog (or the upcoming isl code generation)
> yourself? I am afraid the LoopNestTree will either remain an incomplete code

Yes, I once use cloog, but cloog have side effect: It slightly
optimize the CFG of the SCoP,
so the CLAST_USER_STMT and the SCoPStatements may be not mapping one to one ...

> generation (which fails as soon as an external scheduler provides unexpected
> input), or it will evolve into a full blown code generator (we already have
> two?). What are you aiming for?
>
> I understand that you want to work on user input schedules, original
> schedules and on schedules provided from within the isl schedule optimizer.
> To apply your analysis on all of them it may make sense to temporarily build
> a loop tree. You could use normal code generation for this. Calling the code
> generation as an intermediate step is a known technique, called re-entrance.
> We try to avoid this as much as possible as it adds on compile time, but if
> there is a need for it I am not opposed to such a thing.

Ok.

>
> In Polly transformations such as vectorization work directly on the isl band
> list, and do not work with externally provided schedules or the original
> schedule. There are two reasons:
>
> 1) We avoid re-entrance and the added complexity.

Ok

>
> 2) I see the different optimizations as part of generating an 'optimal'
> polyhedral schedule. To me it makes sense to do this in a single step.

Ok, for the data-locality stuff, I do not plan to modify the schedule,
instead, i only want to insert extra load/stores.

> Trying to take previous schedules (the original one or externally ones) and
> fixing them up incrementally brings us back to the old path ordering issues.
>
> 3) Staying within the isl_band system allows you to apply
> vectorization/localization at the same time.
>
> Please don't understand this as me asking you to move everything to the isl
> band system. I describe this from my perspective, but there may very well be
> reasons you want to take different approach for your data-locality stuff.

Junqi investigate the isl_band stuff first, and I heard he said that
the isl_band not work at that moment.

>
> Also, how much depends your data-locality stuff on the way to find innermost
> loops? What is the information you get from this analysis? Is it a set of
> innermost loops, where each loop is basically described by the subset of the
> scattering space that it enumerates?

We are interested in the SCoPStmts in the loops do not containing sub-loops.
When performing optimization, we want to only optimize them without
messing up with other SCoPStmts,

best regards
ether

>
> Cheers
> Tobi
>

[Tobias Grosser]

On 08/22/2012 04:14 PM, Hongbin Zheng wrote:
> Hi tobi,

> To my knowledge

Thanks for the quick reply.

> On Wed, Aug 22, 2012 at 5:54 PM, Tobias Grosser <tob...@grosser.es> wrote:
>> On 08/21/2012 04:05 PM, Hongbin Zheng wrote:
>>>
>>> Hi tobi,
>>>
>>> What do you think about the LoopNestTree analysis? We may push it to
>>> trunk first if it looks ok.
>>
>>
>> Hi ether,
>>
>> sorry for not coming pack to you earlier. I finally cached up with my
>> emails.
>>
>> Regarding the LoopNestTree description again and some of your answers, I am
>> not yet sure where you are aiming for. Especially this TODO item:
>
> When performing optimization, we want to avoid appling the
> optimizations to the statement in a non-innermost loops:
> for ---not inner most loop {
> for -- this is the inner most loop {
> statement in inner most loop
> }
>
> statement not in inner most loop
> }
>
> And the LoopNestTree analysis is the analysis which recover the loop
> nest information from the scartting.
> With the tree, we can find the statements whose immediate parent loop
> are innermost loop, and only optimze those statements.

I see that. To get this you have the following options:

- Use the isl band tree
- Use cloog to generate a loop tree
- Use the upcoming isl code generation to generate a loop tree
- Add the new LoopNestTree analysis

The question is: Can option 1-3 work or is there a need for something else.

>>> +<th align="left">Arbitrary Schedule</th>
>>> +<td align="center" class='open'>Todo</td>
>>> +<td>Junqi</td>
>>
>> means, you plan to support arbitrary schedules.
> Just want the analysis to be able to analyze the SCoP which is
> processed by isl optimizer.

The output of the isl scheduler is not formally limited. In theory it
could take advantage of the full expressiveness of the schedule. This is
nowadays not really try, but I expect this to become more and more true.
When we perform tiling, we may e.g. do full and partial tile seperation.
Understanding this requires either to directly work in the scheduler or
to do full blown code generation. ;-)

>> I know I talked about that,
>> but my comment was not really meant as a suggestion to do so, but as a
>> question if this is your goal. The question I ask myself is: If you are
>> aiming for generating a loop tree from an arbitrary schedule, how is this
>> different from the code generation problem.
>> And if this is identical to code
>> generation, why don't you use cloog (or the upcoming isl code generation)
>> yourself? I am afraid the LoopNestTree will either remain an incomplete code
> Yes, I once use cloog, but cloog have side effect: It slightly
> optimize the CFG of the SCoP,
> so the CLAST_USER_STMT and the SCoPStatements may be not mapping one to one ...

In which way? A CLAST_USER_STMT may be duplicated (if loops are
splitted), but otherwise each CLAST_USER_STMT is created with a pointer
to a single SCoPStatement. Is this connection not preserved?

>> generation (which fails as soon as an external scheduler provides unexpected
>> input), or it will evolve into a full blown code generator (we already have
>> two?). What are you aiming for?
>>
>> I understand that you want to work on user input schedules, original
>> schedules and on schedules provided from within the isl schedule optimizer.
>> To apply your analysis on all of them it may make sense to temporarily build
>> a loop tree. You could use normal code generation for this. Calling the code
>> generation as an intermediate step is a known technique, called re-entrance.
>> We try to avoid this as much as possible as it adds on compile time, but if
>> there is a need for it I am not opposed to such a thing.
> Ok.
>>
>> In Polly transformations such as vectorization work directly on the isl band
>> list, and do not work with externally provided schedules or the original
>> schedule. There are two reasons:
>>
>> 1) We avoid re-entrance and the added complexity.
> Ok
>>
>> 2) I see the different optimizations as part of generating an 'optimal'
>> polyhedral schedule. To me it makes sense to do this in a single step.
> Ok, for the data-locality stuff, I do not plan to modify the schedule,
> instead, i only want to insert extra load/stores.

Which for me is actually some kind of scheduling modification. You don't
change the original schedule, but you add new statements that have a new
schedule.

>> Trying to take previous schedules (the original one or externally ones) and
>> fixing them up incrementally brings us back to the old path ordering issues.
>>
>> 3) Staying within the isl_band system allows you to apply
>> vectorization/localization at the same time.
>>
>> Please don't understand this as me asking you to move everything to the isl
>> band system. I describe this from my perspective, but there may very well be
>> reasons you want to take different approach for your data-locality stuff.
> Junqi investigate the isl_band stuff first, and I heard he said that
> the isl_band not work at that moment.

What is the exact problem here? Probably he already posted it, but as
you realized I am still catching up with the emails.

>> Also, how much depends your data-locality stuff on the way to find innermost
>> loops? What is the information you get from this analysis? Is it a set of
>> innermost loops, where each loop is basically described by the subset of the
>> scattering space that it enumerates?
> We are interested in the SCoPStmts in the loops do not containing sub-loops.
> When performing optimization, we want to only optimize them without
> messing up with other SCoPStmts,

You could use both CLooG to get this information, as well as adding it
to the isl band tree. The difference is that if you run cloog it will
work on every input schedule, but you probably don't have a close
connection to the transformations on the band tree. Running cloog may
also be a slower in terms of compile time. Using the band tree may
require some interactions with the other transformations there, but
should also be possible. One advantage to work with Cloog is that your
transformation is a really independent transformation and you don't need
to care a lot about interactions with other transformations.

In general, I expect your transformation to be independent of how you
get the set of innermost statements. We could go with a solution that is
easy to commit and not strongly connected with existing stuff, get
something committed soon, push the transformation itself and just at the
very end improve the compile time e.g. by avoiding re-entrance.

Tobi

[Hongbin Zheng]

On Wed, Aug 22, 2012 at 10:32 PM, Tobias Grosser <tob...@grosser.es> wrote:
> On 08/22/2012 04:14 PM, Hongbin Zheng wrote:
>>
>> Hi tobi,
>> To my knowledge
>
>
> Thanks for the quick reply.
>
>
>

> I see that. To get this you have the following options:
>
> - Use the isl band tree
> - Use cloog to generate a loop tree
> - Use the upcoming isl code generation to generate a loop tree
> - Add the new LoopNestTree analysis
>
> The question is: Can option 1-3 work or is there a need for something else.

Yes

>
>
> The output of the isl scheduler is not formally limited. In theory it could
> take advantage of the full expressiveness of the schedule. This is nowadays
> not really try, but I expect this to become more and more true. When we
> perform tiling, we may e.g. do full and partial tile seperation.
> Understanding this requires either to directly work in the scheduler or to
> do full blown code generation. ;-)

Ok, not the loop-nest tree analysis simply assume that the tiled loops
are perfect nested.

>
>
>>> I know I talked about that,
>>> but my comment was not really meant as a suggestion to do so, but as a
>>> question if this is your goal. The question I ask myself is: If you are
>>> aiming for generating a loop tree from an arbitrary schedule, how is this
>>> different from the code generation problem.
>>> And if this is identical to code
>>> generation, why don't you use cloog (or the upcoming isl code generation)
>>> yourself? I am afraid the LoopNestTree will either remain an incomplete
>>> code
>>
>> Yes, I once use cloog, but cloog have side effect: It slightly
>> optimize the CFG of the SCoP,
>> so the CLAST_USER_STMT and the SCoPStatements may be not mapping one to
>> one ...
>
>
> In which way? A CLAST_USER_STMT may be duplicated (if loops are splitted),
> but otherwise each CLAST_USER_STMT is created with a pointer to a single
> SCoPStatement. Is this connection not preserved?

I means two CLAST_USER_STMT pointing to the same SCoPStmt.

>
>
>
> Which for me is actually some kind of scheduling modification. You don't
> change the original schedule, but you add new statements that have a new
> schedule.

I forgot we need to modify the schedule statememts "after" the newly
inserted statements :)
Another approach is to provide a helper analysis to the codegen pass,
for a given statement to perform codegen, the analysis answer that
whether we need to insert prologue or/and epilogue for the statement.
In this approach, the new code is not inserted back into the SCoP.

>
>>
>> Junqi investigate the isl_band stuff first, and I heard he said that
>> the isl_band not work at that moment.
>
>
> What is the exact problem here? Probably he already posted it, but as you
> realized I am still catching up with the emails.

I need some searching.

>
>
>>> Also, how much depends your data-locality stuff on the way to find
>>> innermost
>>> loops? What is the information you get from this analysis? Is it a set of
>>> innermost loops, where each loop is basically described by the subset of
>>> the
>>> scattering space that it enumerates?
>>
>> We are interested in the SCoPStmts in the loops do not containing
>> sub-loops.
>> When performing optimization, we want to only optimize them without
>> messing up with other SCoPStmts,
>
>
> You could use both CLooG to get this information, as well as adding it to
> the isl band tree. The difference is that if you run cloog it will work on
> every input schedule, but you probably don't have a close connection to the
> transformations on the band tree. Running cloog may also be a slower in
> terms of compile time. Using the band tree may require some interactions
> with the other transformations there, but should also be possible. One
> advantage to work with Cloog is that your transformation is a really
> independent transformation and you don't need to care a lot about
> interactions with other transformations.

The pass is supposed to run after the isl optimizer, but it is good if
it can apply without the isl optimizer.

>
> In general, I expect your transformation to be independent of how you get
> the set of innermost statements. We could go with a solution that is easy to
> commit and not strongly connected with existing stuff, get something
> committed soon, push the transformation itself and just at the very end
> improve the compile time e.g. by avoiding re-entrance.

Yes
>
> Tobi
>
>
>

best regards
ether

[Tobias Grosser]

On 08/22/2012 05:08 PM, Hongbin Zheng wrote:
>> In which way? A CLAST_USER_STMT may be duplicated (if loops are splitted),
>> but otherwise each CLAST_USER_STMT is created with a pointer to a single
>> SCoPStatement. Is this connection not preserved?
> I means two CLAST_USER_STMT pointing to the same SCoPStmt.

What exactly was the problem here?

>> Which for me is actually some kind of scheduling modification. You don't
>> change the original schedule, but you add new statements that have a new
>> schedule.
> I forgot we need to modify the schedule statememts "after" the newly
> inserted statements :)
> Another approach is to provide a helper analysis to the codegen pass,
> for a given statement to perform codegen, the analysis answer that
> whether we need to insert prologue or/and epilogue for the statement.
> In this approach, the new code is not inserted back into the SCoP.

We could also need to go this way. I reasoned about it earlier and it
seems not a bad option.

>>> Junqi investigate the isl_band stuff first, and I heard he said that
>>> the isl_band not work at that moment.
>>
>>
>> What is the exact problem here? Probably he already posted it, but as you
>> realized I am still catching up with the emails.
> I need some searching.

OK.

>>>> Also, how much depends your data-locality stuff on the way to find
>>>> innermost
>>>> loops? What is the information you get from this analysis? Is it a set of
>>>> innermost loops, where each loop is basically described by the subset of
>>>> the
>>>> scattering space that it enumerates?
>>>
>>> We are interested in the SCoPStmts in the loops do not containing
>>> sub-loops.
>>> When performing optimization, we want to only optimize them without
>>> messing up with other SCoPStmts,
>>
>>
>> You could use both CLooG to get this information, as well as adding it to
>> the isl band tree. The difference is that if you run cloog it will work on
>> every input schedule, but you probably don't have a close connection to the
>> transformations on the band tree. Running cloog may also be a slower in
>> terms of compile time. Using the band tree may require some interactions
>> with the other transformations there, but should also be possible. One
>> advantage to work with Cloog is that your transformation is a really
>> independent transformation and you don't need to care a lot about
>> interactions with other transformations.
> The pass is supposed to run after the isl optimizer, but it is good if
> it can apply without the isl optimizer.

That would be a point for doing it directly in the code generator. How
much of the polyhedral information do you actually need. Another option
is to do it after Polly, similarly on how we run the BBVectorizer after
Polly. This is another option, but I am not sure if it makes sense in
your case.

Tobi

Cheers
Tobi

[Hongbin Zheng]

On Wed, Aug 22, 2012 at 11:23 PM, Tobias Grosser <tob...@grosser.es> wrote:
> On 08/22/2012 05:08 PM, Hongbin Zheng wrote:
>>>
>>> In which way? A CLAST_USER_STMT may be duplicated (if loops are
>>> splitted),
>>> but otherwise each CLAST_USER_STMT is created with a pointer to a single
>>> SCoPStatement. Is this connection not preserved?
>>
>> I means two CLAST_USER_STMT pointing to the same SCoPStmt.
>
>
> What exactly was the problem here?

We need find some way to distinguish these two instance of SCoPStmt
(Each of them are actually having different schedule), this is not
worked out at that time.
So maybe we need to handle this now :)

>>
>> I forgot we need to modify the schedule statememts "after" the newly
>> inserted statements :)
>> Another approach is to provide a helper analysis to the codegen pass,
>> for a given statement to perform codegen, the analysis answer that
>> whether we need to insert prologue or/and epilogue for the statement.
>> In this approach, the new code is not inserted back into the SCoP.
>
>
> We could also need to go this way. I reasoned about it earlier and it seems
> not a bad option.
>
>
>>>> Junqi investigate the isl_band stuff first, and I heard he said that
>>>> the isl_band not work at that moment.
>>>
>>>
>>>
>>> What is the exact problem here? Probably he already posted it, but as you
>>> realized I am still catching up with the emails.
>>
>> I need some searching.
>
>
> OK.
>
>

>
>

> That would be a point for doing it directly in the code generator. How much

At least We need the memory access function and the scattering, but it
looks like those are also available during the code generation.

> of the polyhedral information do you actually need. Another option is to do
> it after Polly, similarly on how we run the BBVectorizer after Polly. This
> is another option, but I am not sure if it makes sense in your case.

>
> Tobi
>
> Cheers
> Tobi

best regards
ether

[Tobias Grosser]

On 08/22/2012 05:44 PM, Hongbin Zheng wrote:
> On Wed, Aug 22, 2012 at 11:23 PM, Tobias Grosser <tob...@grosser.es> wrote:
>> On 08/22/2012 05:08 PM, Hongbin Zheng wrote:
>>>>
>>>> In which way? A CLAST_USER_STMT may be duplicated (if loops are
>>>> splitted),
>>>> but otherwise each CLAST_USER_STMT is created with a pointer to a single
>>>> SCoPStatement. Is this connection not preserved?
>>>
>>> I means two CLAST_USER_STMT pointing to the same SCoPStmt.
>>
>>
>> What exactly was the problem here?
> We need find some way to distinguish these two instance of SCoPStmt
> (Each of them are actually having different schedule), this is not
> worked out at that time.
> So maybe we need to handle this now :)

What about not working per statement, but on tuples (statement,
iteration-space-subset). So each item is defined you work on is defined
by the statement itself, but also the subset of the domain that is
enumerated in that innermost loop.

>>>>> Junqi investigate the isl_band stuff first, and I heard he said that
>>>>> the isl_band not work at that moment.
>>>>
>>>>
>>>>
>>>> What is the exact problem here? Probably he already posted it, but as you
>>>> realized I am still catching up with the emails.
>>>
>>> I need some searching.
>>
>>
>> OK.
>>
>>
>
>>
>>
>> That would be a point for doing it directly in the code generator. How much
> At least We need the memory access function and the scattering, but it
> looks like those are also available during the code generation.

The memory access function is available through the ScopStmt. The
scattering also. In addition you can get the subset of the scattering
space that is enumerated by the innermost loop, such that you know what
which statement iterations you need to take into account.

Tobi

[Hongbin Zheng]

On Wed, Aug 22, 2012 at 11:50 PM, Tobias Grosser <tob...@grosser.es> wrote:
> On 08/22/2012 05:44 PM, Hongbin Zheng wrote:
>>
>> On Wed, Aug 22, 2012 at 11:23 PM, Tobias Grosser <tob...@grosser.es>
>> wrote:
>>>
>>> On 08/22/2012 05:08 PM, Hongbin Zheng wrote:
>>>>>
>>>>>
>>>>> In which way? A CLAST_USER_STMT may be duplicated (if loops are
>>>>> splitted),
>>>>> but otherwise each CLAST_USER_STMT is created with a pointer to a
>>>>> single
>>>>> SCoPStatement. Is this connection not preserved?
>>>>
>>>>
>>>> I means two CLAST_USER_STMT pointing to the same SCoPStmt.
>>>
>>>
>>>
>>> What exactly was the problem here?
>>
>> We need find some way to distinguish these two instance of SCoPStmt
>> (Each of them are actually having different schedule), this is not
>> worked out at that time.
>> So maybe we need to handle this now :)
>
>
> What about not working per statement, but on tuples (statement,
> iteration-space-subset). So each item is defined you work on is defined by
> the statement itself, but also the subset of the domain that is enumerated
> in that innermost loop.

Sounds reasonable, I will investigate this later as the backend is almost ready.

>
>
>>>>>> Junqi investigate the isl_band stuff first, and I heard he said that
>>>>>> the isl_band not work at that moment.
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> What is the exact problem here? Probably he already posted it, but as
>>>>> you
>>>>> realized I am still catching up with the emails.
>>>>
>>>>
>>>> I need some searching.

I have to sleep now, and will search tomorrow.

>>>
>>>
>>>
>>> OK.
>>>
>>>
>>
>>>
>>>
>>> That would be a point for doing it directly in the code generator. How
>>> much
>>
>> At least We need the memory access function and the scattering, but it
>> looks like those are also available during the code generation.
>
>
> The memory access function is available through the ScopStmt. The scattering
> also. In addition you can get the subset of the scattering space that is
> enumerated by the innermost loop,

This sounds interesting, I am going to investigate this too and thanks
for the hint:)

[Jun-qi Deng]

2012/8/23 Hongbin Zheng <ethe...@gmail.com>

Maybe this is the moment I found why isl_band is not suitable: "Hello! Now I understand how to find innermost loop using isl_band forest which is generated by computing isl_schedule. So there is no problem to find the innermost loop after the isl optimizer. But what if I want to find the original untransformed code's innermost loop? Is it possible that I use the scattering information of each scopstmt within a scop to find the innermost loop? Or are there any ways that I can build a schedule of the original code(which does not re-reschedule anything at all, but just a description of the original schedule) which is similar to the isl_schedule computed by isl_union_set_compute_schedule, so that I can use a similar method as the isl_band forest to locate the innermost loop? Thank you!"

To simply put, at that time I found the isl_band method only works for the "transformed" code, but there is no way to find a loop nest tree in the original code using isl_band.

regards,

tangkk

[Tobias Grosser]

On 08/23/2012 05:50 PM, Jun-qi Deng wrote:
> 2012/8/23 Hongbin Zheng <ethe...@gmail.com <mailto:ethe...@gmail.com>>

>
> On Wed, Aug 22, 2012 at 11:50 PM, Tobias Grosser <tob...@grosser.es
> <mailto:tob...@grosser.es>> wrote:
> > On 08/22/2012 05:44 PM, Hongbin Zheng wrote:
> >>
> >> On Wed, Aug 22, 2012 at 11:23 PM, Tobias Grosser

> <tob...@grosser.es <mailto:tob...@grosser.es>>

Yes, you are right here. If you really want to get a loop nest tree for
an arbitrary schedule (I don't know if that is necessary or not) you
need to generate the loop nest tree yourself. That is possible and there
is nothing inherently bad about it (even though it has some disadvantages).

Assuming you want to handle arbitrary code, one option is to create the
loop tree just for your analysis pass. That is what the LoopNestTree
pass that you implemented does. However, getting it general enough to
handle an arbitrary schedule is to my knowledge equivalent to write a
new code generator. Did you encounter or do you see any problem with
using CLooG directly to extract the innermost loops? ether pointed out
another option where you could do the transformation even after code
generation directly on the generated AST. That may also be an
interesting possibility.

Cheers
Tobi

P.S.: Sorry again for coming so late to that discussion.