[JumpThreading] Preserve DT and LVI across the pass.

[brzycki]

Summary

JumpThreading now preserves dominance and lazy value information across the entire pass. The pass manager is also informed of this preservation with the goal of DT and LVI being recalculated fewer times overall during compilation.

This change prepares JumpThreading for enhanced opportunities; particularly those across loop boundaries.

Patch by Brian Rzycki and Sebastian Pop.

[davide]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

107–108 ↗

(On Diff #114041)

Now that the domtree is preserved, you can probably also preserve LVI.
The reason why it was disabled is that LVI holds a pointer to DomTree, and when you free the dominator analysis result, you end up with garbage.

[kuhar]

This patch uses the "!find-push_back" pattern a lot:

DominatorTree::UpdateType UT = {DominatorTree::Delete, *PI, BB};
if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end()) {
  Updates.push_back(UT);

which made me think that maybe it would be better to offer some better interface for applying updates that would automatically get rid of the duplicate ones? Or maybe it would make sense to just have a second overload that accepts set-like containers.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

1951 ↗

(On Diff #114041)

If there are exactly 3 updates every time, maybe it'd make sense to use SmallVector<DT::UT, 3> or just an array here?

2518 ↗

(On Diff #114041)

(Same us above)
Maybe worth using SmallVector/array?

llvm/lib/Transforms/Utils/Local.cpp

183 ↗

(On Diff #114041)

Why not some standard algorithm? I.E. std::find or std::none_of

1826 ↗

(On Diff #114041)

applyUpdates should work with empty update set, but I guess it makes no real difference here.

[brzycki]

In D37528#862800, @kuhar wrote:

This patch uses the "!find-push_back" pattern a lot:

DominatorTree::UpdateType UT = {DominatorTree::Delete, *PI, BB};
if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end()) {
  Updates.push_back(UT);

which made me think that maybe it would be better to offer some better interface for applying updates that would automatically get rid of the duplicate ones? Or maybe it would make sense to just have a second overload that accepts set-like containers.

Hi Kuba, thanks for taking the time to review. Since this patch is probably the first major consumer of your ABI there might be opportunities to learn here. I'm a bit torn as to which way it should go.

In the current implementation you have strong assert() checks for the following:

• deleting an edge that still exists in the CFG
• attempting to delete or insert the same edge more than once
• attempting to insert an edge to itself { Insert, BB, BB }

Those three reasons are primarily why you see the gating code so often repeated. I hit every one of those problems during make check debug sessions. I actually consider these asserts() to be a good thing since they didn't let errors quietly continue and complicate gdb debugging. The down side is it does clutter the call sites a bit with extra checks.

I'm just brainstorming here but maybe one option is to only assert when running a non-release build. The rest of the time those three cases are simply ignored and you do an early return. But this makes me a little uneasy as it allows for error propagation on new code only tested with Release builds...

Even with this added overhead I find the new interface much easier to use than the old one. When I started this patch a few months ago your code wasn't available and I had several custom functions to fix up the dominator tree. It was slow going and highly error-prone.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

107–108 ↗

(On Diff #114041)

Hi David, I'm hopeful that this (and other benefits) can be obtained with dominance preserved across JumpThreading. This is an important optimization in LLVM and there are more opportunities I'd like to see it catch.

For now I'd like to keep this patch just focused on DT. Let's talk after this gets accepted to preserve LVI.

1951 ↗

(On Diff #114041)

I copied your example code in the new dominator tree unit tests. I'd be happy to change this to whichever you think makes more sense between SmallVector or an Array.

2518 ↗

(On Diff #114041)

Yup, I agree.

llvm/lib/Transforms/Utils/Local.cpp

183 ↗

(On Diff #114041)

I'm a better C programmer than a C++ one. :)

I'll try both STL calls to see which one feels more natural in context.

1826 ↗

(On Diff #114041)

I did this because Updates.empty() is a very fast call and wanted to avoid the potential of calling applyUpdates with no work to do. I can take it out if you think that's over-optimizing.

[brzycki]

In D37528#862800, @kuhar wrote:

One other comment: some of the layout of this patch was designed based on feedback between us in email. I asked you if applyUpdates() was more expensive for a single Insertion/Deletion than a direct call. Were I to assume otherwise some of the calls and logic would be simpler. I'd always create an Updates array and just push_back() throughout the function. On exit I'd call applyUpdates() with an empty vector or not. If you think code clarity trumps the (small?) performance deltas I'd be open to revisiting some of the call sites.

[kuhar]

In D37528#863478, @brzycki wrote:

Hi Kuba, thanks for taking the time to review. Since this patch is probably the first major consumer of your ABI there might be opportunities to learn here. I'm a bit torn as to which way it should go.

In the current implementation you have strong assert() checks for the following:

• deleting an edge that still exists in the CFG
• attempting to delete or insert the same edge more than once
• attempting to insert an edge to itself { Insert, BB, BB }

Those three reasons are primarily why you see the gating code so often repeated. I hit every one of those problems during make check debug sessions. I actually consider these asserts() to be a good thing since they didn't let errors quietly continue and complicate gdb debugging. The down side is it does clutter the call sites a bit with extra checks.

I'm just brainstorming here but maybe one option is to only assert when running a non-release build. The rest of the time those three cases are simply ignored and you do an early return. But this makes me a little uneasy as it allows for error propagation on new code only tested with Release builds...

I don't think having different behavior in debug and release is a good idea. I'd rather see it as either a separate function or a helper utility that lifts these restrictions and automatically deduplicates it, but as you noticed, the current strict API makes it more difficult to make mistakes when collecting updates to apply. Perhaps something worth thinking about would be adding a helper function to JumpThreading itself, eg. addUpdateIfNew(CurrentUpdates, NewUpdate)? For now, it would be only used in JumpThreading anyway.

Even with this added overhead I find the new interface much easier to use than the old one. When I started this patch a few months ago your code wasn't available and I had several custom functions to fix up the dominator tree. It was slow going and highly error-prone.

Good to hear that!

llvm/lib/Transforms/Scalar/JumpThreading.cpp

1951 ↗

(On Diff #114041)

applyUpdates takes ArrayRef as a parameter, so all 3 of vector, SmallVector, and array should do. The thing with vector is that it will probably allocate, whereas the other two won't. I'd personally go with std::array or SmallVector here.

llvm/lib/Transforms/Utils/Local.cpp

1826 ↗

(On Diff #114041)

I think it's fine as-is.

[kuhar]

@brzycki, one related thing: have you tried preserving postdominators as well? I'm not sure if that would be beneficial here, but in theory, it should be pretty simple, as you can pass exactly the same update sequences to the DominatorTree and PostDominatorTree.

[brzycki]

Preserves LVI across JumpThreading.

Removed unnecessary std::vector calls.

Fixed a bug when normal and unwind destinations were the same for one case.

Fixed the JumpThreading declaration of preserved/requires to make sure the dominator tree happens first so that LVI will properly instantiate the private LVI->DT variable.

[brzycki]

In D37528#863731, @kuhar wrote:

@brzycki, one related thing: have you tried preserving postdominators as well? I'm not sure if that would be beneficial here, but in theory, it should be pretty simple, as you can pass exactly the same update sequences to the DominatorTree and PostDominatorTree.

I have not. I'll talk to @sebpop and see if he thinks this makes sense to include in this patch. Depending on our follow-on updates to JT we may need post dominators as well.

[• dberlin]

In D37528#864194, @brzycki wrote:

In D37528#863731, @kuhar wrote:

@brzycki, one related thing: have you tried preserving postdominators as well? I'm not sure if that would be beneficial here, but in theory, it should be pretty simple, as you can pass exactly the same update sequences to the DominatorTree and PostDominatorTree.

I have not. I'll talk to @sebpop and see if he thinks this makes sense to include in this patch. Depending on our follow-on updates to JT we may need post dominators as well.

Even if you don't need it, it's trivial to preserve and probably worth doing.

Jakub, we should just create an updater object that updates whatever is around with the same edge sequence.

if you stare at getBestSimplifyQuery in lib/Analysis/SimplifyInstruction.cpp, you can see how to do that with both the old and new PM.

You can see how it is used in Transforms/Scalar/CorrelatedValuePropagation.cpp and Transforms/Scalar/LoopRotation.cpp for both the old and new PM.
An updater object that gets the postdom/dom tree if it's around, and handles the update edge sequence for both, would go a long way to getting postdom preserved everywhere.

[kuhar]

LGTM after the fixes, but you may want to wait for a green light from someone else.

llvm/lib/Transforms/Utils/Local.cpp

678 ↗

(On Diff #114284)

nit: s/replaceEntryBB/ReplaceEntryBB

[sebpop]

In D37528#864259, @dberlin wrote:

In D37528#864194, @brzycki wrote:

In D37528#863731, @kuhar wrote:

@brzycki, one related thing: have you tried preserving postdominators as well? I'm not sure if that would be beneficial here, but in theory, it should be pretty simple, as you can pass exactly the same update sequences to the DominatorTree and PostDominatorTree.

I have not. I'll talk to @sebpop and see if he thinks this makes sense to include in this patch. Depending on our follow-on updates to JT we may need post dominators as well.

Even if you don't need it, it's trivial to preserve and probably worth doing.

Agreed. Preserving post-dominators will also save some compilation time which is always good to get.

[brzycki]

Use none_of instead of custom loop.

Fixed grammatical case issues.

[brzycki]

In D37528#864736, @sebpop wrote:

In D37528#864259, @dberlin wrote:

In D37528#864194, @brzycki wrote:

In D37528#863731, @kuhar wrote:

@brzycki, one related thing: have you tried preserving postdominators as well? I'm not sure if that would be beneficial here, but in theory, it should be pretty simple, as you can pass exactly the same update sequences to the DominatorTree and PostDominatorTree.

I have not. I'll talk to @sebpop and see if he thinks this makes sense to include in this patch. Depending on our follow-on updates to JT we may need post dominators as well.

Even if you don't need it, it's trivial to preserve and probably worth doing.

Agreed. Preserving post-dominators will also save some compilation time which is always good to get.

@sebpop and @dberlin I'll start looking at this. Depending on the complexity of the updates for PDT at the DT call-sites the work may warrant a separate patch on top of this one.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

107–108 ↗

(On Diff #114041)

@davide The latest uploaded diff preserves LVI as well as DT.

[brzycki]

Rebase to tip as of 9/25. Eugene Zelenko's commit using Clang-tidy modernize-use-using required manual fixes.

Fixed a corner-case bug in MergeBasicBlockIntoOnlyPred() where DestBB could be requested to dominate itself, triggering an assert in the dominance insert code.

[brzycki]

In D37528#881141, @brzycki wrote:

Rebase to tip as of 9/25. Eugene Zelenko's commit using Clang-tidy modernize-use-using required manual fixes.

Fixed a corner-case bug in MergeBasicBlockIntoOnlyPred() where DestBB could be requested to dominate itself, triggering an assert in the dominance insert code.

I also investigated preserving PDT across JumpThreading. It's turning out to be less trivial than originally anticipated. There are corner-cases of PDT->deleteEdge() that do not work automatically when basic blocks are about to be deleted from a function. I also have to update the PDT preservation algorithm for several external functions:

• SplitBlockPredecessors()
• SplitEdge()
• SplitBlockAndInsertIfThen()
• computeKnownBits()
• (and possibly more that I missed)

For these reasons I'd prefer to preserve PDT in a separate patch on top of this one. If @kuhar and @dberlin are OK with this I'd like to move forward with merging this patch as-is.

[kuhar]

LGTM

[brzycki]

In D37528#881713, @kuhar wrote:

LGTM

Thank you @kuhar . @dberlin are you OK with the patch? If so I can ask one of my peers to push it into tip. Thank you both for making this patch better.

[brzycki]

This comment was removed by brzycki.

[brzycki]

I accidentally re-opened the wrong diff.

llvm/trunk/include/llvm/Transforms/Scalar/JumpThreading.h

 
 namespace llvm {
 
 class BasicBlock;
 class BinaryOperator;
 class BranchInst;
 class CmpInst;
 class Constant;
+class DominatorTree;
 class Function;
 class Instruction;
 class IntrinsicInst;
 class LazyValueInfo;
 class LoadInst;
 class PHINode;
 class TargetLibraryInfo;
 class Value;

 ///   if (X < 3) {
 ///
 /// In this case, the unconditional branch at the end of the first if can be
 /// revectored to the false side of the second if.
 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
   TargetLibraryInfo *TLI;
   LazyValueInfo *LVI;
   AliasAnalysis *AA;
+  DominatorTree *DT;
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   bool HasProfileData = false;
   bool HasGuards = false;
 #ifdef NDEBUG
   SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
 #else
   SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
struct RecursionSetRemover {
     ~RecursionSetRemover() { TheSet.erase(ThePair); }
   };
 
 public:
   JumpThreadingPass(int T = -1);
 
   // Glue for old PM.
   bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_,
-               AliasAnalysis *AA_, bool HasProfileData_,
+               AliasAnalysis *AA_, DominatorTree *DT_, bool HasProfileData_,
                std::unique_ptr<BlockFrequencyInfo> BFI_,
                std::unique_ptr<BranchProbabilityInfo> BPI_);
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   void releaseMemory() {
     BFI.reset();
     BPI.reset();

llvm/trunk/include/llvm/Transforms/Utils/Local.h

 /// If a terminator instruction is predicated on a constant value, convert it
 /// into an unconditional branch to the constant destination.
 /// This is a nontrivial operation because the successors of this basic block
 /// must have their PHI nodes updated.
 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
 /// conditions and indirectbr addresses this might make dead if
 /// DeleteDeadConditions is true.
 bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions = false,
-                            const TargetLibraryInfo *TLI = nullptr);
+                            const TargetLibraryInfo *TLI = nullptr,
+                            DominatorTree *DT = nullptr);
 
 //===----------------------------------------------------------------------===//
 //  Local dead code elimination.
 //
 
 /// Return true if the result produced by the instruction is not used, and the
 /// instruction has no side effects.
 bool isInstructionTriviallyDead(Instruction *I,

 ///
 /// Unlike the removePredecessor method, this attempts to simplify uses of PHI
 /// nodes that collapse into identity values.  For example, if we have:
 ///   x = phi(1, 0, 0, 0)
 ///   y = and x, z
 ///
 /// .. and delete the predecessor corresponding to the '1', this will attempt to
 /// recursively fold the 'and' to 0.
-void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred);
+void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred,
+                                  DominatorTree *DT = nullptr);
 
 /// BB is a block with one predecessor and its predecessor is known to have one
 /// successor (BB!). Eliminate the edge between them, moving the instructions in
 /// the predecessor into BB. This deletes the predecessor block.
 void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DominatorTree *DT = nullptr);
 
 /// BB is known to contain an unconditional branch, and contains no instructions
 /// other than PHI nodes, potential debug intrinsics and the branch. If
 /// possible, eliminate BB by rewriting all the predecessors to branch to the
 /// successor block and return true. If we can't transform, return false.
-bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB);
+bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
+                                             DominatorTree *DT = nullptr);
 
 /// Check for and eliminate duplicate PHI nodes in this block. This doesn't try
 /// to be clever about PHI nodes which differ only in the order of the incoming
 /// values, but instcombine orders them so it usually won't matter.
 bool EliminateDuplicatePHINodes(BasicBlock *BB);
 
 /// This function is used to do simplification of a CFG.  For example, it
 /// adjusts branches to branches to eliminate the extra hop, it eliminates

 
 /// Remove all instructions from a basic block other than it's terminator
 /// and any present EH pad instructions.
 unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB);
 
 /// Insert an unreachable instruction before the specified
 /// instruction, making it and the rest of the code in the block dead.
 unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap,
-                             bool PreserveLCSSA = false);
+                             bool PreserveLCSSA = false,
+                             DominatorTree *DT = nullptr);
 
 /// Convert the CallInst to InvokeInst with the specified unwind edge basic
 /// block.  This also splits the basic block where CI is located, because
 /// InvokeInst is a terminator instruction.  Returns the newly split basic
 /// block.
 BasicBlock *changeToInvokeAndSplitBasicBlock(CallInst *CI,
                                              BasicBlock *UnwindEdge);
 
 /// Replace 'BB's terminator with one that does not have an unwind successor
 /// block. Rewrites `invoke` to `call`, etc. Updates any PHIs in unwind
 /// successor.
 ///
 /// \param BB  Block whose terminator will be replaced.  Its terminator must
 ///            have an unwind successor.
-void removeUnwindEdge(BasicBlock *BB);
+void removeUnwindEdge(BasicBlock *BB, DominatorTree *DT = nullptr);
 
 /// Remove all blocks that can not be reached from the function's entry.
 ///
 /// Returns true if any basic block was removed.
-bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr);
+bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI = nullptr,
+                             DominatorTree *DT = nullptr);
 
 /// Combine the metadata of two instructions so that K can replace J
 ///
 /// Metadata not listed as known via KnownIDs is removed
 void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs);
 
 /// Combine the metadata of two instructions so that K can replace J. This
 /// specifically handles the case of CSE-like transformations.

llvm/trunk/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp

public:
     static char ID;
     CorrelatedValuePropagation(): FunctionPass(ID) {
      initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
+      AU.addRequired<DominatorTreeWrapperPass>();
       AU.addRequired<LazyValueInfoWrapperPass>();
       AU.addPreserved<GlobalsAAWrapperPass>();
     }
   };
 }
 
 char CorrelatedValuePropagation::ID = 0;
 INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
                 "Value Propagation", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
 INITIALIZE_PASS_END(CorrelatedValuePropagation, "correlated-propagation",
                 "Value Propagation", false, false)
 
 // Public interface to the Value Propagation pass
 Pass *llvm::createCorrelatedValuePropagationPass() {
   return new CorrelatedValuePropagation();
 }

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

public:
 
     JumpThreading(int T = -1) : FunctionPass(ID), Impl(T) {
       initializeJumpThreadingPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
-      if (PrintLVIAfterJumpThreading)
-        AU.addRequired<DominatorTreeWrapperPass>();
+      AU.addPreserved<DominatorTreeWrapperPass>();
       AU.addRequired<AAResultsWrapperPass>();
       AU.addRequired<LazyValueInfoWrapperPass>();
+      AU.addPreserved<LazyValueInfoWrapperPass>();
       AU.addPreserved<GlobalsAAWrapperPass>();
       AU.addRequired<TargetLibraryInfoWrapperPass>();
     }
 
     void releaseMemory() override { Impl.releaseMemory(); }
   };
 
 } // end anonymous namespace
 
 char JumpThreading::ID = 0;
 
 INITIALIZE_PASS_BEGIN(JumpThreading, "jump-threading",
                 "Jump Threading", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_END(JumpThreading, "jump-threading",
                 "Jump Threading", false, false)
 
 // Public interface to the Jump Threading pass
 FunctionPass *llvm::createJumpThreadingPass(int Threshold) {
static void updatePredecessorProfileMetadata(PHINode *PN, BasicBlock *BB) {
   }
 }
 
 /// runOnFunction - Toplevel algorithm.
 bool JumpThreading::runOnFunction(Function &F) {
   if (skipFunction(F))
     return false;
   auto TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
+  // Get DT analysis before LVI. When LVI is initialized it conditionally adds
+  // DT if it's available.
+  auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   auto LVI = &getAnalysis<LazyValueInfoWrapperPass>().getLVI();
   auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   bool HasProfileData = F.getEntryCount().hasValue();
   if (HasProfileData) {
     LoopInfo LI{DominatorTree(F)};
     BPI.reset(new BranchProbabilityInfo(F, LI, TLI));
     BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
   }
 
-  bool Changed = Impl.runImpl(F, TLI, LVI, AA, HasProfileData, std::move(BFI),
-                              std::move(BPI));
+  bool Changed = Impl.runImpl(F, TLI, LVI, AA, DT, HasProfileData,
+                              std::move(BFI), std::move(BPI));
   if (PrintLVIAfterJumpThreading) {
     dbgs() << "LVI for function '" << F.getName() << "':\n";
-    LVI->printLVI(F, getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
-                  dbgs());
+    LVI->printLVI(F, *DT, dbgs());
   }
   return Changed;
 }
 
 PreservedAnalyses JumpThreadingPass::run(Function &F,
                                          FunctionAnalysisManager &AM) {
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
+  // Get DT analysis before LVI. When LVI is initialized it conditionally adds
+  // DT if it's available.
+  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &LVI = AM.getResult<LazyValueAnalysis>(F);
   auto &AA = AM.getResult<AAManager>(F);
 
   std::unique_ptr<BlockFrequencyInfo> BFI;
   std::unique_ptr<BranchProbabilityInfo> BPI;
   bool HasProfileData = F.getEntryCount().hasValue();
   if (HasProfileData) {
     LoopInfo LI{DominatorTree(F)};
     BPI.reset(new BranchProbabilityInfo(F, LI, &TLI));
     BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
   }
 
-  bool Changed = runImpl(F, &TLI, &LVI, &AA, HasProfileData, std::move(BFI),
-                         std::move(BPI));
+  bool Changed = runImpl(F, &TLI, &LVI, &AA, &DT, HasProfileData,
+                         std::move(BFI), std::move(BPI));
 
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<GlobalsAA>();
+  PA.preserve<DominatorTreeAnalysis>();
+  PA.preserve<LazyValueAnalysis>();
   return PA;
 }
 
 bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
                                 LazyValueInfo *LVI_, AliasAnalysis *AA_,
-                                bool HasProfileData_,
+                                DominatorTree *DT_, bool HasProfileData_,
                                 std::unique_ptr<BlockFrequencyInfo> BFI_,
                                 std::unique_ptr<BranchProbabilityInfo> BPI_) {
   DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n");
   TLI = TLI_;
   LVI = LVI_;
   AA = AA_;
+  DT = DT_;
   BFI.reset();
   BPI.reset();
   // When profile data is available, we need to update edge weights after
   // successful jump threading, which requires both BPI and BFI being available.
   HasProfileData = HasProfileData_;
   auto *GuardDecl = F.getParent()->getFunction(
       Intrinsic::getName(Intrinsic::experimental_guard));
   HasGuards = GuardDecl && !GuardDecl->use_empty();
   if (HasProfileData) {
     BPI = std::move(BPI_);
     BFI = std::move(BFI_);
   }
 
   // Remove unreachable blocks from function as they may result in infinite
   // loop. We do threading if we found something profitable. Jump threading a
   // branch can create other opportunities. If these opportunities form a cycle
   // i.e. if any jump threading is undoing previous threading in the path, then
   // we will loop forever. We take care of this issue by not jump threading for
   // back edges. This works for normal cases but not for unreachable blocks as
   // they may have cycle with no back edge.
   bool EverChanged = false;
-  EverChanged |= removeUnreachableBlocks(F, LVI);
-
+  EverChanged |= removeUnreachableBlocks(F, LVI, DT);
   FindLoopHeaders(F);
 
   bool Changed;
   do {
     Changed = false;
     for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
       BasicBlock *BB = &*I;
       // Thread all of the branches we can over this block.
for (Function::iterator I = F.begin(), E = F.end(); I != E;) {
           // If the terminator is the only non-phi instruction, try to nuke it.
           BB->getFirstNonPHIOrDbg()->isTerminator() && !LoopHeaders.count(BB) &&
           !LoopHeaders.count(BI->getSuccessor(0))) {
         // FIXME: It is always conservatively correct to drop the info
         // for a block even if it doesn't get erased.  This isn't totally
         // awesome, but it allows us to use AssertingVH to prevent nasty
         // dangling pointer issues within LazyValueInfo.
         LVI->eraseBlock(BB);
-        if (TryToSimplifyUncondBranchFromEmptyBlock(BB))
+        if (TryToSimplifyUncondBranchFromEmptyBlock(BB, DT))
           Changed = true;
       }
     }
     EverChanged |= Changed;
   } while (Changed);
 
   LoopHeaders.clear();
   return EverChanged;
if (BasicBlock *SinglePred = BB->getSinglePredecessor()) {
     const TerminatorInst *TI = SinglePred->getTerminator();
     if (!TI->isExceptional() && TI->getNumSuccessors() == 1 &&
         SinglePred != BB && !hasAddressTakenAndUsed(BB)) {
       // If SinglePred was a loop header, BB becomes one.
       if (LoopHeaders.erase(SinglePred))
         LoopHeaders.insert(BB);
 
       LVI->eraseBlock(SinglePred);
-      MergeBasicBlockIntoOnlyPred(BB);
+      MergeBasicBlockIntoOnlyPred(BB, DT);
 
       // Now that BB is merged into SinglePred (i.e. SinglePred Code followed by
       // BB code within one basic block `BB`), we need to invalidate the LVI
       // information associated with BB, because the LVI information need not be
       // true for all of BB after the merge. For example,
       // Before the merge, LVI info and code is as follows:
       // SinglePred: <LVI info1 for %p val>
       // %y = use of %p
if (SimpleVal) {
       Condition = SimpleVal;
     }
   }
 
   // If the terminator is branching on an undef, we can pick any of the
   // successors to branch to.  Let GetBestDestForJumpOnUndef decide.
   if (isa<UndefValue>(Condition)) {
     unsigned BestSucc = GetBestDestForJumpOnUndef(BB);
+    std::vector<DominatorTree::UpdateType> Updates;
 
     // Fold the branch/switch.
     TerminatorInst *BBTerm = BB->getTerminator();
     for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
       if (i == BestSucc) continue;
-      BBTerm->getSuccessor(i)->removePredecessor(BB, true);
+      BasicBlock *Succ = BBTerm->getSuccessor(i);
+      Succ->removePredecessor(BB, true);
+      if (Succ == BB)
+        continue;
+      DominatorTree::UpdateType UT = {DominatorTree::Delete, BB, Succ};
+      // Make sure to remove a DT edge exactly once and not an edge to itself.
+      if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end())
+        Updates.push_back(UT);
     }
 
     DEBUG(dbgs() << "  In block '" << BB->getName()
           << "' folding undef terminator: " << *BBTerm << '\n');
     BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);
     BBTerm->eraseFromParent();
