[Polly][Simplify] Rewrite redundant write detection algorithm.

[Meinersbur]

Summary

The previous algorithm was to search a writes and the sours of its value operand, and see whether the write just stores the same read value back, which includes a search whether there is another write access between them. This is O(n^2) in the max number of accesses in a statement (+ the complexity of isl comparing the access functions).

The new algorithm is more similar to the one used for searching for overwrites and coalescable writes. It scans over all accesses in order of execution while tracking which array elements still have the same value since it was read. This is O(n), not counting the complexity within isl. It should be more reliable than trying to catch all non-conforming cases in the previous approach. It is also less code.

We now also support if the write is a partial write of the read's subset, and to some extent non-affine subregions.

[grosser]

LGTM.

test/Simplify/notredundant_region_loop.ll

3 ↗

(On Diff #109072)

THE store

[Meinersbur]

• Rename GuaranteedReads to Known
• Remove whitespace at end of lines

polly/trunk/lib/Transform/Simplify.cpp

 /// that the analysis of accesses in a statement is becoming too complex. Chosen
 /// to be relatively small because all the common cases should access only few
 /// array elements per statement.
 static int const SimplifyMaxDisjuncts = 4;
 
 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(TotalOverwritesRemoved, "Number of removed overwritten writes");
 STATISTIC(TotalWritesCoalesced, "Number of writes coalesced with another");
 STATISTIC(TotalRedundantWritesRemoved,
           "Number of writes of same value removed in any SCoP");
 STATISTIC(TotalEmptyPartialAccessesRemoved,
           "Number of empty partial accesses removed");
 STATISTIC(TotalDeadAccessesRemoved, "Number of dead accesses removed");
 STATISTIC(TotalDeadInstructionsRemoved,
private:
   /// Return whether at least one simplification has been applied.
   bool isModified() const {
     return OverwritesRemoved > 0 || WritesCoalesced > 0 ||
            RedundantWritesRemoved > 0 || EmptyPartialAccessesRemoved > 0 ||
            DeadAccessesRemoved > 0 || DeadInstructionsRemoved > 0 ||
            StmtsRemoved > 0;
   }
 
-  MemoryAccess *getReadAccessForValue(ScopStmt *Stmt, llvm::Value *Val) {
-    if (!isa<Instruction>(Val))
-      return nullptr;
-
-    for (auto *MA : *Stmt) {
-      if (!MA->isRead())
-        continue;
-      if (MA->getAccessValue() != Val)
-        continue;
-
-      return MA;
-    }
-
-    return nullptr;
-  }
-
-  /// Return a write access that occurs between @p From and @p To.
-  ///
-  /// In region statements the order is ignored because we cannot predict it.
-  ///
-  /// @param Stmt    Statement of both writes.
-  /// @param From    Start looking after this access.
-  /// @param To      Stop looking at this access, with the access itself.
-  /// @param Targets Look for an access that may wrote to one of these elements.
-  ///
-  /// @return A write access between @p From and @p To that writes to at least
-  ///         one element in @p Targets.
-  MemoryAccess *hasWriteBetween(ScopStmt *Stmt, MemoryAccess *From,
-                                MemoryAccess *To, isl::map Targets) {
-    auto TargetsSpace = Targets.get_space();
-
-    bool Started = Stmt->isRegionStmt();
-    auto Accesses = getAccessesInOrder(*Stmt);
-    for (auto *Acc : Accesses) {
-      if (Acc->isLatestScalarKind())
-        continue;
-
-      if (Stmt->isBlockStmt() && From == Acc) {
-        assert(!Started);
-        Started = true;
-        continue;
-      }
-      if (Stmt->isBlockStmt() && To == Acc) {
-        assert(Started);
-        return nullptr;
-      }
-      if (!Started)
-        continue;
-
-      if (!Acc->isWrite())
-        continue;
-
-      isl::map AccRel = Acc->getAccessRelation();
-      auto AccRelSpace = AccRel.get_space();
-
-      // Spaces being different means that they access different arrays.
-      if (!TargetsSpace.has_equal_tuples(AccRelSpace))
-        continue;
-
-      AccRel = AccRel.intersect_domain(give(Acc->getStatement()->getDomain()));
-      AccRel = AccRel.intersect_params(give(S->getContext()));
-      auto CommonElt = Targets.intersect(AccRel);
-      if (!CommonElt.is_empty())
-        return Acc;
-    }
-    assert(Stmt->isRegionStmt() &&
-           "To must be encountered in block statements");
-    return nullptr;
-  }
-
   /// 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());
for (auto &Stmt : *S) {
         }
       }
     }
   }
 
   /// 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) {
