Index: llvm/lib/CodeGen/CodeGenPrepare.cpp
===================================================================
--- llvm/lib/CodeGen/CodeGenPrepare.cpp
+++ llvm/lib/CodeGen/CodeGenPrepare.cpp
@@ -388,9 +388,9 @@
     bool tryToSinkFreeOperands(Instruction *I);
     bool replaceMathCmpWithIntrinsic(BinaryOperator *BO, CmpInst *Cmp,
                                      Intrinsic::ID IID);
-    bool optimizeCmp(CmpInst *Cmp, bool &ModifiedDT);
-    bool combineToUSubWithOverflow(CmpInst *Cmp, bool &ModifiedDT);
-    bool combineToUAddWithOverflow(CmpInst *Cmp, bool &ModifiedDT);
+    bool optimizeCmp(CmpInst *Cmp);
+    bool combineToUSubWithOverflow(CmpInst *Cmp);
+    bool combineToUAddWithOverflow(CmpInst *Cmp);
   };
 
 } // end anonymous namespace
@@ -484,9 +484,13 @@
     if (!LargeOffsetGEPMap.empty())
       MadeChange |= splitLargeGEPOffsets();
 
-    // Really free removed instructions during promotion.
-    for (Instruction *I : RemovedInsts)
+    // Really free instructions removed during promotion or kept around to
+    // improve efficiency (see comments in overflow intrinsic transforms).
+    for (Instruction *I : RemovedInsts) {
+      if (I->getParent())
+        I->removeFromParent();
       I->deleteValue();
+    }
 
     EverMadeChange |= MadeChange;
     SeenChainsForSExt.clear();
@@ -1221,10 +1225,14 @@
   Value *MathOV = Builder.CreateBinaryIntrinsic(IID, Arg0, Arg1);
   Value *Math = Builder.CreateExtractValue(MathOV, 0, "math");
   Value *OV = Builder.CreateExtractValue(MathOV, 1, "ov");
+
+  // Delay the actual removal/deletion of the binop and compare for efficiency.
+  // If we delete those now, we would invalidate the instruction iterator and
+  // trigger dominator tree updates.
   BO->replaceAllUsesWith(Math);
   Cmp->replaceAllUsesWith(OV);
-  BO->eraseFromParent();
-  Cmp->eraseFromParent();
+  RemovedInsts.insert(BO);
+  RemovedInsts.insert(Cmp);
   return true;
 }
 
@@ -1260,8 +1268,7 @@
 
 /// Try to combine the compare into a call to the llvm.uadd.with.overflow
 /// intrinsic. Return true if any changes were made.
-bool CodeGenPrepare::combineToUAddWithOverflow(CmpInst *Cmp,
-                                               bool &ModifiedDT) {
+bool CodeGenPrepare::combineToUAddWithOverflow(CmpInst *Cmp) {
   Value *A, *B;
   BinaryOperator *Add;
   if (!match(Cmp, m_UAddWithOverflow(m_Value(A), m_Value(B), m_BinOp(Add))))
@@ -1281,13 +1288,10 @@
   if (!replaceMathCmpWithIntrinsic(Add, Cmp, Intrinsic::uadd_with_overflow))
     return false;
 
-  // Reset callers - do not crash by iterating over a dead instruction.
-  ModifiedDT = true;
   return true;
 }
 
-bool CodeGenPrepare::combineToUSubWithOverflow(CmpInst *Cmp,
-                                               bool &ModifiedDT) {
+bool CodeGenPrepare::combineToUSubWithOverflow(CmpInst *Cmp) {
   // We are not expecting non-canonical/degenerate code. Just bail out.
   Value *A = Cmp->getOperand(0), *B = Cmp->getOperand(1);
   if (isa<Constant>(A) && isa<Constant>(B))
@@ -1342,8 +1346,6 @@
   if (!replaceMathCmpWithIntrinsic(Sub, Cmp, Intrinsic::usub_with_overflow))
     return false;
 
-  // Reset callers - do not crash by iterating over a dead instruction.
-  ModifiedDT = true;
   return true;
 }
 
@@ -1413,14 +1415,14 @@
   return MadeChange;
 }
 
-bool CodeGenPrepare::optimizeCmp(CmpInst *Cmp, bool &ModifiedDT) {
+bool CodeGenPrepare::optimizeCmp(CmpInst *Cmp) {
   if (sinkCmpExpression(Cmp, *TLI))
     return true;
 
-  if (combineToUAddWithOverflow(Cmp, ModifiedDT))
+  if (combineToUAddWithOverflow(Cmp))
     return true;
 
-  if (combineToUSubWithOverflow(Cmp, ModifiedDT))
+  if (combineToUSubWithOverflow(Cmp))
     return true;
 
   return false;
@@ -6945,7 +6947,7 @@
   }
 
   if (auto *Cmp = dyn_cast<CmpInst>(I))
-    if (TLI && optimizeCmp(Cmp, ModifiedDT))
+    if (TLI && optimizeCmp(Cmp))
       return true;
 
   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {