[LoopSimplify] Preserve Post Dom Trees across Loop Simplify

[dmgreen]

Summary

This extends DeferredDominance to hold an optional PostDomTree, and apply the same set of updated to both dom trees. Loop Simplify is then switched over to use DeferredDominance, and applies the correct set of edge updates to preserve the two trees at once.

[dmgreen]

I will try to rebase this on top of d40146 once it goes in. Providing I can get the applyUpdates to work.

[fhahn]

I assume this depends on D41299?

lib/Target/AMDGPU/SIAnnotateControlFlow.cpp

375 ↗

(On Diff #127155)

Why do we try to preserve the DominatorTree here, but not the PostDominatorTree? Here and in other files below

lib/Transforms/Utils/BasicBlockUtils.cpp

324

Maybe add a comment here like for updating the dominator tree?

522

Update comment to include PostDominator

606

Update comment to include postdominator

lib/Transforms/Utils/LoopSimplify.cpp

470

Update postdominator comment? PDT is optional here but DT is not. I assume that has to do with some instances passing nullptr as above. Is there any reason we cannot make PDT required?`I am not saying we need to do all this in a single commit, but we should keep that in mind.

845

unrelated whitespace change.

[dmgreen]

Hello. Thanks for taking a look.

After starting at D40146 I think a lot of this will end up changing. I will have to look into what that will end up looking like once it is in and I have some time to update things.

I've tried the answer the questions that are relevant to that. I have another patch for the same thing in LICM, which is mostly trivial on top of this.

lib/Target/AMDGPU/SIAnnotateControlFlow.cpp

375 ↗

(On Diff #127155)

I think the only place we currently use PostDominatorTrees in the default pipeline is in ADCE. Theres also places like GVNHoist, but it's off at the moment. We will likely have to add post doms to DSE, which has LICM (and hence LoopSimplify) in between it and ADCE. So if we can at least get these two passes to preserve the tree, we will get the post dom tree for free (ish) :)

So most places currently don't know about PostDomTrees. DomTrees and much more common. In the long run it would be good to get them to preserve, where it makes sense, but it can be a bit fiddly to make sure its correct. This interface will likely change to not take a PostDomTree, taking an updater object instead.

lib/Transforms/Utils/BasicBlockUtils.cpp

522

Will do. I'll update them when I have a new version.

lib/Transforms/Utils/LoopSimplify.cpp

470

This may turn into a DeferredDominance object holding a DT and PDT that applies the same updates to each. The PDT will be rarer and probably still optional, but hopefully a lot of the interface will simplify.

[dmgreen]

I don't know what people will think of the interfaces for SplitBlockPredecessors and simplifyLoop. Let me know if theres a better way I should be doing that. I also removed the old splitBlock from Dominator trees, replacing it with a series of deferred updates. And I made DeferredDominator flush in it's deconstructor. And I may need to move DeferredDominance into Analysis to use PostDomTrees - I'll check this.

[kuhar]

Looks nice, I think that using DeferredDominance as a single DomTree updated object is the right direction.
I just quickly went though the patch and left some comments, but I think this approach is good enough for the first step. Ideally, DDT should update DT first and use the reachability information to update PDT faster. I will comment more on this later when I find some more time.

include/llvm/Analysis/PostDominators.h

33

Nice!

lib/Transforms/Utils/BasicBlockUtils.cpp

324

We can reserve Updates here. 1 + 2 * Preds.size()?

350

Do we always have to flush DDT when we get to this condition here? I think that it's possible to tell that Pred is not reachable if it's enqueued for deletion.

350

Just eyeballing the function, this seems to be the only use od DT in the rest of this function. I'm not sure if always flushing it above is not too conservative/costly.

538

SplitBlockPredecessors(BB, Preds, Suffix, DT ? DDT(*DT) : nullptr, LI, PreserveLCSSA);?

lib/Transforms/Utils/LoopSimplify.cpp

160

Like above.

469

Nit: we can reserve here as well.

632

I would appreciate an extra line here, the continue blends in and it's easy to miss it.

666

SmallVector?

668

Can you rewrite it as a series of if's? It's difficult to parse for me.

763

Same as above.

lib/Transforms/Utils/LoopUtils.cpp

1136

Same.

test/Transforms/LoopSimplify/2004-04-13-LoopSimplifyUpdateDomFrontier.ll

1

Is PDT required? Maybe we should test both with and without it?

[dmgreen]

Hello. Sorry for not getting back to this. You gave a good review, but I haven't had the chance to do anything with this (its been "second" on todo list for the longest time). Essentially I dislike the duplicated functions here enough that I don't think it's workable as-is.

lib/Transforms/Utils/BasicBlockUtils.cpp

350

I think, because this is already working in loop simplify, the number of updates will not be big. It already works fine with an non-deferred updater, so the cost of doing DT updates will likely not be massive.

Could a block be already unreachable, but not queued for deletion?

538

DDT is currently passed as a pointer and takes a reference to a DT. So we dont want to create one if DT is nullptr, and I dont think using SplitBlockPredecessors(.., DT ? &DeferredDominance(DT) : nullptr, ..) is valid use of a rvalue.

I also dont think having these multiple function definitions is sensible/scalable.

My current best guess for how to do this properly and incrementally would be to have something like a "DominatorTreeUpdater" class that both DT and DDT inherrit from. It would have an interface similar to DDT here (insertEdge, deleteEdge, applyUpdate, getDT, getPDT), and would allow a DT and a DDT (holding a DT/PDT) to be used identically. Functions such as this one could then be switched over to use the new class type without changing any external code.

There may be better ideas out there.

lib/Transforms/Utils/LoopSimplify.cpp

668

I agree :)

[kuhar]

lib/Transforms/Utils/BasicBlockUtils.cpp

350

OK.

Could a block be already unreachable, but not queued for deletion?

I'm not sure if it makes sense in this API, but in general yes. And a previously unreachable block can also be (non-trivially) enqueued for insertion

538

I missed the pointer/reference difference here. I'm fine with how it is right now, but I really think we have to consider better design in the future.

include/llvm/Analysis/PostDominators.h

 class Function;
 class raw_ostream;
 
 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
 /// compute the post-dominator tree.
 struct PostDominatorTree : public PostDomTreeBase<BasicBlock> {
   using Base = PostDomTreeBase<BasicBlock>;
 
+  PostDominatorTree() = default;
+  explicit PostDominatorTree(Function &F) { recalculate(F); }
+
   /// Handle invalidation explicitly.
   bool invalidate(Function &F, const PreservedAnalyses &PA,
                   FunctionAnalysisManager::Invalidator &);
 
   /// \brief Verify the correctness of the postdomtree.
   ///
   /// This should only be used for debugging as it aborts the program if the
   /// verification fails.

include/llvm/CodeGen/MachineDominators.h

public:
   /// eraseNode - Removes a node from  the dominator tree. Block must not
   /// dominate any other blocks. Removes node from its immediate dominator's
   /// children list. Deletes dominator node associated with basic block BB.
   inline void eraseNode(MachineBasicBlock *BB) {
     applySplitCriticalEdges();
     DT->eraseNode(BB);
   }
 
-  /// splitBlock - BB is split and now it has one successor. Update dominator
-  /// tree to reflect this change.
-  inline void splitBlock(MachineBasicBlock* NewBB) {
-    applySplitCriticalEdges();
-    DT->splitBlock(NewBB);
-  }
-
   /// isReachableFromEntry - Return true if A is dominated by the entry
   /// block of the function containing it.
   bool isReachableFromEntry(const MachineBasicBlock *A) {
     applySplitCriticalEdges();
     return DT->isReachableFromEntry(A);
   }
 
   void releaseMemory() override;

include/llvm/IR/Dominators.h

public:
   }
 
   void releaseMemory() override { DT.releaseMemory(); }
 
   void print(raw_ostream &OS, const Module *M = nullptr) const override;
 };
 
 //===-------------------------------------
-/// \brief Class to defer updates to a DominatorTree.
+/// \brief Class to defer updates to a DominatorTree and (optionally)
+/// PostDominatorTree.
 ///
 /// Definition: Applying updates to every edge insertion and deletion is
 /// expensive and not necessary. When one needs the DominatorTree for analysis
 /// they can request a flush() to perform a larger batch update. This has the
 /// advantage of the DominatorTree inspecting the set of updates to find
 /// duplicates or unnecessary subtree updates.
 ///
-/// The scope of DeferredDominance operates at a Function level.
+/// The scope of DeferredDominance operates at a Function level. This class
+/// automatically flushes any remaining updates when destroyed.
 ///
 /// It is not necessary for the user to scrub the updates for duplicates or
 /// updates that point to the same block (Delete, BB_A, BB_A). Performance
 /// can be gained if the caller attempts to batch updates before submitting
 /// to applyUpdates(ArrayRef) in cases where duplicate edge requests will
 /// occur.
 ///
 /// It is required for the state of the LLVM IR to be applied *before*
 /// submitting updates. The update routines must analyze the current state
 /// between a pair of (From, To) basic blocks to determine if the update
 /// needs to be queued.
 /// Example (good):
 ///     TerminatorInstructionBB->removeFromParent();
 ///     DDT->deleteEdge(BB, Successor);
 /// Example (bad):
 ///     DDT->deleteEdge(BB, Successor);
 ///     TerminatorInstructionBB->removeFromParent();
 class DeferredDominance {
 public:
-  DeferredDominance(DominatorTree &DT_) : DT(DT_) {}
+  DeferredDominance(DominatorTree &DT_, PostDominatorTree *PDT_ = nullptr)
+      : DT(DT_), PDT(PDT_) {}
+  ~DeferredDominance();
 
   /// \brief Queues multiple updates and discards duplicates.
   void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates);
 
   /// \brief Helper method for a single edge insertion. It's almost always
   /// better to batch updates and call applyUpdates to quickly remove duplicate
   /// edges. This is best used when there is only a single insertion needed to
   /// update Dominators.
   void insertEdge(BasicBlock *From, BasicBlock *To);
 
   /// \brief Helper method for a single edge deletion. It's almost always better
   /// to batch updates and call applyUpdates to quickly remove duplicate edges.
   /// This is best used when there is only a single deletion needed to update
   /// Dominators.
   void deleteEdge(BasicBlock *From, BasicBlock *To);
 
   /// \brief Delays the deletion of a basic block until a flush() event.
   void deleteBB(BasicBlock *DelBB);
 
   /// \brief Returns true if DelBB is awaiting deletion at a flush() event.
   bool pendingDeletedBB(BasicBlock *DelBB);
 
-  /// \brief Flushes all pending updates and block deletions. Returns a
-  /// correct DominatorTree reference to be used by the caller for analysis.
-  DominatorTree &flush();
+  /// \brief Flushes all pending updates and block deletions.
+  void flush();
+
+  /// \brief Flushes and returns a correct DominatorTree reference to
+  /// be used by the caller for analysis.
+  DominatorTree &getDT();
+
+  /// \brief Flushes and returns a correct PostDominatorTree pointer to
+  /// be used by the caller for analysis. Returns nullptr if PDT is not
+  /// being held.
+  PostDominatorTree *getPDT();
 
   /// \brief Drops all internal state and forces a (slow) recalculation of the
   /// DominatorTree based on the current state of the LLVM IR in F. This should
   /// only be used in corner cases such as the Entry block of F being deleted.
   void recalculate(Function &F);
 
   /// \brief Debug method to help view the state of pending updates.
   LLVM_DUMP_METHOD void dump() const;
 
 private:
   DominatorTree &DT;
+  PostDominatorTree *PDT;
   SmallVector<DominatorTree::UpdateType, 16> PendUpdates;
   SmallPtrSet<BasicBlock *, 8> DeletedBBs;
 
   /// Apply an update (Kind, From, To) to the internal queued updates. The
   /// update is only added when determined to be necessary. Checks for
   /// self-domination, unnecessary updates, duplicate requests, and balanced
   /// pairs of requests are all performed. Returns true if the update is
   /// queued and false if it is discarded.

include/llvm/Support/GenericDomTree.h

void eraseNode(NodeT *BB) {
     // Remember to update PostDominatorTree roots.
     auto RIt = llvm::find(Roots, BB);
     if (RIt != Roots.end()) {
       std::swap(*RIt, Roots.back());
       Roots.pop_back();
     }
   }
 
-  /// splitBlock - BB is split and now it has one successor. Update dominator
-  /// tree to reflect this change.
-  void splitBlock(NodeT *NewBB) {
-    if (IsPostDominator)
-      Split<Inverse<NodeT *>>(NewBB);
-    else
-      Split<NodeT *>(NewBB);
-  }
-
   /// print - Convert to human readable form
   ///
   void print(raw_ostream &O) const {
     O << "=============================--------------------------------\n";
     if (IsPostDominator)
       O << "Inorder PostDominator Tree: ";
     else
       O << "Inorder Dominator Tree: ";
void reset() {
     DomTreeNodes.clear();
     Roots.clear();
     RootNode = nullptr;
     Parent = nullptr;
     DFSInfoValid = false;
     SlowQueries = 0;
   }
 
-  // NewBB is split and now it has one successor. Update dominator tree to
-  // reflect this change.
-  template <class N>
-  void Split(typename GraphTraits<N>::NodeRef NewBB) {
-    using GraphT = GraphTraits<N>;
-    using NodeRef = typename GraphT::NodeRef;
-    assert(std::distance(GraphT::child_begin(NewBB),
-                         GraphT::child_end(NewBB)) == 1 &&
-           "NewBB should have a single successor!");
-    NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
-
-    std::vector<NodeRef> PredBlocks;
-    for (const auto &Pred : children<Inverse<N>>(NewBB))
-      PredBlocks.push_back(Pred);
-
-    assert(!PredBlocks.empty() && "No predblocks?");
-
-    bool NewBBDominatesNewBBSucc = true;
-    for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) {
-      if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
-          isReachableFromEntry(Pred)) {
-        NewBBDominatesNewBBSucc = false;
-        break;
-      }
-    }
-
-    // Find NewBB's immediate dominator and create new dominator tree node for
-    // NewBB.
-    NodeT *NewBBIDom = nullptr;
-    unsigned i = 0;
-    for (i = 0; i < PredBlocks.size(); ++i)
-      if (isReachableFromEntry(PredBlocks[i])) {
-        NewBBIDom = PredBlocks[i];
-        break;
-      }
-
-    // It's possible that none of the predecessors of NewBB are reachable;
-    // in that case, NewBB itself is unreachable, so nothing needs to be
-    // changed.
-    if (!NewBBIDom) return;
-
-    for (i = i + 1; i < PredBlocks.size(); ++i) {
-      if (isReachableFromEntry(PredBlocks[i]))
-        NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
-    }
-
-    // Create the new dominator tree node... and set the idom of NewBB.
-    DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
-
-    // If NewBB strictly dominates other blocks, then it is now the immediate
-    // dominator of NewBBSucc.  Update the dominator tree as appropriate.
-    if (NewBBDominatesNewBBSucc) {
-      DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
-      changeImmediateDominator(NewBBSuccNode, NewBBNode);
-    }
-  }
-
  private:
   bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
                                const DomTreeNodeBase<NodeT> *B) const {
     assert(A != B);
     assert(isReachableFromEntry(B));
     assert(isReachableFromEntry(A));
 
     const DomTreeNodeBase<NodeT> *IDom;

include/llvm/Transforms/Utils/BasicBlockUtils.h

 /// The new predecessors are indicated by the Preds array. The new block is
 /// given a suffix of 'Suffix'. Returns new basic block to which predecessors
 /// from Preds are now pointing.
 ///
 /// If BB is a landingpad block then additional basicblock might be introduced.
 /// 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 and PostDominatorTree
+/// through DeferredDominance, 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, DeferredDominance *DDT,
+                                   LoopInfo *LI = nullptr,
+                                   bool PreserveLCSSA = false);
 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
                                    const char *Suffix,
                                    DominatorTree *DT = nullptr,
                                    LoopInfo *LI = nullptr,
                                    bool PreserveLCSSA = false);
 
 /// This method transforms the landing pad, OrigBB, by introducing two new basic
 /// blocks into the function. One of those new basic blocks gets the
 /// predecessors listed in Preds. The other basic block gets the remaining
 /// predecessors of OrigBB. The landingpad instruction OrigBB is clone into both
 /// of the new basic blocks. The new blocks are given the suffixes 'Suffix1' and
 /// 'Suffix2', and are returned in the NewBBs vector.
 ///
 /// 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).
 void SplitLandingPadPredecessors(BasicBlock *OrigBB,
                                  ArrayRef<BasicBlock *> Preds,
                                  const char *Suffix, const char *Suffix2,
                                  SmallVectorImpl<BasicBlock *> &NewBBs,
-                                 DominatorTree *DT = nullptr,
+                                 DeferredDominance *DDT = 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
 /// value defined by a PHI, propagate the right value into the return. It
 /// returns the new return instruction in the predecessor.
 ReturnInst *FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,

include/llvm/Transforms/Utils/LoopSimplify.h

 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
 
 /// \brief Simplify each loop in a loop nest recursively.
 ///
 /// 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.
+/// update DominatorTree/PostDominatorTree through DeferredDominance, LoopInfo
+/// and ScalarEvolution analyses if they're non-null.
+bool simplifyLoop(Loop *L, DeferredDominance *DDT, LoopInfo *LI,
+                  ScalarEvolution *SE, AssumptionCache *AC, bool PreserveLCSSA);
 bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE,
                   AssumptionCache *AC, bool PreserveLCSSA);
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_LOOPSIMPLIFY_H

include/llvm/Transforms/Utils/LoopUtils.h

 
 class AliasSet;
 class AliasSetTracker;
 class BasicBlock;
 class DataLayout;
 class Loop;
 class LoopInfo;
 class OptimizationRemarkEmitter;
+struct PostDominatorTree;
 class PredicatedScalarEvolution;
 class PredIteratorCache;
 class ScalarEvolution;
 class SCEV;
 class TargetLibraryInfo;
 class TargetTransformInfo;
 
 /// \brief Captures loop safety information.
private:
   const SCEV *Step = nullptr;
   // Instruction that advances induction variable.
   BinaryOperator *InductionBinOp = nullptr;
   // Instructions used for type-casts of the induction variable,
   // that are redundant when guarded with a runtime SCEV overflow check.
   SmallVector<Instruction *, 2> RedundantCasts;
 };
 
+BasicBlock *InsertPreheaderForLoop(Loop *L, DeferredDominance *DDT,
+                                   LoopInfo *LI, bool PreserveLCSSA);
 BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
                                    bool PreserveLCSSA);
 
 /// Ensure that all exit blocks of the loop are dedicated exits.
 ///
 /// 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.
+/// tree/postdominator tree (though DeferredDominance) and loop info if
+/// provided, and will preserve LCSSA if requested.
+bool formDedicatedExitBlocks(Loop *L, DeferredDominance *DDT, LoopInfo *LI,
+                             bool PreserveLCSSA);
 bool formDedicatedExitBlocks(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

lib/IR/Dominators.cpp

 // included in libvmcore, because it's not needed.  Forward dominators are
 // needed to support the Verifier pass.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/Dominators.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/GenericDomTreeConstruction.h"
 #include "llvm/Support/raw_ostream.h"

 //  DeferredDominance Implementation
 //===----------------------------------------------------------------------===//
 //
 // The implementation details of the DeferredDominance class which allows
 // one to queue updates to a DominatorTree.
 //
 //===----------------------------------------------------------------------===//
 
+DeferredDominance::~DeferredDominance() { flush(); }
+
 /// \brief Queues multiple updates and discards duplicates.
 void DeferredDominance::applyUpdates(
     ArrayRef<DominatorTree::UpdateType> Updates) {
   SmallVector<DominatorTree::UpdateType, 8> Seen;
   for (auto U : Updates)
     // Avoid duplicates to applyUpdate() to save on analysis.
     if (std::none_of(Seen.begin(), Seen.end(),
                      [U](DominatorTree::UpdateType S) { return S == U; })) {

 
 /// \brief Returns true if DelBB is awaiting deletion at a flush() event.
 bool DeferredDominance::pendingDeletedBB(BasicBlock *DelBB) {
   if (DeletedBBs.empty())
     return false;
   return DeletedBBs.count(DelBB) != 0;
 }
 
-/// \brief Flushes all pending updates and block deletions. Returns a
-/// correct DominatorTree reference to be used by the caller for analysis.
-DominatorTree &DeferredDominance::flush() {
+/// \brief Flushes all pending updates and block deletions.
+void DeferredDominance::flush() {
   // Updates to DT must happen before blocks are deleted below. Otherwise the
   // DT traversal will encounter badref blocks and assert.
   if (!PendUpdates.empty()) {
     DT.applyUpdates(PendUpdates);
+    if (PDT)
+      PDT->applyUpdates(PendUpdates);
     PendUpdates.clear();
   }
   flushDelBB();
+}
+
+/// \brief Flushes and returns a correct DominatorTree reference to
+/// be used by the caller for analysis.
+DominatorTree &DeferredDominance::getDT() {
+  flush();
   return DT;
 }
 
+/// \brief Flushes and returns a correct PostDominatorTree reference to
+/// be used by the caller for analysis.
+PostDominatorTree *DeferredDominance::getPDT() {
+  flush();
+  return PDT;
+}
+
 /// \brief Drops all internal state and forces a (slow) recalculation of the
 /// DominatorTree based on the current state of the LLVM IR in F. This should
 /// only be used in corner cases such as the Entry block of F being deleted.
 void DeferredDominance::recalculate(Function &F) {
   // flushDelBB must be flushed before the recalculation. The state of the IR
   // must be consistent before the DT traversal algorithm determines the
   // actual DT.
   if (flushDelBB() || !PendUpdates.empty()) {
     DT.recalculate(F);
+    if (PDT)
+      PDT->recalculate(F);
     PendUpdates.clear();
   }
 }
 
 /// \brief Debug method to help view the state of pending updates.
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void DeferredDominance::dump() const {
   raw_ostream &OS = llvm::dbgs();

 
 /// Performs all pending basic block deletions. We have to defer the deletion
 /// of these blocks until after the DominatorTree updates are applied. The
 /// internal workings of the DominatorTree code expect every update's From
 /// and To blocks to exist and to be a member of the same Function.
 bool DeferredDominance::flushDelBB() {
   if (DeletedBBs.empty())
     return false;
-  for (auto *BB : DeletedBBs)
+  for (auto *BB : DeletedBBs) {
+    if (PDT && PDT->getNode(BB))
+      PDT->eraseNode(BB);
     BB->eraseFromParent();
+  }
   DeletedBBs.clear();
   return true;
 }

lib/Transforms/Scalar/LoopStrengthReduce.cpp

if (PN->getIncomingValue(i) == LF.OperandValToReplace) {
           BasicBlock *NewBB = nullptr;
           if (!Parent->isLandingPad()) {
             NewBB = SplitCriticalEdge(BB, Parent,
                                       CriticalEdgeSplittingOptions(&DT, &LI)
                                           .setMergeIdenticalEdges()
                                           .setDontDeleteUselessPHIs());
           } else {
             SmallVector<BasicBlock*, 2> NewBBs;
-            SplitLandingPadPredecessors(Parent, BB, "", "", NewBBs, &DT, &LI);
+            DeferredDominance DDT(DT);
+            SplitLandingPadPredecessors(Parent, BB, "", "", NewBBs, &DDT, &LI);
             NewBB = NewBBs[0];
           }
           // If NewBB==NULL, then SplitCriticalEdge refused to split because all
           // phi predecessors are identical. The simple thing to do is skip
           // splitting in this case rather than complicate the API.
           if (NewBB) {
             // If PN is outside of the loop and BB is in the loop, we want to
             // move the block to be immediately before the PHI block, not

lib/Transforms/Utils/BasicBlockUtils.cpp

 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Twine.h"
 #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"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
if (DT)
     }
 
   return New;
 }
 
 /// Update DominatorTree, LoopInfo, and LCCSA analysis information.
 static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB,
                                       ArrayRef<BasicBlock *> Preds,
-                                      DominatorTree *DT, LoopInfo *LI,
+                                      DeferredDominance *DDT, LoopInfo *LI,
                                       bool PreserveLCSSA, bool &HasLoopExit) {
   // Update dominator tree if available.
-  if (DT)
-    DT->splitBlock(NewBB);
+  if (DDT) {
+    std::vector<DominatorTree::UpdateType> Updates;
+    Updates.push_back({DominatorTree::UpdateKind::Insert, NewBB, OldBB});
+    for (auto *Pred : Preds) {
+      Updates.push_back({DominatorTree::UpdateKind::Insert, Pred, NewBB});
+      Updates.push_back({DominatorTree::UpdateKind::Delete, Pred, OldBB});
+    }
+    DDT->applyUpdates(Updates);
+  }
 
   // The rest of the logic is only relevant for updating the loop structures.
   if (!LI)
     return;
 
-  assert(DT && "DT should be available to update LoopInfo!");
+  assert(DDT && "DDT should be available to update LoopInfo!");
+  DominatorTree &DT = DDT->getDT();
   Loop *L = LI->getLoopFor(OldBB);
 
   // If we need to preserve loop analyses, collect some information about how
   // this split will affect loops.
   bool IsLoopEntry = !!L;
   bool SplitMakesNewLoopHeader = false;
   for (BasicBlock *Pred : Preds) {
     // Preds that are not reachable from entry should not be used to identify if
     // OldBB is a loop entry or if SplitMakesNewLoopHeader. Unreachable blocks
     // are not within any loops, so we incorrectly mark SplitMakesNewLoopHeader
     // as true and make the NewBB the header of some loop. This breaks LI.
-    if (!DT->isReachableFromEntry(Pred))
+    if (!DT.isReachableFromEntry(Pred))
       continue;
     // If we need to preserve LCSSA, determine if any of the preds is a loop
     // exit.
     if (PreserveLCSSA)
       if (Loop *PL = LI->getLoopFor(Pred))
         if (!PL->contains(OldBB))
           HasLoopExit = true;
 
for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {
     }
 
     PN->addIncoming(NewPHI, NewBB);
   }
 }
 
 BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
                                          ArrayRef<BasicBlock *> Preds,
-                                         const char *Suffix, DominatorTree *DT,
-                                         LoopInfo *LI, bool PreserveLCSSA) {
+                                         const char *Suffix,
+                                         DeferredDominance *DDT, LoopInfo *LI,
+                                         bool PreserveLCSSA) {
   // Do not attempt to split that which cannot be split.
   if (!BB->canSplitPredecessors())
     return nullptr;
 
   // For the landingpads we need to act a bit differently.
   // Delegate this work to the SplitLandingPadPredecessors.
   if (BB->isLandingPad()) {
     SmallVector<BasicBlock*, 2> NewBBs;
     std::string NewName = std::string(Suffix) + ".split-lp";
 
-    SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs, DT,
+    SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs, DDT,
                                 LI, PreserveLCSSA);
     return NewBBs[0];
   }
 
   // Create new basic block, insert right before the original block.
   BasicBlock *NewBB = BasicBlock::Create(
       BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB);
 
if (Preds.empty()) {
     // Insert dummy values as the incoming value.
     for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
       cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
     return NewBB;
   }
 
   // Update DominatorTree, LoopInfo, and LCCSA analysis information.
   bool HasLoopExit = false;
-  UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, PreserveLCSSA,
+  UpdateAnalysisInformation(BB, NewBB, Preds, DDT, LI, PreserveLCSSA,
                             HasLoopExit);
 
   // Update the PHI nodes in BB with the values coming from NewBB.
   UpdatePHINodes(BB, NewBB, Preds, BI, HasLoopExit);
   return NewBB;
 }
 
+BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
+                                         ArrayRef<BasicBlock *> Preds,
+                                         const char *Suffix, DominatorTree *DT,
+                                         LoopInfo *LI, bool PreserveLCSSA) {
+  if (DT) {
+    DeferredDominance DDT(*DT);
+    return SplitBlockPredecessors(BB, Preds, Suffix, &DDT, LI, PreserveLCSSA);
+  }
+  return SplitBlockPredecessors(BB, Preds, Suffix, (DeferredDominance *)nullptr,
+                                LI, PreserveLCSSA);
+}
+
 void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB,
                                        ArrayRef<BasicBlock *> Preds,
                                        const char *Suffix1, const char *Suffix2,
                                        SmallVectorImpl<BasicBlock *> &NewBBs,
-                                       DominatorTree *DT, LoopInfo *LI,
+                                       DeferredDominance *DDT, LoopInfo *LI,
                                        bool PreserveLCSSA) {
   assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!");
 
   // Create a new basic block for OrigBB's predecessors listed in Preds. Insert
   // it right before the original block.
   BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(),
                                           OrigBB->getName() + Suffix1,
                                           OrigBB->getParent(), OrigBB);
for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
     // is that there be no more than one indirectbr branching to BB. And
     // all BlockAddress uses would need to be updated.
     assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
            "Cannot split an edge from an IndirectBrInst");
     Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
   }
 
   bool HasLoopExit = false;
-  UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, PreserveLCSSA,
+  UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DDT, LI, PreserveLCSSA,
                             HasLoopExit);
 
   // Update the PHI nodes in OrigBB with the values coming from NewBB1.
   UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit);
 
   // Move the remaining edges from OrigBB to point to NewBB2.
   SmallVector<BasicBlock*, 8> NewBB2Preds;
   for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB);
if (!NewBB2Preds.empty()) {
     // The new block unconditionally branches to the old block.
     BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2);
     BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
 
     // Move the remaining edges from OrigBB to point to NewBB2.
     for (BasicBlock *NewBB2Pred : NewBB2Preds)
       NewBB2Pred->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
 
     // Update DominatorTree, LoopInfo, and LCCSA analysis information.
     HasLoopExit = false;
-    UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI,
+    UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DDT, LI,
                               PreserveLCSSA, HasLoopExit);
 
     // Update the PHI nodes in OrigBB with the values coming from NewBB2.
     UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit);
   }
 
   LandingPadInst *LPad = OrigBB->getLandingPadInst();
   Instruction *Clone1 = LPad->clone();

lib/Transforms/Utils/BreakCriticalEdges.cpp

if (Loop *TIL = LI->getLoopFor(TIBB)) {
             // No need to re-simplify, it wasn't to start with.
             LoopPreds.clear();
             break;
           }
           LoopPreds.push_back(P);
         }
         if (!LoopPreds.empty()) {
           assert(!DestBB->isEHPad() && "We don't split edges to EH pads!");
+          DeferredDominance DDT(*DT);
           BasicBlock *NewExitBB = SplitBlockPredecessors(
-              DestBB, LoopPreds, "split", DT, LI, Options.PreserveLCSSA);
+              DestBB, LoopPreds, "split", &DDT, LI, Options.PreserveLCSSA);
           if (Options.PreserveLCSSA)
             createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB);
         }
       }
     }
   }
 
   return NewBB;

lib/Transforms/Utils/LoopSimplify.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #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"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
if (!FoundBB)
     FoundBB = SplitPreds[0];
   NewBB->moveAfter(FoundBB);
 }
 
 /// InsertPreheaderForLoop - Once we discover that a loop doesn't have a
 /// preheader, this method is called to insert one.  This method has two phases:
 /// preheader insertion and analysis updating.
 ///
-BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, DominatorTree *DT,
+BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, DeferredDominance *DDT,
                                          LoopInfo *LI, bool PreserveLCSSA) {
   BasicBlock *Header = L->getHeader();
 
   // Compute the set of predecessors of the loop that are not in the loop.
   SmallVector<BasicBlock*, 8> OutsideBlocks;
   for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header);
        PI != PE; ++PI) {
     BasicBlock *P = *PI;
     if (!L->contains(P)) {         // Coming in from outside the loop?
       // If the loop is branched to from an indirect branch, we won't
       // be able to fully transform the loop, because it prohibits
       // edge splitting.
       if (isa<IndirectBrInst>(P->getTerminator())) return nullptr;
 
       // Keep track of it.
       OutsideBlocks.push_back(P);
     }
   }
 
   // Split out the loop pre-header.
   BasicBlock *PreheaderBB;
-  PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", DT,
+  PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", DDT,
                                        LI, PreserveLCSSA);
   if (!PreheaderBB)
     return nullptr;
 
   DEBUG(dbgs() << "LoopSimplify: Creating pre-header "
                << PreheaderBB->getName() << "\n");
 
   // Make sure that NewBB is put someplace intelligent, which doesn't mess up
   // code layout too horribly.
   placeSplitBlockCarefully(PreheaderBB, OutsideBlocks, L);
 
   return PreheaderBB;
 }
+BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, DominatorTree *DT,
+                                         LoopInfo *LI, bool PreserveLCSSA) {
+  if (DT) {
+    DeferredDominance DDT(*DT);
+    return InsertPreheaderForLoop(L, &DDT, LI, PreserveLCSSA);
+  }
+  return InsertPreheaderForLoop(L, (DeferredDominance *)nullptr, LI,
+                                PreserveLCSSA);
+}
 
 /// Add the specified block, and all of its predecessors, to the specified set,
 /// if it's not already in there.  Stop predecessor traversal when we reach
 /// StopBlock.
 static void addBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock,
                                   std::set<BasicBlock*> &Blocks) {
   SmallVector<BasicBlock *, 8> Worklist;
   Worklist.push_back(InputBB);
   do {
     BasicBlock *BB = Worklist.pop_back_val();
     if (Blocks.insert(BB).second && BB != StopBlock)
       // If BB is not already processed and it is not a stop block then
       // insert its predecessor in the work list
       for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) {
         BasicBlock *WBB = *I;
         Worklist.push_back(WBB);
       }
   } while (!Worklist.empty());
 }
 
 /// \brief The first part of loop-nestification is to find a PHI node that tells
 /// us how to partition the loops.
-static PHINode *findPHIToPartitionLoops(Loop *L, DominatorTree *DT,
+static PHINode *findPHIToPartitionLoops(Loop *L, DeferredDominance *DDT,
                                         AssumptionCache *AC) {
   const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
+  DominatorTree &DT = DDT->getDT();
   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) {
     PHINode *PN = cast<PHINode>(I);
     ++I;
-    if (Value *V = SimplifyInstruction(PN, {DL, nullptr, DT, AC})) {
+    if (Value *V = SimplifyInstruction(PN, {DL, nullptr, &DT, AC})) {
       // This is a degenerate PHI already, don't modify it!
       PN->replaceAllUsesWith(V);
       PN->eraseFromParent();
       continue;
     }
 
     // Scan this PHI node looking for a use of the PHI node by itself.
     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)

 /// To identify this common case, we look at the PHI nodes in the header of the
 /// loop.  PHI nodes with unchanging values on one backedge correspond to values
 /// that change in the "outer" loop, but not in the "inner" loop.
 ///
 /// If we are able to separate out a loop, return the new outer loop that was
 /// created.
 ///
 static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
-                                DominatorTree *DT, LoopInfo *LI,
+                                DeferredDominance *DDT, LoopInfo *LI,
                                 ScalarEvolution *SE, bool PreserveLCSSA,
                                 AssumptionCache *AC) {
   // Don't try to separate loops without a preheader.
   if (!Preheader)
     return nullptr;
 
   // The header is not a landing pad; preheader insertion should ensure this.
   BasicBlock *Header = L->getHeader();
   assert(!Header->isEHPad() && "Can't insert backedge to EH pad");
 
-  PHINode *PN = findPHIToPartitionLoops(L, DT, AC);
+  PHINode *PN = findPHIToPartitionLoops(L, DDT, AC);
   if (!PN) return nullptr;  // No known way to partition.
 
   // Pull out all predecessors that have varying values in the loop.  This
   // handles the case when a PHI node has multiple instances of itself as
   // arguments.
   SmallVector<BasicBlock*, 8> OuterLoopPreds;
   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
     if (PN->getIncomingValue(i) != PN ||
         !L->contains(PN->getIncomingBlock(i))) {
       // We can't split indirectbr edges.
       if (isa<IndirectBrInst>(PN->getIncomingBlock(i)->getTerminator()))
         return nullptr;
       OuterLoopPreds.push_back(PN->getIncomingBlock(i));
     }
   }
   DEBUG(dbgs() << "LoopSimplify: Splitting out a new outer loop\n");
 
   // If ScalarEvolution is around and knows anything about values in
   // this loop, tell it to forget them, because we're about to
   // substantially change it.
   if (SE)
     SE->forgetLoop(L);
 
   BasicBlock *NewBB = SplitBlockPredecessors(Header, OuterLoopPreds, ".outer",
-                                             DT, LI, PreserveLCSSA);
+                                             DDT, LI, PreserveLCSSA);
 
   // Make sure that NewBB is put someplace intelligent, which doesn't mess up
   // code layout too horribly.
   placeSplitBlockCarefully(NewBB, OuterLoopPreds, L);
 
   // Create the new outer loop.
   Loop *NewOuter = LI->AllocateLoop();
 
static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
 
   // Now reset the header in L, which had been moved by
   // SplitBlockPredecessors for the outer loop.
   L->moveToHeader(Header);
 
   // Determine which blocks should stay in L and which should be moved out to
   // the Outer loop now.
   std::set<BasicBlock*> BlocksInL;
+  DominatorTree &DT = DDT->getDT();
   for (pred_iterator PI=pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) {
     BasicBlock *P = *PI;
-    if (DT->dominates(Header, P))
+    if (DT.dominates(Header, P))
       addBlockAndPredsToSet(P, Header, BlocksInL);
   }
 
   // Scan all of the loop children of L, moving them to OuterLoop if they are
   // not part of the inner loop.
   const std::vector<Loop*> &SubLoops = L->getSubLoops();
   for (size_t I = 0; I != SubLoops.size(); )
     if (BlocksInL.count(SubLoops[I]->getHeader()))
if (!BlocksInL.count(BB)) {
         OuterLoopBlocks.push_back(BB);
       }
       --i;
     }
   }
 
   // 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, DDT, LI, PreserveLCSSA);
 
   if (PreserveLCSSA) {
     // Fix LCSSA form for L. Some values, which previously were only used inside
     // L, can now be used in NewOuter loop. We need to insert phi-nodes for them
     // in corresponding exit blocks.
     // We don't need to form LCSSA recursively, because there cannot be uses
     // inside a newly created loop of defs from inner loops as those would
     // already be a use of an LCSSA phi node.
-    formLCSSA(*L, *DT, LI, SE);
+    DominatorTree &DT = DDT->getDT();
+    formLCSSA(*L, DT, LI, SE);
 
-    assert(NewOuter->isRecursivelyLCSSAForm(*DT, *LI) &&
+    assert(NewOuter->isRecursivelyLCSSAForm(DT, *LI) &&
            "LCSSA is broken after separating nested loops!");
   }
 
   return NewOuter;
 }
 
 /// \brief This method is called when the specified loop has more than one
 /// backedge in it.
 ///
 /// If this occurs, revector all of these backedges to target a new basic block
 /// 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) {
+                                             DeferredDominance *DDT,
+                                             LoopInfo *LI) {
   assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!");
 
   // Get information about the loop
   BasicBlock *Header = L->getHeader();
   Function *F = Header->getParent();
 
   // Unique backedge insertion currently depends on having a preheader.
   if (!Preheader)
static BasicBlock *insertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader,
 
   //===--- Update all analyses which we must preserve now -----------------===//
 
   // Update Loop Information - we know that this block is now in the current
   // loop and all parent loops.
   L->addBasicBlockToLoop(BEBlock, *LI);
 
   // Update dominator information
-  DT->splitBlock(BEBlock);
+  std::vector<DominatorTree::UpdateType> Updates;
+  Updates.push_back({DominatorTree::UpdateKind::Insert, BEBlock, Header});
+  for (auto *BB : BackedgeBlocks) {
+    Updates.push_back({DominatorTree::UpdateKind::Insert, BB, BEBlock});
+    Updates.push_back({DominatorTree::UpdateKind::Delete, BB, Header});
+  }
+  DDT->applyUpdates(Updates);
 
   return BEBlock;
 }
 
 /// \brief Simplify one loop and queue further loops for simplification.
 static bool simplifyOneLoop(Loop *L, SmallVectorImpl<Loop *> &Worklist,
-                            DominatorTree *DT, LoopInfo *LI,
+                            DeferredDominance *DDT, LoopInfo *LI,
                             ScalarEvolution *SE, AssumptionCache *AC,
                             bool PreserveLCSSA) {
   bool Changed = false;
 ReprocessLoop:
 
   // Check to see that no blocks (other than the header) in this loop have
   // predecessors that are not in the loop.  This is not valid for natural
   // loops, but can occur if the blocks are unreachable.  Since they are
for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
     // Delete each unique out-of-loop (and thus dead) predecessor.
     for (BasicBlock *P : BadPreds) {
 
       DEBUG(dbgs() << "LoopSimplify: Deleting edge from dead predecessor "
                    << P->getName() << "\n");
 
       // Zap the dead pred's terminator and replace it with unreachable.
       TerminatorInst *TI = P->getTerminator();
-      changeToUnreachable(TI, /*UseLLVMTrap=*/false, PreserveLCSSA);
+      changeToUnreachable(TI, /*UseLLVMTrap=*/false, PreserveLCSSA, DDT);
       Changed = true;
     }
   }
 
   // If there are exiting blocks with branches on undef, resolve the undef in
   // the direction which will exit the loop. This will help simplify loop
   // trip count computations.
   SmallVector<BasicBlock*, 8> ExitingBlocks;
if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
 
           Changed = true;
         }
       }
 
   // 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, DDT, LI, PreserveLCSSA);
     if (Preheader)
       Changed = true;
   }
 
   // Next, check to make sure that all exit nodes of the loop only have
   // 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, DDT, LI, PreserveLCSSA))
     Changed = true;
 
   // If the header has more than two predecessors at this point (from the
   // preheader and from multiple backedges), we must adjust the loop.
   BasicBlock *LoopLatch = L->getLoopLatch();
   if (!LoopLatch) {
     // If this is really a nested loop, rip it out into a child loop.  Don't do
     // 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, DDT, LI, SE,
+                                            PreserveLCSSA, AC)) {
         ++NumNested;
         // Enqueue the outer loop as it should be processed next in our
         // depth-first nest walk.
         Worklist.push_back(OuterL);
 
         // This is a big restructuring change, reprocess the whole loop.
         Changed = true;
         // GCC doesn't tail recursion eliminate this.
         // FIXME: It isn't clear we can't rely on LLVM to TRE this.
         goto ReprocessLoop;
       }
     }
 
     // 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, DDT, LI);
     if (LoopLatch)
       Changed = true;
   }
 
   const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
+  DominatorTree *DT = DDT ? &DDT->getDT() : nullptr;
 
   // Scan over the PHI nodes in the loop header.  Since they now have only two
   // incoming values (the loop is canonicalized), we may have simplified the PHI
   // down to 'X = phi [X, Y]', which should be replaced with 'Y'.
   PHINode *PN;
   for (BasicBlock::iterator I = L->getHeader()->begin();
        (PN = dyn_cast<PHINode>(I++)); )
     if (Value *V = SimplifyInstruction(PN, {DL, nullptr, DT, AC})) {
for (auto *ExitingBB : ExitingBlocks)
           return false;
       }
 
     return true;
   };
   if (HasUniqueExitBlock()) {
     for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
       BasicBlock *ExitingBlock = ExitingBlocks[i];
-      if (!ExitingBlock->getSinglePredecessor()) continue;
+      BasicBlock *Predecessor = ExitingBlock->getSinglePredecessor();
+      if (!Predecessor) continue;
       BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
       if (!BI || !BI->isConditional()) continue;
       CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
       if (!CI || CI->getParent() != ExitingBlock) continue;
 
       // Attempt to hoist out all instructions except for the
       // comparison and the branch.
       bool AllInvariant = true;
for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
         Changed = true;
         // The loop disposition of all SCEV expressions that depend on any
         // hoisted values have also changed.
         if (SE)
           SE->forgetLoopDispositions(L);
       }
       if (!AllInvariant) continue;
 
+      // Get a list of required Dominator Tree edge updates
+      std::vector<DominatorTree::UpdateType> DTUpdates;
+      TerminatorInst *PredecessorTerm = Predecessor->getTerminator();
+      BasicBlock *PredOtherBB = ExitingBlock == PredecessorTerm->getSuccessor(0)
+                                    ? PredecessorTerm->getNumSuccessors() == 1
+                                          ? nullptr
+                                          : PredecessorTerm->getSuccessor(1)
+                                    : PredecessorTerm->getSuccessor(0);
+      BasicBlock *OtherBB = PredOtherBB == BI->getSuccessor(0)
+                                ? BI->getSuccessor(1)
+                                : BI->getSuccessor(0);
+      DTUpdates.push_back(
+          {DominatorTree::UpdateKind::Insert, Predecessor, OtherBB});
+      DTUpdates.push_back(
+          {DominatorTree::UpdateKind::Delete, Predecessor, ExitingBlock});
+      DTUpdates.push_back({DominatorTree::UpdateKind::Delete, ExitingBlock,
+                           BI->getSuccessor(0)});
+      DTUpdates.push_back({DominatorTree::UpdateKind::Delete, ExitingBlock,
+                           BI->getSuccessor(1)});
+
       // The block has now been cleared of all instructions except for
       // a comparison and a conditional branch. SimplifyCFG may be able
       // to fold it now.
       if (!FoldBranchToCommonDest(BI))
         continue;
 
       // Success. The block is now dead, so remove it from the loop,
       // update the dominator tree and delete it.
       DEBUG(dbgs() << "LoopSimplify: Eliminating exiting block "
                    << ExitingBlock->getName() << "\n");
 
       // Notify ScalarEvolution before deleting this block. Currently assume the
       // parent loop doesn't change (spliting edges doesn't count). If blocks,
       // CFG edges, or other values in the parent loop change, then we need call
       // to forgetLoop() for the parent instead.
       if (SE)
         SE->forgetLoop(L);
 
       assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock));
       Changed = true;
       LI->removeBlock(ExitingBlock);
 
-      DomTreeNode *Node = DT->getNode(ExitingBlock);
-      const std::vector<DomTreeNodeBase<BasicBlock> *> &Children =
-        Node->getChildren();
-      while (!Children.empty()) {
-        DomTreeNode *Child = Children.front();
-        DT->changeImmediateDominator(Child, Node->getIDom());
-      }
-      DT->eraseNode(ExitingBlock);
-
       BI->getSuccessor(0)->removePredecessor(
           ExitingBlock, /* DontDeleteUselessPHIs */ PreserveLCSSA);
       BI->getSuccessor(1)->removePredecessor(
           ExitingBlock, /* DontDeleteUselessPHIs */ PreserveLCSSA);
-      ExitingBlock->eraseFromParent();
+
+      DDT->deleteBB(ExitingBlock);
+      DDT->applyUpdates(DTUpdates);
     }
   }
 
   return Changed;
 }
 
-bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
+bool llvm::simplifyLoop(Loop *L, DeferredDominance *DDT, LoopInfo *LI,
                         ScalarEvolution *SE, AssumptionCache *AC,
                         bool PreserveLCSSA) {
   bool Changed = false;
 
 #ifndef NDEBUG
   // If we're asked to preserve LCSSA, the loop nest needs to start in LCSSA
   // form.
   if (PreserveLCSSA) {
-    assert(DT && "DT not available.");
+    assert(DDT && "DT not available.");
+    DominatorTree &DT = DDT->getDT();
     assert(LI && "LI not available.");
-    assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
+    assert(L->isRecursivelyLCSSAForm(DT, *LI) &&
            "Requested to preserve LCSSA, but it's already broken.");
   }
 #endif
 
   // Worklist maintains our depth-first queue of loops in this nest to process.
   SmallVector<Loop *, 4> Worklist;
   Worklist.push_back(L);
 
   // Walk the worklist from front to back, pushing newly found sub loops onto
   // the back. This will let us process loops from back to front in depth-first
   // order. We can use this simple process because loops form a tree.
   for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
     Loop *L2 = Worklist[Idx];
     Worklist.append(L2->begin(), L2->end());
   }
 
   while (!Worklist.empty())
-    Changed |= simplifyOneLoop(Worklist.pop_back_val(), Worklist, DT, LI, SE,
+    Changed |= simplifyOneLoop(Worklist.pop_back_val(), Worklist, DDT, LI, SE,
                                AC, PreserveLCSSA);
 
   return Changed;
 }
 
+bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
+                        ScalarEvolution *SE, AssumptionCache *AC,
+                        bool PreserveLCSSA) {
+  if (DT) {
+    DeferredDominance DDT(*DT);
+    return simplifyLoop(L, &DDT, LI, SE, AC, PreserveLCSSA);
+  }
+  return simplifyLoop(L, (DeferredDominance *)nullptr, LI, SE, AC,
+                      PreserveLCSSA);
+}
+
 namespace {
   struct LoopSimplify : public FunctionPass {
     static char ID; // Pass identification, replacement for typeid
     LoopSimplify() : FunctionPass(ID) {
       initializeLoopSimplifyPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<AssumptionCacheTracker>();
 
       // We need loop information to identify the loops...
       AU.addRequired<DominatorTreeWrapperPass>();
       AU.addPreserved<DominatorTreeWrapperPass>();
+      AU.addPreserved<PostDominatorTreeWrapperPass>();
 
       AU.addRequired<LoopInfoWrapperPass>();
       AU.addPreserved<LoopInfoWrapperPass>();
 
       AU.addPreserved<BasicAAWrapperPass>();
       AU.addPreserved<AAResultsWrapperPass>();
       AU.addPreserved<GlobalsAAWrapperPass>();
       AU.addPreserved<ScalarEvolutionWrapperPass>();

 
 /// runOnFunction - Run down all loops in the CFG (recursively, but we could do
 /// it in any convenient order) inserting preheaders...
 ///
 bool LoopSimplify::runOnFunction(Function &F) {
   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 =
       &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
 
   bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
+  DeferredDominance DDT(*DT, PDT);
 
   // 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, &DDT, LI, SE, AC, PreserveLCSSA);
+
+  DDT.flush();
 
 #ifndef NDEBUG
   if (PreserveLCSSA) {
     bool InLCSSA = all_of(
         *LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, *LI); });
     assert(InLCSSA && "LCSSA is broken after loop-simplify.");
   }
 #endif
+
   return Changed;
 }
 
 PreservedAnalyses LoopSimplifyPass::run(Function &F,
                                         FunctionAnalysisManager &AM) {
   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);
+  DeferredDominance DDT(*DT, PDT);
 
   // 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, &DDT, 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>();
   PA.preserve<SCEVAA>();
   PA.preserve<ScalarEvolutionAnalysis>();
   PA.preserve<DependenceAnalysis>();
   return PA;
 }

lib/Transforms/Utils/LoopUtils.cpp

bool InductionDescriptor::isInductionPHI(
   if (CVSize % Size)
     return false;
   auto *StepValue = SE->getConstant(CV->getType(), CVSize / Size,
                                     true /* signed */);
   D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue);
   return true;
 }
 
-bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
-                                   bool PreserveLCSSA) {
+bool llvm::formDedicatedExitBlocks(Loop *L, DeferredDominance *DDT,
+                                   LoopInfo *LI, bool PreserveLCSSA) {
   bool Changed = false;
 
   // We re-use a vector for the in-loop predecesosrs.
   SmallVector<BasicBlock *, 4> InLoopPredecessors;
 
   auto RewriteExit = [&](BasicBlock *BB) {
     assert(InLoopPredecessors.empty() &&
            "Must start with an empty predecessors list!");
auto RewriteExit = [&](BasicBlock *BB) {
 
     assert(!InLoopPredecessors.empty() && "Must have *some* loop predecessor!");
 
     // Nothing to do if this is already a dedicated exit.
     if (IsDedicatedExit)
       return false;
 
     auto *NewExitBB = SplitBlockPredecessors(
-        BB, InLoopPredecessors, ".loopexit", DT, LI, PreserveLCSSA);
+        BB, InLoopPredecessors, ".loopexit", DDT, LI, PreserveLCSSA);
 
     if (!NewExitBB)
       DEBUG(dbgs() << "WARNING: Can't create a dedicated exit block for loop: "
                    << *L << "\n");
     else
       DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block "
                    << NewExitBB->getName() << "\n");
     return true;
for (auto *SuccBB : successors(BB)) {
         continue;
 
       Changed |= RewriteExit(SuccBB);
     }
 
   return Changed;
 }
 
+bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
+                                   bool PreserveLCSSA) {
+  if (DT) {
+    DeferredDominance DDT(*DT);
+    return formDedicatedExitBlocks(L, &DDT, LI, PreserveLCSSA);
+  }
+  return formDedicatedExitBlocks(L, (DeferredDominance *)nullptr, LI,
+                                 PreserveLCSSA);
+}
+
 /// \brief Returns the instructions that use values defined in the loop.
 SmallVector<Instruction *, 8> llvm::findDefsUsedOutsideOfLoop(Loop *L) {
   SmallVector<Instruction *, 8> UsedOutside;
 
   for (auto *Block : L->getBlocks())
     // FIXME: I believe that this could use copy_if if the Inst reference could
     // be adapted into a pointer.
     for (auto &Inst : *Block) {

test/Transforms/LoopSimplify/2004-04-13-LoopSimplifyUpdateDomFrontier.ll

-; 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:
   br label %loopentry.0.outer1111
 loopentry.0.outer1111:    ; preds = %then.41, %label.11, %loopentry.0.outer1111, %entry
   %left.0.ph1107 = phi i32 [ %tmp.1172, %then.41 ], [ 0, %entry ], [ %tmp.1172, %label.11 ], [ %left.0.ph1107, %loopentry.0.outer1111 ]    ; <i32> [#uses=2]
   %tmp.1172 = sub i32 %left.0.ph1107, 0   ; <i32> [#uses=2]
   switch i32 0, label %label.11 [

test/Transforms/LoopSimplify/2010-07-15-IncorrectDomFrontierUpdate.ll

-; 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 {
 entry:
   br i1 undef, label %bb37, label %bb1.i
 
 bb1.i:                                            ; preds = %bb1.i, %bb
   %indvar = phi i64 [ %indvar.next, %bb1.i ], [ 0, %entry ] ; <i64> [#uses=1]

test/Transforms/LoopSimplify/indirectbr.ll

-; 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
 
 ; LoopSimplify should not try to transform loops when indirectbr is involved.
 
 define void @entry(i8* %x) {
 entry:
   indirectbr i8* %x, [ label %L0, label %L1 ]

test/Transforms/LoopSimplify/merge-exits.ll

-; 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
 ; that indvars can promote the induction variable to i64
 ; without needing casts.
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n32:64"
 

test/Transforms/LoopSimplify/preserve-pdt.ll

+; RUN: opt -passes="require<postdomtree>,loop-simplify,print<postdomtree>" -verify-dom-info -S %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] %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:     [2] %for.inc {4294967295,4294967295} [1]
+; CHECK: Roots: %end %for.inc
+
+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
+}

test/Transforms/LoopSimplify/unreachable-loop-pred.ll

-; 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
 ; block to the enclosing loop and not get confused by the unreachable
 ; bogus loop entry.
 
 define void @is_extract_cab() nounwind {
 entry:

unittests/IR/DeferredDominanceTest.cpp

 //===- llvm/unittests/IR/DeferredDominanceTest.cpp - DDT unit tests -------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/Analysis/PostDominators.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
TEST(DeferredDominance, BasicOperations) {
   // Make the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
   Function *F = M->getFunction(FuncName);
   ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << ".";
 
   // Make the DDT.
   DominatorTree DT(*F);
-  DeferredDominance DDT(DT);
-  ASSERT_TRUE(DDT.flush().verify());
+  PostDominatorTree PDT(*F);
+  DeferredDominance DDT(DT, &PDT);
+  ASSERT_TRUE(DDT.getDT().verify());
+  ASSERT_TRUE(DDT.getPDT()->verify());
 
   Function::iterator FI = F->begin();
   BasicBlock *BB0 = &*FI++;
   BasicBlock *BB1 = &*FI++;
   BasicBlock *BB2 = &*FI++;
   BasicBlock *BB3 = &*FI++;
 
   // Test discards of invalid self-domination updates. These use the single
TEST(DeferredDominance, BasicOperations) {
   DDT.deleteBB(BB3);
   EXPECT_TRUE(DDT.pendingDeletedBB(BB3));
   ASSERT_TRUE(isa<UnreachableInst>(BB3->getTerminator()));
   EXPECT_EQ(BB3->getParent(), F);
 
   // Verify. Updates to DDT must be applied *after* all changes to the CFG
   // (including block deletion).
   DDT.applyUpdates(Updates);
-  ASSERT_TRUE(DDT.flush().verify());
+  ASSERT_TRUE(DDT.getDT().verify());
+  ASSERT_TRUE(DDT.getPDT()->verify());
 }
 
 TEST(DeferredDominance, PairedUpdate) {
   StringRef FuncName = "f";
   StringRef ModuleString =
       "define i32 @f(i32 %i, i32 *%p) {\n"
       " bb0:\n"
       "   store i32 %i, i32 *%p\n"
TEST(DeferredDominance, PairedUpdate) {
   // Make the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
   Function *F = M->getFunction(FuncName);
   ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << ".";
 
   // Make the DDT.
   DominatorTree DT(*F);
-  DeferredDominance DDT(DT);
-  ASSERT_TRUE(DDT.flush().verify());
+  PostDominatorTree PDT(*F);
+  DeferredDominance DDT(DT, &PDT);
+  ASSERT_TRUE(DDT.getDT().verify());
+  ASSERT_TRUE(DDT.getPDT()->verify());
 
   Function::iterator FI = F->begin();
   BasicBlock *BB0 = &*FI++;
   BasicBlock *BB1 = &*FI++;
   BasicBlock *BB2 = &*FI++;
 
   // CFG Change: only edge from bb0 is bb0 -> bb1.
   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 3u);
TEST(DeferredDominance, PairedUpdate) {
 
   // Test the empty DeletedBB list.
   EXPECT_FALSE(DDT.pendingDeletedBB(BB0));
   EXPECT_FALSE(DDT.pendingDeletedBB(BB1));
   EXPECT_FALSE(DDT.pendingDeletedBB(BB2));
 
   // The DT has no changes, this flush() simply returns a reference to the
   // internal DT calculated at the beginning of this test.
-  ASSERT_TRUE(DDT.flush().verify());
+  ASSERT_TRUE(DDT.getDT().verify());
+  ASSERT_TRUE(DDT.getPDT()->verify());
 }
 
 TEST(DeferredDominance, ReplaceEntryBB) {
   StringRef FuncName = "f";
   StringRef ModuleString =
       "define i32 @f() {\n"
       "bb0:\n"
       "   br label %bb1\n"
       " bb1:\n"
       "   ret i32 1\n"
       "}\n";
   // Make the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
   Function *F = M->getFunction(FuncName);
   ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << ".";
 
   // Make the DDT.
   DominatorTree DT(*F);
-  DeferredDominance DDT(DT);
-  ASSERT_TRUE(DDT.flush().verify());
+  PostDominatorTree PDT(*F);
+  DeferredDominance DDT(DT, &PDT);
+  ASSERT_TRUE(DDT.getDT().verify());
+  ASSERT_TRUE(DDT.getPDT()->verify());
 
   Function::iterator FI = F->begin();
   BasicBlock *BB0 = &*FI++;
   BasicBlock *BB1 = &*FI++;
 
   // Add a block as the new function entry BB. We also link it to BB0.
   BasicBlock *NewEntry =
       BasicBlock::Create(F->getContext(), "new_entry", F, BB0);
   BranchInst::Create(BB0, NewEntry);
   EXPECT_EQ(F->begin()->getName(), NewEntry->getName());
   EXPECT_TRUE(&F->getEntryBlock() == NewEntry);
 
   // Insert the new edge between new_eentry -> bb0. Without this the
   // recalculate() call below will not actually recalculate the DT as there
   // are no changes pending and no blocks deleted.
   DDT.insertEdge(NewEntry, BB0);
 
   // Changing the Entry BB requires a full recalulation.
   DDT.recalculate(*F);
-  ASSERT_TRUE(DDT.flush().verify());
+  ASSERT_TRUE(DDT.getDT().verify());
+  ASSERT_TRUE(DDT.getPDT()->verify());
 
   // CFG Change: remove new_edge -> bb0 and redirect to new_edge -> bb1.
   EXPECT_EQ(NewEntry->getTerminator()->getNumSuccessors(), 1u);
   NewEntry->getTerminator()->eraseFromParent();
   BranchInst::Create(BB1, NewEntry);
   EXPECT_EQ(BB0->getTerminator()->getNumSuccessors(), 1u);
 
   // Update the DDT. At this point bb0 now has no predecessors but is still a
   // Child of F.
   DDT.applyUpdates({{DominatorTree::Delete, NewEntry, BB0},
                     {DominatorTree::Insert, NewEntry, BB1}});
-  ASSERT_TRUE(DDT.flush().verify());
+  ASSERT_TRUE(DDT.getDT().verify());
+  ASSERT_TRUE(DDT.getPDT()->verify());
 
   // Now remove bb0 from F.
   ASSERT_FALSE(isa<UnreachableInst>(BB0->getTerminator()));
   EXPECT_FALSE(DDT.pendingDeletedBB(BB0));
   DDT.deleteBB(BB0);
   EXPECT_TRUE(DDT.pendingDeletedBB(BB0));
   ASSERT_TRUE(isa<UnreachableInst>(BB0->getTerminator()));
   EXPECT_EQ(BB0->getParent(), F);
 
   // Perform a full recalculation of the DDT. It is not necessary here but we
   // do this to test the case when there are no pending DT updates but there are
   // pending deleted BBs.
   DDT.recalculate(*F);
-  ASSERT_TRUE(DDT.flush().verify());
+  ASSERT_TRUE(DDT.getDT().verify());
+  ASSERT_TRUE(DDT.getPDT()->verify());
 }
 
 TEST(DeferredDominance, InheritedPreds) {
   StringRef FuncName = "f";
   StringRef ModuleString =
       "define i32 @f(i32 %i, i32 *%p) {\n"
       " bb0:\n"
       "   store i32 %i, i32 *%p\n"
TEST(DeferredDominance, InheritedPreds) {
   // Make the module.
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
   Function *F = M->getFunction(FuncName);
   ASSERT_NE(F, nullptr) << "Couldn't get function " << FuncName << ".";
 
   // Make the DDT.
   DominatorTree DT(*F);
-  DeferredDominance DDT(DT);
-  ASSERT_TRUE(DDT.flush().verify());
+  PostDominatorTree PDT(*F);
+  DeferredDominance DDT(DT, &PDT);
+  ASSERT_TRUE(DDT.getDT().verify());
+  ASSERT_TRUE(DDT.getPDT()->verify());
 
   Function::iterator FI = F->begin();
   BasicBlock *BB0 = &*FI++;
   BasicBlock *BB1 = &*FI++;
   BasicBlock *BB2 = &*FI++;
   BasicBlock *BB3 = &*FI++;
 
   // There are several CFG locations where we have:
TEST(DeferredDominance, InheritedPreds) {
   // Update the DDT. In this case we don't call DDT.insertEdge(BB0, BB3) because
   // the edge previously existed at the start of this test when DT was first
   // created.
   Updates.push_back({DominatorTree::Delete, BB0, BB1});
   Updates.push_back({DominatorTree::Delete, BB1, BB3});
 
   // Verify everything.
   DDT.applyUpdates(Updates);
-  ASSERT_TRUE(DDT.flush().verify());
+  ASSERT_TRUE(DDT.getDT().verify());
+  ASSERT_TRUE(DDT.getPDT()->verify());
 }

unittests/Transforms/Scalar/LoopPassManagerTest.cpp

 //===- llvm/unittest/Analysis/LoopPassManagerTest.cpp - LPM tests ---------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #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"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
LoopPassManagerTest()
                   "  ret void\n"
                   "}\n")),
         LAM(true), FAM(true), MAM(true) {
     // Register our mock analysis.
     LAM.registerPass([&] { return MLAHandle.getAnalysis(); });
 
     // 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.
     FAM.registerPass([&] { return AAManager(); });
     FAM.registerPass([&] { return AssumptionAnalysis(); });
     FAM.registerPass([&] { return ScalarEvolutionAnalysis(); });
     FAM.registerPass([&] { return TargetLibraryAnalysis(); });
     FAM.registerPass([&] { return TargetIRAnalysis(); });

unittests/Transforms/Utils/Local.cpp

TEST(Local, ConstantFoldTerminator) {
 
   auto CFAllTerminators = [&](Function &F, DominatorTree *DT) {
     DeferredDominance DDT(*DT);
     for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
       BasicBlock *BB = &*I++;
       ConstantFoldTerminator(BB, true, nullptr, &DDT);
     }
 
-    EXPECT_TRUE(DDT.flush().verify());
+    EXPECT_TRUE(DDT.getDT().verify());
   };
 
   runWithDomTree(*M, "br_same_dest", CFAllTerminators);
   runWithDomTree(*M, "br_different_dest", CFAllTerminators);
   runWithDomTree(*M, "switch_2_different_dest", CFAllTerminators);
   runWithDomTree(*M, "switch_2_different_dest_default", CFAllTerminators);
   runWithDomTree(*M, "switch_3_different_dest", CFAllTerminators);
   runWithDomTree(*M, "switch_variable_2_default_dest", CFAllTerminators);
   runWithDomTree(*M, "switch_constant_2_default_dest", CFAllTerminators);
   runWithDomTree(*M, "switch_constant_3_repeated_dest", CFAllTerminators);
   runWithDomTree(*M, "indirectbr", CFAllTerminators);
   runWithDomTree(*M, "indirectbr_repeated", CFAllTerminators);
   runWithDomTree(*M, "indirectbr_unreachable", CFAllTerminators);
 }