-        if (!WA->isMustWrite())
-          continue;
-        if (!WA->isLatestArrayKind())
-          continue;
-        if (!isa<StoreInst>(WA->getAccessInstruction()) &&
-            !WA->isOriginalScalarKind())
-          continue;
-
-        llvm::Value *ReadingValue = WA->tryGetValueStored();
-
-        if (!ReadingValue)
-          continue;
+      SmallDenseMap<Value *, isl::set> ValueSets;
+      auto makeValueSet = [&ValueSets, this](Value *V) -> isl::set {
+        assert(V);
+        isl::set &Result = ValueSets[V];
+        if (Result.is_null()) {
+          isl_ctx *Ctx = S->getIslCtx();
+          std::string Name =
+              getIslCompatibleName("Val", V, ValueSets.size() - 1,
+                                   std::string(), UseInstructionNames);
+          isl::id Id = give(isl_id_alloc(Ctx, Name.c_str(), V));
+          Result = isl::set::universe(
+              isl::space(Ctx, 0, 0).set_tuple_id(isl::dim::set, Id));
+        }
+        return Result;
+      };
 
-        auto RA = getReadAccessForValue(&Stmt, ReadingValue);
-        if (!RA)
-          continue;
-        if (!RA->isLatestArrayKind())
-          continue;
+      isl::set Domain = give(Stmt.getDomain());
+      Domain = Domain.intersect_params(give(S->getContext()));
 
-        auto WARel = WA->getLatestAccessRelation();
-        WARel = WARel.intersect_domain(give(WA->getStatement()->getDomain()));
-        WARel = WARel.intersect_params(give(S->getContext()));
-        auto RARel = RA->getLatestAccessRelation();
-        RARel = RARel.intersect_domain(give(RA->getStatement()->getDomain()));
-        RARel = RARel.intersect_params(give(S->getContext()));
-
-        if (!RARel.is_equal(WARel)) {
-          PairUnequalAccRels++;
-          DEBUG(dbgs() << "Not cleaning up " << WA
-                       << " because of unequal access relations:\n");
-          DEBUG(dbgs() << "      RA: " << RARel << "\n");
-          DEBUG(dbgs() << "      WA: " << WARel << "\n");
-          continue;
-        }
+      // List of element reads that still have the same value while iterating
+      // through the MemoryAccesses.
+      // { [Domain[] -> Element[]] -> Val[] }
+      isl::union_map Known = isl::union_map::empty(give(S->getParamSpace()));
 
-        if (auto *Conflicting = hasWriteBetween(&Stmt, RA, WA, WARel)) {
-          (void)Conflicting;
-          InBetweenStore++;
-          DEBUG(dbgs() << "Not cleaning up " << WA
-                       << " because there is another store to the same element "
-                          "between\n");
-          DEBUG(Conflicting->print(dbgs()));
-          continue;
-        }
+      SmallVector<MemoryAccess *, 32> Accesses(getAccessesInOrder(Stmt));
+      for (MemoryAccess *MA : Accesses) {
+        // Is the memory access in a defined order relative to the other
+        // accesses? In region statements, only the first and the last accesses
+        // have defined order. Execution of those in the middle may depend on
+        // runtime conditions an therefore cannot be modified.
+        bool IsOrdered =
+            Stmt.isBlockStmt() || MA->isOriginalScalarKind() ||
+            (!S->getBoxedLoops().size() && MA->getAccessInstruction() &&
+             Stmt.getEntryBlock() == MA->getAccessInstruction()->getParent());
 
-        StoresToRemove.push_back(WA);
-      }
-    }
+        isl::map AccRel = MA->getAccessRelation();
+        AccRel = AccRel.intersect_domain(Domain);
+        isl::set AccRelWrapped = AccRel.wrap();
 
