This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Generalize MatchBinaryAddToConst to support non-add expressions.
ClosedPublic

Authored by fhahn on Jun 21 2021, 4:04 AM.

Details

Summary

This patch generalizes MatchBinaryAddToConst to support matching
(A + C1), (A + C2), instead of just matching (A + C1), A.

The existing cases can be handled by treating non-add expressions A as
A + 0.

Diff Detail

Event Timeline

fhahn created this revision.Jun 21 2021, 4:04 AM
fhahn requested review of this revision.Jun 21 2021, 4:04 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 21 2021, 4:04 AM
mkazantsev requested changes to this revision.Jun 21 2021, 6:01 AM

I think this is wrong.

llvm/lib/Analysis/ScalarEvolution.cpp
10106

Is lack of nsw in (X + C2) intentional? If yes, the counter-example to this is

X = SINT_MIN
C1 = 1
C2 = -1

(X + C1)<nsw> = SINT_MIN + 1 <= (X - 1) = SINT_MAX, but obviously C1 > C2.

This revision now requires changes to proceed.Jun 21 2021, 6:01 AM
mkazantsev added inline comments.Jun 21 2021, 6:04 AM
llvm/lib/Analysis/ScalarEvolution.cpp
10106

I'm not sure whether two-ways implication is required here, or one way implication is enough. It was two-ways in old code. If I'm wrong here, please let me know.

fhahn updated this revision to Diff 353351.Jun 21 2021, 6:15 AM

Add <nsw> and <nuw> to the sub-expressions where it was missing.

fhahn added inline comments.Jun 21 2021, 6:18 AM
llvm/lib/Analysis/ScalarEvolution.cpp
10106

The comment is missing <nsw> from the second expression, the actual checks enforce nsw for both (same for nuw below). I updated the comment.

I'm not sure whether two-ways implication is required here, or one way implication is enough. It was two-ways in old code. If I'm wrong here, please let me know.

The new reasoning should handle both previous checks I think , as, X s<= (X + C) treated as X + 0 s<= (X + C) and (X + C) s<= X is treated as (X + C) s<= X + 0

Ok, thanks for clarification. With this clarification looks fine. Please give me some time to run it through my fuzz corps.

For an optional follow up change, I believe we can avoid checking the wrap flags for one operand, if C1 and C2 share the same sign.

Consider:
(X + C1) s<= (X + C2)<nsw> if C1 s<= C2 and both are positive
(X + C1)<nsw> s<= (X + C2) if C1 s<= C2 and both are negative

If X + C2 does not signed wrap, and C1 s<= C2, then X+C1 also can not wrap if both are positive. As a result, we don't need to check for the wrap flag on LHS as we've proven it. The negative case is the inverse. The mixed sign case does require both checks as the two could overflow off different ends of the range. (Actually, can they? Is there any single value of X which you can add a value to and both wrap above and wrap below? Might be worth further thought.)

It's also worth noting that we can *disprove* cases here as well.

Consider:
// (X + C1)<nsw> s<= (X + C2)<nsw> == false if C1 s> C2.

This would require a change to the API (probably returning an optional bool), but might be interesting to short circuit later checks. Again, follow up change (if interested).

mkazantsev accepted this revision.Jun 21 2021, 8:33 PM

Ok, looks good!

This revision is now accepted and ready to land.Jun 21 2021, 8:33 PM

Looks good to me

fhahn added a comment.Jun 22 2021, 6:37 AM

For an optional follow up change, I believe we can avoid checking the wrap flags for one operand, if C1 and C2 share the same sign.

Thanks, I'll try to look into this as a follow-up.

Ok, thanks for clarification. With this clarification looks fine. Please give me some time to run it through my fuzz corps.

Thanks for the testing ahead of landing! I'll wait a day or so with landing, in case one of my earlier patches surfaces any issues.

fhahn updated this revision to Diff 354171.Jun 24 2021, 2:00 AM

Remove test changes that depend on D102834.