Index: include/llvm/Transforms/Utils/BasicBlockUtils.h =================================================================== --- include/llvm/Transforms/Utils/BasicBlockUtils.h +++ include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -33,6 +33,7 @@ class LoopInfo; class MDNode; class MemoryDependenceResults; +class PostDominatorTree; class ReturnInst; class TargetLibraryInfo; class Value; @@ -193,13 +194,14 @@ /// It will have Suffix+".split_lp". See SplitLandingPadPredecessors for more /// details on this case. /// -/// This currently updates the LLVM IR, DominatorTree, LoopInfo, and LCCSA but -/// no other analyses. In particular, it does not preserve LoopSimplify -/// (because it's complicated to handle the case where one of the edges being -/// split is an exit of a loop with other exits). +/// This currently updates the LLVM IR, DominatorTree, PostDominatorTree, +/// LoopInfo, and LCCSA but no other analyses. In particular, it does not +/// preserve LoopSimplify (because it's complicated to handle the case where one +/// of the edges being split is an exit of a loop with other exits). BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef Preds, const char *Suffix, DominatorTree *DT = nullptr, + PostDominatorTree *PDT = nullptr, LoopInfo *LI = nullptr, bool PreserveLCSSA = false); @@ -214,13 +216,11 @@ /// no other analyses. In particular, it does not preserve LoopSimplify /// (because it's complicated to handle the case where one of the edges being /// split is an exit of a loop with other exits). -void SplitLandingPadPredecessors(BasicBlock *OrigBB, - ArrayRef Preds, - const char *Suffix, const char *Suffix2, - SmallVectorImpl &NewBBs, - DominatorTree *DT = nullptr, - LoopInfo *LI = nullptr, - bool PreserveLCSSA = false); +void SplitLandingPadPredecessors( + BasicBlock *OrigBB, ArrayRef Preds, const char *Suffix, + const char *Suffix2, SmallVectorImpl &NewBBs, + DominatorTree *DT = nullptr, PostDominatorTree *PDT = nullptr, + LoopInfo *LI = nullptr, bool PreserveLCSSA = false); /// This method duplicates the specified return instruction into a predecessor /// which ends in an unconditional branch. If the return instruction returns a Index: include/llvm/Transforms/Utils/LoopSimplify.h =================================================================== --- include/llvm/Transforms/Utils/LoopSimplify.h +++ include/llvm/Transforms/Utils/LoopSimplify.h @@ -46,6 +46,8 @@ namespace llvm { +class PostDominatorTree; + /// This pass is responsible for loop canonicalization. class LoopSimplifyPass : public PassInfoMixin { public: @@ -57,8 +59,9 @@ /// This takes a potentially un-simplified loop L (and its children) and turns /// it into a simplified loop nest with preheaders and single backedges. It will /// update \c AliasAnalysis and \c ScalarEvolution analyses if they're non-null. -bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, - AssumptionCache *AC, bool PreserveLCSSA); +bool simplifyLoop(Loop *L, DominatorTree *DT, PostDominatorTree *PDT, + LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, + bool PreserveLCSSA); } // end namespace llvm Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -39,6 +39,7 @@ class Loop; class LoopInfo; class OptimizationRemarkEmitter; +class PostDominatorTree; class PredicatedScalarEvolution; class PredIteratorCache; class ScalarEvolution; @@ -377,7 +378,8 @@ SmallVector RedundantCasts; }; -BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, +BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, + PostDominatorTree *PDT, LoopInfo *LI, bool PreserveLCSSA); /// Ensure that all exit blocks of the loop are dedicated exits. @@ -385,8 +387,8 @@ /// For any loop exit block with non-loop predecessors, we split the loop /// predecessors to use a dedicated loop exit block. We update the dominator /// tree and loop info if provided, and will preserve LCSSA if requested. -bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, - bool PreserveLCSSA); +bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, PostDominatorTree *PDT, + LoopInfo *LI, bool PreserveLCSSA); /// Ensures LCSSA form for every instruction from the Worklist in the scope of /// innermost containing loop. Index: lib/Target/AMDGPU/SIAnnotateControlFlow.cpp =================================================================== --- lib/Target/AMDGPU/SIAnnotateControlFlow.cpp +++ lib/Target/AMDGPU/SIAnnotateControlFlow.cpp @@ -372,7 +372,8 @@ Preds.push_back(Pred); } - BB = SplitBlockPredecessors(BB, Preds, "endcf.split", DT, LI, false); + BB = SplitBlockPredecessors(BB, Preds, "endcf.split", DT, nullptr, LI, + false); } Value *Exec = popSaved(); Index: lib/Target/PowerPC/PPCCTRLoops.cpp =================================================================== --- lib/Target/PowerPC/PPCCTRLoops.cpp +++ lib/Target/PowerPC/PPCCTRLoops.cpp @@ -598,7 +598,7 @@ // the CTR register because some such uses might be reordered by the // selection DAG after the mtctr instruction). if (!Preheader || mightUseCTR(Preheader)) - Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA); + Preheader = InsertPreheaderForLoop(L, DT, nullptr, LI, PreserveLCSSA); if (!Preheader) return MadeChange; Index: lib/Target/PowerPC/PPCLoopPreIncPrep.cpp =================================================================== --- lib/Target/PowerPC/PPCLoopPreIncPrep.cpp +++ lib/Target/PowerPC/PPCLoopPreIncPrep.cpp @@ -325,7 +325,7 @@ // iteration space), insert a new preheader for the loop. if (!LoopPredecessor || !LoopPredecessor->getTerminator()->getType()->isVoidTy()) { - LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA); + LoopPredecessor = InsertPreheaderForLoop(L, DT, nullptr, LI, PreserveLCSSA); if (LoopPredecessor) MadeChange = true; } Index: lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp =================================================================== --- lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp +++ lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp @@ -1580,7 +1580,7 @@ // This function canonicalizes the loop into Loop-Simplify and LCSSA forms. auto CanonicalizeLoop = [&] (Loop *L, bool IsOriginalLoop) { formLCSSARecursively(*L, DT, &LI, &SE); - simplifyLoop(L, &DT, &LI, &SE, nullptr, true); + simplifyLoop(L, &DT, nullptr, &LI, &SE, nullptr, true); // Pre/post loops are slow paths, we do not need to perform any loop // optimizations on them. if (!IsOriginalLoop) Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -876,7 +876,8 @@ assert(CurLoop->contains(PredBB) && "Expect all predecessors are in the loop"); if (PN->getBasicBlockIndex(PredBB) >= 0) - SplitBlockPredecessors(ExitBB, PredBB, ".split.loop.exit", DT, LI, true); + SplitBlockPredecessors(ExitBB, PredBB, ".split.loop.exit", DT, nullptr, + LI, true); PredBBs.remove(PredBB); } } Index: lib/Transforms/Scalar/LoopInterchange.cpp =================================================================== --- lib/Transforms/Scalar/LoopInterchange.cpp +++ lib/Transforms/Scalar/LoopInterchange.cpp @@ -1003,13 +1003,13 @@ isa(OuterLoopPreHeader->begin()) || !OuterLoopPreHeader->getUniquePredecessor()) { OuterLoopPreHeader = - InsertPreheaderForLoop(OuterLoop, DT, LI, PreserveLCSSA); + InsertPreheaderForLoop(OuterLoop, DT, nullptr, LI, PreserveLCSSA); } if (!InnerLoopPreHeader || InnerLoopPreHeader == InnerLoop->getHeader() || InnerLoopPreHeader == OuterLoop->getHeader()) { InnerLoopPreHeader = - InsertPreheaderForLoop(InnerLoop, DT, LI, PreserveLCSSA); + InsertPreheaderForLoop(InnerLoop, DT, nullptr, LI, PreserveLCSSA); } // TODO: The loops could not be interchanged due to current limitations in the Index: lib/Transforms/Scalar/LoopRerollPass.cpp =================================================================== --- lib/Transforms/Scalar/LoopRerollPass.cpp +++ lib/Transforms/Scalar/LoopRerollPass.cpp @@ -1578,7 +1578,8 @@ } else { BasicBlock *Preheader = L->getLoopPreheader(); if (!Preheader) - Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA); + Preheader = + InsertPreheaderForLoop(L, DT, nullptr, LI, PreserveLCSSA); InsertPtr = Preheader->getTerminator(); } Index: lib/Transforms/Scalar/LoopStrengthReduce.cpp =================================================================== --- lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -5130,7 +5130,8 @@ .setDontDeleteUselessPHIs()); } else { SmallVector NewBBs; - SplitLandingPadPredecessors(Parent, BB, "", "", NewBBs, &DT, &LI); + SplitLandingPadPredecessors(Parent, BB, "", "", NewBBs, &DT, + nullptr, &LI); NewBB = NewBBs[0]; } // If NewBB==NULL, then SplitCriticalEdge refused to split because all Index: lib/Transforms/Scalar/LoopUnrollPass.cpp =================================================================== --- lib/Transforms/Scalar/LoopUnrollPass.cpp +++ lib/Transforms/Scalar/LoopUnrollPass.cpp @@ -1300,7 +1300,8 @@ // will simplify all loops, regardless of whether anything end up being // unrolled. for (auto &L : LI) { - Changed |= simplifyLoop(L, &DT, &LI, &SE, &AC, false /* PreserveLCSSA */); + Changed |= + simplifyLoop(L, &DT, nullptr, &LI, &SE, &AC, false /* PreserveLCSSA */); Changed |= formLCSSARecursively(*L, DT, &LI, &SE); } Index: lib/Transforms/Scalar/LoopUnswitch.cpp =================================================================== --- lib/Transforms/Scalar/LoopUnswitch.cpp +++ lib/Transforms/Scalar/LoopUnswitch.cpp @@ -1185,7 +1185,7 @@ // Although SplitBlockPredecessors doesn't preserve loop-simplify in // general, if we call it on all predecessors of all exits then it does. - SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI, + SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, nullptr, LI, /*PreserveLCSSA*/ true); } } Index: lib/Transforms/Scalar/SimpleLoopUnswitch.cpp =================================================================== --- lib/Transforms/Scalar/SimpleLoopUnswitch.cpp +++ lib/Transforms/Scalar/SimpleLoopUnswitch.cpp @@ -1849,7 +1849,8 @@ // introduced new, non-dedicated exits. At least try to re-form dedicated // exits for these loops. This may fail if they couldn't have dedicated // exits to start with. - formDedicatedExitBlocks(OuterL, &DT, &LI, /*PreserveLCSSA*/ true); + formDedicatedExitBlocks(OuterL, &DT, nullptr, &LI, + /*PreserveLCSSA*/ true); } } Index: lib/Transforms/Utils/BasicBlockUtils.cpp =================================================================== --- lib/Transforms/Utils/BasicBlockUtils.cpp +++ lib/Transforms/Utils/BasicBlockUtils.cpp @@ -20,6 +20,7 @@ #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemoryDependenceAnalysis.h" +#include "llvm/Analysis/PostDominators.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" @@ -314,11 +315,14 @@ /// Update DominatorTree, LoopInfo, and LCCSA analysis information. static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, ArrayRef Preds, - DominatorTree *DT, LoopInfo *LI, - bool PreserveLCSSA, bool &HasLoopExit) { + DominatorTree *DT, PostDominatorTree *PDT, + LoopInfo *LI, bool PreserveLCSSA, + bool &HasLoopExit) { // Update dominator tree if available. if (DT) DT->splitBlock(NewBB); + if (PDT) + PDT->splitBlock(NewBB); // The rest of the logic is only relevant for updating the loop structures. if (!LI) @@ -453,7 +457,8 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, ArrayRef Preds, const char *Suffix, DominatorTree *DT, - LoopInfo *LI, bool PreserveLCSSA) { + PostDominatorTree *PDT, LoopInfo *LI, + bool PreserveLCSSA) { // Do not attempt to split that which cannot be split. if (!BB->canSplitPredecessors()) return nullptr; @@ -465,7 +470,7 @@ std::string NewName = std::string(Suffix) + ".split-lp"; SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs, DT, - LI, PreserveLCSSA); + PDT, LI, PreserveLCSSA); return NewBBs[0]; } @@ -500,7 +505,7 @@ // Update DominatorTree, LoopInfo, and LCCSA analysis information. bool HasLoopExit = false; - UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, PreserveLCSSA, + UpdateAnalysisInformation(BB, NewBB, Preds, DT, PDT, LI, PreserveLCSSA, HasLoopExit); // Update the PHI nodes in BB with the values coming from NewBB. @@ -512,7 +517,8 @@ ArrayRef Preds, const char *Suffix1, const char *Suffix2, SmallVectorImpl &NewBBs, - DominatorTree *DT, LoopInfo *LI, + DominatorTree *DT, + PostDominatorTree *PDT, LoopInfo *LI, bool PreserveLCSSA) { assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!"); @@ -538,7 +544,7 @@ } bool HasLoopExit = false; - UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, PreserveLCSSA, + UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, PDT, LI, PreserveLCSSA, HasLoopExit); // Update the PHI nodes in OrigBB with the values coming from NewBB1. @@ -574,7 +580,7 @@ // Update DominatorTree, LoopInfo, and LCCSA analysis information. HasLoopExit = false; - UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI, + UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, PDT, LI, PreserveLCSSA, HasLoopExit); // Update the PHI nodes in OrigBB with the values coming from NewBB2. Index: lib/Transforms/Utils/BreakCriticalEdges.cpp =================================================================== --- lib/Transforms/Utils/BreakCriticalEdges.cpp +++ lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -283,8 +283,9 @@ } if (!LoopPreds.empty()) { assert(!DestBB->isEHPad() && "We don't split edges to EH pads!"); - BasicBlock *NewExitBB = SplitBlockPredecessors( - DestBB, LoopPreds, "split", DT, LI, Options.PreserveLCSSA); + BasicBlock *NewExitBB = + SplitBlockPredecessors(DestBB, LoopPreds, "split", DT, nullptr, + LI, Options.PreserveLCSSA); if (Options.PreserveLCSSA) createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB); } Index: lib/Transforms/Utils/LoopSimplify.cpp =================================================================== --- lib/Transforms/Utils/LoopSimplify.cpp +++ lib/Transforms/Utils/LoopSimplify.cpp @@ -50,6 +50,7 @@ #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" #include "llvm/IR/CFG.h" @@ -115,7 +116,8 @@ /// preheader insertion and analysis updating. /// BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, DominatorTree *DT, - LoopInfo *LI, bool PreserveLCSSA) { + PostDominatorTree *PDT, LoopInfo *LI, + bool PreserveLCSSA) { BasicBlock *Header = L->getHeader(); // Compute the set of predecessors of the loop that are not in the loop. @@ -137,7 +139,7 @@ // Split out the loop pre-header. BasicBlock *PreheaderBB; PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", DT, - LI, PreserveLCSSA); + PDT, LI, PreserveLCSSA); if (!PreheaderBB) return nullptr; @@ -215,9 +217,9 @@ /// created. /// static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader, - DominatorTree *DT, LoopInfo *LI, - ScalarEvolution *SE, bool PreserveLCSSA, - AssumptionCache *AC) { + DominatorTree *DT, PostDominatorTree *PDT, + LoopInfo *LI, ScalarEvolution *SE, + bool PreserveLCSSA, AssumptionCache *AC) { // Don't try to separate loops without a preheader. if (!Preheader) return nullptr; @@ -251,7 +253,7 @@ SE->forgetLoop(L); BasicBlock *NewBB = SplitBlockPredecessors(Header, OuterLoopPreds, ".outer", - DT, LI, PreserveLCSSA); + DT, PDT, LI, PreserveLCSSA); // Make sure that NewBB is put someplace intelligent, which doesn't mess up // code layout too horribly. @@ -314,7 +316,7 @@ // Split edges to exit blocks from the inner loop, if they emerged in the // process of separating the outer one. - formDedicatedExitBlocks(L, DT, LI, PreserveLCSSA); + formDedicatedExitBlocks(L, DT, PDT, LI, PreserveLCSSA); if (PreserveLCSSA) { // Fix LCSSA form for L. Some values, which previously were only used inside @@ -339,7 +341,9 @@ /// and have that block branch to the loop header. This ensures that loops /// have exactly one backedge. static BasicBlock *insertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader, - DominatorTree *DT, LoopInfo *LI) { + DominatorTree *DT, + PostDominatorTree *PDT, + LoopInfo *LI) { assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); // Get information about the loop @@ -453,15 +457,17 @@ // Update dominator information DT->splitBlock(BEBlock); + if (PDT) + PDT->splitBlock(BEBlock); return BEBlock; } /// \brief Simplify one loop and queue further loops for simplification. static bool simplifyOneLoop(Loop *L, SmallVectorImpl &Worklist, - DominatorTree *DT, LoopInfo *LI, - ScalarEvolution *SE, AssumptionCache *AC, - bool PreserveLCSSA) { + DominatorTree *DT, PostDominatorTree *PDT, + LoopInfo *LI, ScalarEvolution *SE, + AssumptionCache *AC, bool PreserveLCSSA) { bool Changed = false; ReprocessLoop: @@ -487,9 +493,22 @@ DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor " << P->getName() << "\n"); + std::vector Updates; + if (PDT) + // Get all PDT updates for removing the successors + for (BasicBlock *Successor : successors(P)) + Updates.emplace_back(PostDominatorTree::UpdateKind::Delete, P, + Successor); + // Zap the dead pred's terminator and replace it with unreachable. TerminatorInst *TI = P->getTerminator(); changeToUnreachable(TI, /*UseLLVMTrap=*/false, PreserveLCSSA); + + if (PDT) + // FIXME: The applyUpdates updater here will not work if there are + // multiple edges P -> Succ. We apply them manually instead. + for (auto U : Updates) + PDT->deleteEdge(U.getFrom(), U.getTo()); Changed = true; } } @@ -521,7 +540,7 @@ // Does the loop already have a preheader? If so, don't insert one. BasicBlock *Preheader = L->getLoopPreheader(); if (!Preheader) { - Preheader = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA); + Preheader = InsertPreheaderForLoop(L, DT, PDT, LI, PreserveLCSSA); if (Preheader) Changed = true; } @@ -530,7 +549,7 @@ // predecessors that are inside of the loop. This check guarantees that the // loop preheader/header will dominate the exit blocks. If the exit block has // predecessors from outside of the loop, split the edge now. - if (formDedicatedExitBlocks(L, DT, LI, PreserveLCSSA)) + if (formDedicatedExitBlocks(L, DT, PDT, LI, PreserveLCSSA)) Changed = true; // If the header has more than two predecessors at this point (from the @@ -541,8 +560,8 @@ // this for loops with a giant number of backedges, just factor them into a // common backedge instead. if (L->getNumBackEdges() < 8) { - if (Loop *OuterL = - separateNestedLoop(L, Preheader, DT, LI, SE, PreserveLCSSA, AC)) { + if (Loop *OuterL = separateNestedLoop(L, Preheader, DT, PDT, LI, SE, + PreserveLCSSA, AC)) { ++NumNested; // Enqueue the outer loop as it should be processed next in our // depth-first nest walk. @@ -559,7 +578,7 @@ // If we either couldn't, or didn't want to, identify nesting of the loops, // insert a new block that all backedges target, then make it jump to the // loop header. - LoopLatch = insertUniqueBackedgeBlock(L, Preheader, DT, LI); + LoopLatch = insertUniqueBackedgeBlock(L, Preheader, DT, PDT, LI); if (LoopLatch) Changed = true; } @@ -671,6 +690,17 @@ } DT->eraseNode(ExitingBlock); + if (PDT) { + DomTreeNode *Node = PDT->getNode(ExitingBlock); + const std::vector *> &Children = + Node->getChildren(); + while (!Children.empty()) { + DomTreeNode *Child = Children.front(); + PDT->changeImmediateDominator(Child, Node->getIDom()); + } + PDT->eraseNode(ExitingBlock); + } + BI->getSuccessor(0)->removePredecessor( ExitingBlock, /* DontDeleteUselessPHIs */ PreserveLCSSA); BI->getSuccessor(1)->removePredecessor( @@ -682,8 +712,8 @@ return Changed; } -bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, - ScalarEvolution *SE, AssumptionCache *AC, +bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, PostDominatorTree *PDT, + LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, bool PreserveLCSSA) { bool Changed = false; @@ -711,8 +741,8 @@ } while (!Worklist.empty()) - Changed |= simplifyOneLoop(Worklist.pop_back_val(), Worklist, DT, LI, SE, - AC, PreserveLCSSA); + Changed |= simplifyOneLoop(Worklist.pop_back_val(), Worklist, DT, PDT, LI, + SE, AC, PreserveLCSSA); return Changed; } @@ -732,6 +762,7 @@ // We need loop information to identify the loops... AU.addRequired(); AU.addPreserved(); + AU.addPreserved(); AU.addRequired(); AU.addPreserved(); @@ -771,6 +802,8 @@ bool Changed = false; LoopInfo *LI = &getAnalysis().getLoopInfo(); DominatorTree *DT = &getAnalysis().getDomTree(); + auto *PDTWP = getAnalysisIfAvailable(); + PostDominatorTree *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr; auto *SEWP = getAnalysisIfAvailable(); ScalarEvolution *SE = SEWP ? &SEWP->getSE() : nullptr; AssumptionCache *AC = @@ -780,7 +813,7 @@ // Simplify each loop nest in the function. for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) - Changed |= simplifyLoop(*I, DT, LI, SE, AC, PreserveLCSSA); + Changed |= simplifyLoop(*I, DT, PDT, LI, SE, AC, PreserveLCSSA); #ifndef NDEBUG if (PreserveLCSSA) { @@ -789,6 +822,7 @@ assert(InLCSSA && "LCSSA is broken after loop-simplify."); } #endif + return Changed; } @@ -797,19 +831,21 @@ bool Changed = false; LoopInfo *LI = &AM.getResult(F); DominatorTree *DT = &AM.getResult(F); + PostDominatorTree *PDT = AM.getCachedResult(F); ScalarEvolution *SE = AM.getCachedResult(F); AssumptionCache *AC = &AM.getResult(F); // Note that we don't preserve LCSSA in the new PM, if you need it run LCSSA // after simplifying the loops. for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) - Changed |= simplifyLoop(*I, DT, LI, SE, AC, /*PreserveLCSSA*/ false); + Changed |= simplifyLoop(*I, DT, PDT, LI, SE, AC, /*PreserveLCSSA*/ false); if (!Changed) return PreservedAnalyses::all(); PreservedAnalyses PA; PA.preserve(); + PA.preserve(); PA.preserve(); PA.preserve(); PA.preserve(); Index: lib/Transforms/Utils/LoopUnroll.cpp =================================================================== --- lib/Transforms/Utils/LoopUnroll.cpp +++ lib/Transforms/Utils/LoopUnroll.cpp @@ -876,11 +876,11 @@ // TODO: That potentially might be compile-time expensive. We should try // to fix the loop-simplified form incrementally. - simplifyLoop(OuterL, DT, LI, SE, AC, PreserveLCSSA); + simplifyLoop(OuterL, DT, nullptr, LI, SE, AC, PreserveLCSSA); } else { // Simplify loops for which we might've broken loop-simplify form. for (Loop *SubLoop : LoopsToSimplify) - simplifyLoop(SubLoop, DT, LI, SE, AC, PreserveLCSSA); + simplifyLoop(SubLoop, DT, nullptr, LI, SE, AC, PreserveLCSSA); } } Index: lib/Transforms/Utils/LoopUnrollPeel.cpp =================================================================== --- lib/Transforms/Utils/LoopUnrollPeel.cpp +++ lib/Transforms/Utils/LoopUnrollPeel.cpp @@ -552,10 +552,10 @@ SE->forgetLoop(ParentLoop); // FIXME: Incrementally update loop-simplify - simplifyLoop(ParentLoop, DT, LI, SE, AC, PreserveLCSSA); + simplifyLoop(ParentLoop, DT, nullptr, LI, SE, AC, PreserveLCSSA); } else { // FIXME: Incrementally update loop-simplify - simplifyLoop(L, DT, LI, SE, AC, PreserveLCSSA); + simplifyLoop(L, DT, nullptr, LI, SE, AC, PreserveLCSSA); } NumPeeled++; Index: lib/Transforms/Utils/LoopUnrollRuntime.cpp =================================================================== --- lib/Transforms/Utils/LoopUnrollRuntime.cpp +++ lib/Transforms/Utils/LoopUnrollRuntime.cpp @@ -127,8 +127,8 @@ if (PrologLoop->contains(PredBB)) PrologExitPreds.push_back(PredBB); - SplitBlockPredecessors(PrologExit, PrologExitPreds, ".unr-lcssa", DT, LI, - PreserveLCSSA); + SplitBlockPredecessors(PrologExit, PrologExitPreds, ".unr-lcssa", DT, + nullptr, LI, PreserveLCSSA); } // Create a branch around the original loop, which is taken if there are no @@ -146,8 +146,8 @@ B.CreateICmpULT(BECount, ConstantInt::get(BECount->getType(), Count - 1)); // Split the exit to maintain loop canonicalization guarantees SmallVector Preds(predecessors(OriginalLoopLatchExit)); - SplitBlockPredecessors(OriginalLoopLatchExit, Preds, ".unr-lcssa", DT, LI, - PreserveLCSSA); + SplitBlockPredecessors(OriginalLoopLatchExit, Preds, ".unr-lcssa", DT, + nullptr, LI, PreserveLCSSA); // Add the branch to the exit block (around the unrolled loop) B.CreateCondBr(BrLoopExit, OriginalLoopLatchExit, NewPreHeader); InsertPt->eraseFromParent(); @@ -269,7 +269,7 @@ assert(Exit && "Loop must have a single exit block only"); // Split the epilogue exit to maintain loop canonicalization guarantees SmallVector Preds(predecessors(Exit)); - SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, LI, + SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, nullptr, LI, PreserveLCSSA); // Add the branch to the exit block (around the unrolling loop) B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit); @@ -279,7 +279,7 @@ // Split the main loop exit to maintain canonicalization guarantees. SmallVector NewExitPreds{Latch}; - SplitBlockPredecessors(NewExit, NewExitPreds, ".loopexit", DT, LI, + SplitBlockPredecessors(NewExit, NewExitPreds, ".loopexit", DT, nullptr, LI, PreserveLCSSA); } @@ -646,8 +646,8 @@ NewPreHeader->setName(PreHeader->getName() + ".new"); // Split LatchExit to create phi nodes from branch above. SmallVector Preds(predecessors(LatchExit)); - NewExit = SplitBlockPredecessors(LatchExit, Preds, ".unr-lcssa", - DT, LI, PreserveLCSSA); + NewExit = SplitBlockPredecessors(LatchExit, Preds, ".unr-lcssa", DT, + nullptr, LI, PreserveLCSSA); // Split NewExit to insert epilog remainder loop. EpilogPreHeader = SplitBlock(NewExit, NewExit->getTerminator(), DT, LI); EpilogPreHeader->setName(Header->getName() + ".epil.preheader"); @@ -896,11 +896,11 @@ if (OtherExits.size() > 0) { // Generate dedicated exit blocks for the original loop, to preserve // LoopSimplifyForm. - formDedicatedExitBlocks(L, DT, LI, PreserveLCSSA); + formDedicatedExitBlocks(L, DT, nullptr, LI, PreserveLCSSA); // Generate dedicated exit blocks for the remainder loop if one exists, to // preserve LoopSimplifyForm. if (remainderLoop) - formDedicatedExitBlocks(remainderLoop, DT, LI, PreserveLCSSA); + formDedicatedExitBlocks(remainderLoop, DT, nullptr, LI, PreserveLCSSA); } if (remainderLoop && UnrollRemainder) { Index: lib/Transforms/Utils/LoopUtils.cpp =================================================================== --- lib/Transforms/Utils/LoopUtils.cpp +++ lib/Transforms/Utils/LoopUtils.cpp @@ -1063,7 +1063,8 @@ return true; } -bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, +bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, + PostDominatorTree *PDT, LoopInfo *LI, bool PreserveLCSSA) { bool Changed = false; @@ -1096,7 +1097,7 @@ return false; auto *NewExitBB = SplitBlockPredecessors( - BB, InLoopPredecessors, ".loopexit", DT, LI, PreserveLCSSA); + BB, InLoopPredecessors, ".loopexit", DT, PDT, LI, PreserveLCSSA); if (!NewExitBB) DEBUG(dbgs() << "WARNING: Can't create a dedicated exit block for loop: " Index: lib/Transforms/Vectorize/LoopVectorize.cpp =================================================================== --- lib/Transforms/Vectorize/LoopVectorize.cpp +++ lib/Transforms/Vectorize/LoopVectorize.cpp @@ -9087,7 +9087,8 @@ // will simplify all loops, regardless of whether anything end up being // vectorized. for (auto &L : *LI) - Changed |= simplifyLoop(L, DT, LI, SE, AC, false /* PreserveLCSSA */); + Changed |= + simplifyLoop(L, DT, nullptr, LI, SE, AC, false /* PreserveLCSSA */); // Build up a worklist of inner-loops to vectorize. This is necessary as // the act of vectorizing or partially unrolling a loop creates new loops Index: test/Transforms/LoopSimplify/2004-04-13-LoopSimplifyUpdateDomFrontier.ll =================================================================== --- test/Transforms/LoopSimplify/2004-04-13-LoopSimplifyUpdateDomFrontier.ll +++ test/Transforms/LoopSimplify/2004-04-13-LoopSimplifyUpdateDomFrontier.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -sroa -loop-simplify -licm -disable-output -verify-dom-info -verify-loop-info +; RUN: opt < %s -sroa -postdomtree -loop-simplify -licm -disable-output -verify-dom-info -verify-loop-info define void @inflate() { entry: Index: test/Transforms/LoopSimplify/2010-07-15-IncorrectDomFrontierUpdate.ll =================================================================== --- test/Transforms/LoopSimplify/2010-07-15-IncorrectDomFrontierUpdate.ll +++ test/Transforms/LoopSimplify/2010-07-15-IncorrectDomFrontierUpdate.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -domfrontier -loop-simplify -domfrontier -verify-dom-info -analyze +; RUN: opt < %s -postdomtree -domfrontier -loop-simplify -domfrontier -verify-dom-info -analyze define void @a() nounwind { Index: test/Transforms/LoopSimplify/indirectbr.ll =================================================================== --- test/Transforms/LoopSimplify/indirectbr.ll +++ test/Transforms/LoopSimplify/indirectbr.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -loop-simplify -lcssa -verify-loop-info -verify-dom-info -S \ +; RUN: opt < %s -postdomtree -loop-simplify -lcssa -verify-loop-info -verify-dom-info -S \ ; RUN: | grep -F "indirectbr i8* %x, [label %L0, label %L1]" \ ; RUN: | count 6 Index: test/Transforms/LoopSimplify/merge-exits.ll =================================================================== --- test/Transforms/LoopSimplify/merge-exits.ll +++ test/Transforms/LoopSimplify/merge-exits.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -loop-simplify -loop-rotate -instcombine -indvars -S -verify-loop-info -verify-dom-info | FileCheck %s +; RUN: opt < %s -postdomtree -loop-simplify -loop-rotate -instcombine -indvars -S -verify-loop-info -verify-dom-info | FileCheck %s ; Loopsimplify should be able to merge the two loop exits ; into one, so that loop rotate can rotate the loop, so Index: test/Transforms/LoopSimplify/preserve-pdt.ll =================================================================== --- /dev/null +++ test/Transforms/LoopSimplify/preserve-pdt.ll @@ -0,0 +1,36 @@ +; RUN: opt -passes="require,loop-simplify,print" -verify-dom-info %s 2>&1 | FileCheck %s +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +; CHECK: Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries. +; CHECK: [1] <> {4294967295,4294967295} [0] +; CHECK: [2] %for.inc {4294967295,4294967295} [1] +; CHECK: [2] %end {4294967295,4294967295} [1] +; CHECK: [3] %cleanup14 {4294967295,4294967295} [2] +; CHECK: [4] %f {4294967295,4294967295} [3] +; CHECK: [5] %entry {4294967295,4294967295} [4] +; CHECK: [4] %for.end.split {4294967295,4294967295} [3] +; CHECK: Roots: %for.inc %end + +define void @e() local_unnamed_addr { +entry: + br label %f + +f: + br i1 undef, label %for.end.split, label %cleanup14 + +for.inc: + switch i4 undef, label %cleanup14 [ + i4 0, label %for.end.split + i4 -8, label %for.end.split + ] + +for.end.split: + br label %cleanup14 + +cleanup14: + br i1 undef, label %f, label %end + +end: + ret void +} Index: test/Transforms/LoopSimplify/unreachable-loop-pred.ll =================================================================== --- test/Transforms/LoopSimplify/unreachable-loop-pred.ll +++ test/Transforms/LoopSimplify/unreachable-loop-pred.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -loop-simplify -disable-output -verify-loop-info -verify-dom-info < %s +; RUN: opt -S -postdomtree -loop-simplify -disable-output -verify-loop-info -verify-dom-info < %s ; PR5235 ; When loopsimplify inserts a preheader for this loop, it should add the new Index: unittests/Transforms/Scalar/LoopPassManagerTest.cpp =================================================================== --- unittests/Transforms/Scalar/LoopPassManagerTest.cpp +++ unittests/Transforms/Scalar/LoopPassManagerTest.cpp @@ -10,6 +10,7 @@ #include "llvm/Transforms/Scalar/LoopPassManager.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" @@ -299,6 +300,7 @@ // We need DominatorTreeAnalysis for LoopAnalysis. FAM.registerPass([&] { return DominatorTreeAnalysis(); }); + FAM.registerPass([&] { return PostDominatorTreeAnalysis(); }); FAM.registerPass([&] { return LoopAnalysis(); }); // We also allow loop passes to assume a set of other analyses and so need // those.