-    for (auto *WA : StoresToRemove) {
-      auto Stmt = WA->getStatement();
-      auto AccRel = WA->getAccessRelation();
-      auto AccVal = WA->getAccessValue();
+        // Determine whether a write is redundant (stores only values that are
+        // already present in the written array elements) and remove it if this
+        // is the case.
+        if (IsOrdered && MA->isMustWrite() &&
+            (isa<StoreInst>(MA->getAccessInstruction()) ||
+             MA->isOriginalScalarKind())) {
+          Value *StoredVal = MA->tryGetValueStored();
+          if (!StoredVal)
+            StoredVal = MA->getAccessValue();
 
-      DEBUG(dbgs() << "Cleanup of " << WA << ":\n");
-      DEBUG(dbgs() << "      Scalar: " << *AccVal << "\n");
+          if (StoredVal) {
+            // Lookup in the set of known values.
+            isl::map AccRelStoredVal = isl::map::from_domain_and_range(
+                AccRelWrapped, makeValueSet(StoredVal));
+            if (isl::union_map(AccRelStoredVal).is_subset(Known)) {
+              DEBUG(dbgs() << "Cleanup of " << MA << ":\n");
+              DEBUG(dbgs() << "      Scalar: " << *StoredVal << "\n");
               DEBUG(dbgs() << "      AccRel: " << AccRel << "\n");
-      (void)AccVal;
-      (void)AccRel;
 
-      Stmt->removeSingleMemoryAccess(WA);
+              Stmt.removeSingleMemoryAccess(MA);
 
               RedundantWritesRemoved++;
               TotalRedundantWritesRemoved++;
             }
           }
+        }
+
+        // Update the know values set.
+        if (MA->isRead()) {
+          // Loaded values are the currently known values of the array element
+          // it was loaded from.
+          Value *LoadedVal = MA->getAccessValue();
+          if (LoadedVal && IsOrdered) {
+            isl::map AccRelVal = isl::map::from_domain_and_range(
+                AccRelWrapped, makeValueSet(LoadedVal));
+
+            Known = Known.add_map(AccRelVal);
+          }
+        } else if (MA->isWrite()) {
+          // Remove (possibly) overwritten values from the known elements set.
+          // We remove all elements of the accessed array to avoid too complex
+          // isl sets.
+          isl::set AccRelUniv = isl::set::universe(AccRelWrapped.get_space());
+          Known = Known.subtract_domain(AccRelUniv);
+
+          // At this point, we could add the written value of must-writes.
+          // However, writing same values is already handled by
+          // coalesceWrites().
+        }
+      }
+    }
+  }
 
   /// Remove statements without side effects.
   void removeUnnecessaryStmts() {
     auto NumStmtsBefore = S->getSize();
     S->simplifySCoP(true);
     assert(NumStmtsBefore >= S->getSize());
     StmtsRemoved = NumStmtsBefore - S->getSize();
     DEBUG(dbgs() << "Removed " << StmtsRemoved << " (of " << NumStmtsBefore

polly/trunk/test/Simplify/notredundant_region_loop.ll

+; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-postfix=transformed -polly-allow-nonaffine-loops -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+;
+; Do not remove the store in region_entry. It can be executed multiple times
+; due to being part of a non-affine loop.
+;
+define void @notredundant_region_loop(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 %region_entry
+
+    region_entry:
+      store double %val, double* %A
+      %sqr = mul i32 %j, %j
+      %cmp = icmp eq i32 %sqr, 42
+      br i1 %cmp, label %region_true, label %region_exit
+
+    region_true:
+      store double 0.0, double* %A
+      br label %region_entry
+
+    region_exit:
+      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

polly/trunk/test/Simplify/notredundant_region_loop___%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_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_region_entry__TO__region_exit[i0] -> MemRef_A[0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_region_entry__TO__region_exit[i0] -> MemRef_val[] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_region_entry__TO__region_exit[i0] -> MemRef_A[0] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_region_entry__TO__region_exit[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_region_entry__TO__region_exit",
+         "schedule" : "[n] -> { Stmt_region_entry__TO__region_exit[i0] -> [i0, 1] }"
+      }
+   ]
+}

polly/trunk/test/Simplify/notredundant_region_loop___%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[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_region_entry__TO__region_exit[i0] -> MemRef_A[0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_region_entry__TO__region_exit[i0] -> MemRef_A[0] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_region_entry__TO__region_exit[i0] -> MemRef_A[0] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_region_entry__TO__region_exit[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_region_entry__TO__region_exit",
+         "schedule" : "[n] -> { Stmt_region_entry__TO__region_exit[i0] -> [i0, 1] }"
+      }
+   ]
+}

polly/trunk/test/Simplify/notredundant_region_middle.ll

+; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-postfix=transformed -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+;
+; Do not remove redundant stores in the middle of region statements.
+; The store in region_true could be removed, but in practice we do try to
+; determine the relative ordering of block in region statements.
+;
+; for (int j = 0; j < n; j += 1) {
+;   double val = A[0];
+;   if (val == 0.0)
+;     A[0] = val;
+;   else
+;     A[0] = 0.0;
+; }
+;
+define void @notredundant_region(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 %region_entry, label %exit
+
+
+    region_entry:
+      %val = load double, double* %A
+      %cmp = fcmp oeq double %val, 0.0
+      br i1 %cmp, label %region_true, label %region_false
+
+    region_true:
+      store double %val, double* %A
+      br label %region_exit
+
+    region_false:
+      store double 0.0, double* %A
+      br label %region_exit
+
+    region_exit:
+      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

polly/trunk/test/Simplify/redundant_differentindex.ll

 ; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
-; RUN: opt %loadPolly -polly-simplify -disable-output -stats < %s 2>&1 | FileCheck %s --check-prefix=STATS -match-full-lines
-; REQUIRES: asserts
 ;
 ; A store that has a different index than the load it is storing is
 ; not redundant.
 ;
 ; for (int j = 0; j < n; j += 1)
 ;   A[0] = A[0];
 ;
 define void @func(i32 %n, double* noalias nonnull %A) {
exit:
   br label %return
 
 return:
   ret void
 }
 
 
 ; CHECK: SCoP could not be simplified
-
-; STATS: 1 polly-simplify   - Number of Load-Store pairs NOT removed because of different access relations

polly/trunk/test/Simplify/redundant_partialwrite.ll

+; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-postfix=transformed -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+;
+; Remove a redundant store, if its partial domain is a subset of the
+; read's domain.
+;
+define void @redundant_partialwrite(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 = load double, double* %A
+      store double %val, 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 successful import.
+; CHECK:    new: [n] -> { Stmt_body[i0] -> MemRef_A[0] : i0 <= 15 };
+
+; CHECK: Statistics {
+; CHECK:     Redundant writes removed: 1
+; CHECK: }
+
+; CHECK:      After accesses {
+; CHECK-NEXT: }

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

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "[n] -> {  : -2147483648 <= n <= 2147483647 }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "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] }"
+      }
+   ]
+}

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

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

