Index: include/llvm/CodeGen/TargetLowering.h
===================================================================
--- include/llvm/CodeGen/TargetLowering.h
+++ include/llvm/CodeGen/TargetLowering.h
@@ -3702,6 +3702,9 @@
                                                SDValue N1, ISD::CondCode Cond,
                                                DAGCombinerInfo &DCI,
                                                const SDLoc &DL) 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
Index: lib/CodeGen/SelectionDAG/TargetLowering.cpp
===================================================================
--- lib/CodeGen/SelectionDAG/TargetLowering.cpp
+++ lib/CodeGen/SelectionDAG/TargetLowering.cpp
@@ -2794,6 +2794,18 @@
       return V;
   }
 
+  // Fold remainder of division by a 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.
   SDValue Temp;
   if (N0.getValueType().getScalarType() == MVT::i1 && foldBooleans) {
@@ -3763,6 +3775,88 @@
   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 {
+  // 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 (!isTypeLegal(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);
+  const 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();
+
+  // TODO: make this more flexible (e.g. TargetLowering::hasVectorROTR)
+  // When the divisor is even, we will emit a ROTR,
+  // which typically has no SIMD variant and has to be expanded.
+  // The fold is unprofitable when this is the case.
+  // Moreover, if expansion would result in an illegally narrow type,
+  // continuing would cause a *crash* since ROTR nodes cannot be promoted.
+  if (DivisorIsEven && REMVT.isVector())
+    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();
+  const APInt &P = D0.zext(W + 1)
+                       .multiplicativeInverse(APInt::getHighBitsSet(W + 1, 1))
+                       .trunc(W);
+
+  // Q = floor((2^W - 1) / D0)
+  const 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);
+
+  // Rotate right only if D was even
+  if (DivisorIsEven) {
+    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);
+  }
+
+  // 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))) {
Index: test/CodeGen/AArch64/urem-seteq-optsize.ll
===================================================================
--- test/CodeGen/AArch64/urem-seteq-optsize.ll
+++ test/CodeGen/AArch64/urem-seteq-optsize.ll
@@ -26,13 +26,13 @@
 ; 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
