[InstCombine] optimize icmp-ugt-ashr

[nadav]

Summary

This diff optimizes the sequence icmp-ugt(ashr,C_1) C_2. InstCombine already implements this optimization for sgt, and this patch adds support ugt.

@craig.topper came up with the idea and proof.

This patch adds the check for UGT, and also simplifies the check for SGT because Craig's proof shows that the comparison to min_int is not necessary.

define i1 @src(i8 %x, i8 %y, i8 %c) {
  %cp1 = add i8 %c, 1
  %i = shl i8 %cp1, %y
  %i.2 = ashr i8 %i, %y
  %cmp = icmp eq i8 %cp1, %i.2
  ;Assume: C + 1 == (((C + 1) << y) >> y)
  call void @llvm.assume(i1 %cmp)

  ; uncomment for the sgt case
  %j = shl i8 %cp1, %y 
  %j.2 = sub i8 %j, 1
  %cmp2 = icmp ne i8 %j.2, 127
  ;Assume (((c + 1 ) << y) - 1) != 127
  call void @llvm.assume(i1 %cmp2)

  %s = ashr i8 %x, %y
  %r = icmp sgt i8 %s, %c
  ret i1 %r
}

define i1 @tgt(i8 %x, i8 %y, i8 %c) {
  %cp1 = add i8 %c, 1
  %j = shl i8 %cp1, %y
  %j.2 = sub i8 %j, 1

  %r = icmp sgt i8 %x, %j.2
  ret i1 %r
}

declare void @llvm.assume(i1)

This change is related to the optimizations in D117252.

[lebedev.ri]

Could you post the general proof, not for a single constant?

lib/Transforms/InstCombine/InstCombineCompares.cpp

2242

As i have said in D117252, this should be

if (IsExact || Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_ULT) {

[craig.topper]

In D117365#3245910, @lebedev.ri wrote:

Could you post the general proof, not for a single constant?

I think this is the general proof. It requires less pre-conditions than the sgt case.

https://alive2.llvm.org/ce/z/tFAcZt

lib/Transforms/InstCombine/InstCombineCompares.cpp

2253

I believe the !C.isMaxSignedValue() is an unneeded condition for the signed case. If C.isMaxSignedValue() is true then C+1 is 0x80 for i8. (ShiftedC + 1).ashr(ShAmtVal) == (C + 1) could only possibly be true when ShAmtVal is 0. 0x80 only has 1 sign bit, any other ShAmtVal would mean that (C+1) would have more than 1 sign bit.

I'm not suggesting we remove it in this patch. Just pointing it out for alive proof purposes.

[craig.topper]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2253 ↗

(On Diff #400942)

I think the !(C + 1).shl(ShAmtVal).isMinSignedValue() term is required for the signed case isn't it? It's the commented out code in my alive proof.

[nadav]

@craig.topper Thank you for the review, and for writing the proof, of course. This is my understanding of the code and of your proof.

Your proof has two checks, which I added as comments.

;Assume: C + 1 == ((C+1 << y) >> y)
;Assume ((c +1 ) << y) != 127      -- only needed for the sgt case

The first check is implemented with the code:

APInt ShiftedC = (C + 1).shl(ShAmtVal) - 1;
if ((ShiftedC + 1).ashr(ShAmtVal) == (C + 1))

And the second one with:

!C.isMaxSignedValue() && (ShiftedC + 1).ashr(ShAmtVal) == (C + 1)

The code also has this check, which I removed, because the proof does not have this check:

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

Is this also your understanding, or did I miss something.

[nadav]

Ah, I did miss something. I'll rewrite the second check: "Assume ((c +1 ) << y) != 127"

[craig.topper]

LGTM

lib/Transforms/InstCombine/InstCombineCompares.cpp

   bool IsAShr = Shr->getOpcode() == Instruction::AShr;
   bool IsExact = Shr->isExact();
   Type *ShrTy = Shr->getType();
   // TODO: If we could guarantee that InstSimplify would handle all of the
   // constant-value-based preconditions in the folds below, then we could assert
   // those conditions rather than checking them. This is difficult because of
   // undef/poison (PR34838).
   if (IsAShr) {
     if (Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_ULT || IsExact) {
       // When ShAmtC can be shifted losslessly:
       // icmp PRED (ashr exact X, ShAmtC), C --> icmp PRED X, (C << ShAmtC)
       // icmp slt/ult (ashr X, ShAmtC), C --> icmp slt/ult X, (C << ShAmtC)
       APInt ShiftedC = C.shl(ShAmtVal);
       if (ShiftedC.ashr(ShAmtVal) == C)
         return new ICmpInst(Pred, X, ConstantInt::get(ShrTy, ShiftedC));
     }
-    if (Pred == CmpInst::ICMP_SGT) {
-      // icmp sgt (ashr X, ShAmtC), C --> icmp sgt X, ((C + 1) << ShAmtC) - 1
+    if (Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_UGT) {
+      // icmp xgt (ashr X, ShAmtC), C --> icmp xgt 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 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

test/Transforms/InstCombine/icmp-shr-lt-gt.ll

 ;
   %s = ashr i8 %x, 3
   %c = icmp ne i8 %s, 10
   ret i1 %c
 }
 
 define i1 @ashr_ugt_noexact(i8 %x) {
 ; CHECK-LABEL: @ashr_ugt_noexact(
-; CHECK-NEXT:    [[S:%.*]] = ashr i8 [[X:%.*]], 3
-; CHECK-NEXT:    [[C:%.*]] = icmp ugt i8 [[S]], 10
+; CHECK-NEXT:    [[C:%.*]] = icmp ugt i8 [[X:%.*]], 87
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %s = ashr i8 %x, 3
   %c = icmp ugt i8 %s, 10
   ret i1 %c
 }
 
 
 define i1 @ashr_uge_noexact(i8 %x) {
 ; CHECK-LABEL: @ashr_uge_noexact(
-; CHECK-NEXT:    [[S:%.*]] = ashr i8 [[X:%.*]], 3
-; CHECK-NEXT:    [[C:%.*]] = icmp ugt i8 [[S]], 9
+; CHECK-NEXT:    [[C:%.*]] = icmp ugt i8 [[X:%.*]], 79
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %s = ashr i8 %x, 3
   %c = icmp uge i8 %s, 10
   ret i1 %c
 }
 
 define i1 @ashr_ult_noexact(i8 %x) {

test/Transforms/InstCombine/icmp-shr.ll

   %r = icmp ugt i4 %s, 0 ; 0b0000
   ret i1 %r
 }
 
 ; negative test
 
 define i1 @ashr_ugt_1(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_1(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], 1
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 1 ; 0b0001
   ret i1 %r
 }
 
 ; negative test
 
 define i1 @ashr_ugt_2(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_2(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], 2
+; 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

   %r = icmp ugt i4 %s, 11 ; 0b1011
   ret i1 %r
 }
 
 ; negative test
 
 define i1 @ashr_ugt_12(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_12(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], -4
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[X:%.*]], -7
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 12 ; 0b1100
   ret i1 %r
 }
 
 ; negative test
 
 define i1 @ashr_ugt_13(i4 %x) {
 ; CHECK-LABEL: @ashr_ugt_13(
-; CHECK-NEXT:    [[S:%.*]] = ashr i4 [[X:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[S]], -3
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i4 [[X:%.*]], -5
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = ashr i4 %x, 1
   %r = icmp ugt i4 %s, 13 ; 0b1101
   ret i1 %r
 }
 
 ; negative test, but different transform possible