Index: lib/Transform/Simplify.cpp =================================================================== --- lib/Transform/Simplify.cpp +++ lib/Transform/Simplify.cpp @@ -31,8 +31,6 @@ "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"); @@ -105,9 +103,6 @@ /// 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; @@ -119,8 +114,8 @@ /// 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) { @@ -194,75 +189,6 @@ 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 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. /// @@ -407,8 +333,6 @@ /// 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: " @@ -445,9 +369,6 @@ this->S = &S; ScopsProcessed++; - DEBUG(dbgs() << "Removing identical writes...\n"); - removeIdenticalWrites(); - DEBUG(dbgs() << "Removing overwrites...\n"); removeOverwrites(); @@ -480,7 +401,6 @@ virtual void releaseMemory() override { S = nullptr; - IdenticalWritesRemoved = 0; OverwritesRemoved = 0; RedundantWritesRemoved = 0; StmtsRemoved = 0; Index: overwritten.ll =================================================================== --- /dev/null +++ overwritten.ll @@ -0,0 +1,827 @@ +diff --git a/lib/Transform/Simplify.cpp b/lib/Transform/Simplify.cpp +index 16fdbe11..d406134b 100644 +--- a/lib/Transform/Simplify.cpp ++++ b/lib/Transform/Simplify.cpp +@@ -1,397 +1,498 @@ + //===------ Simplify.cpp ----------------------------------------*- C++ -*-===// + // + // The LLVM Compiler Infrastructure + // + // This file is distributed under the University of Illinois Open Source + // License. See LICENSE.TXT for details. + // + //===----------------------------------------------------------------------===// + // + // Simplify a SCoP by removing unnecessary statements and accesses. + // + //===----------------------------------------------------------------------===// + + #include "polly/Simplify.h" + #include "polly/ScopInfo.h" + #include "polly/ScopPass.h" + #include "polly/Support/GICHelper.h" + #include "llvm/ADT/Statistic.h" + #include "llvm/Support/Debug.h" + #define DEBUG_TYPE "polly-simplify" + + using namespace llvm; + using namespace polly; + + namespace { + + 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) { + 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(); + } + ++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( ++ 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(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(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 = give(isl_map_get_space(Targets.keep())); + + bool Started = Stmt->isRegionStmt(); + for (auto *Acc : *Stmt) { + 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; + + auto AccRel = give(Acc->getAccessRelation()); + auto AccRelSpace = give(isl_map_get_space(AccRel.keep())); + + // Spaces being different means that they access different arrays. + if (isl_space_has_equal_tuples(TargetsSpace.keep(), AccRelSpace.keep()) == + isl_bool_false) + continue; + + AccRel = give(isl_map_intersect_domain(AccRel.take(), + Acc->getStatement()->getDomain())); + AccRel = give(isl_map_intersect_params(AccRel.take(), S->getContext())); + auto CommonElt = give(isl_map_intersect(Targets.copy(), AccRel.copy())); + 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 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. ++ /// ++ /// Ther 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 Accesses{AccRange.begin(), ++ AccRange.end()}; ++ ++ // Iterate in reverse order, so the overwrites comes before the write that ++ // is to be removed. ++ for (auto *MA : reverse(Accesses)) { ++ ++ // In region statement, 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 StoresToRemove; + + for (auto &Stmt : *S) { + for (auto *WA : Stmt) { + if (!WA->isMustWrite()) + continue; + if (!WA->isLatestArrayKind()) + continue; + if (!isa(WA->getAccessInstruction())) + continue; + + auto ReadingValue = WA->getAccessValue(); + if (!ReadingValue) + continue; + + auto RA = getReadAccessForValue(&Stmt, ReadingValue); + if (!RA) + continue; + if (!RA->isLatestArrayKind()) + continue; + + auto WARel = give(WA->getLatestAccessRelation()); + WARel = give(isl_map_intersect_domain(WARel.take(), + WA->getStatement()->getDomain())); + WARel = give(isl_map_intersect_params(WARel.take(), S->getContext())); + auto RARel = give(RA->getLatestAccessRelation()); + RARel = give(isl_map_intersect_domain(RARel.take(), + RA->getStatement()->getDomain())); + RARel = give(isl_map_intersect_params(RARel.take(), S->getContext())); + + if (isl_map_is_equal(RARel.keep(), WARel.keep()) != isl_bool_true) { + PairUnequalAccRels++; + DEBUG(dbgs() << "Not cleaning up " << WA + << " because of unequal access relations:\n"); + DEBUG(dbgs() << " RA: " << RARel << "\n"); + DEBUG(dbgs() << " WA: " << WARel << "\n"); + continue; + } + + 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; + } + + StoresToRemove.push_back(WA); + } + } + + for (auto *WA : StoresToRemove) { + auto Stmt = WA->getStatement(); + auto AccRel = give(WA->getAccessRelation()); + auto AccVal = WA->getAccessValue(); + + DEBUG(dbgs() << "Cleanup of " << WA << ":\n"); + DEBUG(dbgs() << " Scalar: " << *AccVal << "\n"); + DEBUG(dbgs() << " AccRel: " << AccRel << "\n"); + (void)AccVal; + (void)AccRel; + + Stmt->removeSingleMemoryAccess(WA); + + RedundantWritesRemoved++; + TotalRedundantWritesRemoved++; + } + } + + /// Remove statements without side effects. + void removeUnnecessayStmts() { + auto NumStmtsBefore = S->getSize(); + S->simplifySCoP(true); + assert(NumStmtsBefore >= S->getSize()); + StmtsRemoved = NumStmtsBefore - S->getSize(); + 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"; + } + + /// Print the current state of all MemoryAccesses to @p OS. + void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const { + OS.indent(Indent) << "After accesses {\n"; + for (auto &Stmt : *S) { + OS.indent(Indent + 4) << Stmt.getBaseName() << "\n"; + for (auto *MA : Stmt) + MA->print(OS); + } + OS.indent(Indent) << "}\n"; + } + + public: + static char ID; + explicit Simplify() : ScopPass(ID) {} + + virtual void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequiredTransitive(); + AU.setPreservesAll(); + } + + 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()) + ScopsModified++; + DEBUG(dbgs() << "\nFinal Scop:\n"); + DEBUG(S.print(dbgs())); + + return false; + } + + virtual void printScop(raw_ostream &OS, Scop &S) const override { + assert(&S == this->S && + "Can only print analysis for the last processed SCoP"); + printStatistics(OS); + + if (!isModified()) { + OS << "SCoP could not be simplified\n"; + 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) +diff --git a/test/Simplify/overwritten.ll b/test/Simplify/overwritten.ll +new file mode 100644 +index 00000000..55d59b34 +--- /dev/null ++++ b/test/Simplify/overwritten.ll +@@ -0,0 +1,44 @@ ++; 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: } +diff --git a/test/Simplify/overwritten_3store.ll b/test/Simplify/overwritten_3store.ll +new file mode 100644 +index 00000000..133a3478 +--- /dev/null ++++ b/test/Simplify/overwritten_3store.ll +@@ -0,0 +1,47 @@ ++; 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: } +diff --git a/test/Simplify/overwritten_implicit_and_explicit.ll b/test/Simplify/overwritten_implicit_and_explicit.ll +new file mode 100644 +index 00000000..43d18ed5 +--- /dev/null ++++ b/test/Simplify/overwritten_implicit_and_explicit.ll +@@ -0,0 +1,53 @@ ++; 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 +diff --git a/test/Simplify/overwritten_implicit_and_explicit___%for---%return.jscop b/test/Simplify/overwritten_implicit_and_explicit___%for---%return.jscop +new file mode 100644 +index 00000000..7ea3ca2a +--- /dev/null ++++ b/test/Simplify/overwritten_implicit_and_explicit___%for---%return.jscop +@@ -0,0 +1,48 @@ ++{ ++ "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] }" ++ } ++ ] ++} +diff --git a/test/Simplify/overwritten_implicit_and_explicit___%for---%return.jscop.transformed b/test/Simplify/overwritten_implicit_and_explicit___%for---%return.jscop.transformed +new file mode 100644 +index 00000000..b49747de +--- /dev/null ++++ b/test/Simplify/overwritten_implicit_and_explicit___%for---%return.jscop.transformed +@@ -0,0 +1,48 @@ ++{ ++ "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] }" ++ } ++ ] ++} +diff --git a/test/Simplify/overwritten_loadbetween.ll b/test/Simplify/overwritten_loadbetween.ll +new file mode 100644 +index 00000000..c06263eb +--- /dev/null ++++ b/test/Simplify/overwritten_loadbetween.ll +@@ -0,0 +1,46 @@ ++; 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 Index: test/Simplify/overwritten_3phi.ll =================================================================== --- test/Simplify/overwritten_3phi.ll +++ test/Simplify/overwritten_3phi.ll @@ -15,7 +15,7 @@ ; A[0] = A[1]; ; } ; -define void @identical_3phi(i32 %n, double* noalias nonnull %A) { +define void @overwritten_3phi(i32 %n, double* noalias nonnull %A) { entry: br label %for @@ -51,11 +51,11 @@ ; CHECK: Statistics { -; CHECK: Identical writes removed: 2 +; CHECK: Overwrites 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: [n] -> { Stmt_body[i0] -> MemRef_phi3__phi[] }; ; CHECK-NEXT: new: [n] -> { Stmt_body[i0] -> MemRef_A[1] }; ; CHECK-NEXT: Stmt_user Index: test/Simplify/overwritten_scalar.ll =================================================================== --- test/Simplify/overwritten_scalar.ll +++ test/Simplify/overwritten_scalar.ll @@ -14,7 +14,7 @@ ; A[0] = A[1]; ; } ; -define void @identical(i32 %n, double* noalias nonnull %A) { +define void @overwritten_scalar(i32 %n, double* noalias nonnull %A) { entry: br label %for @@ -46,11 +46,11 @@ ; CHECK: Statistics { -; CHECK: Identical writes removed: 1 +; CHECK: Overwrites 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: [n] -> { Stmt_body[i0] -> MemRef_val[] }; ; CHECK-NEXT: new: [n] -> { Stmt_body[i0] -> MemRef_A[1] }; ; CHECK-NEXT: Stmt_user