change interface for isStride

isStride now takes a partial schedule as input.

Patch from Tobias Grosser <tobias@grosser.es>.

llvm-svn: 170419

6 files changed, 79 insertions, 59 deletions

diff --git a/polly/include/polly/CodeGen/BlockGenerators.h b/polly/include/polly/CodeGen/BlockGenerators.h
index ed5ff3c7e55..e30042390e0 100644
--- a/polly/include/polly/CodeGen/BlockGenerators.h
+++ b/polly/include/polly/CodeGen/BlockGenerators.h
@@ -152,12 +152,16 @@ public:
   ///                   used for one vector lane. The number of elements in the
   ///                   vector defines the width of the generated vector
   ///                   instructions.
+  /// @param Schedule   A map from the statement to a schedule where the
+  ///                   innermost dimension is the dimension of the innermost
+  ///                   loop containing the statemenet.
   /// @param P          A reference to the pass this function is called from.
   ///                   The pass is needed to update other analysis.
   static void generate(IRBuilder<> &B, ScopStmt &Stmt,
-                       VectorValueMapT &GlobalMaps, __isl_keep isl_set *Domain,
+                       VectorValueMapT &GlobalMaps,
+                       __isl_keep isl_map *Schedule,
                        Pass *P) {
-    VectorBlockGenerator Generator(B, GlobalMaps, Stmt, Domain, P);
+    VectorBlockGenerator Generator(B, GlobalMaps, Stmt, Schedule, P);
     Generator.copyBB();
   }
 
@@ -169,10 +173,13 @@ private:
   // all referenes to the old instructions with their recalculated values.
   VectorValueMapT &GlobalMaps;
 
-  isl_set *Domain;
+  // A map from the statement to a schedule where the innermost dimension is the
+  // dimension of the innermost loop containing the statemenet.
+  isl_map *Schedule;
 
   VectorBlockGenerator(IRBuilder<> &B, VectorValueMapT &GlobalMaps,
-                       ScopStmt &Stmt, __isl_keep isl_set *Domain, Pass *P);
+                       ScopStmt &Stmt, __isl_keep isl_map *Schedule,
+                       Pass *P);
 
   int getVectorWidth();
 
diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index a6cf99771b0..00aefcca737 100755
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -148,20 +148,27 @@ public:
   /// @brief Get the new access function imported from JSCOP file
   isl_map *getNewAccessRelation() const;
 
-  /// @brief Get the stride of this memory access in the specified domain
-  ///        subset.
-  isl_set *getStride(__isl_take const isl_set *domainSubset) const;
-
-  /// @brief Is the stride of the access equal to a certain width.
-  bool isStrideX(__isl_take const isl_set *DomainSubset, int StrideWidth) const;
-
-  /// @brief Is consecutive memory accessed for a given
-  ///        statement instance set?
-  bool isStrideOne(__isl_take const isl_set *domainSubset) const;
-
-  /// @brief Is always the same memory accessed for a given
-  ///        statement instance set?
-  bool isStrideZero(__isl_take const isl_set *domainSubset) const;
+  /// Get the stride of this memory access in the specified Schedule. Schedule
+  /// is a map from the statement to a schedule where the innermost dimension is
+  /// the dimension of the innermost loop containing the statemenet.
+  isl_set *getStride(__isl_take const isl_map *Schedule) const;
+
+  /// Is the stride of the access equal to a certain width? Schedule is a map
+  /// from the statement to a schedule where the innermost dimension is the
+  /// dimension of the innermost loop containing the statemenet.
+  bool isStrideX(__isl_take const isl_map *Schedule, int StrideWidth) const;
+
+  /// Is consecutive memory accessed for a given statement instance set?
+  /// Schedule is a map from the statement to a schedule where the innermost
+  /// dimension is the dimension of the innermost loop containing the
+  /// statemenet.
+  bool isStrideOne(__isl_take const isl_map *Schedule) const;
+
+  /// Is always the same memory accessed for a given statement instance set?
+  /// Schedule is a map from the statement to a schedule where the innermost
+  /// dimension is the dimension of the innermost loop containing the
+  /// statemenet.
+  bool isStrideZero(__isl_take const isl_map *Schedule) const;
 
   /// @brief Get the statement that contains this memory access.
   ScopStmt *getStatement() const { return statement; }
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 9c9932695a7..f0827b3acd7 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -389,41 +389,30 @@ static isl_map *getEqualAndLarger(isl_space *setDomain) {
   return Map;
 }
 
