Index: llvm/trunk/include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Utils/LoopUtils.h +++ llvm/trunk/include/llvm/Transforms/Utils/LoopUtils.h @@ -323,6 +323,20 @@ BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA); +/// Ensures LCSSA form for every instruction from the Worklist in the scope of +/// innermost containing loop. +/// +/// For the given instruction which have uses outside of the loop, an LCSSA PHI +/// node is inserted and the uses outside the loop are rewritten to use this +/// node. +/// +/// LoopInfo and DominatorTree are required and, since the routine makes no +/// changes to CFG, preserved. +/// +/// Returns true if any modifications are made. +bool formLCSSAForInstructions(SmallVectorImpl &Worklist, + DominatorTree &DT, LoopInfo &LI); + /// \brief Put loop into LCSSA form. /// /// Looks at all instructions in the loop which have uses outside of the Index: llvm/trunk/lib/Transforms/Utils/LCSSA.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/LCSSA.cpp +++ llvm/trunk/lib/Transforms/Utils/LCSSA.cpp @@ -57,148 +57,153 @@ return find(ExitBlocks, BB) != ExitBlocks.end(); } -/// Given an instruction in the loop, check to see if it has any uses that are -/// outside the current loop. If so, insert LCSSA PHI nodes and rewrite the -/// uses. -static bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT, - const SmallVectorImpl &ExitBlocks, - PredIteratorCache &PredCache, LoopInfo *LI) { +/// For every instruction from the worklist, check to see if it has any uses +/// that are outside the current loop. If so, insert LCSSA PHI nodes and +/// rewrite the uses. +bool llvm::formLCSSAForInstructions(SmallVectorImpl &Worklist, + DominatorTree &DT, LoopInfo &LI) { SmallVector UsesToRewrite; + SmallVector ExitBlocks; + PredIteratorCache PredCache; + bool Changed = false; - // Tokens cannot be used in PHI nodes, so we skip over them. - // We can run into tokens which are live out of a loop with catchswitch - // instructions in Windows EH if the catchswitch has one catchpad which - // is inside the loop and another which is not. - if (Inst.getType()->isTokenTy()) - return false; - - BasicBlock *InstBB = Inst.getParent(); + while (!Worklist.empty()) { + UsesToRewrite.clear(); + ExitBlocks.clear(); + + Instruction *I = Worklist.pop_back_val(); + BasicBlock *InstBB = I->getParent(); + Loop *L = LI.getLoopFor(InstBB); + L->getExitBlocks(ExitBlocks); - for (Use &U : Inst.uses()) { - Instruction *User = cast(U.getUser()); - BasicBlock *UserBB = User->getParent(); - if (PHINode *PN = dyn_cast(User)) - UserBB = PN->getIncomingBlock(U); + if (ExitBlocks.empty()) + continue; - if (InstBB != UserBB && !L.contains(UserBB)) - UsesToRewrite.push_back(&U); - } + // Tokens cannot be used in PHI nodes, so we skip over them. + // We can run into tokens which are live out of a loop with catchswitch + // instructions in Windows EH if the catchswitch has one catchpad which + // is inside the loop and another which is not. + if (I->getType()->isTokenTy()) + continue; - // If there are no uses outside the loop, exit with no change. - if (UsesToRewrite.empty()) - return false; + for (Use &U : I->uses()) { + Instruction *User = cast(U.getUser()); + BasicBlock *UserBB = User->getParent(); + if (PHINode *PN = dyn_cast(User)) + UserBB = PN->getIncomingBlock(U); - ++NumLCSSA; // We are applying the transformation + if (InstBB != UserBB && !L->contains(UserBB)) + UsesToRewrite.push_back(&U); + } - // Invoke instructions are special in that their result value is not available - // along their unwind edge. The code below tests to see whether DomBB - // dominates the value, so adjust DomBB to the normal destination block, - // which is effectively where the value is first usable. - BasicBlock *DomBB = Inst.getParent(); - if (InvokeInst *Inv = dyn_cast(&Inst)) - DomBB = Inv->getNormalDest(); - - DomTreeNode *DomNode = DT.getNode(DomBB); - - SmallVector AddedPHIs; - SmallVector PostProcessPHIs; - - SSAUpdater SSAUpdate; - SSAUpdate.Initialize(Inst.getType(), Inst.getName()); - - // Insert the LCSSA phi's into all of the exit blocks dominated by the - // value, and add them to the Phi's map. - for (BasicBlock *ExitBB : ExitBlocks) { - if (!DT.dominates(DomNode, DT.getNode(ExitBB))) + // If there are no uses outside the loop, exit with no change. + if (UsesToRewrite.empty()) continue; - // If we already inserted something for this BB, don't reprocess it. - if (SSAUpdate.HasValueForBlock(ExitBB)) - continue; + ++NumLCSSA; // We are applying the transformation - PHINode *PN = PHINode::Create(Inst.getType(), PredCache.size(ExitBB), - Inst.getName() + ".lcssa", &ExitBB->front()); + // Invoke instructions are special in that their result value is not + // available along their unwind edge. The code below tests to see whether + // DomBB dominates the value, so adjust DomBB to the normal destination + // block, which is effectively where the value is first usable. + BasicBlock *DomBB = InstBB; + if (InvokeInst *Inv = dyn_cast(I)) + DomBB = Inv->getNormalDest(); + + DomTreeNode *DomNode = DT.getNode(DomBB); + + SmallVector AddedPHIs; + SmallVector PostProcessPHIs; + + SSAUpdater SSAUpdate; + SSAUpdate.Initialize(I->getType(), I->getName()); + + // Insert the LCSSA phi's into all of the exit blocks dominated by the + // value, and add them to the Phi's map. + for (BasicBlock *ExitBB : ExitBlocks) { + if (!DT.dominates(DomNode, DT.getNode(ExitBB))) + continue; - // Add inputs from inside the loop for this PHI. - for (BasicBlock *Pred : PredCache.get(ExitBB)) { - PN->addIncoming(&Inst, Pred); - - // If the exit block has a predecessor not within the loop, arrange for - // the incoming value use corresponding to that predecessor to be - // rewritten in terms of a different LCSSA PHI. - if (!L.contains(Pred)) - UsesToRewrite.push_back( - &PN->getOperandUse(PN->getOperandNumForIncomingValue( - PN->getNumIncomingValues() - 1))); - } + // If we already inserted something for this BB, don't reprocess it. + if (SSAUpdate.HasValueForBlock(ExitBB)) + continue; - AddedPHIs.push_back(PN); + PHINode *PN = PHINode::Create(I->getType(), PredCache.size(ExitBB), + I->getName() + ".lcssa", &ExitBB->front()); - // Remember that this phi makes the value alive in this block. - SSAUpdate.AddAvailableValue(ExitBB, PN); + // Add inputs from inside the loop for this PHI. + for (BasicBlock *Pred : PredCache.get(ExitBB)) { + PN->addIncoming(I, Pred); + + // If the exit block has a predecessor not within the loop, arrange for + // the incoming value use corresponding to that predecessor to be + // rewritten in terms of a different LCSSA PHI. + if (!L->contains(Pred)) + UsesToRewrite.push_back( + &PN->getOperandUse(PN->getOperandNumForIncomingValue( + PN->getNumIncomingValues() - 1))); + } + + AddedPHIs.push_back(PN); + + // Remember that this phi makes the value alive in this block. + SSAUpdate.AddAvailableValue(ExitBB, PN); + + // LoopSimplify might fail to simplify some loops (e.g. when indirect + // branches are involved). In such situations, it might happen that an + // exit for Loop L1 is the header of a disjoint Loop L2. Thus, when we + // create PHIs in such an exit block, we are also inserting PHIs into L2's + // header. This could break LCSSA form for L2 because these inserted PHIs + // can also have uses outside of L2. Remember all PHIs in such situation + // as to revisit than later on. FIXME: Remove this if indirectbr support + // into LoopSimplify gets improved. + if (auto *OtherLoop = LI.getLoopFor(ExitBB)) + if (!L->contains(OtherLoop)) + PostProcessPHIs.push_back(PN); + } - // LoopSimplify might fail to simplify some loops (e.g. when indirect - // branches are involved). In such situations, it might happen that an exit - // for Loop L1 is the header of a disjoint Loop L2. Thus, when we create - // PHIs in such an exit block, we are also inserting PHIs into L2's header. - // This could break LCSSA form for L2 because these inserted PHIs can also - // have uses outside of L2. Remember all PHIs in such situation as to - // revisit than later on. FIXME: Remove this if indirectbr support into - // LoopSimplify gets improved. - if (auto *OtherLoop = LI->getLoopFor(ExitBB)) - if (!L.contains(OtherLoop)) - PostProcessPHIs.push_back(PN); - } + // Rewrite all uses outside the loop in terms of the new PHIs we just + // inserted. + for (Use *UseToRewrite : UsesToRewrite) { + // If this use is in an exit block, rewrite to use the newly inserted PHI. + // This is required for correctness because SSAUpdate doesn't handle uses + // in the same block. It assumes the PHI we inserted is at the end of the + // block. + Instruction *User = cast(UseToRewrite->getUser()); + BasicBlock *UserBB = User->getParent(); + if (PHINode *PN = dyn_cast(User)) + UserBB = PN->getIncomingBlock(*UseToRewrite); + + if (isa(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) { + // Tell the VHs that the uses changed. This updates SCEV's caches. + if (UseToRewrite->get()->hasValueHandle()) + ValueHandleBase::ValueIsRAUWd(*UseToRewrite, &UserBB->front()); + UseToRewrite->set(&UserBB->front()); + continue; + } - // Rewrite all uses outside the loop in terms of the new PHIs we just - // inserted. - for (Use *UseToRewrite : UsesToRewrite) { - // If this use is in an exit block, rewrite to use the newly inserted PHI. - // This is required for correctness because SSAUpdate doesn't handle uses in - // the same block. It assumes the PHI we inserted is at the end of the - // block. - Instruction *User = cast(UseToRewrite->getUser()); - BasicBlock *UserBB = User->getParent(); - if (PHINode *PN = dyn_cast(User)) - UserBB = PN->getIncomingBlock(*UseToRewrite); - - if (isa(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) { - // Tell the VHs that the uses changed. This updates SCEV's caches. - if (UseToRewrite->get()->hasValueHandle()) - ValueHandleBase::ValueIsRAUWd(*UseToRewrite, &UserBB->front()); - UseToRewrite->set(&UserBB->front()); - continue; + // Otherwise, do full PHI insertion. + SSAUpdate.RewriteUse(*UseToRewrite); } - // Otherwise, do full PHI insertion. - SSAUpdate.RewriteUse(*UseToRewrite); - } + // Post process PHI instructions that were inserted into another disjoint + // loop and update their exits properly. + for (auto *PostProcessPN : PostProcessPHIs) { + if (PostProcessPN->use_empty()) + continue; - // Post process PHI instructions that were inserted into another disjoint loop - // and update their exits properly. - for (auto *I : PostProcessPHIs) { - if (I->use_empty()) - continue; + // Reprocess each PHI instruction. + Worklist.push_back(PostProcessPN); + } - BasicBlock *PHIBB = I->getParent(); - Loop *OtherLoop = LI->getLoopFor(PHIBB); - SmallVector EBs; - OtherLoop->getExitBlocks(EBs); - if (EBs.empty()) - continue; + // Remove PHI nodes that did not have any uses rewritten. + for (PHINode *PN : AddedPHIs) + if (PN->use_empty()) + PN->eraseFromParent(); - // Recurse and re-process each PHI instruction. FIXME: we should really - // convert this entire thing to a worklist approach where we process a - // vector of instructions... - processInstruction(*OtherLoop, *I, DT, EBs, PredCache, LI); + Changed = true; } - - // Remove PHI nodes that did not have any uses rewritten. - for (PHINode *PN : AddedPHIs) - if (PN->use_empty()) - PN->eraseFromParent(); - - return true; + return Changed; } /// Return true if the specified block dominates at least @@ -224,10 +229,10 @@ if (ExitBlocks.empty()) return false; - PredIteratorCache PredCache; + SmallVector Worklist; // Look at all the instructions in the loop, checking to see if they have uses - // outside the loop. If so, rewrite those uses. + // outside the loop. If so, put them into the worklist to rewrite those uses. for (BasicBlock *BB : L.blocks()) { // For large loops, avoid use-scanning by using dominance information: In // particular, if a block does not dominate any of the loop exits, then none @@ -243,9 +248,10 @@ !isa(I.user_back()))) continue; - Changed |= processInstruction(L, I, DT, ExitBlocks, PredCache, LI); + Worklist.push_back(&I); } } + Changed = formLCSSAForInstructions(Worklist, DT, *LI); // If we modified the code, remove any caches about the loop from SCEV to // avoid dangling entries.