[InstCombine] Simplify icmp ult/uge (shl %x, C2), C1 iff C1 is power of two -> icmp eq/ne (and %x, (lshr -C1, C2)), 0.

[huihuiz]

Summary

Simplify 'shl' inequality test into 'and' equality test.

This pattern happens in the middle-end while simplifying bitfield access,
Exposed in https://reviews.llvm.org/D63505

https://rise4fun.com/Alive/6uz

[huihuiz]

This will fix the missing fold found in D63505

Adding original test in differential D63670

[lebedev.ri]

Nice, some comments.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2032

This comment is for the second fold, for the first fold the comment is

// (X l<< C2) u<=/u> C1 iff C1+1 is power of two  ->  X & (~C1 l>> C2) ==/!= 0.

2033

if (Cmp.isUnsigned() && Shl.hasOneUse()) {

llvm/test/Transforms/InstCombine/shl-unsigned-cmp-const.ll

204–205

In this case, these folds should be limited to single-use shl, because we produce 2 instructions,
and only ensure that we replace a single instruction, thus we might increase instruction count.

[lebedev.ri]

llvm/test/Transforms/InstCombine/shl-and-unsigned-cmp-const.ll

15–25 ↗

(On Diff #206087)

Why is this test so complicated?

%shl = shl i8 %x, 5
%cmp = icmp ult i8 %shl, 64

seems sufficient?
https://godbolt.org/z/GcVzPz

[lebedev.ri]

(just marking as reviewed)

[huihuiz]

addressed review comments

[lebedev.ri]

Looks good, thank you.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2041

Like i commented in tests, it is not really possible to guarantely test those predicates.
It seems like the predicates aren't being canonnicalized for vector compares, but that is likely a bug (CC @spatel)
So it would be great if you could add vector test coverage for these, for now at least.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2041

I haven't been following this set of patches closely, but lack of vector folds is still a fairly common problem. You can usually spot those limitations by searching for m_ConstantInt or dyn_cast to 'ConstantInt' rather than 'm_APInt'.

[huihuiz]

update for added vector tests

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (Shl->hasOneUse() && isSignBitCheck(Pred, C, TrueIfSigned)) {
     Constant *Mask = ConstantInt::get(
         ShType,
         APInt::getOneBitSet(TypeBits, TypeBits - ShiftAmt->getZExtValue() - 1));
     Value *And = Builder.CreateAnd(X, Mask, Shl->getName() + ".mask");
     return new ICmpInst(TrueIfSigned ? ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ,
                         And, Constant::getNullValue(ShType));
   }
 
+  // Simplify 'shl' inequality test into 'and' equality test.
+  if (Cmp.isUnsigned() && Shl->hasOneUse()) {
+    // (X l<< C2) u<=/u> C1 iff C1+1 is power of two -> X & (~C1 l>> C2) ==/!= 0
+    if ((C + 1).isPowerOf2() &&
+        (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_UGT)) {
+      Value *And = Builder.CreateAnd(X, (~C).lshr(ShiftAmt->getZExtValue()));
+      return new ICmpInst(Pred == ICmpInst::ICMP_ULE ? ICmpInst::ICMP_EQ
+                                                     : ICmpInst::ICMP_NE,
+                          And, Constant::getNullValue(ShType));
+    }
+    // (X l<< C2) u</u>= C1 iff C1 is power of two -> X & (-C1 l>> C2) ==/!= 0
+    if (C.isPowerOf2() &&
+        (Pred == ICmpInst::ICMP_ULT || Pred == ICmpInst::ICMP_UGE)) {
+      Value *And =
+          Builder.CreateAnd(X, (~(C - 1)).lshr(ShiftAmt->getZExtValue()));
+      return new ICmpInst(Pred == ICmpInst::ICMP_ULT ? ICmpInst::ICMP_EQ
+                                                     : ICmpInst::ICMP_NE,
+                          And, Constant::getNullValue(ShType));
+    }
+  }
+
   // Transform (icmp pred iM (shl iM %v, N), C)
   // -> (icmp pred i(M-N) (trunc %v iM to i(M-N)), (trunc (C>>N))
   // Transform the shl to a trunc if (trunc (C>>N)) has no loss and M-N.
   // This enables us to get rid of the shift in favor of a trunc that may be
   // free on the target. It has the additional benefit of comparing to a
   // smaller constant that may be more target-friendly.
   unsigned Amt = ShiftAmt->getLimitedValue(TypeBits - 1);
   if (Shl->hasOneUse() && Amt != 0 && C.countTrailingZeros() >= Amt &&

llvm/test/Transforms/InstCombine/pr17827.ll

;
   %ashr = ashr <2 x i8> %shl, <i8 5, i8 5>
   %cmp = icmp slt <2 x i8> %ashr, <i8 1, i8 1>
   ret <2 x i1> %cmp
 }
 
 ; Unsigned compare allows a transformation to compare against 0.
 define i1 @test_shift_and_cmp_changed2(i8 %p) {
 ; CHECK-LABEL: @test_shift_and_cmp_changed2(
-; CHECK-NEXT:    [[SHLP:%.*]] = shl i8 [[P:%.*]], 5
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[SHLP]], 64
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[P:%.*]], 6
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shlp = shl i8 %p, 5
   %andp = and i8 %shlp, -64
   %cmp = icmp ult i8 %andp, 32
   ret i1 %cmp
 }
 
 define <2 x i1> @test_shift_and_cmp_changed2_vec(<2 x i8> %p) {
 ; CHECK-LABEL: @test_shift_and_cmp_changed2_vec(
-; CHECK-NEXT:    [[SHLP:%.*]] = shl <2 x i8> [[P:%.*]], <i8 5, i8 5>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult <2 x i8> [[SHLP]], <i8 64, i8 64>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[P:%.*]], <i8 6, i8 6>
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i8> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %shlp = shl <2 x i8> %p, <i8 5, i8 5>
   %andp = and <2 x i8> %shlp, <i8 -64, i8 -64>
   %cmp = icmp ult <2 x i8> %andp, <i8 32, i8 32>
   ret <2 x i1> %cmp
 }
 

llvm/test/Transforms/InstCombine/shl-unsigned-cmp-const.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; Simplify 'shl' inequality test into 'and' equality test.
 ;   (X l<< C2) u</u>= C1 iff C1 is power of 2 -> X & (-C1 l>> C2) ==/!= 0
 
 ; Scalar tests
 
 ; C2 Shift amount smaller than C1 trailing zeros.
 define i1 @scalar_i8_shl_ult_const_1(i8 %x) {
 ; CHECK-LABEL: @scalar_i8_shl_ult_const_1(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 [[X:%.*]], 5
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[SHL]], 64
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], 6
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl i8 %x, 5
   %cmp = icmp ult i8 %shl, 64
   ret i1 %cmp
 }
 
 ; C2 Shift amount equal to C1 trailing zeros.
