[TargetLowering] Add support for non-uniform vectors to BuildUDIV

[RKSimon]

Summary

This patch refactors the existing TargetLowering::BuildUDIV base implementation to support non-uniform constant vector denominators.

This does require a change to the function arguments, which would affect any target that has overridden this (none in mainline though).

[RKSimon]

Bail out if the build vector has implicit truncations.

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

18109

isKnownNeverZero() should also probably be wary of undef?

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

18109

If its a constant build vector then isKnownNeverZero() will return false if any elements contain undef.

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

18109

https://github.com/llvm-mirror/llvm/blob/51a70b932d4c89e412ceea371861e5f7fcca1776/lib/CodeGen/SelectionDAG/SelectionDAG.cpp#L3625-L3645
Ah, it is cautiously-pessimistic by default, right.

[RKSimon]

ping?

[efriedma]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3651

I'm pretty sure this isn't the most efficient way to handle this case. Would it be more efficient to use a variable-amount shift to compute NPQ, rather than shuffle afterwards? Or is it possible to fudge the magic number to avoid the blend?

Please make sure you have test coverage for both UseNPQ=true and UseNPQ=false.

test/CodeGen/X86/combine-udiv.ll

382

I guess it's sort of orthogonal to this patch, but this should probably be using pmulhuw for the shift.

[RKSimon]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3651

We do have full coverage for scalars and uniform vectors only - I'll try to add all the necessary non-uniform cases as well.

test/CodeGen/X86/combine-udiv.ll

382

I raised this on PR38151 but haven't had time to get to it.

[RKSimon]

test/CodeGen/X86/combine-udiv.ll

382

D49562 is an initial attempt at this.

[RKSimon]

Rebased - now with new tests and better SRL->MULHU codegen

[RKSimon]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3651

Tests now ensure we have vector cases with all/none/some NPQ path

[RKSimon]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3651

I'm pretty sure this isn't the most efficient way to handle this case. Would it be more efficient to use a variable amount shift to compute NPQ, rather than shuffle afterwards? Or is it possible to fudge the magic number to avoid the blend?

@efriedma I haven't found anything that works any better then the current shuffle - the additional SUB and ADD seem to get in the way - do you have a codegen example of what you have in mind?

[efriedma]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3651

By "variable amount shift", I was thinking of something like VPSUB+VPSRLVD+VPADD: if the shift amount is zero, it's a no-op.

The other thing I was thinking is that it might be possible to transform the magic number for an element so that SelNPQ is true for all the elements by shifting magics.a left? Not sure if that actually works.

[RKSimon]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3651

ADD( Q, SRL( SUB( N0, Q ), 0 ) ) --> N0

what I think you have in mind is if we can use MULHU/UMUL_LOHI, instead of SRL, so this becomes

ADD( Q, MULHU( SUB( N0, Q ), C ) ) --> Q (C == 0 for non-NPQ path)

Does that sound about right? DAGCombiner::visitMULHU might need some improvements as well.

[RKSimon]

Use an extra MULHU to support the shift-by-one and shift-by-zero NPQ/no-NPQ case.

[efriedma]

LGTM

include/llvm/CodeGen/TargetLowering.h

virtual void LowerAsmOperandForConstraint(SDValue Op, std::string &Constraint,
                                             SelectionDAG &DAG) const;
 
   //===--------------------------------------------------------------------===//
   // Div utility functions
   //
   SDValue BuildSDIV(SDNode *N, const APInt &Divisor, SelectionDAG &DAG,
                     bool IsAfterLegalization,
                     SmallVectorImpl<SDNode *> &Created) const;
