From 3fb336f4df16381ecf955d298c965c3d5614bc92 Mon Sep 17 00:00:00 2001 From: Michael Kruse Date: Tue, 23 Jan 2018 23:56:36 +0000 Subject: [PATCH] [ScopBuilder] Prefer PHI Write accesses in the statement the incoming value is defined. Theoretically, a PHI write can be added to any statement that represents the incoming basic block. We previously always chose the last because the incoming value's definition is guaranteed to be defined. With this patch the PHI write is added to the statement that defines the incoming value. It avoids the requirement for a scalar dependency between the defining statement and the statement containing the write. As such the logic for -polly-stmt-granularity=scalar-indep that ensures that there is such scalar dependencies can be removed. Differential Revision: https://reviews.llvm.org/D42147 git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@323284 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/polly/ScopInfo.h | 5 ++ lib/Analysis/ScopBuilder.cpp | 79 ++++------------------ lib/Analysis/ScopInfo.cpp | 17 +++++ test/ScopInfo/granularity_scalar-indep_epilogue.ll | 8 +-- .../granularity_scalar-indep_epilogue_last.ll | 22 +++--- 5 files changed, 53 insertions(+), 78 deletions(-) diff --git a/include/polly/ScopInfo.h b/include/polly/ScopInfo.h index dadaa300..8f66d050 100644 --- a/include/polly/ScopInfo.h +++ b/include/polly/ScopInfo.h @@ -2744,6 +2744,11 @@ public: /// Return the list of ScopStmts that represent the given @p BB. ArrayRef getStmtListFor(BasicBlock *BB) const; + /// Get the statement to put a PHI WRITE into. + /// + /// @param U The operand of a PHINode. + ScopStmt *getIncomingStmtFor(const Use &U) const; + /// Return the last statement representing @p BB. /// /// Of the sequence of statements that represent a @p BB, this is the last one diff --git a/lib/Analysis/ScopBuilder.cpp b/lib/Analysis/ScopBuilder.cpp index 6831bf1b..794e6d84 100644 --- a/lib/Analysis/ScopBuilder.cpp +++ b/lib/Analysis/ScopBuilder.cpp @@ -140,7 +140,7 @@ void ScopBuilder::buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI, for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) { Value *Op = PHI->getIncomingValue(u); BasicBlock *OpBB = PHI->getIncomingBlock(u); - ScopStmt *OpStmt = scop->getLastStmtFor(OpBB); + ScopStmt *OpStmt = scop->getIncomingStmtFor(PHI->getOperandUse(u)); // Do not build PHI dependences inside a non-affine subregion, but make // sure that the necessary scalar values are still made available. @@ -696,13 +696,16 @@ bool ScopBuilder::shouldModelInst(Instruction *Inst, Loop *L) { /// @param Count The index of the created statement in @p BB. /// @param IsMain Whether this is the main of all statement for @p BB. If true, /// no suffix will be added. +/// @param IsLast Uses a special indicator for the last statement of a BB. static std::string makeStmtName(BasicBlock *BB, long BBIdx, int Count, - bool IsMain) { + bool IsMain, bool IsLast = false) { std::string Suffix; if (!IsMain) { if (UseInstructionNames) Suffix = '_'; - if (Count < 26) + if (IsLast) + Suffix += "last"; + else if (Count < 26) Suffix += 'a' + Count; else Suffix += std::to_string(Count); @@ -773,32 +776,6 @@ static void joinOperandTree(EquivalenceClasses &UnionFind, } } -/// Join instructions that are used as incoming value in successor PHIs into the -/// epilogue. -static void -joinIncomingPHIValuesIntoEpilogue(EquivalenceClasses &UnionFind, - ArrayRef ModeledInsts, - BasicBlock *BB) { - for (BasicBlock *Succ : successors(BB)) { - for (Instruction &SuccInst : *Succ) { - PHINode *SuccPHI = dyn_cast(&SuccInst); - if (!SuccPHI) - break; - - Value *IncomingVal = SuccPHI->getIncomingValueForBlock(BB); - Instruction *IncomingInst = dyn_cast(IncomingVal); - if (!IncomingInst) - continue; - if (IncomingInst->getParent() != BB) - continue; - if (UnionFind.findValue(IncomingInst) == UnionFind.end()) - continue; - - UnionFind.unionSets(nullptr, IncomingInst); - } - } -} - /// Ensure that the order of ordered instructions does not change. /// /// If we encounter an ordered instruction enclosed in instructions belonging to @@ -832,29 +809,6 @@ joinOrderedInstructions(EquivalenceClasses &UnionFind, } } -/// Also ensure that the epilogue is the last statement relative to all ordered -/// instructions. -/// -/// This is basically joinOrderedInstructions() but using the epilogue as -/// 'ordered instruction'. -static void joinAllAfterEpilogue(EquivalenceClasses &UnionFind, - ArrayRef ModeledInsts) { - bool EpilogueSeen = false; - for (Instruction *Inst : ModeledInsts) { - auto PHIWritesLeader = UnionFind.findLeader(nullptr); - auto InstLeader = UnionFind.findLeader(Inst); - - if (PHIWritesLeader == InstLeader) - EpilogueSeen = true; - - if (!isOrderedInstruction(Inst)) - continue; - - if (EpilogueSeen) - UnionFind.unionSets(PHIWritesLeader, InstLeader); - } -} - void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) { Loop *L = LI.getLoopFor(BB); @@ -879,19 +833,8 @@ void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) { MainInst = &Inst; } - // 'nullptr' represents the last statement for a basic block. It contains no - // instructions, but holds the PHI write accesses for successor basic blocks. - // If a PHI has an incoming value defined in this BB, it can also be merged - // with other statements. - // TODO: We wouldn't need this if we would add PHIWrites into the statement - // that defines the incoming value (if in the BB) instead of always the last, - // so we could unconditionally always add a last statement. - UnionFind.insert(nullptr); - joinOperandTree(UnionFind, ModeledInsts); - joinIncomingPHIValuesIntoEpilogue(UnionFind, ModeledInsts, BB); joinOrderedInstructions(UnionFind, ModeledInsts); - joinAllAfterEpilogue(UnionFind, ModeledInsts); // The list of instructions for statement (statement represented by the leader // instruction). The order of statements instructions is reversed such that @@ -899,9 +842,6 @@ void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) { // the last statement. MapVector> LeaderToInstList; - // Ensure that the epilogue is last. - LeaderToInstList[nullptr]; - // Collect the instructions of all leaders. UnionFind's member iterator // unfortunately are not in any specific order. for (Instruction &Inst : reverse(*BB)) { @@ -932,6 +872,13 @@ void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) { scop->addScopStmt(BB, Name, L, std::move(InstList)); Count += 1; } + + // Unconditionally add an epilogue (last statement). It contains no + // instructions, but holds the PHI write accesses for successor basic blocks, + // if the incoming value is not defined in another statement if the same BB. + // The epilogue will be removed if no PHIWrite is added to it. + std::string EpilogueName = makeStmtName(BB, BBIdx, Count, false, true); + scop->addScopStmt(BB, EpilogueName, L, {}); } void ScopBuilder::buildStmts(Region &SR) { diff --git a/lib/Analysis/ScopInfo.cpp b/lib/Analysis/ScopInfo.cpp index 9ecf301b..c8d3f6b5 100644 --- a/lib/Analysis/ScopInfo.cpp +++ b/lib/Analysis/ScopInfo.cpp @@ -4823,6 +4823,23 @@ ArrayRef Scop::getStmtListFor(BasicBlock *BB) const { return StmtMapIt->second; } +ScopStmt *Scop::getIncomingStmtFor(const Use &U) const { + auto *PHI = cast(U.getUser()); + BasicBlock *IncomingBB = PHI->getIncomingBlock(U); + + // If the value is a non-synthesizable from the incoming block, use the + // statement that contains it as user statement. + if (auto *IncomingInst = dyn_cast(U.get())) { + if (IncomingInst->getParent() == IncomingBB) { + if (ScopStmt *IncomingStmt = getStmtFor(IncomingInst)) + return IncomingStmt; + } + } + + // Otherwise, use the epilogue/last statement. + return getLastStmtFor(IncomingBB); +} + ScopStmt *Scop::getLastStmtFor(BasicBlock *BB) const { ArrayRef StmtList = getStmtListFor(BB); if (!StmtList.empty()) diff --git a/test/ScopInfo/granularity_scalar-indep_epilogue.ll b/test/ScopInfo/granularity_scalar-indep_epilogue.ll index f2cb4bfb..a3e6ff3e 100644 --- a/test/ScopInfo/granularity_scalar-indep_epilogue.ll +++ b/test/ScopInfo/granularity_scalar-indep_epilogue.ll @@ -56,13 +56,13 @@ return: ; CHECK-NEXT: %valA = load double, double* %A ; CHECK-NEXT: store double %valA, double* %A ; CHECK-NEXT: } -; CHECK-NEXT: Stmt_bodyA_b +; CHECK-NEXT: Stmt_bodyA_last ; CHECK-NEXT: Domain := -; CHECK-NEXT: [n] -> { Stmt_bodyA_b[i0] : 0 <= i0 < n }; +; CHECK-NEXT: [n] -> { Stmt_bodyA_last[i0] : 0 <= i0 < n }; ; CHECK-NEXT: Schedule := -; CHECK-NEXT: [n] -> { Stmt_bodyA_b[i0] -> [i0, 1] }; +; CHECK-NEXT: [n] -> { Stmt_bodyA_last[i0] -> [i0, 1] }; ; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] -; CHECK-NEXT: [n] -> { Stmt_bodyA_b[i0] -> MemRef_phi__phi[] }; +; CHECK-NEXT: [n] -> { Stmt_bodyA_last[i0] -> MemRef_phi__phi[] }; ; CHECK-NEXT: Instructions { ; CHECK-NEXT: } ; CHECK-NEXT: } diff --git a/test/ScopInfo/granularity_scalar-indep_epilogue_last.ll b/test/ScopInfo/granularity_scalar-indep_epilogue_last.ll index 3c292927..24aa22a9 100644 --- a/test/ScopInfo/granularity_scalar-indep_epilogue_last.ll +++ b/test/ScopInfo/granularity_scalar-indep_epilogue_last.ll @@ -1,8 +1,7 @@ ; RUN: opt %loadPolly -polly-stmt-granularity=scalar-indep -polly-print-instructions -polly-scops -analyze < %s | FileCheck %s -match-full-lines ; -; Check that the statement where the PHI writes are in always comes last. -; Otherwise we'd need to introduce a scalar dependency from the statement -; defining a value to the last statement of a basic block. +; Check that the PHI Write of value that is defined in the same basic +; block is in the statement where it is defined. ; ; for (int j = 0; j < n; j += 1) { ; bodyA: @@ -52,20 +51,27 @@ return: ; CHECK-NEXT: Domain := ; CHECK-NEXT: [n] -> { Stmt_bodyA[i0] : 0 <= i0 < n }; ; CHECK-NEXT: Schedule := -; CHECK-NEXT: [n] -> { Stmt_bodyA[i0] -> [i0] }; +; CHECK-NEXT: [n] -> { Stmt_bodyA[i0] -> [i0, 0] }; ; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] ; CHECK-NEXT: [n] -> { Stmt_bodyA[i0] -> MemRef_A[0] }; ; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] ; CHECK-NEXT: [n] -> { Stmt_bodyA[i0] -> MemRef_A[0] }; -; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] -; CHECK-NEXT: [n] -> { Stmt_bodyA[i0] -> MemRef_B[0] }; -; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] -; CHECK-NEXT: [n] -> { Stmt_bodyA[i0] -> MemRef_B[0] }; ; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] ; CHECK-NEXT: [n] -> { Stmt_bodyA[i0] -> MemRef_phi__phi[] }; ; CHECK-NEXT: Instructions { ; CHECK-NEXT: %valA = load double, double* %A ; CHECK-NEXT: store double %valA, double* %A +; CHECK-NEXT: } +; CHECK-NEXT: Stmt_bodyA_b +; CHECK-NEXT: Domain := +; CHECK-NEXT: [n] -> { Stmt_bodyA_b[i0] : 0 <= i0 < n }; +; CHECK-NEXT: Schedule := +; CHECK-NEXT: [n] -> { Stmt_bodyA_b[i0] -> [i0, 1] }; +; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [n] -> { Stmt_bodyA_b[i0] -> MemRef_B[0] }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [n] -> { Stmt_bodyA_b[i0] -> MemRef_B[0] }; +; CHECK-NEXT: Instructions { ; CHECK-NEXT: %valB = load double, double* %B ; CHECK-NEXT: store double %valB, double* %B ; CHECK-NEXT: } -- 2.11.4.GIT