This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Use trip count information to improve shift recurrence ranges
ClosedPublic

Authored by reames on Mar 8 2021, 4:25 PM.

Details

Summary

This patch exploits the knowledge that we may be running many fewer than bitwidth iterations of the loop, and may be able to disallow the overflow case. This patch specifically implements only the shl case, but this can be generalized to ashr and lshr without difficulty.

In my motivating example (a multiple dimension loop nest w/a shl recurrence at the outer level), this results in a massive improvement in scev-aa results.

Diff Detail

Event Timeline

reames created this revision.Mar 8 2021, 4:25 PM
reames requested review of this revision.Mar 8 2021, 4:25 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 8 2021, 4:25 PM
lebedev.ri added inline comments.
llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll
1

Please precommit

reames updated this revision to Diff 329445.Mar 9 2021, 12:50 PM

rebase over landed tests

mkazantsev added inline comments.Mar 12 2021, 12:52 AM
llvm/lib/Analysis/ScalarEvolution.cpp
5663

LI.isLoopHeader(P->getParent())?
I also wonder why is that needed. The implementation of matchSimpleRecurrence cannot recognize something which is not a header phi, because there is no other way to have BO as operand of Phi and vice versa at the same time. I guess this may be turned into assert after matchSimpleRecurrence.

5671

Looks like it's better split it into two checks, as ashr and lshr will still need BO->getOperand(0) != P.

5673

Are we missing a check that another operand is loop-invariant, or it is implied by something?

mkazantsev added a comment.EditedMar 12 2021, 1:01 AM

Regarding the helper you are using: looking into matchSimpleRecurrence, I don't really think it's doing what it seems to be doing. Consider case:

loop:
  iv = phi [start][iv.next]
  x = load volatile ...  // Loop-variant load
  iv.next = shl iv, x

I didn't really run a test, but from the code I cannot figure why it wouldn't be recognized as a simple recurrence. I guess the loop-invariance check is missing inside this helper, not in your current patch. The logic there could also be simplified if we gave it LoopInfo with notion of latch (we wouldn't need 2 iterations in loop there). Please consider this refactoring.

mkazantsev requested changes to this revision.Mar 12 2021, 1:04 AM
This revision now requires changes to proceed.Mar 12 2021, 1:04 AM

Regarding the helper you are using: looking into matchSimpleRecurrence, I don't really think it's doing what it seems to be doing. Consider case:

loop:
  iv = phi [start][iv.next]
  x = load volatile ...  // Loop-variant load
  iv.next = shl iv, x

I didn't really run a test, but from the code I cannot figure why it wouldn't be recognized as a simple recurrence. I guess the loop-invariance check is missing inside this helper, not in your current patch. The logic there could also be simplified if we gave it LoopInfo with notion of latch (we wouldn't need 2 iterations in loop there). Please consider this refactoring.

The lack of an invariant check in the matching routine is deliberate. Please see usage .e.g. in computeKnownBits. Not all callers want the restriction on step being loop invariant.

In this particular case, you are correct that there is a missing invariance check. I'd originally written this for constant step (which are trivially invariant), but forgot to add back the invariance check when generalizing. Thanks for the catch!

reames added inline comments.Mar 12 2021, 1:00 PM
llvm/lib/Analysis/ScalarEvolution.cpp
5663

You're right, this can become an assert. It made since before some refactoring I did to the code before commit. Not so much anymore. Will fix.

5671

I'd prefer to leave this to when someone actually generalizes for lshr and ashr.

5673

We are, good catch.

reames added inline comments.Mar 12 2021, 1:06 PM
llvm/lib/Analysis/ScalarEvolution.cpp
5673

Actually, now that I think about it further, we don't need the check.

Consider the non-invariant case. The known bits must hold for step on each iteration individually. As a result, they must be a conservative result for the value of step on all iterations. As such, if step is loop variant, we'll get a loose bound on the total step.

Instead of adding a bailout, I'll add a test for this case.

reames added inline comments.Mar 12 2021, 2:15 PM
llvm/lib/Analysis/ScalarEvolution.cpp
5663

Hm, funny story. It turns out this needs to be a bail out after all. Not because it should be, but because asserting it exposes a bug in LoopFusion. I'm putting a careful comment in the code and have filed PR49566 to track the issue.

reames updated this revision to Diff 330371.Mar 12 2021, 2:16 PM

address review comments

(highly suggest reading inline comments on review for context)

I still think that trickery of definition with invariant step should be emphasised, regardless of the bug you've pointed out.

llvm/lib/Analysis/ScalarEvolution.cpp
5673

The problem is not with this implementation, the problem is with the way how this is defined. What I understood from the comments around is that a shift recurrence is something analogous to the add recurrence. However, add recurrence assumes that all components of it are loop-invariant. If you run opt -analyze -scalar-evolution on

declare i1 @cond()

define void @foo(i32* %p) {
entry:
  %x = load volatile i32, i32* %p
  br label %loop

loop:
  %iv = phi i32 [0, %entry], [%iv.next, %loop]
  %iv.next = add i32 %iv, %x
  %cond = call i1 @cond()
  br i1 %cond, label %loop, label %done

done:
  ret void
}

then you get addrec for %iv. But if you modify test to

declare i1 @cond()

define void @foo(i32* %p) {
entry:
  br label %loop

loop:
  %iv = phi i32 [0, %entry], [%iv.next, %loop]
  %x = load volatile i32, i32* %p
  %iv.next = add i32 %iv, %x
  %cond = call i1 @cond()
  br i1 %cond, label %loop, label %done

done:
  ret void
}

then IV is a SCEVUnknown. The first comment inside this function suggests that what you are trying to recognize is analogous to the AddRec, but in fact it's not.

I don't say that the way how it works is wrong, I'm saying that if the pattern recognized is semantically different from AddRec, you can't just say that you are looking for something like "a simple recurrence of the form: <start, ShiftOp, Step>". This needs a better clarification of what Step actually is.

My preference is to avoid any kind of inconsistency in way how we define different recurrencies. If you support invariant step here, it should also be supported for AddRec beforehand.

5913

nit: remove

mkazantsev added inline comments.Mar 14 2021, 9:33 PM
llvm/lib/Analysis/ScalarEvolution.cpp
5673

My preference is to avoid any kind of inconsistency in way how we define different recurrencies. If you support invariant step here, it should also be supported for AddRec beforehand.

sorry, I mean variant step off course.

Max, on the terminology bit, I see your point. I've spent some time thinking about it, and haven't really come up with anything better naming wise. What we have is a recurrence with one extra free variable. Said another way, we have a cyclic dependence through the phi and one binop. Do you have any suggestions on naming here? The best I've got is matchSimpleRecurrenceWithOneFreeVariable but that's a bit ugly to say the least. I also considered matchNearRecurrence, but well, defining "near" is ugly too.

I would prefer to separate the naming point from this review though. While I agree we should change it, it's an issue with existing code and not specific to this use. Would you be okay with moving forward on this review under the understanding that I tackle the naming/terminology issue separately in the very near future?

mkazantsev accepted this revision.Mar 18 2021, 10:06 PM

We can either name it separately (and honestly, I don't think there is a better name than shift recurrence), but please make it crystal clear in the comments that this thing *looks* very much like addrec, but there is a tricky difference that it may have a variant step. Many algorithms for AddRecs rely on invariance of arguments explicitly or implicitly. And if someone ever wants to generalize them with your new recurrencies, they will keep falling into this pithole.

Please add either

  • A Loop Invariant check
  • A comment highlighting that the shift value might not be an invariant

Either should be fine, but the former is more reliable.
Otherwise, looks good.

This revision is now accepted and ready to land.Mar 18 2021, 10:06 PM

We can either name it separately (and honestly, I don't think there is a better name than shift recurrence).

I added a clarifying description to the ValueTracking header in 9c16621c0. Will also update the patch with an explicit comment on the difference with addrec.

This revision was landed with ongoing or failed builds.Mar 22 2021, 9:39 AM
This revision was automatically updated to reflect the committed changes.
uabelho added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
5678

I've seen this assertion fail when running

opt -slsr

I wrote
https://bugs.llvm.org/show_bug.cgi?id=49768
about it.

JFYI, AFK for next few hours.  If this is causing problematic breakage,
feel free to revert.  I'll look at this later today.

Philip

reames added a comment.Apr 5 2021, 8:59 AM

JFYI, AFK for next few hours.  If this is causing problematic breakage,
feel free to revert.  I'll look at this later today.

Philip

JFYI, the reported bug is fixed.

uabelho added inline comments.Apr 6 2021, 5:27 AM
llvm/lib/Analysis/ScalarEvolution.cpp
5678

I reopened
https://bugs.llvm.org/show_bug.cgi?id=49768
due to the assertion triggering again for another

opt -slsr

case.