From 2d3f56beb5f500d48d499bfdef431f0d80d590a1 Mon Sep 17 00:00:00 2001 From: Michael Kruse Date: Thu, 21 Sep 2017 14:23:11 +0000 Subject: [PATCH] [ScopInfo] Use map for value def/PHI read accesses. Before this patch, ScopInfo::getValueDef(SAI) used getStmtFor(Instruction*) to find the MemoryAccess that writes a MemoryKind::Value. In cases where the value is synthesizable within the statement that defines, the instruction is not added to the statement's instruction list, which means getStmtFor() won't return anything. If the synthesiable instruction is not synthesiable in a different statement (due to being defined in a loop that and ScalarEvolution cannot derive its escape value), we still need a MemoryKind::Value and a write to it that makes it available in the other statements. Introduce a separate map for this purpose. This fixes MultiSource/Benchmarks/MallocBench/cfrac where -polly-simplify could not find the writing MemoryAccess for a use. The write was not marked as required and consequently was removed. Because this could in principle happen as well for PHI scalars, add such a map for PHI reads as well. git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@313881 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/polly/ScopInfo.h | 20 +++++++ lib/Analysis/ScopInfo.cpp | 18 +++--- .../notredundant_synthesizable_unknownit.ll | 65 ++++++++++++++++++++++ 3 files changed, 93 insertions(+), 10 deletions(-) create mode 100644 test/Simplify/notredundant_synthesizable_unknownit.ll diff --git a/include/polly/ScopInfo.h b/include/polly/ScopInfo.h index df20ac53..e61b8a1f 100644 --- a/include/polly/ScopInfo.h +++ b/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 ValueDefAccs; + + /// Map of values to the MemoryAccess that reads a PHI. + DenseMap PHIReadAccs; + /// List of all uses (i.e. read MemoryAccesses) for a MemoryKind::Value /// scalar. DenseMap> 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(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/lib/Analysis/ScopInfo.cpp b/lib/Analysis/ScopInfo.cpp index 29860925..01cca27d 100644 --- a/lib/Analysis/ScopInfo.cpp +++ b/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(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 Scop::getValueUses(const ScopArrayInfo *SAI) const { @@ -4952,10 +4953,7 @@ MemoryAccess *Scop::getPHIRead(const ScopArrayInfo *SAI) const { return nullptr; PHINode *PHI = cast(SAI->getBasePtr()); - ScopStmt *Stmt = getStmtFor(PHI); - assert(Stmt && "PHINode must be within the SCoP"); - - return Stmt->lookupPHIReadOf(PHI); + return PHIReadAccs.lookup(PHI); } ArrayRef Scop::getPHIIncomings(const ScopArrayInfo *SAI) const { diff --git a/test/Simplify/notredundant_synthesizable_unknownit.ll b/test/Simplify/notredundant_synthesizable_unknownit.ll new file mode 100644 index 00000000..4dc33dee --- /dev/null +++ b/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: } -- 2.11.4.GIT