diff options
16 files changed, 675 insertions, 141 deletions
diff --git a/polly/lib/Transform/Simplify.cpp b/polly/lib/Transform/Simplify.cpp index d62686c6585..5145ff0dd2a 100644 --- a/polly/lib/Transform/Simplify.cpp +++ b/polly/lib/Transform/Simplify.cpp @@ -36,10 +36,6 @@ 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, @@ -169,76 +165,6 @@ private: 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. /// @@ -484,76 +410,97 @@ private: /// 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; + 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; + }; - llvm::Value *ReadingValue = WA->tryGetValueStored(); + isl::set Domain = give(Stmt.getDomain()); + Domain = Domain.intersect_params(give(S->getContext())); - if (!ReadingValue) - 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())); - auto RA = getReadAccessForValue(&Stmt, ReadingValue); - if (!RA) - continue; - if (!RA->isLatestArrayKind()) - 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()); - 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; - } + isl::map AccRel = MA->getAccessRelation(); + AccRel = AccRel.intersect_domain(Domain); + isl::set AccRelWrapped = AccRel.wrap(); - 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; + // 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(); + + 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"); + + Stmt.removeSingleMemoryAccess(MA); + + RedundantWritesRemoved++; + TotalRedundantWritesRemoved++; + } + } } - StoresToRemove.push_back(WA); + // 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(). + } } } - - for (auto *WA : StoresToRemove) { - auto Stmt = WA->getStatement(); - auto AccRel = 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. diff --git a/polly/test/Simplify/notredundant_region_loop.ll b/polly/test/Simplify/notredundant_region_loop.ll new file mode 100644 index 00000000000..c8b7ee5ae4f --- /dev/null +++ b/polly/test/Simplify/notredundant_region_loop.ll @@ -0,0 +1,46 @@ +; 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 diff --git a/polly/test/Simplify/notredundant_region_loop___%for---%return.jscop b/polly/test/Simplify/notredundant_region_loop___%for---%return.jscop new file mode 100644 index 00000000000..b86534e7a06 --- /dev/null +++ b/polly/test/Simplify/notredundant_region_loop___%for---%return.jscop @@ -0,0 +1,43 @@ +{ + "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] }" + } + ] +} diff --git a/polly/test/Simplify/notredundant_region_loop___%for---%return.jscop.transformed b/polly/test/Simplify/notredundant_region_loop___%for---%return.jscop.transformed new file mode 100644 index 00000000000..9fe65e936fd --- /dev/null +++ b/polly/test/Simplify/notredundant_region_loop___%for---%return.jscop.transformed @@ -0,0 +1,43 @@ +{ + "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] }" + } + ] +} diff --git a/polly/test/Simplify/notredundant_region_middle.ll b/polly/test/Simplify/notredundant_region_middle.ll new file mode 100644 index 00000000000..cadbc1724fc --- /dev/null +++ b/polly/test/Simplify/notredundant_region_middle.ll @@ -0,0 +1,54 @@ +; 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 diff --git a/polly/test/Simplify/redundant_differentindex.ll b/polly/test/Simplify/redundant_differentindex.ll index d460f85a09d..3a5e07334cb 100644 --- a/polly/test/Simplify/redundant_differentindex.ll +++ b/polly/test/Simplify/redundant_differentindex.ll @@ -1,6 +1,4 @@ ; 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. @@ -36,5 +34,3 @@ return: ; CHECK: SCoP could not be simplified - -; STATS: 1 polly-simplify - Number of Load-Store pairs NOT removed because of different access relations diff --git a/polly/test/Simplify/redundant_partialwrite.ll b/polly/test/Simplify/redundant_partialwrite.ll new file mode 100644 index 00000000000..71c27bd349e --- /dev/null +++ b/polly/test/Simplify/redundant_partialwrite.ll @@ -0,0 +1,40 @@ +; 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: } diff --git a/polly/test/Simplify/redundant_partialwrite___%for---%return.jscop b/polly/test/Simplify/redundant_partialwrite___%for---%return.jscop new file mode 100644 index 00000000000..9869237ab63 --- /dev/null +++ b/polly/test/Simplify/redundant_partialwrite___%for---%return.jscop @@ -0,0 +1,28 @@ +{ + "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] }" + } + ] +} diff --git a/polly/test/Simplify/redundant_partialwrite___%for---%return.jscop.transformed b/polly/test/Simplify/redundant_partialwrite___%for---%return.jscop.transformed new file mode 100644 index 00000000000..38b730fc4d4 --- /dev/null +++ b/polly/test/Simplify/redundant_partialwrite___%for---%return.jscop.transformed @@ -0,0 +1,28 @@ +{ + "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] }" + } + ] +} diff --git a/polly/test/Simplify/redundant_region.ll b/polly/test/Simplify/redundant_region.ll new file mode 100644 index 00000000000..c006f4bd3d7 --- /dev/null +++ b/polly/test/Simplify/redundant_region.ll @@ -0,0 +1,49 @@ +; 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: } diff --git a/polly/test/Simplify/redundant_region___%for---%return.jscop b/polly/test/Simplify/redundant_region___%for---%return.jscop new file mode 100644 index 00000000000..7517c3e39bc --- /dev/null +++ b/polly/test/Simplify/redundant_region___%for---%return.jscop @@ -0,0 +1,43 @@ +{ + "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] }" + } + ] +} diff --git a/polly/test/Simplify/redundant_region___%for---%return.jscop.transformed b/polly/test/Simplify/redundant_region___%for---%return.jscop.transformed new file mode 100644 index 00000000000..b416142c358 --- /dev/null +++ b/polly/test/Simplify/redundant_region___%for---%return.jscop.transformed @@ -0,0 +1,43 @@ +{ + "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] }" + } + ] +} diff --git a/polly/test/Simplify/redundant_region_scalar.ll b/polly/test/Simplify/redundant_region_scalar.ll new file mode 100644 index 00000000000..495a4baafee --- /dev/null +++ b/polly/test/Simplify/redundant_region_scalar.ll @@ -0,0 +1,53 @@ +; 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: } diff --git a/polly/test/Simplify/redundant_region_scalar___%for---%return.jscop b/polly/test/Simplify/redundant_region_scalar___%for---%return.jscop new file mode 100644 index 00000000000..7712c264dde --- /dev/null +++ b/polly/test/Simplify/redundant_region_scalar___%for---%return.jscop @@ -0,0 +1,62 @@ +{ + "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] }" + } + ] +} diff --git a/polly/test/Simplify/redundant_region_scalar___%for---%return.jscop.transformed b/polly/test/Simplify/redundant_region_scalar___%for---%return.jscop.transformed new file mode 100644 index 00000000000..9bb0e0c2d71 --- /dev/null +++ b/polly/test/Simplify/redundant_region_scalar___%for---%return.jscop.transformed @@ -0,0 +1,62 @@ +{ + "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] }" + } + ] +} diff --git a/polly/test/Simplify/redundant_storebetween.ll b/polly/test/Simplify/redundant_storebetween.ll index 03172b6b0eb..5e1befcb1a4 100644 --- a/polly/test/Simplify/redundant_storebetween.ll +++ b/polly/test/Simplify/redundant_storebetween.ll @@ -1,6 +1,4 @@ ; 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. @@ -38,4 +36,3 @@ return: ; CHECK: SCoP could not be simplified -; STATS: 1 polly-simplify - Number of Load-Store pairs NOT removed because there is another store between them |
