[InstCombine] reduce test-for-overflow of shifted value

[tianz]

Summary

Refer to issue #57338. The added code makes the following transformations:
For unsigned predicates / eq / ne:

icmp pred (x << 1), x --> icmp getSignedPredicate(pred) x, 0
icmp pred x, (x << 1) --> icmp getSignedPredicate(pred) 0, x

Some examples:
https://alive2.llvm.org/ce/z/ckn4cj
https://alive2.llvm.org/ce/z/h-4bAQ

[tianz]

Rewrote with m_Specific

[tianz]

This comment was removed by tianz.

[tianz]

Removed unnecessary parentheses

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

4556–4557

Nice! I couldn't tell if there was a simple way to express the transform for all predicates, but that looks right.
To verify, please add at least a couple of Alive2 proof links to the patch summary.

llvm/test/Transforms/InstCombine/icmp-shl-1-overflow.ll

13

1. We can reduce the tests by 2x without losing much coverage: drop all of the existing vector tests, and change some of the scalar tests to vector types. You can also vary the scalar/element type from i8 to show that the transform doesn't care what the type is (can even use strange types like <3 x i7>).

2. For vectors, you can replace a "1" element with "poison" to show that the transform works even if the vector constant is not fully defined (has "don't care" elements).

3. We also want at least a couple of negative tests to verify that the transform does not fire when it is not intended (for example, a test with a signed predicate and a test where the shift is by something other than "1").

4. Create an extra use of the shl value in at least one test, so we know that the transform works independent of other uses.

