This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Use lshr in implications
ClosedPublic

Authored by mkazantsev on Dec 22 2021, 2:44 AM.

Details

Summary

This patch adds support for implication inference logic for the
following pattern:

lhs < (y >> z) <= y, y <= rhs --> lhs < rhs

We should be able to use the fact that value shifted to right is
not greater than the original value (provided it is non-negative).

Diff Detail

Event Timeline

mkazantsev created this revision.Dec 22 2021, 2:44 AM
mkazantsev requested review of this revision.Dec 22 2021, 2:44 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 22 2021, 2:44 AM
apilipenko added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
11476

Could you please outline the implication rule you are about to use here? Otherwise, it's not clear why you need this canonicalization.

11495

I find this comment cryptic (maybe this is because I'm not familiar with the lingo of the SCEV implication engine). I think what you meant here is:

LHS <u (shiftee >> shiftvalue) && shiftee <=u RHS ---> x <u RHS
LHS <=u (shiftee >> shiftvalue) && shiftee <=u RHS ---> x <=u RHS
LHS <s (shiftee >> shiftvalue) && shiftee >= 0 && shiftee <=s RHS ---> x <s RHS
LHS <=s (shiftee >> shiftvalue) && shiftee >= 0 && shiftee <=s RHS ---> x <=s RHS
mkazantsev marked 2 inline comments as done.
apilipenko added inline comments.Jan 18 2022, 5:18 PM
llvm/lib/Analysis/ScalarEvolution.cpp
11496–11505

Looking better, but now there is a mismatch between the code and the comment. You don't check for isKnownNonNegative for unsigned predicates, but the comment suggest that this is a precondition for all cases.

mkazantsev added inline comments.Jan 20 2022, 4:02 AM
llvm/lib/Analysis/ScalarEvolution.cpp
11496–11505

All numbers are non-negative w.r.t. unsigned predicate.

Updated comment.

apilipenko accepted this revision.Jan 24 2022, 4:10 AM
This revision is now accepted and ready to land.Jan 24 2022, 4:10 AM
This revision was automatically updated to reflect the committed changes.