+    DT->applyUpdates(Updates);
     return true;
   }
 
   // If the terminator of this block is branching on a constant, simplify the
   // terminator to an unconditional branch.  This can occur due to threading in
   // other blocks.
   if (getKnownConstant(Condition, Preference)) {
     DEBUG(dbgs() << "  In block '" << BB->getName()
           << "' folding terminator: " << *BB->getTerminator() << '\n');
     ++NumFolds;
-    ConstantFoldTerminator(BB, true);
+    ConstantFoldTerminator(BB, true, nullptr, DT);
     return true;
   }
 
   Instruction *CondInst = dyn_cast<Instruction>(Condition);
 
   // All the rest of our checks depend on the condition being an instruction.
   if (!CondInst) {
     // FIXME: Unify this with code below.
if (CondBr && CondConst) {
       assert(CondBr->isConditional() && "Threading on unconditional terminator");
 
       LazyValueInfo::Tristate Ret =
         LVI->getPredicateAt(CondCmp->getPredicate(), CondCmp->getOperand(0),
                             CondConst, CondBr);
       if (Ret != LazyValueInfo::Unknown) {
         unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0;
         unsigned ToKeep = Ret == LazyValueInfo::True ? 0 : 1;
-        CondBr->getSuccessor(ToRemove)->removePredecessor(BB, true);
+        BasicBlock *ToRemoveSucc = CondBr->getSuccessor(ToRemove);
+        ToRemoveSucc->removePredecessor(BB, true);
         BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr);
         CondBr->eraseFromParent();
+        if (BB != ToRemoveSucc)
+          DT->deleteEdge(BB, ToRemoveSucc);
         if (CondCmp->use_empty())
           CondCmp->eraseFromParent();
         // We can safely replace *some* uses of the CondInst if it has
         // exactly one value as returned by LVI. RAUW is incorrect in the
         // presence of guards and assumes, that have the `Cond` as the use. This
         // is because we use the guards/assume to reason about the `Cond` value
         // at the end of block, but RAUW unconditionally replaces all uses
         // including the guards/assumes themselves and the uses before the
if (!PBI || !PBI->isConditional())
       return false;
     if (PBI->getSuccessor(0) != CurrentBB && PBI->getSuccessor(1) != CurrentBB)
       return false;
 
     bool CondIsTrue = PBI->getSuccessor(0) == CurrentBB;
     Optional<bool> Implication =
         isImpliedCondition(PBI->getCondition(), Cond, DL, CondIsTrue);
     if (Implication) {
-      BI->getSuccessor(*Implication ? 1 : 0)->removePredecessor(BB);
+      BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
+      RemoveSucc->removePredecessor(BB);
       BranchInst::Create(BI->getSuccessor(*Implication ? 0 : 1), BI);
       BI->eraseFromParent();
+      if (BB != RemoveSucc)
+        DT->deleteEdge(BB, RemoveSucc);
       return true;
     }
     CurrentBB = CurrentPred;
     CurrentPred = CurrentBB->getSinglePredecessor();
   }
 
   return false;
 }
