[Polly][Simplify] Remove identical write removal. NFC.

[Meinersbur]

Summary

Removal of overwritten writes currently encompasses all the cases of the identical write removal.

Identical write removal might still be superior when partial writes (in preparation) do not share exactly the same domain, but can be merged into a single write. However, this could be implemented with overwritten write removal as well.

The identical write removal algorithm could be extended to handle all cases of overwritten removal, but with O(n^3) performance characteristic.

There is an observable behavioral change in that the last, instead of the first, MemoryAccess is kept. This should not affect the generated code, however.

[grosser]

Hi Michael,

it is not fully clear what this patch is about. I assume this is a WIP alternative to https://reviews.llvm.org/D33142. My current understanding is that https://reviews.llvm.org/D33142 is stable and this is still very much work in progress (also the patch in this submission seems broken). Not sure what you had in mind, but it seems we should go for https://reviews.llvm.org/D33142 and keep this discussing until until we figure out that they work well. Indeed, Indeed, I am worried about the O(N^3) complexity.

overwritten.ll

3 ↗

(On Diff #98809)

Why is there a patch in this file?

[Meinersbur]

• Rebase
• Remove patch file
• Remove double defintions

[Meinersbur]

In D33143#754066, @grosser wrote:

Hi Michael,

it is not fully clear what this patch is about.

It only removes the "identical write removal" algorithm. "overwritten writes removal" does the same thing (and more).

[grosser]

Ah, so this is just a cleanup. LGTM them.

polly/trunk/lib/Transform/Simplify.cpp

 
 STATISTIC(ScopsProcessed, "Number of SCoPs processed");
 STATISTIC(ScopsModified, "Number of SCoPs simplified");
 
 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(TotalOverwritesRemoved, "Number of removed overwritten writes");
 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) {
return concat<MemoryAccess *>(make_filter_range(AllRange, isImplicitRead),
                                 make_filter_range(AllRange, isImplicitWrite));
 }
 
 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 writes that are overwritten anyway.
   int OverwritesRemoved = 0;
 
   /// Number of redundant writes removed from this SCoP.
   int RedundantWritesRemoved = 0;
 
   /// Number of unnecessary statements removed from the SCoP.
   int StmtsRemoved = 0;
 
   /// Return whether at least one simplification has been applied.
   bool isModified() const {
-    return IdenticalWritesRemoved > 0 || OverwritesRemoved > 0 ||
-           RedundantWritesRemoved > 0 || StmtsRemoved > 0;
+    return OverwritesRemoved > 0 || RedundantWritesRemoved > 0 ||
+           StmtsRemoved > 0;
   }
 
   MemoryAccess *getReadAccessForValue(ScopStmt *Stmt, llvm::Value *Val) {
     if (!isa<Instruction>(Val))
       return nullptr;
 
     for (auto *MA : *Stmt) {
       if (!MA->isRead())
for (auto *Acc : *Stmt) {
       if (isl_map_is_empty(CommonElt.keep()) != isl_bool_true)
         return Acc;
     }
     assert(Stmt->isRegionStmt() &&
            "To must be encountered in block statements");
     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 are overwritten unconditionally later in the same
   /// statement.
   ///
   /// There must be no read of the same value between the write (that is to be
   /// removed) and the overwrite.
   void removeOverwrites() {
     for (auto &Stmt : *S) {
       auto Domain = give(Stmt.getDomain());
void removeUnnecessayStmts() {
     DEBUG(dbgs() << "Removed " << StmtsRemoved << " (of " << NumStmtsBefore
                  << ") statements\n");
     TotalStmtsRemoved += StmtsRemoved;
   }
 
   /// 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) << "Overwrites removed: " << OverwritesRemoved
                           << '\n';
     OS.indent(Indent + 4) << "Redundant writes removed: "
                           << RedundantWritesRemoved << "\n";
     OS.indent(Indent + 4) << "Stmts removed: " << StmtsRemoved << "\n";
     OS.indent(Indent) << "}\n";
   }
 
public:
   virtual bool runOnScop(Scop &S) override {
     // Reset statistics of last processed SCoP.
     releaseMemory();
 
     // Prepare processing of this SCoP.
     this->S = &S;
     ScopsProcessed++;
 
-    DEBUG(dbgs() << "Removing identical writes...\n");
-    removeIdenticalWrites();
-
     DEBUG(dbgs() << "Removing overwrites...\n");
     removeOverwrites();
 
     DEBUG(dbgs() << "Removing redundant writes...\n");
     removeRedundantWrites();
 
     DEBUG(dbgs() << "Removing statements without side effects...\n");
     removeUnnecessayStmts();
if (!isModified()) {
       return;
     }
     printAccesses(OS);
   }
 
   virtual void releaseMemory() override {
     S = nullptr;
 
-    IdenticalWritesRemoved = 0;
     OverwritesRemoved = 0;
     RedundantWritesRemoved = 0;
     StmtsRemoved = 0;
   }
 };
 
 char Simplify::ID;
 } // anonymous namespace
 
 Pass *polly::createSimplifyPass() { return new Simplify(); }
 
 INITIALIZE_PASS_BEGIN(Simplify, "polly-simplify", "Polly - Simplify", false,
                       false)
 INITIALIZE_PASS_END(Simplify, "polly-simplify", "Polly - Simplify", false,
                     false)

polly/trunk/test/Simplify/identical.ll

-; 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

polly/trunk/test/Simplify/identical_3phi.ll

-; 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

polly/trunk/test/Simplify/identical_3phi___%for---%return.jscop

-{
-   "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] }"
-      }
-   ]
-}

polly/trunk/test/Simplify/identical_3phi___%for---%return.jscop.transformed

-{
-   "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] }"
-      }
-   ]
-}

polly/trunk/test/Simplify/identical___%for---%return.jscop

-{
-   "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] }"
-      }
-   ]
-}

polly/trunk/test/Simplify/identical___%for---%return.jscop.transformed

-{
-   "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] }"
-      }
-   ]
-}

polly/trunk/test/Simplify/overwritten_3phi.ll

+; 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 @overwritten_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:     Overwrites removed: 2
+; CHECK: }
+
+; CHECK:      Stmt_body
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             [n] -> { Stmt_body[i0] -> MemRef_phi3__phi[] };
+; CHECK-NEXT:        new: [n] -> { Stmt_body[i0] -> MemRef_A[1] };
+; CHECK-NEXT: Stmt_user

polly/trunk/test/Simplify/overwritten_3phi___%for---%return.jscop

+{
+   "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] }"
+      }
+   ]
+}

polly/trunk/test/Simplify/overwritten_3phi___%for---%return.jscop.transformed

+{
+   "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] }"
+      }
+   ]
+}

polly/trunk/test/Simplify/overwritten_scalar.ll

+; 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 @overwritten_scalar(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:     Overwrites removed: 1
+; CHECK: }
+
+; CHECK:      Stmt_body
+; CHECK-NEXT:     MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:            [n] -> { Stmt_body[i0] ->  MemRef_val[] };
+; CHECK-NEXT:       new: [n] -> { Stmt_body[i0] -> MemRef_A[1] };
+; CHECK-NEXT: Stmt_user

polly/trunk/test/Simplify/overwritten_scalar___%for---%return.jscop

+{
+   "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] }"
+      }
+   ]
+}

polly/trunk/test/Simplify/overwritten_scalar___%for---%return.jscop.transformed

+{
+   "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] }"
+      }
+   ]
+}