polly/trunk/test/Simplify/redundant_region.ll

+; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-postfix=transformed -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+;
+; Remove redundant store (a store that writes the same value already
+; at the destination) in a region.
+;
+define void @redundant_region(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 %region_entry, label %exit
+
+
+    region_entry:
+      %val = load double, double* %A
+      %cmp = fcmp oeq double %val, 0.0
+      br i1 %cmp, label %region_true, label %region_exit
+
+    region_true:
+      br label %region_exit
+
+    region_exit:
+      br label %body
+
+    body:
+      store double %val, 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:     Redundant writes removed: 2
+; CHECK: }
+
+; CHECK:      After accesses {
+; CHECK-NEXT: }

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

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

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

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

polly/trunk/test/Simplify/redundant_region_scalar.ll

+; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-postfix=transformed -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+;
+; Remove redundant store (a store that writes the same value already
+; at the destination) in a region.
+;
+define void @redundant_region_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 %bodyA, label %exit
+
+
+    bodyA:
+      %val1 = load double, double* %A
+      br label %region_entry
+
+    region_entry:
+      %val2 = load double, double* %A
+      %cmp = fcmp oeq double %val1, 0.0
+      br i1 %cmp, label %region_true, label %region_exit
+
+    region_true:
+      br label %region_exit
+
+    region_exit:
+      br label %bodyB
+
+    bodyB:
+      store double %val2, 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:     Redundant writes removed: 3
+; CHECK: }
+
+; CHECK:      After accesses {
+; CHECK-NEXT: }

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

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "[n] -> {  : -2147483648 <= n <= 2147483647 }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_bodyA[i0] -> MemRef_A[0] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_bodyA[i0] -> MemRef_val1[] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_bodyA[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_bodyA",
+         "schedule" : "[n] -> { Stmt_bodyA[i0] -> [i0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_region_entry__TO__region_exit[i0] -> MemRef_A[0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_region_entry__TO__region_exit[i0] -> MemRef_val1[] }"
+            },
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_region_entry__TO__region_exit[i0] -> MemRef_val2[] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_region_entry__TO__region_exit[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_region_entry__TO__region_exit",
+         "schedule" : "[n] -> { Stmt_region_entry__TO__region_exit[i0] -> [i0, 1] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_bodyB[i0] -> MemRef_A[0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_bodyB[i0] -> MemRef_val2[] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_bodyB[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_bodyB",
+         "schedule" : "[n] -> { Stmt_bodyB[i0] -> [i0, 2] }"
+      }
+   ]
+}

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

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

polly/trunk/test/Simplify/redundant_storebetween.ll

 ; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
-; RUN: opt %loadPolly -polly-simplify -disable-output -stats < %s 2>&1 | FileCheck %s --check-prefix=STATS -match-full-lines
-; REQUIRES: asserts
 ;
 ; Don't remove store where there is another store to the same target
 ; in-between them.
 ;
 ; for (int j = 0; j < n; j += 1)
 ;   A[0] = A[0];
 ;
 define void @func(i32 %n, double* noalias nonnull %A) {

 
 return:
   ret void
 }
 
 
 ; CHECK: SCoP could not be simplified
 
-; STATS: 1 polly-simplify   - Number of Load-Store pairs NOT removed because there is another store between them