-isl_set *MemoryAccess::getStride(__isl_take const isl_set *domainSubset) const {
-  isl_map *accessRelation = getAccessRelation();
-  isl_set *scatteringDomain = const_cast<isl_set*>(domainSubset);
-  isl_map *scattering = getStatement()->getScattering();
+isl_set *MemoryAccess::getStride(__isl_take const isl_map *Schedule) const {
+  isl_map *S = const_cast<isl_map*>(Schedule);
+  isl_map *AccessRelation = getAccessRelation();
+  isl_space *Space = isl_space_range(isl_map_get_space(S));
+  isl_map *NextScatt = getEqualAndLarger(Space);
 
-  scattering = isl_map_reverse(scattering);
-  int difference = isl_map_n_in(scattering) - isl_set_n_dim(scatteringDomain);
-  scattering = isl_map_project_out(scattering, isl_dim_in,
-                                   isl_set_n_dim(scatteringDomain),
-                                   difference);
+  S = isl_map_reverse(S);
+  NextScatt = isl_map_lexmin(NextScatt);
 
-  // Remove all names of the scattering dimensions, as the names may be lost
-  // anyways during the project. This leads to consistent results.
-  scattering = isl_map_set_tuple_name(scattering, isl_dim_in, "");
-  scatteringDomain = isl_set_set_tuple_name(scatteringDomain, "");
+  NextScatt = isl_map_apply_range(NextScatt, isl_map_copy(S));
+  NextScatt = isl_map_apply_range(NextScatt, isl_map_copy(AccessRelation));
+  NextScatt = isl_map_apply_domain(NextScatt, S);
+  NextScatt = isl_map_apply_domain(NextScatt, AccessRelation);
 
-  isl_map *nextScatt = getEqualAndLarger(isl_set_get_space(scatteringDomain));
-  nextScatt = isl_map_lexmin(nextScatt);
-
-  scattering = isl_map_intersect_domain(scattering, scatteringDomain);
-
-  nextScatt = isl_map_apply_range(nextScatt, isl_map_copy(scattering));
-  nextScatt = isl_map_apply_range(nextScatt, isl_map_copy(accessRelation));
-  nextScatt = isl_map_apply_domain(nextScatt, scattering);
-  nextScatt = isl_map_apply_domain(nextScatt, accessRelation);
-
-  return isl_map_deltas(nextScatt);
+  isl_set *Deltas = isl_map_deltas(NextScatt);
+  return Deltas;
 }
 
-bool MemoryAccess::isStrideX(__isl_take const isl_set *DomainSubset,
+bool MemoryAccess::isStrideX(__isl_take const isl_map *Schedule,
                              int StrideWidth) const {
   isl_set *Stride, *StrideX;
   bool IsStrideX;
 
-  Stride = getStride(DomainSubset);
+  Stride = getStride(Schedule);
   StrideX = isl_set_universe(isl_set_get_space(Stride));
   StrideX = isl_set_fix_si(StrideX, isl_dim_set, 0, StrideWidth);
   IsStrideX = isl_set_is_equal(Stride, StrideX);
@@ -434,12 +423,12 @@ bool MemoryAccess::isStrideX(__isl_take const isl_set *DomainSubset,
   return IsStrideX;
 }
 
-bool MemoryAccess::isStrideZero(const isl_set *DomainSubset) const {
-  return isStrideX(DomainSubset, 0);
+bool MemoryAccess::isStrideZero(const isl_map *Schedule) const {
+  return isStrideX(Schedule, 0);
 }
 
-bool MemoryAccess::isStrideOne(const isl_set *DomainSubset) const {
-  return isStrideX(DomainSubset, 1);
+bool MemoryAccess::isStrideOne(const isl_map *Schedule) const {
+  return isStrideX(Schedule, 1);
 }
 
 void MemoryAccess::setNewAccessRelation(isl_map *newAccess) {
diff --git a/polly/lib/CodeGen/BlockGenerators.cpp b/polly/lib/CodeGen/BlockGenerators.cpp
index e8109bdd1fe..1e5341a36e9 100644
--- a/polly/lib/CodeGen/BlockGenerators.cpp
+++ b/polly/lib/CodeGen/BlockGenerators.cpp
@@ -562,12 +562,14 @@ void BlockGenerator::copyBB(ValueMapT &GlobalMap) {
 }
 
 VectorBlockGenerator::VectorBlockGenerator(IRBuilder<> &B,
-  VectorValueMapT &GlobalMaps, ScopStmt &Stmt, __isl_keep isl_set *Domain,
-  Pass *P) : BlockGenerator(B, Stmt, P), GlobalMaps(GlobalMaps),
-  Domain(Domain) {
-    assert(GlobalMaps.size() > 1 && "Only one vector lane found");
-    assert(Domain && "No statement domain provided");
-  }
+                                           VectorValueMapT &GlobalMaps,
+                                           ScopStmt &Stmt,
+                                           __isl_keep isl_map *Schedule,
+                                           Pass *P)
+  : BlockGenerator(B, Stmt, P), GlobalMaps(GlobalMaps), Schedule(Schedule) {
+  assert(GlobalMaps.size() > 1 && "Only one vector lane found");
+  assert(Schedule && "No statement domain provided");
+}
 
 Value *VectorBlockGenerator::getVectorValue(const Value *Old,
                                             ValueMapT &VectorMap,
@@ -675,9 +677,9 @@ void VectorBlockGenerator::generateLoad(const LoadInst *Load,
   MemoryAccess &Access = Statement.getAccessFor(Load);
 
   Value *NewLoad;
-  if (Access.isStrideZero(isl_set_copy(Domain)))
+  if (Access.isStrideZero(isl_map_copy(Schedule)))
     NewLoad = generateStrideZeroLoad(Load, ScalarMaps[0]);
-  else if (Access.isStrideOne(isl_set_copy(Domain)))
+  else if (Access.isStrideOne(isl_map_copy(Schedule)))
     NewLoad = generateStrideOneLoad(Load, ScalarMaps[0]);
   else
     NewLoad = generateUnknownStrideLoad(Load, ScalarMaps);
@@ -726,7 +728,7 @@ void VectorBlockGenerator::copyStore(const StoreInst *Store,
   Value *Vector = getVectorValue(Store->getValueOperand(), VectorMap,
                                    ScalarMaps);
 
-  if (Access.isStrideOne(isl_set_copy(Domain))) {
+  if (Access.isStrideOne(isl_map_copy(Schedule))) {
     Type *VectorPtrType = getVectorPtrTy(Pointer, VectorWidth);
     Value *NewPointer = getNewValue(Pointer, ScalarMaps[0], GlobalMaps[0]);
 
diff --git a/polly/lib/CodeGen/CodeGeneration.cpp b/polly/lib/CodeGen/CodeGeneration.cpp
index 064c828df79..60302cb123f 100644
--- a/polly/lib/CodeGen/CodeGeneration.cpp
+++ b/polly/lib/CodeGen/CodeGeneration.cpp
@@ -394,6 +394,19 @@ void ClastStmtCodeGen::codegenSubstitutions(const clast_stmt *Assignment,
   }
 }
 
+// Takes the cloog specific domain and translates it into a map Statement ->
+// PartialSchedule, where the PartialSchedule contains all the dimensions that
+// have been code generated up to this point.
+static __isl_give isl_map *extractPartialSchedule(ScopStmt *Statement,
+                                                  isl_set *Domain) {
+  isl_map *Schedule = Statement->getScattering();
+  int ScheduledDimensions = isl_set_dim(Domain, isl_dim_set);
+  int UnscheduledDimensions = isl_map_dim(Schedule, isl_dim_out) - ScheduledDimensions;
+
+  return isl_map_project_out(Schedule, isl_dim_out, ScheduledDimensions,
+                             UnscheduledDimensions);
+}
+
 void ClastStmtCodeGen::codegen(const clast_user_stmt *u,
                                std::vector<Value*> *IVS , const char *iterator,
                                isl_set *Domain) {
@@ -422,7 +435,9 @@ void ClastStmtCodeGen::codegen(const clast_user_stmt *u,
     }
   }
 
-  VectorBlockGenerator::generate(Builder, *Statement, VectorMap, Domain, P);
+  isl_map *Schedule = extractPartialSchedule(Statement, Domain);
+  VectorBlockGenerator::generate(Builder, *Statement, VectorMap, Schedule, P);
+  isl_map_free(Schedule);
 }
 
 void ClastStmtCodeGen::codegen(const clast_block *b) {
diff --git a/polly/lib/CodeGen/IslAst.cpp b/polly/lib/CodeGen/IslAst.cpp
index 5d16fda1612..d3d65dce4ff 100644
--- a/polly/lib/CodeGen/IslAst.cpp
+++ b/polly/lib/CodeGen/IslAst.cpp
@@ -246,7 +246,7 @@ static int containsLoops(__isl_take isl_ast_node *Node, void *User) {
     isl_ast_node_free(Node);
     return 0;
   case isl_ast_node_block: {
-    isl_ast_node_list *List = isl_ast_node_block_get_children(Node); 
+    isl_ast_node_list *List = isl_ast_node_block_get_children(Node);
     int Res = isl_ast_node_list_foreach(List, &containsLoops, NULL);
     isl_ast_node_list_free(List);
     isl_ast_node_free(Node);