There seems to be a fundamental problem in SimplifyCFG: Dead code removal can result in uninitialized variables. The impact is an “endless” loop which can be considered the consequence of searching for the initialization. More details are...

[Gerolf]

Summary

...below.

The proposed patch fixes the problem by eliminating *all* blocks dominated by a
block that has become unreachable. This requires dominance information. The
upside is that using dominance will also allow cleaning up code in SimplifyCFG
that computes “local” dominance eg. DominatesMergePoint(). The potential
downside is an increase in compile time, which I’m still collecting data on.
Anecdotally I hear the argument that computing dominance is expensive. I’m
curious if anyone has specifics about this Theoretically dominance is computed
by a linear run O(CFG), except when the CFG is irreducible (which should be
rare). In that case Tarjan gives an almost linear algorithm. So I would not
expect a material compile-time impact from it.

The patch also externs SimplifyCFG to indicate when more than one block is
delated, so the caller can take care of the stale iterator problem when
necessary.

More details:

The actual endless loop is in the constant compare gather() routine in
Utils/SimplifyCFG.cpp. The same value ret.0.off0.i is pushed back into the
queue:
%.ret.0.off0.i = or i1 %.ret.0.off0.i, %cmp10.i

Here is what happens at the IR level:

for.cond.i: ; preds = %if.end6.i,
%if.end.i54
%ix.0.i = phi i32 [ 0, %if.end.i54 ], [ %inc.i55, %if.end6.i ]
%ret.0.off0.i = phi i1 [false, %if.end.i54], [%.ret.0.off0.i, %if.end6.i] <<<
%cmp2.i = icmp ult i32 %ix.0.i, %11
br i1 %cmp2.i, label %for.body.i, label %LBJ_TmpSimpleNeedExt.exit

if.end6.i: ; preds = %for.body.i
%cmp10.i = icmp ugt i32 %conv.i, %add9.i
%.ret.0.off0.i = or i1 %ret.0.off0.i, %cmp10.i <<<

When if.end.i54 gets eliminated which removes the definition of ret.0.off0.i.
The result is the expression %.ret.0.off0.i = or i1 %.ret.0.off0.i, %cmp10.i
(Note the first ‘or’ operand is now %.ret.0.off0.i, and *NOT* %ret.0.off0.i). And
now there is use of .ret.0.off0.i before a definition which triggers the
“endless” loop in gather():

while(!DFT.empty()) {

V = DFT.pop_back_val();   // V is .ret.0.off0.i

if (Instruction *I = dyn_cast<Instruction>(V)) {
  // If it is a || (or && depending on isEQ), process the operands.
  if (I->getOpcode() == (isEQ ? Instruction::Or : Instruction::And)) {
    DFT.push_back(I->getOperand(1));  // This is now .ret.0.off0.i also
    DFT.push_back(I->getOperand(0));

    continue; // “endless loop” for .ret.0.off0.i
  }

[SimplifyCFG] Fix for "endless" loop after dead code removal

[reames]

I strongly suspect this patch is incorrect as written. I don't have a particular counter example, but there are many places in SimplifyCFG that modify the CFG in ways that effect dominance information and I don't see enough updates in SimplifyCFG to account for that.

I would suggest focusing on the infinite loop you addressed rather than trying to make SimplifyCFG preserve dominator tree. I haven't studied the code you mentioned is at fault, but the standard visited set idiom or another approach for stopping infinite recursion seems likely to be much easier to implement.

If you want to go down that route, I'd suggest separating a separate patch series which teaches SimplifyCFG to preserve dominator tree info through all of the updates. I'll warn you this is going to be a good amount of work though! You'll probably want a on demand mechanism to force recalc within the pass and then go through each transform one at a time to reduce recalcs.

[Gerolf]

Philip, the code does not claim it preserves the dominator tree. Nor does it need to.

The reason why I think the code is correct although SImplifyCFG may modify the cfg is that
a) blocks only get removed when dominance has been computed for them
b) any block that is dominated by an unreachable block can be removed also (by definition)
c) if there is an new block introduce that is dominated by an unreachable block but dominance is missing the unreachable block will still be removed. Then the new block will be removed later in the SimplifyCFGPass loop.. So there is no change from the behavior of the existing code.

The only problematic scenario I can think of is that a) a new block is inserted and b) a block with an initialization becomes unreachable and is removed. Clearly there is no dominance info and thus a block with the PHI node (for.cond.i in the example) would not be removed which could then result in that endless loop. But in this scenario there needs to be a definition from the new block which then avoids the issue.