if (PredToDestList.empty())
     return false;
 
   // If all the predecessors go to a single known successor, we want to fold,
   // not thread. By doing so, we do not need to duplicate the current block and
   // also miss potential opportunities in case we dont/cant duplicate.
   if (OnlyDest && OnlyDest != MultipleDestSentinel) {
     if (PredWithKnownDest ==
         (size_t)std::distance(pred_begin(BB), pred_end(BB))) {
+      std::vector<DominatorTree::UpdateType> Updates;
       bool SeenFirstBranchToOnlyDest = false;
       for (BasicBlock *SuccBB : successors(BB)) {
-        if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest)
+        if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
           SeenFirstBranchToOnlyDest = true; // Don't modify the first branch.
-        else
+        } else {
           SuccBB->removePredecessor(BB, true); // This is unreachable successor.
+          if (SuccBB != OnlyDest && SuccBB != BB) {
+            DominatorTree::UpdateType UT = {DominatorTree::Delete, BB, SuccBB};
+            // Make sure to remove a DT edge exactly once.
+            if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end())
+              Updates.push_back(UT);
+          }
+        }
       }
 
       // Finally update the terminator.
       TerminatorInst *Term = BB->getTerminator();
       BranchInst::Create(OnlyDest, Term);
       Term->eraseFromParent();
+      DT->applyUpdates(Updates);
 
       // If the condition is now dead due to the removal of the old terminator,
       // erase it.
       if (auto *CondInst = dyn_cast<Instruction>(Cond)) {
         if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
           CondInst->eraseFromParent();
         // We can safely replace *some* uses of the CondInst if it has
         // exactly one value as returned by LVI. RAUW is incorrect in the
for (Use &U : I.uses()) {
       if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
         if (UserPN->getIncomingBlock(U) == BB)
           continue;
       } else if (User->getParent() == BB)
         continue;
 
       UsesToRename.push_back(&U);
     }
-
     // If there are no uses outside the block, we're done with this instruction.
     if (UsesToRename.empty())
       continue;
 
     DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n");
 
     // We found a use of I outside of BB.  Rename all uses of I that are outside
     // its block to be uses of the appropriate PHI node etc.  See ValuesInBlocks
bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
   // us to simplify any PHI nodes in BB.
   TerminatorInst *PredTerm = PredBB->getTerminator();
   for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
     if (PredTerm->getSuccessor(i) == BB) {
       BB->removePredecessor(PredBB, true);
       PredTerm->setSuccessor(i, NewBB);
     }
 
+  DT->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB},
+                    {DominatorTree::Insert, PredBB, NewBB},
+                    {DominatorTree::Delete, PredBB, BB}});
+
   // At this point, the IR is fully up to date and consistent.  Do a quick scan
   // over the new instructions and zap any that are constants or dead.  This
   // frequently happens because of phi translation.
   SimplifyInstructionsInBlock(NewBB, TLI);
 
   // Update the edge weight from BB to SuccBB, which should be less than before.
   UpdateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB);
 
BasicBlock *JumpThreadingPass::SplitBlockPreds(BasicBlock *BB,
                                                const char *Suffix) {
   // Collect the frequencies of all predecessors of BB, which will be used to
   // update the edge weight on BB->SuccBB.
   BlockFrequency PredBBFreq(0);
   if (HasProfileData)
     for (auto Pred : Preds)
       PredBBFreq += BFI->getBlockFreq(Pred) * BPI->getEdgeProbability(Pred, BB);
 
-  BasicBlock *PredBB = SplitBlockPredecessors(BB, Preds, Suffix);
+  BasicBlock *PredBB = SplitBlockPredecessors(BB, Preds, Suffix, DT);
 
   // Set the block frequency of the newly created PredBB, which is the sum of
   // frequencies of Preds.
   if (HasProfileData)
     BFI->setBlockFreq(PredBB, PredBBFreq.getFrequency());
   return PredBB;
 }
 