Index: test/CodeGen/AArch64/urem-seteq-vec-nonsplat.ll
===================================================================
--- /dev/null
+++ test/CodeGen/AArch64/urem-seteq-vec-nonsplat.ll
@@ -0,0 +1,240 @@
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=aarch64-unknown-linux-gnu < %s | FileCheck %s
+
+; At the moment, BuildUREMEqFold does not handle nonsplat vectors.
+
+define <4 x i32> @test_urem_odd_div_nonsplat(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_odd_div_nonsplat:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    adrp x8, .LCPI0_0
+; CHECK-NEXT:    ldr q1, [x8, :lo12:.LCPI0_0]
+; CHECK-NEXT:    adrp x8, .LCPI0_1
+; CHECK-NEXT:    ldr q2, [x8, :lo12:.LCPI0_1]
+; CHECK-NEXT:    adrp x8, .LCPI0_2
+; CHECK-NEXT:    umull2 v3.2d, v0.4s, v1.4s
+; CHECK-NEXT:    umull v1.2d, v0.2s, v1.2s
+; CHECK-NEXT:    uzp2 v1.4s, v1.4s, v3.4s
+; CHECK-NEXT:    sub v3.4s, v0.4s, v1.4s
+; CHECK-NEXT:    umull2 v4.2d, v3.4s, v2.4s
+; CHECK-NEXT:    umull v2.2d, v3.2s, v2.2s
+; CHECK-NEXT:    ldr q3, [x8, :lo12:.LCPI0_2]
+; CHECK-NEXT:    adrp x8, .LCPI0_3
+; CHECK-NEXT:    uzp2 v2.4s, v2.4s, v4.4s
+; CHECK-NEXT:    ldr q4, [x8, :lo12:.LCPI0_3]
+; CHECK-NEXT:    neg v3.4s, v3.4s
+; CHECK-NEXT:    add v1.4s, v2.4s, v1.4s
+; CHECK-NEXT:    ushl v1.4s, v1.4s, v3.4s
+; CHECK-NEXT:    mls v0.4s, v1.4s, v4.4s
+; CHECK-NEXT:    cmeq v0.4s, v0.4s, #0
+; 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 3, i32 5, i32 7, i32 9>
+  %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
+}
+
+define <4 x i32> @test_urem_even_div_nonsplat(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_even_div_nonsplat:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    adrp x8, .LCPI1_0
+; CHECK-NEXT:    ldr q1, [x8, :lo12:.LCPI1_0]
+; CHECK-NEXT:    adrp x8, .LCPI1_1
+; CHECK-NEXT:    ldr q2, [x8, :lo12:.LCPI1_1]
+; CHECK-NEXT:    adrp x8, .LCPI1_2
+; CHECK-NEXT:    ldr q3, [x8, :lo12:.LCPI1_2]
+; CHECK-NEXT:    neg v1.4s, v1.4s
+; CHECK-NEXT:    adrp x8, .LCPI1_3
+; CHECK-NEXT:    ushl v1.4s, v0.4s, v1.4s
+; CHECK-NEXT:    umull2 v4.2d, v1.4s, v2.4s
+; CHECK-NEXT:    umull v1.2d, v1.2s, v2.2s
+; CHECK-NEXT:    ldr q2, [x8, :lo12:.LCPI1_3]
+; CHECK-NEXT:    uzp2 v1.4s, v1.4s, v4.4s
+; CHECK-NEXT:    neg v3.4s, v3.4s
+; CHECK-NEXT:    ushl v1.4s, v1.4s, v3.4s
+; CHECK-NEXT:    mls v0.4s, v1.4s, v2.4s
+; CHECK-NEXT:    cmeq v0.4s, v0.4s, #0
+; 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 6, i32 10, i32 12, 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
+}
+
+define <4 x i32> @test_urem_pow2_nonsplat(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_pow2_nonsplat:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    adrp x8, .LCPI2_0
+; CHECK-NEXT:    ldr q1, [x8, :lo12:.LCPI2_0]
+; CHECK-NEXT:    adrp x8, .LCPI2_1
+; CHECK-NEXT:    ldr q2, [x8, :lo12:.LCPI2_1]
+; CHECK-NEXT:    adrp x8, .LCPI2_2
+; CHECK-NEXT:    ldr q3, [x8, :lo12:.LCPI2_2]
+; CHECK-NEXT:    umull2 v4.2d, v0.4s, v1.4s
+; CHECK-NEXT:    umull v1.2d, v0.2s, v1.2s
+; CHECK-NEXT:    uzp2 v1.4s, v1.4s, v4.4s
+; CHECK-NEXT:    neg v2.4s, v2.4s
+; CHECK-NEXT:    ushl v1.4s, v1.4s, v2.4s
+; CHECK-NEXT:    mls v0.4s, v1.4s, v3.4s
+; CHECK-NEXT:    cmeq v0.4s, v0.4s, #0
+; 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 6, i32 10, i32 12, i32 16>
+  %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
+}
+
+define <4 x i32> @test_urem_one_nonsplat(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_one_nonsplat:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    adrp x8, .LCPI3_0
+; CHECK-NEXT:    ldr q1, [x8, :lo12:.LCPI3_0]
+; CHECK-NEXT:    adrp x8, .LCPI3_1
+; CHECK-NEXT:    ldr q2, [x8, :lo12:.LCPI3_1]
+; CHECK-NEXT:    adrp x8, .LCPI3_2
+; CHECK-NEXT:    ldr q3, [x8, :lo12:.LCPI3_2]
+; CHECK-NEXT:    neg v1.4s, v1.4s
+; CHECK-NEXT:    adrp x8, .LCPI3_3
+; CHECK-NEXT:    ushl v1.4s, v0.4s, v1.4s
+; CHECK-NEXT:    umull2 v4.2d, v1.4s, v2.4s
+; CHECK-NEXT:    umull v1.2d, v1.2s, v2.2s
+; CHECK-NEXT:    ldr q2, [x8, :lo12:.LCPI3_3]
+; CHECK-NEXT:    adrp x8, .LCPI3_4
+; CHECK-NEXT:    uzp2 v1.4s, v1.4s, v4.4s
+; CHECK-NEXT:    ldr q4, [x8, :lo12:.LCPI3_4]
+; CHECK-NEXT:    neg v3.4s, v3.4s
+; CHECK-NEXT:    ushl v1.4s, v1.4s, v3.4s
+; CHECK-NEXT:    bsl v2.16b, v0.16b, v1.16b
+; CHECK-NEXT:    mls v0.4s, v2.4s, v4.4s
+; CHECK-NEXT:    cmeq v0.4s, v0.4s, #0
+; 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 6, i32 1, i32 12, 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
+}
+
+define <4 x i32> @test_urem_comp_nonsplat(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_comp_nonsplat:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    mov w8, #52429
+; CHECK-NEXT:    movk w8, #52428, lsl #16
+; CHECK-NEXT:    adrp x9, .LCPI4_0
+; CHECK-NEXT:    dup v2.4s, w8
+; CHECK-NEXT:    ldr q3, [x9, :lo12:.LCPI4_0]
+; CHECK-NEXT:    umull2 v4.2d, v0.4s, v2.4s
+; CHECK-NEXT:    umull v2.2d, v0.2s, v2.2s
+; CHECK-NEXT:    uzp2 v2.4s, v2.4s, v4.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, v3.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 1, i32 0>
+  %ret = zext <4 x i1> %cmp to <4 x i32>
+  ret <4 x i32> %ret
+}
+
+define <4 x i32> @test_urem_both_nonsplat(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_both_nonsplat:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    adrp x8, .LCPI5_0
+; CHECK-NEXT:    ldr q1, [x8, :lo12:.LCPI5_0]
+; CHECK-NEXT:    adrp x8, .LCPI5_1
+; CHECK-NEXT:    ldr q2, [x8, :lo12:.LCPI5_1]
+; CHECK-NEXT:    adrp x8, .LCPI5_2
+; CHECK-NEXT:    ldr q3, [x8, :lo12:.LCPI5_2]
+; CHECK-NEXT:    umull2 v4.2d, v0.4s, v1.4s
+; CHECK-NEXT:    umull v1.2d, v0.2s, v1.2s
+; CHECK-NEXT:    uzp2 v1.4s, v1.4s, v4.4s
+; CHECK-NEXT:    ushr v1.4s, v1.4s, #2
+; CHECK-NEXT:    mls v0.4s, v1.4s, v2.4s
+; CHECK-NEXT:    cmeq v0.4s, v0.4s, v3.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 6, i32 5, i32 6, i32 5>
+  %cmp = icmp eq <4 x i32> %urem, <i32 1, i32 0, i32 1, i32 0>
+  %ret = zext <4 x i1> %cmp to <4 x i32>
+  ret <4 x i32> %ret
+}
+
+define <4 x i32> @test_urem_div_undef(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_div_undef:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    cmeq v0.4s, v0.4s, #0
+; 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 undef, 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
+}
+
+define <4 x i32> @test_urem_comp_undef(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_comp_undef:
+; 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.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 undef, i32 0, i32 0>
+  %ret = zext <4 x i1> %cmp to <4 x i32>
+  ret <4 x i32> %ret
+}
+
+define <4 x i32> @test_urem_both_undef(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_both_undef:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    cmeq v0.4s, v0.4s, #0
+; 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 undef, i32 5>
+  %cmp = icmp eq <4 x i32> %urem, <i32 0, i32 undef, i32 0, i32 0>
+  %ret = zext <4 x i1> %cmp to <4 x i32>
+  ret <4 x i32> %ret
+}
+
+define <4 x i32> @test_urem_div_even_odd(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_div_even_odd:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    adrp x8, .LCPI9_0
+; CHECK-NEXT:    ldr q1, [x8, :lo12:.LCPI9_0]
+; CHECK-NEXT:    adrp x8, .LCPI9_1
+; CHECK-NEXT:    ldr q2, [x8, :lo12:.LCPI9_1]
+; CHECK-NEXT:    umull2 v3.2d, v0.4s, v1.4s
+; CHECK-NEXT:    umull v1.2d, v0.2s, v1.2s
+; CHECK-NEXT:    uzp2 v1.4s, v1.4s, v3.4s
+; CHECK-NEXT:    ushr v1.4s, v1.4s, #2
+; CHECK-NEXT:    mls v0.4s, v1.4s, v2.4s
+; CHECK-NEXT:    cmeq v0.4s, v0.4s, #0
+; 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 6, i32 6>
+  %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
+}
Index: test/CodeGen/AArch64/urem-seteq-vec-splat.ll
===================================================================
--- /dev/null
+++ test/CodeGen/AArch64/urem-seteq-vec-splat.ll
@@ -0,0 +1,139 @@
+; 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:    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 4 x i16 vectors.
+define <4 x i16> @test_urem_odd_vec_i16(<4 x i16> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_odd_vec_i16:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    mov w8, #52429
+; CHECK-NEXT:    dup v2.4h, w8
+; CHECK-NEXT:    movi v1.8b, #51
+; CHECK-NEXT:    mul v0.4h, v0.4h, v2.4h
+; CHECK-NEXT:    cmhs v0.4h, v1.4h, v0.4h
+; CHECK-NEXT:    movi v1.4h, #1
+; CHECK-NEXT:    and v0.8b, v0.8b, v1.8b
+; CHECK-NEXT:    ret
+  %urem = urem <4 x i16> %X, <i16 5, i16 5, i16 5, i16 5>
+  %cmp = icmp eq <4 x i16> %urem, <i16 0, i16 0, i16 0, i16 0>
+  %ret = zext <4 x i1> %cmp to <4 x i16>
+  ret <4 x i16> %ret
+}
+
+; Tests BuildUREMEqFold for 4 x i32 splat vectors with even divisor.
+; The expected behavior is that the fold is _not_ applied
+; because it requires a ROTR in the even case, which has to be expanded.
+define <4 x i32> @test_urem_even_vec_i32(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_even_vec_i32:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    mov w8, #9363
+; CHECK-NEXT:    movk w8, #37449, lsl #16
+; CHECK-NEXT:    ushr v1.4s, v0.4s, #1
+; CHECK-NEXT:    dup v3.4s, w8
+; CHECK-NEXT:    umull2 v4.2d, v1.4s, v3.4s
+; CHECK-NEXT:    umull v1.2d, v1.2s, v3.2s
+; CHECK-NEXT:    uzp2 v1.4s, v1.4s, v4.4s
+; CHECK-NEXT:    movi v2.4s, #14
+; CHECK-NEXT:    ushr v1.4s, v1.4s, #2
+; CHECK-NEXT:    mls v0.4s, v1.4s, v2.4s
+; CHECK-NEXT:    cmeq v0.4s, v0.4s, #0
+; 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 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
+}
+
+; Like test_urem_even_vec_i32, but with 4 x i16 vectors.
+; i16 is not legal for ROTR on AArch64, but ROTR also cannot be promoted to i32,
+; so this would crash if BuildUREMEqFold was applied.
+define <4 x i16> @test_urem_even_vec_i16(<4 x i16> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_even_vec_i16:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    // kill: def $d0 killed $d0 def $q0
+; CHECK-NEXT:    umov w8, v0.h[1]
+; CHECK-NEXT:    mov w9, #9363
+; CHECK-NEXT:    movk w9, #37449, lsl #16
+; CHECK-NEXT:    umov w10, v0.h[0]
+; CHECK-NEXT:    umov w11, v0.h[2]
+; CHECK-NEXT:    umov w12, v0.h[3]
+; CHECK-NEXT:    ubfx w13, w8, #1, #15
+; CHECK-NEXT:    ubfx w14, w10, #1, #15
+; CHECK-NEXT:    ubfx w15, w11, #1, #15
+; CHECK-NEXT:    ubfx w16, w12, #1, #15
+; CHECK-NEXT:    umull x13, w13, w9
+; CHECK-NEXT:    umull x14, w14, w9
+; CHECK-NEXT:    umull x15, w15, w9
+; CHECK-NEXT:    umull x9, w16, w9
+; CHECK-NEXT:    orr w16, wzr, #0xe
+; CHECK-NEXT:    lsr x13, x13, #34
+; CHECK-NEXT:    msub w8, w13, w16, w8
+; CHECK-NEXT:    lsr x13, x14, #34
+; CHECK-NEXT:    msub w10, w13, w16, w10
+; CHECK-NEXT:    lsr x13, x15, #34
+; CHECK-NEXT:    fmov s0, w10
+; CHECK-NEXT:    msub w11, w13, w16, w11
+; CHECK-NEXT:    lsr x9, x9, #34
+; CHECK-NEXT:    mov v0.h[1], w8
+; CHECK-NEXT:    msub w9, w9, w16, w12
+; CHECK-NEXT:    mov v0.h[2], w11
+; CHECK-NEXT:    mov v0.h[3], w9
+; CHECK-NEXT:    cmeq v0.4h, v0.4h, #0
+; CHECK-NEXT:    movi v1.4h, #1
+; CHECK-NEXT:    and v0.8b, v0.8b, v1.8b
+; CHECK-NEXT:    ret
+  %urem = urem <4 x i16> %X, <i16 14, i16 14, i16 14, i16 14>
+  %cmp = icmp eq <4 x i16> %urem, <i16 0, i16 0, i16 0, i16 0>
+  %ret = zext <4 x i1> %cmp to <4 x i16>
+  ret <4 x i16> %ret
+}
+
+; We should not proceed with this fold if the divisor is 1 or -1
+define <4 x i32> @test_urem_one_vec(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_one_vec:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    movi v0.4s, #1
+; CHECK-NEXT:    ret
+  %urem = urem <4 x i32> %X, <i32 1, i32 1, i32 1, i32 1>
+  %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
+}
+
+; BuildUREMEqFold does not work when the only odd factor of the divisor is 1.
+; This ensures we don't touch powers of two.
+define <4 x i32> @test_urem_pow2_vec(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_pow2_vec:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    movi v1.4s, #15
+; CHECK-NEXT:    and v0.16b, v0.16b, v1.16b
+; CHECK-NEXT:    cmeq v0.4s, v0.4s, #0
+; 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 16, i32 16, i32 16, i32 16>
+  %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
+}
Index: test/CodeGen/AArch64/urem-seteq.ll
===================================================================
--- test/CodeGen/AArch64/urem-seteq.ll
+++ test/CodeGen/AArch64/urem-seteq.ll
@@ -10,11 +10,11 @@
 ; 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
