[CodeGen] [SelectionDAG] More efficient code for X % C == 0 (UREM case) (try 2)

[lebedev.ri]

Summary

I'm submitting a new revision since i don't understand how to reclaim/reopen/take over the existing one, D50222.
There is no such action in "Add Action" menu...

This implements an optimization described in Hacker's Delight 10-17: when C is constant,
the result of X % C == 0 can be computed more cheaply without actually calculating the remainder.
The motivation is discussed here: https://bugs.llvm.org/show_bug.cgi?id=35479.

Original patch D50222 by @hermord (Dmytro Shynkevych)

Notes:

• In principle, it's possible to also handle the X % C1 == C2 case, as discussed on bugzilla. This seems to require an extra branch on overflow, so I refrained from implementing this for now.
• An explicit check for when the REM can be reduced to just its LHS is included: the X % C == 0 optimization breaks test1 in test/CodeGen/X86/jump_sign.ll otherwise. I hadn't managed to find a better way to not generate worse output in this case.
• The test/CodeGen/X86/jump_sign.ll regresses, and is being fixed by a followup patch D63390.

[xbolva00]

Thanks, looks fine now (with fixed regression).

Are you going to implement also signed case? And possibly general cases?

GCC’s patch contains quite useful details for “general” rem folds, which can help you:
https://gcc.gnu.org/viewcvs/gcc/trunk/gcc/expr.c?r1=264248&r2=264247&pathrev=264248

[lebedev.ri]

In D63391#1545279, @xbolva00 wrote:

Thanks, looks fine now (with fixed regression).

Are you going to implement also signed case? And possibly general cases?

I haven't decided yet. I don't have a motivational pattern at hand
as of this moment, and all this handwritten pattern-matching is
so depressingly futile that it is all kinda pointless.

GCC’s patch contains quite useful details for “general” rem folds, which can help you:
https://gcc.gnu.org/viewcvs/gcc/trunk/gcc/expr.c?r1=264248&r2=264247&pathrev=264248

Uhm, is it okay license-wise to look at that code even?

[lebedev.ri]

Rebased

[RKSimon]

I'm submitting a new revision since i don't understand how to reclaim/reopen/take over the existing one, D50222.
There is no such action in "Add Action" menu...
Original patch D50222 by @hermord (Dmytro Shynkevych)

Add Action | Revision Actions | Commandeer Revision

[lebedev.ri]

In D63391#1545638, @RKSimon wrote:

I'm submitting a new revision since i don't understand how to reclaim/reopen/take over the existing one, D50222.
There is no such action in "Add Action" menu...
Original patch D50222 by @hermord (Dmytro Shynkevych)

Add Action | Revision Actions | Commandeer Revision

Well, yeah, that's the thing

[xbolva00]

In D63391#1545733, @lebedev.ri wrote:

In D63391#1545638, @RKSimon wrote:

I'm submitting a new revision since i don't understand how to reclaim/reopen/take over the existing one, D50222.
There is no such action in "Add Action" menu...
Original patch D50222 by @hermord (Dmytro Shynkevych)

Add Action | Revision Actions | Commandeer Revision

Well, yeah, that's the thing

Revision is closed, so you cannot see it. Anyway, just continue this revision.

[spatel]

include/llvm/CodeGen/TargetLowering.h

4058–4062

Formatting: use the current guideline 'lowerCamelCase' on these function names?

lib/CodeGen/SelectionDAG/TargetLowering.cpp

4444–4445

Not sure if this legality check is necessary to avoid infinite looping and/or pick up extra diffs, but we don't normally want to distinguish 'custom' from 'legal' like this.

Can we use this simpler check?

if (!isOperationLegalOrCustom(ISD::MUL, REMVT)) 
  return SDValue()

That is, it doesn't matter what stage of combining we're in. If the target supports MUL for this type, this is always a good transfom for performance. That might allow removing the earlier 'isTypeLegal()' check too.

4488–4489

See earlier comment about legality of the MUL. Can we use the simpler check independent of combining stage?

[lebedev.ri]

Address review notes - just use isOperationLegalOrCustom(), entirety of check-llvm-codegen still passes at least.

[spatel]

Logic looks right; I just pointed out some more formatting nits.

@RKSimon started reviewing the original patch, so let's see if he has comments.

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3409

"a a"
Period at end of sentence.

4411–4412

Could shorten:
REMNode -> Rem
CompNode -> check that this operand is zero before we call this, rather than pass it as a param?

4441

Period at end of sentence.

4445

Period at end of sentence.

4465

Period at end of sentence.

4482

Period at end of sentence.

4484

Period at end of sentence.

[xbolva00]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

4411–4412

In terms of possible future general case of this REM == C fold... I think it is okay it to pass it.

[lebedev.ri]

Landed regression fix, rebased, addressed comment comments. ping.

[xbolva00]

Looks ok

[RKSimon]

LGTM - I'd have preferred that non-uniform vectors were supported straight away but this is alright for now.

[lebedev.ri]

Thank you for the reviews!

[lebedev.ri]

http://lab.llvm.org:8011/builders/clang-cmake-x86_64-sde-avx512-linux/builds/23789 complains about this/rL364564.
Since new .exec.status entries are present i'm gonna guess the tests are actually failing.

[lebedev.ri]

Yep, this clearly miscompiles things.

[lebedev.ri]

So the first thought about multiplicativeInverse() being broken does not appear to be correct
(although that interface is extremely susceptible to misuse),

The miscompiles in test-suite happened for urem by 100 (and 10, did not check for more cases).
This code produces:

define i32 @test_urem_100(i32 %X) nounwind readnone {
; X86-LABEL: test_urem_100:
; X86:       # %bb.0:
; X86-NEXT:    imull $-1030792151, {{[0-9]+}}(%esp), %ecx # imm = 0xC28F5C29
; X86-NEXT:    rorl $2, %ecx
; X86-NEXT:    xorl %eax, %eax
; X86-NEXT:    cmpl $171798692, %ecx # imm = 0xA3D70A4
; X86-NEXT:    setb %al
; X86-NEXT:    retl
;
; X64-LABEL: test_urem_100:
; X64:       # %bb.0:
; X64-NEXT:    imull $-1030792151, %edi, %ecx # imm = 0xC28F5C29
; X64-NEXT:    rorl $2, %ecx
; X64-NEXT:    xorl %eax, %eax
; X64-NEXT:    cmpl $171798692, %ecx # imm = 0xA3D70A4
; X64-NEXT:    setb %al
; X64-NEXT:    retq
  %urem = urem i32 %X, 100
  %cmp = icmp eq i32 %urem, 0
  %ret = zext i1 %cmp to i32
  ret i32 %ret
}

GCC: https://godbolt.org/z/ks6Wm-

imull   $-1030792151, %edi, %edi
rorl    $2, %edi
cmpl    $42949672, %edi
setbe   %al

The difference is in the constant we compare with: 171798692 (patch) vs 42949672 (GCC).

[lebedev.ri]

llvm/trunk/lib/CodeGen/SelectionDAG/TargetLowering.cpp

4525–4526 ↗

(On Diff #206884)

Got it, this should be dividing by D, not D l>> cttz(D)

[lebedev.ri]

Fix miscompile (it was even visible in already existing tests!!!) by properly calculating the constant for new comparison.

include/llvm/CodeGen/TargetLowering.h

SDValue foldSetCCWithAnd(EVT VT, SDValue N0, SDValue N1, ISD::CondCode Cond,
                            const SDLoc &DL, DAGCombinerInfo &DCI) const;
   SDValue foldSetCCWithBinOp(EVT VT, SDValue N0, SDValue N1, ISD::CondCode Cond,
                              const SDLoc &DL, DAGCombinerInfo &DCI) const;
 
   SDValue optimizeSetCCOfSignedTruncationCheck(EVT SCCVT, SDValue N0,
                                                SDValue N1, ISD::CondCode Cond,
                                                DAGCombinerInfo &DCI,
                                                const SDLoc &DL) const;
+
+  SDValue prepareUREMEqFold(EVT VT, SDValue N0, SDValue N1, ISD::CondCode Cond,
+                            DAGCombinerInfo &DCI, const SDLoc &DL,
+                            SmallVectorImpl<SDNode *> &Created) const;
+  SDValue buildUREMEqFold(EVT VT, SDValue N0, SDValue N1, ISD::CondCode Cond,
+                          DAGCombinerInfo &DCI, const SDLoc &DL) const;
 };
 
 /// Given an LLVM IR type and return type attributes, compute the return value
 /// EVTs and flags, and optionally also the offsets, if the return value is
 /// being lowered to memory.
 void GetReturnInfo(CallingConv::ID CC, Type *ReturnType, AttributeList attr,
                    SmallVectorImpl<ISD::OutputArg> &Outs,
                    const TargetLowering &TLI, const DataLayout &DL);
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_TARGETLOWERING_H

