[IndVarSimplify] Fix Modified status when handling dead PHI nodes

[dstenb]

Summary

When bailing out in rewriteLoopExitValues() you could be left with PHI
nodes in the DeadInsts vector. Those would be not handled by the use of
RecursivelyDeleteTriviallyDeadInstructions() in IndVarSimplify. This resulted
in the IndVarSimplify pass returning an incorrect modified status. This was
caught by the expensive check introduced in D86589.

This patches changes IndVarSimplify so that it deletes those PHI nodes,
using RecursivelyDeleteDeadPHINode().

This fixes PR47486.

[dstenb]

I'm not very familiar with the IndVars pass, so I have not idea if this is the correct way to solve this.

[TaWeiTu]

In D91153#2385479, @dstenb wrote:

I'm not very familiar with the IndVars pass, so I have not idea if this is the correct way to solve this.

This seems correct to me, but I'm not familiar with IndVar either, so maybe someone else should take a look.
However, I think it would be better if we can return false in this case (i.e. if all PHI nodes created in rewriteLoopExitValues are dead).
But I don't know whether there's some edge case that forces us to return true here.

[mkazantsev]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1880

Do I understand correctly that if RecursivelyDeleteTriviallyDeadInstructions is given a Phi as argument, it doesn't work with it correctly? Maybe we should do this inside of this function? Its name suggests that it should handle any instructions.

[mkazantsev]

llvm/test/Transforms/IndVarSimplify/Mips/rewrite-loop-exit-values-phi.ll

33 ↗

(On Diff #304153)

Please commit this test separately with current auto-generated checks (use utils/update_test_checks.py for it). Then, with your code change, update the automated checks. It will clearly show what exactly your patch changes.

[dstenb]

In D91153#2393018, @TaWeiTu wrote:

In D91153#2385479, @dstenb wrote:

I'm not very familiar with the IndVars pass, so I have not idea if this is the correct way to solve this.

This seems correct to me, but I'm not familiar with IndVar either, so maybe someone else should take a look.
However, I think it would be better if we can return false in this case (i.e. if all PHI nodes created in rewriteLoopExitValues are dead).
But I don't know whether there's some edge case that forces us to return true here.

At least with how this patch is formed, i.e. dealing with PHI nodes first, RecursivelyDeleteDeadPHINode will deal with some trivially dead PHI nodes that RecursivelyDeleteTriviallyDeadInstructions dealt with before this patch. If I just remove the Changed |= part for the PHI nodes, the following tests fails due to the pass return status check:

LLVM :: Transforms/IndVarSimplify/const_phi.ll
LLVM :: Transforms/IndVarSimplify/crash.ll
LLVM :: Transforms/LoopSimplify/pr28272.ll

I guess that the does not really answer your question about returning false specifically for the rewriteLoopExitValues case though.

As far as I have seen in my test runs the bug that this patch fixes occurs very rarely, so perhaps it is not a huge issue to return true here?

[dstenb]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1880

The RecursivelyDeleteTriviallyDeadInstructions instruction is able to delete PHI nodes that are trivially dead. It does not handle the PHI node pairs of the following form that this patch deals with:

%dec.lcssa7.i = phi i64 [ undef, %entry ], [ %0, %for.inc10.i ]
%0 = add i64 %dec.lcssa7.i, -6

since the PHI node has an use (the incoming value).

[dstenb]

llvm/test/Transforms/IndVarSimplify/Mips/rewrite-loop-exit-values-phi.ll

33 ↗

(On Diff #304153)

I do not think that that is possible in this case, since the test in itself will trigger the "Pass modifies its input and doesn't report it" unreachable when using an EXPENSIVE_CHECKS build without this bug fix. There is unfortunately no CLI option to disable those checks.

Here is at least the diff when using a non-EXPENSIVE_CHECKS build:

--- before.txt  2020-11-18 11:45:13.535990930 +0100
+++ after.txt   2020-11-18 11:43:02.432981959 +0100
@@ -8,7 +8,7 @@
   br label %for.cond3.preheader.i
 
 for.cond3.preheader.i:                            ; preds = %for.inc10.i, %entry
-  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc10.i ], [ undef, %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
@@ -16,7 +16,7 @@
   unreachable
 
 for.body5.i:                                      ; preds = %for.body5.i, %for.cond3.preheader.i
-  %dec5.i = phi i64 [ %indvars.iv, %for.cond3.preheader.i ], [ %dec.i, %for.body5.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
@@ -27,6 +27,6 @@
 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 ]
-  %indvars.iv.next = add i64 %indvars.iv, -6
+  %0 = add i64 %dec.lcssa7.i, -6
   br i1 true, label %for.cond12.preheader.i, label %for.cond3.preheader.i
 }

The dead PHI that previously was left behind was coalesced with the %dec.lcssa7.i PHI in subsequent runs of IndVars, so the IR is basically the same with or without this patch for the run of the attached reproducer.

[TaWeiTu]

IMO the bug is not MIPS-specific, the following test has the same assertion failure with opt -S -indvars on X86 machines:

@ptr = external global i64

define dso_local void @hoge() local_unnamed_addr {
entry:                                            ; preds = %entry
  %n = sdiv exact i64 undef, 40
  br label %header

header:                                           ; preds = %latch, %entry
  %idx = phi i64 [ %idx.next, %latch ], [ undef, %entry ]
  %cond = icmp sgt i64 %n, %idx
  br i1 %cond, label %end, label %inner

inner:                                            ; preds = %inner, %header
  %i = phi i64 [ %i.next, %inner ], [ 0, %header ]
  %j = phi i64 [ %j.next, %inner ], [ %n, %header ]
  %i.next = add nsw i64 %i, 1
  %j.next = add nsw i64 %j, 1
  store i64 undef, i64* @ptr
  %cond1 = icmp slt i64 %j, %idx
  br i1 %cond1, label %inner, label %inner_exit

inner_exit:                                       ; preds = %inner
  %indvar = phi i64 [ %i.next, %inner ]
  %indvar_use = add i64 %indvar, 1
  br label %latch

latch:                                            ; preds = %inner_exit
  %idx.next = add nsw i64 %idx, -1
  br label %header

end:                                              ; preds = %header
  ret void
}

[mkazantsev]

Please move the test out of MIPS-specific into general test directory if it's possible. Otherwise, LGTM.

[dstenb]

Use X86 reproducer instead.

[dstenb]

In D91153#2415351, @mkazantsev wrote:

Please move the test out of MIPS-specific into general test directory if it's possible. Otherwise, LGTM.

Thanks for the review! The output for the MIPS test case differed quite a bit depending on which target it was run on, so that would have complicated the FileChecks. Due to that, I used the X86 reproducer provided by @TaWeiTu instead, and moved that to the general test directory.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

#endif
   }
   // Clear the rewriter cache, because values that are in the rewriter's cache
   // can be deleted in the loop below, causing the AssertingVH in the cache to
   // trigger.
   Rewriter.clear();
 
   // 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.
 
   // Loop-invariant instructions in the preheader that aren't used in the
   // loop may be sunk below the loop to reduce register pressure.
   Changed |= sinkUnusedInvariants(L);
 
   // rewriteFirstIterationLoopExitValues does not rely on the computation of

