[InstCombine] Fold "x ?% y ==/!= 0" to "x & (y-1) ==/!= 0" iff y is power-of-two

[lebedev.ri]

Summary

I have stumbled into this by accident while preparing to extend backend x s% C ==/!= 0 handling.

While we did happen to handle this fold in most of the cases,
the folding is indirect - we fold x u% y to x & (y-1) (iff y is power-of-two),
or first turn x s% -y to x u% y; that does handle most of the cases.
But we can't turn x s% INT_MIN to x u% -INT_MIN,
and thus we end up being stuck with (x s% INT_MIN) == 0.

There is no such restriction for the more general fold:
https://rise4fun.com/Alive/IIeS

To be noted, the fold does not enforce that y is a constant,
so it may indeed increase instruction count.
This is consistent with what x u% y->x & (y-1) already does.
I think it makes sense, it's at most one (simple) extra instruction,
while remainder is really much more un-simple (and likely very costly).

[lebedev.ri]

NFC, fix comment and function name.

[xbolva00]

Seems fine.

@spatel ?

[xbolva00]

llvm/include/llvm/IR/PatternMatch.h

1006

Maybe separate patch + test for IRem?

Not sure if needed, since this fold “tests” it actually..

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1335

Do we need a ICmpInst::isEquality(Pred) test?

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1335

This is valid both for equality and all unsigned predicates: https://rise4fun.com/Alive/wp0N
But not signed ones: https://rise4fun.com/Alive/I67

Regardless, see beginning of the function:

// This fold is only valid for equality predicates.
if (!I.isEquality())
  return nullptr;

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1335

Cheers - I missed that - maybe add a TODO that other unsigned predicates could be supported?

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1335

No need: https://godbolt.org/z/XmWERN

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1335

Err, to rephrase: we don't really care about non-equality predicates here,
because the unsigned comparisons with zero will either be constant-folded,
or the predicate will be changed to an equality before we get here.

[RKSimon]

LGTM - thanks for the explanation.

[lebedev.ri]

Thank you for the review!

llvm/include/llvm/IR/PatternMatch.h

 };
 
 struct is_idiv_op {
   bool isOpType(unsigned Opcode) {
     return Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
   }
 };
 
+struct is_irem_op {
+  bool isOpType(unsigned Opcode) {
+    return Opcode == Instruction::SRem || Opcode == Instruction::URem;
+  }
+};
+
 /// Matches shift operations.
 template <typename LHS, typename RHS>
 inline BinOpPred_match<LHS, RHS, is_shift_op> m_Shift(const LHS &L,
                                                       const RHS &R) {
   return BinOpPred_match<LHS, RHS, is_shift_op>(L, R);
 }
 
 /// Matches logical shift operations.

 
 /// Matches integer division operations.
 template <typename LHS, typename RHS>
 inline BinOpPred_match<LHS, RHS, is_idiv_op> m_IDiv(const LHS &L,
                                                     const RHS &R) {
   return BinOpPred_match<LHS, RHS, is_idiv_op>(L, R);
 }
 