I was mostly concerned about compile-time, but my data from the LLVM test suite and benchmark (SPEC 2000, 2006 etc) also shows a few small improvements (likely in the noise) on x86 O3:
Performance Improvements - Execution Time Δ Previous Current σ
SingleSource/Benchmarks/Polybench/linear-algebra/kernels/syrk/syrk -2.69% 2.1296 2.0724 0.0179
MultiSource/Benchmarks/TSVC/CrossingThresholds-dbl/CrossingThresholds-dbl -2.04% 2.9327 2.8728 0.0222
SingleSource/Benchmarks/Polybench/linear-algebra/kernels/syr2k/syr2k -1.75% 3.4523 3.3920 0.0173
MultiSource/Benchmarks/TSVC/CrossingThresholds-flt/CrossingThresholds-flt -1.64% 2.1694 2.1339 0.0083
MultiSource/Benchmarks/TSVC/Packing-dbl/Packing-dbl -1.56% 2.9577 2.9115 0.0175
SingleSource/Benchmarks/Misc-C++/Large/ray -1.18% 1.7727 1.7517 0.0009

Could you give this patch a second thought? Thanks!

[ahatanak]

Is the code still correct when the pass removes an edge entering a loop with two entries?

For example, if we initially have a CFG like this which has a loop (BB1,BB2),

BB0-->BB1<-->BB2<--BB3

BB0:
v0 = a
BB1:
v1 = phi(v0, v3)
...
BB2:
v2 = phi(v1, v4)
v3 = v2 + 1
...
BB3:
v4 = b

BB1 doesn't dominate BB2 because the loop has two entries from BB0 and BB3.

However, if simplifycfg is able to remove edge (BB3->BB2), (BB1,BB2) becomes a single entry loop with header BB1.

BB0:
v0 = a
BB1:
v1 = phi(v0, v3)
...
BB2:
v3 = v1 + 1
...

If simplifycfg is able to remove edge BB0->BB1, then you'll get

BB1:
...
BB2:
v3 = v3 + 1
...

[ahatanak]

Regardless of whether this is a valid counter example, I feel that using a stale dominance information to remove unreachable blocks is a little fragile. Is it possible to incrementally update the dominance information when the CFG is transformed? I guess we have to make sure it doesn't have a huge impact on compile time, but I think there are efficient ways to do it if we can identify the dominator tree nodes that are affected and don't have to update the dominator tree for the whole CFG?

[Gerolf]

Thank you Akira and Philip. I agree with your concerns that using a stale dominator information could at some end up in a situation where the current implementation might not prevent a similar bug. For now I provided a simpler fix for the endless loop problem in http://reviews.llvm.org/D16839. Please take a look at that. In case there is a more systemic problem in SimplifyCFG that requires dominance in this scenario I think the best approach is to compute all blocks dominated by a block B on the fly. This can be done for example in 3 passes over all blocks reachable from B.

include/llvm/Transforms/Utils/Local.h

 
 /// SimplifyCFG - This function is used to do simplification of a CFG.  For
 /// example, it adjusts branches to branches to eliminate the extra hop, it
 /// eliminates unreachable basic blocks, and does other "peephole" optimization
 /// of the CFG.  It returns true if a modification was made, possibly deleting
 /// the basic block that was pointed to.
 ///
 bool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
-                 unsigned BonusInstThreshold, AssumptionCache *AC = nullptr);
+                 unsigned BonusInstThreshold, AssumptionCache *AC = nullptr,
+                 DominatorTree *DT = nullptr, bool *RemovedManyBB = nullptr);
 
 /// FlatternCFG - This function is used to flatten a CFG.  For
 /// example, it uses parallel-and and parallel-or mode to collapse
 //  if-conditions and merge if-regions with identical statements.
 ///
 bool FlattenCFG(BasicBlock *BB, AliasAnalysis *AA = nullptr);
 
 /// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch,

lib/Transforms/Scalar/SimplifyCFGPass.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Scalar.h"
 using namespace llvm;
static bool mergeEmptyReturnBlocks(Function &F) {
 
   return Changed;
 }
 
 /// Call SimplifyCFG on all the blocks in the function,
 /// iterating until no more changes are made.
 static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
                                    AssumptionCache *AC,
-                                   unsigned BonusInstThreshold) {
+                                   unsigned BonusInstThreshold,
+                                   DominatorTree *DT = nullptr) {
   bool Changed = false;
   bool LocalChange = true;
   while (LocalChange) {
     LocalChange = false;
 
     // Loop over all of the basic blocks and remove them if they are unneeded.
     for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
-      if (SimplifyCFG(&*BBIt++, TTI, BonusInstThreshold, AC)) {
+      bool ResetBBIt = false;
+      // ResetBBIt is true when more than one block is removed by SimplifyCFG
+      // and the iterator could be stale.
+      if (SimplifyCFG(&*BBIt++, TTI, BonusInstThreshold, AC, DT, &ResetBBIt)) {
         LocalChange = true;
+        if (ResetBBIt)
+          break;
         ++NumSimpl;
       }
     }
     Changed |= LocalChange;
   }
   return Changed;
 }
 
 static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI,
