Page MenuHomePhabricator

[WIP][ScalarEvolution] Merge howManyGreaterThans with howManyLessThans.
Needs ReviewPublic

Authored by efriedma on Jun 10 2021, 4:46 PM.

Details

Summary

They're basically the same function, so let's not implement it twice. And they've fallen out of sync a bit: howManyLessThans has more features.

Still need to investigate:

  1. We're replacing smin/umin expressions with less efficient smax/umax expressions. Not sure how we're supposed to canonicalize here.
  2. The isLoopEntryGuardedByCond check is failing in places where it used to succeed.

Diff Detail

Event Timeline

efriedma created this revision.Jun 10 2021, 4:46 PM
efriedma requested review of this revision.Jun 10 2021, 4:46 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 10 2021, 4:46 PM
mkazantsev accepted this revision.Jun 11 2021, 2:46 AM

LGTM, but I think we can remove more copy-paste (see comment). Can go as follow-up.

llvm/lib/Analysis/ScalarEvolution.cpp
11813

Instead of this, can we just have smth like

ICmpInst::Predicate Cond = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
if (Invert)
  Cond = getSwappedPredicate(Cond);

? This piece still lppks copy-pastish.

This revision is now accepted and ready to land.Jun 11 2021, 2:46 AM
nikic added a subscriber: nikic.Jun 11 2021, 3:30 AM

There's a minor compile-time impact for this refactoring: https://llvm-compile-time-tracker.com/compare.php?from=57006d2f6d96d8a6836ae901218ed615071b3b8e&to=eca6ad2e31d754420fb114872bfc4060a698155e&stat=instructions It's okay, but you might want to cut down on the number of repeated/redundant getNotSCEV operations you perform. (They're not cached and known to be somewhat expensive.)

llvm/lib/Analysis/ScalarEvolution.cpp
11831

I'm confused by what you're doing here. getNotSCEV has a fold that does ~umin(~x, ~y) to umax(x, y), so the structure you're using here should get undone?

reames requested changes to this revision.Jun 11 2021, 9:55 AM

Several level of comments.

First, the LT handling is substantially more powerful than the GT handling. e.g. for unknown strides. Given that, this is definitely NOT nfc, and should have accompanying test changes.

Second, I'd prefer this not go in until the underlying LT miscompile we've been discussing is addressed. The GT code handles this case differently, and I'm not sure that pushing GT through this code is safe.

Third, I'd suggest an alternate interface. Please remove the IsSigned and Invert parameters, and just pass through the condition. These two properties can be derived inside the method.

This revision now requires changes to proceed.Jun 11 2021, 9:55 AM
efriedma added inline comments.Jun 11 2021, 10:11 AM
llvm/lib/Analysis/ScalarEvolution.cpp
11831

getNotSCEV(RHS) and getNotSCEV(Start) will likely be simplified.

efriedma updated this revision to Diff 352267.Jun 15 2021, 3:13 PM

Address review comments. (Still going to look at adding more tests.)

Note to self: differences between old and new gt codepath that need tests:

  1. Now compute max trip count even if RHS is not invariant.
  2. Now more aggressive with strides that are not known positive (although this codepath currently has issues...)
  3. Now use isUBOnWrap() for stride greater than one.
  4. Now compute MaxOrZero.
efriedma updated this revision to Diff 352302.Jun 15 2021, 5:32 PM

Added tests. A couple more cleanups.

reames added inline comments.Thu, Jul 8, 4:41 PM
llvm/lib/Analysis/ScalarEvolution.cpp
11669

For sanity sake, please actually set Pred here so that if we use it below, we get what we expect.

11812

I'd prefer to make it more powerful if possible.

A couple ideas, not sure if these work out or not:

  • Use SimplifyICmpOperands to canonicalize operands to isBasicBlockEntryGuardedByCond.
  • Teach isLoopEntryGuardedByCond to undo your not(lhs/rhs) transform.
efriedma added inline comments.Thu, Jul 8, 5:24 PM
llvm/lib/Analysis/ScalarEvolution.cpp
11812

There's actually another layer of complexity here on the main branch: if LHS/RHS are pointers, we have ptrtoint expressions floating around here, which isLoopEntryGuardedByCond also doesn't handle well.

After D105510 is merged, I can try messing with isLoopEntryGuardedByCond etc.

efriedma updated this revision to Diff 357401.Thu, Jul 8, 6:50 PM
efriedma retitled this revision from [ScalarEvolution] Merge howManyGreaterThans with howManyLessThans. to [WIP][ScalarEvolution] Merge howManyGreaterThans with howManyLessThans..
efriedma edited the summary of this revision. (Show Details)

Show simplified version. Not ready to merge.