DEBUG(dbgs() << "  Duplicating block '" << BB->getName() << "' into end of '"
         << PredBB->getName() << "' to eliminate branch on phi.  Cost: "
         << DuplicationCost << " block is:" << *BB << "\n");
 
   // Unless PredBB ends with an unconditional branch, split the edge so that we
   // can just clone the bits from BB into the end of the new PredBB.
   BranchInst *OldPredBranch = dyn_cast<BranchInst>(PredBB->getTerminator());
 
   if (!OldPredBranch || !OldPredBranch->isUnconditional()) {
-    PredBB = SplitEdge(PredBB, BB);
+    PredBB = SplitEdge(PredBB, BB, DT);
     OldPredBranch = cast<BranchInst>(PredBB->getTerminator());
   }
 
   // We are going to have to map operands from the original BB block into the
   // PredBB block.  Evaluate PHI nodes in BB.
   DenseMap<Instruction*, Value*> ValueMapping;
 
   BasicBlock::iterator BI = BB->begin();
bool JumpThreadingPass::DuplicateCondBranchOnPHIIntoPred(
   }
 
   // PredBB no longer jumps to BB, remove entries in the PHI node for the edge
   // that we nuked.
   BB->removePredecessor(PredBB, true);
 
   // Remove the unconditional branch at the end of the PredBB block.
   OldPredBranch->eraseFromParent();
+  if (BB != PredBB)
+    DT->deleteEdge(PredBB, BB);
 
   ++NumDupes;
   return true;
 }
 
 /// TryToUnfoldSelect - Look for blocks of the form
 /// bb1:
 ///   %a = select
if ((LHSFolds != LazyValueInfo::Unknown ||
       //  |-----
       //  v
       // BB
       BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold",
                                              BB->getParent(), BB);
       // Move the unconditional branch to NewBB.
       PredTerm->removeFromParent();
       NewBB->getInstList().insert(NewBB->end(), PredTerm);
+      DT->insertEdge(NewBB, BB);
       // Create a conditional branch and update PHI nodes.
       BranchInst::Create(NewBB, BB, SI->getCondition(), Pred);
       CondLHS->setIncomingValue(I, SI->getFalseValue());
       CondLHS->addIncoming(SI->getTrueValue(), NewBB);
       // The select is now dead.
       SI->eraseFromParent();
 
+      DT->insertEdge(Pred, NewBB);
       // Update any other PHI nodes in BB.
       for (BasicBlock::iterator BI = BB->begin();
            PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
         if (Phi != CondLHS)
           Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
       return true;
     }
   }
for (Use &U : PN->uses()) {
         }
       }
     }
 
     if (!SI)
       continue;
     // Expand the select.
     TerminatorInst *Term =
-        SplitBlockAndInsertIfThen(SI->getCondition(), SI, false);
+        SplitBlockAndInsertIfThen(SI->getCondition(), SI, false, nullptr, DT);
     PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI);
     NewPN->addIncoming(SI->getTrueValue(), Term->getParent());
     NewPN->addIncoming(SI->getFalseValue(), BB);
     SI->replaceAllUsesWith(NewPN);
     SI->eraseFromParent();
     return true;
   }
   return false;
else {
     Impl = isImpliedCondition(BranchCond, GuardCond, DL, /* LHSIsTrue */ false);
     if (Impl && *Impl)
       FalseDestIsSafe = true;
   }
 
   if (!TrueDestIsSafe && !FalseDestIsSafe)
     return false;
 
-  BasicBlock *UnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
-  BasicBlock *GuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;
+  BasicBlock *PredUnguardedBlock = TrueDestIsSafe ? TrueDest : FalseDest;
+  BasicBlock *PredGuardedBlock = FalseDestIsSafe ? TrueDest : FalseDest;
 
   ValueToValueMapTy UnguardedMapping, GuardedMapping;
   Instruction *AfterGuard = Guard->getNextNode();
   unsigned Cost = getJumpThreadDuplicationCost(BB, AfterGuard, BBDupThreshold);
   if (Cost > BBDupThreshold)
     return false;
   // Duplicate all instructions before the guard and the guard itself to the
   // branch where implication is not proved.
-  GuardedBlock = DuplicateInstructionsInSplitBetween(
-      BB, GuardedBlock, AfterGuard, GuardedMapping);
+  BasicBlock *GuardedBlock = DuplicateInstructionsInSplitBetween(
+      BB, PredGuardedBlock, AfterGuard, GuardedMapping);
   assert(GuardedBlock && "Could not create the guarded block?");
   // Duplicate all instructions before the guard in the unguarded branch.
   // Since we have successfully duplicated the guarded block and this block
   // has fewer instructions, we expect it to succeed.
-  UnguardedBlock = DuplicateInstructionsInSplitBetween(BB, UnguardedBlock,
-                                                       Guard, UnguardedMapping);
+  BasicBlock *UnguardedBlock = DuplicateInstructionsInSplitBetween(
+      BB, PredUnguardedBlock, Guard, UnguardedMapping);
   assert(UnguardedBlock && "Could not create the unguarded block?");
   DEBUG(dbgs() << "Moved guard " << *Guard << " to block "
                << GuardedBlock->getName() << "\n");
+  // DuplicateInstructionsInSplitBetween inserts a new block, BB.split, between
+  // PredBB and BB. We need to perform two inserts and one delete in DT for each
+  // of the above calls.
+  DT->applyUpdates({// Guarded block split.
+                    {DominatorTree::Delete, PredGuardedBlock, BB},
+                    {DominatorTree::Insert, PredGuardedBlock, GuardedBlock},
+                    {DominatorTree::Insert, GuardedBlock, BB},
+                    // Unguarded block split.
+                    {DominatorTree::Delete, PredUnguardedBlock, BB},
+                    {DominatorTree::Insert, PredUnguardedBlock, UnguardedBlock},
+                    {DominatorTree::Insert, UnguardedBlock, BB}});
 
   // Some instructions before the guard may still have uses. For them, we need
   // to create Phi nodes merging their copies in both guarded and unguarded
   // branches. Those instructions that have no uses can be just removed.
   SmallVector<Instruction *, 4> ToRemove;
   for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI)
     if (!isa<PHINode>(&*BI))
       ToRemove.push_back(&*BI);

llvm/trunk/lib/Transforms/Utils/Local.cpp

 /// ConstantFoldTerminator - If a terminator instruction is predicated on a
 /// constant value, convert it into an unconditional branch to the constant
 /// destination.  This is a nontrivial operation because the successors of this
 /// basic block must have their PHI nodes updated.
 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
 /// conditions and indirectbr addresses this might make dead if
 /// DeleteDeadConditions is true.
 bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
-                                  const TargetLibraryInfo *TLI) {
+                                  const TargetLibraryInfo *TLI,
+                                  DominatorTree *DT) {
   TerminatorInst *T = BB->getTerminator();
   IRBuilder<> Builder(T);
 
   // Branch - See if we are conditional jumping on constant
   if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
     BasicBlock *Dest1 = BI->getSuccessor(0);
     BasicBlock *Dest2 = BI->getSuccessor(1);
if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
 
       // Let the basic block know that we are letting go of it.  Based on this,
       // it will adjust it's PHI nodes.
       OldDest->removePredecessor(BB);
 
       // Replace the conditional branch with an unconditional one.
       Builder.CreateBr(Destination);
       BI->eraseFromParent();
+      if (DT && OldDest != Destination && OldDest != BB)
+        DT->deleteEdge(BB, OldDest);
       return true;
     }
 
     if (Dest2 == Dest1) {       // Conditional branch to same location?
       // This branch matches something like this:
       //     br bool %cond, label %Dest, label %Dest
       // and changes it into:  br label %Dest
 
for (auto i = SI->case_begin(), e = SI->case_end(); i != e;) {
           // Remove weight for this case.
           std::swap(Weights[idx+1], Weights.back());
           Weights.pop_back();
           SI->setMetadata(LLVMContext::MD_prof,
                           MDBuilder(BB->getContext()).
                           createBranchWeights(Weights));
         }
         // Remove this entry.
-        DefaultDest->removePredecessor(SI->getParent());
+        BasicBlock *ParentBB = SI->getParent();
+        DefaultDest->removePredecessor(ParentBB);
         i = SI->removeCase(i);
         e = SI->case_end();
+        if (DT && DefaultDest != ParentBB) {
+          // DefaultDest may still be a successor of a non-default case.
+          if (none_of(successors(ParentBB), [DefaultDest](BasicBlock *S) {
+                return S == DefaultDest;
+              }))
+            DT->deleteEdge(ParentBB, DefaultDest);
+        }
         continue;
       }
 
       // Otherwise, check to see if the switch only branches to one destination.
       // We do this by reseting "TheOnlyDest" to null when we find two non-equal
       // destinations.
       if (i->getCaseSuccessor() != TheOnlyDest)
         TheOnlyDest = nullptr;