-  SDValue BuildUDIV(SDNode *N, const APInt &Divisor, SelectionDAG &DAG,
-                    bool IsAfterLegalization,
+  SDValue BuildUDIV(SDNode *N, SelectionDAG &DAG, bool IsAfterLegalization,
                     SmallVectorImpl<SDNode *> &Created) const;
 
   /// Targets may override this function to provide custom SDIV lowering for
   /// power-of-2 denominators.  If the target returns an empty SDValue, LLVM
   /// assumes SDIV is expensive and replaces it with a series of other integer
   /// operations.
   virtual SDValue BuildSDIVPow2(SDNode *N, const APInt &Divisor,
                                 SelectionDAG &DAG,

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitUDIV(SDNode *N) {
 
   return SDValue();
 }
 
 SDValue DAGCombiner::visitUDIVLike(SDValue N0, SDValue N1, SDNode *N) {
   SDLoc DL(N);
   EVT VT = N->getValueType(0);
 
-  ConstantSDNode *N1C = isConstOrConstSplat(N1);
-
   // fold (udiv x, (1 << c)) -> x >>u c
   if (isConstantOrConstantVector(N1, /*NoOpaques*/ true) &&
       DAG.isKnownToBeAPowerOfTwo(N1)) {
     SDValue LogBase2 = BuildLogBase2(N1, DL);
     AddToWorklist(LogBase2.getNode());
 
     EVT ShiftVT = getShiftAmountTy(N0.getValueType());
     SDValue Trunc = DAG.getZExtOrTrunc(LogBase2, DL, ShiftVT);
if (isConstantOrConstantVector(N10, /*NoOpaques*/ true) &&
       SDValue Add = DAG.getNode(ISD::ADD, DL, ADDVT, N1.getOperand(1), Trunc);
       AddToWorklist(Add.getNode());
       return DAG.getNode(ISD::SRL, DL, VT, N0, Add);
     }
   }
 
   // fold (udiv x, c) -> alternate
   AttributeList Attr = DAG.getMachineFunction().getFunction().getAttributes();
-  if (N1C && !TLI.isIntDivCheap(N->getValueType(0), Attr))
+  if (isConstantOrConstantVector(N1, /*NoOpaques*/ true) &&
+      !TLI.isIntDivCheap(N->getValueType(0), Attr))
     if (SDValue Op = BuildUDIV(N))
       return Op;
 
   return SDValue();
 }
 
 // handles ISD::SREM and ISD::UREM
 SDValue DAGCombiner::visitREM(SDNode *N) {

 /// number.
 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide".
 SDValue DAGCombiner::BuildUDIV(SDNode *N) {
   // when optimising for minimum size, we don't want to expand a div to a mul
   // and a shift.
   if (DAG.getMachineFunction().getFunction().optForMinSize())
     return SDValue();
 
-  ConstantSDNode *C = isConstOrConstSplat(N->getOperand(1));
-  if (!C)
-    return SDValue();
-
-  // Avoid division by zero.
-  if (C->isNullValue())
+  SDValue N1 = N->getOperand(1);
+  if (!isConstantOrConstantVector(N1) || !DAG.isKnownNeverZero(N1))
     return SDValue();
 
   SmallVector<SDNode *, 8> Built;
-  SDValue S =
-      TLI.BuildUDIV(N, C->getAPIntValue(), DAG, LegalOperations, Built);
+  SDValue S = TLI.BuildUDIV(N, DAG, LegalOperations, Built);
 
   for (SDNode *N : Built)
     AddToWorklist(N);
   return S;
 }
 
 /// Determines the LogBase2 value for a non-null input value using the
 /// transform: LogBase2(V) = (EltBits - 1) - ctlz(V).

lib/CodeGen/SelectionDAG/TargetLowering.cpp

SDValue TargetLowering::BuildSDIV(SDNode *N, const APInt &Divisor,
   Created.push_back(T.getNode());
   return DAG.getNode(ISD::ADD, dl, VT, Q, T);
 }
 
 /// Given an ISD::UDIV node expressing a divide by constant,
 /// return a DAG expression to select that will generate the same value by
 /// multiplying by a magic number.
 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide".
-SDValue TargetLowering::BuildUDIV(SDNode *N, const APInt &Divisor,
-                                  SelectionDAG &DAG, bool IsAfterLegalization,
+SDValue TargetLowering::BuildUDIV(SDNode *N, SelectionDAG &DAG,
+                                  bool IsAfterLegalization,
                                   SmallVectorImpl<SDNode *> &Created) const {
-  EVT VT = N->getValueType(0);
   SDLoc dl(N);
   auto &DL = DAG.getDataLayout();
 
+  EVT VT = N->getValueType(0);
+  EVT ShVT = getShiftAmountTy(VT, DL);
+
   // Check to see if we can do this.
   // FIXME: We should be more aggressive here.
   if (!isTypeLegal(VT))
     return SDValue();
 
+  auto BuildUDIVPattern = [](const APInt &Divisor, unsigned &PreShift,
+                             APInt &Magic, unsigned &PostShift) {
     // FIXME: We should use a narrower constant when the upper
     // bits are known to be zero.
     APInt::mu magics = Divisor.magicu();
+    PreShift = PostShift = 0;
 
-  SDValue Q = N->getOperand(0);
-
-  // If the divisor is even, we can avoid using the expensive fixup by shifting
-  // the divided value upfront.
+    // If the divisor is even, we can avoid using the expensive fixup by
+    // shifting the divided value upfront.
     if (magics.a != 0 && !Divisor[0]) {
-    unsigned Shift = Divisor.countTrailingZeros();
-    Q = DAG.getNode(
-        ISD::SRL, dl, VT, Q,
-        DAG.getConstant(Shift, dl, getShiftAmountTy(Q.getValueType(), DL)));
-    Created.push_back(Q.getNode());
-
+      PreShift = Divisor.countTrailingZeros();
       // Get magic number for the shifted divisor.
-    magics = Divisor.lshr(Shift).magicu(Shift);
+      magics = Divisor.lshr(PreShift).magicu(PreShift);
       assert(magics.a == 0 && "Should use cheap fixup now");
     }
 
+    Magic = magics.m;
+
+    if (magics.a == 0) {
+      assert(magics.s < Divisor.getBitWidth() &&
+             "We shouldn't generate an undefined shift!");
+      PostShift = magics.s;
+      return false;
+    } else {
+      PostShift = magics.s - 1;
+      return true;
+    }
+  };
+
+  SDValue N0 = N->getOperand(0);
+  SDValue N1 = N->getOperand(1);
+
+  // Collect the shifts/magic values from each element.
+  bool UseNPQ = false;
+  SDValue PreShift, PostShift, MagicFactor;
+  SmallVector<int, 16> ShuffleMask;
+  if (VT.isVector()) {
+    EVT SVT = VT.getScalarType();
+    EVT ShSVT = ShVT.getScalarType();
+    unsigned EltBits = VT.getScalarSizeInBits();
+    unsigned NumElts = VT.getVectorNumElements();
+    SmallVector<SDValue, 16> PreShifts, PostShifts, MagicFactors;
+    if (ISD::BUILD_VECTOR != N1.getOpcode())
+      return SDValue();
+    for (unsigned i = 0; i != NumElts; ++i) {
+      auto *C = dyn_cast<ConstantSDNode>(N1.getOperand(i));
+      if (!C || C->isNullValue() || C->getAPIntValue().getBitWidth() != EltBits)
+        return SDValue();
+      APInt MagicVal;
+      unsigned PreShiftVal, PostShiftVal;
+      bool SelNPQ = BuildUDIVPattern(C->getAPIntValue(), PreShiftVal, MagicVal,
+                                     PostShiftVal);
+      PreShifts.push_back(DAG.getConstant(PreShiftVal, dl, ShSVT));
+      MagicFactors.push_back(DAG.getConstant(MagicVal, dl, SVT));
+      PostShifts.push_back(DAG.getConstant(PostShiftVal, dl, ShSVT));
+      ShuffleMask.push_back(SelNPQ ? i + NumElts : i);
+      UseNPQ |= SelNPQ;
+    }
+    if (!isShuffleMaskLegal(ShuffleMask, VT))
+      return SDValue();
+    PreShift = DAG.getBuildVector(ShVT, dl, PreShifts);
+    MagicFactor = DAG.getBuildVector(VT, dl, MagicFactors);
+    PostShift = DAG.getBuildVector(ShVT, dl, PostShifts);
+  } else {
+    auto *C = dyn_cast<ConstantSDNode>(N1);
+    if (!C || C->isNullValue())
+      return SDValue();
+    APInt MagicVal;
+    unsigned PreShiftVal, PostShiftVal;
+    UseNPQ = BuildUDIVPattern(C->getAPIntValue(), PreShiftVal, MagicVal,
+                              PostShiftVal);
+    PreShift = DAG.getConstant(PreShiftVal, dl, ShVT);
+    MagicFactor = DAG.getConstant(MagicVal, dl, VT);
+    PostShift = DAG.getConstant(PostShiftVal, dl, ShVT);
+  }
+
+  SDValue Q = N0;
+  Q = DAG.getNode(ISD::SRL, dl, VT, Q, PreShift);
+  Created.push_back(Q.getNode());
+
   // Multiply the numerator (operand 0) by the magic value
   // FIXME: We should support doing a MUL in a wider type
   if (IsAfterLegalization ? isOperationLegal(ISD::MULHU, VT) :
                             isOperationLegalOrCustom(ISD::MULHU, VT))
-    Q = DAG.getNode(ISD::MULHU, dl, VT, Q, DAG.getConstant(magics.m, dl, VT));
+    Q = DAG.getNode(ISD::MULHU, dl, VT, Q, MagicFactor);
   else if (IsAfterLegalization ? isOperationLegal(ISD::UMUL_LOHI, VT) :
-                                 isOperationLegalOrCustom(ISD::UMUL_LOHI, VT))
-    Q = SDValue(DAG.getNode(ISD::UMUL_LOHI, dl, DAG.getVTList(VT, VT), Q,
-                            DAG.getConstant(magics.m, dl, VT)).getNode(), 1);
-  else
+                                 isOperationLegalOrCustom(ISD::UMUL_LOHI, VT)) {
+    SDValue LoHi =
+        DAG.getNode(ISD::UMUL_LOHI, dl, DAG.getVTList(VT, VT), Q, MagicFactor);
+    Q = SDValue(LoHi.getNode(), 1);
+  } else
     return SDValue();       // No mulhu or equivalent
 
   Created.push_back(Q.getNode());
 
-  if (magics.a == 0) {
-    assert(magics.s < Divisor.getBitWidth() &&
-           "We shouldn't generate an undefined shift!");
-    return DAG.getNode(
-        ISD::SRL, dl, VT, Q,
-        DAG.getConstant(magics.s, dl, getShiftAmountTy(Q.getValueType(), DL)));
-  } else {
-    SDValue NPQ = DAG.getNode(ISD::SUB, dl, VT, N->getOperand(0), Q);
+  if (UseNPQ) {
+    SDValue NPQ = DAG.getNode(ISD::SUB, dl, VT, N0, Q);
     Created.push_back(NPQ.getNode());
     NPQ = DAG.getNode(
         ISD::SRL, dl, VT, NPQ,
         DAG.getConstant(1, dl, getShiftAmountTy(NPQ.getValueType(), DL)));
     Created.push_back(NPQ.getNode());
     NPQ = DAG.getNode(ISD::ADD, dl, VT, NPQ, Q);
     Created.push_back(NPQ.getNode());
-    return DAG.getNode(
-        ISD::SRL, dl, VT, NPQ,
-        DAG.getConstant(magics.s - 1, dl,
-                        getShiftAmountTy(NPQ.getValueType(), DL)));
+
+    if (VT.isVector()) {
+      Q = DAG.getVectorShuffle(VT, dl, Q, NPQ, ShuffleMask);
+      Created.push_back(Q.getNode());
+    } else {
+      Q = NPQ;
     }
   }
 
+  return DAG.getNode(ISD::SRL, dl, VT, Q, PostShift);
+}
+
 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/X86/combine-udiv.ll

 ; AVX-NEXT:    retq
   %1 = udiv <8 x i16> %x, <i16 23, i16 23, i16 23, i16 23, i16 23, i16 23, i16 23, i16 23>
   ret <8 x i16> %1
 }
 
 define <8 x i16> @combine_vec_udiv_nonuniform(<8 x i16> %x) {
 ; SSE-LABEL: combine_vec_udiv_nonuniform:
 ; SSE:       # %bb.0:
-; SSE-NEXT:    movd %xmm0, %eax
-; SSE-NEXT:    movzwl %ax, %ecx
-; SSE-NEXT:    imull $25645, %ecx, %ecx # imm = 0x642D
-; SSE-NEXT:    shrl $16, %ecx
-; SSE-NEXT:    subl %ecx, %eax
-; SSE-NEXT:    movzwl %ax, %eax
-; SSE-NEXT:    shrl %eax
-; SSE-NEXT:    addl %ecx, %eax
-; SSE-NEXT:    shrl $4, %eax
-; SSE-NEXT:    movd %eax, %xmm1
-; SSE-NEXT:    pextrw $1, %xmm0, %eax
-; SSE-NEXT:    imull $61681, %eax, %eax # imm = 0xF0F1
-; SSE-NEXT:    shrl $21, %eax
-; SSE-NEXT:    pinsrw $1, %eax, %xmm1
-; SSE-NEXT:    pextrw $2, %xmm0, %eax
-; SSE-NEXT:    imull $8195, %eax, %eax # imm = 0x2003
-; SSE-NEXT:    shrl $29, %eax
-; SSE-NEXT:    pinsrw $2, %eax, %xmm1
-; SSE-NEXT:    pextrw $3, %xmm0, %eax
-; SSE-NEXT:    shrl $3, %eax
-; SSE-NEXT:    imull $9363, %eax, %eax # imm = 0x2493
-; SSE-NEXT:    shrl $16, %eax
-; SSE-NEXT:    pinsrw $3, %eax, %xmm1
-; SSE-NEXT:    pextrw $4, %xmm0, %eax
-; SSE-NEXT:    shrl $7, %eax
-; SSE-NEXT:    pinsrw $4, %eax, %xmm1
-; SSE-NEXT:    pextrw $5, %xmm0, %eax
-; SSE-NEXT:    xorl %ecx, %ecx
-; SSE-NEXT:    cmpl $65535, %eax # imm = 0xFFFF
-; SSE-NEXT:    sete %cl
-; SSE-NEXT:    pinsrw $5, %ecx, %xmm1
-; SSE-NEXT:    pextrw $6, %xmm0, %eax
-; SSE-NEXT:    imull $32897, %eax, %eax # imm = 0x8081
-; SSE-NEXT:    shrl $31, %eax
-; SSE-NEXT:    pinsrw $6, %eax, %xmm1
-; SSE-NEXT:    pextrw $7, %xmm0, %eax
-; SSE-NEXT:    shrl $15, %eax
-; SSE-NEXT:    pinsrw $7, %eax, %xmm1
-; SSE-NEXT:    movdqa %xmm1, %xmm0
+; SSE-NEXT:    movdqa %xmm0, %xmm1
+; SSE-NEXT:    psrlw $3, %xmm1
+; SSE-NEXT:    pblendw {{.*#+}} xmm1 = xmm0[0,1,2],xmm1[3],xmm0[4,5,6,7]
+; SSE-NEXT:    pmulhuw {{.*}}(%rip), %xmm1
+; SSE-NEXT:    psubw %xmm1, %xmm0
+; SSE-NEXT:    psrlw $1, %xmm0
+; SSE-NEXT:    paddw %xmm1, %xmm0
+; SSE-NEXT:    pblendw {{.*#+}} xmm0 = xmm0[0],xmm1[1,2,3,4,5,6,7]
+; SSE-NEXT:    movdqa {{.*#+}} xmm1 = <4096,2048,8,u,u,2,2,u>
+; SSE-NEXT:    pmulhuw %xmm0, %xmm1
+; SSE-NEXT:    pblendw {{.*#+}} xmm0 = xmm1[0,1,2],xmm0[3,4],xmm1[5,6],xmm0[7]
 ; SSE-NEXT:    retq
 ;
 ; AVX-LABEL: combine_vec_udiv_nonuniform:
 ; AVX:       # %bb.0:
-; AVX-NEXT:    vmovd %xmm0, %eax
-; AVX-NEXT:    movzwl %ax, %ecx
-; AVX-NEXT:    imull $25645, %ecx, %ecx # imm = 0x642D
-; AVX-NEXT:    shrl $16, %ecx
-; AVX-NEXT:    subl %ecx, %eax
-; AVX-NEXT:    movzwl %ax, %eax
-; AVX-NEXT:    shrl %eax
-; AVX-NEXT:    addl %ecx, %eax
-; AVX-NEXT:    shrl $4, %eax
-; AVX-NEXT:    vmovd %eax, %xmm1
-; AVX-NEXT:    vpextrw $1, %xmm0, %eax
-; AVX-NEXT:    imull $61681, %eax, %eax # imm = 0xF0F1
-; AVX-NEXT:    shrl $21, %eax
-; AVX-NEXT:    vpinsrw $1, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $2, %xmm0, %eax
-; AVX-NEXT:    imull $8195, %eax, %eax # imm = 0x2003
-; AVX-NEXT:    shrl $29, %eax
-; AVX-NEXT:    vpinsrw $2, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $3, %xmm0, %eax
-; AVX-NEXT:    shrl $3, %eax
-; AVX-NEXT:    imull $9363, %eax, %eax # imm = 0x2493
-; AVX-NEXT:    shrl $16, %eax
-; AVX-NEXT:    vpinsrw $3, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $4, %xmm0, %eax
-; AVX-NEXT:    shrl $7, %eax
-; AVX-NEXT:    vpinsrw $4, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $5, %xmm0, %eax
-; AVX-NEXT:    xorl %ecx, %ecx
-; AVX-NEXT:    cmpl $65535, %eax # imm = 0xFFFF
-; AVX-NEXT:    sete %cl
-; AVX-NEXT:    vpinsrw $5, %ecx, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $6, %xmm0, %eax
-; AVX-NEXT:    imull $32897, %eax, %eax # imm = 0x8081
-; AVX-NEXT:    shrl $31, %eax
-; AVX-NEXT:    vpinsrw $6, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $7, %xmm0, %eax
-; AVX-NEXT:    shrl $15, %eax
-; AVX-NEXT:    vpinsrw $7, %eax, %xmm1, %xmm0
+; AVX-NEXT:    vpsrlw $3, %xmm0, %xmm1
+; AVX-NEXT:    vpblendw {{.*#+}} xmm1 = xmm0[0,1,2],xmm1[3],xmm0[4,5,6,7]
+; AVX-NEXT:    vpmulhuw {{.*}}(%rip), %xmm1, %xmm1
+; AVX-NEXT:    vpsubw %xmm1, %xmm0, %xmm0
+; AVX-NEXT:    vpsrlw $1, %xmm0, %xmm0
+; AVX-NEXT:    vpaddw %xmm1, %xmm0, %xmm0
+; AVX-NEXT:    vpblendw {{.*#+}} xmm0 = xmm0[0],xmm1[1,2,3,4,5,6,7]
+; AVX-NEXT:    vpmulhuw {{.*}}(%rip), %xmm0, %xmm1
+; AVX-NEXT:    vpblendw {{.*#+}} xmm0 = xmm1[0,1,2],xmm0[3,4],xmm1[5,6],xmm0[7]
 ; AVX-NEXT:    retq
   %1 = udiv <8 x i16> %x, <i16 23, i16 34, i16 -23, i16 56, i16 128, i16 -1, i16 -256, i16 -32768>
   ret <8 x i16> %1
 }
 
 define <8 x i16> @combine_vec_udiv_nonuniform2(<8 x i16> %x) {
 ; SSE-LABEL: combine_vec_udiv_nonuniform2:
 ; SSE:       # %bb.0:
-; SSE-NEXT:    pextrw $1, %xmm0, %eax
-; SSE-NEXT:    imull $59919, %eax, %eax # imm = 0xEA0F
-; SSE-NEXT:    shrl $21, %eax
-; SSE-NEXT:    pextrw $0, %xmm0, %ecx
-; SSE-NEXT:    shrl %ecx
-; SSE-NEXT:    imull $16393, %ecx, %ecx # imm = 0x4009
-; SSE-NEXT:    shrl $29, %ecx
-; SSE-NEXT:    movd %ecx, %xmm1
-; SSE-NEXT:    pinsrw $1, %eax, %xmm1
-; SSE-NEXT:    pextrw $2, %xmm0, %eax
-; SSE-NEXT:    imull $58255, %eax, %eax # imm = 0xE38F
-; SSE-NEXT:    shrl $21, %eax
-; SSE-NEXT:    pinsrw $2, %eax, %xmm1
-; SSE-NEXT:    pextrw $3, %xmm0, %eax
-; SSE-NEXT:    imull $32787, %eax, %eax # imm = 0x8013
-; SSE-NEXT:    shrl $31, %eax
-; SSE-NEXT:    pinsrw $3, %eax, %xmm1
-; SSE-NEXT:    pextrw $4, %xmm0, %eax
-; SSE-NEXT:    imull $55189, %eax, %eax # imm = 0xD795
-; SSE-NEXT:    shrl $21, %eax
-; SSE-NEXT:    pinsrw $4, %eax, %xmm1
-; SSE-NEXT:    pextrw $5, %xmm0, %eax
-; SSE-NEXT:    imull $8197, %eax, %eax # imm = 0x2005
-; SSE-NEXT:    shrl $29, %eax
-; SSE-NEXT:    pinsrw $5, %eax, %xmm1
-; SSE-NEXT:    pextrw $6, %xmm0, %eax
-; SSE-NEXT:    imull $52429, %eax, %eax # imm = 0xCCCD
-; SSE-NEXT:    shrl $21, %eax
-; SSE-NEXT:    pinsrw $6, %eax, %xmm1
-; SSE-NEXT:    pextrw $7, %xmm0, %eax
-; SSE-NEXT:    imull $32789, %eax, %eax # imm = 0x8015
-; SSE-NEXT:    shrl $31, %eax
-; SSE-NEXT:    pinsrw $7, %eax, %xmm1
+; SSE-NEXT:    movdqa %xmm0, %xmm1
+; SSE-NEXT:    psrlw $1, %xmm1
+; SSE-NEXT:    pblendw {{.*#+}} xmm1 = xmm1[0],xmm0[1,2,3,4,5,6,7]
+; SSE-NEXT:    pmulhuw {{.*}}(%rip), %xmm1
+; SSE-NEXT:    pmulhuw {{.*}}(%rip), %xmm1
 ; SSE-NEXT:    movdqa %xmm1, %xmm0
 ; SSE-NEXT:    retq
 ;
 ; AVX-LABEL: combine_vec_udiv_nonuniform2:
 ; AVX:       # %bb.0:
-; AVX-NEXT:    vpextrw $1, %xmm0, %eax
-; AVX-NEXT:    imull $59919, %eax, %eax # imm = 0xEA0F
-; AVX-NEXT:    shrl $21, %eax
-; AVX-NEXT:    vpextrw $0, %xmm0, %ecx
-; AVX-NEXT:    shrl %ecx
-; AVX-NEXT:    imull $16393, %ecx, %ecx # imm = 0x4009
-; AVX-NEXT:    shrl $29, %ecx
-; AVX-NEXT:    vmovd %ecx, %xmm1
-; AVX-NEXT:    vpinsrw $1, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $2, %xmm0, %eax
-; AVX-NEXT:    imull $58255, %eax, %eax # imm = 0xE38F
-; AVX-NEXT:    shrl $21, %eax
-; AVX-NEXT:    vpinsrw $2, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $3, %xmm0, %eax
-; AVX-NEXT:    imull $32787, %eax, %eax # imm = 0x8013
-; AVX-NEXT:    shrl $31, %eax
-; AVX-NEXT:    vpinsrw $3, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $4, %xmm0, %eax
-; AVX-NEXT:    imull $55189, %eax, %eax # imm = 0xD795
-; AVX-NEXT:    shrl $21, %eax
-; AVX-NEXT:    vpinsrw $4, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $5, %xmm0, %eax
-; AVX-NEXT:    imull $8197, %eax, %eax # imm = 0x2005
-; AVX-NEXT:    shrl $29, %eax
-; AVX-NEXT:    vpinsrw $5, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $6, %xmm0, %eax
-; AVX-NEXT:    imull $52429, %eax, %eax # imm = 0xCCCD
-; AVX-NEXT:    shrl $21, %eax
-; AVX-NEXT:    vpinsrw $6, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $7, %xmm0, %eax
-; AVX-NEXT:    imull $32789, %eax, %eax # imm = 0x8015
-; AVX-NEXT:    shrl $31, %eax
-; AVX-NEXT:    vpinsrw $7, %eax, %xmm1, %xmm0
+; AVX-NEXT:    vpsrlw $1, %xmm0, %xmm1
+; AVX-NEXT:    vpblendw {{.*#+}} xmm0 = xmm1[0],xmm0[1,2,3,4,5,6,7]
+; AVX-NEXT:    vpmulhuw {{.*}}(%rip), %xmm0, %xmm0
+; AVX-NEXT:    vpmulhuw {{.*}}(%rip), %xmm0, %xmm0
 ; AVX-NEXT:    retq
   %1 = udiv <8 x i16> %x, <i16 -34, i16 35, i16 36, i16 -37, i16 38, i16 -39, i16 40, i16 -41>
   ret <8 x i16> %1
 }
 
 define <8 x i16> @combine_vec_udiv_nonuniform3(<8 x i16> %x) {
 ; SSE-LABEL: combine_vec_udiv_nonuniform3:
 ; SSE:       # %bb.0:
-; SSE-NEXT:    pextrw $1, %xmm0, %eax
-; SSE-NEXT:    imull $25645, %eax, %ecx # imm = 0x642D
-; SSE-NEXT:    shrl $16, %ecx
-; SSE-NEXT:    subl %ecx, %eax
-; SSE-NEXT:    movzwl %ax, %eax
-; SSE-NEXT:    shrl %eax
-; SSE-NEXT:    addl %ecx, %eax
-; SSE-NEXT:    shrl $4, %eax
-; SSE-NEXT:    movd %xmm0, %ecx
-; SSE-NEXT:    movzwl %cx, %edx
-; SSE-NEXT:    imull $9363, %edx, %edx # imm = 0x2493
-; SSE-NEXT:    shrl $16, %edx
-; SSE-NEXT:    subl %edx, %ecx
-; SSE-NEXT:    movzwl %cx, %ecx
-; SSE-NEXT:    shrl %ecx
-; SSE-NEXT:    addl %edx, %ecx
-; SSE-NEXT:    shrl $2, %ecx
-; SSE-NEXT:    movd %ecx, %xmm1
-; SSE-NEXT:    pinsrw $1, %eax, %xmm1
-; SSE-NEXT:    pextrw $2, %xmm0, %eax
-; SSE-NEXT:    imull $18351, %eax, %ecx # imm = 0x47AF
-; SSE-NEXT:    shrl $16, %ecx
-; SSE-NEXT:    subl %ecx, %eax
-; SSE-NEXT:    movzwl %ax, %eax
-; SSE-NEXT:    shrl %eax
-; SSE-NEXT:    addl %ecx, %eax
-; SSE-NEXT:    shrl $4, %eax
-; SSE-NEXT:    pinsrw $2, %eax, %xmm1
-; SSE-NEXT:    pextrw $3, %xmm0, %eax
-; SSE-NEXT:    imull $12137, %eax, %ecx # imm = 0x2F69
-; SSE-NEXT:    shrl $16, %ecx
-; SSE-NEXT:    subl %ecx, %eax
-; SSE-NEXT:    movzwl %ax, %eax
-; SSE-NEXT:    shrl %eax
-; SSE-NEXT:    addl %ecx, %eax
-; SSE-NEXT:    shrl $4, %eax
-; SSE-NEXT:    pinsrw $3, %eax, %xmm1
-; SSE-NEXT:    pextrw $4, %xmm0, %eax
-; SSE-NEXT:    imull $2115, %eax, %ecx # imm = 0x843
-; SSE-NEXT:    shrl $16, %ecx
-; SSE-NEXT:    subl %ecx, %eax
-; SSE-NEXT:    movzwl %ax, %eax
-; SSE-NEXT:    shrl %eax
-; SSE-NEXT:    addl %ecx, %eax
-; SSE-NEXT:    shrl $4, %eax
-; SSE-NEXT:    pinsrw $4, %eax, %xmm1
-; SSE-NEXT:    pextrw $5, %xmm0, %eax
-; SSE-NEXT:    imull $23705, %eax, %ecx # imm = 0x5C99
-; SSE-NEXT:    shrl $16, %ecx
-; SSE-NEXT:    subl %ecx, %eax
-; SSE-NEXT:    movzwl %ax, %eax
-; SSE-NEXT:    shrl %eax
-; SSE-NEXT:    addl %ecx, %eax
-; SSE-NEXT:    shrl $5, %eax
-; SSE-NEXT:    pinsrw $5, %eax, %xmm1
-; SSE-NEXT:    pextrw $6, %xmm0, %eax
-; SSE-NEXT:    imull $1041, %eax, %ecx # imm = 0x411
-; SSE-NEXT:    shrl $16, %ecx
-; SSE-NEXT:    subl %ecx, %eax
-; SSE-NEXT:    movzwl %ax, %eax
-; SSE-NEXT:    shrl %eax
-; SSE-NEXT:    addl %ecx, %eax
-; SSE-NEXT:    shrl $5, %eax
-; SSE-NEXT:    pinsrw $6, %eax, %xmm1
-; SSE-NEXT:    pextrw $7, %xmm0, %eax
-; SSE-NEXT:    imull $517, %eax, %ecx # imm = 0x205
-; SSE-NEXT:    shrl $16, %ecx
-; SSE-NEXT:    subl %ecx, %eax
-; SSE-NEXT:    movzwl %ax, %eax
-; SSE-NEXT:    shrl %eax
-; SSE-NEXT:    addl %ecx, %eax
-; SSE-NEXT:    shrl $6, %eax
-; SSE-NEXT:    pinsrw $7, %eax, %xmm1
-; SSE-NEXT:    movdqa %xmm1, %xmm0
+; SSE-NEXT:    movdqa {{.*#+}} xmm1 = [9363,25645,18351,12137,2115,23705,1041,517]
+; SSE-NEXT:    pmulhuw %xmm0, %xmm1
+; SSE-NEXT:    psubw %xmm1, %xmm0
+; SSE-NEXT:    psrlw $1, %xmm0
+; SSE-NEXT:    paddw %xmm1, %xmm0
+; SSE-NEXT:    pmulhuw {{.*}}(%rip), %xmm0
 ; SSE-NEXT:    retq
 ;
 ; AVX-LABEL: combine_vec_udiv_nonuniform3:
 ; AVX:       # %bb.0:
-; AVX-NEXT:    vpextrw $1, %xmm0, %eax
-; AVX-NEXT:    imull $25645, %eax, %ecx # imm = 0x642D
-; AVX-NEXT:    shrl $16, %ecx
-; AVX-NEXT:    subl %ecx, %eax
-; AVX-NEXT:    movzwl %ax, %eax
-; AVX-NEXT:    shrl %eax
-; AVX-NEXT:    addl %ecx, %eax
-; AVX-NEXT:    shrl $4, %eax
-; AVX-NEXT:    vmovd %xmm0, %ecx
-; AVX-NEXT:    movzwl %cx, %edx
-; AVX-NEXT:    imull $9363, %edx, %edx # imm = 0x2493
-; AVX-NEXT:    shrl $16, %edx
-; AVX-NEXT:    subl %edx, %ecx
-; AVX-NEXT:    movzwl %cx, %ecx
-; AVX-NEXT:    shrl %ecx
-; AVX-NEXT:    addl %edx, %ecx
-; AVX-NEXT:    shrl $2, %ecx
-; AVX-NEXT:    vmovd %ecx, %xmm1
-; AVX-NEXT:    vpinsrw $1, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $2, %xmm0, %eax
-; AVX-NEXT:    imull $18351, %eax, %ecx # imm = 0x47AF
-; AVX-NEXT:    shrl $16, %ecx
-; AVX-NEXT:    subl %ecx, %eax
-; AVX-NEXT:    movzwl %ax, %eax
-; AVX-NEXT:    shrl %eax
-; AVX-NEXT:    addl %ecx, %eax
-; AVX-NEXT:    shrl $4, %eax
-; AVX-NEXT:    vpinsrw $2, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $3, %xmm0, %eax
-; AVX-NEXT:    imull $12137, %eax, %ecx # imm = 0x2F69
-; AVX-NEXT:    shrl $16, %ecx
-; AVX-NEXT:    subl %ecx, %eax
-; AVX-NEXT:    movzwl %ax, %eax
-; AVX-NEXT:    shrl %eax
-; AVX-NEXT:    addl %ecx, %eax
-; AVX-NEXT:    shrl $4, %eax
-; AVX-NEXT:    vpinsrw $3, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $4, %xmm0, %eax
-; AVX-NEXT:    imull $2115, %eax, %ecx # imm = 0x843
-; AVX-NEXT:    shrl $16, %ecx
-; AVX-NEXT:    subl %ecx, %eax
-; AVX-NEXT:    movzwl %ax, %eax
-; AVX-NEXT:    shrl %eax
-; AVX-NEXT:    addl %ecx, %eax
-; AVX-NEXT:    shrl $4, %eax
-; AVX-NEXT:    vpinsrw $4, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $5, %xmm0, %eax
-; AVX-NEXT:    imull $23705, %eax, %ecx # imm = 0x5C99
-; AVX-NEXT:    shrl $16, %ecx
-; AVX-NEXT:    subl %ecx, %eax
-; AVX-NEXT:    movzwl %ax, %eax
-; AVX-NEXT:    shrl %eax
-; AVX-NEXT:    addl %ecx, %eax
-; AVX-NEXT:    shrl $5, %eax
-; AVX-NEXT:    vpinsrw $5, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $6, %xmm0, %eax
-; AVX-NEXT:    imull $1041, %eax, %ecx # imm = 0x411
-; AVX-NEXT:    shrl $16, %ecx
-; AVX-NEXT:    subl %ecx, %eax
-; AVX-NEXT:    movzwl %ax, %eax
-; AVX-NEXT:    shrl %eax
-; AVX-NEXT:    addl %ecx, %eax
-; AVX-NEXT:    shrl $5, %eax
-; AVX-NEXT:    vpinsrw $6, %eax, %xmm1, %xmm1
-; AVX-NEXT:    vpextrw $7, %xmm0, %eax
-; AVX-NEXT:    imull $517, %eax, %ecx # imm = 0x205
-; AVX-NEXT:    shrl $16, %ecx
-; AVX-NEXT:    subl %ecx, %eax
-; AVX-NEXT:    movzwl %ax, %eax
-; AVX-NEXT:    shrl %eax
-; AVX-NEXT:    addl %ecx, %eax
-; AVX-NEXT:    shrl $6, %eax
-; AVX-NEXT:    vpinsrw $7, %eax, %xmm1, %xmm0
+; AVX-NEXT:    vpmulhuw {{.*}}(%rip), %xmm0, %xmm1
+; AVX-NEXT:    vpsubw %xmm1, %xmm0, %xmm0
+; AVX-NEXT:    vpsrlw $1, %xmm0, %xmm0
+; AVX-NEXT:    vpaddw %xmm1, %xmm0, %xmm0
+; AVX-NEXT:    vpmulhuw {{.*}}(%rip), %xmm0, %xmm0
 ; AVX-NEXT:    retq
   %1 = udiv <8 x i16> %x, <i16 7, i16 23, i16 25, i16 27, i16 31, i16 47, i16 63, i16 127>
   ret <8 x i16> %1
 }