[InstCombine] Canonicalize range test idiom
authorNikita Popov <nikita.ppv@gmail.com>
Sat, 6 Nov 2021 23:05:00 +0000 (00:05 +0100)
committerNikita Popov <nikita.ppv@gmail.com>
Mon, 8 Nov 2021 20:15:46 +0000 (21:15 +0100)
commit1376301c87274bccf5565eb892173442782b1de3
tree8bf00c12846b0cb8831e3dbe2d2238f812628083
parent6d44387e21a1b78eb7263f3610e7f11a42fecd24
[InstCombine] Canonicalize range test idiom

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

Differential Revision: https://reviews.llvm.org/D113366
17 files changed:
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
llvm/test/CodeGen/BPF/adjust-opt-icmp1.ll
llvm/test/CodeGen/BPF/adjust-opt-icmp2.ll
llvm/test/Transforms/InstCombine/2006-12-15-Range-Test.ll
llvm/test/Transforms/InstCombine/2007-03-21-SignedRangeTest.ll
llvm/test/Transforms/InstCombine/2008-08-05-And.ll
llvm/test/Transforms/InstCombine/and-or-icmps.ll
llvm/test/Transforms/InstCombine/canonicalize-signed-truncation-check.ll
llvm/test/Transforms/InstCombine/icmp-add.ll
llvm/test/Transforms/InstCombine/icmp-sub.ll
llvm/test/Transforms/InstCombine/icmp-topbitssame.ll
llvm/test/Transforms/InstCombine/load-cmp.ll
llvm/test/Transforms/InstCombine/minmax-fold.ll
llvm/test/Transforms/InstCombine/or.ll
llvm/test/Transforms/InstCombine/overflow.ll
llvm/test/Transforms/InstCombine/smulo.ll