[InstCombine] fold sign-bit compares of srem

[spatel]

Summary

(srem X, pow2C) sgt/slt 0 can be reduced using bit hacks as shown:
https://rise4fun.com/Alive/jSO
A '2' divisor allows slightly more folding:
https://rise4fun.com/Alive/tDBM

Any chance to remove an 'srem' use is probably worthwhile, but I've kept this to the strict improvement case because it may expose other missing folds. That means it does nothing for PR21929 yet:
https://bugs.llvm.org/show_bug.cgi?id=21929

[RKSimon]

Slightly beyond the scope of this patch, but would it be realistic to support non-constant cases? I know at present m_Power2 can't handle this

[spatel]

In D67334#1662930, @RKSimon wrote:

Slightly beyond the scope of this patch, but would it be realistic to support non-constant cases? I know at present m_Power2 can't handle this

Yes, this patch is only for constant divisors. We could use ValueTracking's isKnownToBeAPowerOfTwo() and be more general. But in that case, the transform would require 2 extra instructions: sub + or to produce the bitmask. It's unusual for instcombine to increase instruction sequences, but this is probably a justifiable case since there's almost no analysis for srem. Another option would be to add an SDAG expansion for that.

[lebedev.ri]

I'm not sure about the cases where we'd have to increase instruction count,
those may be best suited for codegen, but this patch looks good, some nits.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2255–2256

Match an 'is positive' or 'is negative' comparison of remainder by a constant power-of-2 value

2265–2268

I'd maybe split this into correctness check, and one-use check, to make the comment even more obvious.

[spatel]

Patch updated:
Corrected code comment and improved structure.

[lebedev.ri]

LG

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (Shr->hasOneUse()) {
     Constant *Mask = ConstantInt::get(ShrTy, Val);
     Value *And = Builder.CreateAnd(X, Mask, Shr->getName() + ".mask");
     return new ICmpInst(Pred, And, ConstantInt::get(ShrTy, C << ShAmtVal));
   }
 
   return nullptr;
 }
 
+Instruction *InstCombiner::foldICmpSRemConstant(ICmpInst &Cmp,
+                                                BinaryOperator *SRem,
+                                                const APInt &C) {
+  // Match an 'is positive' or 'is negative' comparison where the remainder is
+  // a constant power-of-2 value:
+  // (X % pow2C) sgt/slt 0
+  const ICmpInst::Predicate Pred = Cmp.getPredicate();
+  if (Pred != ICmpInst::ICMP_SGT && Pred != ICmpInst::ICMP_SLT)
+    return nullptr;
+
+  // TODO: The one-use check is standard because we do not typically want to
+  //       create longer instruction sequences, but this might be a special-case
+  //       because srem is not good for analysis or codegen.
+  const APInt *DivisorC;
+  if (!SRem->hasOneUse() || !C.isNullValue() ||
+      !match(SRem->getOperand(1), m_Power2(DivisorC)))
+    return nullptr;
+
+  // Mask off the sign bit and the modulo bits (low-bits).
+  Type *Ty = SRem->getType();
+  APInt SignMask = APInt::getSignMask(Ty->getScalarSizeInBits());
+  Constant *MaskC = ConstantInt::get(Ty, SignMask | (*DivisorC - 1));
+  Value *And = Builder.CreateAnd(SRem->getOperand(0), MaskC);
+
+  // For 'is positive?' check that the sign-bit is clear and at least 1 masked
+  // bit is set. Example:
+  // (i8 X % 32) s> 0 --> (X & 159) s> 0
+  if (Pred == ICmpInst::ICMP_SGT)
+    return new ICmpInst(ICmpInst::ICMP_SGT, And, ConstantInt::getNullValue(Ty));
+
+  // For 'is negative?' check that the sign-bit is set and at least 1 masked
+  // bit is set. Example:
+  // (i16 X % 4) s< 0 --> (X & 32771) u> 32768
+  return new ICmpInst(ICmpInst::ICMP_UGT, And, ConstantInt::get(Ty, SignMask));
+}
+
 /// Fold icmp (udiv X, Y), C.
 Instruction *InstCombiner::foldICmpUDivConstant(ICmpInst &Cmp,
                                                 BinaryOperator *UDiv,
                                                 const APInt &C) {
   const APInt *C2;
   if (!match(UDiv->getOperand(0), m_APInt(C2)))
     return nullptr;
 
case Instruction::Shl:
       if (Instruction *I = foldICmpShlConstant(Cmp, BO, *C))
         return I;
       break;
     case Instruction::LShr:
     case Instruction::AShr:
       if (Instruction *I = foldICmpShrConstant(Cmp, BO, *C))
         return I;
       break;
+    case Instruction::SRem:
+      if (Instruction *I = foldICmpSRemConstant(Cmp, BO, *C))
+        return I;
+      break;
     case Instruction::UDiv:
       if (Instruction *I = foldICmpUDivConstant(Cmp, BO, *C))
         return I;
       LLVM_FALLTHROUGH;
     case Instruction::SDiv:
       if (Instruction *I = foldICmpDivConstant(Cmp, BO, *C))
         return I;
       break;

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

private:
   Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
                                   const APInt &C);
   Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
                                    const APInt &C);
   Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
                                    const APInt &C);
   Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
                                    const APInt &C);
