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<BasicBlock *> 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<BasicBlock *> Preds,
-                                 const char *Suffix, const char *Suffix2,
-                                 SmallVectorImpl<BasicBlock *> &NewBBs,
-                                 DominatorTree *DT = nullptr,
-                                 LoopInfo *LI = nullptr,
-                                 bool PreserveLCSSA = false);
+void SplitLandingPadPredecessors(
+    BasicBlock *OrigBB, ArrayRef<BasicBlock *> Preds, const char *Suffix,
+    const char *Suffix2, SmallVectorImpl<BasicBlock *> &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<LoopSimplifyPass> {
 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<Instruction *, 2> 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<PHINode>(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<BasicBlock*, 2> 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<BasicBlock *> 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<BasicBlock *> 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<BasicBlock *> Preds,
                                        const char *Suffix1, const char *Suffix2,
                                        SmallVectorImpl<BasicBlock *> &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<Loop *> &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<PostDominatorTree::UpdateType> 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<DomTreeNodeBase<BasicBlock> *> &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<DominatorTreeWrapperPass>();
       AU.addPreserved<DominatorTreeWrapperPass>();
+      AU.addPreserved<PostDominatorTreeWrapperPass>();
 
       AU.addRequired<LoopInfoWrapperPass>();
       AU.addPreserved<LoopInfoWrapperPass>();
@@ -771,6 +802,8 @@
   bool Changed = false;
   LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  auto *PDTWP = getAnalysisIfAvailable<PostDominatorTreeWrapperPass>();
+  PostDominatorTree *PDT = PDTWP ? &PDTWP->getPostDomTree() : nullptr;
   auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
   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<LoopAnalysis>(F);
   DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F);
+  PostDominatorTree *PDT = AM.getCachedResult<PostDominatorTreeAnalysis>(F);
   ScalarEvolution *SE = AM.getCachedResult<ScalarEvolutionAnalysis>(F);
   AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(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<DominatorTreeAnalysis>();
+  PA.preserve<PostDominatorTreeAnalysis>();
   PA.preserve<LoopAnalysis>();
   PA.preserve<BasicAA>();
   PA.preserve<GlobalsAA>();
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<BasicBlock *, 4> 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<BasicBlock*, 4> 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<BasicBlock*, 4> 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<BasicBlock*, 4> 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<postdomtree>,loop-simplify,print<postdomtree>" -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]  <<exit node>> {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.