[InstCombine] (ShiftValC >> Y) >s -1/<s 0 --> Y != 0/==0

[Chenbing.Zheng]

Summary

We can do
(ShiftValC >> Y) >s -1 --> Y != 0,
(ShiftValC >> Y) <s 0 --> Y == 0,
with ShiftValC < 0

https://alive2.llvm.org/ce/z/-PRHfD
https://alive2.llvm.org/ce/z/bWfp-s

[spatel]

This will not solve the problem in general. We need to add a fold for lshr values. We should be able to optimize something like this:
https://godbolt.org/z/7Mhdd8dfa
https://alive2.llvm.org/ce/z/3sB6au

Can we generalize or adapt this recent patch?
d4f39d8333324bdcf2056

[Chenbing.Zheng]

address comment，
add fold (ShiftValC >> Y) >s -1 --> Y != 0 with ShiftValC < 0
https://alive2.llvm.org/ce/z/TTnvgs

[Chenbing.Zheng]

update tests

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2242

We should also handle the related pattern that is checking if the shifted value is negative:
https://alive2.llvm.org/ce/z/bWfp-s

Using InstCombiner::isSignBitCheck() can reduce the code needed to match these patterns. Look around this file for examples of usage.

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

1195

typo: "Negative"

You may pre-commit tests in "NFC" patches. You can push that kind of patch without pre-commit review on Phabricator. It would be good to test at least 2 more code patterns:

1. Use a vector type with "splat" constants.
2. Add an extra use of the shift.

[Chenbing.Zheng]

address comments

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2246

