[InstCombine] Add transform `(icmp pred (shl {nsw and/or nuw} X, Y), C)` -> `(icmp pred X, C)`

[goldstein.w.n]

Summary

Three new transforms:

1. (icmp pred (shl nsw nuw X, Y), C) [if C <= 0] -> (icmp pred X, C)
   • ugt: https://alive2.llvm.org/ce/z/K_57J_
   • sgt: https://alive2.llvm.org/ce/z/BL8u_a
   • sge: https://alive2.llvm.org/ce/z/yZZVYz
   • uge: https://alive2.llvm.org/ce/z/R4jwwJ
   • ule: https://alive2.llvm.org/ce/z/-gbmth
   • sle: https://alive2.llvm.org/ce/z/ycZVsh
   • slt: https://alive2.llvm.org/ce/z/4MzHYm
   • sle: https://alive2.llvm.org/ce/z/fgNfex
   • ult: https://alive2.llvm.org/ce/z/cXfvH5
   • eq : https://alive2.llvm.org/ce/z/sZh_Ti
   • ne : https://alive2.llvm.org/ce/z/UrqSWA
2. (icmp eq/ne (shl {nsw|nuw} X, Y), 0) -> (icmp eq/ne X, 0)
   • eq+nsw: https://alive2.llvm.org/ce/z/aSJN6D
   • eq+nuw: https://alive2.llvm.org/ce/z/r2_-br
   • ne+nuw: https://alive2.llvm.org/ce/z/RkETtu
   • ne+nsw: https://alive2.llvm.org/ce/z/8iSfW3
3. (icmp slt (shl nsw X, Y), 0/1) -> (icmp pred X, 0/1) (icmp sgt (shl nsw X, Y), 0/-1) -> (icmp pred X, 0/-1)
   • slt: https://alive2.llvm.org/ce/z/eZYRan
   • sgt: https://alive2.llvm.org/ce/z/QQeP26
     
     Transform 3) is really sle/slt/sge/sgt with 0, but sle/sge canonicalize to slt/sgt respectively so its implemented as such.

[goldstein.w.n]

ping.

[goldstein.w.n]

ping.

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2254–2258

