Index: polly/trunk/include/polly/ScopInfo.h =================================================================== --- polly/trunk/include/polly/ScopInfo.h +++ polly/trunk/include/polly/ScopInfo.h @@ -2744,6 +2744,11 @@ /// 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 Index: polly/trunk/lib/Analysis/ScopBuilder.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopBuilder.cpp +++ polly/trunk/lib/Analysis/ScopBuilder.cpp @@ -140,7 +140,7 @@ 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 @@ /// @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 @@ } } -/// 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 @@ } } -/// 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 @@ 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 @@ // 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 @@ 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) { Index: polly/trunk/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopInfo.cpp +++ polly/trunk/lib/Analysis/ScopInfo.cpp @@ -4823,6 +4823,23 @@ 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()) Index: polly/trunk/test/ScopInfo/granularity_scalar-indep_epilogue.ll =================================================================== --- polly/trunk/test/ScopInfo/granularity_scalar-indep_epilogue.ll +++ polly/trunk/test/ScopInfo/granularity_scalar-indep_epilogue.ll @@ -56,13 +56,13 @@ ; 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: } Index: polly/trunk/test/ScopInfo/granularity_scalar-indep_epilogue_last.ll =================================================================== --- polly/trunk/test/ScopInfo/granularity_scalar-indep_epilogue_last.ll +++ polly/trunk/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 @@ ; 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: }