summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--polly/include/polly/ScopInfo.h20
-rw-r--r--polly/lib/Analysis/ScopInfo.cpp18
-rw-r--r--polly/test/Simplify/notredundant_synthesizable_unknownit.ll65
3 files changed, 93 insertions, 10 deletions
diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index df20ac53597..e61b8a1f411 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -1912,6 +1912,14 @@ private:
/// A number that uniquely represents a Scop within its function
const int ID;
+ /// Map of values to the MemoryAccess that writes its definition.
+ ///
+ /// There must be at most one definition per llvm::Instruction in a SCoP.
+ DenseMap<Value *, MemoryAccess *> ValueDefAccs;
+
+ /// Map of values to the MemoryAccess that reads a PHI.
+ DenseMap<PHINode *, MemoryAccess *> PHIReadAccs;
+
/// List of all uses (i.e. read MemoryAccesses) for a MemoryKind::Value
/// scalar.
DenseMap<const ScopArrayInfo *, SmallVector<MemoryAccess *, 4>> ValueUseAccs;
@@ -2392,6 +2400,18 @@ public:
/// created in this pass.
void addAccessFunction(MemoryAccess *Access) {
AccessFunctions.emplace_back(Access);
+
+ // Register value definitions.
+ if (Access->isWrite() && Access->isOriginalValueKind()) {
+ assert(!ValueDefAccs.count(Access->getAccessValue()) &&
+ "there can be just one definition per value");
+ ValueDefAccs[Access->getAccessValue()] = Access;
+ } else if (Access->isRead() && Access->isOriginalPHIKind()) {
+ PHINode *PHI = cast<PHINode>(Access->getAccessInstruction());
+ assert(!PHIReadAccs.count(PHI) &&
+ "there can be just one PHI read per PHINode");
+ PHIReadAccs[PHI] = Access;
+ }
}
/// Add metadata for @p Access.
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 298609258ea..01cca27de55 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -4914,9 +4914,14 @@ void Scop::addAccessData(MemoryAccess *Access) {
}
void Scop::removeAccessData(MemoryAccess *Access) {
- if (Access->isOriginalValueKind() && Access->isRead()) {
+ if (Access->isOriginalValueKind() && Access->isWrite()) {
+ ValueDefAccs.erase(Access->getAccessValue());
+ } else if (Access->isOriginalValueKind() && Access->isRead()) {
auto &Uses = ValueUseAccs[Access->getScopArrayInfo()];
std::remove(Uses.begin(), Uses.end(), Access);
+ } else if (Access->isOriginalPHIKind() && Access->isRead()) {
+ PHINode *PHI = cast<PHINode>(Access->getAccessInstruction());
+ PHIReadAccs.erase(PHI);
} else if (Access->isOriginalAnyPHIKind() && Access->isWrite()) {
auto &Incomings = PHIIncomingAccs[Access->getScopArrayInfo()];
std::remove(Incomings.begin(), Incomings.end(), Access);
@@ -4930,11 +4935,7 @@ MemoryAccess *Scop::getValueDef(const ScopArrayInfo *SAI) const {
if (!Val)
return nullptr;
- ScopStmt *Stmt = getStmtFor(Val);
- if (!Stmt)
- return nullptr;
-
- return Stmt->lookupValueWriteOf(Val);
+ return ValueDefAccs.lookup(Val);
}
ArrayRef<MemoryAccess *> Scop::getValueUses(const ScopArrayInfo *SAI) const {
@@ -4952,10 +4953,7 @@ MemoryAccess *Scop::getPHIRead(const ScopArrayInfo *SAI) const {
return nullptr;
PHINode *PHI = cast<PHINode>(SAI->getBasePtr());
- ScopStmt *Stmt = getStmtFor(PHI);
- assert(Stmt && "PHINode must be within the SCoP");
-
- return Stmt->lookupPHIReadOf(PHI);
+ return PHIReadAccs.lookup(PHI);
}
ArrayRef<MemoryAccess *> Scop::getPHIIncomings(const ScopArrayInfo *SAI) const {
diff --git a/polly/test/Simplify/notredundant_synthesizable_unknownit.ll b/polly/test/Simplify/notredundant_synthesizable_unknownit.ll
new file mode 100644
index 00000000000..4dc33deedb7
--- /dev/null
+++ b/polly/test/Simplify/notredundant_synthesizable_unknownit.ll
@@ -0,0 +1,65 @@
+; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+;
+; Do not remove the scalar value write of %i.trunc in inner.for.
+; It is used by body.
+; %i.trunc is synthesizable in inner.for, so some code might think it is
+; synthesizable everywhere such that no scalar write would be needed.
+;
+; Note that -polly-simplify rightfully removes %inner.cond. It should
+; not have been added to the instruction list in the first place.
+;
+define void @func(i32 %n, i32* noalias nonnull %A) {
+entry:
+ br label %for
+
+for:
+ %j = phi i32 [0, %entry], [%j.inc, %inc]
+ %j.cmp = icmp slt i32 %j, %n
+ %zero = sext i32 0 to i64
+ br i1 %j.cmp, label %inner.for, label %exit
+
+
+ ; This loop has some unusual properties:
+ ; * It has a known iteration count (8), therefore SCoP-compatible.
+ ; * %i.trunc is synthesizable within the loop ({1,+,1}<%while.body>).
+ ; * %i.trunc is not synthesizable outside of the loop, because its value is
+ ; unknown when exiting.
+ ; (should be 8, but ScalarEvolution currently seems unable to derive that)
+ ;
+ ; ScalarEvolution currently seems to not able to handle the %zero.
+ ; If it becomes more intelligent, there might be other such loop constructs.
+ inner.for:
+ %i = phi i64 [%zero, %for], [%i.inc, %inner.for]
+ %i.inc = add nuw nsw i64 %i, 1
+ %i.trunc = trunc i64 %i.inc to i32
+ %i.and = and i32 %i.trunc, 7
+ %inner.cond = icmp eq i32 %i.and, 0
+ br i1 %inner.cond, label %body, label %inner.for
+
+ body:
+ store i32 %i.trunc, i32* %A
+ br label %inc
+
+
+inc:
+ %j.inc = add nuw nsw i32 %j, 1
+ br label %for
+
+exit:
+ br label %return
+
+return:
+ ret void
+}
+
+
+; CHECK: After accesses {
+; CHECK-NEXT: Stmt_inner_for
+; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT: [n] -> { Stmt_inner_for[i0, i1] -> MemRef_i_trunc[] };
+; CHECK-NEXT: Stmt_body
+; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT: [n] -> { Stmt_body[i0] -> MemRef_A[0] };
+; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT: [n] -> { Stmt_body[i0] -> MemRef_i_trunc[] };
+; CHECK-NEXT: }
OpenPOWER on IntegriCloud