We are inside of the "InstCombiner" namespace, so there is no reason to specify "InstCombiner::" explicitly.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombinerImpl::foldICmpShrConstant(ICmpInst &Cmp,
   // icmp eq/ne (shr X, Y), 0 --> icmp eq/ne X, 0
   Value *X = Shr->getOperand(0);
   CmpInst::Predicate Pred = Cmp.getPredicate();
   if (Cmp.isEquality() && Shr->isExact() && C.isZero())
     return new ICmpInst(Pred, X, Cmp.getOperand(1));
 
   bool IsAShr = Shr->getOpcode() == Instruction::AShr;
   const APInt *ShiftValC;
-  if (match(Shr->getOperand(0), m_APInt(ShiftValC))) {
+  if (match(X, m_APInt(ShiftValC))) {
     if (Cmp.isEquality())
       return foldICmpShrConstConst(Cmp, Shr->getOperand(1), C, *ShiftValC);
 
+    // (ShiftValC >> Y) >s -1 --> Y != 0 with ShiftValC < 0
+    // (ShiftValC >> Y) <s  0 --> Y == 0 with ShiftValC < 0
+    bool TrueIfSigned;
+    if (!IsAShr && ShiftValC->isNegative() &&
+        isSignBitCheck(Pred, C, TrueIfSigned))
+      return new ICmpInst(TrueIfSigned ? CmpInst::ICMP_EQ : CmpInst::ICMP_NE,
+                          Shr->getOperand(1),
+                          ConstantInt::getNullValue(X->getType()));
+
     // If the shifted constant is a power-of-2, test the shift amount directly:
-    // (ShiftValC >> X) >u C --> X <u (LZ(C) - LZ(ShiftValC))
-    // (ShiftValC >> X) <u C --> X >=u (LZ(C-1) - LZ(ShiftValC))
+    // (ShiftValC >> Y) >u C --> X <u (LZ(C) - LZ(ShiftValC))
+    // (ShiftValC >> Y) <u C --> X >=u (LZ(C-1) - LZ(ShiftValC))
     if (!IsAShr && ShiftValC->isPowerOf2() &&
         (Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_ULT)) {
       bool IsUGT = Pred == CmpInst::ICMP_UGT;
       assert(ShiftValC->uge(C) && "Expected simplify of compare");
       assert((IsUGT || !C.isZero()) && "Expected X u< 0 to simplify");
 
       unsigned CmpLZ =
           IsUGT ? C.countLeadingZeros() : (C - 1).countLeadingZeros();

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

 ; CHECK-NEXT:    [[R:%.*]] = icmp ne i32 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shr = lshr i32 16, %x
   %r = icmp ult i32 %shr, 16
   ret i1 %r
 }
 
-; TODO: This should reduce to X != 0.
-
 define i1 @lshr_pow2_ult_smin(i8 %x) {
 ; CHECK-LABEL: @lshr_pow2_ult_smin(
-; CHECK-NEXT:    [[S:%.*]] = lshr i8 -128, [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[S]], -1
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = lshr i8 128, %x
   %r = icmp ult i8 %s, 128
   ret i1 %r
 }
 
 ; negative test - need logical shift
;
   %r = icmp slt i8 %s, 3
   ret i1 %r
 }
 
 ; (ShiftValC >> X) >s -1 --> X != 0 with ShiftValC < 0
 
 define i1 @lshr_neg_sgt_minus_1(i8 %x) {
 ; CHECK-LABEL: @lshr_neg_sgt_minus_1(
-; CHECK-NEXT:    [[S:%.*]] = lshr i8 -17, [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[S]], -1
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = lshr i8 -17, %x
   %r = icmp sgt i8 %s, -1
   ret i1 %r
 }
 
 define <2 x i1> @lshr_neg_sgt_minus_1_vector(<2 x i8> %x) {
 ; CHECK-LABEL: @lshr_neg_sgt_minus_1_vector(
-; CHECK-NEXT:    [[S:%.*]] = lshr <2 x i8> <i8 -17, i8 -17>, [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt <2 x i8> [[S]], <i8 -1, i8 -1>
+; CHECK-NEXT:    [[R:%.*]] = icmp ne <2 x i8> [[X:%.*]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %s = lshr <2 x i8> <i8 -17, i8 -17>, %x
   %r = icmp sgt <2 x i8> %s, <i8 -1, i8 -1>
   ret <2 x i1> %r
 }
 
-; Negative tests
-
 define i1 @lshr_neg_sgt_minus_1_extra_use(i8 %x) {
 ; CHECK-LABEL: @lshr_neg_sgt_minus_1_extra_use(
 ; CHECK-NEXT:    [[S:%.*]] = lshr i8 -17, [[X:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[S]])
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[S]], -1
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[X]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = lshr i8 -17, %x
   call void @use(i8 %s)
   %r = icmp sgt i8 %s, -1
   ret i1 %r
 }
 
+; Negative tests
+
 define i1 @lshr_neg_sgt_minus_2(i8 %x) {
 ; CHECK-LABEL: @lshr_neg_sgt_minus_2(
 ; CHECK-NEXT:    [[S:%.*]] = lshr i8 -17, [[X:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[S]], -2
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = lshr i8 -17, %x
   %r = icmp sgt i8 %s, -2
;
   %r = icmp slt i8 %s, -1
   ret i1 %r
 }
 
 ; (ShiftValC >> X) <s 0 --> X == 0 with ShiftValC < 0
 
 define i1 @lshr_neg_slt_zero(i8 %x) {
 ; CHECK-LABEL: @lshr_neg_slt_zero(
-; CHECK-NEXT:    [[S:%.*]] = lshr i8 -17, [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp slt i8 [[S]], 0
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = lshr i8 -17, %x
   %r = icmp slt i8 %s, 0
   ret i1 %r
 }
 
 define <2 x i1> @lshr_neg_slt_zero_vector(<2 x i8> %x) {
 ; CHECK-LABEL: @lshr_neg_slt_zero_vector(
-; CHECK-NEXT:    [[S:%.*]] = lshr <2 x i8> <i8 -17, i8 -17>, [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp slt <2 x i8> [[S]], zeroinitializer
+; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i8> [[X:%.*]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %s = lshr <2 x i8> <i8 -17, i8 -17>, %x
   %r = icmp slt <2 x i8> %s, <i8 0, i8 0>
   ret <2 x i1> %r
 }
 
-; Negative tests
-
 define i1 @lshr_neg_slt_zero_extra_use(i8 %x) {
 ; CHECK-LABEL: @lshr_neg_slt_zero_extra_use(
 ; CHECK-NEXT:    [[S:%.*]] = lshr i8 -17, [[X:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[S]])
-; CHECK-NEXT:    [[R:%.*]] = icmp slt i8 [[S]], 0
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[X]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = lshr i8 -17, %x
   call void @use(i8 %s)
   %r = icmp slt i8 %s, 0
   ret i1 %r
 }
 
+; Negative tests
+
 define i1 @lshr_neg_slt_non-zero(i8 %x) {
 ; CHECK-LABEL: @lshr_neg_slt_non-zero(
 ; CHECK-NEXT:    [[S:%.*]] = lshr i8 -17, [[X:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = icmp slt i8 [[S]], 2
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = lshr i8 -17, %x
   %r = icmp slt i8 %s, 2