[InstCombine] improve fold for icmp-ugt-ashr

[Chenbing.Zheng]

Summary

Existing condition for
fold icmp ugt (ashr X, ShAmtC), C --> icmp ugt X, ((C + 1) << ShAmtC) - 1
missed some boundary. It cause this fold don't work for some cases, and the
reason is due to signed number overflow.

[RKSimon]

Do you have an alive2 test?

[spatel]

For reference, this was the Alive2 from the original review ( D117365 ):
https://alive2.llvm.org/ce/z/tFAcZt

To catch the overflow case, I think we check if the incremented + shifted constant became signed min (0x8000...):
https://alive2.llvm.org/ce/z/RZdftJ

So that should be simpler than the pre-condition currently shown in this patch.

(C + 1).shl(ShAmtVal).isMinSignedValue()

[Chenbing.Zheng]

address comment

[spatel]

LGTM - it may be worth looking at the related folds to see if there's some generalization that we missed (see inline comment about the other TODO comment in the test file).

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

857–858

Check the history to see where this got fixed? Either way, we should delete the TODO since it optimized now.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2258–2259

Rephrase this comment:

// 'C + 1 << ShAmtC' can overflow as a signed number, so the 2nd
// clause accounts for that pattern.

[Chenbing.Zheng]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2258–2259

I modified it when commit

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

857–858

I modified it when commit

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (Pred == CmpInst::ICMP_SGT) {
       // icmp sgt (ashr X, ShAmtC), C --> icmp sgt X, ((C + 1) << ShAmtC) - 1
       APInt ShiftedC = (C + 1).shl(ShAmtVal) - 1;
       if (!C.isMaxSignedValue() && !(C + 1).shl(ShAmtVal).isMinSignedValue() &&
           (ShiftedC + 1).ashr(ShAmtVal) == (C + 1))
         return new ICmpInst(Pred, X, ConstantInt::get(ShrTy, ShiftedC));
     }
     if (Pred == CmpInst::ICMP_UGT) {
       // icmp ugt (ashr X, ShAmtC), C --> icmp ugt X, ((C + 1) << ShAmtC) - 1
+      // 'C + 1 << ShAmtC' can overflow as a signed number, so the 2nd
+      // clause accounts for that pattern.
       APInt ShiftedC = (C + 1).shl(ShAmtVal) - 1;
-      if ((ShiftedC + 1).ashr(ShAmtVal) == (C + 1))
+      if ((ShiftedC + 1).ashr(ShAmtVal) == (C + 1) ||
+          (C + 1).shl(ShAmtVal).isMinSignedValue())
         return new ICmpInst(Pred, X, ConstantInt::get(ShrTy, ShiftedC));
     }
 
     // If the compare constant has significant bits above the lowest sign-bit,
     // then convert an unsigned cmp to a test of the sign-bit:
     // (ashr X, ShiftC) u> C --> X s< 0
     // (ashr X, ShiftC) u< C --> X s> -1
     if (C.getBitWidth() > 2 && C.getNumSignBits() <= ShAmtVal) {

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

 ; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[X:%.*]], 5
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 2 ; 0b0010
   ret i1 %r
 }
 
-; negative test
-; TODO: This is a sign-bit test, but we don't recognize the pattern.
-
 define i1 @ashr_ugt_3(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_3(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], 3
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i4 [[X:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 3 ; 0b0011
   ret i1 %r
 }
 
 define i1 @ashr_ugt_4(i4 %x) {

 ; CHECK-NEXT:    [[R:%.*]] = icmp sgt i4 [[X:%.*]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 11 ; 0b1011
   ret i1 %r
 }
 
 ; negative test
-; TODO: This is a sign-bit test, but we don't recognize the pattern.
 
 define i1 @ashr_ult_12(i4 %x) {
 ; CHECK-LABEL: @ashr_ult_12(
 ; CHECK-NEXT:    [[R:%.*]] = icmp sgt i4 [[X:%.*]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ult i4 %s, 12 ; 0b1100
   ret i1 %r