Index: include/llvm/CodeGen/MachineBasicBlock.h
===================================================================
--- include/llvm/CodeGen/MachineBasicBlock.h
+++ include/llvm/CodeGen/MachineBasicBlock.h
@@ -461,12 +461,18 @@
 
   /// Remove successor from the successors list of this MachineBasicBlock. The
   /// Predecessors list of Succ is automatically updated.
-  void removeSuccessor(MachineBasicBlock *Succ);
+  /// If NormalizeSuccProbs is true, then normalize successors' probabilities
+  /// after the successor is removed.
+  void removeSuccessor(MachineBasicBlock *Succ,
+                       bool NormalizeSuccProbs = false);
 
   /// Remove specified successor from the successors list of this
   /// MachineBasicBlock. The Predecessors list of Succ is automatically updated.
+  /// If NormalizeSuccProbs is true, then normalize successors' probabilities
+  /// after the successor is removed.
   /// Return the iterator to the element after the one removed.
-  succ_iterator removeSuccessor(succ_iterator I);
+  succ_iterator removeSuccessor(succ_iterator I,
+                                bool NormalizeSuccProbs = false);
 
   /// Replace successor OLD with NEW and update probability info.
   void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New);
Index: lib/CodeGen/EarlyIfConversion.cpp
===================================================================
--- lib/CodeGen/EarlyIfConversion.cpp
+++ lib/CodeGen/EarlyIfConversion.cpp
@@ -538,11 +538,11 @@
 
   // Fix up the CFG, temporarily leave Head without any successors.
   Head->removeSuccessor(TBB);
-  Head->removeSuccessor(FBB);
+  Head->removeSuccessor(FBB, true);
   if (TBB != Tail)
-    TBB->removeSuccessor(Tail);
+    TBB->removeSuccessor(Tail, true);
   if (FBB != Tail)
-    FBB->removeSuccessor(Tail);
+    FBB->removeSuccessor(Tail, true);
 
   // Fix up Head's terminators.
   // It should become a single branch or a fallthrough.
Index: lib/CodeGen/IfConversion.cpp
===================================================================
--- lib/CodeGen/IfConversion.cpp
+++ lib/CodeGen/IfConversion.cpp
@@ -1113,7 +1113,7 @@
 
     // RemoveExtraEdges won't work if the block has an unanalyzable branch, so
     // explicitly remove CvtBBI as a successor.
-    BBI.BB->removeSuccessor(CvtBBI->BB);
+    BBI.BB->removeSuccessor(CvtBBI->BB, true);
   } else {
     RemoveKills(CvtBBI->BB->begin(), CvtBBI->BB->end(), DontKill, *TRI);
     PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond);
@@ -1226,7 +1226,7 @@
 
     // RemoveExtraEdges won't work if the block has an unanalyzable branch, so
     // explicitly remove CvtBBI as a successor.
-    BBI.BB->removeSuccessor(CvtBBI->BB);
+    BBI.BB->removeSuccessor(CvtBBI->BB, true);
   } else {
     // Predicate the 'true' block after removing its branch.
     CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB);
@@ -1260,6 +1260,7 @@
     auto NewFalse = BBCvt * CvtFalse;
     TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, nullptr, RevCond, dl);
     BBI.BB->addSuccessor(CvtBBI->FalseBB, NewFalse);
+    BBI.BB->normalizeSuccProbs();
   }
 
   // Merge in the 'false' block if the 'false' block has no other
@@ -1512,7 +1513,7 @@
   // which can happen here if TailBB is unanalyzable and is merged, so
   // explicitly remove BBI1 and BBI2 as successors.
   BBI.BB->removeSuccessor(BBI1->BB);
-  BBI.BB->removeSuccessor(BBI2->BB);
+  BBI.BB->removeSuccessor(BBI2->BB, true);
   RemoveExtraEdges(BBI);
 
   // Update block info.
@@ -1749,6 +1750,9 @@
   if (NBB && !FromBBI.BB->isSuccessor(NBB))
     FromBBI.BB->addSuccessor(NBB);
 
+  ToBBI.BB->normalizeSuccProbs();
+  FromBBI.BB->normalizeSuccProbs();
+
   ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
   FromBBI.Predicate.clear();
 
Index: lib/CodeGen/MachineBasicBlock.cpp
===================================================================
--- lib/CodeGen/MachineBasicBlock.cpp
+++ lib/CodeGen/MachineBasicBlock.cpp
@@ -525,13 +525,14 @@
   Succ->addPredecessor(this);
 }
 
-void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ) {
+void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ,
+                                        bool NormalizeSuccProbs) {
   succ_iterator I = std::find(Successors.begin(), Successors.end(), Succ);
-  removeSuccessor(I);
+  removeSuccessor(I, NormalizeSuccProbs);
 }
 
 MachineBasicBlock::succ_iterator
-MachineBasicBlock::removeSuccessor(succ_iterator I) {
+MachineBasicBlock::removeSuccessor(succ_iterator I, bool NormalizeSuccProbs) {
   assert(I != Successors.end() && "Not a current successor!");
 
   // If probability list is empty it means we don't use it (disabled
@@ -539,6 +540,8 @@
   if (!Probs.empty()) {
     probability_iterator WI = getProbabilityIterator(I);
     Probs.erase(WI);
+    if (NormalizeSuccProbs)
+      normalizeSuccProbs();
   }
 
   (*I)->removePredecessor(this);
@@ -636,6 +639,7 @@
           MO.setMBB(this);
       }
   }
+  normalizeSuccProbs();
 }
 
 bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const {
@@ -1088,6 +1092,8 @@
     }
   }
 
+  if (Changed)
+    normalizeSuccProbs();
   return Changed;
 }
 
Index: lib/CodeGen/TailDuplication.cpp
===================================================================
--- lib/CodeGen/TailDuplication.cpp
+++ lib/CodeGen/TailDuplication.cpp
@@ -751,6 +751,7 @@
     assert(NumSuccessors <= 1);
     if (NumSuccessors == 0 || *PredBB->succ_begin() != NewTarget)
       PredBB->addSuccessor(NewTarget, Prob);
+    PredBB->normalizeSuccProbs();
 
     TDBBs.push_back(PredBB);
   }
@@ -859,6 +860,7 @@
     for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(),
            E = TailBB->succ_end(); I != E; ++I)
       PredBB->addSuccessor(*I, MBPI->getEdgeProbability(TailBB, I));
+    PredBB->normalizeSuccProbs();
 
     Changed = true;
     ++NumTailDups;
Index: lib/Target/AArch64/AArch64ConditionalCompares.cpp
===================================================================
--- lib/Target/AArch64/AArch64ConditionalCompares.cpp
+++ lib/Target/AArch64/AArch64ConditionalCompares.cpp
@@ -567,8 +567,8 @@
   // All CmpBB instructions are moved into Head, and CmpBB is deleted.
   // Update the CFG first.
   updateTailPHIs();
-  Head->removeSuccessor(CmpBB);
-  CmpBB->removeSuccessor(Tail);
+  Head->removeSuccessor(CmpBB, true);
+  CmpBB->removeSuccessor(Tail, true);
   Head->transferSuccessorsAndUpdatePHIs(CmpBB);
   DebugLoc TermDL = Head->getFirstTerminator()->getDebugLoc();
   TII->RemoveBranch(*Head);
Index: lib/Target/AMDGPU/AMDILCFGStructurizer.cpp
===================================================================
--- lib/Target/AMDGPU/AMDILCFGStructurizer.cpp
+++ lib/Target/AMDGPU/AMDILCFGStructurizer.cpp
@@ -1164,7 +1164,7 @@
 
   for (SmallVectorImpl<MachineBasicBlock *>::iterator It = ContMBB.begin(),
       E = ContMBB.end(); It != E; ++It) {
-    (*It)->removeSuccessor(LoopHeader);
+    (*It)->removeSuccessor(LoopHeader, true);
   }
 
   numLoopcontPatternMatch += NumCont;
@@ -1487,7 +1487,7 @@
   );
   DstMBB->splice(DstMBB->end(), SrcMBB, SrcMBB->begin(), SrcMBB->end());
 
-  DstMBB->removeSuccessor(SrcMBB);
+  DstMBB->removeSuccessor(SrcMBB, true);
   cloneSuccessorList(DstMBB, SrcMBB);
 
   removeSuccessor(SrcMBB);
@@ -1537,9 +1537,9 @@
 
   if (TrueMBB) {
     MBB->splice(I, TrueMBB, TrueMBB->begin(), TrueMBB->end());
-    MBB->removeSuccessor(TrueMBB);
+    MBB->removeSuccessor(TrueMBB, true);
     if (LandMBB && TrueMBB->succ_size()!=0)
-      TrueMBB->removeSuccessor(LandMBB);
+      TrueMBB->removeSuccessor(LandMBB, true);
     retireBlock(TrueMBB);
     MLI->removeBlock(TrueMBB);
   }
@@ -1548,9 +1548,9 @@
     insertInstrBefore(I, AMDGPU::ELSE);
     MBB->splice(I, FalseMBB, FalseMBB->begin(),
                    FalseMBB->end());
