[CodeGenPrepare][NFC] Update the dominator tree instead of rebuilding it

[efriedma]

Have you tried to measure compile-time impact?

llvm/lib/CodeGen/CodeGenPrepare.cpp

7042

This might work, but it's going to be expensive; deleting the edge before adding the other edges will force the whole tree to be reconstructed, I think.

Can we use the SplitBlockAndInsertIfThen/SplitBlockAndInsertIfThenElse utilities here?

[nikic]

As a high level comment: If we always work on DTU, that would allow to only flush the DT updates when the DT is next accessed, rather than in each transform.

llvm/lib/CodeGen/CodeGenPrepare.cpp

618–619

Would it be hard to also preserve the DT though the handful of transforms above? If we did that, we could directly use the DT from the pass manager, and also preserve it afterwards as well.

[chill]

In D153638#4445127, @efriedma wrote:

Have you tried to measure compile-time impact?

Yeah, I measured with the whole stack as of today and the results aren't ... impressive. Basically, differences within error/noise margin, maybe with a tiny hint of regression.

[chill]

Update:

• now we use a DT from the optimisation pipeline, instead of building a new one in the pass
• made applying DT updates even lazier - they are accumulated in a lazy DomTreeUpdater and applied when/if the DT is requested by a transform (and also at the end of the pass, when the updated is destructed).
• some more transforms are made to update the DT
• one extra rebuild of the DT removed

On CTMark with LTO, measuring only the final link step, wall-clock time and instruction count, I get:

	Time	Inst
7zip	-0.32%	-0.18%
bullet	0.15%	-0.12%
clamav	-0.61%	-0.14%
consumer-typeset	-0.06%	-0.07%
kc	-0.41%	-0.31%
lencod	-0.29%	-0.05%
mafft	0.34%	-0.06%
spass	-0.08%	-0.11%
sqlite	0.06%	-0.11%
tramp3d	-0.14%	-0.14%

or -0.14%/-0.13% geomean, respectively.

llvm/lib/CodeGen/CodeGenPrepare.cpp

618–619

Done, mostly.
For eliminateMostlyEmptyBlocks and SplitIndirectBrCriticalEdges it's not entirely apparent how to update the DT/LI, so I just rebuild it
of those transforms made changes.

[chill]

Ping?

[dmgreen]

llvm/lib/CodeGen/CodeGenPrepare.cpp

435

I think DTU->getDomTree() will already do this.

8343

Formatting?

[dmgreen]

This seems to look OK, right? I know there are dragons here with some functions, but it looks like the compile time is better and it seems like a better design to keep the DomTree up to date, if we can do so without destroying compile time.

llvm/lib/CodeGen/CodeGenPrepare.cpp

607

This should be less indented?

690

ConstantFoldTerminator

896

As a general rule you should probably just run clang-format on any patch you upload :)

[nikic]

LGTM

llvm/lib/CodeGen/CodeGenPrepare.cpp

6180

This is a bit unfortunate, would be better if SplitEdge accepted DTU. But it looks like that would take a larger refactoring.

[rupprecht]

fyi, I bisected a crash during codegen prepare to this commit. I'm trying to reduce a repro now.

[rupprecht]

Reduced:

struct a {
  a(decltype(nullptr));
  long b;
} *c;
enum { d };
struct t {
  _Atomic(a) e;
};
struct f : t {};
struct atomic {
  f g;
  void h() {
    f *j = &g;
    t *k = j;
    __c11_atomic_load(&k->e, d);
  }
};
a l(a *addr) {
  reinterpret_cast<atomic *>(addr)->h();
  return 0;
}
struct {
  void m(long v) {
    long w = sizeof(this);
    c = reinterpret_cast<a *>(w);
    a *o = c;
    l(&o[v]);
  }
} p;
a q();
long r;
bool u();
a s() {
  if (u()) return q();
  for (long i = r; i; i++) p.m(i);
  return nullptr;
}

Compiled w/ bin/clang -c /tmp/repro.cc -O2 -std=c++17

1.      <eof> parser at end of file
2.      Code generation
3.      Running pass 'Function Pass Manager' on module '/tmp/repro.cc'.
4.      Running pass 'CodeGen Prepare' on function '@_Z1sv'
...
 #5 0x00005632704fe3b9 llvm::ilist_node_base<true>::isSentinel() const /home/rupprecht/src/llvm-project/llvm/include/llvm/ADT/ilist_node_base.h:45:36
 #6 0x00005632704fe3b9 llvm::ilist_node_base<true>::isKnownSentinel() const /home/rupprecht/src/llvm-project/llvm/include/llvm/ADT/ilist_node_base.h:46:41
 #7 0x00005632704fe3b9 llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::BasicBlock, true, false, void>, false, false>::operator*() const /home/rupprecht/src/llvm-project/llvm/include/llvm/ADT/ilist_iterator.h:138:5
 #8 0x00005632704fe3b9 llvm::early_inc_iterator_impl<llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::BasicBlock, true, false, void>, false, false>>::operator*() /home/rupprecht/src/llvm-project/llvm/include/llvm/ADT/STLExtras.h:631:12
 #9 0x00005632704fe3b9 (anonymous namespace)::CodeGenPrepare::runOnFunction(llvm::Function&) /home/rupprecht/src/llvm-project/llvm/lib/CodeGen/CodeGenPrepare.cpp:622:25
#10 0x0000563270a9d9ac llvm::FPPassManager::runOnFunction(llvm::Function&) /home/rupprecht/src/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:0:27
#11 0x0000563270aa3d61 llvm::FPPassManager::runOnModule(llvm::Module&) /home/rupprecht/src/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1481:13
#12 0x0000563270a9e008 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /home/rupprecht/src/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:0:27

[chill]

Thank you! I'll look at it.

[chill]

I couldn't so far reproduce it (basic config with assertions and expensive checks).
Maybe llvm::make_early_inc_range(F) fails because of non-finalised deletion of blocks ... I'll keep on digging.

[chill]

In D153638#4553265, @chill wrote:

I couldn't so far reproduce it (basic config with assertions and expensive checks).
Maybe llvm::make_early_inc_range(F) fails because of non-finalised deletion of blocks ... I'll keep on digging.

Quite likely.

I did a bootstrap on a slightly modified version where I forced the integrity checks on the DT tree,
unfortunately that had the side-effect of forcing DTU updates.

When I remove the checks I get the crash.

[chill]

Fixed the crash during compilation. Requesting the DT, while vising all the function blocks, can have the side effect of
deleting blocks, which can cause the traversal to access free/reused memory.

I think I fixed this by checking/making sure all the loops over the basic blocks fall into these cases:

• basic traversal (e.g for (auto &BB : F) ... ) while not requesting the DT in the body of the loop.
• traversal using an auxiliary vector of WeakTrackingVHs.
• the main loops of the pass:

DTU->flush();
for (BasicBlock &BB : llvm::make_early_inc_range(F)) {

which can only delete the current block (in dupRetToEnableTailCallOpts).
The extra flush of the DTU (added in this update) ensures the current block is valid at the start of the first iteration
and the early increment ensures the block is valid at the start of each subsequent iteration.

[chill]

Ping?

[chill]

rebase and ping?

llvm/include/llvm/Transforms/Utils/BypassSlowDivision.h

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/IR/ValueHandle.h"
 #include <cstdint>
 
 namespace llvm {
 
 class BasicBlock;
+class DomTreeUpdater;
+class LoopInfo;
 class Value;
 
 struct DivRemMapKey {
   bool SignedOp;
   AssertingVH<Value> Dividend;
   AssertingVH<Value> Divisor;
 
   DivRemMapKey() = default;
template <> struct DenseMapInfo<DivRemMapKey> {
   }
 };
 
 /// This optimization identifies DIV instructions in a BB that can be
 /// profitably bypassed and carried out with a shorter, faster divide.
 ///
 /// This optimization may add basic blocks immediately after BB; for obvious
 /// reasons, you shouldn't pass those blocks to bypassSlowDivision.
-bool bypassSlowDivision(
-    BasicBlock *BB, const DenseMap<unsigned int, unsigned int> &BypassWidth);
+bool bypassSlowDivision(BasicBlock *BB,
+                        const DenseMap<unsigned int, unsigned int> &BypassWidth,
+                        DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr);
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_BYPASSSLOWDIVISION_H

llvm/lib/CodeGen/CodeGenPrepare.cpp

 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/CodeGen/Analysis.h"
static cl::opt<bool>
     EnableGEPOffsetSplit("cgp-split-large-offset-gep", cl::Hidden,
                          cl::init(true),
                          cl::desc("Enable splitting large offset of GEP."));
 
 static cl::opt<bool> EnableICMP_EQToICMP_ST(
     "cgp-icmp-eq2icmp-st", cl::Hidden, cl::init(false),
     cl::desc("Enable ICMP_EQ to ICMP_S(L|G)T conversion."));
 
+#ifdef EXPENSIVE_CHECKS
+static bool VerifyDT = true;
+#else
+static bool VerifyDT = false;
+#endif
+static cl::opt<bool, true> VerifyDTUpdates(
+    "cgp-verify-dt-updates", cl::location(VerifyDT), cl::Hidden,
+    cl::desc("Verify dominator tree updates in CodeGenPrepare"));
+
 static cl::opt<bool>
     VerifyBFIUpdates("cgp-verify-bfi-updates", cl::Hidden, cl::init(false),
                      cl::desc("Enable BFI update verification for "
                               "CodeGenPrepare."));
 
 static cl::opt<bool>
     OptimizePhiTypes("cgp-optimize-phi-types", cl::Hidden, cl::init(true),
                      cl::desc("Enable converting phi types in CodeGenPrepare"));

 class CodeGenPrepare : public FunctionPass {
   const TargetMachine *TM = nullptr;
   const TargetSubtargetInfo *SubtargetInfo = nullptr;
   const TargetLowering *TLI = nullptr;
   const TargetRegisterInfo *TRI = nullptr;
   const TargetTransformInfo *TTI = nullptr;
   const BasicBlockSectionsProfileReader *BBSectionsProfileReader = nullptr;
   const TargetLibraryInfo *TLInfo = nullptr;
+  DominatorTree *DT = nullptr;
+  DomTreeUpdater *DTU = nullptr;
   LoopInfo *LI = nullptr;
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   ProfileSummaryInfo *PSI = nullptr;
 
   /// As we scan instructions optimizing them, this is the next instruction
   /// to optimize. Transforms that can invalidate this should update it.
   BasicBlock::iterator CurInstIterator;
class CodeGenPrepare : public FunctionPass {
   ValueToSExts ValToSExtendedUses;
 
   /// True if the function has the OptSize attribute.
   bool OptSize;
 
   /// DataLayout for the Function being processed.
   const DataLayout *DL = nullptr;
 
-  /// Building the dominator tree can be expensive, so we only build it
-  /// lazily and update it when required.
-  std::unique_ptr<DominatorTree> DT;
-
 public:
   /// If encounter huge function, we need to limit the build time.
   bool IsHugeFunc = false;
 
   /// FreshBBs is like worklist, it collected the updated BBs which need
   /// to be optimized again.
   /// Note: Consider building time in this pass, when a BB updated, we need
   /// to insert such BB into FreshBBs for huge function.
public:
   StringRef getPassName() const override { return "CodeGen Prepare"; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     // FIXME: When we can selectively preserve passes, preserve the domtree.
     AU.addRequired<ProfileSummaryInfoWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     AU.addRequired<TargetPassConfig>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
+    AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
     AU.addUsedIfAvailable<BasicBlockSectionsProfileReader>();
   }
 
 private:
   template <typename F>
   void resetIteratorIfInvalidatedWhileCalling(BasicBlock *BB, F f) {
     // Substituting can cause recursive simplifications, which can invalidate
     // our iterator.  Use a WeakTrackingVH to hold onto it in case this
     // happens.
     Value *CurValue = &*CurInstIterator;
     WeakTrackingVH IterHandle(CurValue);
 
     f();
 
     // If the iterator instruction was recursively deleted, start over at the
     // start of the block.
     if (IterHandle != CurValue) {
       CurInstIterator = BB->begin();
       SunkAddrs.clear();
     }
   }
 
-  // Get the DominatorTree, building if necessary.
-  DominatorTree &getDT(Function &F) {
-    if (!DT)
-      DT = std::make_unique<DominatorTree>(F);
-    return *DT;
-  }
+  // Get the DominatorTree, updating it if necessary.
+  DominatorTree &getDT() { return DTU->getDomTree(); }
 
   void removeAllAssertingVHReferences(Value *V);
   bool eliminateAssumptions(Function &F);
-  bool eliminateFallThrough(Function &F, DominatorTree *DT = nullptr);
-  bool eliminateMostlyEmptyBlocks(Function &F);
+  bool eliminateFallThrough(Function &F);
+  bool eliminateMostlyEmptyBlocks(Function &F, bool &ResetDT);
   BasicBlock *findDestBlockOfMergeableEmptyBlock(BasicBlock *BB);
   bool canMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const;
-  void eliminateMostlyEmptyBlock(BasicBlock *BB);
+  bool eliminateMostlyEmptyBlock(BasicBlock *BB);
   bool isMergingEmptyBlockProfitable(BasicBlock *BB, BasicBlock *DestBB,
                                      bool isPreheader);
   bool makeBitReverse(Instruction &I);
   bool optimizeBlock(BasicBlock &BB, ModifyDT &ModifiedDT);
   bool optimizeInst(Instruction *I, ModifyDT &ModifiedDT);
   bool optimizeMemoryInst(Instruction *MemoryInst, Value *Addr, Type *AccessTy,
                           unsigned AddrSpace);
   bool optimizeGatherScatterInst(Instruction *MemoryInst, Value *Ptr);
private:
   bool splitLargeGEPOffsets();
   bool optimizePhiType(PHINode *Inst, SmallPtrSetImpl<PHINode *> &Visited,
                        SmallPtrSetImpl<Instruction *> &DeletedInstrs);
   bool optimizePhiTypes(Function &F);
   bool performAddressTypePromotion(
       Instruction *&Inst, bool AllowPromotionWithoutCommonHeader,
       bool HasPromoted, TypePromotionTransaction &TPT,
       SmallVectorImpl<Instruction *> &SpeculativelyMovedExts);
-  bool splitBranchCondition(Function &F, ModifyDT &ModifiedDT);
+  bool splitBranchCondition(Function &F);
   bool simplifyOffsetableRelocate(GCStatepointInst &I);
 
   bool tryToSinkFreeOperands(Instruction *I);
   bool replaceMathCmpWithIntrinsic(BinaryOperator *BO, Value *Arg0, Value *Arg1,
                                    CmpInst *Cmp, Intrinsic::ID IID);
   bool optimizeCmp(CmpInst *Cmp, ModifyDT &ModifiedDT);
   bool combineToUSubWithOverflow(CmpInst *Cmp, ModifyDT &ModifiedDT);
   bool combineToUAddWithOverflow(CmpInst *Cmp, ModifyDT &ModifiedDT);
   void verifyBFIUpdates(Function &F);
 };
 
 } // end anonymous namespace
 
 char CodeGenPrepare::ID = 0;
 
 INITIALIZE_PASS_BEGIN(CodeGenPrepare, DEBUG_TYPE,
                       "Optimize for code generation", false, false)
 INITIALIZE_PASS_DEPENDENCY(BasicBlockSectionsProfileReader)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_END(CodeGenPrepare, DEBUG_TYPE, "Optimize for code generation",
                     false, false)
 
 FunctionPass *llvm::createCodeGenPreparePass() { return new CodeGenPrepare(); }
 
 bool CodeGenPrepare::runOnFunction(Function &F) {
   if (skipFunction(F))
     return false;
 
   DL = &F.getParent()->getDataLayout();
 
   bool EverMadeChange = false;
 
   TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
   SubtargetInfo = TM->getSubtargetImpl(F);
   TLI = SubtargetInfo->getTargetLowering();
   TRI = SubtargetInfo->getRegisterInfo();
   TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
+  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   BPI.reset(new BranchProbabilityInfo(F, *LI));
   BFI.reset(new BlockFrequencyInfo(F, *BPI, *LI));
   PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
   BBSectionsProfileReader =
       getAnalysisIfAvailable<BasicBlockSectionsProfileReader>();
   OptSize = F.hasOptSize();
   // Use the basic-block-sections profile to promote hot functions to .text.hot
if (BBSectionsGuidedSectionPrefix && BBSectionsProfileReader &&
     else if (PSI->isFunctionColdInCallGraph(&F, *BFI) ||
              F.hasFnAttribute(Attribute::Cold))
       F.setSectionPrefix("unlikely");
     else if (ProfileUnknownInSpecialSection && PSI->hasPartialSampleProfile() &&
              PSI->isFunctionHotnessUnknown(F))
       F.setSectionPrefix("unknown");
   }
 
+  DomTreeUpdater DTUpdater(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+  DTU = &DTUpdater;
+  auto resetDTAndLI = [&]() {
+    DTU->recalculate(F);
+    LI->releaseMemory();
+    LI->analyze(*DT);
+  };
+
   /// This optimization identifies DIV instructions that can be
   /// profitably bypassed and carried out with a shorter, faster divide.
   if (!OptSize && !PSI->hasHugeWorkingSetSize() && TLI->isSlowDivBypassed()) {
     const DenseMap<unsigned int, unsigned int> &BypassWidths =
         TLI->getBypassSlowDivWidths();
     BasicBlock *BB = &*F.begin();
     while (BB != nullptr) {
       // bypassSlowDivision may create new BBs, but we don't want to reapply the
       // optimization to those blocks.
       BasicBlock *Next = BB->getNextNode();
       // F.hasOptSize is already checked in the outer if statement.
       if (!llvm::shouldOptimizeForSize(BB, PSI, BFI.get()))
-        EverMadeChange |= bypassSlowDivision(BB, BypassWidths);
+        EverMadeChange |= bypassSlowDivision(BB, BypassWidths, DTU, LI);
       BB = Next;
     }
   }
 
   // Get rid of @llvm.assume builtins before attempting to eliminate empty
   // blocks, since there might be blocks that only contain @llvm.assume calls
   // (plus arguments that we can get rid of).
   EverMadeChange |= eliminateAssumptions(F);
 
   // Eliminate blocks that contain only PHI nodes and an
   // unconditional branch.
-  EverMadeChange |= eliminateMostlyEmptyBlocks(F);
+  bool ResetDT = false;
+  EverMadeChange |= eliminateMostlyEmptyBlocks(F, ResetDT);
+  if (ResetDT)
+    resetDTAndLI();
 
-  ModifyDT ModifiedDT = ModifyDT::NotModifyDT;
   if (!DisableBranchOpts)
-    EverMadeChange |= splitBranchCondition(F, ModifiedDT);
+    EverMadeChange |= splitBranchCondition(F);
 
   // Split some critical edges where one of the sources is an indirect branch,
   // to help generate sane code for PHIs involving such edges.
-  EverMadeChange |=
-      SplitIndirectBrCriticalEdges(F, /*IgnoreBlocksWithoutPHI=*/true);
+  if (SplitIndirectBrCriticalEdges(F, /*IgnoreBlocksWithoutPHI=*/true)) {
+    EverMadeChange = true;
+    resetDTAndLI();
+  }
+
+#ifndef NDEBUG
+  if (VerifyDT)
+    assert(getDT().verify(DominatorTree::VerificationLevel::Fast) &&
+           "Incorrect DominatorTree updates in CGP");
+
+  if (VerifyLoopInfo)
+    LI->verify(getDT());
+#endif
 
   // If we are optimzing huge function, we need to consider the build time.
   // Because the basic algorithm's complex is near O(N!).
   IsHugeFunc = F.size() > HugeFuncThresholdInCGPP;
 
-  // Transformations above may invalidate dominator tree and/or loop info.
-  DT.reset();
-  LI->releaseMemory();
-  LI->analyze(getDT(F));
-
   bool MadeChange = true;
   bool FuncIterated = false;
   while (MadeChange) {
     MadeChange = false;
 
+    DTU->flush();
     for (BasicBlock &BB : llvm::make_early_inc_range(F)) {
       if (FuncIterated && !FreshBBs.contains(&BB))
         continue;
 
       ModifyDT ModifiedDTOnIteration = ModifyDT::NotModifyDT;
       bool Changed = optimizeBlock(BB, ModifiedDTOnIteration);
 
-      if (ModifiedDTOnIteration == ModifyDT::ModifyBBDT)
-        DT.reset();
-
       MadeChange |= Changed;
       if (IsHugeFunc) {
         // If the BB is updated, it may still has chance to be optimized.
         // This usually happen at sink optimization.
         // For example:
         //
         // bb0：
         // %and = and i32 %a, 4
while (MadeChange) {
 
     if (EnableTypePromotionMerge && !ValToSExtendedUses.empty())
       MadeChange |= mergeSExts(F);
     if (!LargeOffsetGEPMap.empty())
       MadeChange |= splitLargeGEPOffsets();
     MadeChange |= optimizePhiTypes(F);
 
     if (MadeChange)
-      eliminateFallThrough(F, DT.get());
+      eliminateFallThrough(F);
 
 #ifndef NDEBUG
-    if (MadeChange && VerifyLoopInfo)
-      LI->verify(getDT(F));
+    if (VerifyDT)
+      assert(getDT().verify(DominatorTree::VerificationLevel::Fast) &&
+             "Incorrect DominatorTree updates in CGP");
+
+    if (VerifyLoopInfo)
+      LI->verify(getDT());
 #endif
 
     // Really free removed instructions during promotion.
     for (Instruction *I : RemovedInsts)
       I->deleteValue();
 
     EverMadeChange |= MadeChange;
     SeenChainsForSExt.clear();
     ValToSExtendedUses.clear();
     RemovedInsts.clear();
     LargeOffsetGEPMap.clear();
     LargeOffsetGEPID.clear();
   }
 
   NewGEPBases.clear();
   SunkAddrs.clear();
 
+  // LoopInfo is not needed anymore and ConstantFoldTerminator can break it.
+  LI = nullptr;
+
   if (!DisableBranchOpts) {
     MadeChange = false;
     // Use a set vector to get deterministic iteration order. The order the
     // blocks are removed may affect whether or not PHI nodes in successors
     // are removed.
     SmallSetVector<BasicBlock *, 8> WorkList;
     for (BasicBlock &BB : F) {
       SmallVector<BasicBlock *, 2> Successors(successors(&BB));
-      MadeChange |= ConstantFoldTerminator(&BB, true);
+      MadeChange |= ConstantFoldTerminator(&BB, true, nullptr, DTU);
       if (!MadeChange)
         continue;
 
       for (BasicBlock *Succ : Successors)
         if (pred_empty(Succ))
           WorkList.insert(Succ);
     }
 
     // Delete the dead blocks and any of their dead successors.
     MadeChange |= !WorkList.empty();
     while (!WorkList.empty()) {
       BasicBlock *BB = WorkList.pop_back_val();
       SmallVector<BasicBlock *, 2> Successors(successors(BB));
 
-      DeleteDeadBlock(BB);
+      DeleteDeadBlock(BB, DTU);
 
       for (BasicBlock *Succ : Successors)
         if (pred_empty(Succ))
           WorkList.insert(Succ);
     }
 
+    // Flush pending DT updates in order to finalise deletion of dead blocks.
+    DTU->flush();
+
     // Merge pairs of basic blocks with unconditional branches, connected by
     // a single edge.
     if (EverMadeChange || MadeChange)
       MadeChange |= eliminateFallThrough(F);
 
     EverMadeChange |= MadeChange;
   }
 
void LLVM_ATTRIBUTE_UNUSED CodeGenPrepare::verifyBFIUpdates(Function &F) {
   BranchProbabilityInfo NewBPI(F, NewLI, TLInfo);
   BlockFrequencyInfo NewBFI(F, NewBPI, NewLI);
   NewBFI.verifyMatch(*BFI);
 }
 
 /// Merge basic blocks which are connected by a single edge, where one of the
 /// basic blocks has a single successor pointing to the other basic block,
 /// which has a single predecessor.
-bool CodeGenPrepare::eliminateFallThrough(Function &F, DominatorTree *DT) {
+bool CodeGenPrepare::eliminateFallThrough(Function &F) {
   bool Changed = false;
   // Scan all of the blocks in the function, except for the entry block.
   // Use a temporary array to avoid iterator being invalidated when
   // deleting blocks.
   SmallVector<WeakTrackingVH, 16> Blocks;
   for (auto &Block : llvm::drop_begin(F))
     Blocks.push_back(&Block);
 
   SmallSet<WeakTrackingVH, 16> Preds;
   for (auto &Block : Blocks) {
     auto *BB = cast_or_null<BasicBlock>(Block);
     if (!BB)
       continue;
     // If the destination block has a single pred, then this is a trivial
     // edge, just collapse it.
     BasicBlock *SinglePred = BB->getSinglePredecessor();
 
     // Don't merge if BB's address is taken.
     if (!SinglePred || SinglePred == BB || BB->hasAddressTaken())
       continue;
 
-    // Make an effort to skip unreachable blocks.
-    if (DT && !DT->isReachableFromEntry(BB))
-      continue;
-
     BranchInst *Term = dyn_cast<BranchInst>(SinglePred->getTerminator());
     if (Term && !Term->isConditional()) {
       Changed = true;
       LLVM_DEBUG(dbgs() << "To merge:\n" << *BB << "\n\n\n");
 
       // Merge BB into SinglePred and delete it.
-      MergeBlockIntoPredecessor(BB, /* DTU */ nullptr, LI, /* MSSAU */ nullptr,
-                                /* MemDep */ nullptr,
-                                /* PredecessorWithTwoSuccessors */ false, DT);
+      MergeBlockIntoPredecessor(BB, DTU, LI);
       Preds.insert(SinglePred);
 
       if (IsHugeFunc) {
         // Update FreshBBs to optimize the merged BB.
         FreshBBs.insert(SinglePred);
         FreshBBs.erase(BB);
       }
     }
BasicBlock *CodeGenPrepare::findDestBlockOfMergeableEmptyBlock(BasicBlock *BB) {
 
   return DestBB;
 }
 
 /// Eliminate blocks that contain only PHI nodes, debug info directives, and an
 /// unconditional branch. Passes before isel (e.g. LSR/loopsimplify) often split
 /// edges in ways that are non-optimal for isel. Start by eliminating these
 /// blocks so we can split them the way we want them.
-bool CodeGenPrepare::eliminateMostlyEmptyBlocks(Function &F) {
+bool CodeGenPrepare::eliminateMostlyEmptyBlocks(Function &F, bool &ResetDT) {
   SmallPtrSet<BasicBlock *, 16> Preheaders;
   SmallVector<Loop *, 16> LoopList(LI->begin(), LI->end());
   while (!LoopList.empty()) {
     Loop *L = LoopList.pop_back_val();
     llvm::append_range(LoopList, *L);
     if (BasicBlock *Preheader = L->getLoopPreheader())
       Preheaders.insert(Preheader);
   }
 
+  ResetDT = false;
   bool MadeChange = false;
   // Copy blocks into a temporary array to avoid iterator invalidation issues
   // as we remove them.
   // Note that this intentionally skips the entry block.
   SmallVector<WeakTrackingVH, 16> Blocks;
   for (auto &Block : llvm::drop_begin(F)) {
     // Delete phi nodes that could block deleting other empty blocks.
     if (!DisableDeletePHIs)
       MadeChange |= DeleteDeadPHIs(&Block, TLInfo);
     Blocks.push_back(&Block);
   }
 
   for (auto &Block : Blocks) {
     BasicBlock *BB = cast_or_null<BasicBlock>(Block);
     if (!BB)
       continue;
     BasicBlock *DestBB = findDestBlockOfMergeableEmptyBlock(BB);
     if (!DestBB ||
         !isMergingEmptyBlockProfitable(BB, DestBB, Preheaders.count(BB)))
       continue;
 
-    eliminateMostlyEmptyBlock(BB);
+    ResetDT |= eliminateMostlyEmptyBlock(BB);
     MadeChange = true;
   }
   return MadeChange;
 }
 
 bool CodeGenPrepare::isMergingEmptyBlockProfitable(BasicBlock *BB,
                                                    BasicBlock *DestBB,
                                                    bool isPreheader) {
for (Value::user_iterator UI = OldI->user_begin(), E = OldI->user_end();
         FreshBBs.insert(User->getParent());
     }
   }
   Old->replaceAllUsesWith(New);
 }
 
 /// Eliminate a basic block that has only phi's and an unconditional branch in
 /// it.
-void CodeGenPrepare::eliminateMostlyEmptyBlock(BasicBlock *BB) {
+/// Indicate that the DT was modified only if the DT wasn't updated.
+bool CodeGenPrepare::eliminateMostlyEmptyBlock(BasicBlock *BB) {
   BranchInst *BI = cast<BranchInst>(BB->getTerminator());
   BasicBlock *DestBB = BI->getSuccessor(0);
 
   LLVM_DEBUG(dbgs() << "MERGING MOSTLY EMPTY BLOCKS - BEFORE:\n"
                     << *BB << *DestBB);
 
   // If the destination block has a single pred, then this is a trivial edge,
   // just collapse it.
   if (BasicBlock *SinglePred = DestBB->getSinglePredecessor()) {
     if (SinglePred != DestBB) {
       assert(SinglePred == BB &&
              "Single predecessor not the same as predecessor");
       // Merge DestBB into SinglePred/BB and delete it.
-      MergeBlockIntoPredecessor(DestBB);
+      MergeBlockIntoPredecessor(DestBB, DTU, LI);
       // Note: BB(=SinglePred) will not be deleted on this path.
       // DestBB(=its single successor) is the one that was deleted.
       LLVM_DEBUG(dbgs() << "AFTER:\n" << *SinglePred << "\n\n\n");
 
       if (IsHugeFunc) {
         // Update FreshBBs to optimize the merged BB.
         FreshBBs.insert(SinglePred);
         FreshBBs.erase(DestBB);
       }
-      return;
+      return false;
     }
   }
 
   // Otherwise, we have multiple predecessors of BB.  Update the PHIs in DestBB
   // to handle the new incoming edges it is about to have.
   for (PHINode &PN : DestBB->phis()) {
     // Remove the incoming value for BB, and remember it.
     Value *InVal = PN.removeIncomingValue(BB, false);
bool CodeGenPrepare::eliminateMostlyEmptyBlock(BasicBlock *BB) {
 
   // The PHIs are now updated, change everything that refers to BB to use
   // DestBB and remove BB.
   BB->replaceAllUsesWith(DestBB);
   BB->eraseFromParent();
   ++NumBlocksElim;
 
   LLVM_DEBUG(dbgs() << "AFTER:\n" << *DestBB << "\n\n\n");
+  return true;
 }
 
 // Computes a map of base pointer relocation instructions to corresponding
 // derived pointer relocation instructions given a vector of all relocate calls
 static void computeBaseDerivedRelocateMap(
     const SmallVectorImpl<GCRelocateInst *> &AllRelocateCalls,
     DenseMap<GCRelocateInst *, SmallVector<GCRelocateInst *, 2>>
         &RelocateInstMap) {
auto IsReplacableIVIncrement = [this, &Cmp](BinaryOperator *BO) {
     assert(L && "L should not be null after isIVIncrement()");
     // Do not risk on moving increment into a child loop.
     if (LI->getLoopFor(Cmp->getParent()) != L)
       return false;
 
     // Finally, we need to ensure that the insert point will dominate all
     // existing uses of the increment.
 
-    auto &DT = getDT(*BO->getParent()->getParent());
+    auto &DT = getDT();
     if (DT.dominates(Cmp->getParent(), BO->getParent()))
       // If we're moving up the dom tree, all uses are trivially dominated.
       // (This is the common case for code produced by LSR.)
       return true;
 
     // Otherwise, special case the single use in the phi recurrence.
     return BO->hasOneUse() && DT.dominates(Cmp->getParent(), L->getLoopLatch());
   };

 ///   cond.false:
 ///     %z = call i64 @llvm.cttz.i64(i64 %A, i1 true)
 ///     br label %cond.end
 ///   cond.end:
 ///     %ctz = phi i64 [ 64, %entry ], [ %z, %cond.false ]
 ///
 /// If the transform is performed, return true and set ModifiedDT to true.
 static bool despeculateCountZeros(IntrinsicInst *CountZeros,
-                                  LoopInfo &LI,
+                                  DomTreeUpdater &DTU, LoopInfo &LI,
                                   const TargetLowering *TLI,
                                   const DataLayout *DL, ModifyDT &ModifiedDT,
                                   SmallSet<BasicBlock *, 32> &FreshBBs,
                                   bool IsHugeFunc) {
   // If a zero input is undefined, it doesn't make sense to despeculate that.
   if (match(CountZeros->getOperand(1), m_One()))
     return false;
 
static bool despeculateCountZeros(IntrinsicInst *CountZeros,
 
   // Bail if the value is never zero.
   Use &Op = CountZeros->getOperandUse(0);
   if (isKnownNonZero(Op, *DL))
     return false;
 
   // The intrinsic will be sunk behind a compare against zero and branch.
   BasicBlock *StartBlock = CountZeros->getParent();
-  BasicBlock *CallBlock = StartBlock->splitBasicBlock(CountZeros, "cond.false");
+  BasicBlock *CallBlock = SplitBlock(StartBlock, CountZeros, &DTU, &LI,
+                                     /* MSSAU */ nullptr, "cond.false");
   if (IsHugeFunc)
     FreshBBs.insert(CallBlock);
 
   // Create another block after the count zero intrinsic. A PHI will be added
   // in this block to select the result of the intrinsic or the bit-width
   // constant if the input to the intrinsic is zero.
   BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(CountZeros));
-  BasicBlock *EndBlock = CallBlock->splitBasicBlock(SplitPt, "cond.end");
+  BasicBlock *EndBlock = SplitBlock(CallBlock, &*SplitPt, &DTU, &LI,
+                                    /* MSSAU */ nullptr, "cond.end");
   if (IsHugeFunc)
     FreshBBs.insert(EndBlock);
 
-  // Update the LoopInfo. The new blocks are in the same loop as the start
-  // block.
-  if (Loop *L = LI.getLoopFor(StartBlock)) {
-    L->addBasicBlockToLoop(CallBlock, LI);
-    L->addBasicBlockToLoop(EndBlock, LI);
-  }
-
   // Set up a builder to create a compare, conditional branch, and PHI.
   IRBuilder<> Builder(CountZeros->getContext());
   Builder.SetInsertPoint(StartBlock->getTerminator());
   Builder.SetCurrentDebugLocation(CountZeros->getDebugLoc());
 
   // Replace the unconditional branch that was created by the first split with
   // a compare against zero and a conditional branch.
   Value *Zero = Constant::getNullValue(Ty);
   // Avoid introducing branch on poison. This also replaces the ctz operand.
   if (!isGuaranteedNotToBeUndefOrPoison(Op))
     Op = Builder.CreateFreeze(Op, Op->getName() + ".fr");
   Value *Cmp = Builder.CreateICmpEQ(Op, Zero, "cmpz");
   Builder.CreateCondBr(Cmp, EndBlock, CallBlock);
   StartBlock->getTerminator()->eraseFromParent();
+  DTU.applyUpdates({{DominatorTree::Insert, StartBlock, EndBlock}});
 
   // Create a PHI in the end block to select either the output of the intrinsic
   // or the bit width of the operand.
   Builder.SetInsertPoint(&EndBlock->front());
   PHINode *PN = Builder.CreatePHI(Ty, 2, "ctz");
   replaceAllUsesWith(CountZeros, PN, FreshBBs, IsHugeFunc);
   Value *BitWidth = Builder.getInt(APInt(SizeInBits, SizeInBits));
   PN->addIncoming(BitWidth, StartBlock);
case Intrinsic::strip_invariant_group: {
 
       replaceAllUsesWith(II, ArgVal, FreshBBs, IsHugeFunc);
       II->eraseFromParent();
       return true;
     }
     case Intrinsic::cttz:
     case Intrinsic::ctlz:
       // If counting zeros is expensive, try to avoid it.
-      return despeculateCountZeros(II, *LI, TLI, DL, ModifiedDT, FreshBBs,
+      return despeculateCountZeros(II, *DTU, *LI, TLI, DL, ModifiedDT, FreshBBs,
                                    IsHugeFunc);
     case Intrinsic::fshl:
     case Intrinsic::fshr:
       return optimizeFunnelShift(II);
     case Intrinsic::dbg_assign:
     case Intrinsic::dbg_value:
       return fixupDbgValue(II);
     case Intrinsic::masked_gather:
bool CodeGenPrepare::dupRetToEnableTailCallOpts(BasicBlock *BB,
   for (auto const &TailCallBB : TailCallBBs) {
     // Make sure the call instruction is followed by an unconditional branch to
     // the return block.
     BranchInst *BI = dyn_cast<BranchInst>(TailCallBB->getTerminator());
     if (!BI || !BI->isUnconditional() || BI->getSuccessor(0) != BB)
       continue;
 
     // Duplicate the return into TailCallBB.
-    (void)FoldReturnIntoUncondBranch(RetI, BB, TailCallBB);
+    (void)FoldReturnIntoUncondBranch(RetI, BB, TailCallBB, DTU);
     assert(!VerifyBFIUpdates ||
            BFI->getBlockFreq(BB) >= BFI->getBlockFreq(TailCallBB));
     BFI->setBlockFreq(
         BB,
         (BFI->getBlockFreq(BB) - BFI->getBlockFreq(TailCallBB)).getFrequency());
     ModifiedDT = ModifyDT::ModifyBBDT;
     Changed = true;
     ++NumRetsDup;
   }
 
   // If we eliminated all predecessors of the block, delete the block now.
   if (Changed && !BB->hasAddressTaken() && pred_empty(BB))
-    BB->eraseFromParent();
+    DTU->deleteBB(BB);
 
   return Changed;
 }
 
 //===----------------------------------------------------------------------===//
 // Memory Optimization
 //===----------------------------------------------------------------------===//
 
while (!worklist.empty()) {
     // the result may differ depending on what other uses our candidate
     // addressing instructions might have.
     AddrModeInsts.clear();
     std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(nullptr,
                                                                       0);
     // Defer the query (and possible computation of) the dom tree to point of
     // actual use.  It's expected that most address matches don't actually need
     // the domtree.
-    auto getDTFn = [MemoryInst, this]() -> const DominatorTree & {
-      Function *F = MemoryInst->getParent()->getParent();
-      return this->getDT(*F);
-    };
+    auto getDTFn = [this]() -> const DominatorTree & { return getDT(); };
     ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
         V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *LI, getDTFn,
         *TRI, InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP, OptSize, PSI,
         BFI.get());
 
     GetElementPtrInst *GEP = LargeOffsetGEP.first;
     if (GEP && !NewGEPBases.count(GEP)) {
       // If splitting the underlying data structure can reduce the offset of a
for (auto &Entry : ValToSExtendedUses) {
     SExts &Insts = Entry.second;
     SExts CurPts;
     for (Instruction *Inst : Insts) {
       if (RemovedInsts.count(Inst) || !isa<SExtInst>(Inst) ||
           Inst->getOperand(0) != Entry.first)
         continue;
       bool inserted = false;
       for (auto &Pt : CurPts) {
-        if (getDT(F).dominates(Inst, Pt)) {
+        if (getDT().dominates(Inst, Pt)) {
           replaceAllUsesWith(Pt, Inst, FreshBBs, IsHugeFunc);
           RemovedInsts.insert(Pt);
           Pt->removeFromParent();
           Pt = Inst;
           inserted = true;
           Changed = true;
           break;
         }
-        if (!getDT(F).dominates(Pt, Inst))
+        if (!getDT().dominates(Pt, Inst))
           // Give up if we need to merge in a common dominator as the
           // experiments show it is not profitable.
           continue;
         replaceAllUsesWith(Inst, Pt, FreshBBs, IsHugeFunc);
         RemovedInsts.insert(Inst);
         Inst->removeFromParent();
         inserted = true;
         Changed = true;
while (LargeOffsetGEP != LargeOffsetGEPs.end()) {
         BasicBlock *NewBaseInsertBB;
         if (auto *BaseI = dyn_cast<Instruction>(OldBase)) {
           // If the base of the struct is an instruction, the new base will be
           // inserted close to it.
           NewBaseInsertBB = BaseI->getParent();
           if (isa<PHINode>(BaseI))
             NewBaseInsertPt = NewBaseInsertBB->getFirstInsertionPt();
           else if (InvokeInst *Invoke = dyn_cast<InvokeInst>(BaseI)) {
-            NewBaseInsertBB =
-                SplitEdge(NewBaseInsertBB, Invoke->getNormalDest(), DT.get(), LI);
+            NewBaseInsertBB = SplitEdge(NewBaseInsertBB,
+                                        Invoke->getNormalDest(), &getDT(), LI);
             NewBaseInsertPt = NewBaseInsertBB->getFirstInsertionPt();
           } else
             NewBaseInsertPt = std::next(BaseI->getIterator());
         } else {
           // If the current base is an argument or global value, the new base
           // will be inserted to the entry block.
           NewBaseInsertBB = &BaseGEP->getFunction()->getEntryBlock();
           NewBaseInsertPt = NewBaseInsertBB->getFirstInsertionPt();
bool CodeGenPrepare::optimizeSelectInst(SelectInst *SI) {
   else
     SelectKind = TargetLowering::ScalarValSelect;
 
   if (TLI->isSelectSupported(SelectKind) &&
       (!isFormingBranchFromSelectProfitable(TTI, TLI, SI) || OptSize ||
        llvm::shouldOptimizeForSize(SI->getParent(), PSI, BFI.get())))
     return false;
 
-  // The DominatorTree needs to be rebuilt by any consumers after this
-  // transformation. We simply reset here rather than setting the ModifiedDT
-  // flag to avoid restarting the function walk in runOnFunction for each
-  // select optimized.
-  DT.reset();
-
   // Transform a sequence like this:
   //    start:
   //       %cmp = cmp uge i32 %a, %b
   //       %sel = select i1 %cmp, i32 %c, i32 %d
   //
   // Into:
   //    start:
   //       %cmp = cmp uge i32 %a, %b
   //       %cmp.frozen = freeze %cmp
   //       br i1 %cmp.frozen, label %select.true, label %select.false
   //    select.true:
   //       br label %select.end
   //    select.false:
   //       br label %select.end
   //    select.end:
   //       %sel = phi i32 [ %c, %select.true ], [ %d, %select.false ]
   //
   // %cmp should be frozen, otherwise it may introduce undefined behavior.
   // In addition, we may sink instructions that produce %c or %d from
   // the entry block into the destination(s) of the new branch.
   // If the true or false blocks do not contain a sunken instruction, that
   // block and its branch may be optimized away. In that case, one side of the
   // first branch will point directly to select.end, and the corresponding PHI
   // predecessor block will be the start block.
+  // The CFG is altered here and we update the DominatorTree and the LoopInfo,
+  // but we don't set a ModifiedDT flag to avoid restarting the function walk in
+  // runOnFunction for each select optimized.
 
   // Collect values that go on the true side and the values that go on the false
   // side.
   SmallVector<Instruction *> TrueInstrs, FalseInstrs;
   for (SelectInst *SI : ASI) {
     if (Value *V = SI->getTrueValue(); sinkSelectOperand(TTI, V))
       TrueInstrs.push_back(cast<Instruction>(V));
     if (Value *V = SI->getFalseValue(); sinkSelectOperand(TTI, V))
       FalseInstrs.push_back(cast<Instruction>(V));
   }
 
   // Split the select block, according to how many (if any) values go on each
   // side.
   BasicBlock *StartBlock = SI->getParent();
   BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(LastSI));
 
   IRBuilder<> IB(SI);
   auto *CondFr = IB.CreateFreeze(SI->getCondition(), SI->getName() + ".frozen");
 
   BasicBlock *TrueBlock = nullptr;
   BasicBlock *FalseBlock = nullptr;
   BasicBlock *EndBlock = nullptr;
   BranchInst *TrueBranch = nullptr;
   BranchInst *FalseBranch = nullptr;
   if (TrueInstrs.size() == 0) {
-    FalseBranch = cast<BranchInst>(SplitBlockAndInsertIfElse(
-        CondFr, &*SplitPt, false, nullptr, nullptr, LI));
+    FalseBranch = cast<BranchInst>(
+        SplitBlockAndInsertIfElse(CondFr, &*SplitPt, false, nullptr, DTU, LI));
     FalseBlock = FalseBranch->getParent();
     EndBlock = cast<BasicBlock>(FalseBranch->getOperand(0));
   } else if (FalseInstrs.size() == 0) {
-    TrueBranch = cast<BranchInst>(SplitBlockAndInsertIfThen(
-        CondFr, &*SplitPt, false, nullptr, nullptr, LI));
+    TrueBranch = cast<BranchInst>(
+        SplitBlockAndInsertIfThen(CondFr, &*SplitPt, false, nullptr, DTU, LI));
     TrueBlock = TrueBranch->getParent();
     EndBlock = cast<BasicBlock>(TrueBranch->getOperand(0));
   } else {
     Instruction *ThenTerm = nullptr;
     Instruction *ElseTerm = nullptr;
     SplitBlockAndInsertIfThenElse(CondFr, &*SplitPt, &ThenTerm, &ElseTerm,
-                                  nullptr, nullptr, LI);
+                                  nullptr, DTU, LI);
     TrueBranch = cast<BranchInst>(ThenTerm);
     FalseBranch = cast<BranchInst>(ElseTerm);
     TrueBlock = TrueBranch->getParent();
     FalseBlock = FalseBranch->getParent();
     EndBlock = cast<BasicBlock>(TrueBranch->getOperand(0));
   }
 
   EndBlock->setName("select.end");
do {
     CurInstIterator = BB.begin();
     ModifiedDT = ModifyDT::NotModifyDT;
     while (CurInstIterator != BB.end()) {
       MadeChange |= optimizeInst(&*CurInstIterator++, ModifiedDT);
       if (ModifiedDT != ModifyDT::NotModifyDT) {
         // For huge function we tend to quickly go though the inner optmization
         // opportunities in the BB. So we go back to the BB head to re-optimize
         // each instruction instead of go back to the function head.
-        if (IsHugeFunc) {
-          DT.reset();
-          getDT(*BB.getParent());
+        if (IsHugeFunc)
           break;
-        } else {
-          return true;
-        }
-      }
-    }
   } while (ModifiedDT == ModifyDT::ModifyInstDT);
 
   bool MadeBitReverse = true;
   while (MadeBitReverse) {
     MadeBitReverse = false;
     for (auto &I : reverse(BB)) {
       if (makeBitReverse(I)) {
         MadeBitReverse = MadeChange = true;

 
 // A llvm.dbg.value may be using a value before its definition, due to
 // optimizations in this pass and others. Scan for such dbg.values, and rescue
 // them by moving the dbg.value to immediately after the value definition.
 // FIXME: Ideally this should never be necessary, and this has the potential
 // to re-order dbg.value intrinsics.
 bool CodeGenPrepare::placeDbgValues(Function &F) {
   bool MadeChange = false;
-  DominatorTree DT(F);
+  DominatorTree &DT = getDT();
 
   for (BasicBlock &BB : F) {
     for (Instruction &Insn : llvm::make_early_inc_range(BB)) {
       DbgValueInst *DVI = dyn_cast<DbgValueInst>(&Insn);
       if (!DVI)
         continue;
 
       SmallVector<Instruction *, 4> VIs;

 ///     br i1 %1, label %TrueBB, label %FalseBB
 /// \endcode
 /// This usually allows instruction selection to do even further optimizations
 /// and combine the compare with the branch instruction. Currently this is
 /// applied for targets which have "cheap" jump instructions.
 ///
 /// FIXME: Remove the (equivalent?) implementation in SelectionDAG.
 ///
-bool CodeGenPrepare::splitBranchCondition(Function &F, ModifyDT &ModifiedDT) {
+bool CodeGenPrepare::splitBranchCondition(Function &F) {
   if (!TM->Options.EnableFastISel || TLI->isJumpExpensive())
     return false;
 
   bool MadeChange = false;
   for (auto &BB : F) {
     // Does this BB end with the following?
     //   %cond1 = icmp|fcmp|binary instruction ...
     //   %cond2 = icmp|fcmp|binary instruction ...
for (auto &BB : F) {
     TBB->replacePhiUsesWith(&BB, TmpBB);
 
     // Add another incoming edge from the new BB.
     for (PHINode &PN : FBB->phis()) {
       auto *Val = PN.getIncomingValueForBlock(&BB);
       PN.addIncoming(Val, TmpBB);
     }
 
+    if (LI) {
+      if (Loop *L = LI->getLoopFor(&BB))
+        L->addBasicBlockToLoop(TmpBB, *LI);
+    }
+
+    if (DTU) {
+      // The edge we need to delete starts at BB and ends at whatever TBB ends
+      // up pointing to.
+      DTU->applyUpdates({{DominatorTree::Insert, &BB, TmpBB},
+                         {DominatorTree::Insert, TmpBB, TBB},
+                         {DominatorTree::Insert, TmpBB, FBB},
+                         {DominatorTree::Delete, &BB, TBB}});
+    }
+
     // Update the branch weights (from SelectionDAGBuilder::
     // FindMergedConditions).
     if (Opc == Instruction::Or) {
       // Codegen X | Y as:
       // BB1:
       //   jmp_if_X TBB
       //   jmp TmpBB
       // TmpBB:
if (Opc == Instruction::Or) {
         NewFalseWeight = FalseWeight;
         scaleWeights(NewTrueWeight, NewFalseWeight);
         Br2->setMetadata(LLVMContext::MD_prof,
                          MDBuilder(Br2->getContext())
                              .createBranchWeights(TrueWeight, FalseWeight));
       }
     }
 
-    ModifiedDT = ModifyDT::ModifyBBDT;
     MadeChange = true;
 
     LLVM_DEBUG(dbgs() << "After branch condition splitting\n"; BB.dump();
                TmpBB->dump());
   }
   return MadeChange;
 }

llvm/lib/Transforms/Utils/BypassSlowDivision.cpp

 // positive and less than 256 use an unsigned 8-bit divide.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/BypassSlowDivision.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Analysis/DomTreeUpdater.h"
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/KnownBits.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include <cassert>
 #include <cstdint>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "bypass-slow-division"
 
 namespace {
enum ValueRange {
   VALRNG_LIKELY_LONG
 };
 
 class FastDivInsertionTask {
   bool IsValidTask = false;
   Instruction *SlowDivOrRem = nullptr;
   IntegerType *BypassType = nullptr;
   BasicBlock *MainBB = nullptr;
+  DomTreeUpdater *DTU = nullptr;
+  LoopInfo *LI = nullptr;
 
   bool isHashLikeValue(Value *V, VisitedSetTy &Visited);
   ValueRange getValueRange(Value *Op, VisitedSetTy &Visited);
   QuotRemWithBB createSlowBB(BasicBlock *Successor);
   QuotRemWithBB createFastBB(BasicBlock *Successor);
   QuotRemPair createDivRemPhiNodes(QuotRemWithBB &LHS, QuotRemWithBB &RHS,
                                    BasicBlock *PhiBB);
   Value *insertOperandRuntimeCheck(Value *Op1, Value *Op2);
   std::optional<QuotRemPair> insertFastDivAndRem();
 
   bool isSignedOp() {
     return SlowDivOrRem->getOpcode() == Instruction::SDiv ||
            SlowDivOrRem->getOpcode() == Instruction::SRem;
   }
 
   bool isDivisionOp() {
     return SlowDivOrRem->getOpcode() == Instruction::SDiv ||
            SlowDivOrRem->getOpcode() == Instruction::UDiv;
   }
 
   Type *getSlowType() { return SlowDivOrRem->getType(); }
 
 public:
-  FastDivInsertionTask(Instruction *I, const BypassWidthsTy &BypassWidths);
+  FastDivInsertionTask(Instruction *I, const BypassWidthsTy &BypassWidths,
+                       DomTreeUpdater *DTU, LoopInfo *LI);
 
   Value *getReplacement(DivCacheTy &Cache);
 };
 
 } // end anonymous namespace
 
 FastDivInsertionTask::FastDivInsertionTask(Instruction *I,
-                                           const BypassWidthsTy &BypassWidths) {
+                                           const BypassWidthsTy &BypassWidths,
+                                           DomTreeUpdater *DTU, LoopInfo *LI)
+    : DTU(DTU), LI(LI) {
   switch (I->getOpcode()) {
   case Instruction::UDiv:
   case Instruction::SDiv:
   case Instruction::URem:
   case Instruction::SRem:
     SlowDivOrRem = I;
     break;
   default:
if (DividendShort && !isSignedOp()) {
     // 2) Divisor is greater than Dividend. In this case, no division is needed
     //    at all: The quotient is 0 and the remainder is equal to Dividend.
     //
     // So instead of checking at runtime whether Divisor fits into BypassType,
     // we emit a runtime check to differentiate between these two cases. This
     // lets us entirely avoid a long div.
 
     // Split the basic block before the div/rem.
-    BasicBlock *SuccessorBB = MainBB->splitBasicBlock(SlowDivOrRem);
+    BasicBlock *SuccessorBB = SplitBlock(MainBB, SlowDivOrRem, DTU, LI);
     // Remove the unconditional branch from MainBB to SuccessorBB.
     MainBB->back().eraseFromParent();
     QuotRemWithBB Long;
     Long.BB = MainBB;
     Long.Quotient = ConstantInt::get(getSlowType(), 0);
     Long.Remainder = Dividend;
     QuotRemWithBB Fast = createFastBB(SuccessorBB);
     QuotRemPair Result = createDivRemPhiNodes(Fast, Long, SuccessorBB);
     Value *CmpV = Builder.CreateICmpUGE(Dividend, Divisor);
     Builder.CreateCondBr(CmpV, Fast.BB, SuccessorBB);
+
+    if (DTU)
+      DTU->applyUpdates({{DominatorTree::Insert, MainBB, Fast.BB},
+                         {DominatorTree::Insert, Fast.BB, SuccessorBB}});
+
+    if (LI) {
+      if (Loop *L = LI->getLoopFor(MainBB))
+        L->addBasicBlockToLoop(Fast.BB, *LI);
+    }
+
     return Result;
   } else {
     // General case. Create both slow and fast div/rem pairs and choose one of
     // them at runtime.
 
     // Split the basic block before the div/rem.
-    BasicBlock *SuccessorBB = MainBB->splitBasicBlock(SlowDivOrRem);
+    BasicBlock *SuccessorBB = SplitBlock(MainBB, SlowDivOrRem, DTU, LI);
     // Remove the unconditional branch from MainBB to SuccessorBB.
     MainBB->back().eraseFromParent();
     QuotRemWithBB Fast = createFastBB(SuccessorBB);
     QuotRemWithBB Slow = createSlowBB(SuccessorBB);
     QuotRemPair Result = createDivRemPhiNodes(Fast, Slow, SuccessorBB);
     Value *CmpV = insertOperandRuntimeCheck(DividendShort ? nullptr : Dividend,
                                             DivisorShort ? nullptr : Divisor);
     Builder.CreateCondBr(CmpV, Fast.BB, Slow.BB);
+
+    if (DTU)
+      DTU->applyUpdates({{DominatorTree::Insert, MainBB, Fast.BB},
+                         {DominatorTree::Insert, MainBB, Slow.BB},
+                         {DominatorTree::Insert, Fast.BB, SuccessorBB},
+                         {DominatorTree::Insert, Slow.BB, SuccessorBB},
+                         {DominatorTree::Delete, MainBB, SuccessorBB}});
+
+    if (LI) {
+      if (Loop *L = LI->getLoopFor(MainBB)) {
+        L->addBasicBlockToLoop(Fast.BB, *LI);
+        L->addBasicBlockToLoop(Slow.BB, *LI);
+      }
+    }
+
     return Result;
   }
 }
 
 /// This optimization identifies DIV/REM instructions in a BB that can be
 /// profitably bypassed and carried out with a shorter, faster divide.
 bool llvm::bypassSlowDivision(BasicBlock *BB,
-                              const BypassWidthsTy &BypassWidths) {
+                              const BypassWidthsTy &BypassWidths,
+                              DomTreeUpdater *DTU, LoopInfo *LI) {
   DivCacheTy PerBBDivCache;
 
   bool MadeChange = false;
   Instruction *Next = &*BB->begin();
   while (Next != nullptr) {
     // We may add instructions immediately after I, but we want to skip over
     // them.
     Instruction *I = Next;
     Next = Next->getNextNode();
 
     // Ignore dead code to save time and avoid bugs.
     if (I->hasNUses(0))
       continue;
 
-    FastDivInsertionTask Task(I, BypassWidths);
+    FastDivInsertionTask Task(I, BypassWidths, DTU, LI);
     if (Value *Replacement = Task.getReplacement(PerBBDivCache)) {
       I->replaceAllUsesWith(Replacement);
       I->eraseFromParent();
       MadeChange = true;
     }
   }
 
   // Above we eagerly create divs and rems, as pairs, so that we can efficiently
   // create divrem machine instructions.  Now erase any unused divs / rems so we
   // don't leave extra instructions sitting around.
   for (auto &KV : PerBBDivCache)
     for (Value *V : {KV.second.Quotient, KV.second.Remainder})
       RecursivelyDeleteTriviallyDeadInstructions(V);
 
   return MadeChange;
 }

llvm/test/Transforms/CodeGenPrepare/AMDGPU/bypass-slow-div-debug-info-inseltpoison.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -mtriple=amdgcn-amd-amdhsa -codegenprepare %s | FileCheck %s
 ; Make sure BypassSlowDivision doesn't drop debug info
 
 define i64 @sdiv64(i64 %a, i64 %b) {
 ; CHECK-LABEL: @sdiv64(
-; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[A:%.*]], [[B:%.*]], [[DBG6:!dbg !.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[TMP1]], -4294967296, [[DBG6]]
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i64 [[TMP2]], 0, [[DBG6]]
-; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP9:%.*]], [[DBG6]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[A:%.*]], [[B:%.*]], !dbg [[DBG6:![0-9]+]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[TMP1]], -4294967296, !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i64 [[TMP2]], 0, !dbg [[DBG6]]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP9:%.*]], !dbg [[DBG6]]
 ; CHECK:       4:
-; CHECK-NEXT:    [[TMP5:%.*]] = trunc i64 [[B]] to i32, [[DBG6]]
-; CHECK-NEXT:    [[TMP6:%.*]] = trunc i64 [[A]] to i32, [[DBG6]]
-; CHECK-NEXT:    [[TMP7:%.*]] = udiv i32 [[TMP6]], [[TMP5]], [[DBG6]]
-; CHECK-NEXT:    [[TMP8:%.*]] = zext i32 [[TMP7]] to i64, [[DBG6]]
-; CHECK-NEXT:    br label [[TMP11:%.*]], [[DBG6]]
+; CHECK-NEXT:    [[TMP5:%.*]] = trunc i64 [[B]] to i32, !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP6:%.*]] = trunc i64 [[A]] to i32, !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP7:%.*]] = udiv i32 [[TMP6]], [[TMP5]], !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP8:%.*]] = zext i32 [[TMP7]] to i64, !dbg [[DBG6]]
+; CHECK-NEXT:    br label [[DOTSPLIT:%.*]], !dbg [[DBG6]]
 ; CHECK:       9:
-; CHECK-NEXT:    [[TMP10:%.*]] = sdiv i64 [[A]], [[B]], [[DBG6]]
-; CHECK-NEXT:    br label [[TMP11]], [[DBG6]]
-; CHECK:       11:
-; CHECK-NEXT:    [[TMP12:%.*]] = phi i64 [ [[TMP8]], [[TMP4]] ], [ [[TMP10]], [[TMP9]] ], [[DBG6]]
-; CHECK-NEXT:    ret i64 [[TMP12]]
+; CHECK-NEXT:    [[TMP10:%.*]] = sdiv i64 [[A]], [[B]], !dbg [[DBG6]]
+; CHECK-NEXT:    br label [[DOTSPLIT]], !dbg [[DBG6]]
+; CHECK:       .split:
+; CHECK-NEXT:    [[TMP11:%.*]] = phi i64 [ [[TMP8]], [[TMP4]] ], [ [[TMP10]], [[TMP9]] ], !dbg [[DBG6]]
+; CHECK-NEXT:    ret i64 [[TMP11]]
 ;
   %d = sdiv i64 %a, %b, !dbg !6
   ret i64 %d
 }
 
 ; FIXME: The debugloc for the rem parts end up with the dbg of the
 ; division.
 define <2 x i64> @sdivrem64(i64 %a, i64 %b) {
 ; CHECK-LABEL: @sdivrem64(
-; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[A:%.*]], [[B:%.*]], [[DBG6]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[TMP1]], -4294967296, [[DBG6]]
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i64 [[TMP2]], 0, [[DBG6]]
-; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP11:%.*]], [[DBG6]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[A:%.*]], [[B:%.*]], !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[TMP1]], -4294967296, !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i64 [[TMP2]], 0, !dbg [[DBG6]]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP11:%.*]], !dbg [[DBG6]]
 ; CHECK:       4:
-; CHECK-NEXT:    [[TMP5:%.*]] = trunc i64 [[B]] to i32, [[DBG6]]
-; CHECK-NEXT:    [[TMP6:%.*]] = trunc i64 [[A]] to i32, [[DBG6]]
-; CHECK-NEXT:    [[TMP7:%.*]] = udiv i32 [[TMP6]], [[TMP5]], [[DBG6]]
-; CHECK-NEXT:    [[TMP8:%.*]] = urem i32 [[TMP6]], [[TMP5]], [[DBG6]]
-; CHECK-NEXT:    [[TMP9:%.*]] = zext i32 [[TMP7]] to i64, [[DBG6]]
-; CHECK-NEXT:    [[TMP10:%.*]] = zext i32 [[TMP8]] to i64, [[DBG6]]
-; CHECK-NEXT:    br label [[TMP14:%.*]], [[DBG6]]
+; CHECK-NEXT:    [[TMP5:%.*]] = trunc i64 [[B]] to i32, !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP6:%.*]] = trunc i64 [[A]] to i32, !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP7:%.*]] = udiv i32 [[TMP6]], [[TMP5]], !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP8:%.*]] = urem i32 [[TMP6]], [[TMP5]], !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP9:%.*]] = zext i32 [[TMP7]] to i64, !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP10:%.*]] = zext i32 [[TMP8]] to i64, !dbg [[DBG6]]
+; CHECK-NEXT:    br label [[DOTSPLIT:%.*]], !dbg [[DBG6]]
 ; CHECK:       11:
-; CHECK-NEXT:    [[TMP12:%.*]] = sdiv i64 [[A]], [[B]], [[DBG6]]
-; CHECK-NEXT:    [[TMP13:%.*]] = srem i64 [[A]], [[B]], [[DBG6]]
-; CHECK-NEXT:    br label [[TMP14]], [[DBG6]]
-; CHECK:       14:
-; CHECK-NEXT:    [[TMP15:%.*]] = phi i64 [ [[TMP9]], [[TMP4]] ], [ [[TMP12]], [[TMP11]] ], [[DBG6]]
-; CHECK-NEXT:    [[TMP16:%.*]] = phi i64 [ [[TMP10]], [[TMP4]] ], [ [[TMP13]], [[TMP11]] ], [[DBG6]]
-; CHECK-NEXT:    [[INS0:%.*]] = insertelement <2 x i64> poison, i64 [[TMP15]], i32 0
-; CHECK-NEXT:    [[INS1:%.*]] = insertelement <2 x i64> [[INS0]], i64 [[TMP16]], i32 1
+; CHECK-NEXT:    [[TMP12:%.*]] = sdiv i64 [[A]], [[B]], !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP13:%.*]] = srem i64 [[A]], [[B]], !dbg [[DBG6]]
+; CHECK-NEXT:    br label [[DOTSPLIT]], !dbg [[DBG6]]
+; CHECK:       .split:
+; CHECK-NEXT:    [[TMP14:%.*]] = phi i64 [ [[TMP9]], [[TMP4]] ], [ [[TMP12]], [[TMP11]] ], !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP15:%.*]] = phi i64 [ [[TMP10]], [[TMP4]] ], [ [[TMP13]], [[TMP11]] ], !dbg [[DBG6]]
+; CHECK-NEXT:    [[INS0:%.*]] = insertelement <2 x i64> poison, i64 [[TMP14]], i32 0
+; CHECK-NEXT:    [[INS1:%.*]] = insertelement <2 x i64> [[INS0]], i64 [[TMP15]], i32 1
 ; CHECK-NEXT:    ret <2 x i64> [[INS1]]
 ;
   %d = sdiv i64 %a, %b, !dbg !6
   %r = srem i64 %a, %b, !dbg !10
   %ins0 = insertelement <2 x i64> poison, i64 %d, i32 0
   %ins1 = insertelement <2 x i64> %ins0, i64 %r, i32 1
   ret <2 x i64> %ins1
 }

llvm/test/Transforms/CodeGenPrepare/AMDGPU/bypass-slow-div-debug-info.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -mtriple=amdgcn-amd-amdhsa -codegenprepare %s | FileCheck %s
 ; Make sure BypassSlowDivision doesn't drop debug info
 
 define i64 @sdiv64(i64 %a, i64 %b) {
 ; CHECK-LABEL: @sdiv64(
-; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[A:%.*]], [[B:%.*]], !dbg !6
-; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[TMP1]], -4294967296, !dbg !6
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i64 [[TMP2]], 0, !dbg !6
-; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP9:%.*]], !dbg !6
+; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[A:%.*]], [[B:%.*]], !dbg [[DBG6:![0-9]+]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[TMP1]], -4294967296, !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i64 [[TMP2]], 0, !dbg [[DBG6]]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP9:%.*]], !dbg [[DBG6]]
 ; CHECK:       4:
-; CHECK-NEXT:    [[TMP5:%.*]] = trunc i64 [[B]] to i32, !dbg !6
-; CHECK-NEXT:    [[TMP6:%.*]] = trunc i64 [[A]] to i32, !dbg !6
-; CHECK-NEXT:    [[TMP7:%.*]] = udiv i32 [[TMP6]], [[TMP5]], !dbg !6
-; CHECK-NEXT:    [[TMP8:%.*]] = zext i32 [[TMP7]] to i64, !dbg !6
-; CHECK-NEXT:    br label [[TMP11:%.*]], !dbg !6
+; CHECK-NEXT:    [[TMP5:%.*]] = trunc i64 [[B]] to i32, !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP6:%.*]] = trunc i64 [[A]] to i32, !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP7:%.*]] = udiv i32 [[TMP6]], [[TMP5]], !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP8:%.*]] = zext i32 [[TMP7]] to i64, !dbg [[DBG6]]
+; CHECK-NEXT:    br label [[DOTSPLIT:%.*]], !dbg [[DBG6]]
 ; CHECK:       9:
-; CHECK-NEXT:    [[TMP10:%.*]] = sdiv i64 [[A]], [[B]], !dbg !6
-; CHECK-NEXT:    br label [[TMP11]], !dbg !6
-; CHECK:       11:
-; CHECK-NEXT:    [[TMP12:%.*]] = phi i64 [ [[TMP8]], [[TMP4]] ], [ [[TMP10]], [[TMP9]] ], !dbg !6
-; CHECK-NEXT:    ret i64 [[TMP12]]
+; CHECK-NEXT:    [[TMP10:%.*]] = sdiv i64 [[A]], [[B]], !dbg [[DBG6]]
+; CHECK-NEXT:    br label [[DOTSPLIT]], !dbg [[DBG6]]
+; CHECK:       .split:
+; CHECK-NEXT:    [[TMP11:%.*]] = phi i64 [ [[TMP8]], [[TMP4]] ], [ [[TMP10]], [[TMP9]] ], !dbg [[DBG6]]
+; CHECK-NEXT:    ret i64 [[TMP11]]
 ;
   %d = sdiv i64 %a, %b, !dbg !6
   ret i64 %d
 }
 
 ; FIXME: The debugloc for the rem parts end up with the dbg of the
 ; division.
 define <2 x i64> @sdivrem64(i64 %a, i64 %b) {
 ; CHECK-LABEL: @sdivrem64(
-; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[A:%.*]], [[B:%.*]], !dbg !6
-; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[TMP1]], -4294967296, !dbg !6
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i64 [[TMP2]], 0, !dbg !6
-; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP11:%.*]], !dbg !6
+; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[A:%.*]], [[B:%.*]], !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[TMP1]], -4294967296, !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i64 [[TMP2]], 0, !dbg [[DBG6]]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP11:%.*]], !dbg [[DBG6]]
 ; CHECK:       4:
-; CHECK-NEXT:    [[TMP5:%.*]] = trunc i64 [[B]] to i32, !dbg !6
-; CHECK-NEXT:    [[TMP6:%.*]] = trunc i64 [[A]] to i32, !dbg !6
-; CHECK-NEXT:    [[TMP7:%.*]] = udiv i32 [[TMP6]], [[TMP5]], !dbg !6
-; CHECK-NEXT:    [[TMP8:%.*]] = urem i32 [[TMP6]], [[TMP5]], !dbg !6
-; CHECK-NEXT:    [[TMP9:%.*]] = zext i32 [[TMP7]] to i64, !dbg !6
-; CHECK-NEXT:    [[TMP10:%.*]] = zext i32 [[TMP8]] to i64, !dbg !6
-; CHECK-NEXT:    br label [[TMP14:%.*]], !dbg !6
+; CHECK-NEXT:    [[TMP5:%.*]] = trunc i64 [[B]] to i32, !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP6:%.*]] = trunc i64 [[A]] to i32, !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP7:%.*]] = udiv i32 [[TMP6]], [[TMP5]], !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP8:%.*]] = urem i32 [[TMP6]], [[TMP5]], !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP9:%.*]] = zext i32 [[TMP7]] to i64, !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP10:%.*]] = zext i32 [[TMP8]] to i64, !dbg [[DBG6]]
+; CHECK-NEXT:    br label [[DOTSPLIT:%.*]], !dbg [[DBG6]]
 ; CHECK:       11:
