[Polly][Simplify] Remove writes that are overwritten.

[Meinersbur]

Summary

Remove memory writes that are overwritten by later writes. This works for StoreInsts:

store double 21.0, double* %A
store double 42.0, double* %A

, scalar writes at the end of a statement and mixes of these.

Multiple writes can be the result of DeLICM, which might map multiple writes to the same location when it knows that these do no conflict (for instance because they write the same value). Such writes interfere with pattern-matched optimization such as gemm and may not get removed by other LLVM passes after code generation.

[grosser]

L:GTM

lib/Transform/Simplify.cpp

87 ↗

(On Diff #98807)

Formatting is broken.

269 ↗

(On Diff #98807)

There

282 ↗

(On Diff #98807)

overwrite

285 ↗

(On Diff #98807)

"a region statement" or "region statements"

[grosser]

Btw, this improves the gemm performance nicely from 4s to 1.3 seconds, which matches the results we obtain without pattern matching based opts.

polly/trunk/lib/Transform/Simplify.cpp

 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) {
   assert(WA->isWrite());
for (auto Incoming : WA->getIncoming()) {
       return nullptr;
     }
     return Result;
   }
 
   return WA->getAccessInstruction();
 }
 
+static bool isImplicitRead(MemoryAccess *MA) {
+  return MA->isRead() && MA->isOriginalScalarKind();
+}
+
+static bool isExplicitAccess(MemoryAccess *MA) {
+  return MA->isOriginalArrayKind();
+}
+
+static bool isImplicitWrite(MemoryAccess *MA) {
+  return MA->isWrite() && MA->isOriginalScalarKind();
+}
+
+/// Return an iterator range that iterates over MemoryAccesses in the order in
+/// which they are executed.
+///
+/// The order is:
+/// - Implicit reads (BlockGenerator::generateScalarLoads)
+/// - Explicit reads and writes (BlockGenerator::generateArrayLoad,
+///   BlockGenerator::generateArrayStore)
+///   - In block statements, the accesses are in order in which their
+///     instructions are executed.
+///   - In region statements, that order of execution is not predictable at
+///     compile-time.
+/// - Implicit writes (BlockGenerator::generateScalarStores)
+///   The order in which implicit writes are executed relative to each other is
+///   undefined.
+static auto accessesInOrder(ScopStmt *Stmt) -> decltype(concat<MemoryAccess *>(
+    make_filter_range(make_range(Stmt->begin(), Stmt->end()), isImplicitRead),
+    make_filter_range(make_range(Stmt->begin(), Stmt->end()), isExplicitAccess),
+    make_filter_range(make_range(Stmt->begin(), Stmt->end()),
+                      isImplicitWrite))) {
+  auto AllRange = make_range(Stmt->begin(), Stmt->end());
+  return concat<MemoryAccess *>(make_filter_range(AllRange, isImplicitRead),
+                                make_filter_range(AllRange, isExplicitAccess),
+                                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 || RedundantWritesRemoved > 0 ||
-           StmtsRemoved > 0;
+    return IdenticalWritesRemoved > 0 || 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 &Stmt : *S) {
         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());
+      isl::union_map WillBeOverwritten =
+          isl::union_map::empty(give(S->getParamSpace()));
+
+      auto AccRange = accessesInOrder(&Stmt);
+      SmallVector<MemoryAccess *, 32> Accesses{AccRange.begin(),
+                                               AccRange.end()};
+
+      // Iterate in reverse order, so the overwrite comes before the write that
+      // is to be removed.
+      for (auto *MA : reverse(Accesses)) {
+
+        // In region statements, the explicit accesses can be in blocks that are
+        // can be executed in any order. We therefore process only the implicit
+        // writes and stop after that.
+        if (Stmt.isRegionStmt() && isExplicitAccess(MA))
+          break;
+
+        auto AccRel = give(MA->getAccessRelation());
+        AccRel = AccRel.intersect_domain(Domain);
+        AccRel = AccRel.intersect_params(give(S->getContext()));
+
+        // If a value is read in-between, do not consider it as overwritten.
+        if (MA->isRead()) {
+          WillBeOverwritten = WillBeOverwritten.subtract(AccRel);
+          continue;
+        }
+
+        // If all of a write's elements are overwritten, remove it.
+        isl::union_map AccRelUnion = AccRel;
+        if (isl_union_map_is_subset(AccRelUnion.keep(),
+                                    WillBeOverwritten.keep()) ==
+            isl_bool_true) {
+          DEBUG(dbgs() << "Removing " << MA
+                       << " which will be overwritten anyway\n");
+
+          Stmt.removeSingleMemoryAccess(MA);
+          OverwritesRemoved++;
+          TotalOverwritesRemoved++;
+        }
+
+        // Unconditional writes overwrite other values.
+        if (MA->isMustWrite())
+          WillBeOverwritten = WillBeOverwritten.add_map(AccRel);
+      }
+    }
+  }
+
   /// Remove writes that just write the same value already stored in the
   /// element.
   void removeRedundantWrites() {
     // Delay actual removal to not invalidate iterators.
     SmallVector<MemoryAccess *, 8> StoresToRemove;
 
     for (auto &Stmt : *S) {
       for (auto *WA : Stmt) {
void removeUnnecessayStmts() {
     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";
   }
 
   /// Print the current state of all MemoryAccesses to @p OS.
   void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const {
virtual bool runOnScop(Scop &S) override {
 
     // 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())
       ScopsModified++;
virtual void printScop(raw_ostream &OS, Scop &S) const override {
     }
     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/overwritten.ll

+; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck -match-full-lines %s 
+;
+; Remove a store that is overwritten by another store in the same statement.
+;
+; for (int j = 0; j < n; j += 1) {
+;   A[0] = 21.0;
+;   A[0] = 42.0;
+; }
+;
+define void @overwritten(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:
+      store double 21.0, double* %A
+      store double 42.0, 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:      After accesses {
+; CHECK-NEXT:     Stmt_body
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n] -> { Stmt_body[i0] -> MemRef_A[0] };
+; CHECK-NEXT: }

polly/trunk/test/Simplify/overwritten_3store.ll

+; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck -match-full-lines %s 
+;
+; Remove a store that is overwritten by another store in the same statement.
+; Check that even multiple stores are removed.
+;
+; for (int j = 0; j < n; j += 1) {
+;   A[0] = 10.5;
+;   A[0] = 21.0;
+;   A[0] = 42.0;
+; }
+;
+define void @overwritten_3store(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:
+      store double 10.5, double* %A
+      store double 21.0, double* %A
+      store double 42.0, 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:      After accesses {
+; CHECK-NEXT:     Stmt_body
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 [n] -> { Stmt_body[i0] -> MemRef_A[0] };
+; CHECK-NEXT: }

polly/trunk/test/Simplify/overwritten_implicit_and_explicit.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 a store that is overwritten by another store in the same statement.
+; Check that this works even if one of the writes is a scalar MemoryKind.
+;
+; for (int j = 0; j < n; j += 1) {
+; body:
+;   val = 21.0 + 21.0;
+;   A[1] = val;
+;
+; user:
+;   A[0] = val;
+; }
+;
+define void @overwritten_implicit_and_explicit(i32 %n, double* noalias nonnull %A, double* noalias nonnull %C) {
+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
+      store double %val, double* %A
+      br label %user
+
+    user:
+      store double %val, double* %C
+      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[0] };
+; CHECK-NEXT:     Stmt_user

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

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      },
+      {
+         "name" : "MemRef_C",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "[n] -> {  : -2147483648 <= n <= 2147483647 }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[i0] -> MemRef_A[0] }"
+            },
+            {
+               "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" : "write",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_C[0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_val[] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_user[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_user",
+         "schedule" : "[n] -> { Stmt_user[i0] -> [i0, 1] }"
+      }
+   ]
+}

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

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      },
+      {
+         "name" : "MemRef_C",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "[n] -> {  : -2147483648 <= n <= 2147483647 }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[i0] -> MemRef_A[0] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[i0] ->  MemRef_A[0] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_body",
+         "schedule" : "[n] -> { Stmt_body[i0] -> [i0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_C[0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_val[] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_user[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_user",
+         "schedule" : "[n] -> { Stmt_user[i0] -> [i0, 1] }"
+      }
+   ]
+}

polly/trunk/test/Simplify/overwritten_loadbetween.ll

+; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck -match-full-lines %s 
+;
+; Do not remove overwrites when the value is read before.
+;
+; for (int j = 0; j < n; j += 1) {
+;body:
+;   A[0] = 21.0;
+;   val = A[0];
+;   A[0] = 42.0;
+;
+;user:
+;   B[0] = val;
+; }
+;
+define void @overwritten(i32 %n, double* noalias nonnull %A, double* noalias nonnull %B) {
+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:
+      store double 21.0, double* %A
+      %val = load double, double* %A
+      store double 42.0, double* %A
+      br label %user
+
+    user:
+      store double %val, double* %B
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK: SCoP could not be simplified