This is an archive of the discontinued LLVM Phabricator instance.

[IndVars] Forget the SCEV when the instruction has been sunk.
ClosedPublic

Authored by StephenFan on Oct 31 2022, 1:28 AM.

Details

Summary

In the past, the SCEV expression of the sunk instruction was not
forgetted. This led to the incorrect block dispositions after the
instruction be sunk.

Fixes https://github.com/llvm/llvm-project/issues/58662

Diff Detail

Event Timeline

StephenFan created this revision.Oct 31 2022, 1:28 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 31 2022, 1:28 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
StephenFan requested review of this revision.Oct 31 2022, 1:28 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 31 2022, 1:28 AM

The test will be added if it is the right fix.

nikic added a comment.Oct 31 2022, 2:10 AM

This is likely not the right fix. I don't see how there can be an addrec whose start value is not available at loop entry (of its own loop).

nikic requested changes to this revision.Nov 1 2022, 1:32 AM

Marking this as changes request, as this does not look correct without more information. A reduced test case that shows how the addrec looks like would be helpful. (Maybe something like this could happen in unreachable code or something.)

This revision now requires changes to proceed.Nov 1 2022, 1:32 AM

Marking this as changes request, as this does not look correct without more information. A reduced test case that shows how the addrec looks like would be helpful. (Maybe something like this could happen in unreachable code or something.)

@f = dso_local global i16 0, align 2
@a = dso_local global i32 0, align 4
@b = dso_local global i32 0, align 4
@d = dso_local global i32 0, align 4
@e = dso_local global i32 0, align 4
@g = dso_local global i8 0, align 1

define dso_local zeroext i8 @l() local_unnamed_addr #2 {
entry:
  %0 = load i32, ptr @b, align 4
  %a.promoted = load i32, ptr @a, align 4
  br label %for.cond

for.cond:                                         ; preds = %h.exit, %entry
  %inc8 = phi i32 [ %a.promoted, %entry ], [ %inc, %h.exit ]
  %storemerge = phi i16 [ 0, %entry ], [ %sub6, %h.exit ]
  %inc = add nsw i32 %inc8, 1
  %and = and i32 %0, %inc
  %conv = sext i16 %storemerge to i32
  %sub = add nsw i32 %conv, -6
  br label %while.body.i

while.body.i:                                     ; preds = %for.cond, %while.body.i
  %c.05.i = phi i32 [ %inc.i, %while.body.i ], [ 0, %for.cond ]
  %i.addr.04.i = phi i32 [ %shr.i, %while.body.i ], [ %sub, %for.cond ]
  %shr.i = ashr i32 %i.addr.04.i, 1
  %inc.i = add nsw i32 %c.05.i, 1
  %cmp.i = icmp sgt i32 %c.05.i, 5
  %tobool.not.i = icmp ult i32 %i.addr.04.i, 4
  %or.cond.i = select i1 %cmp.i, i1 true, i1 %tobool.not.i
  br i1 %or.cond.i, label %h.exit, label %while.body.i

h.exit:                                           ; preds = %while.body.i
  %inc.i.lcssa = phi i32 [ %inc.i, %while.body.i ]
  %1 = trunc i32 %and to i8
  %2 = trunc i32 %inc.i.lcssa to i8
  %3 = sub i8 %1, %2
  %tobool.not = icmp eq i8 %3, 17
  %sub6 = add i16 %storemerge, -8
  br i1 %tobool.not, label %for.cond, label %if.then

if.then:                                          ; preds = %h.exit
  %storemerge.lcssa = phi i16 [ %storemerge, %h.exit ]
  %inc.lcssa = phi i32 [ %inc, %h.exit ]
  %and.lcssa = phi i32 [ %and, %h.exit ]
  %inc.i.lcssa.lcssa = phi i32 [ %inc.i.lcssa, %h.exit ]
  store i16 %storemerge.lcssa, ptr @f, align 2
  store i32 %inc.lcssa, ptr @a, align 4
  store i32 %and.lcssa, ptr @d, align 4
  store i32 %inc.i.lcssa.lcssa, ptr @e, align 4
  %4 = load i8, ptr @g, align 1
  ret i8 %4
}

This is the test case that I am debugging. But I have not reduced it.
The scalar evolution output of %3 = sub i8 %1, %2 is {(-1 + (trunc i32 %and to i8)),+,-1}<%while.body.i> U: full-set S: full-set --> (-1 + (trunc i32 %and to i8)) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant, %while.body.i: Computable }
It seems that this problem is caused by calling isKnownOnEveryIteration with the SCEVAddRecExpr above. Since the above SCEV's LoopHeader is while.body.i but the start value is not available at while.body.i's entry.

StephenFan retitled this revision from [SCEV] Make isKnownOnEveryIteration return false if LHS's start value is not available at loop entry to [IndVars] Forget a SCEV when an instruction has been sunk..
StephenFan edited the summary of this revision. (Show Details)

Change solution.

Drop previous solution.

fhahn added a comment.Nov 2 2022, 10:48 AM

Thanks for the update. Could you add a test case?

StephenFan retitled this revision from [IndVars] Forget a SCEV when an instruction has been sunk. to [IndVars] Forget the SCEV when the instruction has been sunk..

Fix grammer.

Thanks for the update. Could you add a test case?

Yes. I will add a test case tomorrow.

nikic added inline comments.Nov 2 2022, 12:45 PM
llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
1284

I think you can drop the forgetBlockAndLoopDispositions() call now, it should be handled by forgetValue().

Add a test case and drop the forgetBlockAndLoopDispositions call.

nikic added inline comments.Nov 3 2022, 1:08 AM
llvm/test/Transforms/IndVarSimplify/pr58662.ll
100

Could you please reduce this test case further? Just running it through llvm-reduce already produces something smaller (https://gist.github.com/nikic/b315c6ab41ee4676c2a32953a077a3e9), and possibly further manual reduction is possible.

StephenFan updated this revision to Diff 472951.Nov 3 2022, 8:36 AM

reduce test case.

fhahn accepted this revision.Nov 3 2022, 12:27 PM

LGTM, thanks!

llvm/test/Transforms/IndVarSimplify/pr58662.ll
6

It looks like there already SCEV invalidation tests in llvm/test/Transforms/IndVarSimplify/scev-invalidation.ll. Could you move the test there?

33

Naming could be improved to make things easier to read, e.g. %for.cond -> outer.header, while.body.i -> inner, h.exit-> outer.latch.

34

store merge -> outer.iv, sub6 -> outer.iv.next

48

this seems mis-named, maybe just lcssa?

StephenFan updated this revision to Diff 473115.Nov 3 2022, 8:36 PM

Move test case and reduce variable name.

Thanks for reviewing! And thanks @nikic for providing a reduced test case.

This revision was not accepted when it landed; it landed in state Needs Review.Nov 6 2022, 7:41 AM
This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.