[InstCombine] Inefficient pattern for high-bits checking (PR38708)

[lebedev.ri]

Summary

It is sometimes important to check that some newly-computed value
is non-negative and only n bits wide (where n is a variable.)
There are many ways to check that:
https://godbolt.org/z/o4RB8D
The last variant seems best?
(I'm sure there are some other variations i haven't thought of..)

Let's handle the second variant first, since it is much simpler.
https://rise4fun.com/Alive/LYjY

https://bugs.llvm.org/show_bug.cgi?id=38708

[spatel]

LGTM

[lebedev.ri]

In D51985#1232246, @spatel wrote:

LGTM

Thank you for the review!

lib/Transforms/InstCombine/InstCombineCompares.cpp

case ICmpInst::ICMP_SGE:
     std::swap(A, B);
     LLVM_FALLTHROUGH;
   case ICmpInst::ICMP_SLE:
     // icmp sle i1 A, B -> A | ~B
     return BinaryOperator::CreateOr(Builder.CreateNot(B), A);
   }
 }
 
+// Transform pattern like:
+//   (1 << Y) u<= X
+//   (1 << Y) u>  X
+// Into:
+//   (X l>> Y) != 0
+//   (X l>> Y) == 0
+static Instruction *foldICmpWithHighBitMask(ICmpInst &Cmp,
+                                            InstCombiner::BuilderTy &Builder) {
+  ICmpInst::Predicate Pred;
+  Value *X, *Y;
+  if (!match(&Cmp,
+             m_c_ICmp(Pred, m_OneUse(m_Shl(m_One(), m_Value(Y))), m_Value(X))))
+    return nullptr;
+
+  // We want X to be the icmp's second operand, so swap predicate if it is not.
+  if (Cmp.getOperand(0) == X)
+    Pred = Cmp.getSwappedPredicate();
+
+  ICmpInst::Predicate NewPred;
+  switch (Pred) {
+  case ICmpInst::ICMP_ULE:
+    NewPred = ICmpInst::ICMP_NE;
+    break;
+  case ICmpInst::ICMP_UGT:
+    NewPred = ICmpInst::ICMP_EQ;
+    break;
+  default:
+    return nullptr;
+  }
+
+  Value *NewX = Builder.CreateLShr(X, Y, X->getName() + ".highbits");
+  Constant *Zero = Constant::getNullValue(NewX->getType());
+  return CmpInst::Create(Instruction::ICmp, NewPred, NewX, Zero);
+}
+
 static Instruction *foldVectorCmp(CmpInst &Cmp,
                                   InstCombiner::BuilderTy &Builder) {
   // If both arguments of the cmp are shuffles that use the same mask and
   // shuffle within a single vector, move the shuffle after the cmp.
   Value *LHS = Cmp.getOperand(0), *RHS = Cmp.getOperand(1);
   Value *V1, *V2;
   Constant *M;
   if (match(LHS, m_ShuffleVector(m_Value(V1), m_Undef(), m_Constant(M))) &&
if (I.getPredicate() == ICmpInst::ICMP_EQ)
     if (match(Op0, m_Add(m_Value(X), m_APInt(C))) && Op1 == X)
       return foldICmpAddOpConst(X, *C, I.getPredicate());
 
     // icmp X, X+Cst
     if (match(Op1, m_Add(m_Value(X), m_APInt(C))) && Op0 == X)
       return foldICmpAddOpConst(X, *C, I.getSwappedPredicate());
   }
 
+  if (Instruction *Res = foldICmpWithHighBitMask(I, Builder))
+    return Res;
+
   if (I.getType()->isVectorTy())
     if (Instruction *Res = foldVectorCmp(I, Builder))
       return Res;
 
   return Changed ? &I : nullptr;
 }
 
 /// Fold fcmp ([us]itofp x, cst) if possible.