-; CHECK-NEXT:    [[TMP12:%.*]] = sdiv i64 [[A]], [[B]], !dbg !6
-; CHECK-NEXT:    [[TMP13:%.*]] = srem i64 [[A]], [[B]], !dbg !6
-; CHECK-NEXT:    br label [[TMP14]], !dbg !6
-; CHECK:       14:
-; CHECK-NEXT:    [[TMP15:%.*]] = phi i64 [ [[TMP9]], [[TMP4]] ], [ [[TMP12]], [[TMP11]] ], !dbg !6
-; CHECK-NEXT:    [[TMP16:%.*]] = phi i64 [ [[TMP10]], [[TMP4]] ], [ [[TMP13]], [[TMP11]] ], !dbg !6
-; CHECK-NEXT:    [[INS0:%.*]] = insertelement <2 x i64> undef, i64 [[TMP15]], i32 0
-; CHECK-NEXT:    [[INS1:%.*]] = insertelement <2 x i64> [[INS0]], i64 [[TMP16]], i32 1
+; CHECK-NEXT:    [[TMP12:%.*]] = sdiv i64 [[A]], [[B]], !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP13:%.*]] = srem i64 [[A]], [[B]], !dbg [[DBG6]]
+; CHECK-NEXT:    br label [[DOTSPLIT]], !dbg [[DBG6]]
+; CHECK:       .split:
+; CHECK-NEXT:    [[TMP14:%.*]] = phi i64 [ [[TMP9]], [[TMP4]] ], [ [[TMP12]], [[TMP11]] ], !dbg [[DBG6]]
+; CHECK-NEXT:    [[TMP15:%.*]] = phi i64 [ [[TMP10]], [[TMP4]] ], [ [[TMP13]], [[TMP11]] ], !dbg [[DBG6]]
+; CHECK-NEXT:    [[INS0:%.*]] = insertelement <2 x i64> undef, i64 [[TMP14]], i32 0
+; CHECK-NEXT:    [[INS1:%.*]] = insertelement <2 x i64> [[INS0]], i64 [[TMP15]], i32 1
 ; CHECK-NEXT:    ret <2 x i64> [[INS1]]
 ;
   %d = sdiv i64 %a, %b, !dbg !6
   %r = srem i64 %a, %b, !dbg !10
   %ins0 = insertelement <2 x i64> undef, i64 %d, i32 0
   %ins1 = insertelement <2 x i64> %ins0, i64 %r, i32 1
   ret <2 x i64> %ins1
 }