Use wrapped reduction dependences

  This change will ease the transision to multiple reductions per statement as
  we can now distinguish the effects of multiple reductions in the same
  statement.

  + Wrapped reduction dependences are used to compute privatization dependences
  + Modified test cases to account for the change

llvm-svn: 211795

4 files changed, 67 insertions, 44 deletions

diff --git a/polly/lib/Analysis/Dependences.cpp b/polly/lib/Analysis/Dependences.cpp
index bcdcb93eaab..37be06c70f1 100644
--- a/polly/lib/Analysis/Dependences.cpp
+++ b/polly/lib/Analysis/Dependences.cpp
@@ -284,22 +284,6 @@ void Dependences::calculateDependences(Scop &S) {
                                             isl_union_map_domain(StmtSchedule));
   DEBUG(dbgs() << "Wrapped Dependences:\n"; printScop(dbgs()); dbgs() << "\n");
 
-  RAW = isl_union_map_zip(RAW);
-  WAW = isl_union_map_zip(WAW);
-  WAR = isl_union_map_zip(WAR);
-
-  DEBUG(dbgs() << "Zipped Dependences:\n"; printScop(dbgs()); dbgs() << "\n");
-
-  RAW = isl_union_map_union(isl_union_set_unwrap(isl_union_map_domain(RAW)),
-                            STMT_RAW);
-  WAW = isl_union_map_union(isl_union_set_unwrap(isl_union_map_domain(WAW)),
-                            STMT_WAW);
-  WAR = isl_union_map_union(isl_union_set_unwrap(isl_union_map_domain(WAR)),
-                            STMT_WAR);
-
-  DEBUG(dbgs() << "Unwrapped Dependences:\n"; printScop(dbgs());
-        dbgs() << "\n");
-
   // To handle reduction dependences we proceed as follows:
   // 1) Aggregate all possible reduction dependences, namely all self
   //    dependences on reduction like statements.
