[Simplify] Remove identical scalar writes.

After DeLICM, it is possible to have two writes of the same value to
the same location in the same statement when it determined that those
writes do not conflict (write the same value).

Teach -polly-simplify to remove one of the writes. It interferes with
the pattern matching of matrix-multiplication kernels and also seem
to not be optimized away by LLVM.

The algorthm is simple, has O(n^2) behaviour (n = max number of
MemoryAccesses in a statement) and only matches the most obvious cases,
but seem to be enough to pattern-match Boost ublas gemm.

Not handled cases include:
- StoreInst instructions (a.k.a. explicit writes), since the value might
  be loaded or overwritten between the two stores.
- PHINode, especially LCSSA, when the PHI value matches with on other's.
- Partial writes (in preparation)

llvm-svn: 302805

7 files changed, 428 insertions, 1 deletions

diff --git a/polly/lib/Transform/Simplify.cpp b/polly/lib/Transform/Simplify.cpp
index 11d7b2f8dae..7a9df5cc4ca 100644
--- a/polly/lib/Transform/Simplify.cpp
+++ b/polly/lib/Transform/Simplify.cpp
@@ -31,15 +31,46 @@ STATISTIC(PairUnequalAccRels, "Number of Load-Store pairs NOT removed because "
                               "of different access relations");
 STATISTIC(InBetweenStore, "Number of Load-Store pairs NOT removed because "
                           "there is another store between them");
+STATISTIC(TotalIdenticalWritesRemoved,
+          "Number of double writes removed in any SCoP");
 STATISTIC(TotalRedundantWritesRemoved,
           "Number of writes of same value removed in any SCoP");
 STATISTIC(TotalStmtsRemoved, "Number of statements removed in any SCoP");
 
