Index: lib/Transforms/Utils/LCSSA.cpp
===================================================================
--- lib/Transforms/Utils/LCSSA.cpp
+++ lib/Transforms/Utils/LCSSA.cpp
@@ -74,7 +74,7 @@
 bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
                                     DominatorTree &DT, LoopInfo &LI) {
   SmallVector<Use *, 16> UsesToRewrite;
-  SmallSetVector<PHINode *, 16> PHIsToRemove;
+  SmallSetVector<PHINode *, 16> PHIsToRemoveIfNotUsed;
   PredIteratorCache PredCache;
   bool Changed = false;
 
@@ -214,22 +214,34 @@
       if (!PostProcessPN->use_empty())
         Worklist.push_back(PostProcessPN);
 
-    // Keep track of PHI nodes that we want to remove because they did not have
-    // any uses rewritten. If the new PHI is used, store it so that we can
-    // try to propagate dbg.value intrinsics to it.
+    // Keep track of PHI nodes that we create, so that we can remove them again
+    // if they did not have any uses rewritten.
+    PHIsToRemoveIfNotUsed.insert(AddedPHIs.begin(), AddedPHIs.end());
+
+    // If the new PHI is used, store it so that we can try to propagate
+    // dbg.value intrinsics to it.
     SmallVector<PHINode *, 2> NeedDbgValues;
     for (PHINode *PN : AddedPHIs)
-      if (PN->use_empty())
-        PHIsToRemove.insert(PN);
-      else
+      if (!PN->use_empty())
         NeedDbgValues.push_back(PN);
     insertDebugValuesForPHIs(InstBB, NeedDbgValues);
     Changed = true;
   }
-  // Remove PHI nodes that did not have any uses rewritten.
-  for (PHINode *PN : PHIsToRemove) {
-    assert (PN->use_empty() && "Trying to remove a phi with uses.");
-    PN->eraseFromParent();
+  // Remove PHI nodes that did not have any uses rewritten. We do this
+  // iteratively as we may reveal more unused PHI nodes along the way.
+  bool RemovePHIs = true;
+  while (RemovePHIs) {
+    RemovePHIs = false;
+    SmallSetVector<PHINode *, 16> NotRemoved;
+    for (PHINode *PN : PHIsToRemoveIfNotUsed) {
+      if (PN->use_empty()) {
+        PN->eraseFromParent();
+        RemovePHIs = true;
+      } else
+        NotRemoved.insert(PN);
+    }
+    // Update the set of candidates for the next iteration.
+    PHIsToRemoveIfNotUsed = NotRemoved;
   }
   return Changed;
 }
Index: test/Transforms/LCSSA/remove-phis.ll
===================================================================
--- /dev/null
+++ test/Transforms/LCSSA/remove-phis.ll
@@ -0,0 +1,56 @@
+; RUN: opt < %s -lcssa -verify -S -o /dev/null
+
+; This bugpoint reduced test case used to assert when removing unused PHI nodes.
+; Just verify that we do not assert/crash.
+
+define void @test() {
+entry:
+  br label %gazank
+
+gazank:
+  %value = phi i16 [ 0, %entry ], [ undef, %gazonk ]
+  br i1 undef, label %gazink, label %qqq
+
+gazink:
+  br i1 undef, label %gazonk, label %infinite.loop.pred
+
+gazonk:
+  br i1 undef, label %exit1, label %gazank
+
+qqq:
+  br i1 undef, label %www, label %exit2
+
+www:
+  br i1 undef, label %qqq, label %foo.pred
+
+foo.pred:
+  br label %foo
+
+foo:
+  br i1 undef, label %bar, label %exit1.pred
+
+bar:
+  br i1 undef, label %foo, label %exit2.pred
+
+unreachable1:
+  br i1 undef, label %foo, label %exit2.pred
+
+exit1.pred:
+  br label %exit1
+
+exit1:
+  ret void
+
+exit2.pred:
+  br label %exit2
+
+exit2:
+  ret void
+
+infinite.loop.pred:
+  br label %infinite.loop
+
+infinite.loop:
+  %dead = phi i16 [ %value, %infinite.loop.pred ], [ 0, %infinite.loop ]
+  br label %infinite.loop
+}