[WIP][ScalarEvolution] Merge howManyGreaterThans with howManyLessThans.

[efriedma]

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.

[mkazantsev]

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

llvm/lib/Analysis/ScalarEvolution.cpp

11540

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.

[nikic]

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

11553

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]

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.

[efriedma]

llvm/lib/Analysis/ScalarEvolution.cpp

11553

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

[efriedma]

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

[efriedma]

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]

Added tests. A couple more cleanups.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

11401

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

11530

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]

llvm/lib/Analysis/ScalarEvolution.cpp

11530

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]

Show simplified version. Not ready to merge.

[reames]

@efriedma Just to note, I think we've hit the point where howManyLessThans isn't getting any more stable in the near future, and howManyGreaterThans is at least as buggy. If you wanted to rebase this, I'd be up for reviewing with intent to land in near future.

[reames]

Pending action by author, please request review once ready for more discussion. Just getting this off my active review queue.

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.