DeadCodeElimination: Fix liveout computation

We move back to a simple approach where the liveout is the last must-write
statement for a data-location plus all may-write statements. The previous
approach did not work out. We would have to consider per-data-access
dependences, instead of per-statement dependences to correct it. As this adds
complexity and it seems we would not gain anything over the simpler approach
that we implement in this commit, I moved us back to the old approach of
computing the liveout, but enhanced it to also add may-write accesses.

We also fix the test case and explain why we can not perform dead code
elimination in this case.

llvm-svn: 212925

2 files changed, 32 insertions, 17 deletions

diff --git a/polly/lib/Transform/DeadCodeElimination.cpp b/polly/lib/Transform/DeadCodeElimination.cpp
index 45e5a61adee..c5cd57913da 100644
--- a/polly/lib/Transform/DeadCodeElimination.cpp
+++ b/polly/lib/Transform/DeadCodeElimination.cpp
@@ -78,21 +78,29 @@ private:
 
 char DeadCodeElim::ID = 0;
 
-// To compute the live outs, we first assume all must and may-writes are exposed
-// and then subtract the set of statements that are definitely overwritten.
+// To compute the live outs, we compute for the data-locations that are
+// must-written to the last statement that touches these locations. On top of
+// this we add all statements that perform may-write accesses.
+//
+// We could be more precise by removing may-write accesses for which we know
+// that they are overwritten by a must-write after. However, at the moment the
+// only may-writes we introduce access the full (unbounded) array, such that
+// bounded write accesses can not overwrite all of the data-locations. As
+// this means may-writes are in the current situation always live, there is
+// no point in trying to remove them from the live-out set.
 isl_union_set *DeadCodeElim::getLiveOut(Scop &S) {
-  isl_union_map *Kills = S.getMustWrites();
-  isl_union_map *Empty = isl_union_map_empty(S.getParamSpace());
-
-  isl_union_map *Covering;
-  isl_union_map *Writes = S.getWrites();
-  isl_union_map_compute_flow(Kills, Empty, isl_union_map_copy(Writes),
-                             S.getSchedule(), NULL, &Covering, NULL, NULL);
-
-  isl_union_map *Exposed = Writes;
-  Exposed =
-      isl_union_map_subtract_domain(Exposed, isl_union_map_domain(Covering));
-  return isl_union_map_domain(Exposed);
+  isl_union_map *Schedule = S.getSchedule();
+  isl_union_map *WriteIterations = isl_union_map_reverse(S.getMustWrites());
+  isl_union_map *WriteTimes =
+      isl_union_map_apply_range(WriteIterations, isl_union_map_copy(Schedule));
+
+  isl_union_map *LastWriteTimes = isl_union_map_lexmax(WriteTimes);
+  isl_union_map *LastWriteIterations = isl_union_map_apply_range(
+      LastWriteTimes, isl_union_map_reverse(Schedule));
+
+  isl_union_set *Live = isl_union_map_range(LastWriteIterations);
+  Live = isl_union_set_union(Live, isl_union_map_domain(S.getMayWrites()));
+  return isl_union_set_coalesce(Live);
 }
 
 /// Performs polyhedral dead iteration elimination by:
diff --git a/polly/test/DeadCodeElimination/non-affine-affine-mix.ll b/polly/test/DeadCodeElimination/non-affine-affine-mix.ll
index 1537c39dbcd..24b04a14084 100644
--- a/polly/test/DeadCodeElimination/non-affine-affine-mix.ll
+++ b/polly/test/DeadCodeElimination/non-affine-affine-mix.ll
@@ -7,9 +7,13 @@
 ; S2:    A[i2] = i;
 ;    }
 
-; CHECK-NOT: Stmt_S1
+; We unfortunately do need to execute all iterations of S1, as we do not know
+; the size of A and as a result S1 may write for example to A[1024], which
+; is not overwritten by S2.
 
 ; CHECK: for (int c1 = 0; c1 <= 1023; c1 += 1)
+; CHECK:   Stmt_S1(c1);
+; CHECK: for (int c1 = 0; c1 <= 1023; c1 += 1)
 ; CHECK:   Stmt_S2(c1);
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64"
@@ -21,7 +25,7 @@ entry:
 for.cond:
   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
   %exitcond = icmp ne i32 %i.0, 1024
-  br i1 %exitcond, label %S1, label %for.cond.2
+  br i1 %exitcond, label %S1, label %next
 
 S1:
   %rem = srem i32 %i.0, 2
@@ -33,8 +37,11 @@ for.inc:
   %inc = add nsw i32 %i.0, 1
   br label %for.cond
 
+next:
+ br label %for.cond.2
+
 for.cond.2:
-  %i.2 = phi i32 [ 0, %for.cond ], [ %inc.2, %for.inc.2 ]
+  %i.2 = phi i32 [ 0, %next ], [ %inc.2, %for.inc.2 ]
   %exitcond.2 = icmp ne i32 %i.2, 1024
   br i1 %exitcond.2, label %S2, label %for.end