+  Instruction *foldICmpSRemConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
+                                    const APInt &C);
   Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
                                     const APInt &C);
   Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
                                    const APInt &C);
   Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
                                    const APInt &C);
   Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
                                    const APInt &C);

llvm/test/Transforms/InstCombine/icmp-div-constant.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define i1 @is_rem2_neg_i8(i8 %x) {
 ; CHECK-LABEL: @is_rem2_neg_i8(
-; CHECK-NEXT:    [[S:%.*]] = srem i8 [[X:%.*]], 2
-; CHECK-NEXT:    [[R:%.*]] = icmp slt i8 [[S]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], -127
+; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[TMP1]], -127
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = srem i8 %x, 2
   %r = icmp slt i8 %s, 0
   ret i1 %r
 }
 
 define <2 x i1> @is_rem2_pos_v2i8(<2 x i8> %x) {
 ; CHECK-LABEL: @is_rem2_pos_v2i8(
-; CHECK-NEXT:    [[S:%.*]] = srem <2 x i8> [[X:%.*]], <i8 2, i8 2>
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt <2 x i8> [[S]], zeroinitializer
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], <i8 -127, i8 -127>
+; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i8> [[TMP1]], <i8 1, i8 1>
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %s = srem <2 x i8> %x, <i8 2, i8 2>
   %r = icmp sgt <2 x i8> %s, zeroinitializer
   ret <2 x i1> %r
 }
 
+; i8 -97 == 159 == 0b10011111
+
 define i1 @is_rem32_pos_i8(i8 %x) {
 ; CHECK-LABEL: @is_rem32_pos_i8(
-; CHECK-NEXT:    [[S:%.*]] = srem i8 [[X:%.*]], 32
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[S]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], -97
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = srem i8 %x, 32
   %r = icmp sgt i8 %s, 0
   ret i1 %r
 }
 
+; i16 -32765 == 32771 == 0b1000000000000011
+
 define i1 @is_rem4_neg_i16(i16 %x) {
 ; CHECK-LABEL: @is_rem4_neg_i16(
-; CHECK-NEXT:    [[S:%.*]] = srem i16 [[X:%.*]], 4
-; CHECK-NEXT:    [[R:%.*]] = icmp slt i16 [[S]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[X:%.*]], -32765
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i16 [[TMP1]], -32768
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = srem i16 %x, 4
   %r = icmp slt i16 %s, 0
   ret i1 %r
 }
 
 declare void @use(i32)
 
+; TODO: This is still worth folding because srem is difficult?
+
 define i1 @is_rem32_neg_i32_extra_use(i32 %x) {
 ; CHECK-LABEL: @is_rem32_neg_i32_extra_use(
 ; CHECK-NEXT:    [[S:%.*]] = srem i32 [[X:%.*]], 32
 ; CHECK-NEXT:    call void @use(i32 [[S]])
 ; CHECK-NEXT:    [[R:%.*]] = icmp slt i32 [[S]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = srem i32 %x, 32
   call void @use(i32 %s)
   %r = icmp slt i32 %s, 0
   ret i1 %r
 }
 
+; Negative test - wrong compare constant
+
 define i1 @is_rem8_nonneg_i16(i16 %x) {
 ; CHECK-LABEL: @is_rem8_nonneg_i16(
 ; CHECK-NEXT:    [[S:%.*]] = srem i16 [[X:%.*]], 8
 ; CHECK-NEXT:    [[R:%.*]] = icmp sgt i16 [[S]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = srem i16 %x, 8
   %r = icmp sgt i16 %s, -1
   ret i1 %r
 }
 
+; Negative test - wrong remainder constant
+
 define i1 @is_rem3_neg_i8(i8 %x) {
 ; CHECK-LABEL: @is_rem3_neg_i8(
 ; CHECK-NEXT:    [[S:%.*]] = srem i8 [[X:%.*]], 3
 ; CHECK-NEXT:    [[R:%.*]] = icmp slt i8 [[S]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = srem i8 %x, 3
   %r = icmp slt i8 %s, 0
   ret i1 %r
 }
 
+; Negative test - wrong compare constant
+
 define i1 @is_rem16_something_i8(i8 %x) {
 ; CHECK-LABEL: @is_rem16_something_i8(
 ; CHECK-NEXT:    [[S:%.*]] = srem i8 [[X:%.*]], 16
 ; CHECK-NEXT:    [[R:%.*]] = icmp slt i8 [[S]], 7
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = srem i8 %x, 16
   %r = icmp slt i8 %s, 7