[DAGCombiner] Bug 31275- Extract a shift from a constant mul or udiv if a rotate can be formed

[sameconrad]

Summary

Attempt to extract a shrl from a udiv or a shl from a mul if this allows a rotate to be formed. This targets cases where the input to a rotate pattern was a mul or udiv by a constant and InstCombine merged one of the shifts with the op.

Patch by: sameconrad (Sam Conrad)

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5091–5102 ↗

(On Diff #149623)

Aren't we loosing by bailing out here? (And no tests show it?!)
Maybe you meant:

// If only one side has a shift, see if we can extract it
if (!(NeedRotLHS ^ NeedRotRHS)) {
  if (NeedRotRHS) {
    if (SDValue Shift = extractShiftFromMulOrUDiv(LHSShift, RHS, RHSMask, DL))
      RHSShift = Shift;
  }
  if (NeedRotLHS) {
    if (SDValue Shift = extractShiftFromMulOrUDiv(RHSShift, LHS, LHSMask, DL))
      LHSShift = Shift;
  }
}

Please don't blindly follow that snippet, i don't know what the other code does,
so your change may be correct as-is.

test/CodeGen/X86/rotate-extract.ll

1 ↗

(On Diff #149623)

You might want to use llvm/utils/update_llc_test_checks.py

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5096–5100 ↗

(On Diff #149623)

Also, it is intentional that you extract from LHS and store it into a variable named RHS and vice-versa?
If yes, add a comment please.

[sameconrad]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5091–5102 ↗

(On Diff #149623)

I'll add some extra comments here and update in a bit, but I don't think we're losing out on anything.
The idea here is that if MatchRotateHalf matches one half of the OR as a shl/srl but not the other, we try to extract the needed shift from the unmatched side to complete the rotate. The case where neither side matched (ie NeedRotLHS && NeedRotRHS) is handled above, so at this point either no side is missing and neither of these if cases will fire, or only one side is missing, in which case we try to extract the shift from the missing side (using the shift that did match from the opposite side to compute the shift amount and opcode needed, hence we pass LHSShift when trying to extract from the RHS and vice versa). If extraction fails at that point then we definitely can't complete the rotate and bail.

For instance if NeedRotRHS==true and LHSShift is (srl v 10) and bitwidth(v)==32, then extractShiftFromMulOrDiv will compute that we need to extract (shl v 22) from RHS based on the shift amount and opcode in LHSShift.

[sameconrad]

Update tests with update_llc_test_checks
Improve comments in MatchRotate

[sameconrad]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5096–5100 ↗

(On Diff #149623)

Updated with some clarifying comments

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5057 ↗

(On Diff #149658)

Is this always considered worth doing,
or the check whether this should be done is on the caller's side?

test/CodeGen/X86/rotate-extract.ll

2 ↗

(On Diff #149658)

You could also copy this into test/CodeGen/AArch64/rotate-extract.ll,
since that should also profit from the transform.

[sameconrad]

Added AArch64 test

[sameconrad]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5057 ↗

(On Diff #149658)

It looks like MatchRotate always gets called from DAGCombiner::visitOr, I don't think there's any sort of profitability check, so it seems to assume its always worthwhile (however I'm still pretty new to LLVM and don't know if there are other places this could be done). In any case, the new code would transform 4 instructions to 2 (2 mul/udiv ops, 1 shift, 1 or -> one mul/udiv op and 1 rotate).

[sameconrad]

Quick update to improve assert messages

[sameconrad]

Ping

[RKSimon]

The tests probably need committing with trunk's current codegen, so this patch then shows the diff.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4822 ↗

(On Diff #149902)

You can merge these if statements:

if (Op.getOpcode() == ISD::AND &&
    DAG.isConstantIntBuildVectorOrConstantInt(Op.getOperand(1))) {

4831 ↗

(On Diff #149902)

Does this need to be a DAGCombiner method any more? Just reduce it to a static.

4842 ↗

(On Diff #149902)

Again, what do you gain from this being a DAGCombiner method?

4850 ↗

(On Diff #149902)

Do we have any tests that use the Mask?

4878 ↗

(On Diff #149902)

This is more convoluted than it needs to be - the GetConstant isn't really helping and comparing against APInt() is a bad idea

Would it be better to just do (not sure about this):

// Attempt to find non-zero constants for opposing shift and the mul/div +shift.
ConstantSDNode *OppShiftCst = isConstOrConstSplat(OpposingShift.getOperand(1));
ConstantSDNode *ShiftCst = isConstOrConstSplat(ShiftLHS.getOperand(1));
ConstantSDNode *MulOrDivCst = isConstOrConstSplat(MulOrDiv.getOperand(1));
if (!OppShiftCst || !ShiftCst !! MulOrDivCst ||
    !OppShiftCst->getAPIntValue() || !ShiftCst->getAPIntValue() || !MulOrDivCst->getAPIntValue())
  return SDValue();

Also, we should bail if the OppShiftCst is out of range.

4885 ↗

(On Diff #149902)

Is this better?

APInt ShiftExtractDiv = APInt::getOneBitSet(VTWidth, NewShiftAmt;.getZextValue());

4901 ↗

(On Diff #149902)

Worth doing this earlier?

5116 ↗

(On Diff #149902)

This could be reduced to:

if (NeedRotRHS)
  RHSShift = extractShiftFromMulOrUDiv(LHSShift, RHS, RHSMask, DL);
if (NeedRotLHS)
  LHSShift = extractShiftFromMulOrUDiv(RHSShift, LHS, LHSMask, DL);
if (!RHSShift || !LHSShift)
  return nullptr;

[lebedev.ri]

BTW, that reminds me.
@sameconrad while you are looking at rotates in backend, can you please also check (at least add tests,
if there aren't any yet) that backend properly handles the cases where mul/div were transformed into shifts?

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

490 ↗

(On Diff #149902)

In other words, the cases where c0, c1, c2 were power-of-two, and thus instcombine turned them into shifts.
So additional [straight-forward] cases are:

///   (or (shrl (shl v c0') c1) (shl v c2')) ->
///   (or (shrl (shl v c0') c1) (shl (shl v c0') c3))
/// and
///   (or (shrl v c0') (shl (shrl v c1') c2)) ->
///   (or (shrl (shrl v c1') c3) (shl (shrl v c1') c2))

There is also an additional problem when we are/will convert shrl+shl / shl+rhrl into masking...

[sameconrad]

Clean up code quality
Add tests with bitmask case

[sameconrad]

Small bit of code cleanup that was missed

[sameconrad]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4850 ↗

(On Diff #149902)

Added a mask test

4878 ↗

(On Diff #149902)

Fixed up most of this but wasn't sure what you meant by out of range, do you mean if the existing shift amount is greater than the bitwidth?

[sameconrad]

In D47681#1131359, @lebedev.ri wrote:

BTW, that reminds me.
@sameconrad while you are looking at rotates in backend, can you please also check (at least add tests,
if there aren't any yet) that backend properly handles the cases where mul/div were transformed into shifts?

I can take a look at that, will do that in a separate patch.

Actually nvm, I see what you're saying. I'll try to update this patch in a bit for that case.

[lebedev.ri]

In D47681#1131982, @sameconrad wrote:

In D47681#1131359, @lebedev.ri wrote:

BTW, that reminds me.
@sameconrad while you are looking at rotates in backend, can you please also check (at least add tests,
if there aren't any yet) that backend properly handles the cases where mul/div were transformed into shifts?

I can take a look at that, will do that in a separate patch.

Actually nvm, I see what you're saying. I'll try to update this patch in a bit for that case.

You can refer to the tests in D48229 for the examples of patterns that are related.

[sameconrad]

Update to also handle cases where we need to extract a smaller shift from a shl/srl.

[sameconrad]

In D47681#1134801, @lebedev.ri wrote:

In D47681#1131982, @sameconrad wrote:

In D47681#1131359, @lebedev.ri wrote:

BTW, that reminds me.
@sameconrad while you are looking at rotates in backend, can you please also check (at least add tests,
if there aren't any yet) that backend properly handles the cases where mul/div were transformed into shifts?

I can take a look at that, will do that in a separate patch.

Actually nvm, I see what you're saying. I'll try to update this patch in a bit for that case.

You can refer to the tests in D48229 for the examples of patterns that are related.

Updated the patch to handle extracting from a shl/srl.
For handling srl+shl->bitmask cases I'd prefer to do a follow-up patch since I need a bit more time to look at it.

[lebedev.ri]

In D47681#1134871, @sameconrad wrote:

In D47681#1134801, @lebedev.ri wrote:

In D47681#1131982, @sameconrad wrote:

In D47681#1131359, @lebedev.ri wrote:

BTW, that reminds me.
@sameconrad while you are looking at rotates in backend, can you please also check (at least add tests,
if there aren't any yet) that backend properly handles the cases where mul/div were transformed into shifts?

I can take a look at that, will do that in a separate patch.

Actually nvm, I see what you're saying. I'll try to update this patch in a bit for that case.

You can refer to the tests in D48229 for the examples of patterns that are related.

Updated the patch to handle extracting from a shl/srl.

For handling srl+shl->bitmask cases I'd prefer to do a follow-up patch since I need a bit more time to look at it.

Yes, absolutely. Currently we don't produce that pattern yet in all the cases, so it is of less importance!

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4831–4841 ↗

(On Diff #151651)

This should be:

//   (or (shrl (mul v c0) c1)      (mul v c2)) ->
//   (or (shrl (mul v c0) c1) (shl (mul v c3) c4))
//
//   (or       (udiv v c0)     (shl (udiv v c1) c2)) ->
//   (or (shrl (udiv v c3) c4) (shl (udiv v c1) c2))
//
//   (or (shrl (shl v c0) c1)      (shl v c2)) ->
//   (or (shrl (shl v c0) c1) (shl (shl v c3) c4))
//
//   (or       (shrl v c0)     (shl (shrl v c1) c2)) ->
//   (or (shrl (shrl v c1) c3) (shl (shrl v c1) c2))
//
// NEW:
//   (or (shrl (shl v c0) c1)      (mul v c2)) ->
//   (or (shrl (shl v c0) c1) (shl (mul v c3) c4))
//
//   (or       (shrl v c0)     (shl (div v c1) c2)) ->
//   (or (shrl (shrl v c1) c3) (shl (div v c1) c2))

We may not always succeed in converting mul/div into a shift,

4842–4843 ↗

(On Diff #151651)

You want to add a comment that it will be called for both the LHS and RHS,
so it does not have to worry about looking at the other side here.

[sameconrad]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4831–4841 ↗

(On Diff #151651)

Could you clarify a bit? The four cases shown in the original code comment were meant to be the valid expansions the function may produce, whereas the added cases don't seem to be valid expansions that could be used to form rotates. For example in your comment the first case was changed to show the LHS of the original shift as (mul v c0) but the LHS of the new shift as (mul v c3) which seems to imply c0 != c3. If the function encountered that it would return an empty SDValue because a rotate can't be formed if the LHS of the existing shift and the leftover LHS of the extracted shift don't match.

(or (shrl (shl v c0) c1) (mul v c2)) ->
// (or (shrl (shl v c0) c1) (shl (mul v c3) c4))

Would InstCombine would generate a case like this that would still provide a valid expansion after extracting the shift (ie where the resulting (mul v c3) is equivalent to (shl v c0))?
In its current state this function should see that the existing shift's LHS (shl v c0) has an opcode that doesn't match the extract op (mul v c3) and just return the SDValue(), because it expects that if InstCombine had merged a shl with another shl the result should have been a greater shl rather than a mul (and thus just assumes that after extracting we couldn't have a leftover op that matches (shl v c0)). I had assumed that if InstCombine merges a mul by a power of 2 with a shift it would produce a greater shift rather than a mul by a greater power of 2 but I would have to test that, if it doesn't and produces a mul then I could probably add some logic to check if the leftover mul can be converted to a shift after extraction to match the existing shift's LHS.

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4831–4841 ↗

(On Diff #151651)

If the function encountered that it would return an empty SDValue because a rotate can't be formed if the LHS of the existing shift and the leftover LHS of the extracted shift don't match.

So that is the requirement on the end result? That explains it. Then i was wrong.
Can you please state that in the comment, somehow, in addition to the Attempts to expand:.

Would InstCombine would generate a case like this that would still provide a valid expansion after extracting the shift (ie where the resulting (mul v c3) is equivalent to (shl v c0))?

Now that i actually think about, no, i think it's not possible.

I had assumed that if InstCombine merges a mul by a power of 2 with a shift it would produce a greater shift

Yes, pretty sure that is what will happen.

[sameconrad]

Try to fix up clarity of comments

[sameconrad]

Friendly ping. Any more issues with this?

[lebedev.ri]

I can add some nits, but i'm not confident reviewing this as a whole..

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4863–4876 ↗

(On Diff #152011)

This does basically the same (but opposite) thing twice.
I would personally try to do something like

auto parse = [&IsMulOrDiv, &Opcode, OppShift, ExtractFrom](unsigned Op0, unsigned Op1, unsigned Op2) -> bool {
  if (OppShift.getOpcode() != Op0)
    return false;
  IsMulOrDiv = ExtractFrom.getOpcode() == Op1;
  if (IsMulOrDiv || ExtractFrom.getOpcode() == Op2)
    Opcode = Op2;
  return true;
};
if(!(parse(ISD::SRL, ISD::MUL,  ISD::SHL) ||
     parse(ISD::SHL, ISD::UDIV, ISD::SRL)) ||
   Opcode == ISD::DELETED_NODE)
  return SDValue();

Even if it's the same LOC, it significantly reduced duplication,
allowing to focus on the actual details..

4895–4897 ↗

(On Diff #152011)

What does getAPIntValue() check? We don't want shifts/mul/div by 0?

4901 ↗

(On Diff #149902)

+1 this should be done right ExtractFrom is modified.

[RKSimon]

test/CodeGen/X86/rotate-extract.ll

10 ↗

(On Diff #152011)

Please can you add tests for a mixture of i8, i16, i32 and i64 integers - no need for duplication of all these tests just have decent range.

Ideally we'd include some vector tests as well, possibly in a separate test file.

[sameconrad]

Address code style nits
Update scalar tests to use a variety of types/bitwidths
Add X86 vector tests

[sameconrad]

Forgot to add vector test file

[lebedev.ri]

Some more nits.
Overall, this seems ok, but i don't feel confident reviewing this as a whole :/

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

4964 ↗

(On Diff #153660)

Nit: unneeded {}

5037–5039 ↗

(On Diff #153660)

Can't you check OppShiftLHS.getOperand(0) != ExtractFrom.getOperand(0) here?

5080 ↗

(On Diff #153660)

bitwidth

5292–5294 ↗

(On Diff #153660)

Do you need those extra variables to to track this?
Maybe you can s/NeedRotLHS/!LHSShift/, and drop the variables?
Otherwise i fear later on they may start meaning different things.

4895–4897 ↗

(On Diff #152011)

I didn't receive a reply here

4901 ↗

(On Diff #149902)

Not done.

test/CodeGen/X86/rotate-extract.ll

83 ↗

(On Diff #153660)

These are all rol's, and in aarch64 they are all ror's, even though the tests appear identical, interesting.
Any way to produce both ror and rol instructions for both arches?

[efriedma]

test/CodeGen/X86/rotate-extract.ll

83 ↗

(On Diff #153660)

AArch64 doesn't have a rol instruction.

[sameconrad]

Address comments

[sameconrad]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5037–5039 ↗

(On Diff #153660)

I moved the opcode check to right after stripConstantMask like you mentioned in your other comment, so this operand(0) check comes right after that now. I think we should verify the ExtractFrom opcode is a shift/mul/udiv before checking operands, otherwise we don't know what the operand count of the instruction is.

5292–5294 ↗

(On Diff #153660)

Thanks for pointing that out. Those bools were completely unneeded.

4895–4897 ↗

(On Diff #152011)

Yes, just checks that is not 0. A rotate by zero would just be a noop, so it didn't seem to make sense to try and extract anything in that case.

4842–4843 ↗

(On Diff #151651)

This is mentioned in the comments I added in MatchRotate

4901 ↗

(On Diff #149902)

I moved the opcode check to the beginning of the function, I believe that was the original request here? The review comments get misaligned after updating the code

test/CodeGen/X86/rotate-extract.ll

83 ↗

(On Diff #153660)

The ISD selection in MatchRotate just looks like HasROTL ? ISD::ROTL : ISD::ROTR, so it looks will just always choose a rotl if available and fall back to a rotr like it does on AArch64. Since X86 has rotl it will always select that, I don't see any way to vary it within the same ISA.

[lebedev.ri]

It seems everyone else is busy with other differentials, and don't have time to spare to review this :/

Have you run this on a llvm test suite?

I don't have further comments, and i could accept this, if testsuite passes,
but it would be more comfortable if someone else could review this, too.

[sameconrad]

In D47681#1162716, @lebedev.ri wrote:

It seems everyone else is busy with other differentials, and don't have time to spare to review this :/

Have you run this on a llvm test suite?

I don't have further comments, and i could accept this, if testsuite passes,
but it would be more comfortable if someone else could review this, too.

Sorry about the late response, missed this comment before. I just ran the test-suite and it looks like all 2555 passed without issue.

[lebedev.ri]

In D47681#1167516, @sameconrad wrote:

In D47681#1162716, @lebedev.ri wrote:

It seems everyone else is busy with other differentials, and don't have time to spare to review this :/

Have you run this on a llvm test suite?

I don't have further comments, and i could accept this, if testsuite passes,
but it would be more comfortable if someone else could review this, too.

Sorry about the late response, missed this comment before. I just ran the test-suite and it looks like all 2555 passed without issue.

Ok then, LG.
Please wait a bit (until monday?) just in case others may want to comment, and then feel free to commit.

[RKSimon]

I've added your tests to trunk with current codegen so you need to rebase, which will show the effects of your patch.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5049 ↗

(On Diff #154474)

(style) full stops at the end of comments.

5063 ↗

(On Diff #154474)

It'd be great if this could support non-uniform constant vectors but a TODO comment is fine for now.

[sameconrad]

Rebase after tests were committed
Add full stops to comments
Add todo for handling non-splat vectors

[sameconrad]

Updated after rebasing
If this looks good someone else will have to commit since I don't have commit access
Thanks!

[lebedev.ri]

Last-minute thought - should this be limited to some specific value types?
On X86, the RCL/RCR/ROL/ROR only exist for 8/16/32/64 bit widths.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5371 ↗

(On Diff #156406)

@lebedev.ri This should ensure legality of the ROT

[lebedev.ri]

In D47681#1169179, @sameconrad wrote:

Updated after rebasing
If this looks good someone else will have to commit since I don't have commit access
Thanks!

Two other landed differentials over the last year, might as well ask for the commit rights and land it yourself :)

[RKSimon]

@sameconrad Are you getting commit access (and in time for the Aug 1 branch)?

[sameconrad]

In D47681#1179976, @RKSimon wrote:

@sameconrad Are you getting commit access (and in time for the Aug 1 branch)?

I requested it but haven't heard anything back yet, so I'm not sure if I'll be able to commit by August 1st.

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

private:
     /// Try to replace a store and any possibly adjacent stores on
     /// consecutive chains with better chains. Return true only if St is
     /// replaced.
     ///
     /// Notice that other chains may still be replaced even if the function
     /// returns false.
     bool findBetterNeighborChains(StoreSDNode *St);
 
-    /// Match "(X shl/srl V1) & V2" where V2 may not be present.
-    bool MatchRotateHalf(SDValue Op, SDValue &Shift, SDValue &Mask);
-
     /// Holds a pointer to an LSBaseSDNode as well as information on where it
     /// is located in a sequence of memory operations connected by a chain.
     struct MemOpLink {
       // Ptr to the mem node.
       LSBaseSDNode *MemNode;
 
       // Offset from the base ptr.
       int64_t OffsetFromBase;
SDValue DAGCombiner::visitOR(SDNode *N) {
 
   // Simplify the operands using demanded-bits information.
   if (SimplifyDemandedBits(SDValue(N, 0)))
     return SDValue(N, 0);
 
   return SDValue();
 }
 
-/// Match "(X shl/srl V1) & V2" where V2 may not be present.
-bool DAGCombiner::MatchRotateHalf(SDValue Op, SDValue &Shift, SDValue &Mask) {
-  if (Op.getOpcode() == ISD::AND) {
-    if (DAG.isConstantIntBuildVectorOrConstantInt(Op.getOperand(1))) {
-      Mask = Op.getOperand(1);
-      Op = Op.getOperand(0);
-    } else {
-      return false;
-    }
-  }
+static SDValue stripConstantMask(SelectionDAG &DAG, SDValue Op, SDValue &Mask) {
+  if (Op.getOpcode() == ISD::AND &&
+      DAG.isConstantIntBuildVectorOrConstantInt(Op.getOperand(1))) {
+    return Op.getOperand(0);
+  return Op;
 
+/// Match "(X shl/srl V1) & V2" where V2 may not be present.
+static bool matchRotateHalf(SelectionDAG &DAG, SDValue Op, SDValue &Shift,
+                            SDValue &Mask) {
+  Op = stripConstantMask(DAG, Op, Mask);
   if (Op.getOpcode() == ISD::SRL || Op.getOpcode() == ISD::SHL) {
     Shift = Op;
     return true;
   }
+  return false;
+}
 
+/// Helper function for visitOR to extract the needed side of a rotate idiom
+/// from a shl/srl/mul/udiv.  This is meant to handle cases where
+/// InstCombine merged some outside op with one of the shifts from
+/// the rotate pattern.
+/// \returns An empty \c SDValue if the needed shift couldn't be extracted.
+/// Otherwise, returns an expansion of \p ExtractFrom based on the following
+/// patterns:
+///
+///   (or (mul v c0) (shrl (mul v c1) c2)):
+///     expands (mul v c0) -> (shl (mul v c1) c3)
+///
+///   (or (udiv v c0) (shl (udiv v c1) c2)):
+///     expands (udiv v c0) -> (shrl (udiv v c1) c3)
+///
+///   (or (shl v c0) (shrl (shl v c1) c2)):
+///     expands (shl v c0) -> (shl (shl v c1) c3)
+///
+///   (or (shrl v c0) (shl (shrl v c1) c2)):
+///     expands (shrl v c0) -> (shrl (shrl v c1) c3)
+///
+/// Such that in all cases, c3+c2==bitwidth(op v c1).
+static SDValue extractShiftForRotate(SelectionDAG &DAG, SDValue OppShift,
+                                     SDValue ExtractFrom, SDValue &Mask,
+                                     const SDLoc &DL) {
+  assert(OppShift && ExtractFrom && "Empty SDValue");
+  assert(
+      (OppShift.getOpcode() == ISD::SHL || OppShift.getOpcode() == ISD::SRL) &&
+      "Existing shift must be valid as a rotate half");
+
+  ExtractFrom = stripConstantMask(DAG, ExtractFrom, Mask);
+  // Preconditions:
+  //    (or (op0 v c0) (shiftl/r (op0 v c1) c2))
+  //
+  // Find opcode of the needed shift to be extracted from (op0 v c0).
+  unsigned Opcode = ISD::DELETED_NODE;
+  bool IsMulOrDiv = false;
+  // Set Opcode and IsMulOrDiv if the extract opcode matches the needed shift
+  // opcode or its arithmetic (mul or udiv) variant.
+  auto SelectOpcode = [&](unsigned NeededShift, unsigned MulOrDivVariant) {
+    IsMulOrDiv = ExtractFrom.getOpcode() == MulOrDivVariant;
+    if (!IsMulOrDiv && ExtractFrom.getOpcode() != NeededShift)
       return false;
+    Opcode = NeededShift;
+    return true;
+  };
+  // op0 must be either the needed shift opcode or the mul/udiv equivalent
+  // that the needed shift can be extracted from.
+  if ((OppShift.getOpcode() != ISD::SRL || !SelectOpcode(ISD::SHL, ISD::MUL)) &&
+      (OppShift.getOpcode() != ISD::SHL || !SelectOpcode(ISD::SRL, ISD::UDIV)))
+    return SDValue();
+
+  // op0 must be the same opcode on both sides, have the same LHS argument,
+  // and produce the same value type.
+  SDValue OppShiftLHS = OppShift.getOperand(0);
+  EVT ShiftedVT = OppShiftLHS.getValueType();
+  if (OppShiftLHS.getOpcode() != ExtractFrom.getOpcode() ||
+      OppShiftLHS.getOperand(0) != ExtractFrom.getOperand(0) ||
+      ShiftedVT != ExtractFrom.getValueType())
+    return SDValue();
+
+  // Amount of the existing shift.
+  ConstantSDNode *OppShiftCst = isConstOrConstSplat(OppShift.getOperand(1));
+  // Constant mul/udiv/shift amount from the RHS of the shift's LHS op.
+  ConstantSDNode *OppLHSCst = isConstOrConstSplat(OppShiftLHS.getOperand(1));
+  // Constant mul/udiv/shift amount from the RHS of the ExtractFrom op.
+  ConstantSDNode *ExtractFromCst =
+      isConstOrConstSplat(ExtractFrom.getOperand(1));
+  // TODO: We should be able to handle non-uniform constant vectors for these values
+  // Check that we have constant values.
+  if (!OppShiftCst || !OppShiftCst->getAPIntValue() ||
+      !OppLHSCst || !OppLHSCst->getAPIntValue() ||
+      !ExtractFromCst || !ExtractFromCst->getAPIntValue())
+    return SDValue();
+
+  // Compute the shift amount we need to extract to complete the rotate.
+  const unsigned VTWidth = ShiftedVT.getScalarSizeInBits();
+  APInt NeededShiftAmt = VTWidth - OppShiftCst->getAPIntValue();
+  if (NeededShiftAmt.isNegative())
+    return SDValue();
+  // Normalize the bitwidth of the two mul/udiv/shift constant operands.
+  APInt ExtractFromAmt = ExtractFromCst->getAPIntValue();
+  APInt OppLHSAmt = OppLHSCst->getAPIntValue();
+  zeroExtendToMatch(ExtractFromAmt, OppLHSAmt);
+
+  // Now try extract the needed shift from the ExtractFrom op and see if the
+  // result matches up with the existing shift's LHS op.
+  if (IsMulOrDiv) {
+    // Op to extract from is a mul or udiv by a constant.
+    // Check:
+    //     c2 / (1 << (bitwidth(op0 v c0) - c1)) == c0
+    //     c2 % (1 << (bitwidth(op0 v c0) - c1)) == 0
+    const APInt ExtractDiv = APInt::getOneBitSet(ExtractFromAmt.getBitWidth(),
+                                                 NeededShiftAmt.getZExtValue());
+    APInt ResultAmt;
+    APInt Rem;
+    APInt::udivrem(ExtractFromAmt, ExtractDiv, ResultAmt, Rem);
+    if (Rem != 0 || ResultAmt != OppLHSAmt)
+      return SDValue();
+  } else {
+    // Op to extract from is a shift by a constant.
+    // Check:
+    //      c2 - (bitwidth(op0 v c0) - c1) == c0
+    if (OppLHSAmt != ExtractFromAmt - NeededShiftAmt.zextOrTrunc(
+                                          ExtractFromAmt.getBitWidth()))
+      return SDValue();
+  }
+
+  // Return the expanded shift op that should allow a rotate to be formed.
+  EVT ShiftVT = OppShift.getOperand(1).getValueType();
+  EVT ResVT = ExtractFrom.getValueType();
+  SDValue NewShiftNode = DAG.getConstant(NeededShiftAmt, DL, ShiftVT);
+  return DAG.getNode(Opcode, DL, ResVT, OppShiftLHS, NewShiftNode);
 }
 
 // Return true if we can prove that, whenever Neg and Pos are both in the
 // range [0, EltSize), Neg == (Pos == 0 ? 0 : EltSize - Pos).  This means that
 // for two opposing shifts shift1 and shift2 and a value X with OpBits bits:
 //
 //     (or (shift1 X, Neg), (shift2 X, Pos))
 //
if (SDNode *Rot = MatchRotate(LHS.getOperand(0), RHS.getOperand(0), DL)) {
       return DAG.getNode(ISD::TRUNCATE, SDLoc(LHS), LHS.getValueType(),
                          SDValue(Rot, 0)).getNode();
     }
   }
 
   // Match "(X shl/srl V1) & V2" where V2 may not be present.
   SDValue LHSShift;   // The shift.
   SDValue LHSMask;    // AND value if any.
-  if (!MatchRotateHalf(LHS, LHSShift, LHSMask))
-    return nullptr; // Not part of a rotate.
+  matchRotateHalf(DAG, LHS, LHSShift, LHSMask);
 
   SDValue RHSShift;   // The shift.
   SDValue RHSMask;    // AND value if any.
-  if (!MatchRotateHalf(RHS, RHSShift, RHSMask))
-    return nullptr; // Not part of a rotate.
+  matchRotateHalf(DAG, RHS, RHSShift, RHSMask);
+
+  // If neither side matched a rotate half, bail
+  if (!LHSShift && !RHSShift)
+    return nullptr;
+
+  // InstCombine may have combined a constant shl, srl, mul, or udiv with one
+  // side of the rotate, so try to handle that here. In all cases we need to
+  // pass the matched shift from the opposite side to compute the opcode and
+  // needed shift amount to extract.  We still want to do this if both sides
+  // matched a rotate half because one half may be a potential overshift that
+  // can be broken down (ie if InstCombine merged two shl or srl ops into a
+  // single one).
+
+  // Have LHS side of the rotate, try to extract the needed shift from the RHS.
+  if (LHSShift)
+    if (SDValue NewRHSShift =
+            extractShiftForRotate(DAG, LHSShift, RHS, RHSMask, DL))
+      RHSShift = NewRHSShift;
+  // Have RHS side of the rotate, try to extract the needed shift from the LHS.
+  if (RHSShift)
+    if (SDValue NewLHSShift =
+            extractShiftForRotate(DAG, RHSShift, LHS, LHSMask, DL))
+      LHSShift = NewLHSShift;
+
+  // If a side is still missing, nothing else we can do.
+  if (!RHSShift || !LHSShift)
+    return nullptr;
+
+  // At this point we've matched or extracted a shift op on each side.
   
   if (LHSShift.getOperand(0) != RHSShift.getOperand(0))
     return nullptr;   // Not shifting the same value.
 
   if (LHSShift.getOpcode() == RHSShift.getOpcode())
     return nullptr;   // Shifts must disagree.
 
   // Canonicalize shl to left side in a shl/srl pair.
   if (RHSShift.getOpcode() == ISD::SHL) {

llvm/trunk/test/CodeGen/AArch64/rotate-extract.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=aarch64-unknown-unknown | FileCheck %s
 
 ; Check that under certain conditions we can factor out a rotate
 ; from the following idioms:
 ;   (a*c0) >> s1 | (a*c1)
 ;   (a/c0) << s1 | (a/c1)
 ; This targets cases where instcombine has folded a shl/srl/mul/udiv
 ; with one of the shifts from the rotate idiom
 
 define i64 @ror_extract_shl(i64 %i) nounwind {
 ; CHECK-LABEL: ror_extract_shl:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    lsl x8, x0, #10
-; CHECK-NEXT:    bfxil x8, x0, #54, #7
-; CHECK-NEXT:    mov x0, x8
+; CHECK-NEXT:    lsl x8, x0, #3
+; CHECK-NEXT:    ror x0, x8, #57
 ; CHECK-NEXT:    ret
   %lhs_mul = shl i64 %i, 3
   %rhs_mul = shl i64 %i, 10
   %lhs_shift = lshr i64 %lhs_mul, 57
   %out = or i64 %lhs_shift, %rhs_mul
   ret i64 %out
 }
 
 define i32 @ror_extract_shrl(i32 %i) nounwind {
 ; CHECK-LABEL: ror_extract_shrl:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    ror w8, w0, #7
-; CHECK-NEXT:    and w0, w8, #0xf1ffffff
+; CHECK-NEXT:    lsr w8, w0, #3
+; CHECK-NEXT:    ror w0, w8, #4
 ; CHECK-NEXT:    ret
   %lhs_div = lshr i32 %i, 7
   %rhs_div = lshr i32 %i, 3
   %rhs_shift = shl i32 %rhs_div, 28
   %out = or i32 %lhs_div, %rhs_shift
   ret i32 %out
 }
 

 }
 
 define i64 @ror_extract_udiv(i64 %i) nounwind {
 ; CHECK-LABEL: ror_extract_udiv:
 ; CHECK:       // %bb.0:
 ; CHECK-NEXT:    mov x8, #-6148914691236517206
 ; CHECK-NEXT:    movk x8, #43691
 ; CHECK-NEXT:    umulh x8, x0, x8
-; CHECK-NEXT:    ror x8, x8, #5
-; CHECK-NEXT:    and x0, x8, #0xf7ffffffffffffff
+; CHECK-NEXT:    lsr x8, x8, #1
+; CHECK-NEXT:    ror x0, x8, #4
 ; CHECK-NEXT:    ret
   %lhs_div = udiv i64 %i, 3
   %rhs_div = udiv i64 %i, 48
   %lhs_shift = shl i64 %lhs_div, 60
   %out = or i64 %lhs_shift, %rhs_div
   ret i64 %out
 }
 
 define i64 @ror_extract_mul_with_mask(i64 %i) nounwind {
 ; CHECK-LABEL: ror_extract_mul_with_mask:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    add w8, w0, w0, lsl #3
-; CHECK-NEXT:    lsl w8, w8, #7
-; CHECK-NEXT:    add x9, x0, x0, lsl #3
-; CHECK-NEXT:    and x0, x8, #0x80
-; CHECK-NEXT:    bfxil x0, x9, #57, #7
+; CHECK-NEXT:    add x8, x0, x0, lsl #3
+; CHECK-NEXT:    ror x8, x8, #57
+; CHECK-NEXT:    and x0, x8, #0xff
 ; CHECK-NEXT:    ret
   %lhs_mul = mul i64 %i, 1152
   %rhs_mul = mul i64 %i, 9
   %lhs_and = and i64 %lhs_mul, 160
   %rhs_shift = lshr i64 %rhs_mul, 57
   %out = or i64 %lhs_and, %rhs_shift
   ret i64 %out
 }

llvm/trunk/test/CodeGen/X86/rotate-extract-vector.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i686-unknown -mattr=+avx512bw | FileCheck %s --check-prefixes=CHECK,X86
 ; RUN: llc < %s -mtriple=x86_64-unknown -mattr=+avx512bw | FileCheck %s --check-prefixes=CHECK,X64
 
 ; Check that under certain conditions we can factor out a rotate
 ; from the following idioms:
 ;   (a*c0) >> s1 | (a*c1)
 ;   (a/c0) << s1 | (a/c1)
 ; This targets cases where instcombine has folded a shl/srl/mul/udiv
 ; with one of the shifts from the rotate idiom
 
 define <4 x i32> @vroll_v4i32_extract_shl(<4 x i32> %i) {
 ; CHECK-LABEL: vroll_v4i32_extract_shl:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    vpslld $3, %xmm0, %xmm1
-; CHECK-NEXT:    vpslld $10, %xmm0, %xmm0
-; CHECK-NEXT:    vpsrld $25, %xmm1, %xmm1
-; CHECK-NEXT:    vpor %xmm0, %xmm1, %xmm0
+; CHECK-NEXT:    vpslld $3, %xmm0, %xmm0
+; CHECK-NEXT:    vprold $7, %zmm0, %zmm0
+; CHECK-NEXT:    # kill: def $xmm0 killed $xmm0 killed $zmm0
+; CHECK-NEXT:    vzeroupper
 ; CHECK-NEXT:    ret{{[l|q]}}
   %lhs_mul = shl <4 x i32> %i, <i32 3, i32 3, i32 3, i32 3>
   %rhs_mul = shl <4 x i32> %i, <i32 10, i32 10, i32 10, i32 10>
   %lhs_shift = lshr <4 x i32> %lhs_mul, <i32 25, i32 25, i32 25, i32 25>
   %out = or <4 x i32> %lhs_shift, %rhs_mul
   ret <4 x i32> %out
 }
 
 define <4 x i64> @vrolq_v4i64_extract_shrl(<4 x i64> %i) nounwind {
-; X86-LABEL: vrolq_v4i64_extract_shrl:
-; X86:       # %bb.0:
-; X86-NEXT:    # kill: def $ymm0 killed $ymm0 def $zmm0
-; X86-NEXT:    vprolq $24, %zmm0, %zmm0
-; X86-NEXT:    vpand {{\.LCPI.*}}, %ymm0, %ymm0
-; X86-NEXT:    retl
-;
-; X64-LABEL: vrolq_v4i64_extract_shrl:
-; X64:       # %bb.0:
-; X64-NEXT:    # kill: def $ymm0 killed $ymm0 def $zmm0
-; X64-NEXT:    vprolq $24, %zmm0, %zmm0
-; X64-NEXT:    vpbroadcastq {{.*#+}} ymm1 = [18446744073189457919,18446744073189457919,18446744073189457919,18446744073189457919]
-; X64-NEXT:    vpand %ymm1, %ymm0, %ymm0
-; X64-NEXT:    retq
+; CHECK-LABEL: vrolq_v4i64_extract_shrl:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    vpsrlq $5, %ymm0, %ymm0
+; CHECK-NEXT:    vprolq $29, %zmm0, %zmm0
+; CHECK-NEXT:    # kill: def $ymm0 killed $ymm0 killed $zmm0
+; CHECK-NEXT:    ret{{[l|q]}}
   %lhs_div = lshr <4 x i64> %i, <i64 40, i64 40, i64 40, i64 40>
   %rhs_div = lshr <4 x i64> %i, <i64 5, i64 5, i64 5, i64 5>
   %rhs_shift = shl <4 x i64> %rhs_div, <i64 29, i64 29, i64 29, i64 29>
   %out = or <4 x i64> %lhs_div, %rhs_shift
   ret <4 x i64> %out
 }
 
 define <8 x i32> @vroll_extract_mul(<8 x i32> %i) nounwind {
 ; CHECK-LABEL: vroll_extract_mul:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    vpbroadcastd {{.*#+}} ymm1 = [640,640,640,640,640,640,640,640]
-; CHECK-NEXT:    vpmulld %ymm1, %ymm0, %ymm1
-; CHECK-NEXT:    vpbroadcastd {{.*#+}} ymm2 = [10,10,10,10,10,10,10,10]
-; CHECK-NEXT:    vpmulld %ymm2, %ymm0, %ymm0
-; CHECK-NEXT:    vpsrld $26, %ymm0, %ymm0
-; CHECK-NEXT:    vpor %ymm0, %ymm1, %ymm0
+; CHECK-NEXT:    vpbroadcastd {{.*#+}} ymm1 = [10,10,10,10,10,10,10,10]
+; CHECK-NEXT:    vpmulld %ymm1, %ymm0, %ymm0
+; CHECK-NEXT:    vprold $6, %zmm0, %zmm0
+; CHECK-NEXT:    # kill: def $ymm0 killed $ymm0 killed $zmm0
 ; CHECK-NEXT:    ret{{[l|q]}}
   %lhs_mul = mul <8 x i32> %i, <i32 640, i32 640, i32 640, i32 640, i32 640, i32 640, i32 640, i32 640>
   %rhs_mul = mul <8 x i32> %i, <i32 10, i32 10, i32 10, i32 10, i32 10, i32 10, i32 10, i32 10>
   %rhs_shift = lshr <8 x i32> %rhs_mul, <i32 26, i32 26, i32 26, i32 26, i32 26, i32 26, i32 26, i32 26>
   %out = or <8 x i32> %lhs_mul, %rhs_shift
   ret <8 x i32> %out
 }
 
 define <2 x i64> @vrolq_extract_udiv(<2 x i64> %i) nounwind {
 ; X86-LABEL: vrolq_extract_udiv:
 ; X86:       # %bb.0:
-; X86-NEXT:    subl $60, %esp
+; X86-NEXT:    subl $44, %esp
 ; X86-NEXT:    vmovups %xmm0, {{[-0-9]+}}(%e{{[sb]}}p) # 16-byte Spill
 ; X86-NEXT:    vextractps $1, %xmm0, {{[0-9]+}}(%esp)
 ; X86-NEXT:    vmovss %xmm0, (%esp)
 ; X86-NEXT:    movl $0, {{[0-9]+}}(%esp)
 ; X86-NEXT:    movl $3, {{[0-9]+}}(%esp)
 ; X86-NEXT:    calll __udivdi3
 ; X86-NEXT:    vmovups {{[-0-9]+}}(%e{{[sb]}}p), %xmm0 # 16-byte Reload
 ; X86-NEXT:    vextractps $3, %xmm0, {{[0-9]+}}(%esp)
 ; X86-NEXT:    vextractps $2, %xmm0, (%esp)
 ; X86-NEXT:    movl $0, {{[0-9]+}}(%esp)
 ; X86-NEXT:    movl $3, {{[0-9]+}}(%esp)
 ; X86-NEXT:    vmovd %eax, %xmm0
 ; X86-NEXT:    vpinsrd $1, %edx, %xmm0, %xmm0
 ; X86-NEXT:    vmovdqu %xmm0, {{[-0-9]+}}(%e{{[sb]}}p) # 16-byte Spill
 ; X86-NEXT:    calll __udivdi3
 ; X86-NEXT:    vmovdqu {{[-0-9]+}}(%e{{[sb]}}p), %xmm0 # 16-byte Reload
 ; X86-NEXT:    vpinsrd $2, %eax, %xmm0, %xmm0
 ; X86-NEXT:    vpinsrd $3, %edx, %xmm0, %xmm0
-; X86-NEXT:    vmovdqu %xmm0, {{[-0-9]+}}(%e{{[sb]}}p) # 16-byte Spill
-; X86-NEXT:    vmovups {{[-0-9]+}}(%e{{[sb]}}p), %xmm0 # 16-byte Reload
-; X86-NEXT:    vextractps $1, %xmm0, {{[0-9]+}}(%esp)
-; X86-NEXT:    vmovss %xmm0, (%esp)
-; X86-NEXT:    movl $0, {{[0-9]+}}(%esp)
-; X86-NEXT:    movl $384, {{[0-9]+}}(%esp) # imm = 0x180
-; X86-NEXT:    calll __udivdi3
-; X86-NEXT:    vmovups {{[-0-9]+}}(%e{{[sb]}}p), %xmm0 # 16-byte Reload
-; X86-NEXT:    vextractps $3, %xmm0, {{[0-9]+}}(%esp)
-; X86-NEXT:    vextractps $2, %xmm0, (%esp)
-; X86-NEXT:    movl $0, {{[0-9]+}}(%esp)
-; X86-NEXT:    movl $384, {{[0-9]+}}(%esp) # imm = 0x180
-; X86-NEXT:    vmovd %eax, %xmm0
-; X86-NEXT:    vpinsrd $1, %edx, %xmm0, %xmm0
-; X86-NEXT:    vmovdqu %xmm0, {{[-0-9]+}}(%e{{[sb]}}p) # 16-byte Spill
-; X86-NEXT:    calll __udivdi3
-; X86-NEXT:    vmovdqu {{[-0-9]+}}(%e{{[sb]}}p), %xmm0 # 16-byte Reload
-; X86-NEXT:    vpinsrd $2, %eax, %xmm0, %xmm0
-; X86-NEXT:    vpinsrd $3, %edx, %xmm0, %xmm0
-; X86-NEXT:    vmovdqu {{[-0-9]+}}(%e{{[sb]}}p), %xmm1 # 16-byte Reload
-; X86-NEXT:    vpsllq $57, %xmm1, %xmm1
-; X86-NEXT:    vpor %xmm0, %xmm1, %xmm0
-; X86-NEXT:    addl $60, %esp
+; X86-NEXT:    vprolq $57, %zmm0, %zmm0
+; X86-NEXT:    # kill: def $xmm0 killed $xmm0 killed $zmm0
+; X86-NEXT:    addl $44, %esp
+; X86-NEXT:    vzeroupper
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: vrolq_extract_udiv:
 ; X64:       # %bb.0:
 ; X64-NEXT:    vpextrq $1, %xmm0, %rax
-; X64-NEXT:    movabsq $-6148914691236517205, %rsi # imm = 0xAAAAAAAAAAAAAAAB
-; X64-NEXT:    mulq %rsi
-; X64-NEXT:    movq %rdx, %rcx
-; X64-NEXT:    movq %rdx, %rax
-; X64-NEXT:    shrq %rax
-; X64-NEXT:    vmovq %rax, %xmm1
+; X64-NEXT:    movabsq $-6148914691236517205, %rcx # imm = 0xAAAAAAAAAAAAAAAB
+; X64-NEXT:    mulq %rcx
+; X64-NEXT:    shrq %rdx
+; X64-NEXT:    vmovq %rdx, %xmm1
 ; X64-NEXT:    vmovq %xmm0, %rax
-; X64-NEXT:    mulq %rsi
-; X64-NEXT:    movq %rdx, %rax
-; X64-NEXT:    shrq %rax
-; X64-NEXT:    vmovq %rax, %xmm0
+; X64-NEXT:    mulq %rcx
+; X64-NEXT:    shrq %rdx
+; X64-NEXT:    vmovq %rdx, %xmm0
 ; X64-NEXT:    vpunpcklqdq {{.*#+}} xmm0 = xmm0[0],xmm1[0]
-; X64-NEXT:    shrq $8, %rcx
-; X64-NEXT:    vmovq %rcx, %xmm1
-; X64-NEXT:    shrq $8, %rdx
-; X64-NEXT:    vmovq %rdx, %xmm2
-; X64-NEXT:    vpunpcklqdq {{.*#+}} xmm1 = xmm2[0],xmm1[0]
-; X64-NEXT:    vpsllq $57, %xmm0, %xmm0
-; X64-NEXT:    vpor %xmm1, %xmm0, %xmm0
+; X64-NEXT:    vprolq $57, %zmm0, %zmm0
+; X64-NEXT:    # kill: def $xmm0 killed $xmm0 killed $zmm0
+; X64-NEXT:    vzeroupper
 ; X64-NEXT:    retq
   %lhs_div = udiv <2 x i64> %i, <i64 3, i64 3>
   %rhs_div = udiv <2 x i64> %i, <i64 384, i64 384>
   %lhs_shift = shl <2 x i64> %lhs_div, <i64 57, i64 57>
   %out = or <2 x i64> %lhs_shift, %rhs_div
   ret <2 x i64> %out
 }
 
 define <4 x i32> @vrolw_extract_mul_with_mask(<4 x i32> %i) nounwind {
-; CHECK-LABEL: vrolw_extract_mul_with_mask:
-; CHECK:       # %bb.0:
-; CHECK-NEXT:    vpbroadcastd {{.*#+}} xmm1 = [1152,1152,1152,1152]
-; CHECK-NEXT:    vpmulld %xmm1, %xmm0, %xmm1
-; CHECK-NEXT:    vpbroadcastd {{.*#+}} xmm2 = [9,9,9,9]
-; CHECK-NEXT:    vpmulld %xmm2, %xmm0, %xmm0
-; CHECK-NEXT:    vpbroadcastd {{.*#+}} xmm2 = [160,160,160,160]
-; CHECK-NEXT:    vpand %xmm2, %xmm1, %xmm1
-; CHECK-NEXT:    vpsrld $25, %xmm0, %xmm0
-; CHECK-NEXT:    vpor %xmm0, %xmm1, %xmm0
-; CHECK-NEXT:    ret{{[l|q]}}
+; X86-LABEL: vrolw_extract_mul_with_mask:
+; X86:       # %bb.0:
+; X86-NEXT:    vpbroadcastd {{.*#+}} xmm1 = [9,9,9,9]
+; X86-NEXT:    vpmulld %xmm1, %xmm0, %xmm0
+; X86-NEXT:    vprold $7, %zmm0, %zmm0
+; X86-NEXT:    vpand {{\.LCPI.*}}, %xmm0, %xmm0
+; X86-NEXT:    vzeroupper
+; X86-NEXT:    retl
+;
+; X64-LABEL: vrolw_extract_mul_with_mask:
+; X64:       # %bb.0:
+; X64-NEXT:    vpbroadcastd {{.*#+}} xmm1 = [9,9,9,9]
+; X64-NEXT:    vpmulld %xmm1, %xmm0, %xmm0
+; X64-NEXT:    vprold $7, %zmm0, %zmm0
+; X64-NEXT:    vpand {{.*}}(%rip), %xmm0, %xmm0
+; X64-NEXT:    vzeroupper
+; X64-NEXT:    retq
   %lhs_mul = mul <4 x i32> %i, <i32 1152, i32 1152, i32 1152, i32 1152>
   %rhs_mul = mul <4 x i32> %i, <i32 9, i32 9, i32 9, i32 9>
   %lhs_and = and <4 x i32> %lhs_mul, <i32 160, i32 160, i32 160, i32 160>
   %rhs_shift = lshr <4 x i32> %rhs_mul, <i32 25, i32 25, i32 25, i32 25>
   %out = or <4 x i32> %lhs_and, %rhs_shift
   ret <4 x i32> %out
 }
 

llvm/trunk/test/CodeGen/X86/rotate-extract.ll

 ; X86-NEXT:    shll $10, %ecx
 ; X86-NEXT:    shrl $25, %eax
 ; X86-NEXT:    orl %ecx, %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: rolq_extract_shl:
 ; X64:       # %bb.0:
 ; X64-NEXT:    leaq (,%rdi,8), %rax
-; X64-NEXT:    shlq $10, %rdi
-; X64-NEXT:    shrq $57, %rax
-; X64-NEXT:    orq %rdi, %rax
+; X64-NEXT:    rolq $7, %rax
 ; X64-NEXT:    retq
   %lhs_mul = shl i64 %i, 3
   %rhs_mul = shl i64 %i, 10
   %lhs_shift = lshr i64 %lhs_mul, 57
   %out = or i64 %lhs_shift, %rhs_mul
   ret i64 %out
 }
 
 define i16 @rolw_extract_shrl(i16 %i) nounwind {
 ; X86-LABEL: rolw_extract_shrl:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movzwl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    rolw $9, %ax
-; X86-NEXT:    andl $61951, %eax # imm = 0xF1FF
+; X86-NEXT:    shrl $3, %eax
+; X86-NEXT:    rolw $12, %ax
 ; X86-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: rolw_extract_shrl:
 ; X64:       # %bb.0:
-; X64-NEXT:    rolw $9, %di
-; X64-NEXT:    andl $61951, %edi # imm = 0xF1FF
-; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    movzwl %di, %eax
+; X64-NEXT:    shrl $3, %eax
+; X64-NEXT:    rolw $12, %ax
+; X64-NEXT:    # kill: def $ax killed $ax killed $eax
 ; X64-NEXT:    retq
   %lhs_div = lshr i16 %i, 7
   %rhs_div = lshr i16 %i, 3
   %rhs_shift = shl i16 %rhs_div, 12
   %out = or i16 %lhs_div, %rhs_shift
   ret i16 %out
 }
 
 define i32 @roll_extract_mul(i32 %i) nounwind {
 ; X86-LABEL: roll_extract_mul:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    leal (%ecx,%ecx,8), %eax
-; X86-NEXT:    shll $7, %ecx
-; X86-NEXT:    leal (%ecx,%ecx,8), %ecx
-; X86-NEXT:    shrl $25, %eax
-; X86-NEXT:    orl %ecx, %eax
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    leal (%eax,%eax,8), %eax
+; X86-NEXT:    roll $7, %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: roll_extract_mul:
 ; X64:       # %bb.0:
 ; X64-NEXT:    # kill: def $edi killed $edi def $rdi
 ; X64-NEXT:    leal (%rdi,%rdi,8), %eax
-; X64-NEXT:    shll $7, %edi
-; X64-NEXT:    leal (%rdi,%rdi,8), %ecx
-; X64-NEXT:    shrl $25, %eax
-; X64-NEXT:    orl %ecx, %eax
+; X64-NEXT:    roll $7, %eax
 ; X64-NEXT:    retq
   %lhs_mul = mul i32 %i, 9
   %rhs_mul = mul i32 %i, 1152
   %lhs_shift = lshr i32 %lhs_mul, 25
   %out = or i32 %lhs_shift, %rhs_mul
   ret i32 %out
 }
 
 define i8 @rolb_extract_udiv(i8 %i) nounwind {
 ; X86-LABEL: rolb_extract_udiv:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    imull $171, %eax, %eax
-; X86-NEXT:    movb %ah, %cl
-; X86-NEXT:    shlb $3, %cl
-; X86-NEXT:    andb $-16, %cl
-; X86-NEXT:    shrl $13, %eax
-; X86-NEXT:    orb %cl, %al
+; X86-NEXT:    shrl $9, %eax
+; X86-NEXT:    rolb $4, %al
 ; X86-NEXT:    # kill: def $al killed $al killed $eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: rolb_extract_udiv:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movzbl %dil, %eax
 ; X64-NEXT:    imull $171, %eax, %eax
-; X64-NEXT:    movl %eax, %ecx
-; X64-NEXT:    shrl $8, %ecx
-; X64-NEXT:    shlb $3, %cl
-; X64-NEXT:    andb $-16, %cl
-; X64-NEXT:    shrl $13, %eax
-; X64-NEXT:    orb %cl, %al
+; X64-NEXT:    shrl $9, %eax
+; X64-NEXT:    rolb $4, %al
 ; X64-NEXT:    # kill: def $al killed $al killed $eax
 ; X64-NEXT:    retq
   %lhs_div = udiv i8 %i, 3
   %rhs_div = udiv i8 %i, 48
   %lhs_shift = shl i8 %lhs_div, 4
   %out = or i8 %lhs_shift, %rhs_div
   ret i8 %out
 }

 ; X86-NEXT:    orl %ecx, %eax
 ; X86-NEXT:    xorl %edx, %edx
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: rolq_extract_mul_with_mask:
 ; X64:       # %bb.0:
 ; X64-NEXT:    leaq (%rdi,%rdi,8), %rax
-; X64-NEXT:    # kill: def $edi killed $edi killed $rdi def $rdi
-; X64-NEXT:    shll $7, %edi
-; X64-NEXT:    leal (%rdi,%rdi,8), %ecx
-; X64-NEXT:    movzbl %cl, %ecx
-; X64-NEXT:    shrq $57, %rax
-; X64-NEXT:    orq %rcx, %rax
+; X64-NEXT:    rolq $7, %rax
+; X64-NEXT:    movzbl %al, %eax
 ; X64-NEXT:    retq
   %lhs_mul = mul i64 %i, 1152
   %rhs_mul = mul i64 %i, 9
   %lhs_and = and i64 %lhs_mul, 160
   %rhs_shift = lshr i64 %rhs_mul, 57
   %out = or i64 %lhs_and, %rhs_shift
   ret i64 %out
 }