+/// Matches integer remainder operations.
+template <typename LHS, typename RHS>
+inline BinOpPred_match<LHS, RHS, is_irem_op> m_IRem(const LHS &L,
+                                                    const RHS &R) {
+  return BinOpPred_match<LHS, RHS, is_irem_op>(L, R);
+}
+
 //===----------------------------------------------------------------------===//
 // Class that matches exact binary ops.
 //
 template <typename SubPattern_t> struct Exact_match {
   SubPattern_t SubPattern;
 
   Exact_match(const SubPattern_t &SP) : SubPattern(SP) {}
 

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

static Instruction *processUGT_ADDCST_ADD(ICmpInst &I, Value *A, Value *B,
   // The inner add was the result of the narrow add, zero extended to the
   // wider type.  Replace it with the result computed by the intrinsic.
   IC.replaceInstUsesWith(*OrigAdd, ZExt);
 
   // The original icmp gets replaced with the overflow value.
   return ExtractValueInst::Create(Call, 1, "sadd.overflow");
 }
 
+/// If we have:
+///   icmp eq/ne (urem/srem %x, %y), 0
+/// iff %y is a power-of-two, we can replace this with a bit test:
+///   icmp eq/ne (and %x, (add %y, -1)), 0
+Instruction *InstCombiner::foldIRemByPowerOfTwoToBitTest(ICmpInst &I) {
+  // This fold is only valid for equality predicates.
+  if (!I.isEquality())
+    return nullptr;
+  ICmpInst::Predicate Pred;
+  Value *X, *Y, *Zero;
+  if (!match(&I, m_ICmp(Pred, m_OneUse(m_IRem(m_Value(X), m_Value(Y))),
+                        m_CombineAnd(m_Zero(), m_Value(Zero)))))
+    return nullptr;
+  if (!isKnownToBeAPowerOfTwo(Y, /*OrZero*/ true, 0, &I))
+    return nullptr;
+  // This may increase instruction count, we don't enforce that Y is a constant.
+  Value *Mask = Builder.CreateAdd(Y, Constant::getAllOnesValue(Y->getType()));
+  Value *Masked = Builder.CreateAnd(X, Mask);
+  return ICmpInst::Create(Instruction::ICmp, Pred, Masked, Zero);
+}
+
 // Handle  icmp pred X, 0
 Instruction *InstCombiner::foldICmpWithZero(ICmpInst &Cmp) {
   CmpInst::Predicate Pred = Cmp.getPredicate();
   if (!match(Cmp.getOperand(1), m_Zero()))
     return nullptr;
 
   // (icmp sgt smin(PosA, B) 0) -> (icmp sgt B 0)
   if (Pred == ICmpInst::ICMP_SGT) {
     Value *A, *B;
     SelectPatternResult SPR = matchSelectPattern(Cmp.getOperand(0), A, B);
     if (SPR.Flavor == SPF_SMIN) {
       if (isKnownPositive(A, DL, 0, &AC, &Cmp, &DT))
         return new ICmpInst(Pred, B, Cmp.getOperand(1));
       if (isKnownPositive(B, DL, 0, &AC, &Cmp, &DT))
         return new ICmpInst(Pred, A, Cmp.getOperand(1));
     }
   }
 
+  if (Instruction *New = foldIRemByPowerOfTwoToBitTest(Cmp))
+    return New;
+
   // Given:
   //   icmp eq/ne (urem %x, %y), 0
   // Iff %x has 0 or 1 bits set, and %y has at least 2 bits set, omit 'urem':
   //   icmp eq/ne %x, 0
   Value *X, *Y;
   if (match(Cmp.getOperand(0), m_URem(m_Value(X), m_Value(Y))) &&
       ICmpInst::isEquality(Pred)) {
     KnownBits XKnown = computeKnownBits(X, 0, &Cmp);

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

private:
 
   Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
   Instruction *foldICmpWithDominatingICmp(ICmpInst &Cmp);
   Instruction *foldICmpWithConstant(ICmpInst &Cmp);
   Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
   Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
   Instruction *foldICmpBinOp(ICmpInst &Cmp);
   Instruction *foldICmpEquality(ICmpInst &Cmp);
+  Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
   Instruction *foldICmpWithZero(ICmpInst &Cmp);
 
   Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
                                       ConstantInt *C);
   Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
                                      const APInt &C);
   Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
                                    const APInt &C);

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

Instruction *InstCombiner::visitURem(BinaryOperator &I) {
 
   if (Instruction *NarrowRem = narrowUDivURem(I, Builder))
     return NarrowRem;
 
   // X urem Y -> X and Y-1, where Y is a power of 2,
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   Type *Ty = I.getType();
   if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
+    // This may increase instruction count, we don't enforce that Y is a
+    // constant.
     Constant *N1 = Constant::getAllOnesValue(Ty);
     Value *Add = Builder.CreateAdd(Op1, N1);
     return BinaryOperator::CreateAnd(Op0, Add);
   }
 
   // 1 urem X -> zext(X != 1)
   if (match(Op0, m_One()))
     return CastInst::CreateZExtOrBitCast(Builder.CreateICmpNE(Op1, Op0), Ty);