if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
     }
 
     // If we found a single destination that we can fold the switch into, do so
     // now.
     if (TheOnlyDest) {
       // Insert the new branch.
       Builder.CreateBr(TheOnlyDest);
       BasicBlock *BB = SI->getParent();
+      BasicBlock *TheOnlyDestCheck = TheOnlyDest;
+      std::vector<DominatorTree::UpdateType> Updates;
 
       // Remove entries from PHI nodes which we no longer branch to...
       for (BasicBlock *Succ : SI->successors()) {
         // Found case matching a constant operand?
-        if (Succ == TheOnlyDest)
+        if (Succ == TheOnlyDest) {
           TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest
-        else
+        } else {
           Succ->removePredecessor(BB);
+          if (DT && Succ != TheOnlyDestCheck && Succ != BB) {
+            DominatorTree::UpdateType UT = {DominatorTree::Delete, BB, Succ};
+            if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end())
+              Updates.push_back(UT);
+          }
+        }
       }
 
       // Delete the old switch.
       Value *Cond = SI->getCondition();
       SI->eraseFromParent();
+      if (DT && !Updates.empty())
+        DT->applyUpdates(Updates);
       if (DeleteDeadConditions)
         RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
       return true;
     }
 
     if (SI->getNumCases() == 1) {
       // Otherwise, we can fold this switch into a conditional branch
       // instruction if it has only one non-default destination.
if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
     return false;
   }
 
   if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) {
     // indirectbr blockaddress(@F, @BB) -> br label @BB
     if (BlockAddress *BA =
           dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
       BasicBlock *TheOnlyDest = BA->getBasicBlock();
+      BasicBlock *TheOnlyDestCheck = TheOnlyDest;
+      std::vector<DominatorTree::UpdateType> Updates;
       // Insert the new branch.
       Builder.CreateBr(TheOnlyDest);
 
       for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
-        if (IBI->getDestination(i) == TheOnlyDest)
+        if (IBI->getDestination(i) == TheOnlyDest) {
           TheOnlyDest = nullptr;
-        else
-          IBI->getDestination(i)->removePredecessor(IBI->getParent());
+        } else {
+          BasicBlock *ParentBB = IBI->getParent();
+          BasicBlock *DestBB = IBI->getDestination(i);
+          DestBB->removePredecessor(ParentBB);
+          if (DT && DestBB != TheOnlyDestCheck && DestBB != ParentBB) {
+            DominatorTree::UpdateType UT = {DominatorTree::Delete, ParentBB,
+                                            DestBB};
+            if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end())
+              Updates.push_back(UT);
+          }
+        }
       }
       Value *Address = IBI->getAddress();
       IBI->eraseFromParent();
+      if (DT && !Updates.empty())
+        DT->applyUpdates(Updates);
       if (DeleteDeadConditions)
         RecursivelyDeleteTriviallyDeadInstructions(Address, TLI);
 
       // If we didn't find our destination in the IBI successor list, then we
       // have undefined behavior.  Replace the unconditional branch with an
       // 'unreachable' instruction.
       if (TheOnlyDest) {
         BB->getTerminator()->eraseFromParent();

 ///
 /// Unlike the removePredecessor method, this attempts to simplify uses of PHI
 /// nodes that collapse into identity values.  For example, if we have:
 ///   x = phi(1, 0, 0, 0)
 ///   y = and x, z
 ///
 /// .. and delete the predecessor corresponding to the '1', this will attempt to
 /// recursively fold the and to 0.
-void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred) {
+void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred,
+                                        DominatorTree *DT) {
   // This only adjusts blocks with PHI nodes.
   if (!isa<PHINode>(BB->begin()))
     return;
 
   // Remove the entries for Pred from the PHI nodes in BB, but do not simplify
   // them down.  This will leave us with single entry phi nodes and other phis
   // that can be removed.
   BB->removePredecessor(Pred, true);
 
   WeakTrackingVH PhiIt = &BB->front();
   while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) {
     PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt));
     Value *OldPhiIt = PhiIt;
 
     if (!recursivelySimplifyInstruction(PN))
       continue;
 
     // If recursive simplification ended up deleting the next PHI node we would
     // iterate to, then our iterator is invalid, restart scanning from the top
     // of the block.
     if (PhiIt != OldPhiIt) PhiIt = &BB->front();
   }
+  if (DT && BB != Pred)
+    DT->deleteEdge(Pred, BB);
 }
 
 
 /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
 /// predecessor is known to have one successor (DestBB!).  Eliminate the edge
 /// between them, moving the instructions in the predecessor into DestBB and
 /// deleting the predecessor block.
 ///
 void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, DominatorTree *DT) {
   // If BB has single-entry PHI nodes, fold them.
   while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
     Value *NewVal = PN->getIncomingValue(0);
     // Replace self referencing PHI with undef, it must be dead.
     if (NewVal == PN) NewVal = UndefValue::get(PN->getType());
     PN->replaceAllUsesWith(NewVal);
     PN->eraseFromParent();
   }
 
   BasicBlock *PredBB = DestBB->getSinglePredecessor();
   assert(PredBB && "Block doesn't have a single predecessor!");
 
+  // Collect all the edges that enter PredBB, discarding edges to itself and
+  // duplicates. These dominator edges will be redirected to DestBB.
+  std::vector<DominatorTree::UpdateType> Updates;
+  if (DT)
+    for (pred_iterator PI = pred_begin(PredBB), E = pred_end(PredBB); PI != E;
+         ++PI) {
+      if (*PI == PredBB)
+        continue;
+      DominatorTree::UpdateType UT = {DominatorTree::Delete, *PI, PredBB};
+      if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end()) {
+        Updates.push_back(UT);
+        // DestBB cannot dominate itself.
+        if (*PI != DestBB)
+          Updates.push_back({DominatorTree::Insert, *PI, DestBB});
+      }
+    }
+
   // Zap anything that took the address of DestBB.  Not doing this will give the
   // address an invalid value.
   if (DestBB->hasAddressTaken()) {
     BlockAddress *BA = BlockAddress::get(DestBB);
     Constant *Replacement =
       ConstantInt::get(llvm::Type::getInt32Ty(BA->getContext()), 1);
     BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
                                                      BA->getType()));
     BA->destroyConstant();
   }
 
   // Anything that branched to PredBB now branches to DestBB.
   PredBB->replaceAllUsesWith(DestBB);
 
   // Splice all the instructions from PredBB to DestBB.
   PredBB->getTerminator()->eraseFromParent();
   DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
 
   // If the PredBB is the entry block of the function, move DestBB up to
   // become the entry block after we erase PredBB.
-  if (PredBB == &DestBB->getParent()->getEntryBlock())
+  bool ReplacedEntryBB = false;
+  if (PredBB == &DestBB->getParent()->getEntryBlock()) {
     DestBB->moveAfter(PredBB);
+    ReplacedEntryBB = true;
+  }
 
-  if (DT) {
-    BasicBlock *PredBBIDom = DT->getNode(PredBB)->getIDom()->getBlock();
-    DT->changeImmediateDominator(DestBB, PredBBIDom);
-    DT->eraseNode(PredBB);
+  if (DT && !ReplacedEntryBB) {
+    Updates.push_back({DominatorTree::Delete, PredBB, DestBB});
+    DT->applyUpdates(Updates);
   }
+
   // Nuke BB.
   PredBB->eraseFromParent();
+
+  // The entry block was removed and there is no external interface for the
+  // dominator tree to be notified of this change. In this corner-case we
+  // recalculate the entire tree.
+  if (DT && ReplacedEntryBB)
+    DT->recalculate(*(DestBB->getParent()));
 }
 
 /// CanMergeValues - Return true if we can choose one of these values to use
 /// in place of the other. Note that we will always choose the non-undef
 /// value to keep.
 static bool CanMergeValues(Value *First, Value *Second) {
   return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);
 }
static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB,
   replaceUndefValuesInPhi(PN, IncomingValues);
 }
 
 /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an
 /// unconditional branch, and contains no instructions other than PHI nodes,
 /// potential side-effect free intrinsics and the branch.  If possible,
 /// eliminate BB by rewriting all the predecessors to branch to the successor
 /// block and return true.  If we can't transform, return false.
-bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) {
+bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
+                                                   DominatorTree *DT) {
   assert(BB != &BB->getParent()->getEntryBlock() &&
          "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
 
   // We can't eliminate infinite loops.
   BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
   if (BB == Succ) return false;
 
   // Check to see if merging these blocks would cause conflicts for any of the
while (isa<PHINode>(*BBI)) {
         }
       }
       ++BBI;
     }
   }
 
   DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
 
+  // Collect all the edges that enter BB, discarding edges to itself and
+  // duplicates. These dominator edges will be redirected to Succ.
+  std::vector<DominatorTree::UpdateType> Updates;
+  if (DT)
+    for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+      if (*PI == BB)
+        continue;
+      DominatorTree::UpdateType UT = {DominatorTree::Delete, *PI, BB};
+      if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end()) {
+        Updates.push_back(UT);
+        Updates.push_back({DominatorTree::Insert, *PI, Succ});
+      }
+    }
+
   if (isa<PHINode>(Succ->begin())) {
     // If there is more than one pred of succ, and there are PHI nodes in
     // the successor, then we need to add incoming edges for the PHI nodes
     //
     const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB));
 
     // Loop over all of the PHI nodes in the successor of BB.
     for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
       PN->eraseFromParent();
     }
   }
 
   // If the unconditional branch we replaced contains llvm.loop metadata, we
   // add the metadata to the branch instructions in the predecessors.
   unsigned LoopMDKind = BB->getContext().getMDKindID("llvm.loop");
   Instruction *TI = BB->getTerminator();
-  if (TI)
+  if (TI) {
     if (MDNode *LoopMD = TI->getMetadata(LoopMDKind))
       for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
         BasicBlock *Pred = *PI;
         Pred->getTerminator()->setMetadata(LoopMDKind, LoopMD);
       }
+    // Replace the terminator instruction with unreachable to ensure the CFG is
+    // consistent. This is necessary for dominance to be correctly calculated.
+    new UnreachableInst(BB->getContext(), TI);
+    TI->eraseFromParent();
+  }
 
   // Everything that jumped to BB now goes to Succ.
   BB->replaceAllUsesWith(Succ);
   if (!Succ->hasName()) Succ->takeName(BB);
+
+  if (DT) {
+    Updates.push_back({DominatorTree::Delete, BB, Succ});
+    DT->applyUpdates(Updates);
+  }
+
   BB->eraseFromParent();              // Delete the old basic block.
   return true;
 }
 
 /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI
 /// nodes in this block. This doesn't try to be clever about PHI nodes
 /// which differ only in the order of the incoming values, but instcombine
 /// orders them so it usually won't matter.
while (EndInst != &BB->front()) {
     if (!isa<DbgInfoIntrinsic>(Inst))
       ++NumDeadInst;
     Inst->eraseFromParent();
   }
   return NumDeadInst;
 }
 
 unsigned llvm::changeToUnreachable(Instruction *I, bool UseLLVMTrap,
-                                   bool PreserveLCSSA) {
+                                   bool PreserveLCSSA, DominatorTree *DT) {
   BasicBlock *BB = I->getParent();
+  std::vector<DominatorTree::UpdateType> Updates;
   // Loop over all of the successors, removing BB's entry from any PHI
   // nodes.
-  for (BasicBlock *Successor : successors(BB))
+  for (BasicBlock *Successor : successors(BB)) {
     Successor->removePredecessor(BB, PreserveLCSSA);
-
+    if (DT && BB != Successor) {
+      DominatorTree::UpdateType UT = {DominatorTree::Delete, BB, Successor};
+      if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end())
+        Updates.push_back(UT);
+    }
+  }
   // Insert a call to llvm.trap right before this.  This turns the undefined
   // behavior into a hard fail instead of falling through into random code.
   if (UseLLVMTrap) {
     Function *TrapFn =
       Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);
     CallInst *CallTrap = CallInst::Create(TrapFn, "", I);
     CallTrap->setDebugLoc(I->getDebugLoc());
   }
   new UnreachableInst(I->getContext(), I);
 
   // All instructions after this are dead.
   unsigned NumInstrsRemoved = 0;
   BasicBlock::iterator BBI = I->getIterator(), BBE = BB->end();
   while (BBI != BBE) {
     if (!BBI->use_empty())
       BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
     BB->getInstList().erase(BBI++);
     ++NumInstrsRemoved;
   }
+  if (DT && !Updates.empty())
+    DT->applyUpdates(Updates);
   return NumInstrsRemoved;
 }
 
 /// changeToCall - Convert the specified invoke into a normal call.
-static void changeToCall(InvokeInst *II) {
+static void changeToCall(InvokeInst *II, DominatorTree *DT = nullptr) {
   SmallVector<Value*, 8> Args(II->arg_begin(), II->arg_end());
   SmallVector<OperandBundleDef, 1> OpBundles;
   II->getOperandBundlesAsDefs(OpBundles);
   CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, OpBundles,
                                        "", II);
   NewCall->takeName(II);
   NewCall->setCallingConv(II->getCallingConv());
   NewCall->setAttributes(II->getAttributes());
   NewCall->setDebugLoc(II->getDebugLoc());
   II->replaceAllUsesWith(NewCall);
 
   // Follow the call by a branch to the normal destination.
-  BranchInst::Create(II->getNormalDest(), II);
+  BasicBlock *NormalDestBB = II->getNormalDest();
+  BranchInst::Create(NormalDestBB, II);
 
   // Update PHI nodes in the unwind destination
-  II->getUnwindDest()->removePredecessor(II->getParent());
+  BasicBlock *BB = II->getParent();
+  BasicBlock *UnwindDestBB = II->getUnwindDest();
+  UnwindDestBB->removePredecessor(BB);
   II->eraseFromParent();
+  if (DT && BB != UnwindDestBB && NormalDestBB != UnwindDestBB)
+    DT->deleteEdge(BB, UnwindDestBB);
 }
 
 BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
                                                    BasicBlock *UnwindEdge) {
   BasicBlock *BB = CI->getParent();
 
   // Convert this function call into an invoke instruction.  First, split the
   // basic block.
BasicBlock *llvm::changeToInvokeAndSplitBasicBlock(CallInst *CI,
   CI->replaceAllUsesWith(II);
 
   // Delete the original call
   Split->getInstList().pop_front();
   return Split;
 }
 
 static bool markAliveBlocks(Function &F,
-                            SmallPtrSetImpl<BasicBlock*> &Reachable) {
+                            SmallPtrSetImpl<BasicBlock *> &Reachable,
+                            DominatorTree *DT = nullptr) {
 
   SmallVector<BasicBlock*, 128> Worklist;
   BasicBlock *BB = &F.front();
   Worklist.push_back(BB);
   Reachable.insert(BB);
   bool Changed = false;
   do {
     BB = Worklist.pop_back_val();
 
     // Do a quick scan of the basic block, turning any obviously unreachable
     // instructions into LLVM unreachable insts.  The instruction combining pass
     // canonicalizes unreachable insts into stores to null or undef.
     for (Instruction &I : *BB) {
       // Assumptions that are known to be false are equivalent to unreachable.
       // Also, if the condition is undefined, then we make the choice most
       // beneficial to the optimizer, and choose that to also be unreachable.
       if (auto *II = dyn_cast<IntrinsicInst>(&I)) {
         if (II->getIntrinsicID() == Intrinsic::assume) {
           if (match(II->getArgOperand(0), m_CombineOr(m_Zero(), m_Undef()))) {
             // Don't insert a call to llvm.trap right before the unreachable.
-            changeToUnreachable(II, false);
+            changeToUnreachable(II, false, false, DT);
             Changed = true;
             break;
           }
         }
 
         if (II->getIntrinsicID() == Intrinsic::experimental_guard) {
           // A call to the guard intrinsic bails out of the current compilation
           // unit if the predicate passed to it is false.  If the predicate is a
           // constant false, then we know the guard will bail out of the current
           // compile unconditionally, so all code following it is dead.
           //
           // Note: unlike in llvm.assume, it is not "obviously profitable" for
           // guards to treat `undef` as `false` since a guard on `undef` can
           // still be useful for widening.
           if (match(II->getArgOperand(0), m_Zero()))
             if (!isa<UnreachableInst>(II->getNextNode())) {
-              changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/ false);
+              changeToUnreachable(II->getNextNode(), /*UseLLVMTrap=*/false,
+                                  false, DT);
               Changed = true;
               break;
             }
         }
       }
 
       if (auto *CI = dyn_cast<CallInst>(&I)) {
         Value *Callee = CI->getCalledValue();
         if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
-          changeToUnreachable(CI, /*UseLLVMTrap=*/false);
+          changeToUnreachable(CI, /*UseLLVMTrap=*/false, false, DT);
           Changed = true;
           break;
         }
         if (CI->doesNotReturn()) {
           // If we found a call to a no-return function, insert an unreachable
           // instruction after it.  Make sure there isn't *already* one there
           // though.
           if (!isa<UnreachableInst>(CI->getNextNode())) {
             // Don't insert a call to llvm.trap right before the unreachable.
-            changeToUnreachable(CI->getNextNode(), false);
+            changeToUnreachable(CI->getNextNode(), false, false, DT);
             Changed = true;
           }
           break;
         }
       }
 
       // Store to undef and store to null are undefined and used to signal that
       // they should be changed to unreachable by passes that can't modify the
       // CFG.
       if (auto *SI = dyn_cast<StoreInst>(&I)) {
         // Don't touch volatile stores.
         if (SI->isVolatile()) continue;
 
         Value *Ptr = SI->getOperand(1);
 
         if (isa<UndefValue>(Ptr) ||
             (isa<ConstantPointerNull>(Ptr) &&
              SI->getPointerAddressSpace() == 0)) {
-          changeToUnreachable(SI, true);
+          changeToUnreachable(SI, true, false, DT);
           Changed = true;
           break;
         }
       }
     }
 
     TerminatorInst *Terminator = BB->getTerminator();
     if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
       // Turn invokes that call 'nounwind' functions into ordinary calls.
       Value *Callee = II->getCalledValue();
       if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
-        changeToUnreachable(II, true);
+        changeToUnreachable(II, true, false, DT);
         Changed = true;
       } else if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(&F)) {
         if (II->use_empty() && II->onlyReadsMemory()) {
           // jump to the normal destination branch.
+          BasicBlock *UnwindDestBB = II->getUnwindDest();
           BranchInst::Create(II->getNormalDest(), II);
-          II->getUnwindDest()->removePredecessor(II->getParent());
+          UnwindDestBB->removePredecessor(II->getParent());
           II->eraseFromParent();
+          if (DT && BB != UnwindDestBB)
+            DT->deleteEdge(BB, UnwindDestBB);
         } else
-          changeToCall(II);
+          changeToCall(II, DT);
         Changed = true;
       }
     } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Terminator)) {
       // Remove catchpads which cannot be reached.
       struct CatchPadDenseMapInfo {
         static CatchPadInst *getEmptyKey() {
           return DenseMapInfo<CatchPadInst *>::getEmptyKey();
         }
if (auto *II = dyn_cast<InvokeInst>(Terminator)) {
           CatchSwitch->removeHandler(I);
           --I;
           --E;
           Changed = true;
         }
       }
     }
 
-    Changed |= ConstantFoldTerminator(BB, true);
+    Changed |= ConstantFoldTerminator(BB, true, nullptr, DT);
     for (BasicBlock *Successor : successors(BB))
       if (Reachable.insert(Successor).second)
         Worklist.push_back(Successor);
   } while (!Worklist.empty());
   return Changed;
 }
 
-void llvm::removeUnwindEdge(BasicBlock *BB) {
+void llvm::removeUnwindEdge(BasicBlock *BB, DominatorTree *DT) {
   TerminatorInst *TI = BB->getTerminator();
 
   if (auto *II = dyn_cast<InvokeInst>(TI)) {
-    changeToCall(II);
+    changeToCall(II, DT);
     return;
   }
 
   TerminatorInst *NewTI;
   BasicBlock *UnwindDest;
 
   if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
     NewTI = CleanupReturnInst::Create(CRI->getCleanupPad(), nullptr, CRI);
if (auto *CRI = dyn_cast<CleanupReturnInst>(TI)) {
     llvm_unreachable("Could not find unwind successor");
   }
 
   NewTI->takeName(TI);
   NewTI->setDebugLoc(TI->getDebugLoc());
   UnwindDest->removePredecessor(BB);
   TI->replaceAllUsesWith(NewTI);
   TI->eraseFromParent();
+  if (DT && BB != UnwindDest)
+    DT->deleteEdge(BB, UnwindDest);
 }
 
 /// removeUnreachableBlocks - Remove blocks that are not reachable, even
 /// if they are in a dead cycle.  Return true if a change was made, false
 /// otherwise. If `LVI` is passed, this function preserves LazyValueInfo
 /// after modifying the CFG.
-bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI) {
+bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI,
+                                   DominatorTree *DT) {
   SmallPtrSet<BasicBlock*, 16> Reachable;
-  bool Changed = markAliveBlocks(F, Reachable);
+  bool Changed = markAliveBlocks(F, Reachable, DT);
+  std::vector<DominatorTree::UpdateType> Updates;
 
   // If there are unreachable blocks in the CFG...
   if (Reachable.size() == F.size())
     return Changed;
 
   assert(Reachable.size() < F.size());
   NumRemoved += F.size()-Reachable.size();
 
+  SmallPtrSet<TerminatorInst *, 4> TIRemoved;
+
   // Loop over all of the basic blocks that are not reachable, dropping all of
   // their internal references...
   for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) {
     if (Reachable.count(&*BB))
       continue;
 
     for (BasicBlock *Successor : successors(&*BB))
-      if (Reachable.count(Successor))
+      if (Reachable.count(Successor)) {
         Successor->removePredecessor(&*BB);
+        if (DT && &*BB != Successor) {
+          DominatorTree::UpdateType UT = {DominatorTree::Delete, &*BB,
+                                          Successor};
+          if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end())
+            Updates.push_back(UT);
+        }
+      }
+
     if (LVI)
       LVI->eraseBlock(&*BB);
+
+    TerminatorInst *TI = BB->getTerminator();
+    TIRemoved.insert(TI);
+    new UnreachableInst(BB->getContext(), TI);
+
     BB->dropAllReferences();
   }
 
+  // Remove all the terminator instructions after dropping all references. This
+  // keeps the state of the CFG consistent and prevents asserts from circular
+  // use counts in groups of unreachable basic blocks.
+  for (TerminatorInst *TI : TIRemoved)
+    TI->eraseFromParent();
+
+  if (DT && !Updates.empty())
+    DT->applyUpdates(Updates);
+
   for (Function::iterator I = ++F.begin(); I != F.end();)
     if (!Reachable.count(&*I))
       I = F.getBasicBlockList().erase(I);
     else
       ++I;
 
   return true;
 }

llvm/trunk/test/Analysis/LazyValueAnalysis/lvi-after-jumpthreading.ll

 ; CHECK-NEXT:    ; LatticeVal for: 'i32 %a' is: overdefined
 ; CHECK-NEXT:    ; LatticeVal for: 'i32 %length' is: overdefined
   br label %loop
 
 ; CHECK-LABEL: backedge:
 ; CHECK-NEXT:     ; LatticeVal for: 'i32 %a' is: overdefined
 ; CHECK-NEXT:     ; LatticeVal for: 'i32 %length' is: overdefined
 ; CHECK-NEXT:     ; LatticeVal for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%backedge' is: constantrange<0, 400>
+; CHECK-NEXT:     ; LatticeVal for: '  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]' in BB: '%exit' is: constantrange<399, 400>
 ; CHECK-NEXT:  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
 ; CHECK-NEXT:     ; LatticeVal for: '  %iv.next = add nsw i32 %iv, 1' in BB: '%backedge' is: constantrange<1, 401>
+; CHECK-NEXT:     ; LatticeVal for: '  %iv.next = add nsw i32 %iv, 1' in BB: '%exit' is: constantrange<400, 401>
 ; CHECK-NEXT:  %iv.next = add nsw i32 %iv, 1
 ; CHECK-NEXT:     ; LatticeVal for: '  %cont = icmp slt i32 %iv.next, 400' in BB: '%backedge' is: overdefined
+; CHECK-NEXT:     ; LatticeVal for: '  %cont = icmp slt i32 %iv.next, 400' in BB: '%exit' is: constantrange<0, -1>
 ; CHECK-NEXT:  %cont = icmp slt i32 %iv.next, 400
 ; CHECK-NOT: loop
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %backedge]
   %cnd = icmp sge i32 %iv, 0
   br i1 %cnd, label %backedge, label %exit
 
 backedge: