Index: lib/Analysis/ScopBuilder.cpp =================================================================== --- lib/Analysis/ScopBuilder.cpp +++ lib/Analysis/ScopBuilder.cpp @@ -139,7 +139,14 @@ 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 = nullptr; + if (Instruction *OpInst = dyn_cast(Op)) { + if (OpInst->getParent() == OpBB) + OpStmt = scop->getStmtFor(OpInst); + } + if (!OpStmt) + OpStmt = scop->getLastStmtFor(OpBB); // Do not build PHI dependences inside a non-affine subregion, but make // sure that the necessary scalar values are still made available. @@ -739,32 +746,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 @@ -798,29 +779,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); @@ -835,19 +793,8 @@ UnionFind.insert(&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 @@ -855,9 +802,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)) { @@ -877,6 +821,12 @@ scop->addScopStmt(BB, L, std::move(InstList), Count); 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. + scop->addScopStmt(BB, L, {}, Count); } void ScopBuilder::buildStmts(Region &SR) { Index: test/ScopInfo/granularity_scalar-indep_epilogue_last.ll =================================================================== --- test/ScopInfo/granularity_scalar-indep_epilogue_last.ll +++ 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_bodyA1 +; CHECK-NEXT: Domain := +; CHECK-NEXT: [n] -> { Stmt_bodyA1[i0] : 0 <= i0 < n }; +; CHECK-NEXT: Schedule := +; CHECK-NEXT: [n] -> { Stmt_bodyA1[i0] -> [i0, 1] }; +; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [n] -> { Stmt_bodyA1[i0] -> MemRef_B[0] }; +; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0] +; CHECK-NEXT: [n] -> { Stmt_bodyA1[i0] -> MemRef_B[0] }; +; CHECK-NEXT: Instructions { ; CHECK-NEXT: %valB = load double, double* %B ; CHECK-NEXT: store double %valB, double* %B ; CHECK-NEXT: }