test/Transforms/InstCombine/icmp-ugt-of-shl-1-by-bits-and-val-to-icmp-eq-of-lshr-val-by-bits-and-0.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; https://bugs.llvm.org/show_bug.cgi?id=38708
 
 ; Pattern:
 ;   (1 << bits) u> val
 ; Should be transformed into:
 ;   (val l>> bits) == 0
 
 ; ============================================================================ ;
 ; Basic positive tests
 ; ============================================================================ ;
 
 define i1 @p0(i8 %val, i8 %bits) {
 ; CHECK-LABEL: @p0(
-; CHECK-NEXT:    [[T0:%.*]] = shl i8 1, [[BITS:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[T0]], [[VAL:%.*]]
+; CHECK-NEXT:    [[VAL_HIGHBITS:%.*]] = lshr i8 [[VAL:%.*]], [[BITS:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[VAL_HIGHBITS]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = shl i8 1, %bits
   %r = icmp ugt i8 %t0, %val
   ret i1 %r
 }
 
 ; ============================================================================ ;
 ; Vector tests
 ; ============================================================================ ;
 
 define <2 x i1> @p1_vec(<2 x i8> %val, <2 x i8> %bits) {
 ; CHECK-LABEL: @p1_vec(
-; CHECK-NEXT:    [[T0:%.*]] = shl <2 x i8> <i8 1, i8 1>, [[BITS:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt <2 x i8> [[T0]], [[VAL:%.*]]
+; CHECK-NEXT:    [[VAL_HIGHBITS:%.*]] = lshr <2 x i8> [[VAL:%.*]], [[BITS:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i8> [[VAL_HIGHBITS]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %t0 = shl <2 x i8> <i8 1, i8 1>, %bits
   %r = icmp ugt <2 x i8> %t0, %val
   ret <2 x i1> %r
 }
 
 define <3 x i1> @p2_vec_undef(<3 x i8> %val, <3 x i8> %bits) {
 ; CHECK-LABEL: @p2_vec_undef(
-; CHECK-NEXT:    [[T0:%.*]] = shl <3 x i8> <i8 1, i8 undef, i8 1>, [[BITS:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt <3 x i8> [[T0]], [[VAL:%.*]]
+; CHECK-NEXT:    [[VAL_HIGHBITS:%.*]] = lshr <3 x i8> [[VAL:%.*]], [[BITS:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp eq <3 x i8> [[VAL_HIGHBITS]], zeroinitializer
 ; CHECK-NEXT:    ret <3 x i1> [[R]]
 ;
   %t0 = shl <3 x i8> <i8 1, i8 undef, i8 1>, %bits
   %r = icmp ugt <3 x i8> %t0, %val
   ret <3 x i1> %r
 }
 
 ; ============================================================================ ;
 ; Commutativity tests.
 ; ============================================================================ ;
 
 declare i8 @gen8()
 
 define i1 @c0(i8 %bits) {
 ; CHECK-LABEL: @c0(
-; CHECK-NEXT:    [[T0:%.*]] = shl i8 1, [[BITS:%.*]]
 ; CHECK-NEXT:    [[VAL:%.*]] = call i8 @gen8()
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i8 [[VAL]], [[T0]]
+; CHECK-NEXT:    [[VAL_HIGHBITS:%.*]] = lshr i8 [[VAL]], [[BITS:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[VAL_HIGHBITS]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = shl i8 1, %bits
   %val = call i8 @gen8()
   %r = icmp ult i8 %val, %t0 ; swapped order and predicate
   ret i1 %r
 }
 

test/Transforms/InstCombine/icmp-ule-of-shl-1-by-bits-and-val-to-icmp-ne-of-lshr-val-by-bits-and-0.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; https://bugs.llvm.org/show_bug.cgi?id=38708
 
 ; Pattern:
 ;   (1 << bits) u<= val
 ; Should be transformed into:
 ;   (val l>> bits) != 0
 
 ; ============================================================================ ;
 ; Basic positive tests
 ; ============================================================================ ;
 
 define i1 @p0(i8 %val, i8 %bits) {
 ; CHECK-LABEL: @p0(
-; CHECK-NEXT:    [[T0:%.*]] = shl i8 1, [[BITS:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ule i8 [[T0]], [[VAL:%.*]]
+; CHECK-NEXT:    [[VAL_HIGHBITS:%.*]] = lshr i8 [[VAL:%.*]], [[BITS:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[VAL_HIGHBITS]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = shl i8 1, %bits
   %r = icmp ule i8 %t0, %val
   ret i1 %r
 }
 
 ; ============================================================================ ;
 ; Vector tests
 ; ============================================================================ ;
 
 define <2 x i1> @p1_vec(<2 x i8> %val, <2 x i8> %bits) {
 ; CHECK-LABEL: @p1_vec(
-; CHECK-NEXT:    [[T0:%.*]] = shl <2 x i8> <i8 1, i8 1>, [[BITS:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ule <2 x i8> [[T0]], [[VAL:%.*]]
+; CHECK-NEXT:    [[VAL_HIGHBITS:%.*]] = lshr <2 x i8> [[VAL:%.*]], [[BITS:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ne <2 x i8> [[VAL_HIGHBITS]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %t0 = shl <2 x i8> <i8 1, i8 1>, %bits
   %r = icmp ule <2 x i8> %t0, %val
   ret <2 x i1> %r
 }
 
 define <3 x i1> @p2_vec_undef(<3 x i8> %val, <3 x i8> %bits) {
 ; CHECK-LABEL: @p2_vec_undef(
-; CHECK-NEXT:    [[T0:%.*]] = shl <3 x i8> <i8 1, i8 undef, i8 1>, [[BITS:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ule <3 x i8> [[T0]], [[VAL:%.*]]
+; CHECK-NEXT:    [[VAL_HIGHBITS:%.*]] = lshr <3 x i8> [[VAL:%.*]], [[BITS:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ne <3 x i8> [[VAL_HIGHBITS]], zeroinitializer
 ; CHECK-NEXT:    ret <3 x i1> [[R]]
 ;
   %t0 = shl <3 x i8> <i8 1, i8 undef, i8 1>, %bits
   %r = icmp ule <3 x i8> %t0, %val
   ret <3 x i1> %r
 }
 
 ; ============================================================================ ;
 ; Commutativity tests.
 ; ============================================================================ ;
 
 declare i8 @gen8()
 
 define i1 @c0(i8 %bits) {
 ; CHECK-LABEL: @c0(
-; CHECK-NEXT:    [[T0:%.*]] = shl i8 1, [[BITS:%.*]]
 ; CHECK-NEXT:    [[VAL:%.*]] = call i8 @gen8()
-; CHECK-NEXT:    [[R:%.*]] = icmp uge i8 [[VAL]], [[T0]]
+; CHECK-NEXT:    [[VAL_HIGHBITS:%.*]] = lshr i8 [[VAL]], [[BITS:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[VAL_HIGHBITS]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %t0 = shl i8 1, %bits
   %val = call i8 @gen8()
   %r = icmp uge i8 %val, %t0 ; swapped order and predicate
   ret i1 %r
 }