Page MenuHomePhabricator

[IndVarSimplify] Fix Modified status when handling dead PHI nodes
ClosedPublic

Authored by dstenb on Nov 10 2020, 5:22 AM.

Details

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.

Diff Detail

Event Timeline

dstenb created this revision.Nov 10 2020, 5:22 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 10 2020, 5:22 AM
dstenb requested review of this revision.Nov 10 2020, 5:22 AM

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

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 added inline comments.Nov 17 2020, 8:36 PM
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 added inline comments.Nov 17 2020, 8:39 PM
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.

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 added inline comments.Nov 18 2020, 12:49 AM
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 added inline comments.Nov 18 2020, 2:53 AM
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 added a comment.EditedNov 18 2020, 3:01 AM

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 accepted this revision.Nov 24 2020, 8:25 PM

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

This revision is now accepted and ready to land.Nov 24 2020, 8:25 PM
dstenb updated this revision to Diff 307714.Nov 25 2020, 2:24 PM

Use X86 reproducer instead.

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.