From 27c010a22e5a856794adea22895325e0b6963e74 Mon Sep 17 00:00:00 2001
From: Michael Kruse <llvm@meinersbur.de>
Date: Tue, 8 Aug 2017 11:27:12 +0000
Subject: [PATCH] [DeLICM] Properly handle PHI writes becoming empty partial
 writes.

It is possible that partial writes are empty (write is never executed).
In this case, when in PHINode's incoming edge is never taken such that
the incoming write becomes an empty partial write, if enabled. The
issue is that when converting the union_map to an map, it's space
cannot be derived from the union_map itself. Rather, we need to
determine its space independently.

This fixes test-suite's MultiSource/Benchmarks/ASC_Sequoia/CrystalMk.

llvm-svn: 310348
---
 polly/lib/Transform/DeLICM.cpp                     | 11 ++-
 .../DeLICM/reduction_looprotate_alwaystaken.ll     | 80 ++++++++++++++++++++++
 2 files changed, 88 insertions(+), 3 deletions(-)
 create mode 100644 polly/test/DeLICM/reduction_looprotate_alwaystaken.ll

diff --git a/polly/lib/Transform/DeLICM.cpp b/polly/lib/Transform/DeLICM.cpp
index 4747a7b..8a47d21 100644
--- a/polly/lib/Transform/DeLICM.cpp
+++ b/polly/lib/Transform/DeLICM.cpp
@@ -1048,6 +1048,9 @@ private:
   void mapPHI(const ScopArrayInfo *SAI, isl::map ReadTarget,
               isl::union_map WriteTarget, isl::map Lifetime,
               Knowledge Proposed) {
+    // { Element[] }
+    isl::space ElementSpace = ReadTarget.get_space().range();
+
     // Redirect the PHI incoming writes.
     for (auto *MA : S->getPHIIncomings(SAI)) {
       // { DomainWrite[] }
@@ -1055,11 +1058,13 @@ private:
 
       // { DomainWrite[] -> Element[] }
       auto NewAccRel = give(isl_union_map_intersect_domain(
-          WriteTarget.copy(), isl_union_set_from_set(Domain.take())));
+          WriteTarget.copy(), isl_union_set_from_set(Domain.copy())));
       simplify(NewAccRel);
 
-      assert(isl_union_map_n_map(NewAccRel.keep()) == 1);
-      MA->setNewAccessRelation(isl::map::from_union_map(NewAccRel));
+      isl::space NewAccRelSpace =
+          Domain.get_space().map_from_domain_and_range(ElementSpace);
+      isl::map NewAccRelMap = singleton(NewAccRel, NewAccRelSpace);
+      MA->setNewAccessRelation(NewAccRelMap);
     }
 
     // Redirect the PHI read.
diff --git a/polly/test/DeLICM/reduction_looprotate_alwaystaken.ll b/polly/test/DeLICM/reduction_looprotate_alwaystaken.ll
new file mode 100644
index 0000000..fbb20e1
--- /dev/null
+++ b/polly/test/DeLICM/reduction_looprotate_alwaystaken.ll
@@ -0,0 +1,80 @@
+; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-overapproximate-writes=true -polly-delicm-compute-known=true -polly-delicm -analyze < %s | FileCheck %s
+;
+; Verify that delicm can cope with never taken PHI incoming edges.
+; The edge %body -> %body_phi is never taken, hence the access MemoryKind::PHI,
+; WRITE in %body for %phi is never used.
+; When mapping %phi, the write's access relation is the empty set.
+;
+;    void func(double *A) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        for (int i = 0; i < 4; i += 1) { /* reduction */
+;          double phi = 21.0;
+;          if (j < 10) // Tautology, since 0<=j<2
+;            phi = 42.0;
+;        }
+;        A[j] = phi;
+;      }
+;    }
+;
+define void @func(double* noalias nonnull %A, double* noalias nonnull %dummy) {
+entry:
+  br label %outer.preheader
+
+outer.preheader:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %outer.preheader], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.preheader, label %outer.exit
+
+
+    reduction.preheader:
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      br label %reduction.for
+
+    reduction.for:
+      %i = phi i32 [0, %reduction.preheader], [%i.inc, %reduction.inc]
+      br label %body
+
+
+
+        body:
+          %cond = icmp slt i32 %j, 10
+          br i1 %cond, label %alwaystaken, label %body_phi
+
+        alwaystaken:
+          store double 0.0, double* %dummy
+          br label %body_phi
+
+        body_phi:
+          %phi = phi double [21.0, %body], [42.0, %alwaystaken]
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      %i.cmp = icmp slt i32 %i.inc, 4
+      br i1 %i.cmp, label %reduction.for, label %reduction.exit
+
+    reduction.exit:
+      store double %phi, double* %A_idx
+      br label %outer.inc
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK: Statistics {
+; CHECK:     PHI scalars mapped:    1
+; CHECK: }
-- 
2.7.4