This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Make howFarToZero produce a smaller max backedge-taken count
ClosedPublic

Authored by efriedma on Jan 5 2017, 7:33 PM.

Diff Detail

Repository
rL LLVM

Event Timeline

efriedma updated this revision to Diff 83340.Jan 5 2017, 7:33 PM
efriedma retitled this revision from to [SCEV] Make howFarToZero produce a smaller max backedge-taken count.
efriedma updated this object.
efriedma added reviewers: sanjoy, silviu.baranga.
efriedma set the repository for this revision to rL LLVM.
efriedma added a subscriber: llvm-commits.
sbaranga added inline comments.
lib/Analysis/ScalarEvolution.cpp
7217 ↗(On Diff #83340)

This looks correct to me, but I think it could use a comment.

Do we only need to match against Distance + 1 because this is what we typically get from rotating the loop? Otherwise I think this could be generalized to Distance + constant, but we would need to do some work to find the value of the constant.

efriedma added inline comments.Jan 10 2017, 10:26 AM
lib/Analysis/ScalarEvolution.cpp
7217 ↗(On Diff #83340)

The transform is correct because we prove "Distance + 1" doesn't overflow. I'll add a comment explaining that.

You could generalize this to "Distance + Constant", but it's not clear what sort of pattern we would be looking for. (Also, at that point, it would probably be better to just write a context-sensitive version of getUnsignedRange().)

efriedma updated this revision to Diff 83834.Jan 10 2017, 11:30 AM
efriedma removed rL LLVM as the repository for this revision.

Update comments; add additional testcase.

sanjoy requested changes to this revision.Jan 10 2017, 1:51 PM
sanjoy edited edge metadata.

I'm happy with the direction, but I think this is changing the code in two ways at once. I'd rather have the two changes clearly spelt out as different checkins.

lib/Analysis/ScalarEvolution.cpp
7210 ↗(On Diff #83834)

I think we should really split this change up into two.

  • First the cleanup to handle count-up loops and count-down loops more uniformly (i.e. first reduce to {D,+,-1} and then compute getUnsignedMax(D)) than the current ad-hoc logic. IIUC, this change is already an improvement for cases like {X,+,1} != 0 if range(X) == [-5, 1) (say).
  • Add the smartness around unsigned_max(D) == unsigned_max(D + 1) - 1 on no overflow in a separate commit.
7216 ↗(On Diff #83340)

s/getAddExpr(Distance, getOne(Distance->getType()))/getAddExpr(Distance, One)/ ?

7219 ↗(On Diff #83340)

Why are you checking (Distance + 1) != 0 instead of Distance != -1? I'd find the latter more straightforward.

This revision now requires changes to proceed.Jan 10 2017, 1:51 PM
sanjoy added inline comments.Jan 10 2017, 1:52 PM
lib/Analysis/ScalarEvolution.cpp
7219 ↗(On Diff #83340)

In case I gave the wrong impression, I don't specifically care about checking (Distance + 1) != 0 vs. Distance != -1. If you find the former more straightforward, then I'm okay too.

efriedma updated this revision to Diff 83864.Jan 10 2017, 1:59 PM
efriedma updated this object.
efriedma edited edge metadata.
efriedma set the repository for this revision to rL LLVM.

Split so this change just contains the cleanup. (This is enough to fix ne_max_trip_count_1.)

efriedma added inline comments.Jan 10 2017, 2:01 PM
lib/Analysis/ScalarEvolution.cpp
7210 ↗(On Diff #83834)

Okay, uploaded the first part of the split version.

7219 ↗(On Diff #83340)

I went with (Distance + 1) != 0 because it matches the condition which is likely to be written in the IR.

sanjoy accepted this revision.Jan 10 2017, 2:42 PM
sanjoy edited edge metadata.

lgtm

lib/Analysis/ScalarEvolution.cpp
7209 ↗(On Diff #83864)

I'd add a one-liner here:

// Solve {Distance,+,-1} == 0.
This revision is now accepted and ready to land.Jan 10 2017, 2:42 PM
This revision was automatically updated to reflect the committed changes.