@@ -320,9 +304,9 @@ void Dependences::calculateDependences(Scop &S) {
     for (MemoryAccess *MA : *Stmt) {
       if (!MA->isReductionLike())
         continue;
-      isl_set *AccDom = isl_map_domain(MA->getAccessRelation());
+      isl_set *AccDomW = isl_map_wrap(MA->getAccessRelation());
       isl_map *Identity =
-          isl_map_from_domain_and_range(isl_set_copy(AccDom), AccDom);
+          isl_map_from_domain_and_range(isl_set_copy(AccDomW), AccDomW);
       RED = isl_union_map_add_map(RED, Identity);
       break;
     }
@@ -342,6 +326,28 @@ void Dependences::calculateDependences(Scop &S) {
     addPrivatizationDependences();
   }
 
+  DEBUG(dbgs() << "Final Wrapped Dependences:\n"; printScop(dbgs());
+        dbgs() << "\n");
+
+  RAW = isl_union_map_zip(RAW);
+  WAW = isl_union_map_zip(WAW);
+  WAR = isl_union_map_zip(WAR);
+  RED = isl_union_map_zip(RED);
+
+  DEBUG(dbgs() << "Zipped Dependences:\n"; printScop(dbgs()); dbgs() << "\n");
+
+  RAW = isl_union_set_unwrap(isl_union_map_domain(RAW));
+  WAW = isl_union_set_unwrap(isl_union_map_domain(WAW));
+  WAR = isl_union_set_unwrap(isl_union_map_domain(WAR));
+  RED = isl_union_set_unwrap(isl_union_map_domain(RED));
+
+  DEBUG(dbgs() << "Unwrapped Dependences:\n"; printScop(dbgs());
+        dbgs() << "\n");
+
+  RAW = isl_union_map_union(RAW, STMT_RAW);
+  WAW = isl_union_map_union(WAW, STMT_WAW);
+  WAR = isl_union_map_union(WAR, STMT_WAR);
+
   RAW = isl_union_map_coalesce(RAW);
   WAW = isl_union_map_coalesce(WAW);
   WAR = isl_union_map_coalesce(WAR);
diff --git a/polly/test/Dependences/reduction_multiple_reductions.ll b/polly/test/Dependences/reduction_multiple_reductions.ll
index 68bb81a60d1..461f9e4746b 100644
--- a/polly/test/Dependences/reduction_multiple_reductions.ll
+++ b/polly/test/Dependences/reduction_multiple_reductions.ll
@@ -9,7 +9,8 @@
 ; CHECK: WAW dependences:
 ; CHECK:   {  }
 ; CHECK: Reduction dependences:
-; CHECK:   { Stmt_if_then[i0] -> Stmt_if_then[1 + i0] : i0 <= 510 and i0 >= 0; Stmt_if_else[i0] -> Stmt_if_else[1 + i0] : i0 <= 1022 and i0 >= 512 }
+; CHECK-DAG: Stmt_if_then[i0] -> Stmt_if_then[1 + i0] : i0 <= 510 and i0 >= 0
+; CHECK-DAG: Stmt_if_else[i0] -> Stmt_if_else[1 + i0] : i0 <= 1022 and i0 >= 512
 ;
 ; void f(int *restrict sum, int *restrict prod) {
 ;   for (int i = 0; i < 1024; i++)
diff --git a/polly/test/Dependences/reduction_privatization_deps.ll b/polly/test/Dependences/reduction_privatization_deps.ll
index e733a3d9f57..a4f08950620 100644
--- a/polly/test/Dependences/reduction_privatization_deps.ll
+++ b/polly/test/Dependences/reduction_privatization_deps.ll
@@ -24,7 +24,6 @@
 ;      for (int i = 0; i < 1024; i++)
 ; S2:    sum[i] = sum[i + 1] * 3;
 ;    }
-;
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
 
 define void @f(i32* %sum)  {
diff --git a/polly/test/Dependences/reduction_simple_iv_debug_wrapped_dependences.ll b/polly/test/Dependences/reduction_simple_iv_debug_wrapped_dependences.ll
index ae461346aea..2982f9eb660 100644
--- a/polly/test/Dependences/reduction_simple_iv_debug_wrapped_dependences.ll
+++ b/polly/test/Dependences/reduction_simple_iv_debug_wrapped_dependences.ll
@@ -6,32 +6,49 @@
 ; CHECK: Write: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> MemRef_sum[0] : i0 >= 0 and i0 <= 100 }
 ; CHECK: Schedule: { Stmt_for_cond[i0] -> scattering[0, i0, 0]; [Stmt_for_cond[i0] -> MemRef_sum[0]] -> scattering[0, i0, 0] : i0 <= 100 and i0 >= 0 }
 ; CHECK: Wrapped Dependences:
-; CHECK:         RAW dependences:
-; CHECK:                 { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 >= 0 and i0 <= 99 }
-; CHECK:         WAR dependences:
-; CHECK:                 {  }
-; CHECK:         WAW dependences:
-; CHECK:                 { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 >= 0 and i0 <= 99 }
-; CHECK:         Reduction dependences:
-; CHECK:                 n/a
+; CHECK: RAW dependences:
+; CHECK:   { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 >= 0 and i0 <= 99 }
+; CHECK: WAR dependences:
+; CHECK:   {  }
+; CHECK: WAW dependences:
+; CHECK:   { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 >= 0 and i0 <= 99 }
+; CHECK: Reduction dependences:
+; CHECK:   n/a
+; CHECK: Final Wrapped Dependences:
+; CHECK: RAW dependences:
+; CHECK:   {  }
+; CHECK: WAR dependences:
+; CHECK:   {  }
+; CHECK: WAW dependences:
+; CHECK:   {  }
+; CHECK: Reduction dependences:
+; CHECK:   { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 <= 99 and i0 >= 0 }
 ; CHECK: Zipped Dependences:
-; CHECK:         RAW dependences:
-; CHECK:                 { [Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0]] -> [MemRef_sum[0] -> MemRef_sum[0]] : i0 >= 0 and i0 <= 99 }
-; CHECK:         WAR dependences:
-; CHECK:                 {  }
-; CHECK:         WAW dependences:
-; CHECK:                 { [Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0]] -> [MemRef_sum[0] -> MemRef_sum[0]] : i0 >= 0 and i0 <= 99 }
-; CHECK:         Reduction dependences:
-; CHECK:                 n/a
+; CHECK: RAW dependences:
+; CHECK:   {  }
+; CHECK: WAR dependences:
+; CHECK:   {  }
+; CHECK: WAW dependences:
+; CHECK:   {  }
+; CHECK: Reduction dependences:
+; CHECK:   { [Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0]] -> [MemRef_sum[0] -> MemRef_sum[0]] : i0 <= 99 and i0 >= 0 }
 ; CHECK: Unwrapped Dependences:
-; CHECK:         RAW dependences:
-; CHECK:                 { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : i0 >= 0 and i0 <= 99 }
-; CHECK:         WAR dependences:
-; CHECK:                 {  }
-; CHECK:         WAW dependences:
-; CHECK:                 { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : i0 >= 0 and i0 <= 99 }
-; CHECK:         Reduction dependences:
-; CHECK:                 n/a
+; CHECK: RAW dependences:
+; CHECK:   {  }
+; CHECK: WAR dependences:
+; CHECK:   {  }
+; CHECK: WAW dependences:
+; CHECK:   {  }
+; CHECK: Reduction dependences:
+; CHECK:   { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : i0 <= 99 and i0 >= 0 }
+; CHECK: RAW dependences:
+; CHECK:   {  }
+; CHECK: WAR dependences:
+; CHECK:   {  }
+; CHECK: WAW dependences:
+; CHECK:   {  }
+; CHECK: Reduction dependences:
+; CHECK:   { Stmt_for_cond[i0] -> Stmt_for_cond[1 + i0] : i0 <= 99 and i0 >= 0 }
 ;
 ; void f(int* sum) {
 ;   for (int i = 0; i <= 100; i++)