llvm/test/Transforms/IndVarSimplify/rewrite-loop-exit-values-phi.ll

+; 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.
+
+; CHECK-LABEL: header:
+; CHECK-NEXT: %idx = phi i64 [ %idx.next, %latch ], [ undef, %entry ]
+; CHECK-NEXT: %cond = icmp sgt i64 %n, %idx
+; CHECK-NEXT: br i1 %cond, label %end, label %inner.preheader
+
+; CHECK-LABEL: latch:
+; CHECK-NEXT: %idx.next = add nsw i64 %idx, -1
+; CHECK-NEXT: br label %header
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@ptr = external global i64
+
+define dso_local void @hoge() local_unnamed_addr {
+entry:                                            ; preds = %entry
+  %n = sdiv exact i64 undef, 40
+  br label %header
+
+header:                                           ; preds = %latch, %entry
+  %idx = phi i64 [ %idx.next, %latch ], [ undef, %entry ]
+  %cond = icmp sgt i64 %n, %idx
+  br i1 %cond, label %end, label %inner
+
+inner:                                            ; preds = %inner, %header
+  %i = phi i64 [ %i.next, %inner ], [ 0, %header ]
+  %j = phi i64 [ %j.next, %inner ], [ %n, %header ]
+  %i.next = add nsw i64 %i, 1
+  %j.next = add nsw i64 %j, 1
+  store i64 undef, i64* @ptr
+  %cond1 = icmp slt i64 %j, %idx
+  br i1 %cond1, label %inner, label %inner_exit
+
+inner_exit:                                       ; preds = %inner
+  %indvar = phi i64 [ %i.next, %inner ]
+  %indvar_use = add i64 %indvar, 1
+  br label %latch
+
+latch:                                            ; preds = %inner_exit
+  %idx.next = add nsw i64 %idx, -1
+  br label %header
+
+end:                                              ; preds = %header
+  ret void
+}