;
   %shl = shl i8 %x, 7
   %cmp = icmp ult i8 %shl, 64
   ret i1 %cmp
 }
 
 ; C2 Shift amount smaller than C1 trailing zeros.
 define i1 @scalar_i16_shl_ult_const(i16 %x) {
 ; CHECK-LABEL: @scalar_i16_shl_ult_const(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i16 [[X:%.*]], 8
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i16 [[SHL]], 1024
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[X:%.*]], 252
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl i16 %x, 8
   %cmp = icmp ult i16 %shl, 1024
   ret i1 %cmp
 }
 
 define i1 @scalar_i32_shl_ult_const(i32 %x) {
 ; CHECK-LABEL: @scalar_i32_shl_ult_const(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], 11
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[SHL]], 131072
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], 2097088
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl i32 %x, 11
   %cmp = icmp ult i32 %shl, 131072
   ret i1 %cmp
 }
 
 define i1 @scalar_i64_shl_ult_const(i64 %x) {
 ; CHECK-LABEL: @scalar_i64_shl_ult_const(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i64 [[X:%.*]], 25
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i64 [[SHL]], 8589934592
+; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[X:%.*]], 549755813632
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl i64 %x, 25
   %cmp = icmp ult i64 %shl, 8589934592
   ret i1 %cmp
 }
 
 ; Check 'uge' predicate
 define i1 @scalar_i8_shl_uge_const(i8 %x) {
 ; CHECK-LABEL: @scalar_i8_shl_uge_const(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 [[X:%.*]], 5
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[SHL]], 63
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], 6
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl i8 %x, 5
   %cmp = icmp uge i8 %shl, 64
   ret i1 %cmp
 }
 
 ; Check 'ule' predicate
 define i1 @scalar_i8_shl_ule_const(i8 %x) {
 ; CHECK-LABEL: @scalar_i8_shl_ule_const(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 [[X:%.*]], 5
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[SHL]], 64
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], 6
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl i8 %x, 5
   %cmp = icmp ule i8 %shl, 63
   ret i1 %cmp
 }
 
 ; Check 'ugt' predicate
 define i1 @scalar_i8_shl_ugt_const(i8 %x) {
 ; CHECK-LABEL: @scalar_i8_shl_ugt_const(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 [[X:%.*]], 5
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i8 [[SHL]], 63
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], 6
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl i8 %x, 5
   %cmp = icmp ugt i8 %shl, 63
   ret i1 %cmp
 }
 
 ; Vector tests
 
 define <4 x i1> @vector_4xi32_shl_ult_const(<4 x i32> %x) {
 ; CHECK-LABEL: @vector_4xi32_shl_ult_const(
-; CHECK-NEXT:    [[SHL:%.*]] = shl <4 x i32> [[X:%.*]], <i32 11, i32 11, i32 11, i32 11>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult <4 x i32> [[SHL]], <i32 131072, i32 131072, i32 131072, i32 131072>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <4 x i32> [[X:%.*]], <i32 2097088, i32 2097088, i32 2097088, i32 2097088>
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <4 x i32> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <4 x i1> [[CMP]]
 ;
   %shl = shl <4 x i32> %x, <i32 11, i32 11, i32 11, i32 11>
   %cmp = icmp ult <4 x i32> %shl, <i32 131072, i32 131072, i32 131072, i32 131072>
   ret <4 x i1> %cmp
 }
 
 define <4 x i1> @vector_4xi32_shl_ult_const_undef1(<4 x i32> %x) {
;
   %shl = shl <4 x i32> %x, <i32 11, i32 11, i32 undef, i32 11>
   %cmp = icmp ult <4 x i32> %shl, <i32 undef, i32 131072, i32 131072, i32 131072>
   ret <4 x i1> %cmp
 }
 
 ; Check 'uge' predicate
 define <4 x i1> @vector_4xi32_shl_uge_const(<4 x i32> %x) {
 ; CHECK-LABEL: @vector_4xi32_shl_uge_const(
-; CHECK-NEXT:    [[SHL:%.*]] = shl <4 x i32> [[X:%.*]], <i32 11, i32 11, i32 11, i32 11>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt <4 x i32> [[SHL]], <i32 131071, i32 131071, i32 131071, i32 131071>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <4 x i32> [[X:%.*]], <i32 2097088, i32 2097088, i32 2097088, i32 2097088>
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <4 x i32> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <4 x i1> [[CMP]]
 ;
   %shl = shl <4 x i32> %x, <i32 11, i32 11, i32 11, i32 11>
   %cmp = icmp uge <4 x i32> %shl, <i32 131072, i32 131072, i32 131072, i32 131072>
   ret <4 x i1> %cmp
 }
 
 ; Check 'ule' predicate
 define <4 x i1> @vector_4xi32_shl_ule_const(<4 x i32> %x) {
 ; CHECK-LABEL: @vector_4xi32_shl_ule_const(
-; CHECK-NEXT:    [[SHL:%.*]] = shl <4 x i32> [[X:%.*]], <i32 11, i32 11, i32 11, i32 11>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult <4 x i32> [[SHL]], <i32 131072, i32 131072, i32 131072, i32 131072>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <4 x i32> [[X:%.*]], <i32 2097088, i32 2097088, i32 2097088, i32 2097088>
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <4 x i32> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <4 x i1> [[CMP]]
 ;
   %shl = shl <4 x i32> %x, <i32 11, i32 11, i32 11, i32 11>
   %cmp = icmp ule <4 x i32> %shl, <i32 131071, i32 131071, i32 131071, i32 131071>
   ret <4 x i1> %cmp
 }
 
 ; Check 'ugt' predicate
 define <4 x i1> @vector_4xi32_shl_ugt_const(<4 x i32> %x) {
 ; CHECK-LABEL: @vector_4xi32_shl_ugt_const(
-; CHECK-NEXT:    [[SHL:%.*]] = shl <4 x i32> [[X:%.*]], <i32 11, i32 11, i32 11, i32 11>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt <4 x i32> [[SHL]], <i32 131071, i32 131071, i32 131071, i32 131071>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <4 x i32> [[X:%.*]], <i32 2097088, i32 2097088, i32 2097088, i32 2097088>
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <4 x i32> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <4 x i1> [[CMP]]
 ;
   %shl = shl <4 x i32> %x, <i32 11, i32 11, i32 11, i32 11>
   %cmp = icmp ugt <4 x i32> %shl, <i32 131071, i32 131071, i32 131071, i32 131071>
   ret <4 x i1> %cmp
 }
 
 ; Extra use
 
 ; Not simplified
 define i1 @scalar_i8_shl_ult_const_extra_use_shl(i8 %x, i8* %p) {
 ; CHECK-LABEL: @scalar_i8_shl_ult_const_extra_use_shl(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i8 [[X:%.*]], 5
 ; CHECK-NEXT:    store i8 [[SHL]], i8* [[P:%.*]], align 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i8 [[SHL]], 64
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl i8 %x, 5
   store i8 %shl, i8* %p
   %cmp = icmp ult i8 %shl, 64
   ret i1 %cmp
 }
 
 ; Negative tests