lib/CodeGen/SelectionDAG/TargetLowering.cpp

if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
         N1.getOpcode() == ISD::XOR)
       if (SDValue V = foldSetCCWithBinOp(VT, N1, N0, Cond, dl, DCI))
         return V;
 
     if (SDValue V = foldSetCCWithAnd(VT, N0, N1, Cond, dl, DCI))
       return V;
   }
 
+  // Fold remainder of division by a constant.
+  if (N0.getOpcode() == ISD::UREM && N0.hasOneUse() &&
+      (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
+    AttributeList Attr = DAG.getMachineFunction().getFunction().getAttributes();
+
+    // When division is cheap or optimizing for minimum size,
+    // fall through to DIVREM creation by skipping this fold.
+    if (!isIntDivCheap(VT, Attr) && !Attr.hasFnAttribute(Attribute::MinSize))
+      if (SDValue Folded = buildUREMEqFold(VT, N0, N1, Cond, DCI, dl))
+        return Folded;
+  }
+
   // Fold away ALL boolean setcc's.
   if (N0.getValueType().getScalarType() == MVT::i1 && foldBooleans) {
     SDValue Temp;
     switch (Cond) {
     default: llvm_unreachable("Unknown integer setcc!");
     case ISD::SETEQ:  // X == Y  -> ~(X^Y)
       Temp = DAG.getNode(ISD::XOR, dl, OpVT, N0, N1);
       N0 = DAG.getNOT(dl, Temp, OpVT);
SDValue TargetLowering::BuildUDIV(SDNode *N, SelectionDAG &DAG,
   Q = DAG.getNode(ISD::SRL, dl, VT, Q, PostShift);
   Created.push_back(Q.getNode());
 
   SDValue One = DAG.getConstant(1, dl, VT);
   SDValue IsOne = DAG.getSetCC(dl, VT, N1, One, ISD::SETEQ);
   return DAG.getSelect(dl, VT, IsOne, N0, Q);
 }
 
+/// Given an ISD::UREM used only by an ISD::SETEQ or ISD::SETNE
+/// where the divisor is constant and the comparison target is zero,
+/// return a DAG expression that will generate the same comparison result
+/// using only multiplications, additions and shifts/rotations.
+/// Ref: "Hacker's Delight" 10-17.
+SDValue TargetLowering::buildUREMEqFold(EVT VT, SDValue REMNode,
+                                        SDValue CompNode, ISD::CondCode Cond,
+                                        DAGCombinerInfo &DCI,
+                                        const SDLoc &DL) const {
+  SmallVector<SDNode *, 2> Built;
+  if (SDValue Folded =
+          prepareUREMEqFold(VT, REMNode, CompNode, Cond, DCI, DL, Built)) {
+    for (SDNode *N : Built)
+      DCI.AddToWorklist(N);
+    return Folded;
+  }
+
+  return SDValue();
+}
+
+SDValue
+TargetLowering::prepareUREMEqFold(EVT VT, SDValue REMNode, SDValue CompNode,
+                                  ISD::CondCode Cond, DAGCombinerInfo &DCI,
+                                  const SDLoc &DL,
+                                  SmallVectorImpl<SDNode *> &Created) const {
+  // fold (seteq/ne (urem N, D), 0) -> (setule/ugt (rotr (mul N, P), K), Q)
+  // - D must be constant with D = D0 * 2^K where D0 is odd and D0 != 1
+  // - P is the multiplicative inverse of D0 modulo 2^W
+  // - Q = floor((2^W - 1) / D0)
+  // where W is the width of the common type of N and D.
+  assert((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
+         "Only applicable for (in)equality comparisons.");
+
+  EVT REMVT = REMNode->getValueType(0);
+
+  // If MUL is unavailable, we cannot proceed in any case.
+  if (!isOperationLegalOrCustom(ISD::MUL, REMVT))
+    return SDValue();
+
+  // TODO: Add non-uniform constant support.
+  ConstantSDNode *Divisor = isConstOrConstSplat(REMNode->getOperand(1));
+  ConstantSDNode *CompTarget = isConstOrConstSplat(CompNode);
+  if (!Divisor || !CompTarget || Divisor->isNullValue() ||
+      !CompTarget->isNullValue())
+    return SDValue();
+
+  const APInt &D = Divisor->getAPIntValue();
+
+  // Decompose D into D0 * 2^K
+  unsigned K = D.countTrailingZeros();
+  bool DivisorIsEven = (K != 0);
+  APInt D0 = D.lshr(K);
+
+  // The fold is invalid when D0 == 1.
+  // This is reachable because visitSetCC happens before visitREM.
+  if (D0.isOneValue())
+    return SDValue();
+
+  // P = inv(D0, 2^W)
+  // 2^W requires W + 1 bits, so we have to extend and then truncate.
+  unsigned W = D.getBitWidth();
+  APInt P = D0.zext(W + 1)
+                .multiplicativeInverse(APInt::getHighBitsSet(W + 1, 1))
+                .trunc(W);
+
+  // Q = floor((2^W - 1) / D0)
+  APInt Q = APInt::getAllOnesValue(W).udiv(D0);
+
+  SelectionDAG &DAG = DCI.DAG;
+
+  SDValue PVal = DAG.getConstant(P, DL, REMVT);
+  SDValue QVal = DAG.getConstant(Q, DL, REMVT);
+  // (mul N, P)
+  SDValue Op1 = DAG.getNode(ISD::MUL, DL, REMVT, REMNode->getOperand(0), PVal);
+  Created.push_back(Op1.getNode());
+
+  // Rotate right only if D was even.
+  if (DivisorIsEven) {
+    // We need ROTR to do this.
+    if (!isOperationLegalOrCustom(ISD::ROTR, REMVT))
+      return SDValue();
+    SDValue ShAmt =
+        DAG.getConstant(K, DL, getShiftAmountTy(REMVT, DAG.getDataLayout()));
+    SDNodeFlags Flags;
+    Flags.setExact(true);
+    // UREM: (rotr (mul N, P), K)
+    Op1 = DAG.getNode(ISD::ROTR, DL, REMVT, Op1, ShAmt, Flags);
+    Created.push_back(Op1.getNode());
+  }
+
+  // UREM: (setule/setugt (rotr (mul N, P), K), Q)
+  return DAG.getSetCC(DL, VT, Op1, QVal,
+                      ((Cond == ISD::SETEQ) ? ISD::SETULE : ISD::SETUGT));
+}
+
 bool TargetLowering::
 verifyReturnAddressArgumentIsConstant(SDValue Op, SelectionDAG &DAG) const {
   if (!isa<ConstantSDNode>(Op.getOperand(0))) {
     DAG.getContext()->emitError("argument to '__builtin_return_address' must "
                                 "be a constant integer");
     return true;
   }
 

test/CodeGen/AArch64/urem-seteq-optsize.ll

; CHECK-NEXT:    ret
   ret i32 %ret
 }
 
 define i32 @test_optsize(i32 %X) optsize nounwind readnone {
 ; CHECK-LABEL: test_optsize:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    mov w8, #52429
 ; CHECK-NEXT:    movk w8, #52428, lsl #16
-; CHECK-NEXT:    umull x8, w0, w8
-; CHECK-NEXT:    lsr x8, x8, #34
-; CHECK-NEXT:    add w8, w8, w8, lsl #2
-; CHECK-NEXT:    mov w9, #-10
-; CHECK-NEXT:    cmp w0, w8
+; CHECK-NEXT:    mov w9, #13108
+; CHECK-NEXT:    movk w9, #13107, lsl #16
+; CHECK-NEXT:    mul w8, w0, w8
+; CHECK-NEXT:    mov w10, #-10
+; CHECK-NEXT:    cmp w8, w9
 ; CHECK-NEXT:    mov w8, #42
-; CHECK-NEXT:    csel w0, w8, w9, eq
+; CHECK-NEXT:    csel w0, w8, w10, lo
 ; CHECK-NEXT:    ret
   %rem = urem i32 %X, 5
   %cmp = icmp eq i32 %rem, 0
   %ret = select i1 %cmp, i32 42, i32 -10
   ret i32 %ret
 }

test/CodeGen/AArch64/urem-seteq-vec-splat.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=aarch64-unknown-linux-gnu < %s | FileCheck %s
 
 ; Tests BuildUREMEqFold for 4 x i32 splat vectors with odd divisor.
 ; See urem-seteq.ll for justification behind constants emitted.
 define <4 x i32> @test_urem_odd_vec_i32(<4 x i32> %X) nounwind readnone {
 ; CHECK-LABEL: test_urem_odd_vec_i32:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    mov w8, #52429
 ; CHECK-NEXT:    movk w8, #52428, lsl #16
 ; CHECK-NEXT:    dup v2.4s, w8
-; CHECK-NEXT:    umull2 v3.2d, v0.4s, v2.4s
-; CHECK-NEXT:    umull v2.2d, v0.2s, v2.2s
-; CHECK-NEXT:    uzp2 v2.4s, v2.4s, v3.4s
-; CHECK-NEXT:    movi v1.4s, #5
-; CHECK-NEXT:    ushr v2.4s, v2.4s, #2
-; CHECK-NEXT:    mls v0.4s, v2.4s, v1.4s
-; CHECK-NEXT:    cmeq v0.4s, v0.4s, #0
+; CHECK-NEXT:    movi v1.16b, #51
+; CHECK-NEXT:    mul v0.4s, v0.4s, v2.4s
+; CHECK-NEXT:    cmhs v0.4s, v1.4s, v0.4s
 ; CHECK-NEXT:    movi v1.4s, #1
 ; CHECK-NEXT:    and v0.16b, v0.16b, v1.16b
 ; CHECK-NEXT:    ret
   %urem = urem <4 x i32> %X, <i32 5, i32 5, i32 5, i32 5>
   %cmp = icmp eq <4 x i32> %urem, <i32 0, i32 0, i32 0, i32 0>
   %ret = zext <4 x i1> %cmp to <4 x i32>
   ret <4 x i32> %ret
 }
 
 ; Like test_urem_odd_vec_i32, but with 8 x i16 vectors.
 define <8 x i16> @test_urem_odd_vec_i16(<8 x i16> %X) nounwind readnone {
 ; CHECK-LABEL: test_urem_odd_vec_i16:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    mov w8, #52429
 ; CHECK-NEXT:    dup v2.8h, w8
-; CHECK-NEXT:    umull2 v3.4s, v0.8h, v2.8h
-; CHECK-NEXT:    umull v2.4s, v0.4h, v2.4h
-; CHECK-NEXT:    uzp2 v2.8h, v2.8h, v3.8h
-; CHECK-NEXT:    movi v1.8h, #5
-; CHECK-NEXT:    ushr v2.8h, v2.8h, #2
-; CHECK-NEXT:    mls v0.8h, v2.8h, v1.8h
-; CHECK-NEXT:    cmeq v0.8h, v0.8h, #0
+; CHECK-NEXT:    movi v1.16b, #51
+; CHECK-NEXT:    mul v0.8h, v0.8h, v2.8h
+; CHECK-NEXT:    cmhs v0.8h, v1.8h, v0.8h
 ; CHECK-NEXT:    movi v1.8h, #1
 ; CHECK-NEXT:    and v0.16b, v0.16b, v1.16b
 ; CHECK-NEXT:    ret
   %urem = urem <8 x i16> %X, <i16 5, i16 5, i16 5, i16 5,
                               i16 5, i16 5, i16 5, i16 5>
   %cmp = icmp eq <8 x i16> %urem, <i16 0, i16 0, i16 0, i16 0,
                                    i16 0, i16 0, i16 0, i16 0>
   %ret = zext <8 x i1> %cmp to <8 x i16>

test/CodeGen/AArch64/urem-seteq.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=aarch64-unknown-linux-gnu < %s | FileCheck %s
 
 ; This tests the BuildREMEqFold optimization with UREM, i32, odd divisor, SETEQ.
 ; The corresponding pseudocode is:
 ; Q <- [N * multInv(5, 2^32)] <=> [N * 0xCCCCCCCD] <=> [N * (-858993459)]
 ; res <- [Q <= (2^32 - 1) / 5] <=> [Q <= 858993459] <=> [Q < 858993460]
 define i32 @test_urem_odd(i32 %X) nounwind readnone {
 ; CHECK-LABEL: test_urem_odd:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    mov w8, #52429
 ; CHECK-NEXT:    movk w8, #52428, lsl #16
-; CHECK-NEXT:    umull x8, w0, w8
-; CHECK-NEXT:    lsr x8, x8, #34
-; CHECK-NEXT:    add w8, w8, w8, lsl #2
-; CHECK-NEXT:    cmp w0, w8
-; CHECK-NEXT:    cset w0, eq
+; CHECK-NEXT:    mov w9, #13108
+; CHECK-NEXT:    mul w8, w0, w8
+; CHECK-NEXT:    movk w9, #13107, lsl #16
+; CHECK-NEXT:    cmp w8, w9
+; CHECK-NEXT:    cset w0, lo
 ; CHECK-NEXT:    ret
   %urem = urem i32 %X, 5
   %cmp = icmp eq i32 %urem, 0
   %ret = zext i1 %cmp to i32
   ret i32 %ret
 }
 
 ; This is like test_urem_odd, except the divisor has bit 30 set.
 define i32 @test_urem_odd_bit30(i32 %X) nounwind readnone {
 ; CHECK-LABEL: test_urem_odd_bit30:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    mov w8, #-11
-; CHECK-NEXT:    umull x8, w0, w8
-; CHECK-NEXT:    mov w9, #3
-; CHECK-NEXT:    lsr x8, x8, #62
-; CHECK-NEXT:    movk w9, #16384, lsl #16
-; CHECK-NEXT:    msub w8, w8, w9, w0
-; CHECK-NEXT:    cmp w8, #0 // =0
-; CHECK-NEXT:    cset w0, eq
+; CHECK-NEXT:    mov w8, #43691
+; CHECK-NEXT:    movk w8, #27306, lsl #16
+; CHECK-NEXT:    mul w8, w0, w8
+; CHECK-NEXT:    cmp w8, #4 // =4
+; CHECK-NEXT:    cset w0, lo
 ; CHECK-NEXT:    ret
   %urem = urem i32 %X, 1073741827
   %cmp = icmp eq i32 %urem, 0
   %ret = zext i1 %cmp to i32
   ret i32 %ret
 }
 
 ; This is like test_urem_odd, except the divisor has bit 31 set.
 define i32 @test_urem_odd_bit31(i32 %X) nounwind readnone {
 ; CHECK-LABEL: test_urem_odd_bit31:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    mov w8, w0
-; CHECK-NEXT:    lsl x9, x8, #30
-; CHECK-NEXT:    sub x8, x9, x8
-; CHECK-NEXT:    lsr x8, x8, #61
-; CHECK-NEXT:    mov w9, #-2147483645
-; CHECK-NEXT:    msub w8, w8, w9, w0
-; CHECK-NEXT:    cmp w8, #0 // =0
-; CHECK-NEXT:    cset w0, eq
+; CHECK-NEXT:    mov w8, #43691
+; CHECK-NEXT:    movk w8, #10922, lsl #16
+; CHECK-NEXT:    mul w8, w0, w8
+; CHECK-NEXT:    cmp w8, #2 // =2
+; CHECK-NEXT:    cset w0, lo
 ; CHECK-NEXT:    ret
   %urem = urem i32 %X, 2147483651
   %cmp = icmp eq i32 %urem, 0
   %ret = zext i1 %cmp to i32
   ret i32 %ret
 }
 
 ; This tests the BuildREMEqFold optimization with UREM, i16, even divisor, SETNE.
 ; In this case, D <=> 14 <=> 7 * 2^1, so D0 = 7 and K = 1.
 ; The corresponding pseudocode is:
 ; Q <- [N * multInv(D0, 2^16)] <=> [N * multInv(7, 2^16)] <=> [N * 28087]
 ; Q <- [Q >>rot K] <=> [Q >>rot 1]
 ; res <- ![Q <= (2^16 - 1) / 7] <=> ![Q <= 9362] <=> [Q > 9362]
 define i16 @test_urem_even(i16 %X) nounwind readnone {
 ; CHECK-LABEL: test_urem_even:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    mov w10, #9363
-; CHECK-NEXT:    ubfx w9, w0, #1, #15
-; CHECK-NEXT:    movk w10, #37449, lsl #16
-; CHECK-NEXT:    umull x9, w9, w10
+; CHECK-NEXT:    mov w9, #28087
 ; CHECK-NEXT:    and w8, w0, #0xffff
-; CHECK-NEXT:    lsr x9, x9, #34
-; CHECK-NEXT:    mov w10, #14
-; CHECK-NEXT:    msub w8, w9, w10, w8
-; CHECK-NEXT:    cmp w8, #0 // =0
-; CHECK-NEXT:    cset w0, ne
+; CHECK-NEXT:    movk w9, #46811, lsl #16
+; CHECK-NEXT:    mul w8, w8, w9
+; CHECK-NEXT:    mov w9, #18724
+; CHECK-NEXT:    ror w8, w8, #1
+; CHECK-NEXT:    movk w9, #9362, lsl #16
+; CHECK-NEXT:    cmp w8, w9
+; CHECK-NEXT:    cset w0, hi
 ; CHECK-NEXT:    ret
   %urem = urem i16 %X, 14
   %cmp = icmp ne i16 %urem, 0
   %ret = zext i1 %cmp to i16
   ret i16 %ret
 }
 
 ; This is like test_urem_even, except the divisor has bit 30 set.
 define i32 @test_urem_even_bit30(i32 %X) nounwind readnone {
 ; CHECK-LABEL: test_urem_even_bit30:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    mov w8, #-415
-; CHECK-NEXT:    umull x8, w0, w8
-; CHECK-NEXT:    mov w9, #104
-; CHECK-NEXT:    lsr x8, x8, #62
-; CHECK-NEXT:    movk w9, #16384, lsl #16
-; CHECK-NEXT:    msub w8, w8, w9, w0
-; CHECK-NEXT:    cmp w8, #0 // =0
-; CHECK-NEXT:    cset w0, eq
+; CHECK-NEXT:    mov w8, #20165
+; CHECK-NEXT:    movk w8, #64748, lsl #16
+; CHECK-NEXT:    mul w8, w0, w8
+; CHECK-NEXT:    ror w8, w8, #3
+; CHECK-NEXT:    cmp w8, #32 // =32
+; CHECK-NEXT:    cset w0, lo
 ; CHECK-NEXT:    ret
   %urem = urem i32 %X, 1073741928
   %cmp = icmp eq i32 %urem, 0
   %ret = zext i1 %cmp to i32
   ret i32 %ret
 }
 
 ; This is like test_urem_odd, except the divisor has bit 31 set.
 define i32 @test_urem_even_bit31(i32 %X) nounwind readnone {
 ; CHECK-LABEL: test_urem_even_bit31:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    mov w8, #65435
-; CHECK-NEXT:    movk w8, #32767, lsl #16
-; CHECK-NEXT:    umull x8, w0, w8
-; CHECK-NEXT:    mov w9, #102
-; CHECK-NEXT:    lsr x8, x8, #62
-; CHECK-NEXT:    movk w9, #32768, lsl #16
-; CHECK-NEXT:    msub w8, w8, w9, w0
-; CHECK-NEXT:    cmp w8, #0 // =0
-; CHECK-NEXT:    cset w0, eq
+; CHECK-NEXT:    mov w8, #64251
+; CHECK-NEXT:    movk w8, #47866, lsl #16
+; CHECK-NEXT:    mul w8, w0, w8
+; CHECK-NEXT:    ror w8, w8, #1
+; CHECK-NEXT:    cmp w8, #4 // =4
+; CHECK-NEXT:    cset w0, lo
 ; CHECK-NEXT:    ret
   %urem = urem i32 %X, 2147483750
   %cmp = icmp eq i32 %urem, 0
   %ret = zext i1 %cmp to i32
   ret i32 %ret
 }
 
 ; We should not proceed with this fold if the divisor is 1 or -1

test/CodeGen/X86/jump_sign.ll

 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    jne .LBB12_5
 ; CHECK-NEXT:  # %bb.3: # %sw.bb
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    jne .LBB12_8
 ; CHECK-NEXT:  # %bb.4: # %if.end29
 ; CHECK-NEXT:    movzwl (%eax), %eax
+; CHECK-NEXT:    imull $-13107, %eax, %eax # imm = 0xCCCD
+; CHECK-NEXT:    rorw %ax
 ; CHECK-NEXT:    movzwl %ax, %eax
-; CHECK-NEXT:    imull $52429, %eax, %ecx # imm = 0xCCCD
-; CHECK-NEXT:    shrl $18, %ecx
-; CHECK-NEXT:    andl $-2, %ecx
-; CHECK-NEXT:    leal (%ecx,%ecx,4), %ecx
-; CHECK-NEXT:    cmpw %cx, %ax
-; CHECK-NEXT:    jne .LBB12_5
+; CHECK-NEXT:    cmpl $13108, %eax # imm = 0x3334
+; CHECK-NEXT:    jae .LBB12_5
 ; CHECK-NEXT:  .LBB12_8: # %if.then44
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    je .LBB12_9
 ; CHECK-NEXT:  # %bb.10: # %if.else.i104
 ; CHECK-NEXT:    retl
 ; CHECK-NEXT:  .LBB12_5: # %sw.default
 ; CHECK-NEXT:    xorl %eax, %eax

test/CodeGen/X86/omit-urem-of-power-of-two-or-zero-when-comparing-with-zero.ll

; CHECK-NEXT:    retq
   %t3 = icmp eq i32 %t2, 0
   ret i1 %t3
 }
 
 define i1 @p2_scalar_shifted_urem_by_const(i32 %x, i32 %y) {
 ; CHECK-LABEL: p2_scalar_shifted_urem_by_const:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movl %esi, %ecx
-; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
 ; CHECK-NEXT:    andl $1, %edi
 ; CHECK-NEXT:    # kill: def $cl killed $cl killed $ecx
 ; CHECK-NEXT:    shll %cl, %edi
-; CHECK-NEXT:    movl $2863311531, %eax # imm = 0xAAAAAAAB
-; CHECK-NEXT:    imulq %rdi, %rax
-; CHECK-NEXT:    shrq $33, %rax
-; CHECK-NEXT:    leal (%rax,%rax,2), %eax
-; CHECK-NEXT:    cmpl %eax, %edi
-; CHECK-NEXT:    sete %al
+; CHECK-NEXT:    imull $-1431655765, %edi, %eax # imm = 0xAAAAAAAB
+; CHECK-NEXT:    cmpl $1431655766, %eax # imm = 0x55555556
+; CHECK-NEXT:    setb %al
 ; CHECK-NEXT:    retq
   %t0 = and i32 %x, 1 ; clearly a power-of-two or zero
   %t1 = shl i32 %t0, %y ; will still be a power-of-two or zero with any %y
   %t2 = urem i32 %t1, 3 ; '3' is clearly not a power of two
   %t3 = icmp eq i32 %t2, 0
   ret i1 %t3
 }
 
 define i1 @p3_scalar_shifted2_urem_by_const(i32 %x, i32 %y) {
 ; CHECK-LABEL: p3_scalar_shifted2_urem_by_const:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movl %esi, %ecx
-; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
 ; CHECK-NEXT:    andl $2, %edi
 ; CHECK-NEXT:    # kill: def $cl killed $cl killed $ecx
 ; CHECK-NEXT:    shll %cl, %edi
-; CHECK-NEXT:    movl $2863311531, %eax # imm = 0xAAAAAAAB
-; CHECK-NEXT:    imulq %rdi, %rax
-; CHECK-NEXT:    shrq $33, %rax
-; CHECK-NEXT:    leal (%rax,%rax,2), %eax
-; CHECK-NEXT:    cmpl %eax, %edi
-; CHECK-NEXT:    sete %al
+; CHECK-NEXT:    imull $-1431655765, %edi, %eax # imm = 0xAAAAAAAB
+; CHECK-NEXT:    cmpl $1431655766, %eax # imm = 0x55555556
+; CHECK-NEXT:    setb %al
 ; CHECK-NEXT:    retq
   %t0 = and i32 %x, 2 ; clearly a power-of-two or zero
   %t1 = shl i32 %t0, %y ; will still be a power-of-two or zero with any %y
   %t2 = urem i32 %t1, 3 ; '3' is clearly not a power of two
   %t3 = icmp eq i32 %t2, 0
   ret i1 %t3
 }
 

 
 ;------------------------------------------------------------------------------;
 ; Basic negative tests
 ;------------------------------------------------------------------------------;
 
 define i1 @n0_urem_of_maybe_not_power_of_two(i32 %x, i32 %y) {
 ; CHECK-LABEL: n0_urem_of_maybe_not_power_of_two:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
 ; CHECK-NEXT:    andl $3, %edi
-; CHECK-NEXT:    movl $2863311531, %eax # imm = 0xAAAAAAAB
-; CHECK-NEXT:    imulq %rdi, %rax
-; CHECK-NEXT:    shrq $33, %rax
-; CHECK-NEXT:    leal (%rax,%rax,2), %eax
-; CHECK-NEXT:    cmpl %eax, %edi
-; CHECK-NEXT:    sete %al
+; CHECK-NEXT:    imull $-1431655765, %edi, %eax # imm = 0xAAAAAAAB
+; CHECK-NEXT:    cmpl $1431655766, %eax # imm = 0x55555556
+; CHECK-NEXT:    setb %al
 ; CHECK-NEXT:    retq
   %t0 = and i32 %x, 3 ; up to two bits set, not power-of-two
   %t1 = urem i32 %t0, 3
   %t2 = icmp eq i32 %t1, 0
   ret i1 %t2
 }
 
 define i1 @n1_urem_by_maybe_power_of_two(i32 %x, i32 %y) {

test/CodeGen/X86/urem-seteq-optsize.ll

; X64-NEXT:    retq
   %cmp = icmp eq i32 %rem, 0
   %ret = select i1 %cmp, i32 42, i32 -10
   ret i32 %ret
 }
 
 define i32 @test_optsize(i32 %X) optsize nounwind readnone {
 ; X86-LABEL: test_optsize:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl $-858993459, %edx # imm = 0xCCCCCCCD
-; X86-NEXT:    movl %ecx, %eax
-; X86-NEXT:    mull %edx
-; X86-NEXT:    shrl $2, %edx
-; X86-NEXT:    leal (%edx,%edx,4), %eax
-; X86-NEXT:    cmpl %eax, %ecx
+; X86-NEXT:    imull $-858993459, {{[0-9]+}}(%esp), %eax # imm = 0xCCCCCCCD
+; X86-NEXT:    cmpl $858993460, %eax # imm = 0x33333334
 ; X86-NEXT:    movl $42, %eax
-; X86-NEXT:    je .LBB1_2
+; X86-NEXT:    jb .LBB1_2
 ; X86-NEXT:  # %bb.1:
 ; X86-NEXT:    movl $-10, %eax
 ; X86-NEXT:  .LBB1_2:
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_optsize:
 ; X64:       # %bb.0:
-; X64-NEXT:    movl %edi, %eax
-; X64-NEXT:    movl $3435973837, %ecx # imm = 0xCCCCCCCD
-; X64-NEXT:    imulq %rax, %rcx
-; X64-NEXT:    shrq $34, %rcx
-; X64-NEXT:    leal (%rcx,%rcx,4), %eax
-; X64-NEXT:    cmpl %eax, %edi
+; X64-NEXT:    imull $-858993459, %edi, %eax # imm = 0xCCCCCCCD
+; X64-NEXT:    cmpl $858993460, %eax # imm = 0x33333334
 ; X64-NEXT:    movl $42, %ecx
 ; X64-NEXT:    movl $-10, %eax
-; X64-NEXT:    cmovel %ecx, %eax
+; X64-NEXT:    cmovbl %ecx, %eax
 ; X64-NEXT:    retq
   %rem = urem i32 %X, 5
   %cmp = icmp eq i32 %rem, 0
   %ret = select i1 %cmp, i32 42, i32 -10
   ret i32 %ret
 }

test/CodeGen/X86/urem-seteq-vec-splat.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=x86_64-unknown-linux-gnu -mattr=+sse2 < %s | FileCheck %s --check-prefixes=CHECK,CHECK-SSE,CHECK-SSE2
 ; RUN: llc -mtriple=x86_64-unknown-linux-gnu -mattr=+sse4.1 < %s | FileCheck %s --check-prefixes=CHECK,CHECK-SSE,CHECK-SSE41
 ; RUN: llc -mtriple=x86_64-unknown-linux-gnu -mattr=+avx < %s | FileCheck %s --check-prefixes=CHECK,CHECK-AVX,CHECK-AVX1
 ; RUN: llc -mtriple=x86_64-unknown-linux-gnu -mattr=+avx2 < %s | FileCheck %s --check-prefixes=CHECK,CHECK-AVX,CHECK-AVX2
 ; RUN: llc -mtriple=x86_64-unknown-linux-gnu -mattr=+avx512f,+avx512vl < %s | FileCheck %s --check-prefixes=CHECK,CHECK-AVX,CHECK-AVX512VL
 
 ; Tests BuildUREMEqFold for 4 x i32 splat vectors with odd divisor.
 ; See urem-seteq.ll for justification behind constants emitted.
 define <4 x i32> @test_urem_odd_vec_i32(<4 x i32> %X) nounwind readnone {
 ; CHECK-SSE2-LABEL: test_urem_odd_vec_i32:
 ; CHECK-SSE2:       # %bb.0:
 ; CHECK-SSE2-NEXT:    movdqa {{.*#+}} xmm1 = [3435973837,3435973837,3435973837,3435973837]
-; CHECK-SSE2-NEXT:    movdqa %xmm0, %xmm2
+; CHECK-SSE2-NEXT:    pshufd {{.*#+}} xmm2 = xmm0[1,1,3,3]
+; CHECK-SSE2-NEXT:    pmuludq %xmm1, %xmm0
+; CHECK-SSE2-NEXT:    pshufd {{.*#+}} xmm0 = xmm0[0,2,2,3]
 ; CHECK-SSE2-NEXT:    pmuludq %xmm1, %xmm2
-; CHECK-SSE2-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[1,3,2,3]
-; CHECK-SSE2-NEXT:    pshufd {{.*#+}} xmm3 = xmm0[1,1,3,3]
-; CHECK-SSE2-NEXT:    pmuludq %xmm1, %xmm3
-; CHECK-SSE2-NEXT:    pshufd {{.*#+}} xmm1 = xmm3[1,3,2,3]
-; CHECK-SSE2-NEXT:    punpckldq {{.*#+}} xmm2 = xmm2[0],xmm1[0],xmm2[1],xmm1[1]
-; CHECK-SSE2-NEXT:    psrld $2, %xmm2
-; CHECK-SSE2-NEXT:    movdqa %xmm2, %xmm1
-; CHECK-SSE2-NEXT:    pslld $2, %xmm1
-; CHECK-SSE2-NEXT:    paddd %xmm2, %xmm1
-; CHECK-SSE2-NEXT:    psubd %xmm1, %xmm0
-; CHECK-SSE2-NEXT:    pxor %xmm1, %xmm1
-; CHECK-SSE2-NEXT:    pcmpeqd %xmm1, %xmm0
-; CHECK-SSE2-NEXT:    psrld $31, %xmm0
+; CHECK-SSE2-NEXT:    pshufd {{.*#+}} xmm1 = xmm2[0,2,2,3]
+; CHECK-SSE2-NEXT:    punpckldq {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1]
+; CHECK-SSE2-NEXT:    pxor {{.*}}(%rip), %xmm0
+; CHECK-SSE2-NEXT:    pcmpgtd {{.*}}(%rip), %xmm0
+; CHECK-SSE2-NEXT:    pandn {{.*}}(%rip), %xmm0
 ; CHECK-SSE2-NEXT:    retq
 ;
 ; CHECK-SSE41-LABEL: test_urem_odd_vec_i32:
 ; CHECK-SSE41:       # %bb.0:
-; CHECK-SSE41-NEXT:    pshufd {{.*#+}} xmm1 = xmm0[1,1,3,3]
-; CHECK-SSE41-NEXT:    movdqa {{.*#+}} xmm2 = [3435973837,3435973837,3435973837,3435973837]
-; CHECK-SSE41-NEXT:    pmuludq %xmm2, %xmm1
-; CHECK-SSE41-NEXT:    pmuludq %xmm0, %xmm2
-; CHECK-SSE41-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[1,1,3,3]
-; CHECK-SSE41-NEXT:    pblendw {{.*#+}} xmm2 = xmm2[0,1],xmm1[2,3],xmm2[4,5],xmm1[6,7]
-; CHECK-SSE41-NEXT:    psrld $2, %xmm2
-; CHECK-SSE41-NEXT:    pmulld {{.*}}(%rip), %xmm2
-; CHECK-SSE41-NEXT:    psubd %xmm2, %xmm0
-; CHECK-SSE41-NEXT:    pxor %xmm1, %xmm1
+; CHECK-SSE41-NEXT:    pmulld {{.*}}(%rip), %xmm0
+; CHECK-SSE41-NEXT:    movdqa {{.*#+}} xmm1 = [858993459,858993459,858993459,858993459]
+; CHECK-SSE41-NEXT:    pminud %xmm0, %xmm1
 ; CHECK-SSE41-NEXT:    pcmpeqd %xmm1, %xmm0
 ; CHECK-SSE41-NEXT:    psrld $31, %xmm0
 ; CHECK-SSE41-NEXT:    retq
 ;
 ; CHECK-AVX1-LABEL: test_urem_odd_vec_i32:
 ; CHECK-AVX1:       # %bb.0:
-; CHECK-AVX1-NEXT:    vpshufd {{.*#+}} xmm1 = xmm0[1,1,3,3]
-; CHECK-AVX1-NEXT:    vmovdqa {{.*#+}} xmm2 = [3435973837,3435973837,3435973837,3435973837]
-; CHECK-AVX1-NEXT:    vpmuludq %xmm2, %xmm1, %xmm1
-; CHECK-AVX1-NEXT:    vpmuludq %xmm2, %xmm0, %xmm2
-; CHECK-AVX1-NEXT:    vpshufd {{.*#+}} xmm2 = xmm2[1,1,3,3]
-; CHECK-AVX1-NEXT:    vpblendw {{.*#+}} xmm1 = xmm2[0,1],xmm1[2,3],xmm2[4,5],xmm1[6,7]
-; CHECK-AVX1-NEXT:    vpsrld $2, %xmm1, %xmm1
-; CHECK-AVX1-NEXT:    vpmulld {{.*}}(%rip), %xmm1, %xmm1
-; CHECK-AVX1-NEXT:    vpsubd %xmm1, %xmm0, %xmm0
-; CHECK-AVX1-NEXT:    vpxor %xmm1, %xmm1, %xmm1
+; CHECK-AVX1-NEXT:    vpmulld {{.*}}(%rip), %xmm0, %xmm0
+; CHECK-AVX1-NEXT:    vpminud {{.*}}(%rip), %xmm0, %xmm1
 ; CHECK-AVX1-NEXT:    vpcmpeqd %xmm1, %xmm0, %xmm0
 ; CHECK-AVX1-NEXT:    vpsrld $31, %xmm0, %xmm0
 ; CHECK-AVX1-NEXT:    retq
 ;
 ; CHECK-AVX2-LABEL: test_urem_odd_vec_i32:
 ; CHECK-AVX2:       # %bb.0:
-; CHECK-AVX2-NEXT:    vpshufd {{.*#+}} xmm1 = xmm0[1,1,3,3]
-; CHECK-AVX2-NEXT:    vpbroadcastd {{.*#+}} xmm2 = [3435973837,3435973837,3435973837,3435973837]
-; CHECK-AVX2-NEXT:    vpmuludq %xmm2, %xmm1, %xmm1
-; CHECK-AVX2-NEXT:    vpmuludq %xmm2, %xmm0, %xmm2
-; CHECK-AVX2-NEXT:    vpshufd {{.*#+}} xmm2 = xmm2[1,1,3,3]
-; CHECK-AVX2-NEXT:    vpblendd {{.*#+}} xmm1 = xmm2[0],xmm1[1],xmm2[2],xmm1[3]
-; CHECK-AVX2-NEXT:    vpsrld $2, %xmm1, %xmm1
-; CHECK-AVX2-NEXT:    vpbroadcastd {{.*#+}} xmm2 = [5,5,5,5]
-; CHECK-AVX2-NEXT:    vpmulld %xmm2, %xmm1, %xmm1
-; CHECK-AVX2-NEXT:    vpsubd %xmm1, %xmm0, %xmm0
-; CHECK-AVX2-NEXT:    vpxor %xmm1, %xmm1, %xmm1
+; CHECK-AVX2-NEXT:    vpbroadcastd {{.*#+}} xmm1 = [3435973837,3435973837,3435973837,3435973837]
+; CHECK-AVX2-NEXT:    vpmulld %xmm1, %xmm0, %xmm0
+; CHECK-AVX2-NEXT:    vpbroadcastd {{.*#+}} xmm1 = [858993459,858993459,858993459,858993459]
+; CHECK-AVX2-NEXT:    vpminud %xmm1, %xmm0, %xmm1
 ; CHECK-AVX2-NEXT:    vpcmpeqd %xmm1, %xmm0, %xmm0
 ; CHECK-AVX2-NEXT:    vpsrld $31, %xmm0, %xmm0
 ; CHECK-AVX2-NEXT:    retq
 ;
 ; CHECK-AVX512VL-LABEL: test_urem_odd_vec_i32:
 ; CHECK-AVX512VL:       # %bb.0:
-; CHECK-AVX512VL-NEXT:    vpshufd {{.*#+}} xmm1 = xmm0[1,1,3,3]
-; CHECK-AVX512VL-NEXT:    vpbroadcastd {{.*#+}} xmm2 = [3435973837,3435973837,3435973837,3435973837]
-; CHECK-AVX512VL-NEXT:    vpmuludq %xmm2, %xmm1, %xmm1
-; CHECK-AVX512VL-NEXT:    vpmuludq %xmm2, %xmm0, %xmm2
-; CHECK-AVX512VL-NEXT:    vpshufd {{.*#+}} xmm2 = xmm2[1,1,3,3]
-; CHECK-AVX512VL-NEXT:    vpblendd {{.*#+}} xmm1 = xmm2[0],xmm1[1],xmm2[2],xmm1[3]
-; CHECK-AVX512VL-NEXT:    vpsrld $2, %xmm1, %xmm1
-; CHECK-AVX512VL-NEXT:    vpmulld {{.*}}(%rip){1to4}, %xmm1, %xmm1
-; CHECK-AVX512VL-NEXT:    vpsubd %xmm1, %xmm0, %xmm0
-; CHECK-AVX512VL-NEXT:    vpxor %xmm1, %xmm1, %xmm1
+; CHECK-AVX512VL-NEXT:    vpmulld {{.*}}(%rip){1to4}, %xmm0, %xmm0
+; CHECK-AVX512VL-NEXT:    vpminud {{.*}}(%rip){1to4}, %xmm0, %xmm1
 ; CHECK-AVX512VL-NEXT:    vpcmpeqd %xmm1, %xmm0, %xmm0
 ; CHECK-AVX512VL-NEXT:    vpsrld $31, %xmm0, %xmm0
 ; CHECK-AVX512VL-NEXT:    retq
   %urem = urem <4 x i32> %X, <i32 5, i32 5, i32 5, i32 5>
   %cmp = icmp eq <4 x i32> %urem, <i32 0, i32 0, i32 0, i32 0>
   %ret = zext <4 x i1> %cmp to <4 x i32>
   ret <4 x i32> %ret
 }
 
 ; Like test_urem_odd_vec_i32, but with 8 x i16 vectors.
 define <8 x i16> @test_urem_odd_vec_i16(<8 x i16> %X) nounwind readnone {
-; CHECK-SSE-LABEL: test_urem_odd_vec_i16:
-; CHECK-SSE:       # %bb.0:
-; CHECK-SSE-NEXT:    movdqa {{.*#+}} xmm1 = [52429,52429,52429,52429,52429,52429,52429,52429]
-; CHECK-SSE-NEXT:    pmulhuw %xmm0, %xmm1
-; CHECK-SSE-NEXT:    psrlw $2, %xmm1
-; CHECK-SSE-NEXT:    pmullw {{.*}}(%rip), %xmm1
-; CHECK-SSE-NEXT:    psubw %xmm1, %xmm0
-; CHECK-SSE-NEXT:    pxor %xmm1, %xmm1
-; CHECK-SSE-NEXT:    pcmpeqw %xmm1, %xmm0
-; CHECK-SSE-NEXT:    psrlw $15, %xmm0
-; CHECK-SSE-NEXT:    retq
+; CHECK-SSE2-LABEL: test_urem_odd_vec_i16:
+; CHECK-SSE2:       # %bb.0:
+; CHECK-SSE2-NEXT:    pmullw {{.*}}(%rip), %xmm0
+; CHECK-SSE2-NEXT:    psubusw {{.*}}(%rip), %xmm0
+; CHECK-SSE2-NEXT:    pxor %xmm1, %xmm1
+; CHECK-SSE2-NEXT:    pcmpeqw %xmm1, %xmm0
+; CHECK-SSE2-NEXT:    psrlw $15, %xmm0
+; CHECK-SSE2-NEXT:    retq
+;
+; CHECK-SSE41-LABEL: test_urem_odd_vec_i16:
+; CHECK-SSE41:       # %bb.0:
+; CHECK-SSE41-NEXT:    pmullw {{.*}}(%rip), %xmm0
+; CHECK-SSE41-NEXT:    movdqa {{.*#+}} xmm1 = [13107,13107,13107,13107,13107,13107,13107,13107]
+; CHECK-SSE41-NEXT:    pminuw %xmm0, %xmm1
+; CHECK-SSE41-NEXT:    pcmpeqw %xmm1, %xmm0
+; CHECK-SSE41-NEXT:    psrlw $15, %xmm0
+; CHECK-SSE41-NEXT:    retq
 ;
 ; CHECK-AVX-LABEL: test_urem_odd_vec_i16:
 ; CHECK-AVX:       # %bb.0:
-; CHECK-AVX-NEXT:    vpmulhuw {{.*}}(%rip), %xmm0, %xmm1
-; CHECK-AVX-NEXT:    vpsrlw $2, %xmm1, %xmm1
-; CHECK-AVX-NEXT:    vpmullw {{.*}}(%rip), %xmm1, %xmm1
-; CHECK-AVX-NEXT:    vpsubw %xmm1, %xmm0, %xmm0
-; CHECK-AVX-NEXT:    vpxor %xmm1, %xmm1, %xmm1
+; CHECK-AVX-NEXT:    vpmullw {{.*}}(%rip), %xmm0, %xmm0
+; CHECK-AVX-NEXT:    vpminuw {{.*}}(%rip), %xmm0, %xmm1
 ; CHECK-AVX-NEXT:    vpcmpeqw %xmm1, %xmm0, %xmm0
 ; CHECK-AVX-NEXT:    vpsrlw $15, %xmm0, %xmm0
 ; CHECK-AVX-NEXT:    retq
   %urem = urem <8 x i16> %X, <i16 5, i16 5, i16 5, i16 5,
                               i16 5, i16 5, i16 5, i16 5>
   %cmp = icmp eq <8 x i16> %urem, <i16 0, i16 0, i16 0, i16 0,
                                    i16 0, i16 0, i16 0, i16 0>
   %ret = zext <8 x i1> %cmp to <8 x i16>

 ; CHECK-AVX2-NEXT:    vpsubd %xmm1, %xmm0, %xmm0
 ; CHECK-AVX2-NEXT:    vpxor %xmm1, %xmm1, %xmm1
 ; CHECK-AVX2-NEXT:    vpcmpeqd %xmm1, %xmm0, %xmm0
 ; CHECK-AVX2-NEXT:    vpsrld $31, %xmm0, %xmm0
 ; CHECK-AVX2-NEXT:    retq
 ;
 ; CHECK-AVX512VL-LABEL: test_urem_even_vec_i32:
 ; CHECK-AVX512VL:       # %bb.0:
-; CHECK-AVX512VL-NEXT:    vpsrld $1, %xmm0, %xmm1
-; CHECK-AVX512VL-NEXT:    vpshufd {{.*#+}} xmm2 = xmm1[1,1,3,3]
-; CHECK-AVX512VL-NEXT:    vpbroadcastd {{.*#+}} xmm3 = [2454267027,2454267027,2454267027,2454267027]
-; CHECK-AVX512VL-NEXT:    vpmuludq %xmm3, %xmm2, %xmm2
-; CHECK-AVX512VL-NEXT:    vpmuludq %xmm3, %xmm1, %xmm1
-; CHECK-AVX512VL-NEXT:    vpshufd {{.*#+}} xmm1 = xmm1[1,1,3,3]
-; CHECK-AVX512VL-NEXT:    vpblendd {{.*#+}} xmm1 = xmm1[0],xmm2[1],xmm1[2],xmm2[3]
-; CHECK-AVX512VL-NEXT:    vpsrld $2, %xmm1, %xmm1
-; CHECK-AVX512VL-NEXT:    vpmulld {{.*}}(%rip){1to4}, %xmm1, %xmm1
-; CHECK-AVX512VL-NEXT:    vpsubd %xmm1, %xmm0, %xmm0
-; CHECK-AVX512VL-NEXT:    vpxor %xmm1, %xmm1, %xmm1
+; CHECK-AVX512VL-NEXT:    vpmulld {{.*}}(%rip){1to4}, %xmm0, %xmm0
+; CHECK-AVX512VL-NEXT:    vprord $1, %xmm0, %xmm0
+; CHECK-AVX512VL-NEXT:    vpminud {{.*}}(%rip){1to4}, %xmm0, %xmm1
 ; CHECK-AVX512VL-NEXT:    vpcmpeqd %xmm1, %xmm0, %xmm0
 ; CHECK-AVX512VL-NEXT:    vpsrld $31, %xmm0, %xmm0
 ; CHECK-AVX512VL-NEXT:    retq
   %urem = urem <4 x i32> %X, <i32 14, i32 14, i32 14, i32 14>
   %cmp = icmp eq <4 x i32> %urem, <i32 0, i32 0, i32 0, i32 0>
   %ret = zext <4 x i1> %cmp to <4 x i32>
   ret <4 x i32> %ret
 }

test/CodeGen/X86/urem-seteq.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=i686-unknown-linux-gnu < %s | FileCheck %s --check-prefixes=CHECK,X86
 ; RUN: llc -mtriple=x86_64-unknown-linux-gnu < %s | FileCheck %s --check-prefixes=CHECK,X64
 
 ; This tests the BuildREMEqFold optimization with UREM, i32, odd divisor, SETEQ.
 ; The corresponding pseudocode is:
 ; Q <- [N * multInv(5, 2^32)] <=> [N * 0xCCCCCCCD] <=> [N * (-858993459)]
 ; res <- [Q <= (2^32 - 1) / 5] <=> [Q <= 858993459] <=> [Q < 858993460]
 define i32 @test_urem_odd(i32 %X) nounwind readnone {
 ; X86-LABEL: test_urem_odd:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl $-858993459, %edx # imm = 0xCCCCCCCD
-; X86-NEXT:    movl %ecx, %eax
-; X86-NEXT:    mull %edx
-; X86-NEXT:    shrl $2, %edx
-; X86-NEXT:    leal (%edx,%edx,4), %edx
+; X86-NEXT:    imull $-858993459, {{[0-9]+}}(%esp), %ecx # imm = 0xCCCCCCCD
 ; X86-NEXT:    xorl %eax, %eax
-; X86-NEXT:    cmpl %edx, %ecx
-; X86-NEXT:    sete %al
+; X86-NEXT:    cmpl $858993460, %ecx # imm = 0x33333334
+; X86-NEXT:    setb %al
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_urem_odd:
 ; X64:       # %bb.0:
-; X64-NEXT:    movl %edi, %eax
-; X64-NEXT:    movl $3435973837, %ecx # imm = 0xCCCCCCCD
-; X64-NEXT:    imulq %rax, %rcx
-; X64-NEXT:    shrq $34, %rcx
-; X64-NEXT:    leal (%rcx,%rcx,4), %ecx
+; X64-NEXT:    imull $-858993459, %edi, %ecx # imm = 0xCCCCCCCD
 ; X64-NEXT:    xorl %eax, %eax
-; X64-NEXT:    cmpl %ecx, %edi
-; X64-NEXT:    sete %al
+; X64-NEXT:    cmpl $858993460, %ecx # imm = 0x33333334
+; X64-NEXT:    setb %al
 ; X64-NEXT:    retq
   %urem = urem i32 %X, 5
   %cmp = icmp eq i32 %urem, 0
   %ret = zext i1 %cmp to i32
   ret i32 %ret
 }
 
 ; This is like test_urem_odd, except the divisor has bit 30 set.
 define i32 @test_urem_odd_bit30(i32 %X) nounwind readnone {
 ; X86-LABEL: test_urem_odd_bit30:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl $-11, %edx
-; X86-NEXT:    movl %ecx, %eax
-; X86-NEXT:    mull %edx
-; X86-NEXT:    shrl $30, %edx
-; X86-NEXT:    imull $1073741827, %edx, %edx # imm = 0x40000003
+; X86-NEXT:    imull $1789569707, {{[0-9]+}}(%esp), %ecx # imm = 0x6AAAAAAB
 ; X86-NEXT:    xorl %eax, %eax
-; X86-NEXT:    cmpl %edx, %ecx
-; X86-NEXT:    sete %al
+; X86-NEXT:    cmpl $4, %ecx
+; X86-NEXT:    setb %al
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_urem_odd_bit30:
 ; X64:       # %bb.0:
-; X64-NEXT:    movl %edi, %eax
-; X64-NEXT:    movl $4294967285, %ecx # imm = 0xFFFFFFF5
-; X64-NEXT:    imulq %rax, %rcx
-; X64-NEXT:    shrq $62, %rcx
-; X64-NEXT:    imull $1073741827, %ecx, %ecx # imm = 0x40000003
+; X64-NEXT:    imull $1789569707, %edi, %ecx # imm = 0x6AAAAAAB
 ; X64-NEXT:    xorl %eax, %eax
-; X64-NEXT:    cmpl %ecx, %edi
-; X64-NEXT:    sete %al
+; X64-NEXT:    cmpl $4, %ecx
+; X64-NEXT:    setb %al
 ; X64-NEXT:    retq
   %urem = urem i32 %X, 1073741827
   %cmp = icmp eq i32 %urem, 0
   %ret = zext i1 %cmp to i32
   ret i32 %ret
 }
 
 ; This is like test_urem_odd, except the divisor has bit 31 set.
 define i32 @test_urem_odd_bit31(i32 %X) nounwind readnone {
 ; X86-LABEL: test_urem_odd_bit31:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl $1073741823, %edx # imm = 0x3FFFFFFF
-; X86-NEXT:    movl %ecx, %eax
-; X86-NEXT:    mull %edx
-; X86-NEXT:    shrl $29, %edx
-; X86-NEXT:    imull $-2147483645, %edx, %edx # imm = 0x80000003
+; X86-NEXT:    imull $715827883, {{[0-9]+}}(%esp), %ecx # imm = 0x2AAAAAAB
 ; X86-NEXT:    xorl %eax, %eax
-; X86-NEXT:    cmpl %edx, %ecx
-; X86-NEXT:    sete %al
+; X86-NEXT:    cmpl $2, %ecx
+; X86-NEXT:    setb %al
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_urem_odd_bit31:
 ; X64:       # %bb.0:
-; X64-NEXT:    movl %edi, %eax
-; X64-NEXT:    movq %rax, %rcx
-; X64-NEXT:    shlq $30, %rcx
-; X64-NEXT:    subq %rax, %rcx
-; X64-NEXT:    shrq $61, %rcx
-; X64-NEXT:    imull $-2147483645, %ecx, %ecx # imm = 0x80000003
+; X64-NEXT:    imull $715827883, %edi, %ecx # imm = 0x2AAAAAAB
 ; X64-NEXT:    xorl %eax, %eax
-; X64-NEXT:    cmpl %ecx, %edi
-; X64-NEXT:    sete %al
+; X64-NEXT:    cmpl $2, %ecx
+; X64-NEXT:    setb %al
 ; X64-NEXT:    retq
   %urem = urem i32 %X, 2147483651
   %cmp = icmp eq i32 %urem, 0
   %ret = zext i1 %cmp to i32
   ret i32 %ret
 }
 
 ; This tests the BuildREMEqFold optimization with UREM, i16, even divisor, SETNE.
 ; In this case, D <=> 14 <=> 7 * 2^1, so D0 = 7 and K = 1.
 ; The corresponding pseudocode is:
 ; Q <- [N * multInv(D0, 2^16)] <=> [N * multInv(7, 2^16)] <=> [N * 28087]
 ; Q <- [Q >>rot K] <=> [Q >>rot 1]
 ; res <- ![Q <= (2^16 - 1) / 7] <=> ![Q <= 9362] <=> [Q > 9362]
 define i16 @test_urem_even(i16 %X) nounwind readnone {
 ; X86-LABEL: test_urem_even:
 ; X86:       # %bb.0:
-; X86-NEXT:    movzwl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl %ecx, %eax
-; X86-NEXT:    shrl %eax
-; X86-NEXT:    imull $18725, %eax, %eax # imm = 0x4925
-; X86-NEXT:    shrl $17, %eax
-; X86-NEXT:    movl %eax, %edx
-; X86-NEXT:    shll $4, %edx
-; X86-NEXT:    subl %eax, %edx
-; X86-NEXT:    subl %eax, %edx
+; X86-NEXT:    imull $28087, {{[0-9]+}}(%esp), %eax # imm = 0x6DB7
+; X86-NEXT:    rorw %ax
+; X86-NEXT:    movzwl %ax, %ecx
 ; X86-NEXT:    xorl %eax, %eax
-; X86-NEXT:    cmpw %dx, %cx
-; X86-NEXT:    setne %al
+; X86-NEXT:    cmpl $9362, %ecx # imm = 0x2492
+; X86-NEXT:    seta %al
 ; X86-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_urem_even:
 ; X64:       # %bb.0:
-; X64-NEXT:    movzwl %di, %ecx
-; X64-NEXT:    movl %ecx, %eax
-; X64-NEXT:    shrl %eax
-; X64-NEXT:    imull $18725, %eax, %eax # imm = 0x4925
-; X64-NEXT:    shrl $17, %eax
-; X64-NEXT:    movl %eax, %edx
-; X64-NEXT:    shll $4, %edx
-; X64-NEXT:    subl %eax, %edx
-; X64-NEXT:    subl %eax, %edx
+; X64-NEXT:    imull $28087, %edi, %eax # imm = 0x6DB7
+; X64-NEXT:    rorw %ax
+; X64-NEXT:    movzwl %ax, %ecx
 ; X64-NEXT:    xorl %eax, %eax
-; X64-NEXT:    cmpw %dx, %cx
-; X64-NEXT:    setne %al
+; X64-NEXT:    cmpl $9362, %ecx # imm = 0x2492
+; X64-NEXT:    seta %al
 ; X64-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X64-NEXT:    retq
   %urem = urem i16 %X, 14
   %cmp = icmp ne i16 %urem, 0
   %ret = zext i1 %cmp to i16
   ret i16 %ret
 }
 
 ; This is like test_urem_even, except the divisor has bit 30 set.
 define i32 @test_urem_even_bit30(i32 %X) nounwind readnone {
 ; X86-LABEL: test_urem_even_bit30:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl $-415, %edx # imm = 0xFE61
-; X86-NEXT:    movl %ecx, %eax
-; X86-NEXT:    mull %edx
-; X86-NEXT:    shrl $30, %edx
-; X86-NEXT:    imull $1073741928, %edx, %edx # imm = 0x40000068
+; X86-NEXT:    imull $-51622203, {{[0-9]+}}(%esp), %ecx # imm = 0xFCEC4EC5
+; X86-NEXT:    rorl $3, %ecx
 ; X86-NEXT:    xorl %eax, %eax
-; X86-NEXT:    cmpl %edx, %ecx
-; X86-NEXT:    sete %al
+; X86-NEXT:    cmpl $32, %ecx
+; X86-NEXT:    setb %al
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_urem_even_bit30:
 ; X64:       # %bb.0:
-; X64-NEXT:    movl %edi, %eax
-; X64-NEXT:    movl $4294966881, %ecx # imm = 0xFFFFFE61
-; X64-NEXT:    imulq %rax, %rcx
-; X64-NEXT:    shrq $62, %rcx
-; X64-NEXT:    imull $1073741928, %ecx, %ecx # imm = 0x40000068
+; X64-NEXT:    imull $-51622203, %edi, %ecx # imm = 0xFCEC4EC5
+; X64-NEXT:    rorl $3, %ecx
 ; X64-NEXT:    xorl %eax, %eax
-; X64-NEXT:    cmpl %ecx, %edi
-; X64-NEXT:    sete %al
+; X64-NEXT:    cmpl $32, %ecx
+; X64-NEXT:    setb %al
 ; X64-NEXT:    retq
   %urem = urem i32 %X, 1073741928
   %cmp = icmp eq i32 %urem, 0
   %ret = zext i1 %cmp to i32
   ret i32 %ret
 }
 
 ; This is like test_urem_odd, except the divisor has bit 31 set.
 define i32 @test_urem_even_bit31(i32 %X) nounwind readnone {
 ; X86-LABEL: test_urem_even_bit31:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl $2147483547, %edx # imm = 0x7FFFFF9B
-; X86-NEXT:    movl %ecx, %eax
-; X86-NEXT:    mull %edx
-; X86-NEXT:    shrl $30, %edx
-; X86-NEXT:    imull $-2147483546, %edx, %edx # imm = 0x80000066
+; X86-NEXT:    imull $-1157956869, {{[0-9]+}}(%esp), %ecx # imm = 0xBAFAFAFB
+; X86-NEXT:    rorl %ecx
 ; X86-NEXT:    xorl %eax, %eax
-; X86-NEXT:    cmpl %edx, %ecx
-; X86-NEXT:    sete %al
+; X86-NEXT:    cmpl $4, %ecx
+; X86-NEXT:    setb %al
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: test_urem_even_bit31:
 ; X64:       # %bb.0:
-; X64-NEXT:    movl %edi, %eax
-; X64-NEXT:    imulq $2147483547, %rax, %rax # imm = 0x7FFFFF9B
-; X64-NEXT:    shrq $62, %rax
-; X64-NEXT:    imull $-2147483546, %eax, %ecx # imm = 0x80000066
+; X64-NEXT:    imull $-1157956869, %edi, %ecx # imm = 0xBAFAFAFB
+; X64-NEXT:    rorl %ecx
 ; X64-NEXT:    xorl %eax, %eax
-; X64-NEXT:    cmpl %ecx, %edi
-; X64-NEXT:    sete %al
+; X64-NEXT:    cmpl $4, %ecx
+; X64-NEXT:    setb %al
 ; X64-NEXT:    retq
   %urem = urem i32 %X, 2147483750
   %cmp = icmp eq i32 %urem, 0
   %ret = zext i1 %cmp to i32
   ret i32 %ret
 }
 
 ; We should not proceed with this fold if the divisor is 1 or -1