This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Limited support for unsigned preds in isImpliedViaOperations
ClosedPublic

Authored by mkazantsev on Sep 22 2020, 3:59 AM.

Details

Summary

The logic there only considers SLT/SGT predicates. We can use the same logic
for proving ULT/UGT predicates if all involved values are non-negative.

Adding full-scale support for unsigned might be challenging because of code amount,
so we can consider this in the future.

Diff Detail

Event Timeline

mkazantsev created this revision.Sep 22 2020, 3:59 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 22 2020, 3:59 AM
mkazantsev requested review of this revision.Sep 22 2020, 3:59 AM

Added ULT check showing use of D87890

reames requested changes to this revision.Sep 28 2020, 11:14 AM
reames added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
10158

I'm confused by this check, it seems overly complicated given the comment? Why is this simply not:
if (isKnownNonNegative(LHS) && isKnownNonNegative(RHS) &&

 isKnownNonNegative(FoundLHS) && isKnownNonNegative(FoundRHS)) {
Pred = ICmpInst::getSignedPredicate(Pred);

}

This revision now requires changes to proceed.Sep 28 2020, 11:14 AM
mkazantsev added inline comments.Sep 29 2020, 2:17 AM
llvm/lib/Analysis/ScalarEvolution.cpp
10158

Because non-negativity of LHS and RHS is not known.

mkazantsev added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
10158

We need an extra fact SignedPred FoundLHS FoundRHS to prove it. And we only have this fact if we know Pred FoundLHS FoundRHS && isKnownNonNegative(FoundLHS) && isKnownNonNegative(FoundRHS).

reames added inline comments.Sep 29 2020, 11:50 AM
llvm/lib/Analysis/ScalarEvolution.cpp
10158

If FoundLHS and FoundRHS are both non-negative, then all unsigned predicates are equivalent to their signed variants. There's no separate fact needed for that. Same for LHS and RHS.

Max, it may help if we talked offline here. I can't tell if you're saying my argument is wrong, or that the example your trying to optimize doesn't have sufficient information to establish the non-negative facts. Please either talk to me offline, or be very specific in your next response.

lebedev.ri requested changes to this revision.Sep 29 2020, 12:46 PM
lebedev.ri added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
10158

If FoundLHS and FoundRHS are both non-negative, then all unsigned predicates are equivalent to their signed variants. There's no separate fact needed for that. Same for LHS and RHS.

I agree. The actual rules are: (for any signed/unsigned pred, they just have to be identical)
https://rise4fun.com/Alive/P9Il

Let me elaborate a bit.

We are trying to prove LHS >u RHS, knowing that FoundLHS >u FoundRHS. We want to somehow reduce this to an equivalent >s proof.

You are correct that if we know that all LHS, RHS, FoundLHS and FoundRHS are non-negative, we can simply call isImpliedViaOperations(>s, LHS, RHS, FoundLHS, FoundRHS).

However, we might not be able to prove isKnownNonNegative(LHS) or isKnownNonNegative(RHS). Imagine the case when we have proved isKnownNonNegative(FoundLHS) and isKnownNonNegative(FoundRHS), but cannot do so for neither LHS nor RHS. In this case (and this is what my patch is about), we should try to infer non-negativity of LHS and RHS from FoundLHS > FoundRHS. And the way to do it is to call isImpliedViaOperations(>s, LHS, -1, FoundLHS, FoundRHS) and isImpliedViaOperations(>s, RHS, -1, FoundLHS, FoundRHS). What you proposed is just a subset of what can be proved with implication.

I can split this change into two pieces: first piece with trivially provable non-negativity of LHS and RHS, and the second case is when we cannot prove this trivially and should use implication. Does it make sense now?

..The only problem is that it is not possible to create a test for which isKnownNonNegative would actually return true for LHS beign a + b.

mkazantsev updated this revision to Diff 295486.EditedOct 1 2020, 1:26 AM
  • Simplified code, making it crystal clear that it only works for ULT/UGT;
  • Simplified test to show what we are trying to prove without redundant entities;
  • Checks with isKnownNonNegative(LHS/RHS) do not work, because if these facts are known, we never reach this code and prove the required fact with other means. But more commonly, it is just not known even in simplest cases. For example, for %x = load ... {1, SINT_MAX}, it cannot prove that add(x, -1) is non-negative. We could fix that, but it's a problem which has nothing to do with what I am trying to achieve here.
reames accepted this revision.Oct 1 2020, 10:56 AM

I'd prefer to have this split, but not enough to insist on it. With improved explanation and comments, LGTM.

This revision was not accepted when it landed; it landed in state Needs Review.Oct 1 2020, 8:40 PM
This revision was automatically updated to reflect the committed changes.
xbolva00 added a subscriber: xbolva00.EditedOct 2 2020, 1:44 AM

https://llvm-compile-time-tracker.com/compare.php?from=f29645e7afdbb8d1fc2dd603c0b128bac055625c&to=b8ac19cf1cca5faec8b4404bb0f666cb63c9e1de&stat=instructions

Compile time regressed a bit but I see no binary changes so.. how useful is this in practise? Any benchmark data to justify small regression?

reames added a comment.Oct 2 2020, 8:21 AM

https://llvm-compile-time-tracker.com/compare.php?from=f29645e7afdbb8d1fc2dd603c0b128bac055625c&to=b8ac19cf1cca5faec8b4404bb0f666cb63c9e1de&stat=instructions

Compile time regressed a bit but I see no binary changes so.. how useful is this in practise? Any benchmark data to justify small regression?

I'll assert this is justified. Only being able to handle signed predicates when we canonicalize to unsigned is a bit of a problem. :)

Can you be more specific about how much compile time regressed and on what?

lebedev.ri added inline comments.Oct 2 2020, 8:30 AM
llvm/lib/Analysis/ScalarEvolution.cpp
10172

I'll look into adding a method to ConstantRange to find compatible [un]signed predicate.