This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Canonicalize range test idiom
ClosedPublic

Authored by nikic on Nov 7 2021, 9:35 AM.

Details

Summary

InstCombine converts range tests of the form (X > C1 && X < C2) or (X < C1 || X > C2) into checks of the form (X + C3 < C4) or (X + C3 > C4). It is possible to express all range tests in either of these forms (with different choices of constants), but currently neither of them is considered canonical. We may have equivalent range tests using either ult or ugt.

This proposes to canonicalize all range tests to use ult. An alternative would be to canonicalize to either ult or ugt depending on the specific constants involved -- e.g. in practice we currently generate ult for && style ranges and ugt for || style ranges when going through the insertRangeTest() helper. In fact, the "clamp like" fold was relying on this, which is why I had to tweak it to not assume whether inversion is needed based on just the predicate.

Proof: https://alive2.llvm.org/ce/z/_SP_rQ

Diff Detail

Event Timeline

nikic created this revision.Nov 7 2021, 9:35 AM
nikic requested review of this revision.Nov 7 2021, 9:35 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 7 2021, 9:35 AM
nikic edited the summary of this revision. (Show Details)Nov 7 2021, 9:38 AM
This revision is now accepted and ready to land.Nov 7 2021, 9:46 AM
xbolva00 added inline comments.
llvm/test/Transforms/InstCombine/2006-12-15-Range-Test.ll
58

Maybe prefer ugt? To keep positive numbers. (Common cases).

nikic added inline comments.Nov 7 2021, 10:06 AM
llvm/test/Transforms/InstCombine/2006-12-15-Range-Test.ll
58

Using ugt will not prefer positive numbers in general, it depends on the tested range. I did check that variant, and the impact is about the same, just for different test cases.

We would have to canonicalize to ugt/ult based on some heuristic involving the specific constants required, which seems a bit unusual for InstCombine.

xbolva00 added inline comments.Nov 7 2021, 10:11 AM
llvm/test/Transforms/InstCombine/2006-12-15-Range-Test.ll
58

Ok.

spatel accepted this revision.Nov 8 2021, 6:21 AM

LGTM
If I'm seeing it correctly, this is currently limited to ignore a canonical umax pattern from somewhere higher in the callers. We must have a test for that pattern somewhere, so it would be nice to put an explanatory comment on that (currently negative) test along with this patch.

This revision was landed with ongoing or failed builds.Nov 8 2021, 12:15 PM
This revision was automatically updated to reflect the committed changes.
yiranwang added a subscriber: yiranwang.EditedOct 2 2023, 10:17 AM

This change is problematic, as something like
if (x >= '0' && x <= '9')
before this change is "if (x - '0‘ <u 10)", and now it becomes "if (245 <u x - '9')".
The later one is more expensive, as the ZExt followed by ADD(of type i32) is not removable, say, if the ISA does not have native i8-ADD instruction. While the former form is just OK, and the ZExt is removable.
So at least, if the type does not have native addition instruction, we should not do this. Or maybe, just don't do this in general, as no cannonicalization in that sense is possible.
Another issue is that some ISA may not like big constant integer. ISEL may be able to handle that, although.

Herald added a project: Restricted Project. · View Herald TranscriptOct 2 2023, 10:17 AM