Index: lib/Transforms/InstCombine/InstructionCombining.cpp
===================================================================
--- lib/Transforms/InstCombine/InstructionCombining.cpp
+++ lib/Transforms/InstCombine/InstructionCombining.cpp
@@ -3574,7 +3574,7 @@
   return MadeIRChange;
 }
 
-/// Walk the function in depth-first order, adding all reachable code to the
+/// Walk the function in reverse post-order, adding all reachable code to the
 /// worklist.
 ///
 /// This has a couple of tricks to make the code faster and more powerful.  In
@@ -3582,22 +3582,20 @@
 /// them to the worklist (this significantly speeds up instcombine on code where
 /// many instructions are dead or constant).  Additionally, if we find a branch
 /// whose condition is a known constant, we only visit the reachable successors.
-static bool AddReachableCodeToWorklist(BasicBlock *BB, const DataLayout &DL,
-                                       SmallPtrSetImpl<BasicBlock *> &Visited,
-                                       InstCombineWorklist &ICWorklist,
-                                       const TargetLibraryInfo *TLI) {
+static bool AddReachableCodeToWorklist(
+    BasicBlock *BB, const DataLayout &DL,
+    SmallPtrSetImpl<BasicBlock *> &LiveBlocks, InstCombineWorklist &ICWorklist,
+    const TargetLibraryInfo *TLI) {
   bool MadeIRChange = false;
-  SmallVector<BasicBlock*, 256> Worklist;
-  Worklist.push_back(BB);
 
   SmallVector<Instruction*, 128> InstrsForInstCombineWorklist;
   DenseMap<Constant *, Constant *> FoldedConstants;
 
-  do {
-    BB = Worklist.pop_back_val();
+  ReversePostOrderTraversal<BasicBlock *> RPOT(BB);
+  LiveBlocks.insert(BB);
 
-    // We have now visited this block!  If we've already been here, ignore it.
-    if (!Visited.insert(BB).second)
+  for (BasicBlock *BB : RPOT) {
+    if (!LiveBlocks.count(BB))
       continue;
 
     for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
@@ -3644,26 +3642,26 @@
         InstrsForInstCombineWorklist.push_back(Inst);
     }
 
-    // Recursively visit successors.  If this is a branch or switch on a
-    // constant, only visit the reachable successor.
+    // If this is a branch or switch on a constant, mark only the single
+    // live successor. Otherwise assume all successors are live.
     Instruction *TI = BB->getTerminator();
     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
       if (BI->isConditional() && isa<ConstantInt>(BI->getCondition())) {
         bool CondVal = cast<ConstantInt>(BI->getCondition())->getZExtValue();
         BasicBlock *ReachableBB = BI->getSuccessor(!CondVal);
-        Worklist.push_back(ReachableBB);
+        LiveBlocks.insert(ReachableBB);
         continue;
       }
     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
       if (ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition())) {
-        Worklist.push_back(SI->findCaseValue(Cond)->getCaseSuccessor());
+        LiveBlocks.insert(SI->findCaseValue(Cond)->getCaseSuccessor());
         continue;
       }
     }
 
     for (BasicBlock *SuccBB : successors(TI))
-      Worklist.push_back(SuccBB);
-  } while (!Worklist.empty());
+      LiveBlocks.insert(SuccBB);
+  }
 
   // Once we've found all of the instructions to add to instcombine's worklist,
   // add them in reverse order.  This way instcombine will visit from the top
@@ -3702,15 +3700,15 @@
   // Do a depth-first traversal of the function, populate the worklist with
   // the reachable instructions.  Ignore blocks that are not reachable.  Keep
   // track of which blocks we visit.
-  SmallPtrSet<BasicBlock *, 32> Visited;
+  SmallPtrSet<BasicBlock *, 32> LiveBlocks;
   MadeIRChange |=
-      AddReachableCodeToWorklist(&F.front(), DL, Visited, ICWorklist, TLI);
+      AddReachableCodeToWorklist(&F.front(), DL, LiveBlocks, ICWorklist, TLI);
 
   // Do a quick scan over the function.  If we find any blocks that are
   // unreachable, remove any instructions inside of them.  This prevents
   // the instcombine code from having to deal with some bad special cases.
   for (BasicBlock &BB : F) {
-    if (Visited.count(&BB))
+    if (LiveBlocks.count(&BB))
       continue;
 
     unsigned NumDeadInstInBB = removeAllNonTerminatorAndEHPadInstructions(&BB);
Index: test/Transforms/InstCombine/icmp-div-constant.ll
===================================================================
--- test/Transforms/InstCombine/icmp-div-constant.ll
+++ test/Transforms/InstCombine/icmp-div-constant.ll
@@ -149,8 +149,7 @@
 ; CHECK:       then:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ -1, [[ENTRY:%.*]] ], [ 0, [[THEN]] ]
-; CHECK-NEXT:    ret i32 [[PHI]]
+; CHECK-NEXT:    ret i32 -1
 ;
 entry:
   %tobool = icmp eq i16 %a, 0
Index: test/Transforms/InstCombine/pr44245.ll
===================================================================
--- test/Transforms/InstCombine/pr44245.ll
+++ test/Transforms/InstCombine/pr44245.ll
@@ -157,6 +157,7 @@
 ; CHECK:       for.cond:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[COND_TRUE133:%.*]], label [[COND_FALSE138:%.*]]
 ; CHECK:       cond.true133:
+; CHECK-NEXT:    store %type_2* undef, %type_2** null, align 536870912
 ; CHECK-NEXT:    br label [[COND_END144:%.*]]
 ; CHECK:       cond.false138:
 ; CHECK-NEXT:    store %type_2* undef, %type_2** null, align 536870912
Index: test/Transforms/InstCombine/store.ll
===================================================================
--- test/Transforms/InstCombine/store.ll
+++ test/Transforms/InstCombine/store.ll
@@ -1,5 +1,5 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -instcombine -S | FileCheck %s
+; RUN: opt < %s -instcombine -instcombine-infinite-loop-threshold=2 -S | FileCheck %s
 
 define void @test1(i32* %P) {
 ; CHECK-LABEL: @test1(