+/// Find the llvm::Value that is written by a MemoryAccess. Return nullptr if
+/// there is no such unique value.
+static Value *getWrittenScalar(MemoryAccess *WA) {
+  assert(WA->isWrite());
+
+  if (WA->isOriginalAnyPHIKind()) {
+    Value *Result = nullptr;
+    for (auto Incoming : WA->getIncoming()) {
+      assert(Incoming.second);
+
+      if (!Result) {
+        Result = Incoming.second;
+        continue;
+      }
+
+      if (Result == Incoming.second)
+        continue;
+
+      return nullptr;
+    }
+    return Result;
+  }
+
+  return WA->getAccessInstruction();
+}
+
 class Simplify : public ScopPass {
 private:
   /// The last/current SCoP that is/has been processed.
   Scop *S;
 
+  /// Number of double writes removed from this SCoP.
+  int IdenticalWritesRemoved = 0;
+
   /// Number of redundant writes removed from this SCoP.
   int RedundantWritesRemoved = 0;
 
@@ -48,7 +79,8 @@ private:
 
   /// Return whether at least one simplification has been applied.
   bool isModified() const {
-    return RedundantWritesRemoved > 0 || StmtsRemoved > 0;
+    return IdenticalWritesRemoved > 0 || RedundantWritesRemoved > 0 ||
+           StmtsRemoved > 0;
   }
 
   MemoryAccess *getReadAccessForValue(ScopStmt *Stmt, llvm::Value *Val) {
@@ -122,6 +154,75 @@ private:
     return nullptr;
   }
 
+  /// If there are two writes in the same statement that write the same value to
+  /// the same location, remove one of them.
+  ///
+  /// This currently handles only implicit writes (writes which logically occur
+  /// at the end of a statement when all StoreInst and LoadInst have been
+  /// executed), to avoid interference with other memory accesses.
+  ///
+  /// Two implicit writes have no defined order. It can be produced by DeLICM
+  /// when it determined that both write the same value.
+  void removeIdenticalWrites() {
+    for (auto &Stmt : *S) {
+      // Delay actual removal to not invalidate iterators.
+      SmallPtrSet<MemoryAccess *, 4> StoresToRemove;
+
+      auto Domain = give(Stmt.getDomain());
+
+      // TODO: This has quadratic runtime. Accesses could be grouped by
+      // getAccessValue() to avoid.
+      for (auto *WA1 : Stmt) {
+        if (!WA1->isMustWrite())
+          continue;
+        if (!WA1->isOriginalScalarKind())
+          continue;
+        if (StoresToRemove.count(WA1))
+          continue;
+
+        auto *WrittenScalar1 = getWrittenScalar(WA1);
+        if (!WrittenScalar1)
+          continue;
+
+        for (auto *WA2 : Stmt) {
+          if (WA1 == WA2)
+            continue;
+          if (!WA2->isMustWrite())
+            continue;
+          if (!WA2->isOriginalScalarKind())
+            continue;
+          if (StoresToRemove.count(WA2))
+            continue;
+
+          auto *WrittenScalar2 = getWrittenScalar(WA2);
+          if (WrittenScalar1 != WrittenScalar2)
+            continue;
+
+          auto AccRel1 = give(isl_map_intersect_domain(WA1->getAccessRelation(),
+                                                       Domain.copy()));
+          auto AccRel2 = give(isl_map_intersect_domain(WA2->getAccessRelation(),
+                                                       Domain.copy()));
+          if (isl_map_is_equal(AccRel1.keep(), AccRel2.keep()) != isl_bool_true)
+            continue;
+
+          DEBUG(dbgs() << "Remove identical writes:\n");
+          DEBUG(dbgs() << "  First write  (kept)   : " << WA1 << '\n');
+          DEBUG(dbgs() << "  Second write (removed): " << WA2 << '\n');
+          StoresToRemove.insert(WA2);
+        }
+      }
+
+      for (auto *WA : StoresToRemove) {
+        auto *Stmt = WA->getStatement();
+
+        Stmt->removeSingleMemoryAccess(WA);
+
+        IdenticalWritesRemoved++;
+        TotalIdenticalWritesRemoved++;
+      }
+    }
+  }
+
   /// Remove writes that just write the same value already stored in the
   /// element.
   void removeRedundantWrites() {
@@ -211,6 +312,8 @@ private:
   /// Print simplification statistics to @p OS.
   void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const {
     OS.indent(Indent) << "Statistics {\n";
+    OS.indent(Indent + 4) << "Identical writes removed: "
+                          << IdenticalWritesRemoved << '\n';
     OS.indent(Indent + 4) << "Redundant writes removed: "
                           << RedundantWritesRemoved << "\n";
     OS.indent(Indent + 4) << "Stmts removed: " << StmtsRemoved << "\n";
@@ -245,6 +348,9 @@ public:
     this->S = &S;
     ScopsProcessed++;
 
+    DEBUG(dbgs() << "Removing identical writes...\n");
+    removeIdenticalWrites();
+
     DEBUG(dbgs() << "Removing redundant writes...\n");
     removeRedundantWrites();
 
diff --git a/polly/test/Simplify/identical.ll b/polly/test/Simplify/identical.ll
new file mode 100644
index 00000000000..df4a4cdf9bf
--- /dev/null
+++ b/polly/test/Simplify/identical.ll
@@ -0,0 +1,56 @@
+; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=transformed -polly-simplify -analyze < %s | FileCheck -match-full-lines %s
+;
+; Remove identical writes
+; (two stores in the same statement that write the same value to the same
+; destination)
+;
+; for (int j = 0; j < n; j += 1) {
+; body:
+;   val = 21.0 + 21.0;
+;   A[1] = val;
+;   A[1] = val;
+;
+; user:
+;   A[0] = A[1];
+; }
+;
+define void @identical(i32 %n, double* noalias nonnull %A) {
+entry:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %body, label %exit
+
+    body:
+      %val = fadd double 21.0, 21.0
+      br label %user
+
+    user:
+      %phi = phi double [%val, %body]
+      %add = fadd double %val, %phi
+      store double %add, double* %A
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK: Statistics {
+; CHECK:     Identical writes removed: 1
+; CHECK: }
+
+; CHECK:      Stmt_body
+; CHECK-NEXT:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:            [n] -> { Stmt_body[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:       new: [n] -> { Stmt_body[i0] -> MemRef_A[1] };
+; CHECK-NEXT: Stmt_user
diff --git a/polly/test/Simplify/identical_3phi.ll b/polly/test/Simplify/identical_3phi.ll
new file mode 100644
index 00000000000..3a7a61dee8d
--- /dev/null
+++ b/polly/test/Simplify/identical_3phi.ll
@@ -0,0 +1,61 @@
+; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=transformed -polly-simplify -analyze < %s | FileCheck -match-full-lines %s
+;
+; Remove identical writes
+; (two stores in the same statement that write the same value to the same
+; destination)
+;
+; for (int j = 0; j < n; j += 1) {
+; body:
+;   val = 21.0 + 21.0;
+;   A[1] = val;
+;   A[1] = val;
+;   A[1] = val;
+;
+; user:
+;   A[0] = A[1];
+; }
+;
+define void @identical_3phi(i32 %n, double* noalias nonnull %A) {
+entry:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %body, label %exit
+
+    body:
+      %val = fadd double 21.0, 21.0
+      br label %user
+
+    user:
+      %phi1 = phi double [%val, %body]
+      %phi2 = phi double [%val, %body]
+      %phi3 = phi double [%val, %body]
+      %add1 = fadd double %phi1, %phi2
+      %add2 = fadd double %add1, %phi3
+      store double %add2, double* %A
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+
+; CHECK: Statistics {
+; CHECK:     Identical writes removed: 2
+; CHECK: }
+
+; CHECK:      Stmt_body
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [n] -> { Stmt_body[i0] -> MemRef_phi1__phi[] };
+; CHECK-NEXT:        new: [n] -> { Stmt_body[i0] -> MemRef_A[1] };
+; CHECK-NEXT: Stmt_user
diff --git a/polly/test/Simplify/identical_3phi___%for---%return.jscop b/polly/test/Simplify/identical_3phi___%for---%return.jscop
new file mode 100644
index 00000000000..af26b0ad698
--- /dev/null
+++ b/polly/test/Simplify/identical_3phi___%for---%return.jscop
@@ -0,0 +1,55 @@
+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "[n] -> {  : -2147483648 <= n <= 2147483647 }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[i0] -> MemRef_phi1__phi[] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[i0] -> MemRef_phi2__phi[] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[i0] -> MemRef_phi3__phi[] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_body",
+         "schedule" : "[n] -> { Stmt_body[i0] -> [i0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_phi1__phi[] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_phi2__phi[] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_phi3__phi[] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[0] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_user[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_user",
+         "schedule" : "[n] -> { Stmt_user[i0] -> [i0, 1] }"
+      }
+   ]
+}
diff --git a/polly/test/Simplify/identical_3phi___%for---%return.jscop.transformed b/polly/test/Simplify/identical_3phi___%for---%return.jscop.transformed
new file mode 100644
index 00000000000..ddd927958a1
--- /dev/null
+++ b/polly/test/Simplify/identical_3phi___%for---%return.jscop.transformed
@@ -0,0 +1,55 @@
+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "[n] -> {  : -2147483648 <= n <= 2147483647 }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[i0] -> MemRef_A[1] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[i0] -> MemRef_A[1] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[i0] -> MemRef_A[1] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_body",
+         "schedule" : "[n] -> { Stmt_body[i0] -> [i0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[1] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[0] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_user[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_user",
+         "schedule" : "[n] -> { Stmt_user[i0] -> [i0, 1] }"
+      }
+   ]
+}
diff --git a/polly/test/Simplify/identical___%for---%return.jscop b/polly/test/Simplify/identical___%for---%return.jscop
new file mode 100644
index 00000000000..248afa83478
--- /dev/null
+++ b/polly/test/Simplify/identical___%for---%return.jscop
@@ -0,0 +1,47 @@
+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "[n] -> {  : -2147483648 <= n <= 2147483647 }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[i0] -> MemRef_phi__phi[] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[i0] -> MemRef_val[] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_body",
+         "schedule" : "[n] -> { Stmt_body[i0] -> [i0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_phi__phi[] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_val[] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[0] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_user[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_user",
+         "schedule" : "[n] -> { Stmt_user[i0] -> [i0, 1] }"
+      }
+   ]
+}
diff --git a/polly/test/Simplify/identical___%for---%return.jscop.transformed b/polly/test/Simplify/identical___%for---%return.jscop.transformed
new file mode 100644
index 00000000000..25beb614584
--- /dev/null
+++ b/polly/test/Simplify/identical___%for---%return.jscop.transformed
@@ -0,0 +1,47 @@
+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "[n] -> {  : -2147483648 <= n <= 2147483647 }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[i0] -> MemRef_A[1] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[i0] -> MemRef_A[1] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_body",
+         "schedule" : "[n] -> { Stmt_body[i0] -> [i0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[1] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[1] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[0] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_user[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_user",
+         "schedule" : "[n] -> { Stmt_user[i0] -> [i0, 1] }"
+      }
+   ]
+}