From 195892e7002fc3461245b22d24a1d6e7e52d5201 Mon Sep 17 00:00:00 2001 From: Michael Kruse Date: Mon, 24 Jul 2017 12:43:27 +0000 Subject: [PATCH] [ForwardOpTree] Support read-only value uses. Read-only values (values defined before the SCoP) require special handing with -polly-analyze-read-only-scalars=true (which is the default). If active, each use of a value requires a read access. When a copied value uses a read-only value, we must also ensure that such a MemoryAccess is available or is created. Differential Revision: https://reviews.llvm.org/D35764 git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@308876 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/polly/ScopBuilder.h | 3 ++ include/polly/ScopInfo.h | 12 +++++ lib/Analysis/ScopBuilder.cpp | 15 +++++- lib/Analysis/ScopInfo.cpp | 16 +++++++ lib/Transform/ForwardOpTree.cpp | 26 +++++++++-- test/ForwardOpTree/forward_readonly.ll | 84 ++++++++++++++++++++++++++++++++++ 6 files changed, 149 insertions(+), 7 deletions(-) create mode 100644 test/ForwardOpTree/forward_readonly.ll diff --git a/include/polly/ScopBuilder.h b/include/polly/ScopBuilder.h index 67a287ff..0b6fa795 100644 --- a/include/polly/ScopBuilder.h +++ b/include/polly/ScopBuilder.h @@ -21,6 +21,9 @@ namespace polly { +/// Command line switch whether to model read-only accesses. +extern bool ModelReadOnlyScalars; + /// Build the Polly IR (Scop and ScopStmt) on a Region. class ScopBuilder { //===-------------------------------------------------------------------===// diff --git a/include/polly/ScopInfo.h b/include/polly/ScopInfo.h index e504444a..8b56b668 100644 --- a/include/polly/ScopInfo.h +++ b/include/polly/ScopInfo.h @@ -1628,6 +1628,18 @@ public: /// void printInstructions(raw_ostream &OS) const; + /// Check whether there is a value read access for @p V in this statement, and + /// if not, create one. + /// + /// This allows to add MemoryAccesses after the initial creation of the Scop + /// by ScopBuilder. + /// + /// @return The already existing or newly created MemoryKind::Value READ + /// MemoryAccess. + /// + /// @see ScopBuilder::ensureValueRead(Value*,ScopStmt*) + MemoryAccess *ensureValueRead(Value *V); + #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) /// Print the ScopStmt to stderr. void dump() const; diff --git a/lib/Analysis/ScopBuilder.cpp b/lib/Analysis/ScopBuilder.cpp index f6b929ab..cf253bfa 100644 --- a/lib/Analysis/ScopBuilder.cpp +++ b/lib/Analysis/ScopBuilder.cpp @@ -32,10 +32,12 @@ STATISTIC(RichScopFound, "Number of Scops containing a loop"); STATISTIC(InfeasibleScops, "Number of SCoPs with statically infeasible context."); -static cl::opt ModelReadOnlyScalars( +bool polly::ModelReadOnlyScalars; +static cl::opt XModelReadOnlyScalars( "polly-analyze-read-only-scalars", cl::desc("Model read-only scalar values in the scop description"), - cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory)); + cl::location(ModelReadOnlyScalars), cl::Hidden, cl::ZeroOrMore, + cl::init(true), cl::cat(PollyCategory)); static cl::opt UnprofitableScalarAccs( "polly-unprofitable-scalar-accs", @@ -778,6 +780,15 @@ void ScopBuilder::ensureValueWrite(Instruction *Inst) { } void ScopBuilder::ensureValueRead(Value *V, ScopStmt *UserStmt) { + // TODO: Make ScopStmt::ensureValueRead(Value*) offer the same functionality + // to be able to replace this one. Currently, there is a split responsibility. + // In a first step, the MemoryAccess is created, but without the + // AccessRelation. In the second step by ScopStmt::buildAccessRelations(), the + // AccessRelation is created. At least for scalar accesses, there is no new + // information available at ScopStmt::buildAccessRelations(), so we could + // create the AccessRelation right away. This is what + // ScopStmt::ensureValueRead(Value*) does. + auto *Scope = UserStmt->getSurroundingLoop(); auto VUse = VirtualUse::create(scop.get(), UserStmt, Scope, V, false); switch (VUse.getKind()) { diff --git a/lib/Analysis/ScopInfo.cpp b/lib/Analysis/ScopInfo.cpp index 6defb4f1..c1a30b9b 100644 --- a/lib/Analysis/ScopInfo.cpp +++ b/lib/Analysis/ScopInfo.cpp @@ -2042,6 +2042,22 @@ void ScopStmt::removeSingleMemoryAccess(MemoryAccess *MA) { } } +MemoryAccess *ScopStmt::ensureValueRead(Value *V) { + MemoryAccess *Access = lookupInputAccessOf(V); + if (Access) + return Access; + + ScopArrayInfo *SAI = + Parent.getOrCreateScopArrayInfo(V, V->getType(), {}, MemoryKind::Value); + Access = new MemoryAccess(this, nullptr, MemoryAccess::READ, V, V->getType(), + true, {}, {}, V, MemoryKind::Value); + Parent.addAccessFunction(Access); + Access->buildAccessRelation(SAI); + addAccess(Access); + Parent.addAccessData(Access); + return Access; +} + raw_ostream &polly::operator<<(raw_ostream &O, const ScopStmt &S) { S.print(O, PollyPrintInstructions); return O; diff --git a/lib/Transform/ForwardOpTree.cpp b/lib/Transform/ForwardOpTree.cpp index e0fd5781..fe5a6311 100644 --- a/lib/Transform/ForwardOpTree.cpp +++ b/lib/Transform/ForwardOpTree.cpp @@ -13,6 +13,7 @@ #include "polly/ForwardOpTree.h" +#include "polly/ScopBuilder.h" #include "polly/ScopInfo.h" #include "polly/ScopPass.h" #include "polly/Support/GICHelper.h" @@ -25,6 +26,7 @@ using namespace polly; using namespace llvm; STATISTIC(TotalInstructionsCopied, "Number of copied instructions"); +STATISTIC(TotalReadOnlyCopied, "Number of copied read-only accesses"); STATISTIC(TotalForwardedTrees, "Number of forwarded operand trees"); STATISTIC(TotalModifiedStmts, "Number of statements with at least one forwarded tree"); @@ -37,6 +39,7 @@ namespace { enum ForwardingDecision { FD_CannotForward, FD_CanForward, + FD_CanForwardTree, FD_DidForward, }; @@ -58,6 +61,9 @@ private: /// How many instructions have been copied to other statements. int NumInstructionsCopied = 0; + /// How many read-only accesses have been copied. + int NumReadOnlyCopied = 0; + /// How many operand trees have been forwarded. int NumForwardedTrees = 0; @@ -71,6 +77,8 @@ private: OS.indent(Indent) << "Statistics {\n"; OS.indent(Indent + 4) << "Instructions copied: " << NumInstructionsCopied << '\n'; + OS.indent(Indent + 4) << "Read-only accesses copied: " << NumReadOnlyCopied + << '\n'; OS.indent(Indent + 4) << "Operand trees forwarded: " << NumForwardedTrees << '\n'; OS.indent(Indent + 4) << "Statements with forwarded operand trees: " @@ -132,9 +140,16 @@ private: return FD_CannotForward; case VirtualUse::ReadOnly: - // Not supported yet. - DEBUG(dbgs() << " Cannot forward read-only val: " << *UseVal << "\n"); - return FD_CannotForward; + if (!DoIt) + return FD_CanForward; + + // If we model read-only scalars, we need to create a MemoryAccess for it. + if (ModelReadOnlyScalars) + TargetStmt->ensureValueRead(UseVal); + + NumReadOnlyCopied++; + TotalReadOnlyCopied++; + return FD_DidForward; case VirtualUse::Intra: case VirtualUse::Inter: @@ -183,6 +198,7 @@ private: return FD_CannotForward; case FD_CanForward: + case FD_CanForwardTree: assert(!DoIt); break; @@ -194,7 +210,7 @@ private: if (DoIt) return FD_DidForward; - return FD_CanForward; + return FD_CanForwardTree; } llvm_unreachable("Case unhandled"); @@ -211,7 +227,7 @@ private: ForwardingDecision Assessment = canForwardTree(Stmt, RA->getAccessValue(), Stmt, InLoop, false); assert(Assessment != FD_DidForward); - if (Assessment == FD_CannotForward) + if (Assessment != FD_CanForwardTree) return false; ForwardingDecision Execution = diff --git a/test/ForwardOpTree/forward_readonly.ll b/test/ForwardOpTree/forward_readonly.ll new file mode 100644 index 00000000..ca514cfc --- /dev/null +++ b/test/ForwardOpTree/forward_readonly.ll @@ -0,0 +1,84 @@ +; RUN: opt %loadPolly -polly-analyze-read-only-scalars=true -polly-optree -analyze < %s | FileCheck %s -match-full-lines -check-prefixes=STATS,MODEL +; RUN: opt %loadPolly -polly-analyze-read-only-scalars=false -polly-optree -analyze < %s | FileCheck %s -match-full-lines -check-prefixes=STATS,NOMODEL +; +; Move %val to %bodyB, so %bodyA can be removed (by -polly-simplify) +; +; for (int j = 0; j < n; j += 1) { +; bodyA: +; double val = arg + 21.0; +; +; bodyB: +; A[0] = val; +; } +; +define void @func(i32 %n, double* noalias nonnull %A, double %arg) { +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: + %val = fadd double %arg, 21.0 + br label %bodyB + + bodyB: + 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 +} + + +; STATS: Statistics { +; STATS: Instructions copied: 1 +; STATS: Read-only accesses copied: 1 +; STATS: Operand trees forwarded: 1 +; STATS: Statements with forwarded operand trees: 1 +; STATS: } + +; MODEL: After statements { +; MODEL-NEXT: Stmt_bodyA +; MODEL-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; MODEL-NEXT: [n] -> { Stmt_bodyA[i0] -> MemRef_arg[] }; +; MODEL-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; MODEL-NEXT: [n] -> { Stmt_bodyA[i0] -> MemRef_val[] }; +; MODEL-NEXT: Instructions { +; MODEL-NEXT: %val = fadd double %arg, 2.100000e+01 +; MODEL-NEXT: } +; MODEL-NEXT: Stmt_bodyB +; MODEL-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; MODEL-NEXT: [n] -> { Stmt_bodyB[i0] -> MemRef_A[0] }; +; MODEL-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 1] +; MODEL-NEXT: [n] -> { Stmt_bodyB[i0] -> MemRef_arg[] }; +; MODEL-NEXT: Instructions { +; MODEL-NEXT: %val = fadd double %arg, 2.100000e+01 +; MODEL-NEXT: store double %val, double* %A +; MODEL-NEXT: } +; MODEL-NEXT: } + +; NOMODEL: After statements { +; NOMODEL-NEXT: Stmt_bodyA +; NOMODEL-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; NOMODEL-NEXT: [n] -> { Stmt_bodyA[i0] -> MemRef_val[] }; +; NOMODEL-NEXT: Instructions { +; NOMODEL-NEXT: %val = fadd double %arg, 2.100000e+01 +; NOMODEL-NEXT: } +; NOMODEL-NEXT: Stmt_bodyB +; NOMODEL-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; NOMODEL-NEXT: [n] -> { Stmt_bodyB[i0] -> MemRef_A[0] }; +; NOMODEL-NEXT: Instructions { +; NOMODEL-NEXT: %val = fadd double %arg, 2.100000e+01 +; NOMODEL-NEXT: store double %val, double* %A +; NOMODEL-NEXT: } +; NOMODEL-NEXT: } -- 2.11.4.GIT