-    MBB->removeSuccessor(FalseMBB);
+    MBB->removeSuccessor(FalseMBB, true);
     if (LandMBB && FalseMBB->succ_size() != 0)
-      FalseMBB->removeSuccessor(LandMBB);
+      FalseMBB->removeSuccessor(LandMBB, true);
     retireBlock(FalseMBB);
     MLI->removeBlock(FalseMBB);
   }
@@ -1591,7 +1591,7 @@
   //now branchInst can be erase safely
   BranchMI->eraseFromParent();
   //now take care of successors, retire blocks
-  ExitingMBB->removeSuccessor(LandMBB);
+  ExitingMBB->removeSuccessor(LandMBB, true);
 }
 
 void AMDGPUCFGStructurizer::settleLoopcontBlock(MachineBasicBlock *ContingMBB,
@@ -1757,7 +1757,7 @@
   DEBUG(dbgs() << "Removing unneeded cond branch instr: " << *BranchMI);
   BranchMI->eraseFromParent();
   SHOWNEWBLK(MBB1, "Removing redundant successor");
-  MBB->removeSuccessor(MBB1);
+  MBB->removeSuccessor(MBB1, true);
 }
 
 void AMDGPUCFGStructurizer::addDummyExitBlock(
Index: lib/Target/ARM/ARMISelLowering.cpp
===================================================================
--- lib/Target/ARM/ARMISelLowering.cpp
+++ lib/Target/ARM/ARMISelLowering.cpp
@@ -7402,6 +7402,7 @@
     }
 
     BB->addSuccessor(DispatchBB, BranchProbability::getZero());
+    BB->normalizeSuccProbs();
 
     // Find the invoke call and mark all of the callee-saved registers as
     // 'implicit defined' so that they're spilled. This prevents code from
Index: lib/Target/Hexagon/HexagonEarlyIfConv.cpp
===================================================================
--- lib/Target/Hexagon/HexagonEarlyIfConv.cpp
+++ lib/Target/Hexagon/HexagonEarlyIfConv.cpp
@@ -939,7 +939,7 @@
     B->removeSuccessor(B->succ_begin());
 
   for (auto I = B->pred_begin(), E = B->pred_end(); I != E; ++I)
-    (*I)->removeSuccessor(B);
+    (*I)->removeSuccessor(B, true);
 
   Deleted.insert(B);
   MDT->eraseNode(B);
@@ -1001,6 +1001,7 @@
   MachineBasicBlock::succ_iterator I, E = SuccB->succ_end();
   for (I = SuccB->succ_begin(); I != E; ++I)
     PredB->addSuccessor(*I);
+  PredB->normalizeSuccProbs();
   replacePhiEdges(SuccB, PredB);
   removeBlock(SuccB);
   if (!TermOk)
Index: lib/Target/Mips/MipsLongBranch.cpp
===================================================================
--- lib/Target/Mips/MipsLongBranch.cpp
+++ lib/Target/Mips/MipsLongBranch.cpp
@@ -148,7 +148,7 @@
   // Insert NewMBB and fix control flow.
   MachineBasicBlock *Tgt = getTargetMBB(*FirstBr);
   NewMBB->transferSuccessors(MBB);
-  NewMBB->removeSuccessor(Tgt);
+  NewMBB->removeSuccessor(Tgt, true);
   MBB->addSuccessor(NewMBB);
   MBB->addSuccessor(Tgt);
   MF->insert(std::next(MachineFunction::iterator(MBB)), NewMBB);
Index: lib/Target/PowerPC/PPCEarlyReturn.cpp
===================================================================
--- lib/Target/PowerPC/PPCEarlyReturn.cpp
+++ lib/Target/PowerPC/PPCEarlyReturn.cpp
@@ -153,7 +153,7 @@
       }
 
       for (unsigned i = 0, ie = PredToRemove.size(); i != ie; ++i)
-        PredToRemove[i]->removeSuccessor(&ReturnMBB);
+        PredToRemove[i]->removeSuccessor(&ReturnMBB, true);
 
       if (Changed && !ReturnMBB.hasAddressTaken()) {
         // We now might be able to merge this blr-only block into its
@@ -163,7 +163,7 @@
           if (PrevMBB.isLayoutSuccessor(&ReturnMBB) && PrevMBB.canFallThrough()) {
             // Move the blr into the preceding block.
             PrevMBB.splice(PrevMBB.end(), &ReturnMBB, I);
-            PrevMBB.removeSuccessor(&ReturnMBB);
+            PrevMBB.removeSuccessor(&ReturnMBB, true);
           }
         }