diff --git a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
--- a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
+++ b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
@@ -412,8 +412,14 @@
     // Make sure that we reprocess all operands now that we reduced their
     // use counts.
     for (Use &Operand : I.operands())
-      if (auto *Inst = dyn_cast<Instruction>(Operand))
+      if (auto *Inst = dyn_cast<Instruction>(Operand)) {
         Worklist.add(Inst);
+        // If this instruction uses a phi node then we need to process the phi
+        // node, as it may potentially be able to delete it
+        for (Use &OpOp : Inst->operands())
+          if (auto *PN = dyn_cast<PHINode>(OpOp))
+            Worklist.add(PN);
+      }
 
     Worklist.remove(&I);
     I.eraseFromParent();
diff --git a/llvm/test/Transforms/InstCombine/phi-elimination-iteration.ll b/llvm/test/Transforms/InstCombine/phi-elimination-iteration.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/InstCombine/phi-elimination-iteration.ll
@@ -0,0 +1,21 @@
+; RUN: opt < %s -passes=instcombine -S -debug 2>&1 | FileCheck %s
+define void @f() {
+entry:
+	br label %a
+a:
+	%phi.a = phi i32 [ 0, %entry ], [ %x, %a ]
+	%x = add i32 %phi.a, 1
+	br i1 false, label %a, label %b
+b:
+	%phi.b = phi i32 [ %x, %a ], [ %y, %b ]
+	%y = add i32 %phi.b, 1
+	br label %b
+}
+
+; CHECK: INSTCOMBINE ITERATION #1
+; CHECK: INSTCOMBINE ITERATION #2
+; CHECK-NOT: INSTCOMBINE ITERATION #3
+; CHECK-LABEL: a:
+; CHECK-NEXT:    br i1 false, label %a, label %b
+; CHECK-LABEL: b:
+; CHECK-NEXT:    br label %b