[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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare void @use16(i16)
 declare void @usev4(<4 x i4>)
 
 define i1 @icmp_shl_ugt_1(i8 %x) {
 ; CHECK-LABEL: @icmp_shl_ugt_1(
-; CHECK-NEXT:    [[ADD:%.*]] = shl i8 [[X:%.*]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[ADD]], [[X]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add = shl i8 %x, 1
   %cmp = icmp ugt i8 %add, %x
   ret i1 %cmp
 }
 
 define <2 x i1> @icmp_shl_ugt_2(<2 x i32> %_x) {
 ; CHECK-LABEL: @icmp_shl_ugt_2(
 ; CHECK-NEXT:    [[X:%.*]] = add <2 x i32> [[_X:%.*]], <i32 42, i32 42>
-; CHECK-NEXT:    [[ADD:%.*]] = shl <2 x i32> [[X]], <i32 1, i32 1>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt <2 x i32> [[X]], [[ADD]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <2 x i32> [[X]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %x = add <2 x i32> <i32 42, i32 42>, %_x ; thwart complexity-based canonicalization
   %add = shl <2 x i32> %x, <i32 1, i32 1>
   %cmp = icmp ugt <2 x i32> %x, %add
   ret <2 x i1> %cmp
 }
 
 define <3 x i1> @icmp_shl_uge_1(<3 x i7> %x) {
 ; CHECK-LABEL: @icmp_shl_uge_1(
-; CHECK-NEXT:    [[ADD:%.*]] = shl <3 x i7> [[X:%.*]], <i7 1, i7 1, i7 1>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp uge <3 x i7> [[ADD]], [[X]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <3 x i7> [[X:%.*]], <i7 -1, i7 -1, i7 -1>
 ; CHECK-NEXT:    ret <3 x i1> [[CMP]]
 ;
   %add = shl <3 x i7> %x, <i7 1, i7 1, i7 1>
   %cmp = icmp uge <3 x i7> %add, %x
   ret <3 x i1> %cmp
 }
 
 define i1 @icmp_shl_uge_2(i5 %_x) {
 ; CHECK-LABEL: @icmp_shl_uge_2(
 ; CHECK-NEXT:    [[X:%.*]] = add i5 [[_X:%.*]], 10
-; CHECK-NEXT:    [[ADD:%.*]] = shl i5 [[X]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i5 [[X]], [[ADD]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i5 [[X]], 1
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %x = add i5 42, %_x ; thwart complexity-based canonicalization
   %add = shl i5 %x, 1
   %cmp = icmp uge i5 %x, %add
   ret i1 %cmp
 }
 
 define i1 @icmp_shl_ult_1(i16 %x) {
 ; CHECK-LABEL: @icmp_shl_ult_1(
 ; CHECK-NEXT:    [[ADD:%.*]] = shl i16 [[X:%.*]], 1
 ; CHECK-NEXT:    call void @use16(i16 [[ADD]])
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i16 [[ADD]], [[X]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i16 [[X]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add = shl i16 %x, 1
   call void @use16(i16 %add) ; extra use of shl
   %cmp = icmp ult i16 %add, %x
   ret i1 %cmp
 }
 
 define <4 x i1> @icmp_shl_ult_2(<4 x i4> %_x) {
 ; CHECK-LABEL: @icmp_shl_ult_2(
 ; CHECK-NEXT:    [[X:%.*]] = add <4 x i4> [[_X:%.*]], <i4 -6, i4 -6, i4 -6, i4 -6>
 ; CHECK-NEXT:    [[ADD:%.*]] = shl <4 x i4> [[X]], <i4 1, i4 1, i4 1, i4 1>
 ; CHECK-NEXT:    call void @usev4(<4 x i4> [[ADD]])
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult <4 x i4> [[X]], [[ADD]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <4 x i4> [[X]], zeroinitializer
 ; CHECK-NEXT:    ret <4 x i1> [[CMP]]
 ;
   %x = add <4 x i4> <i4 42, i4 42, i4 42, i4 42>, %_x ; thwart complexity-based canonicalization
   %add = shl <4 x i4> %x, <i4 1, i4 1, i4 1, i4 1>
   call void @usev4(<4 x i4> %add) ; extra use of shl
   %cmp = icmp ult <4 x i4> %x, %add
   ret <4 x i1> %cmp
 }
 
 define <2 x i1> @icmp_shl_ule_1(<2 x i8> %x) {
 ; CHECK-LABEL: @icmp_shl_ule_1(
-; CHECK-NEXT:    [[ADD:%.*]] = shl <2 x i8> [[X:%.*]], <i8 1, i8 poison>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ule <2 x i8> [[ADD]], [[X]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <2 x i8> [[X:%.*]], <i8 1, i8 1>
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %add = shl <2 x i8> %x, <i8 1, i8 poison>
   %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:    [[X:%.*]] = add i8 [[_X:%.*]], 42
-; CHECK-NEXT:    [[ADD:%.*]] = shl i8 [[X]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ule i8 [[X]], [[ADD]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i8 [[X]], -1
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %x = add i8 42, %_x ; thwart complexity-based canonicalization
   %add = shl i8 %x, 1
   %cmp = icmp ule i8 %x, %add
   ret i1 %cmp
 }
 
 define i1 @icmp_shl_eq_1(i8 %x) {
 ; CHECK-LABEL: @icmp_shl_eq_1(
-; CHECK-NEXT:    [[ADD:%.*]] = shl i8 [[X:%.*]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[ADD]], [[X]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %add = shl i8 %x, 1
   %cmp = icmp eq i8 %add, %x
   ret i1 %cmp
 }
 
 define <2 x i1> @icmp_shl_eq_2(<2 x i8> %_x) {
 ; CHECK-LABEL: @icmp_shl_eq_2(
-; CHECK-NEXT:    [[X:%.*]] = add <2 x i8> [[_X:%.*]], <i8 42, i8 42>
-; CHECK-NEXT:    [[ADD:%.*]] = shl <2 x i8> [[X]], <i8 1, i8 1>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i8> [[X]], [[ADD]]
+; CHECK-NEXT:    [[X:%.*]] = sdiv <2 x i8> <i8 42, i8 42>, [[_X:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i8> [[X]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
-  %x = add <2 x i8> <i8 42, i8 42>, %_x ; thwart complexity-based canonicalization
+  %x = sdiv <2 x i8> <i8 42, i8 42>, %_x ; thwart complexity-based canonicalization
   %add = shl <2 x i8> %x, <i8 1, i8 1>
   %cmp = icmp eq <2 x i8> %x, %add
   ret <2 x i1> %cmp
 }
 
 define <2 x i1> @icmp_shl_ne_1(<2 x i8> %x) {
 ; CHECK-LABEL: @icmp_shl_ne_1(
-; CHECK-NEXT:    [[ADD:%.*]] = shl <2 x i8> [[X:%.*]], <i8 1, i8 1>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i8> [[ADD]], [[X]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i8> [[X:%.*]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %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:    [[X:%.*]] = add i8 [[_X:%.*]], 42
-; CHECK-NEXT:    [[ADD:%.*]] = shl i8 [[X]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[X]], [[ADD]]
+; CHECK-NEXT:    [[X:%.*]] = sdiv i8 42, [[_X:%.*]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[X]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
-  %x = add i8 42, %_x ; thwart complexity-based canonicalization
+  %x = sdiv i8 42, %_x ; thwart complexity-based canonicalization
   %add = shl i8 %x, 1
   %cmp = icmp ne i8 %x, %add
   ret i1 %cmp
 }
 
 define i1 @negative_test_signed_pred(i8 %x) {
 ; CHECK-LABEL: @negative_test_signed_pred(
 ; CHECK-NEXT:    [[ADD:%.*]] = shl i8 [[X:%.*]], 1