Can we drop this fold now?

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

 /// Fold icmp (shl X, Y), C.
 Instruction *InstCombinerImpl::foldICmpShlConstant(ICmpInst &Cmp,
                                                    BinaryOperator *Shl,
                                                    const APInt &C) {
   const APInt *ShiftVal;
   if (Cmp.isEquality() && match(Shl->getOperand(0), m_APInt(ShiftVal)))
     return foldICmpShlConstConst(Cmp, Shl->getOperand(1), C, *ShiftVal);
 
+  ICmpInst::Predicate Pred = Cmp.getPredicate();
+  // (icmp pred (shl nuw&nsw X, Y), Csle0)
+  //      -> (icmp pred X, Csle0)
+  //
+  // The idea is the nuw/nsw essentially freeze the sign bit for the shift op
+  // so X's must be what is used.
+  if (C.sle(0) && Shl->hasNoUnsignedWrap() && Shl->hasNoSignedWrap())
+    return new ICmpInst(Pred, Shl->getOperand(0), Cmp.getOperand(1));
+
+  // (icmp eq/ne (shl nuw|nsw X, Y), 0)
+  //      -> (icmp eq/ne X, 0)
+  if (ICmpInst::isEquality(Pred) && C.isZero() &&
+      (Shl->hasNoUnsignedWrap() || Shl->hasNoSignedWrap()))
+    return new ICmpInst(Pred, Shl->getOperand(0), Cmp.getOperand(1));
+
+  // (icmp slt (shl nsw X, Y), 0/1)
+  //      -> (icmp slt X, 0/1)
+  // (icmp sgt (shl nsw X, Y), 0/-1)
+  //      -> (icmp sgt X, 0/-1)
+  //
+  // NB: sge/sle with a constant will canonicalize to sgt/slt.
+  if (Shl->hasNoSignedWrap() &&
+      (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLT))
+    if (C.isZero() || (Pred == ICmpInst::ICMP_SGT ? C.isAllOnes() : C.isOne()))
+      return new ICmpInst(Pred, Shl->getOperand(0), Cmp.getOperand(1));
+
   const APInt *ShiftAmt;
   if (!match(Shl->getOperand(1), m_APInt(ShiftAmt)))
     return foldICmpShlOne(Cmp, Shl, C);
 
   // Check that the shift amount is in range. If not, don't perform undefined
   // shifts. When the shift is visited, it will be simplified.
   unsigned TypeBits = C.getBitWidth();
   if (ShiftAmt->uge(TypeBits))
     return nullptr;
 
-  ICmpInst::Predicate Pred = Cmp.getPredicate();
   Value *X = Shl->getOperand(0);
   Type *ShType = Shl->getType();
 
   // NSW guarantees that we are only shifting out sign bits from the high bits,
   // so we can ASHR the compare constant without needing a mask and eliminate
   // the shift.
   if (Shl->hasNoSignedWrap()) {
     if (Pred == ICmpInst::ICMP_SGT) {
if (Pred == ICmpInst::ICMP_SLT) {
       // SLE is the same as above, but SLE is canonicalized to SLT, so convert:
       // (X << S) <=s C is equiv to X <=s (C >> S) for all C
       // (X << S) <s (C + 1) is equiv to X <s (C >> S) + 1 if C <s SMAX
       // (X << S) <s C is equiv to X <s ((C - 1) >> S) + 1 if C >s SMIN
       assert(!C.isMinSignedValue() && "Unexpected icmp slt");
       APInt ShiftedC = (C - 1).ashr(*ShiftAmt) + 1;
       return new ICmpInst(Pred, X, ConstantInt::get(ShType, ShiftedC));
     }
     // If this is a signed comparison to 0 and the shift is sign preserving,
     // use the shift LHS operand instead; isSignTest may change 'Pred', so only
     // do that if we're sure to not continue on in this function.
     if (isSignTest(Pred, C))
       return new ICmpInst(Pred, X, Constant::getNullValue(ShType));
   }
 
   // NUW guarantees that we are only shifting out zero bits from the high bits,
   // so we can LSHR the compare constant without needing a mask and eliminate
   // the shift.
   if (Shl->hasNoUnsignedWrap()) {
     if (Pred == ICmpInst::ICMP_UGT) {
       // icmp Pred (shl nuw X, ShiftAmt), C --> icmp Pred X, (C >>u ShiftAmt)

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 define i1 @shl_nuw_eq_0(i8 %x, i8 %C) {
 ; CHECK-LABEL: @shl_nuw_eq_0(
-; CHECK-NEXT:    [[Y:%.*]] = shl nuw i8 [[X:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp eq i8 [[Y]], 0
+; CHECK-NEXT:    [[Z:%.*]] = icmp eq i8 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %y = shl nuw i8 %x, %C
   %z = icmp eq i8 %y, 0
   ret i1 %z
 }
 
 define <2 x i1> @shl_nsw_ne_0(<2 x i8> %x, <2 x i8> %C) {
 ; CHECK-LABEL: @shl_nsw_ne_0(
-; CHECK-NEXT:    [[Y:%.*]] = shl nsw <2 x i8> [[X:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp ne <2 x i8> [[Y]], zeroinitializer
+; CHECK-NEXT:    [[Z:%.*]] = icmp ne <2 x i8> [[X:%.*]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[Z]]
 ;
   %y = shl nsw <2 x i8> %x, %C
   %z = icmp ne <2 x i8> %y, zeroinitializer
   ret <2 x i1> %z
 }
 
 define i1 @shl_eq_0_fail_missing_flags(i8 %x, i8 %C) {

 ;
   %y = shl nsw nuw i8 %x, %C
   %z = icmp ne i8 %y, 1
   ret i1 %z
 }
 
 define i1 @shl_nsw_slt_1(i8 %x, i8 %C) {
 ; CHECK-LABEL: @shl_nsw_slt_1(
-; CHECK-NEXT:    [[Y:%.*]] = shl nsw i8 [[X:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp slt i8 [[Y]], 1
+; CHECK-NEXT:    [[Z:%.*]] = icmp slt i8 [[X:%.*]], 1
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %y = shl nsw i8 %x, %C
   %z = icmp slt i8 %y, 1
   ret i1 %z
 }
 
 define <2 x i1> @shl_vec_nsw_slt_1_0_todo_non_splat(<2 x i8> %x, <2 x i8> %C) {

 ;
   %y = shl nsw <2 x i8> %x, %C
   %z = icmp sle <2 x i8> %y, <i8 1, i8 1>
   ret <2 x i1> %z
 }
 
 define <2 x i1> @shl_nsw_sge_1(<2 x i8> %x, <2 x i8> %C) {
 ; CHECK-LABEL: @shl_nsw_sge_1(
-; CHECK-NEXT:    [[Y:%.*]] = shl nsw <2 x i8> [[X:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp sgt <2 x i8> [[Y]], zeroinitializer
+; CHECK-NEXT:    [[Z:%.*]] = icmp sgt <2 x i8> [[X:%.*]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[Z]]
 ;
   %y = shl nsw <2 x i8> %x, %C
   %z = icmp sge <2 x i8> %y, <i8 1, i8 1>
   ret <2 x i1> %z
 }
 
 define i1 @shl_nsw_sgt_n1(i8 %x, i8 %C) {
 ; CHECK-LABEL: @shl_nsw_sgt_n1(
-; CHECK-NEXT:    [[Y:%.*]] = shl nsw i8 [[X:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp sgt i8 [[Y]], -1
+; CHECK-NEXT:    [[Z:%.*]] = icmp sgt i8 [[X:%.*]], -1
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %y = shl nsw i8 %x, %C
   %z = icmp sgt i8 %y, -1
   ret i1 %z
 }
 
 define i1 @shl_nuw_sgt_n1_fail_wrong_flag(i8 %x, i8 %C) {
 ; CHECK-LABEL: @shl_nuw_sgt_n1_fail_wrong_flag(
 ; CHECK-NEXT:    [[Y:%.*]] = shl nuw i8 [[X:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = icmp sgt i8 [[Y]], -1
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %y = shl nuw i8 %x, %C
   %z = icmp sgt i8 %y, -1
   ret i1 %z
 }
 
 define i1 @shl_nsw_nuw_ult_Csle0(i8 %x, i8 %C) {
 ; CHECK-LABEL: @shl_nsw_nuw_ult_Csle0(
-; CHECK-NEXT:    [[Y:%.*]] = shl nuw nsw i8 [[X:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp ult i8 [[Y]], -19
+; CHECK-NEXT:    [[Z:%.*]] = icmp ult i8 [[X:%.*]], -19
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %y = shl nuw nsw i8 %x, %C
   %z = icmp ult i8 %y, -19
   ret i1 %z
 }
 
 define i1 @shl_nsw_ule_Csle0_fail_missing_flag(i8 %x, i8 %C) {
 ; CHECK-LABEL: @shl_nsw_ule_Csle0_fail_missing_flag(
 ; CHECK-NEXT:    [[Y:%.*]] = shl nsw i8 [[X:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = icmp ult i8 [[Y]], -18
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %y = shl nsw i8 %x, %C
   %z = icmp ule i8 %y, -19
   ret i1 %z
 }
 
 define i1 @shl_nsw_nuw_uge_Csle0(i8 %x, i8 %C) {
 ; CHECK-LABEL: @shl_nsw_nuw_uge_Csle0(
-; CHECK-NEXT:    [[Y:%.*]] = shl nuw nsw i8 [[X:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp ugt i8 [[Y]], -121
+; CHECK-NEXT:    [[Z:%.*]] = icmp ugt i8 [[X:%.*]], -121
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %y = shl nuw nsw i8 %x, %C
   %z = icmp uge i8 %y, -120
   ret i1 %z
 }
 
 define i1 @shl_nuw_ugt_Csle0_fail_missing_flag(i8 %x, i8 %C) {
 ; CHECK-LABEL: @shl_nuw_ugt_Csle0_fail_missing_flag(
 ; CHECK-NEXT:    [[Y:%.*]] = shl nuw i8 [[X:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = icmp ugt i8 [[Y]], -19
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %y = shl nuw i8 %x, %C
   %z = icmp ugt i8 %y, -19
   ret i1 %z
 }
 
 define <2 x i1> @shl_nsw_nuw_sgt_Csle0(<2 x i8> %x, <2 x i8> %C) {
 ; CHECK-LABEL: @shl_nsw_nuw_sgt_Csle0(
-; CHECK-NEXT:    [[Y:%.*]] = shl nuw nsw <2 x i8> [[X:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp sgt <2 x i8> [[Y]], <i8 -10, i8 -10>
+; CHECK-NEXT:    [[Z:%.*]] = icmp sgt <2 x i8> [[X:%.*]], <i8 -10, i8 -10>
 ; CHECK-NEXT:    ret <2 x i1> [[Z]]
 ;
   %y = shl nsw nuw <2 x i8> %x, %C
   %z = icmp sgt <2 x i8> %y, <i8 -10, i8 -10>
   ret <2 x i1> %z
 }
 
 define <2 x i1> @shl_nsw_nuw_sge_Csle0_todo_non_splat(<2 x i8> %x, <2 x i8> %C) {
 ; CHECK-LABEL: @shl_nsw_nuw_sge_Csle0_todo_non_splat(
 ; CHECK-NEXT:    [[Y:%.*]] = shl nuw nsw <2 x i8> [[X:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = icmp sgt <2 x i8> [[Y]], <i8 -11, i8 -66>
 ; CHECK-NEXT:    ret <2 x i1> [[Z]]
 ;
   %y = shl nsw nuw <2 x i8> %x, %C
   %z = icmp sge <2 x i8> %y, <i8 -10, i8 -65>
   ret <2 x i1> %z
 }
 
 define <2 x i1> @shl_nsw_nuw_sle_Csle0(<2 x i8> %x, <2 x i8> %C) {
 ; CHECK-LABEL: @shl_nsw_nuw_sle_Csle0(
-; CHECK-NEXT:    [[Y:%.*]] = shl nuw nsw <2 x i8> [[X:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp slt <2 x i8> [[Y]], <i8 -5, i8 -5>
+; CHECK-NEXT:    [[Z:%.*]] = icmp slt <2 x i8> [[X:%.*]], <i8 -5, i8 -5>
 ; CHECK-NEXT:    ret <2 x i1> [[Z]]
 ;
   %y = shl nsw nuw <2 x i8> %x, %C
   %z = icmp sle <2 x i8> %y, <i8 -6, i8 -6>
   ret <2 x i1> %z
 }
 
 define <2 x i1> @shl_nsw_nuw_slt_Csle0_fail_positive(<2 x i8> %x, <2 x i8> %C) {