Index: lib/Transforms/Utils/LCSSA.cpp
===================================================================
--- lib/Transforms/Utils/LCSSA.cpp
+++ lib/Transforms/Utils/LCSSA.cpp
@@ -226,11 +226,16 @@
     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 need to redo the
+  // use_empty() check here, because even if the PHI node wasn't used when added
+  // to PHIsToRemove, later added PHI nodes can be using it.  This cleanup is
+  // not guaranteed to handle trees/cycles of PHI nodes that only are used by
+  // each other. Such situations has only been noticed when the input IR
+  // contains unreachable code, and leaving some extra redundant PHI nodes in
+  // such situations is considered a minor problem.
+  for (PHINode *PN : PHIsToRemove)
+    if (PN->use_empty())
+      PN->eraseFromParent();
   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
+}