-                                AssumptionCache *AC, int BonusInstThreshold) {
+                                AssumptionCache *AC, int BonusInstThreshold,
+                                DominatorTree *DT = nullptr) {
   bool EverChanged = removeUnreachableBlocks(F);
   EverChanged |= mergeEmptyReturnBlocks(F);
-  EverChanged |= iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold);
+  EverChanged |= iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold, DT);
 
   // If neither pass changed anything, we're done.
   if (!EverChanged) return false;
 
   // iterativelySimplifyCFG can (rarely) make some loops dead.  If this happens,
   // removeUnreachableBlocks is needed to nuke them, which means we should
   // iterate between the two optimizations.  We structure the code like this to
   // avoid rerunning iterativelySimplifyCFG if the second pass of
   // removeUnreachableBlocks doesn't do anything.
   if (!removeUnreachableBlocks(F))
     return true;
 
   do {
-    EverChanged = iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold);
+    EverChanged = iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold, DT);
     EverChanged |= removeUnreachableBlocks(F);
   } while (EverChanged);
 
   return true;
 }
 
 SimplifyCFGPass::SimplifyCFGPass()
     : BonusInstThreshold(UserBonusInstThreshold) {}
PreservedAnalyses SimplifyCFGPass::run(Function &F,
 
   return PreservedAnalyses::all();
 }
 
 namespace {
 struct CFGSimplifyPass : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
   unsigned BonusInstThreshold;
+  DominatorTree *DT;
   std::function<bool(const Function &)> PredicateFtor;
 
   CFGSimplifyPass(int T = -1,
                   std::function<bool(const Function &)> Ftor = nullptr)
       : FunctionPass(ID), PredicateFtor(Ftor) {
     BonusInstThreshold = (T == -1) ? UserBonusInstThreshold : unsigned(T);
     initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
   }
   bool runOnFunction(Function &F) override {
     if (PredicateFtor && !PredicateFtor(F))
       return false;
 
     if (skipOptnoneFunction(F))
       return false;
 
     AssumptionCache *AC =
         &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     const TargetTransformInfo &TTI =
         getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
-    return simplifyFunctionCFG(F, TTI, AC, BonusInstThreshold);
+    DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    return simplifyFunctionCFG(F, TTI, AC, BonusInstThreshold, DT);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
+    AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
   }
 };
 }
 
 char CFGSimplifyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false,
                     false)
 
 // Public interface to the CFGSimplification pass
 FunctionPass *
 llvm::createCFGSimplificationPass(int Threshold,
                                   std::function<bool(const Function &)> Ftor) {
   return new CFGSimplifyPass(Threshold, Ftor);
 }

lib/Transforms/Utils/SimplifyCFG.cpp

struct ValueEqualityComparisonCase {
     bool operator==(BasicBlock *RHSDest) const { return Dest == RHSDest; }
   };
 
 class SimplifyCFGOpt {
   const TargetTransformInfo &TTI;
   const DataLayout &DL;
   unsigned BonusInstThreshold;
   AssumptionCache *AC;
+  DominatorTree *DT;
+  // Indicator for the iterator problem: when more than one
+  // block is removed an iterator over all blocks in a function
+  // could be stale. In this case the variable is set to true.
+  bool *RemovedManyBB;
   Value *isValueEqualityComparison(TerminatorInst *TI);
   BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI,
                                std::vector<ValueEqualityComparisonCase> &Cases);
   bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI,
                                                      BasicBlock *Pred,
                                                      IRBuilder<> &Builder);
   bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
                                            IRBuilder<> &Builder);
 
   bool SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder);
   bool SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder);
   bool SimplifySingleResume(ResumeInst *RI);
   bool SimplifyCommonResume(ResumeInst *RI);
   bool SimplifyCleanupReturn(CleanupReturnInst *RI);
   bool SimplifyUnreachable(UnreachableInst *UI);
   bool SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder);
   bool SimplifyIndirectBr(IndirectBrInst *IBI);
   bool SimplifyUncondBranch(BranchInst *BI, IRBuilder <> &Builder);
   bool SimplifyCondBranch(BranchInst *BI, IRBuilder <>&Builder);
 
 public:
   SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout &DL,
-                 unsigned BonusInstThreshold, AssumptionCache *AC)
-      : TTI(TTI), DL(DL), BonusInstThreshold(BonusInstThreshold), AC(AC) {}
+                 unsigned BonusInstThreshold, AssumptionCache *AC,
+                 DominatorTree *DT = nullptr, bool *RemovedManyBB = nullptr)
+      : TTI(TTI), DL(DL), BonusInstThreshold(BonusInstThreshold), AC(AC),
+        DT(DT), RemovedManyBB(RemovedManyBB) {}
   bool run(BasicBlock *BB);
 };
 }
 
 /// Return true if it is safe to merge these two
 /// terminator instructions together.
 static bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) {
   if (SI1 == SI2) return false;  // Can't merge with self!

 /// end:
 ///   ... = phi i1 [ true, %entry ], [ %tmp, %DEFAULT ], [ true, %entry ]
 ///
 /// We prefer to split the edge to 'end' so that there is a true/false entry to
 /// the PHI, merging the third icmp into the switch.
 static bool TryToSimplifyUncondBranchWithICmpInIt(
     ICmpInst *ICI, IRBuilder<> &Builder, const DataLayout &DL,
     const TargetTransformInfo &TTI, unsigned BonusInstThreshold,
-    AssumptionCache *AC) {
+    AssumptionCache *AC, DominatorTree *DT, bool *RemovedManyBB) {
   BasicBlock *BB = ICI->getParent();
 
   // If the block has any PHIs in it or the icmp has multiple uses, it is too
   // complex.
   if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse()) return false;
 
   Value *V = ICI->getOperand(0);
   ConstantInt *Cst = cast<ConstantInt>(ICI->getOperand(1));
if (SI->getDefaultDest() != BB) {
     assert(VVal && "Should have a unique destination value");
     ICI->setOperand(0, VVal);
 
     if (Value *V = SimplifyInstruction(ICI, DL)) {
       ICI->replaceAllUsesWith(V);
       ICI->eraseFromParent();
     }
     // BB is now empty, so it is likely to simplify away.
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+           true;
   }
 
   // Ok, the block is reachable from the default dest.  If the constant we're
   // comparing exists in one of the other edges, then we can constant fold ICI
   // and zap it.
   if (SI->findCaseValue(Cst) != SI->case_default()) {
     Value *V;
     if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
       V = ConstantInt::getFalse(BB->getContext());
     else
       V = ConstantInt::getTrue(BB->getContext());
 
     ICI->replaceAllUsesWith(V);
     ICI->eraseFromParent();
     // BB is now empty, so it is likely to simplify away.
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+           true;
   }
 
   // The use of the icmp has to be in the 'end' block, by the only PHI node in
   // the block.
   BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0);
   PHINode *PHIUse = dyn_cast<PHINode>(ICI->user_back());
   if (PHIUse == nullptr || PHIUse != &SuccBlock->front() ||
       isa<PHINode>(++BasicBlock::iterator(PHIUse)))

 bool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) {
   BasicBlock *BB = SI->getParent();
 
   if (isValueEqualityComparison(SI)) {
     // If we only have one predecessor, and if it is a branch on this value,
     // see if that predecessor totally determines the outcome of this switch.
     if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
       if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+               true;
 
     Value *Cond = SI->getCondition();
     if (SelectInst *Select = dyn_cast<SelectInst>(Cond))
       if (SimplifySwitchOnSelect(SI, Select))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+               true;
 
     // If the block only contains the switch, see if we can fold the block
     // away into any preds.
     BasicBlock::iterator BBI = BB->begin();
     // Ignore dbg intrinsics.
     while (isa<DbgInfoIntrinsic>(BBI))
       ++BBI;
     if (SI == &*BBI)
       if (FoldValueComparisonIntoPredecessors(SI, Builder))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+               true;
   }
 
   // Try to transform the switch into an icmp and a branch.
   if (TurnSwitchRangeIntoICmp(SI, Builder))
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+           true;
 
   // Remove unreachable cases.
   if (EliminateDeadSwitchCases(SI, AC, DL))
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+           true;
 
   if (SwitchToSelect(SI, Builder, AC, DL))
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+           true;
 
   if (ForwardSwitchConditionToPHI(SI))
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+           true;
 
   if (SwitchToLookupTable(SI, Builder, DL, TTI))
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+           true;
 
   return false;
 }
 
 bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) {
   BasicBlock *BB = IBI->getParent();
   bool Changed = false;
 
if (IBI->getNumDestinations() == 1) {
     // If the indirectbr has one successor, change it to a direct branch.
     BranchInst::Create(IBI->getDestination(0), IBI);
     EraseTerminatorInstAndDCECond(IBI);
     return true;
   }
 
   if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) {
     if (SimplifyIndirectBrOnSelect(IBI, SI))
-      return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+      return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+             true;
   }
   return Changed;
 }
 
 /// Given an block with only a single landing pad and a unconditional branch
 /// try to find another basic block which this one can be merged with.  This
 /// handles cases where we have multiple invokes with unique landing pads, but
 /// a shared handler.
bool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder){
 
   // If the only instruction in the block is a seteq/setne comparison
   // against a constant, try to simplify the block.
   if (ICmpInst *ICI = dyn_cast<ICmpInst>(I))
     if (ICI->isEquality() && isa<ConstantInt>(ICI->getOperand(1))) {
       for (++I; isa<DbgInfoIntrinsic>(I); ++I)
         ;
       if (I->isTerminator() &&
-          TryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, DL, TTI,
-                                                BonusInstThreshold, AC))
+          TryToSimplifyUncondBranchWithICmpInIt(
+              ICI, Builder, DL, TTI, BonusInstThreshold, AC, DT, RemovedManyBB))
         return true;
     }
 
   // See if we can merge an empty landing pad block with another which is
   // equivalent.
   if (LandingPadInst *LPad = dyn_cast<LandingPadInst>(I)) {
     for (++I; isa<DbgInfoIntrinsic>(I); ++I) {}
     if (I->isTerminator() &&
         TryToMergeLandingPad(LPad, BI, BB))
       return true;
   }
 
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // branches to us and our successor, fold the comparison into the
   // predecessor and use logical operations to update the incoming value
   // for PHI nodes in common successor.
   if (FoldBranchToCommonDest(BI, BonusInstThreshold))
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+           true;
   return false;
 }
 
 static BasicBlock *allPredecessorsComeFromSameSource(BasicBlock *BB) {
   BasicBlock *PredPred = nullptr;
   for (auto *P : predecessors(BB)) {
     BasicBlock *PPred = P->getSinglePredecessor();
     if (!PPred || (PredPred && PredPred != PPred))
       return nullptr;
     PredPred = PPred;
   }
   return PredPred;
 }
 
 bool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) {
   BasicBlock *BB = BI->getParent();
 
   // Conditional branch
   if (isValueEqualityComparison(BI)) {
     // If we only have one predecessor, and if it is a branch on this value,
     // see if that predecessor totally determines the outcome of this
     // switch.
     if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
       if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+               true;
 
     // This block must be empty, except for the setcond inst, if it exists.
     // Ignore dbg intrinsics.
     BasicBlock::iterator I = BB->begin();
     // Ignore dbg intrinsics.
     while (isa<DbgInfoIntrinsic>(I))
       ++I;
     if (&*I == BI) {
       if (FoldValueComparisonIntoPredecessors(BI, Builder))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+               true;
     } else if (&*I == cast<Instruction>(BI->getCondition())){
       ++I;
       // Ignore dbg intrinsics.
       while (isa<DbgInfoIntrinsic>(I))
         ++I;
       if (&*I == BI && FoldValueComparisonIntoPredecessors(BI, Builder))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+               true;
     }
   }
 
   // Try to turn "br (X == 0 | X == 1), T, F" into a switch instruction.
   if (SimplifyBranchOnICmpChain(BI, Builder, DL))
     return true;
 
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // branches to us and one of our successors, fold the comparison into the
   // predecessor and use logical operations to pick the right destination.
   if (FoldBranchToCommonDest(BI, BonusInstThreshold))
-    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+           true;
 
   // We have a conditional branch to two blocks that are only reachable
   // from BI.  We know that the condbr dominates the two blocks, so see if
   // there is any identical code in the "then" and "else" blocks.  If so, we
   // can hoist it up to the branching block.
   if (BI->getSuccessor(0)->getSinglePredecessor()) {
     if (BI->getSuccessor(1)->getSinglePredecessor()) {
       if (HoistThenElseCodeToIf(BI, TTI))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+               true;
     } else {
       // If Successor #1 has multiple preds, we may be able to conditionally
       // execute Successor #0 if it branches to Successor #1.
       TerminatorInst *Succ0TI = BI->getSuccessor(0)->getTerminator();
       if (Succ0TI->getNumSuccessors() == 1 &&
           Succ0TI->getSuccessor(0) == BI->getSuccessor(1))
         if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0), TTI))
-          return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+          return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT,
+                             RemovedManyBB) |
+                 true;
     }
   } else if (BI->getSuccessor(1)->getSinglePredecessor()) {
     // If Successor #0 has multiple preds, we may be able to conditionally
     // execute Successor #1 if it branches to Successor #0.
     TerminatorInst *Succ1TI = BI->getSuccessor(1)->getTerminator();
     if (Succ1TI->getNumSuccessors() == 1 &&
         Succ1TI->getSuccessor(0) == BI->getSuccessor(0))
       if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1), TTI))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+               true;
   }
 
   // If this is a branch on a phi node in the current block, thread control
   // through this block if any PHI node entries are constants.
   if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition()))
     if (PN->getParent() == BI->getParent())
       if (FoldCondBranchOnPHI(BI, DL))
-        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+        return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT, RemovedManyBB) |
+               true;
 
   // Scan predecessor blocks for conditional branches.
   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
     if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator()))
       if (PBI != BI && PBI->isConditional())
         if (SimplifyCondBranchToCondBranch(PBI, BI, DL))
-          return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+          return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT,
+                             RemovedManyBB) |
+                 true;
 
   // Look for diamond patterns.
   if (MergeCondStores)
     if (BasicBlock *PrevBB = allPredecessorsComeFromSameSource(BB))
       if (BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
         if (PBI != BI && PBI->isConditional())
           if (mergeConditionalStores(PBI, BI))
-            return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
-  
+            return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, DT,
+                               RemovedManyBB) |
+                   true;
   return false;
 }
 
 /// Check if passing a value to an instruction will cause undefined behavior.
 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) {
   Constant *C = dyn_cast<Constant>(V);
   if (!C)
     return false;
for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
           return true;
         }
         // TODO: SwitchInst.
       }
 
   return false;
 }
 
+// Remove all blocks dominated by BB. When DT is null remove BB only.
+// Return true when more than one block has been removed.
+static uint64_t removeAllBlocksDominated(BasicBlock *BB, DominatorTree *DT) {
+
+  // This is a helper routine for run(). Protect from unintended invocations.
+  assert(((pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) ||
+          BB->getSinglePredecessor() == BB) &&
+         "Invalid BasicBlock \n");
+
+  SmallVector<BasicBlock *, 16> Worklist;
+  SmallVector<BasicBlock *, 16> DominatedBlocks;
+  ;
+  SmallPtrSet<BasicBlock *, 16> Visited;
+
+  BasicBlock *Root = BB;
+  DomTreeNode *DRoot = DT ? DT->getNode(Root) : nullptr;
+  uint64_t Count = 0;
+
+  // Initialize Worklist
+  if (Visited.insert(Root).second) {
+    Worklist.push_back(Root);
+    DominatedBlocks.push_back(Root);
+  }
+
+  // Collect all block dominate by Root (includes Root)
+  // Predecessors of all blocks collected must be
+  // dominated by Root also. This ensures that only
+  // blocks of the original control-flow graph are
+  // considered, and not blocks inserted by SimplifyCFG.
+  // For this reason, dominance must be checked on dominator
+  // nodes rather than just basic blocks.
+  while (!Worklist.empty()) {
+    BasicBlock *SeedBB = Worklist.pop_back_val();
+    for (auto *SuccBB : make_range(succ_begin(SeedBB), succ_end(SeedBB)))
+      if (DT) {
+        DomTreeNode *DSuccBB = DT->getNode(SuccBB);
+        if (DRoot && DSuccBB && DT->dominates(DRoot, DSuccBB)) {
+          bool DominatesAll = true;
+          for (auto *PredBB :
+               make_range(pred_begin(SuccBB), pred_end(SuccBB))) {
+            DomTreeNode *DPredBB = DT->getNode(PredBB);
+            if (!DPredBB || !DT->dominates(DRoot, DPredBB)) {
+              DominatesAll = false;
+              break;
+            }
+          }
+          if (DominatesAll)
+            if (Visited.insert(SuccBB).second) {
+              Worklist.push_back(SuccBB);
+              DominatedBlocks.push_back(SuccBB);
+            }
+        }
+      }
+  }
+  // Remove all block dominated by Root
+  // Note: At least Root is removed here
+  while (!DominatedBlocks.empty()) {
+    BasicBlock *DeleteBB = DominatedBlocks.pop_back_val();
+    if (DeleteBB != Root && !pred_empty(DeleteBB))
+      for (auto *PredBB :
+           make_range(pred_begin(DeleteBB), pred_end(DeleteBB))) {
+        DeleteBB->removePredecessor(PredBB);
+        TerminatorInst *TI = PredBB->getTerminator();
+        if (!TI->use_empty())
+          TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
+        new UnreachableInst(TI->getContext(), TI);
+        TI->eraseFromParent();
+      }
+    Count++;
+    DeleteDeadBlock(DeleteBB);
+  }
+  assert(Count && "Root block not removed!");
+  return Count;
+}
+
 bool SimplifyCFGOpt::run(BasicBlock *BB) {
   bool Changed = false;
 
   assert(BB && BB->getParent() && "Block not embedded in function!");
   assert(BB->getTerminator() && "Degenerate basic block encountered!");
 
-  // Remove basic blocks that have no predecessors (except the entry block)...
+  // Remove basic blocks that have no predecessors (except the entry block)
   // or that just have themself as a predecessor.  These are unreachable.
+  // When DT is available also remove all blocks dominated by that block.
   if ((pred_empty(BB) &&
        BB != &BB->getParent()->getEntryBlock()) ||
       BB->getSinglePredecessor() == BB) {
-    DEBUG(dbgs() << "Removing BB: \n" << *BB);
-    DeleteDeadBlock(BB);
+    uint64_t BlocksRemoved = removeAllBlocksDominated(BB, DT);
+    if (RemovedManyBB)
+      *RemovedManyBB = BlocksRemoved > 1;
     return true;
   }
 
   // Check to see if we can constant propagate this terminator instruction
   // away...
   Changed |= ConstantFoldTerminator(BB, true);
 
   // Check for and eliminate duplicate PHI nodes in this block.

 }
 
 /// This function is used to do simplification of a CFG.
 /// For example, it adjusts branches to branches to eliminate the extra hop,
 /// eliminates unreachable basic blocks, and does other "peephole" optimization
 /// of the CFG.  It returns true if a modification was made.
 ///
 bool llvm::SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
-                       unsigned BonusInstThreshold, AssumptionCache *AC) {
+                       unsigned BonusInstThreshold, AssumptionCache *AC,
+                       DominatorTree *DT, bool *RemovedManyBB) {
   return SimplifyCFGOpt(TTI, BB->getModule()->getDataLayout(),
-                        BonusInstThreshold, AC).run(BB);
+                        BonusInstThreshold, AC, DT, RemovedManyBB).run(BB);
 }

test/Transforms/SimplifyCFG/InfLoop.ll

