Index: polly/trunk/include/polly/ScopBuilder.h =================================================================== --- polly/trunk/include/polly/ScopBuilder.h +++ polly/trunk/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 { //===-------------------------------------------------------------------===// Index: polly/trunk/include/polly/ScopInfo.h =================================================================== --- polly/trunk/include/polly/ScopInfo.h +++ polly/trunk/include/polly/ScopInfo.h @@ -1628,6 +1628,18 @@ /// 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; Index: polly/trunk/lib/Analysis/ScopBuilder.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopBuilder.cpp +++ polly/trunk/lib/Analysis/ScopBuilder.cpp @@ -32,10 +32,12 @@ 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::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()) { Index: polly/trunk/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopInfo.cpp +++ polly/trunk/lib/Analysis/ScopInfo.cpp @@ -2042,6 +2042,22 @@ } } +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; Index: polly/trunk/lib/Transform/ForwardOpTree.cpp =================================================================== --- polly/trunk/lib/Transform/ForwardOpTree.cpp +++ polly/trunk/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 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 @@ enum ForwardingDecision { FD_CannotForward, FD_CanForward, + FD_CanForwardTree, FD_DidForward, }; @@ -58,6 +61,9 @@ /// 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 @@ 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 @@ 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 @@ return FD_CannotForward; case FD_CanForward: + case FD_CanForwardTree: assert(!DoIt); break; @@ -194,7 +210,7 @@ if (DoIt) return FD_DidForward; - return FD_CanForward; + return FD_CanForwardTree; } llvm_unreachable("Case unhandled"); @@ -211,7 +227,7 @@ 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 = Index: polly/trunk/test/ForwardOpTree/forward_readonly.ll =================================================================== --- polly/trunk/test/ForwardOpTree/forward_readonly.ll +++ polly/trunk/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: }