llvm/test/Transforms/InstCombine/rem.ll

 ; CHECK-NEXT:    ret <2 x i19> [[B]]
 ;
   %B = urem <2 x i19> %A, <i19 8, i19 8>
   ret <2 x i19> %B
 }
 
 define i1 @test3a(i32 %A) {
 ; CHECK-LABEL: @test3a(
-; CHECK-NEXT:    [[B1:%.*]] = and i32 [[A:%.*]], 7
-; CHECK-NEXT:    [[C:%.*]] = icmp ne i32 [[B1]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], 7
+; CHECK-NEXT:    [[C:%.*]] = icmp ne i32 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %B = srem i32 %A, -8
   %C = icmp ne i32 %B, 0
   ret i1 %C
 }
 
 define <2 x i1> @test3a_vec(<2 x i32> %A) {
 ; CHECK-LABEL: @test3a_vec(
-; CHECK-NEXT:    [[B1:%.*]] = and <2 x i32> [[A:%.*]], <i32 7, i32 7>
-; CHECK-NEXT:    [[C:%.*]] = icmp ne <2 x i32> [[B1]], zeroinitializer
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[A:%.*]], <i32 7, i32 7>
+; CHECK-NEXT:    [[C:%.*]] = icmp ne <2 x i32> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[C]]
 ;
   %B = srem <2 x i32> %A, <i32 -8, i32 -8>
   %C = icmp ne <2 x i32> %B, zeroinitializer
   ret <2 x i1> %C
 }
 
 define i32 @test4(i32 %X, i1 %C) {

 ;
   %B = urem <2 x i32> %A, <i32 2147483648, i32 2147483648>
   %C = icmp ne <2 x i32> %B, zeroinitializer
   ret <2 x i1> %C
 }
 
 define i1 @test25(i32 %A) {
 ; CHECK-LABEL: @test25(
-; CHECK-NEXT:    [[B:%.*]] = srem i32 [[A:%.*]], -2147483648
-; CHECK-NEXT:    [[C:%.*]] = icmp ne i32 [[B]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], 2147483647
+; CHECK-NEXT:    [[C:%.*]] = icmp ne i32 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %B = srem i32 %A, 2147483648 ; signbit
   %C = icmp ne i32 %B, 0
   ret i1 %C
 }
 
 define <2 x i1> @test25_vec(<2 x i32> %A) {
 ; CHECK-LABEL: @test25_vec(
-; CHECK-NEXT:    [[B:%.*]] = srem <2 x i32> [[A:%.*]], <i32 -2147483648, i32 -2147483648>
-; CHECK-NEXT:    [[C:%.*]] = icmp ne <2 x i32> [[B]], zeroinitializer
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[A:%.*]], <i32 2147483647, i32 2147483647>
+; CHECK-NEXT:    [[C:%.*]] = icmp ne <2 x i32> [[TMP1]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[C]]
 ;
   %B = srem <2 x i32> %A, <i32 2147483648, i32 2147483648>
   %C = icmp ne <2 x i32> %B, zeroinitializer
   ret <2 x i1> %C
 }
 
 define i1 @test26(i32 %A, i32 %B) {
 ; CHECK-LABEL: @test26(
-; CHECK-NEXT:    [[C:%.*]] = shl nuw i32 1, [[B:%.*]]
-; CHECK-NEXT:    [[D:%.*]] = srem i32 [[A:%.*]], [[C]]
-; CHECK-NEXT:    [[E:%.*]] = icmp ne i32 [[D]], 0
+; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw i32 -1, [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[NOTMASK]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A:%.*]]
+; CHECK-NEXT:    [[E:%.*]] = icmp ne i32 [[TMP2]], 0
 ; CHECK-NEXT:    ret i1 [[E]]
 ;
   %C = shl i32 1, %B ; not a constant
   %D = srem i32 %A, %C
   %E = icmp ne i32 %D, 0
   ret i1 %E
 }
 
 define i1 @test27(i32 %A, i32* %remdst) {
 ; CHECK-LABEL: @test27(
 ; CHECK-NEXT:    [[B:%.*]] = srem i32 [[A:%.*]], -2147483648
 ; CHECK-NEXT:    store i32 [[B]], i32* [[REMDST:%.*]], align 1
 ; CHECK-NEXT:    [[C:%.*]] = icmp ne i32 [[B]], 0
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %B = srem i32 %A, 2147483648 ; signbit
   store i32 %B, i32* %remdst, align 1 ; extra use of rem
   %C = icmp ne i32 %B, 0
   ret i1 %C
 }
 
 define i1 @test28(i32 %A) {
 ; CHECK-LABEL: @test28(
-; CHECK-NEXT:    [[B:%.*]] = srem i32 [[A:%.*]], -2147483648
-; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[B]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], 2147483647
+; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[C]]
 ;
   %B = srem i32 %A, 2147483648 ; signbit
   %C = icmp eq i32 %B, 0 ; another equality predicate
   ret i1 %C
 }
 
 ; FP division-by-zero is not UB.