+; RUN: opt < %s -simplifycfg -disable-output
+; END.
+
+target datalayout = "e-m:o-p:32:32-f64:32:64-v64:32:64-v128:32:128-a:0:32-n32-S32"
+target triple = "thumbv7-apple-ios9.0.0"
+
+%struct.anon = type { %struct.anon.0, i32, i32, %union.T1 }
+%struct.anon.0 = type { i32, [256 x i32], [256 x i8] }
+%union.T1 = type { %struct.F}
+%struct.G_t = type { i32, i32, i32, i32, i32, i8 }
+%struct.F = type { i32 }
+%struct.S_t = type { %struct.anon.1 }
+%struct.anon.1 = type { i64, i64, i64, i64, i64, i64, i64, i64 }
+%struct.T1 = type { %union.T1*, i32, %struct.L_t }
+%struct.L_t = type { i32*, i32, i32 }
+%struct.T2 = type { [256 x i32] }
+
+@U = internal global %struct.anon zeroinitializer, align 4
+@S = external global %struct.S_t, align 4
+@G = external global %struct.G_t, align 4
+@table = external global [17 x i32], align 4
+@T1 = external global %struct.T1, align 4
+declare i32 @bar()
+declare i32 @extend(i32)
+declare i8* @update(i32 %t1Ix, i32 %old_sz, i32 %sz)
+declare i32 @getix(i8*)
+
+
+define void @main() {
+entry:
+  %0 = load i32, i32* getelementptr inbounds (%struct.anon, %struct.anon* @U, i32 0, i32 2), align 4
+  %cmp.i = icmp eq i32 %0, -1
+  br i1 %cmp.i, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  %1 = load i32, i32* getelementptr inbounds (%struct.anon, %struct.anon* @U, i32 0, i32 2), align 4
+  %bf.load = load i32, i32* getelementptr inbounds (%struct.anon, %struct.anon* @U, i32 0, i32 3, i32 0, i32 0), align 4
+  %cmp = icmp slt i32 %bf.load, 0
+  br i1 %cmp, label %if.end7, label %cond.false
+
+cond.false:                                       ; preds = %if.end
+  %bf.clear = shl i32 %bf.load, 1
+  %add = and i32 %bf.clear, 30
+  %shl = add nuw nsw i32 %add, 2
+  br label %if.end7
+
+if.end7:                                          ; preds = %if.end, %cond.false
+  %old_sz.0 = phi i32 [ %shl, %cond.false ], [ 0, %if.end ]
+  %2 = load i32, i32* getelementptr inbounds (%struct.anon, %struct.anon* @U, i32 0, i32 0, i32 0), align 4
+  %cmp.i52 = icmp eq i32 %2, 1
+  br i1 %cmp.i52, label %if.then9, label %if.else10
+
+if.then9:                                         ; preds = %if.end7
+  %3 = load i64, i64* getelementptr inbounds (%struct.S_t, %struct.S_t* @S, i32 0, i32 0, i32 5), align 4
+  %inc = add i64 %3, 1
+  store i64 %inc, i64* getelementptr inbounds (%struct.S_t, %struct.S_t* @S, i32 0, i32 0, i32 5), align 4
+  %4 = load i32, i32* getelementptr inbounds (%struct.anon, %struct.anon* @U, i32 0, i32 0, i32 1, i32 0), align 4
+  br label %if.end29
+
+if.else10:                                        ; preds = %if.end7
+  %cmp11 = icmp ugt i32 %2, 13
+  br i1 %cmp11, label %if.then12, label %if.else14
+
+if.then12:                                        ; preds = %if.else10
+  %call13 = tail call fastcc i8* @update(i32 %1, i32 %old_sz.0, i32 16)
+  %5 = bitcast i8* %call13 to %struct.T2*
+  br label %if.end26
+
+if.else14:                                        ; preds = %if.else10
+  %6 = load i8, i8* getelementptr inbounds (%struct.G_t, %struct.G_t* @G, i32 0, i32 5), align 4
+  %tobool = icmp eq i8 %6, 0
+  br i1 %tobool, label %lor.rhs, label %if.then18
+
+lor.rhs:                                          ; preds = %if.else14
+  %tobool.not.i = icmp eq i8 %6, 0
+  br i1 %tobool.not.i, label %if.else21, label %if.end.i54
+
+if.end.i54:                                       ; preds = %lor.rhs
+  %add.i = add i32 %2, 1
+  %call.i = tail call i32 @extend(i32 %add.i)
+  %7 = load i32, i32* getelementptr inbounds (%struct.G_t, %struct.G_t* @G, i32 0, i32 3), align 4
+  %add1.i = add i32 %7, %call.i
+  %8 = load i32, i32* getelementptr inbounds (%struct.anon, %struct.anon* @U, i32 0, i32 0, i32 0), align 4
+  %shl.i = shl i32 1, %add1.i
+  %9 = load i32, i32* getelementptr inbounds (%struct.G_t, %struct.G_t* @G, i32 0, i32 4), align 4
+  %add9.i = add i32 %9, 1
+  br label %for.cond.i
+
+for.cond.i:                                       ; preds = %if.end6.i, %if.end.i54
+  %ix.0.i = phi i32 [ 0, %if.end.i54 ], [ %inc.i55, %if.end6.i ]
+  %ret.0.off0.i = phi i1 [ false, %if.end.i54 ], [ %.ret.0.off0.i, %if.end6.i ]
+  %cmp2.i = icmp ult i32 %ix.0.i, %8
+  br i1 %cmp2.i, label %for.body.i, label %TmpSimpleNeedExt.exit
+
+for.body.i:                                       ; preds = %for.cond.i
+  %arrayidx.i = getelementptr inbounds %struct.anon, %struct.anon* @U, i32 0, i32 0, i32 2, i32 %ix.0.i
+  %10 = load i8, i8* %arrayidx.i, align 1
+  %conv.i = zext i8 %10 to i32
+  %cmp3.i = icmp sgt i32 %conv.i, %shl.i
+  br i1 %cmp3.i, label %if.else21, label %if.end6.i
+
+if.end6.i:                                        ; preds = %for.body.i
+  %cmp10.i = icmp ugt i32 %conv.i, %add9.i
+  %.ret.0.off0.i = or i1 %ret.0.off0.i, %cmp10.i
+  %inc.i55 = add i32 %ix.0.i, 1
+  br label %for.cond.i
+
+TmpSimpleNeedExt.exit:                        ; preds = %for.cond.i
+  br i1 %ret.0.off0.i, label %if.then18, label %if.else21
+
+if.then18:                                        ; preds = %if.else14, %TmpSimpleNeedExt.exit
+  %11 = load i32, i32* getelementptr inbounds (%struct.anon, %struct.anon* @U, i32 0, i32 0, i32 0), align 4
+  %add.i56 = add i32 %11, 1
+  %arrayidx = getelementptr inbounds [17 x i32], [17 x i32]* @table, i32 0, i32 %add.i56
+  %12 = load i32, i32* %arrayidx, align 4
+  %call20 = tail call fastcc i8* @update(i32 %1, i32 %old_sz.0, i32 %12)
+  %13 = bitcast i8* %call20 to %struct.T2*
+  br label %if.end26
+
+if.else21:                                        ; preds = %for.body.i, %lor.rhs, %TmpSimpleNeedExt.exit
+  %call22 = tail call fastcc i32 @bar()
+  %arrayidx23 = getelementptr inbounds [17 x i32], [17 x i32]* @table, i32 0, i32 %call22
+  %14 = load i32, i32* %arrayidx23, align 4
+  %call24 = tail call fastcc i8* @update(i32 %1, i32 %old_sz.0, i32 %14)
+  %15 = bitcast i8* %call24 to %struct.T2*
+  br label %if.end26
+
+if.end26:                                         ; preds = %if.then18, %if.else21, %if.then12
+  %new_.0 = phi i8* [ %call13, %if.then12 ], [ %call20, %if.then18 ], [ %call24, %if.else21 ]
+  %sz.0 = phi i32 [ 16, %if.then12 ], [ %12, %if.then18 ], [ %14, %if.else21 ]
+  %call27 = tail call i32 @getix(i8* %new_.0)
+  %16 = load %union.T1*, %union.T1** getelementptr inbounds (%struct.T1, %struct.T1* @T1, i32 0, i32 0), align 4
+  %17 = getelementptr inbounds %union.T1, %union.T1* %16, i32 %1, i32 0, i32 0
+  %bf.load.i = load i32, i32* %17, align 4
+  %cmp.i51 = icmp slt i32 %bf.load.i, 0
+  br i1 %cmp.i51, label %if.then.i, label %if.end.i
+
+if.then.i:                                        ; preds = %if.end26
+  %18 = load i32, i32* getelementptr inbounds (%struct.T1, %struct.T1* @T1, i32 0, i32 2, i32 2), align 4
+  %inc.i = add i32 %18, 1
+  store i32 %inc.i, i32* getelementptr inbounds (%struct.T1, %struct.T1* @T1, i32 0, i32 2, i32 2), align 4
+  br label %if.end.i
+
+if.end.i:                                         ; preds = %if.then.i, %if.end26
+  %and.i = and i32 %call27, 1
+  %cmp1.i = icmp eq i32 %and.i, 0
+  br i1 %cmp1.i, label %main.exit, label %if.then2.i
+
+if.then2.i:                                       ; preds = %if.end.i
+  %.pre.i = load %union.T1*, %union.T1** getelementptr inbounds (%struct.T1, %struct.T1* @T1, i32 0, i32 0), align 4
+  br label %main.exit
+
+main.exit:                       ; preds = %if.end.i, %if.then2.i
+  %19 = phi %union.T1* [ %.pre.i, %if.then2.i ], [ %16, %if.end.i ]
+  %shr.i = lshr i32 %sz.0, 1
+  %sub.i = add nuw i32 %shr.i, 15
+  %bf.value.i = and i32 %sub.i, 15
+  %20 = shl i32 %call27, 3
+  %bf.shl.i = and i32 %20, 2147483632
+  %bf.set10.i = or i32 %bf.value.i, %bf.shl.i
+  %ci = getelementptr inbounds %union.T1, %union.T1* %19, i32 %1, i32 0, i32 0
+  store i32 %bf.set10.i, i32* %ci, align 1
+  br label %if.end29
+
+if.end29:                                         ; preds = %main.exit, %if.then9
+  store i32 -1, i32* getelementptr inbounds (%struct.anon, %struct.anon* @U, i32 0, i32 2), align 4
+  ret void
+}