5. If some other transform alters the code before it reaches the new transform, then adjustments will be needed (grep for "thwart complexity-based canonicalization" in this test dir to how to work around operands that get commuted.

Once you have the tests updated, let's pre-commit them with the baseline CHECK lines. That way we can confirm that we are testing the expected patterns.

[tianz]

Updated tests according to review comments

[tianz]

llvm/test/Transforms/InstCombine/icmp-shl-1-overflow.ll

13

Thanks for all the suggestions! I've updated the tests according to #1 - #4. I don't find "thwart complexity-based canonicalization" necessary, but definitely correct me if I'm wrong.

For some of the tests, the result code is actually altered after the transform I added, so I had to modify the check to compare against the altered code (e.g. I transform uge i8 %x, %add into sge i8 0, %x, but the code is then altered by some other transform and eventually becomes slt i8 %x, 1 ) I'm sure what's the best way to handle that in the tests.

Regarding your last comment, I'm not exactly sure what you meant. Would you mind giving some examples on how to add the baseline CHECK lines?

Thanks a lot!

[spatel]

llvm/test/Transforms/InstCombine/icmp-shl-1-overflow.ll

13

Baseline tests: create a patch with only these tests and the current CHECK lines after running "utils/update_test_checks.py".
Then, we'll commit those to the main branch to show any transforms we already do (before the code change in this patch).
After that, rebase/update this patch after applying the code change. This patch will then show the test diffs created directly by this patch.

That helps in a few ways: it makes it clear what current output looks like, it makes the review easier by showing diffs, and we won't lose test coverage even if this patch has to be reverted for some reason.

If you don't have commit privileges, you can post the baseline tests as is its own review here on Phabricator, and I can push it for you.

The tests with commuted operands (half of the tests) are not exercising the code path that you want because the operands are changed before we reach the new transform. Example:

define <2 x i1> @icmp_shl_ugt_2(<2 x i32> %x) {
  %add = shl <2 x i32> %x, <i32 1, i32 1>
  %cmp = icmp ugt <2 x i32> %x, %add
  ret <2 x i1> %cmp
}

% opt -instcombine icmp.ll -S
...
define <2 x i1> @icmp_shl_ugt_2(<2 x i32> %x) {
  %add = shl <2 x i32> %x, <i32 1, i32 1>
  %cmp = icmp ult <2 x i32> %add, %x  ; these got switched based on operand "complexity"
  ret <2 x i1> %cmp
}

[tianz]

llvm/test/Transforms/InstCombine/icmp-shl-1-overflow.ll

13

Thanks for the explanation! Here are the baseline tests https://reviews.llvm.org/D133182. I updated them with "thwart complexity-based canonicalization" when %add is the second operand. Please push it for me it they look good to you, since I don't have commit privileges yet. I'll then update the tests here as well!

[tianz]

llvm/test/Transforms/InstCombine/icmp-shl-1-overflow.ll

13

I have updated the tests here as well!

[spatel]

LGTM

llvm/test/Transforms/InstCombine/icmp-shl-1-overflow.ll

117

You changed this test (and one below) because there's a follow-on transform that would fold the add into the equality comparison?
It's fine to demonstrate a sequence of transforms as long as we're starting from the transform in this patch.

In fact, this result shows that we missed another optimization - the result is 0 when the input is signed > 42 or signed < -42, and that can be reduced to:
https://alive2.llvm.org/ce/z/erdvwc

[spatel]

llvm/test/Transforms/InstCombine/icmp-shl-1-overflow.ll

117

Filed that here:
https://github.com/llvm/llvm-project/issues/57338

[spatel]

llvm/test/Transforms/InstCombine/icmp-shl-1-overflow.ll

117

Oops - copied the wrong link. Should be:
https://github.com/llvm/llvm-project/issues/57542

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (BO0) {
     auto BitwiseAnd = m_c_And(m_Value(), LSubOne);
 
     if (match(BO0, BitwiseAnd) && Pred == ICmpInst::ICMP_ULT) {
       auto *Zero = Constant::getNullValue(BO0->getType());
       return new ICmpInst(ICmpInst::ICMP_NE, Op1, Zero);
     }
   }
 
+  // For unsigned predicates / eq / ne:
+  // icmp pred (x << 1), x --> icmp getSignedPredicate(pred) x, 0
+  // icmp pred x, (x << 1) --> icmp getSignedPredicate(pred) 0, x
+  if (!ICmpInst::isSigned(Pred)) {
+    if (match(Op0, m_Shl(m_Specific(Op1), m_One())))
+      return new ICmpInst(ICmpInst::getSignedPredicate(Pred), Op1,
+                          Constant::getNullValue(Op1->getType()));
+    else if (match(Op1, m_Shl(m_Specific(Op0), m_One())))
+      return new ICmpInst(ICmpInst::getSignedPredicate(Pred),
+                          Constant::getNullValue(Op0->getType()), Op0);
+  }
+
   if (Value *V = foldMultiplicationOverflowCheck(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = foldICmpWithLowBitMaskedVal(I, Builder))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = foldICmpWithTruncSignExtendedVal(I, Builder))
     return replaceInstUsesWith(I, V);

llvm/test/Transforms/InstCombine/icmp-shl-1-overflow.ll

+; RUN: opt < %s -passes=instcombine -S | FileCheck %s
+
+define i1 @icmp_shl_ugt_1(i8 %x) {
+; CHECK-LABEL: @icmp_shl_ugt_1(
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[X:%.*]], 0
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %add = shl i8 %x, 1
+  %cmp = icmp ugt i8 %add, %x
+  ret i1 %cmp
+}
+
+define <2 x i1> @icmp_shl_ugt_1_vec(<2 x i8> %x) {
+; CHECK-LABEL: @icmp_shl_ugt_1_vec(
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt <2 x i8> [[X:%.*]], zeroinitializer
+; CHECK-NEXT:    ret <2 x i1> [[R]]
+;
+  %add = shl <2 x i8> %x, <i8 1, i8 1>
+  %cmp = icmp ugt <2 x i8> %add, %x
+  ret <2 x i1> %cmp
+}
+
+define i1 @icmp_shl_ugt_2(i8 %x) {
+; CHECK-LABEL: @icmp_shl_ugt_2(
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i8 [[X:%.*]], 0
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %add = shl i8 %x, 1
+  %cmp = icmp ugt i8 %x, %add
+  ret i1 %cmp
+}
+
+define <2 x i1> @icmp_shl_ugt_2_vec(<2 x i8> %x) {
+; CHECK-LABEL: @icmp_shl_ugt_2_vec(
+; CHECK-NEXT:    [[R:%.*]] = icmp slt <2 x i8> [[X:%.*]], zeroinitializer
+; CHECK-NEXT:    ret <2 x i1> [[R]]
+;
+  %add = shl <2 x i8> %x, <i8 1, i8 1>
+  %cmp = icmp ugt <2 x i8> %x, %add
+  ret <2 x i1> %cmp
+}
+
+define i1 @icmp_shl_uge_1(i8 %x) {
+; CHECK-LABEL: @icmp_shl_uge_1(
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[X:%.*]], -1
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %add = shl i8 %x, 1
+  %cmp = icmp uge i8 %add, %x
+  ret i1 %cmp
+}
+
+define <2 x i1> @icmp_shl_uge_1_vec(<2 x i8> %x) {
+; CHECK-LABEL: @icmp_shl_uge_1_vec(
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt <2 x i8> [[X:%.*]], <i8 -1, i8 -1>
+; CHECK-NEXT:    ret <2 x i1> [[R]]
+;
+  %add = shl <2 x i8> %x, <i8 1, i8 1>
+  %cmp = icmp uge <2 x i8> %add, %x
+  ret <2 x i1> %cmp
+}
+
+define i1 @icmp_shl_uge_2(i8 %x) {
+; CHECK-LABEL: @icmp_shl_uge_2(
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i8 [[X:%.*]], 1
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %add = shl i8 %x, 1
+  %cmp = icmp uge i8 %x, %add
+  ret i1 %cmp
+}
+
+define <2 x i1> @icmp_shl_uge_2_vec(<2 x i8> %x) {
+; CHECK-LABEL: @icmp_shl_uge_2_vec(
+; CHECK-NEXT:    [[R:%.*]] = icmp slt <2 x i8> [[X:%.*]], <i8 1, i8 1>
+; CHECK-NEXT:    ret <2 x i1> [[R]]
+;
+  %add = shl <2 x i8> %x, <i8 1, i8 1>
+  %cmp = icmp uge <2 x i8> %x, %add
+  ret <2 x i1> %cmp
+}
+
+define i1 @icmp_shl_ult_1(i8 %x) {
+; CHECK-LABEL: @icmp_shl_ult_1(
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i8 [[X:%.*]], 0
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %add = shl i8 %x, 1
+  %cmp = icmp ult i8 %add, %x
+  ret i1 %cmp
+}
+
+define <2 x i1> @icmp_shl_ult_1_vec(<2 x i8> %x) {
+; CHECK-LABEL: @icmp_shl_ult_1_vec(
+; CHECK-NEXT:    [[R:%.*]] = icmp slt <2 x i8> [[X:%.*]], zeroinitializer
+; CHECK-NEXT:    ret <2 x i1> [[R]]
+;
+  %add = shl <2 x i8> %x, <i8 1, i8 1>
+  %cmp = icmp ult <2 x i8> %add, %x
+  ret <2 x i1> %cmp
+}
+
+define i1 @icmp_shl_ult_2(i8 %x) {
+; CHECK-LABEL: @icmp_shl_ult_2(
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[X:%.*]], 0
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %add = shl i8 %x, 1
+  %cmp = icmp ult i8 %x, %add
+  ret i1 %cmp
+}
+
+define <2 x i1> @icmp_shl_ult_2_vec(<2 x i8> %x) {
+; CHECK-LABEL: @icmp_shl_ult_2_vec(
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt <2 x i8> [[X:%.*]], zeroinitializer
+; CHECK-NEXT:    ret <2 x i1> [[R]]
+;
+  %add = shl <2 x i8> %x, <i8 1, i8 1>
+  %cmp = icmp ult <2 x i8> %x, %add
+  ret <2 x i1> %cmp
+}
+
+define i1 @icmp_shl_ule_1(i8 %x) {
+; CHECK-LABEL: @icmp_shl_ule_1(
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i8 [[X:%.*]], 1
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %add = shl i8 %x, 1
+  %cmp = icmp ule i8 %add, %x
+  ret i1 %cmp
+}
+
+define <2 x i1> @icmp_shl_ule_1_vec(<2 x i8> %x) {
+; CHECK-LABEL: @icmp_shl_ule_1_vec(
+; CHECK-NEXT:    [[R:%.*]] = icmp slt <2 x i8> [[X:%.*]], <i8 1, i8 1>
+; CHECK-NEXT:    ret <2 x i1> [[R]]
+;
+  %add = shl <2 x i8> %x, <i8 1, i8 1>
+  %cmp = icmp ule <2 x i8> %add, %x
+  ret <2 x i1> %cmp
+}
+
+define i1 @icmp_shl_ule_2(i8 %x) {
+; CHECK-LABEL: @icmp_shl_ule_2(
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[X:%.*]], -1
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %add = shl i8 %x, 1
+  %cmp = icmp ule i8 %x, %add
+  ret i1 %cmp
+}
+
+define <2 x i1> @icmp_shl_ule_2_vec(<2 x i8> %x) {
+; CHECK-LABEL: @icmp_shl_ule_2_vec(
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt <2 x i8> [[X:%.*]], <i8 -1, i8 -1>
+; CHECK-NEXT:    ret <2 x i1> [[R]]
+;
+  %add = shl <2 x i8> %x, <i8 1, i8 1>
+  %cmp = icmp ule <2 x i8> %x, %add
+  ret <2 x i1> %cmp
+}
+
+define i1 @icmp_shl_eq_1(i8 %x) {
+; CHECK-LABEL: @icmp_shl_eq_1(
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[X:%.*]], 0
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %add = shl i8 %x, 1
+  %cmp = icmp eq i8 %add, %x
+  ret i1 %cmp
+}
+
+define <2 x i1> @icmp_shl_eq_1_vec(<2 x i8> %x) {
+; CHECK-LABEL: @icmp_shl_eq_1_vec(
+; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i8> [[X:%.*]], zeroinitializer
+; CHECK-NEXT:    ret <2 x i1> [[R]]
+;
+  %add = shl <2 x i8> %x, <i8 1, i8 1>
+  %cmp = icmp eq <2 x i8> %add, %x
+  ret <2 x i1> %cmp
+}
+
+define i1 @icmp_shl_eq_2(i8 %x) {
+; CHECK-LABEL: @icmp_shl_eq_2(
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[X:%.*]], 0
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %add = shl i8 %x, 1
+  %cmp = icmp eq i8 %x, %add
+  ret i1 %cmp
+}
+
+define <2 x i1> @icmp_shl_eq_2_vec(<2 x i8> %x) {
+; CHECK-LABEL: @icmp_shl_eq_2_vec(
+; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i8> [[X:%.*]], zeroinitializer
+; CHECK-NEXT:    ret <2 x i1> [[R]]
+;
+  %add = shl <2 x i8> %x, <i8 1, i8 1>
+  %cmp = icmp eq <2 x i8> %x, %add
+  ret <2 x i1> %cmp
+}
+
+define i1 @icmp_shl_ne_1(i8 %x) {
+; CHECK-LABEL: @icmp_shl_ne_1(
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[X:%.*]], 0
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %add = shl i8 %x, 1
+  %cmp = icmp ne i8 %add, %x
+  ret i1 %cmp
+}
+
+define <2 x i1> @icmp_shl_ne_1_vec(<2 x i8> %x) {
+; CHECK-LABEL: @icmp_shl_ne_1_vec(
+; CHECK-NEXT:    [[R:%.*]] = icmp ne <2 x i8> [[X:%.*]], zeroinitializer
+; CHECK-NEXT:    ret <2 x i1> [[R]]
+;
+  %add = shl <2 x i8> %x, <i8 1, i8 1>
+  %cmp = icmp ne <2 x i8> %add, %x
+  ret <2 x i1> %cmp
+}
+
+define i1 @icmp_shl_ne_2(i8 %x) {
+; CHECK-LABEL: @icmp_shl_ne_2(
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[X:%.*]], 0
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %add = shl i8 %x, 1
+  %cmp = icmp ne i8 %x, %add
+  ret i1 %cmp
+}
+
+define <2 x i1> @icmp_shl_ne_2_vec(<2 x i8> %x) {
+; CHECK-LABEL: @icmp_shl_ne_2_vec(
+; CHECK-NEXT:    [[R:%.*]] = icmp ne <2 x i8> [[X:%.*]], zeroinitializer
+; CHECK-NEXT:    ret <2 x i1> [[R]]
+;
+  %add = shl <2 x i8> %x, <i8 1, i8 1>
+  %cmp = icmp ne <2 x i8> %x, %add
+  ret <2 x i1> %cmp
+}