@@ -26,14 +26,11 @@
 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
@@ -45,14 +42,11 @@
 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
@@ -69,16 +63,15 @@
 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:    orr w10, wzr, #0xe
-; 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
@@ -90,14 +83,12 @@
 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
@@ -109,15 +100,12 @@
 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
Index: test/CodeGen/X86/jump_sign.ll
===================================================================
--- test/CodeGen/X86/jump_sign.ll
+++ test/CodeGen/X86/jump_sign.ll
@@ -236,13 +236,11 @@
 ; 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 $1, %ax
 ; CHECK-NEXT:    movzwl %ax, %eax
-; CHECK-NEXT:    imull $52429, %eax, %ecx # imm = 0xCCCD
-; CHECK-NEXT:    shrl $19, %ecx
-; CHECK-NEXT:    addl %ecx, %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
@@ -398,15 +396,20 @@
 define i32 @func_test1(i32 %p1) nounwind uwtable {
 ; CHECK-LABEL: func_test1:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    movl b, %eax
-; CHECK-NEXT:    cmpl {{[0-9]+}}(%esp), %eax
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    movl a, %eax
-; CHECK-NEXT:    testb %al, %cl
-; CHECK-NEXT:    je .LBB18_2
+; CHECK-NEXT:    movl b, %ecx
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    cmpl {{[0-9]+}}(%esp), %ecx
+; CHECK-NEXT:    setb %al
+; CHECK-NEXT:    movl a, %ecx
+; CHECK-NEXT:    andl %ecx, %eax
+; CHECK-NEXT:    movb $-85, %dl
+; CHECK-NEXT:    # kill: def $al killed $al killed $eax
+; CHECK-NEXT:    mulb %dl
+; CHECK-NEXT:    cmpb $86, %al
+; CHECK-NEXT:    jb .LBB18_2
 ; CHECK-NEXT:  # %bb.1: # %if.then
-; CHECK-NEXT:    decl %eax
-; CHECK-NEXT:    movl %eax, a
+; CHECK-NEXT:    decl %ecx
+; CHECK-NEXT:    movl %ecx, a
 ; CHECK-NEXT:  .LBB18_2: # %if.end
 ; CHECK-NEXT:    retl
 entry:
Index: test/CodeGen/X86/urem-seteq-optsize.ll
===================================================================
--- test/CodeGen/X86/urem-seteq-optsize.ll
+++ test/CodeGen/X86/urem-seteq-optsize.ll
@@ -48,15 +48,10 @@
 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:
@@ -64,15 +59,11 @@
 ;
 ; 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
Index: test/CodeGen/X86/urem-seteq-vec-nonsplat.ll
===================================================================
--- /dev/null
+++ test/CodeGen/X86/urem-seteq-vec-nonsplat.ll
@@ -0,0 +1,319 @@
+; 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-SSE2
+
+; At the moment, BuildUREMEqFold does not handle nonsplat vectors.
+
+define <4 x i32> @test_urem_odd_div_nonsplat(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_odd_div_nonsplat:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movdqa {{.*#+}} xmm1 = [2863311531,3435973837,613566757,954437177]
+; CHECK-NEXT:    movdqa %xmm0, %xmm2
+; CHECK-NEXT:    pmuludq %xmm1, %xmm2
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[1,3,2,3]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[1,1,3,3]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm0[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm3
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm3[1,3,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm2 = xmm2[0],xmm1[0],xmm2[1],xmm1[1]
+; CHECK-NEXT:    movdqa %xmm0, %xmm1
+; CHECK-NEXT:    psubd %xmm2, %xmm1
+; CHECK-NEXT:    pmuludq {{.*}}(%rip), %xmm1
+; CHECK-NEXT:    psrlq $32, %xmm1
+; CHECK-NEXT:    paddd %xmm2, %xmm1
+; CHECK-NEXT:    movdqa %xmm1, %xmm2
+; CHECK-NEXT:    psrld $1, %xmm2
+; CHECK-NEXT:    psrld $2, %xmm1
+; CHECK-NEXT:    movdqa %xmm1, %xmm3
+; CHECK-NEXT:    shufps {{.*#+}} xmm3 = xmm3[1,1],xmm2[3,3]
+; CHECK-NEXT:    movdqa {{.*#+}} xmm4 = [3,5,7,9]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm5 = xmm4[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm3, %xmm5
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm5[0,2,2,3]
+; CHECK-NEXT:    shufps {{.*#+}} xmm2 = xmm2[0,3],xmm1[1,2]
+; CHECK-NEXT:    shufps {{.*#+}} xmm2 = xmm2[0,2,3,1]
+; CHECK-NEXT:    pmuludq %xmm4, %xmm2
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm2[0,2,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm1 = xmm1[0],xmm3[0],xmm1[1],xmm3[1]
+; CHECK-NEXT:    psubd %xmm1, %xmm0
+; CHECK-NEXT:    pxor %xmm1, %xmm1
+; CHECK-NEXT:    pcmpeqd %xmm1, %xmm0
+; CHECK-NEXT:    psrld $31, %xmm0
+; CHECK-NEXT:    retq
+  %urem = urem <4 x i32> %X, <i32 3, i32 5, i32 7, i32 9>
+  %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
+}
+
+define <4 x i32> @test_urem_even_div_nonsplat(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_even_div_nonsplat:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movdqa %xmm0, %xmm1
+; CHECK-NEXT:    psrld $1, %xmm1
+; CHECK-NEXT:    movdqa %xmm0, %xmm2
+; CHECK-NEXT:    shufps {{.*#+}} xmm2 = xmm2[1,1],xmm1[3,3]
+; CHECK-NEXT:    movdqa {{.*#+}} xmm3 = [2863311531,3435973837,2863311531,2454267027]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm4 = xmm3[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm2, %xmm4
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm4[1,3,2,3]
+; CHECK-NEXT:    shufps {{.*#+}} xmm1 = xmm1[3,0],xmm0[2,0]
+; CHECK-NEXT:    movaps %xmm0, %xmm4
+; CHECK-NEXT:    shufps {{.*#+}} xmm4 = xmm4[0,1],xmm1[2,0]
+; CHECK-NEXT:    pmuludq %xmm3, %xmm4
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm4[1,3,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm1 = xmm1[0],xmm2[0],xmm1[1],xmm2[1]
+; CHECK-NEXT:    movdqa %xmm1, %xmm2
+; CHECK-NEXT:    psrld $2, %xmm2
+; CHECK-NEXT:    psrld $3, %xmm1
+; CHECK-NEXT:    movdqa %xmm1, %xmm3
+; CHECK-NEXT:    shufps {{.*#+}} xmm3 = xmm3[1,1],xmm2[3,3]
+; CHECK-NEXT:    movdqa {{.*#+}} xmm4 = [6,10,12,14]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm5 = xmm4[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm3, %xmm5
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm5[0,2,2,3]
+; CHECK-NEXT:    shufps {{.*#+}} xmm2 = xmm2[0,3],xmm1[1,2]
+; CHECK-NEXT:    shufps {{.*#+}} xmm2 = xmm2[0,2,3,1]
+; CHECK-NEXT:    pmuludq %xmm4, %xmm2
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm2[0,2,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm1 = xmm1[0],xmm3[0],xmm1[1],xmm3[1]
+; CHECK-NEXT:    psubd %xmm1, %xmm0
+; CHECK-NEXT:    pxor %xmm1, %xmm1
+; CHECK-NEXT:    pcmpeqd %xmm1, %xmm0
+; CHECK-NEXT:    psrld $31, %xmm0
+; CHECK-NEXT:    retq
+  %urem = urem <4 x i32> %X, <i32 6, i32 10, i32 12, 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
+}
+
+define <4 x i32> @test_urem_pow2_nonsplat(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_pow2_nonsplat:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movdqa {{.*#+}} xmm1 = [2863311531,3435973837,2863311531,268435456]
+; CHECK-NEXT:    movdqa %xmm0, %xmm2
+; CHECK-NEXT:    pmuludq %xmm1, %xmm2
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[1,3,2,3]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[1,1,3,3]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm0[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm3
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm3[1,3,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm2 = xmm2[0],xmm1[0],xmm2[1],xmm1[1]
+; CHECK-NEXT:    movdqa %xmm2, %xmm1
+; CHECK-NEXT:    psrld $3, %xmm1
+; CHECK-NEXT:    movdqa %xmm1, %xmm3
+; CHECK-NEXT:    punpckhqdq {{.*#+}} xmm3 = xmm3[1],xmm2[1]
+; CHECK-NEXT:    movdqa %xmm2, %xmm4
+; CHECK-NEXT:    psrld $2, %xmm4
+; CHECK-NEXT:    punpcklqdq {{.*#+}} xmm4 = xmm4[0],xmm1[0]
+; CHECK-NEXT:    shufps {{.*#+}} xmm4 = xmm4[0,3],xmm3[0,3]
+; CHECK-NEXT:    movdqa {{.*#+}} xmm3 = [6,10,12,16]
+; CHECK-NEXT:    pmuludq %xmm3, %xmm4
+; CHECK-NEXT:    pshufd {{.*#+}} xmm4 = xmm4[0,2,2,3]
+; CHECK-NEXT:    shufps {{.*#+}} xmm1 = xmm1[1,1],xmm2[3,3]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm3[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm2
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm2[0,2,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm4 = xmm4[0],xmm1[0],xmm4[1],xmm1[1]
+; CHECK-NEXT:    psubd %xmm4, %xmm0
+; CHECK-NEXT:    pxor %xmm1, %xmm1
+; CHECK-NEXT:    pcmpeqd %xmm1, %xmm0
+; CHECK-NEXT:    psrld $31, %xmm0
+; CHECK-NEXT:    retq
+  %urem = urem <4 x i32> %X, <i32 6, i32 10, i32 12, i32 16>
+  %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
+}
+
+define <4 x i32> @test_urem_one_nonsplat(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_one_nonsplat:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movdqa %xmm0, %xmm1
+; CHECK-NEXT:    psrld $1, %xmm1
+; CHECK-NEXT:    movdqa %xmm0, %xmm2
+; CHECK-NEXT:    shufps {{.*#+}} xmm2 = xmm2[1,1],xmm1[3,3]
+; CHECK-NEXT:    movdqa {{.*#+}} xmm3 = [2863311531,0,2863311531,2454267027]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm4 = xmm3[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm2, %xmm4
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm4[1,3,2,3]
+; CHECK-NEXT:    shufps {{.*#+}} xmm1 = xmm1[3,0],xmm0[2,0]
+; CHECK-NEXT:    movaps %xmm0, %xmm4
+; CHECK-NEXT:    shufps {{.*#+}} xmm4 = xmm4[0,1],xmm1[2,0]
+; CHECK-NEXT:    pmuludq %xmm3, %xmm4
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm4[1,3,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm1 = xmm1[0],xmm2[0],xmm1[1],xmm2[1]
+; CHECK-NEXT:    movdqa %xmm1, %xmm2
+; CHECK-NEXT:    psrld $2, %xmm2
+; CHECK-NEXT:    psrld $3, %xmm1
+; CHECK-NEXT:    punpckhqdq {{.*#+}} xmm1 = xmm1[1],xmm2[1]
+; CHECK-NEXT:    movaps %xmm0, %xmm3
+; CHECK-NEXT:    shufps {{.*#+}} xmm3 = xmm3[1,0],xmm2[0,0]
+; CHECK-NEXT:    shufps {{.*#+}} xmm3 = xmm3[2,0],xmm1[0,3]
+; CHECK-NEXT:    movdqa {{.*#+}} xmm1 = [6,1,12,14]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm3
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm3[0,2,2,3]
+; CHECK-NEXT:    movaps %xmm0, %xmm4
+; CHECK-NEXT:    shufps {{.*#+}} xmm4 = xmm4[1,1],xmm2[3,3]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm4, %xmm1
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[0,2,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm3 = xmm3[0],xmm1[0],xmm3[1],xmm1[1]
+; CHECK-NEXT:    psubd %xmm3, %xmm0
+; CHECK-NEXT:    pxor %xmm1, %xmm1
+; CHECK-NEXT:    pcmpeqd %xmm1, %xmm0
+; CHECK-NEXT:    psrld $31, %xmm0
+; CHECK-NEXT:    retq
+  %urem = urem <4 x i32> %X, <i32 6, i32 1, i32 12, 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
+}
+
+define <4 x i32> @test_urem_comp_nonsplat(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_comp_nonsplat:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movdqa {{.*#+}} xmm1 = [3435973837,3435973837,3435973837,3435973837]
+; CHECK-NEXT:    movdqa %xmm0, %xmm2
+; CHECK-NEXT:    pmuludq %xmm1, %xmm2
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[1,3,2,3]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm0[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm3
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm3[1,3,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm2 = xmm2[0],xmm1[0],xmm2[1],xmm1[1]
+; CHECK-NEXT:    psrld $2, %xmm2
+; CHECK-NEXT:    movdqa {{.*#+}} xmm1 = [5,5,5,5]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm2[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm2
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[0,2,2,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm3
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm3[0,2,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm2 = xmm2[0],xmm1[0],xmm2[1],xmm1[1]
+; CHECK-NEXT:    psubd %xmm2, %xmm0
+; CHECK-NEXT:    pcmpeqd {{.*}}(%rip), %xmm0
+; CHECK-NEXT:    psrld $31, %xmm0
+; CHECK-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 1, i32 0>
+  %ret = zext <4 x i1> %cmp to <4 x i32>
+  ret <4 x i32> %ret
+}
+
+define <4 x i32> @test_urem_both_nonsplat(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_both_nonsplat:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movdqa {{.*#+}} xmm1 = [2863311531,3435973837,2863311531,3435973837]
+; CHECK-NEXT:    movdqa %xmm0, %xmm2
+; CHECK-NEXT:    pmuludq %xmm1, %xmm2
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[1,3,2,3]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[1,1,3,3]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm0[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm3
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm3[1,3,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm2 = xmm2[0],xmm1[0],xmm2[1],xmm1[1]
+; CHECK-NEXT:    psrld $2, %xmm2
+; CHECK-NEXT:    movdqa {{.*#+}} xmm1 = [6,5,6,5]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm2[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm2
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[0,2,2,3]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm3, %xmm1
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[0,2,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm2 = xmm2[0],xmm1[0],xmm2[1],xmm1[1]
+; CHECK-NEXT:    psubd %xmm2, %xmm0
+; CHECK-NEXT:    pcmpeqd {{.*}}(%rip), %xmm0
+; CHECK-NEXT:    psrld $31, %xmm0
+; CHECK-NEXT:    retq
+  %urem = urem <4 x i32> %X, <i32 6, i32 5, i32 6, i32 5>
+  %cmp = icmp eq <4 x i32> %urem, <i32 1, i32 0, i32 1, i32 0>
+  %ret = zext <4 x i1> %cmp to <4 x i32>
+  ret <4 x i32> %ret
+}
+
+define <4 x i32> @test_urem_div_undef(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_div_undef:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    pxor %xmm0, %xmm0
+; CHECK-NEXT:    pcmpeqd %xmm0, %xmm0
+; CHECK-NEXT:    psrld $31, %xmm0
+; CHECK-NEXT:    retq
+  %urem = urem <4 x i32> %X, <i32 5, i32 5, i32 undef, 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
+}
+
+define <4 x i32> @test_urem_comp_undef(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_comp_undef:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movdqa {{.*#+}} xmm1 = [3435973837,3435973837,3435973837,3435973837]
+; CHECK-NEXT:    movdqa %xmm0, %xmm2
+; CHECK-NEXT:    pmuludq %xmm1, %xmm2
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[1,3,2,3]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm0[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm3
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm3[1,3,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm2 = xmm2[0],xmm1[0],xmm2[1],xmm1[1]
+; CHECK-NEXT:    psrld $2, %xmm2
+; CHECK-NEXT:    movdqa {{.*#+}} xmm1 = [5,5,5,5]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm2[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm2
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[0,2,2,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm3
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm3[0,2,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm2 = xmm2[0],xmm1[0],xmm2[1],xmm1[1]
+; CHECK-NEXT:    psubd %xmm2, %xmm0
+; CHECK-NEXT:    pxor %xmm1, %xmm1
+; CHECK-NEXT:    pcmpeqd %xmm1, %xmm0
+; CHECK-NEXT:    psrld $31, %xmm0
+; CHECK-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 undef, i32 0, i32 0>
+  %ret = zext <4 x i1> %cmp to <4 x i32>
+  ret <4 x i32> %ret
+}
+
+define <4 x i32> @test_urem_both_undef(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_both_undef:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    pxor %xmm0, %xmm0
+; CHECK-NEXT:    pcmpeqd %xmm0, %xmm0
+; CHECK-NEXT:    psrld $31, %xmm0
+; CHECK-NEXT:    retq
+  %urem = urem <4 x i32> %X, <i32 5, i32 5, i32 undef, i32 5>
+  %cmp = icmp eq <4 x i32> %urem, <i32 0, i32 undef, i32 0, i32 0>
+  %ret = zext <4 x i1> %cmp to <4 x i32>
+  ret <4 x i32> %ret
+}
+
+define <4 x i32> @test_urem_div_even_odd(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_div_even_odd:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movdqa {{.*#+}} xmm1 = [3435973837,3435973837,2863311531,2863311531]
+; CHECK-NEXT:    movdqa %xmm0, %xmm2
+; CHECK-NEXT:    pmuludq %xmm1, %xmm2
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[1,3,2,3]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[1,1,3,3]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm0[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm3
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm3[1,3,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm2 = xmm2[0],xmm1[0],xmm2[1],xmm1[1]
+; CHECK-NEXT:    psrld $2, %xmm2
+; CHECK-NEXT:    movdqa {{.*#+}} xmm1 = [5,5,6,6]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm2[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm2
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm2[0,2,2,3]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm3, %xmm1
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[0,2,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm2 = xmm2[0],xmm1[0],xmm2[1],xmm1[1]
+; CHECK-NEXT:    psubd %xmm2, %xmm0
+; CHECK-NEXT:    pxor %xmm1, %xmm1
+; CHECK-NEXT:    pcmpeqd %xmm1, %xmm0
+; CHECK-NEXT:    psrld $31, %xmm0
+; CHECK-NEXT:    retq
+  %urem = urem <4 x i32> %X, <i32 5, i32 5, i32 6, i32 6>
+  %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
+}
Index: test/CodeGen/X86/urem-seteq-vec-splat.ll
===================================================================
--- /dev/null
+++ test/CodeGen/X86/urem-seteq-vec-splat.ll
@@ -0,0 +1,141 @@
+; 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-SSE2
+
+; 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:    movdqa {{.*#+}} xmm1 = [3435973837,3435973837,3435973837,3435973837]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm0[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm0
+; CHECK-NEXT:    pshufd {{.*#+}} xmm0 = xmm0[0,2,2,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm2
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm2[0,2,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1]
+; CHECK-NEXT:    pxor {{.*}}(%rip), %xmm0
+; CHECK-NEXT:    pcmpgtd {{.*}}(%rip), %xmm0
+; CHECK-NEXT:    pandn {{.*}}(%rip), %xmm0
+; CHECK-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 4 x i16 vectors.
+define <4 x i16> @test_urem_odd_vec_i16(<4 x i16> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_odd_vec_i16:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    pand {{.*}}(%rip), %xmm0
+; CHECK-NEXT:    movdqa {{.*#+}} xmm1 = [3435973837,3435973837,3435973837,3435973837]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm0[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm0
+; CHECK-NEXT:    pshufd {{.*#+}} xmm0 = xmm0[0,2,2,3]
+; CHECK-NEXT:    pmuludq %xmm1, %xmm2
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm2[0,2,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[1],xmm1[1]
+; CHECK-NEXT:    pxor {{.*}}(%rip), %xmm0
+; CHECK-NEXT:    pcmpgtd {{.*}}(%rip), %xmm0
+; CHECK-NEXT:    pandn {{.*}}(%rip), %xmm0
+; CHECK-NEXT:    retq
+  %urem = urem <4 x i16> %X, <i16 5, i16 5, i16 5, i16 5>
+  %cmp = icmp eq <4 x i16> %urem, <i16 0, i16 0, i16 0, i16 0>
+  %ret = zext <4 x i1> %cmp to <4 x i16>
+  ret <4 x i16> %ret
+}
+
+; Tests BuildUREMEqFold for 4 x i32 splat vectors with even divisor.
+; The expected behavior is that the fold is _not_ applied
+; because it requires a ROTR in the even case, which has to be expanded.
+define <4 x i32> @test_urem_even_vec_i32(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_even_vec_i32:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movdqa %xmm0, %xmm1
+; CHECK-NEXT:    psrld $1, %xmm1
+; CHECK-NEXT:    movdqa {{.*#+}} xmm2 = [2454267027,2454267027,2454267027,2454267027]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm1[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm2, %xmm1
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[1,3,2,3]
+; CHECK-NEXT:    pmuludq %xmm2, %xmm3
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm3[1,3,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm1 = xmm1[0],xmm2[0],xmm1[1],xmm2[1]
+; CHECK-NEXT:    psrld $2, %xmm1
+; CHECK-NEXT:    movdqa {{.*#+}} xmm2 = [14,14,14,14]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm1[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm2, %xmm1
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[0,2,2,3]
+; CHECK-NEXT:    pmuludq %xmm2, %xmm3
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm3[0,2,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm1 = xmm1[0],xmm2[0],xmm1[1],xmm2[1]
+; CHECK-NEXT:    psubd %xmm1, %xmm0
+; CHECK-NEXT:    pxor %xmm1, %xmm1
+; CHECK-NEXT:    pcmpeqd %xmm1, %xmm0
+; CHECK-NEXT:    psrld $31, %xmm0
+; CHECK-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
+}
+
+; Like test_urem_even_vec_i32, but with 4 x i16 vectors.
+define <4 x i16> @test_urem_even_vec_i16(<4 x i16> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_even_vec_i16:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    pand {{.*}}(%rip), %xmm0
+; CHECK-NEXT:    movdqa %xmm0, %xmm1
+; CHECK-NEXT:    psrld $1, %xmm1
+; CHECK-NEXT:    movdqa {{.*#+}} xmm2 = [2454267027,2454267027,2454267027,2454267027]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm1[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm2, %xmm1
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[1,3,2,3]
+; CHECK-NEXT:    pmuludq %xmm2, %xmm3
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm3[1,3,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm1 = xmm1[0],xmm2[0],xmm1[1],xmm2[1]
+; CHECK-NEXT:    psrld $2, %xmm1
+; CHECK-NEXT:    movdqa {{.*#+}} xmm2 = [14,14,14,14]
+; CHECK-NEXT:    pshufd {{.*#+}} xmm3 = xmm1[1,1,3,3]
+; CHECK-NEXT:    pmuludq %xmm2, %xmm1
+; CHECK-NEXT:    pshufd {{.*#+}} xmm1 = xmm1[0,2,2,3]
+; CHECK-NEXT:    pmuludq %xmm2, %xmm3
+; CHECK-NEXT:    pshufd {{.*#+}} xmm2 = xmm3[0,2,2,3]
+; CHECK-NEXT:    punpckldq {{.*#+}} xmm1 = xmm1[0],xmm2[0],xmm1[1],xmm2[1]
+; CHECK-NEXT:    psubd %xmm1, %xmm0
+; CHECK-NEXT:    pxor %xmm1, %xmm1
+; CHECK-NEXT:    pcmpeqd %xmm1, %xmm0
+; CHECK-NEXT:    psrld $31, %xmm0
+; CHECK-NEXT:    retq
+  %urem = urem <4 x i16> %X, <i16 14, i16 14, i16 14, i16 14>
+  %cmp = icmp eq <4 x i16> %urem, <i16 0, i16 0, i16 0, i16 0>
+  %ret = zext <4 x i1> %cmp to <4 x i16>
+  ret <4 x i16> %ret
+}
+
+; We should not proceed with this fold if the divisor is 1 or -1
+define <4 x i32> @test_urem_one_vec(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_one_vec:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movaps {{.*#+}} xmm0 = [1,1,1,1]
+; CHECK-NEXT:    retq
+  %urem = urem <4 x i32> %X, <i32 1, i32 1, i32 1, i32 1>
+  %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
+}
+
+; BuildUREMEqFold does not work when the only odd factor of the divisor is 1.
+; This ensures we don't touch powers of two.
+define <4 x i32> @test_urem_pow2_vec(<4 x i32> %X) nounwind readnone {
+; CHECK-LABEL: test_urem_pow2_vec:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    pand {{.*}}(%rip), %xmm0
+; CHECK-NEXT:    pxor %xmm1, %xmm1
+; CHECK-NEXT:    pcmpeqd %xmm1, %xmm0
+; CHECK-NEXT:    psrld $31, %xmm0
+; CHECK-NEXT:    retq
+  %urem = urem <4 x i32> %X, <i32 16, i32 16, i32 16, i32 16>
+  %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
+}
Index: test/CodeGen/X86/urem-seteq.ll
===================================================================
--- test/CodeGen/X86/urem-seteq.ll
+++ test/CodeGen/X86/urem-seteq.ll
@@ -10,27 +10,18 @@
 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
@@ -42,27 +33,18 @@
 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
@@ -74,28 +56,18 @@
 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
@@ -112,35 +84,23 @@
 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 $1, %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 $1, %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
@@ -153,27 +113,20 @@
 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
@@ -185,26 +138,20 @@
 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 $1, %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 $1, %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