[InstCombine] Generalize (icmp sgt (1 << Y), -1) -> (icmp ne Y, BitWidth-1) to any negative constant.

[craig.topper]

Summary

Similar for the sle version which will be canonicalized to slt first.

Alive2 proof as implemented: https://alive2.llvm.org/ce/z/_YawdM

@spatel's original Alive2: https://alive2.llvm.org/ce/z/3YB2vs

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2051

Nitpick: either change the proof to check *this* precondition, or use the same check as in the proof.

2057–2058

Same nitpick. Not what the proof shows.

[lebedev.ri]

(or, well, just post two proofs)

[craig.topper]

In D141773#4054254, @lebedev.ri wrote:

(or, well, just post two proofs)

I've added new proofs for the version as implemented.

[lebedev.ri]

https://alive2.llvm.org/ce/z/ynf5JE
LG, thank you.

I suspect, there should be a generalization for non-negative constants, too.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

 //===- InstCombineCompares.cpp --------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (!CIsPowerOf2) {
         Pred = ICmpInst::ICMP_UGT;
     }
 
     unsigned CLog2 = C.logBase2();
     return new ICmpInst(Pred, Y, ConstantInt::get(ShiftType, CLog2));
   } else if (Cmp.isSigned()) {
     Constant *BitWidthMinusOne = ConstantInt::get(ShiftType, TypeBits - 1);
     // (1 << Y) >  0 -> Y != 31
-    // (1 << Y) > -1 -> Y != 31
-    // TODO: This can be generalized to any negative constant.
-    if (Pred == ICmpInst::ICMP_SGT && (C.isZero() || C.isAllOnes()))
+    // (1 << Y) >  C -> Y != 31 if C is negative.
+    if (Pred == ICmpInst::ICMP_SGT && C.sle(0))
       return new ICmpInst(ICmpInst::ICMP_NE, Y, BitWidthMinusOne);
 
     // (1 << Y) <  0 -> Y == 31
     // (1 << Y) <  1 -> Y == 31
-    // TODO: This can be generalized to any negative constant except signed min.
-    if (Pred == ICmpInst::ICMP_SLT && (C.isZero() || C.isOne()))
+    // (1 << Y) <  C -> Y == 31 if C is negative and not signed min.
+    // Exclude signed min by subtracting 1 and lower the upper bound to 0.
+    if (Pred == ICmpInst::ICMP_SLT && (C-1).sle(0))
       return new ICmpInst(ICmpInst::ICMP_EQ, Y, BitWidthMinusOne);
   } else if (Cmp.isEquality() && CIsPowerOf2) {
     return new ICmpInst(Pred, Y, ConstantInt::get(ShiftType, C.logBase2()));
   }
 
   return nullptr;
 }
 

llvm/test/Transforms/InstCombine/icmp.ll

 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i32> [[V:%.*]], <i32 31, i32 31>
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %shl = shl <2 x i32> <i32 1, i32 1>, %V
   %cmp = icmp sle <2 x i32> %shl, <i32 0, i32 0>
   ret <2 x i1> %cmp
 }
 
+define i1 @icmp_shl_1_V_sle_negative(i32 %V) {
+; CHECK-LABEL: @icmp_shl_1_V_sle_negative(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[V:%.*]], 31
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %shl = shl i32 1, %V
+  %cmp = icmp sle i32 %shl, -42
+  ret i1 %cmp
+}
+
+define <2 x i1> @icmp_shl_1_V_sle_0_negative(<2 x i32> %V) {
+; CHECK-LABEL: @icmp_shl_1_V_sle_0_negative(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i32> [[V:%.*]], <i32 31, i32 31>
+; CHECK-NEXT:    ret <2 x i1> [[CMP]]
+;
+  %shl = shl <2 x i32> <i32 1, i32 1>, %V
+  %cmp = icmp sle <2 x i32> %shl, <i32 -2147483647, i32 -2147483647>
+  ret <2 x i1> %cmp
+}
+
 define i1 @icmp_shl_1_V_sgt_0(i32 %V) {
 ; CHECK-LABEL: @icmp_shl_1_V_sgt_0(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[V:%.*]], 31
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shl = shl i32 1, %V
   %cmp = icmp sgt i32 %shl, 0
   ret i1 %cmp
 }
 
 define <2 x i1> @icmp_shl_1_V_sgt_0_vec(<2 x i32> %V) {
 ; CHECK-LABEL: @icmp_shl_1_V_sgt_0_vec(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i32> [[V:%.*]], <i32 31, i32 31>
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %shl = shl <2 x i32> <i32 1, i32 1>, %V
   %cmp = icmp sgt <2 x i32> %shl, <i32 0, i32 0>
   ret <2 x i1> %cmp
 }
 
+define i1 @icmp_shl_1_V_sgt_negative(i32 %V) {
+; CHECK-LABEL: @icmp_shl_1_V_sgt_negative(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[V:%.*]], 31
+; CHECK-NEXT:    ret i1 [[CMP]]
+;
+  %shl = shl i32 1, %V
+  %cmp = icmp sgt i32 %shl, -12345
+  ret i1 %cmp
+}
+
+define <2 x i1> @icmp_shl_1_V_sgt_negative_vec(<2 x i32> %V) {
+; CHECK-LABEL: @icmp_shl_1_V_sgt_negative_vec(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i32> [[V:%.*]], <i32 31, i32 31>
+; CHECK-NEXT:    ret <2 x i1> [[CMP]]
+;
+  %shl = shl <2 x i32> <i32 1, i32 1>, %V
+  %cmp = icmp sgt <2 x i32> %shl, <i32 -2, i32 -2>
+  ret <2 x i1> %cmp
+}
+
 define i1 @or_icmp_eq_B_0_icmp_ult_A_B(i64 %a, i64 %b) {
 ; CHECK-LABEL: @or_icmp_eq_B_0_icmp_ult_A_B(
 ; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[B:%.*]], -1
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp uge i64 [[TMP1]], [[A:%.*]]
 ; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %1 = icmp eq i64 %b, 0
   %2 = icmp ult i64 %a, %b