Index: llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
===================================================================
--- llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -2858,11 +2858,15 @@
 
   // Now that we're done iterating through lists, clean up any instructions
   // which are now dead.
-  while (!DeadInsts.empty())
-    if (Instruction *Inst =
-            dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val()))
+  while (!DeadInsts.empty()) {
+    Value *V = DeadInsts.pop_back_val();
+
+    if (PHINode *PHI = dyn_cast_or_null<PHINode>(V))
+      Changed |= RecursivelyDeleteDeadPHINode(PHI, TLI, MSSAU.get());
+    else if (Instruction *Inst = dyn_cast_or_null<Instruction>(V))
       Changed |=
           RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI, MSSAU.get());
+  }
 
   // The Rewriter may not be used from this point on.
 
Index: llvm/test/Transforms/IndVarSimplify/Mips/lit.local.cfg
===================================================================
--- /dev/null
+++ llvm/test/Transforms/IndVarSimplify/Mips/lit.local.cfg
@@ -0,0 +1,2 @@
+if not 'Mips' in config.root.targets:
+    config.unsupported = True
Index: llvm/test/Transforms/IndVarSimplify/Mips/rewrite-loop-exit-values-phi.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/IndVarSimplify/Mips/rewrite-loop-exit-values-phi.ll
@@ -0,0 +1,62 @@
+; RUN: opt -indvars -S %s -o - | FileCheck %s
+
+; When bailing out in rewriteLoopExitValues() you would be left with a PHI node
+; that was not deleted, and the IndVar pass would return an incorrect modified
+; status. This was caught by the expensive check introduced in D86589.
+
+; Keeping the PHI node after the IndVars run would result in redundant PHI
+; nodes:
+;
+; for.cond3.preheader.i:
+;   %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc10.i ], [ undef, %entry ]
+;   %dec.lcssa7.i = phi i64 [ undef, %entry ], [ %0, %for.inc10.i ]
+;
+; for.inc10.i:
+;   [...]
+;   %0 = add i64 %dec.lcssa7.i, -6
+;   %indvars.iv.next = add i64 %indvars.iv, -6
+;
+; which would however be coalesced after subsequent runs of IndVars, so we
+; would get a very similar output for the RUN line with or without the patch
+; that is connected to this test case.
+
+; CHECK-LABEL: for.cond3.preheader.i:
+; CHECK-NEXT: %dec.lcssa7.i = phi i64 [ undef, %entry ], [ %0, %for.inc10.i ]
+; CHECK-NEXT: br label %for.body5.i
+
+; CHECK-LABEL: for.inc10.i:
+; CHECK-NEXT: %dec5.i.lcssa = phi i64 [ %dec5.i, %for.body5.i ]
+; CHECK-NEXT: %xor.i.lcssa = phi i64 [ %xor.i, %for.body5.i ]
+; CHECK-NEXT: %0 = add i64 %dec.lcssa7.i, -6
+; CHECK-NEXT: br i1 true, label %for.cond12.preheader.i, label %for.cond3.preheader.i
+
+target datalayout = "e-m:m-p:32:32-i8:8:32-i16:16:32-i64:64-n32-S64"
+target triple = "mipsel"
+
+define void @k() {
+entry:
+  br label %for.cond3.preheader.i
+
+for.cond3.preheader.i:                            ; preds = %for.inc10.i, %entry
+  %dec.lcssa7.i = phi i64 [ undef, %entry ], [ %0, %for.inc10.i ]
+  br label %for.body5.i
+
+for.cond12.preheader.i:                           ; preds = %for.inc10.i
+  %dec5.i.lcssa.lcssa = phi i64 [ %dec5.i.lcssa, %for.inc10.i ]
+  unreachable
+
+for.body5.i:                                      ; preds = %for.body5.i, %for.cond3.preheader.i
+  %dec5.i = phi i64 [ %dec.lcssa7.i, %for.cond3.preheader.i ], [ %dec.i, %for.body5.i ]
+  %storemerge13.i = phi i32 [ 6, %for.cond3.preheader.i ], [ %dec9.i, %for.body5.i ]
+  %dec.i = add nsw i64 %dec5.i, -1
+  %xor.i = xor i64 %dec5.i, undef
+  %dec9.i = add nsw i32 %storemerge13.i, -1
+  %tobool4.not.i = icmp eq i32 %dec9.i, 0
+  br i1 %tobool4.not.i, label %for.inc10.i, label %for.body5.i
+
+for.inc10.i:                                      ; preds = %for.body5.i
+  %dec5.i.lcssa = phi i64 [ %dec5.i, %for.body5.i ]
+  %xor.i.lcssa = phi i64 [ %xor.i, %for.body5.i ]
+  %0 = add i64 %dec.lcssa7.i, -6
+  br i1 undef, label %for.cond12.preheader.i, label %for.cond3.preheader.i
+}