[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

5292–5303

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

2

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

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5297–5301

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

5292–5303

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

5297–5301

Updated with some clarifying comments

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5258

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

3

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

5258

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

4977–4978

You can merge these if statements:

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

4988

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

5000

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

5008

Do we have any tests that use the Mask?

5036

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.

5043

Is this better?

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

5059

Worth doing this earlier?

5316

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

486

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

5008

Added a mask test

5036

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

5005–5015

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,

5016–5017

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

5005–5015

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

5005–5015

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

5037–5050

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..

5059

+1 this should be done right ExtractFrom is modified.

5069–5071

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

[RKSimon]

test/CodeGen/X86/rotate-extract.ll

11

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

Nit: unneeded {}

5037–5039

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

5059

Not done.

5069–5071

I didn't receive a reply here

5080

bitwidth

5292–5294

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.

test/CodeGen/X86/rotate-extract.ll

83

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

AArch64 doesn't have a rol instruction.

[sameconrad]

Address comments

[sameconrad]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

5016–5017

This is mentioned in the comments I added in MatchRotate

5037–5039

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.

5059

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

5069–5071

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.

5292–5294

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

test/CodeGen/X86/rotate-extract.ll

83

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

5052

(style) full stops at the end of comments.

5066

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

5266

@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.

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;
 
       MemOpLink(LSBaseSDNode *N, int64_t Offset)
           : MemNode(N), OffsetFromBase(Offset) {}
     };
 
SDValue DAGCombiner::visitOR(SDNode *N) {
   }
 
   // Simplify: (or (op x...), (op y...))  -> (op (or x, y))
   if (N0.getOpcode() == N1.getOpcode())
     if (SDValue Tmp = SimplifyBinOpWithSameOpcodeHands(N))
       return Tmp;
 
   // See if this is some rotate idiom.
-  if (SDNode *Rot = MatchRotate(N0, N1, SDLoc(N)))
+  if (SDNode *Rot = MatchRotate(N0, N1, SDLoc(N))) {
     return SDValue(Rot, 0);
+  }
 
   if (SDValue Load = MatchLoadCombine(N))
     return Load;
 
   // 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");
+
+  // Preconditions:
+  //
+  //    (or (op0 v c0) (shiftl/r (op0 v c1) c2))
+  //
+  // op0 must be the same opcode on both sides and the same value type
+  ExtractFrom = stripConstantMask(DAG, ExtractFrom, Mask);
+  SDValue OppShiftLHS = OppShift.getOperand(0);
+  EVT ShiftedVT = OppShiftLHS.getValueType();
+  if (OppShiftLHS.getOpcode() != ExtractFrom.getOpcode() ||
+      ShiftedVT != ExtractFrom.getValueType())
+    return SDValue();
+
+  // 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;
+  };
+  bool GotOpcode =
+      ((OppShift.getOpcode() == ISD::SRL && SelectOpcode(ISD::SHL, ISD::MUL)) ||
+       (OppShift.getOpcode() == ISD::SHL && SelectOpcode(ISD::SRL, ISD::UDIV)));
+  // op0 must be either the needed shift opcode or the mul/udiv equivalent that
+  // the needed shift can be extracted from. Both cases must have v as the LHS
+  // input.
+  if (!GotOpcode || OppShiftLHS.getOperand(0) != ExtractFrom.getOperand(0))
+    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));
+  // 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 bitwdith 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))
 //
 // reduces to a rotate in direction shift2 by Pos or (equivalently) a rotate
 // in direction shift1 by Neg.  The range [0, EltSize) means that we only need
SDNode *DAGCombiner::MatchRotatePosNeg(SDValue Shifted, SDValue Pos,
   }
 
   return nullptr;
 }
 
 // MatchRotate - Handle an 'or' of two operands.  If this is one of the many
 // idioms for rotate, and if the target supports rotation instructions, generate
 // a rot[lr].
 SDNode *DAGCombiner::MatchRotate(SDValue LHS, SDValue RHS, const SDLoc &DL) {
   // Must be a legal type.  Expanded 'n promoted things won't work with rotates.
   EVT VT = LHS.getValueType();
   if (!TLI.isTypeLegal(VT)) return nullptr;
 
   // The target must have at least one rotate flavor.
   bool HasROTL = hasOperation(ISD::ROTL, VT);
   bool HasROTR = hasOperation(ISD::ROTR, VT);
   if (!HasROTL && !HasROTR) return nullptr;
 
   // Check for truncated rotate.
   if (LHS.getOpcode() == ISD::TRUNCATE && RHS.getOpcode() == ISD::TRUNCATE &&
       LHS.getOperand(0).getValueType() == RHS.getOperand(0).getValueType()) {
     assert(LHS.getValueType() == RHS.getValueType());
     if (SDNode *Rot = MatchRotate(LHS.getOperand(0), RHS.getOperand(0), DL)) {
       return DAG.getNode(ISD::TRUNCATE, SDLoc(LHS), LHS.getValueType(),
                          SDValue(Rot, 0)).getNode();
     }
   }
 
+  bool NeedRotLHS = true;
+  bool NeedRotRHS = true;
+
   // 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.
+  if (matchRotateHalf(DAG, LHS, LHSShift, LHSMask))
+    NeedRotLHS = false;
 
   SDValue RHSShift;   // The shift.
   SDValue RHSMask;    // AND value if any.
-  if (!MatchRotateHalf(RHS, RHSShift, RHSMask))
-    return nullptr; // Not part of a rotate.
+  if (matchRotateHalf(DAG, RHS, RHSShift, RHSMask))
+    NeedRotRHS = false;
+
+  // If neither side matched a rotate half, bail
+  if (NeedRotLHS && NeedRotRHS)
+    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 (!NeedRotLHS)
+    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 (!NeedRotRHS)
+    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) {

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, #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:    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 i32 @ror_extract_mul(i32 %i) nounwind {
+; CHECK-LABEL: ror_extract_mul:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    add w8, w0, w0, lsl #3
+; CHECK-NEXT:    ror w0, w8, #25
+; CHECK-NEXT:    ret
+  %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 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:    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 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
+}
+
+; Result would undershift
+define i64 @no_extract_shl(i64 %i) nounwind {
+; CHECK-LABEL: no_extract_shl:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    lsl x8, x0, #10
+; CHECK-NEXT:    bfxil x8, x0, #52, #7
+; CHECK-NEXT:    mov x0, x8
+; CHECK-NEXT:    ret
+  %lhs_mul = shl i64 %i, 5
+  %rhs_mul = shl i64 %i, 10
+  %lhs_shift = lshr i64 %lhs_mul, 57
+  %out = or i64 %lhs_shift, %rhs_mul
+  ret i64 %out
+}
+
+; Result would overshift
+define i32 @no_extract_shrl(i32 %i) nounwind {
+; CHECK-LABEL: no_extract_shrl:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    lsr w8, w0, #3
+; CHECK-NEXT:    lsr w0, w0, #9
+; CHECK-NEXT:    bfi w0, w8, #28, #4
+; CHECK-NEXT:    ret
+  %lhs_div = lshr i32 %i, 3
+  %rhs_div = lshr i32 %i, 9
+  %lhs_shift = shl i32 %lhs_div, 28
+  %out = or i32 %lhs_shift, %rhs_div
+  ret i32 %out
+}
+
+; Can factor 128 from 2304, but result is 18 instead of 9
+define i64 @no_extract_mul(i64 %i) nounwind {
+; CHECK-LABEL: no_extract_mul:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    add x8, x0, x0, lsl #3
+; CHECK-NEXT:    lsr x0, x8, #57
+; CHECK-NEXT:    bfi x0, x8, #8, #56
+; CHECK-NEXT:    ret
+  %lhs_mul = mul i64 %i, 2304
+  %rhs_mul = mul i64 %i, 9
+  %rhs_shift = lshr i64 %rhs_mul, 57
+  %out = or i64 %lhs_mul, %rhs_shift
+  ret i64 %out
+}
+
+; Can't evenly factor 16 from 49
+define i32 @no_extract_udiv(i32 %i) nounwind {
+; CHECK-LABEL: no_extract_udiv:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    mov w8, #43691
+; CHECK-NEXT:    mov w9, #33437
+; CHECK-NEXT:    movk w8, #43690, lsl #16
+; CHECK-NEXT:    movk w9, #21399, lsl #16
+; CHECK-NEXT:    umull x8, w0, w8
+; CHECK-NEXT:    umull x9, w0, w9
+; CHECK-NEXT:    lsr x8, x8, #33
+; CHECK-NEXT:    lsr x9, x9, #32
+; CHECK-NEXT:    extr w0, w8, w9, #4
+; CHECK-NEXT:    ret
+  %lhs_div = udiv i32 %i, 3
+  %rhs_div = udiv i32 %i, 49
+  %lhs_shift = shl i32 %lhs_div, 28
+  %out = or i32 %lhs_shift, %rhs_div
+  ret i32 %out
+}

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

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=x86_64-unknown -mattr=+avx512bw | 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 <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, %xmm0
+; CHECK-NEXT:    vprold $7, %zmm0, %zmm0
+; CHECK-NEXT:    # kill: def $xmm0 killed $xmm0 killed $zmm0
+; CHECK-NEXT:    vzeroupper
+; CHECK-NEXT:    retq
+  %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 {
+; 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:    retq
+  %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 = [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:    retq
+  %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 {
+; CHECK-LABEL: vrolq_extract_udiv:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    vpextrq $1, %xmm0, %rax
+; CHECK-NEXT:    movabsq $-6148914691236517205, %rcx # imm = 0xAAAAAAAAAAAAAAAB
+; CHECK-NEXT:    mulq %rcx
+; CHECK-NEXT:    shrq %rdx
+; CHECK-NEXT:    vmovq %rdx, %xmm1
+; CHECK-NEXT:    vmovq %xmm0, %rax
+; CHECK-NEXT:    mulq %rcx
+; CHECK-NEXT:    shrq %rdx
+; CHECK-NEXT:    vmovq %rdx, %xmm0
+; CHECK-NEXT:    vpunpcklqdq {{.*#+}} xmm0 = xmm0[0],xmm1[0]
+; CHECK-NEXT:    vprolq $57, %zmm0, %zmm0
+; CHECK-NEXT:    # kill: def $xmm0 killed $xmm0 killed $zmm0
+; CHECK-NEXT:    vzeroupper
+; CHECK-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 = [9,9,9,9]
+; CHECK-NEXT:    vpmulld %xmm1, %xmm0, %xmm0
+; CHECK-NEXT:    vprold $7, %zmm0, %zmm0
+; CHECK-NEXT:    vpand {{.*}}(%rip), %xmm0, %xmm0
+; CHECK-NEXT:    vzeroupper
+; CHECK-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
+}
+
+define <32 x i16> @illegal_no_extract_mul(<32 x i16> %i) nounwind {
+; CHECK-LABEL: illegal_no_extract_mul:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    vpmullw {{.*}}(%rip), %zmm0, %zmm1
+; CHECK-NEXT:    vpmullw {{.*}}(%rip), %zmm0, %zmm0
+; CHECK-NEXT:    vpsrlw $10, %zmm0, %zmm0
+; CHECK-NEXT:    vporq %zmm0, %zmm1, %zmm0
+; CHECK-NEXT:    retq
+  %lhs_mul = mul <32 x i16> %i, <i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640, i16 640>
+  %rhs_mul = mul <32 x i16> %i, <i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10>
+  %rhs_shift = lshr <32 x i16> %rhs_mul, <i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10, i16 10>
+  %out = or <32 x i16> %lhs_mul, %rhs_shift
+  ret <32 x i16> %out
+}
+
+; Result would undershift
+define <4 x i64> @no_extract_shl(<4 x i64> %i) nounwind {
+; CHECK-LABEL: no_extract_shl:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    vpsllq $11, %ymm0, %ymm1
+; CHECK-NEXT:    vpsllq $24, %ymm0, %ymm0
+; CHECK-NEXT:    vpsrlq $50, %ymm1, %ymm1
+; CHECK-NEXT:    vpor %ymm0, %ymm1, %ymm0
+; CHECK-NEXT:    retq
+  %lhs_mul = shl <4 x i64> %i, <i64 11, i64 11, i64 11, i64 11>
+  %rhs_mul = shl <4 x i64> %i, <i64 24, i64 24, i64 24, i64 24>
+  %lhs_shift = lshr <4 x i64> %lhs_mul, <i64 50, i64 50, i64 50, i64 50>
+  %out = or <4 x i64> %lhs_shift, %rhs_mul
+  ret <4 x i64> %out
+}
+
+; Result would overshift
+define <4 x i32> @no_extract_shrl(<4 x i32> %i) nounwind {
+; CHECK-LABEL: no_extract_shrl:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    vpbroadcastd {{.*#+}} xmm1 = [4026531840,4026531840,4026531840,4026531840]
+; CHECK-NEXT:    vpslld $25, %xmm0, %xmm2
+; CHECK-NEXT:    vpand %xmm1, %xmm2, %xmm1
+; CHECK-NEXT:    vpsrld $9, %xmm0, %xmm0
+; CHECK-NEXT:    vpor %xmm0, %xmm1, %xmm0
+; CHECK-NEXT:    retq
+  %lhs_div = lshr <4 x i32> %i, <i32 3, i32 3, i32 3, i32 3>
+  %rhs_div = lshr <4 x i32> %i, <i32 9, i32 9, i32 9, i32 9>
+  %lhs_shift = shl <4 x i32> %lhs_div, <i32 28, i32 28, i32 28, i32 28>
+  %out = or <4 x i32> %lhs_shift, %rhs_div
+  ret <4 x i32> %out
+}
+
+; Can factor 512 from 1536, but result is 3 instead of 9
+define <8 x i32> @no_extract_mul(<8 x i32> %i) nounwind {
+; CHECK-LABEL: no_extract_mul:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    vpbroadcastd {{.*#+}} ymm1 = [1536,1536,1536,1536,1536,1536,1536,1536]
+; CHECK-NEXT:    vpmulld %ymm1, %ymm0, %ymm1
+; CHECK-NEXT:    vpbroadcastd {{.*#+}} ymm2 = [9,9,9,9,9,9,9,9]
+; CHECK-NEXT:    vpmulld %ymm2, %ymm0, %ymm0
+; CHECK-NEXT:    vpsrld $23, %ymm0, %ymm0
+; CHECK-NEXT:    vpor %ymm0, %ymm1, %ymm0
+; CHECK-NEXT:    retq
+  %lhs_mul = mul <8 x i32> %i, <i32 1536, i32 1536, i32 1536, i32 1536, i32 1536, i32 1536, i32 1536, i32 1536>
+  %rhs_mul = mul <8 x i32> %i, <i32 9, i32 9, i32 9, i32 9, i32 9, i32 9, i32 9, i32 9>
+  %rhs_shift = lshr <8 x i32> %rhs_mul, <i32 23, i32 23, i32 23, i32 23, i32 23, i32 23, i32 23, i32 23>
+  %out = or <8 x i32> %lhs_mul, %rhs_shift
+  ret <8 x i32> %out
+}
+
+; Can't evenly factor 256 from 770
+define <2 x i64> @no_extract_udiv(<2 x i64> %i) nounwind {
+; CHECK-LABEL: no_extract_udiv:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    vpextrq $1, %xmm0, %rcx
+; CHECK-NEXT:    movabsq $-6148914691236517205, %rdi # imm = 0xAAAAAAAAAAAAAAAB
+; CHECK-NEXT:    movq %rcx, %rax
+; CHECK-NEXT:    mulq %rdi
+; CHECK-NEXT:    shrq %rdx
+; CHECK-NEXT:    vmovq %rdx, %xmm1
+; CHECK-NEXT:    vmovq %xmm0, %rsi
+; CHECK-NEXT:    movq %rsi, %rax
+; CHECK-NEXT:    mulq %rdi
+; CHECK-NEXT:    shrq %rdx
+; CHECK-NEXT:    vmovq %rdx, %xmm0
+; CHECK-NEXT:    vpunpcklqdq {{.*#+}} xmm0 = xmm0[0],xmm1[0]
+; CHECK-NEXT:    movabsq $-6180857105216966645, %rdi # imm = 0xAA392F35DC17F00B
+; CHECK-NEXT:    movq %rcx, %rax
+; CHECK-NEXT:    mulq %rdi
+; CHECK-NEXT:    shrq $9, %rdx
+; CHECK-NEXT:    vmovq %rdx, %xmm1
+; CHECK-NEXT:    movq %rsi, %rax
+; CHECK-NEXT:    mulq %rdi
+; CHECK-NEXT:    shrq $9, %rdx
+; CHECK-NEXT:    vmovq %rdx, %xmm2
+; CHECK-NEXT:    vpunpcklqdq {{.*#+}} xmm1 = xmm2[0],xmm1[0]
+; CHECK-NEXT:    vpsllq $56, %xmm0, %xmm0
+; CHECK-NEXT:    vpor %xmm1, %xmm0, %xmm0
+; CHECK-NEXT:    retq
+  %lhs_div = udiv <2 x i64> %i, <i64 3, i64 3>
+  %rhs_div = udiv <2 x i64> %i, <i64 770, i64 770>
+  %lhs_shift = shl <2 x i64> %lhs_div, <i64 56, i64 56>
+  %out = or <2 x i64> %lhs_shift, %rhs_div
+  ret <2 x i64> %out
+}

test/CodeGen/X86/rotate-extract.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=x86_64-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 @rolq_extract_shl(i64 %i) nounwind {
+; CHECK-LABEL: rolq_extract_shl:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    leaq (,%rdi,8), %rax
+; CHECK-NEXT:    rolq $7, %rax
+; CHECK-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 {
+; CHECK-LABEL: rolw_extract_shrl:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movzwl %di, %eax
+; CHECK-NEXT:    shrl $3, %eax
+; CHECK-NEXT:    rolw $12, %ax
+; CHECK-NEXT:    # kill: def $ax killed $ax killed $eax
+; CHECK-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 {
+; CHECK-LABEL: roll_extract_mul:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
+; CHECK-NEXT:    leal (%rdi,%rdi,8), %eax
+; CHECK-NEXT:    roll $7, %eax
+; CHECK-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 {
+; CHECK-LABEL: rolb_extract_udiv:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movzbl %dil, %eax
+; CHECK-NEXT:    imull $171, %eax, %eax
+; CHECK-NEXT:    shrl $9, %eax
+; CHECK-NEXT:    rolb $4, %al
+; CHECK-NEXT:    # kill: def $al killed $al killed $eax
+; CHECK-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
+}
+
+define i64 @rolq_extract_mul_with_mask(i64 %i) nounwind {
+; CHECK-LABEL: rolq_extract_mul_with_mask:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    leaq (%rdi,%rdi,8), %rax
+; CHECK-NEXT:    rolq $7, %rax
+; CHECK-NEXT:    movzbl %al, %eax
+; CHECK-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
+}
+
+; Result would undershift
+define i64 @no_extract_shl(i64 %i) nounwind {
+; CHECK-LABEL: no_extract_shl:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    shlq $5, %rax
+; CHECK-NEXT:    shlq $10, %rdi
+; CHECK-NEXT:    shrq $57, %rax
+; CHECK-NEXT:    leaq (%rax,%rdi), %rax
+; CHECK-NEXT:    retq
+  %lhs_mul = shl i64 %i, 5
+  %rhs_mul = shl i64 %i, 10
+  %lhs_shift = lshr i64 %lhs_mul, 57
+  %out = or i64 %lhs_shift, %rhs_mul
+  ret i64 %out
+}
+
+; Result would overshift
+define i32 @no_extract_shrl(i32 %i) nounwind {
+; CHECK-LABEL: no_extract_shrl:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
+; CHECK-NEXT:    movl %edi, %eax
+; CHECK-NEXT:    andl $-8, %eax
+; CHECK-NEXT:    shll $25, %eax
+; CHECK-NEXT:    shrl $9, %edi
+; CHECK-NEXT:    leal (%rdi,%rax), %eax
+; CHECK-NEXT:    retq
+  %lhs_div = lshr i32 %i, 3
+  %rhs_div = lshr i32 %i, 9
+  %lhs_shift = shl i32 %lhs_div, 28
+  %out = or i32 %lhs_shift, %rhs_div
+  ret i32 %out
+}
+
+; Can factor 128 from 2304, but result is 18 instead of 9
+define i16 @no_extract_mul(i16 %i) nounwind {
+; CHECK-LABEL: no_extract_mul:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
+; CHECK-NEXT:    leal (%rdi,%rdi,8), %eax
+; CHECK-NEXT:    # kill: def $edi killed $edi killed $rdi def $rdi
+; CHECK-NEXT:    shll $8, %edi
+; CHECK-NEXT:    leal (%rdi,%rdi,8), %ecx
+; CHECK-NEXT:    movzwl %ax, %eax
+; CHECK-NEXT:    shrl $9, %eax
+; CHECK-NEXT:    orl %ecx, %eax
+; CHECK-NEXT:    # kill: def $ax killed $ax killed $eax
+; CHECK-NEXT:    retq
+  %lhs_mul = mul i16 %i, 2304
+  %rhs_mul = mul i16 %i, 9
+  %rhs_shift = lshr i16 %rhs_mul, 9
+  %out = or i16 %lhs_mul, %rhs_shift
+  ret i16 %out
+}
+
+; Can't evenly factor 16 from 49
+define i8 @no_extract_udiv(i8 %i) nounwind {
+; CHECK-LABEL: no_extract_udiv:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movzbl %dil, %eax
+; CHECK-NEXT:    imull $171, %eax, %ecx
+; CHECK-NEXT:    shrl $8, %ecx
+; CHECK-NEXT:    shlb $3, %cl
+; CHECK-NEXT:    andb $-16, %cl
+; CHECK-NEXT:    imull $79, %eax, %edx
+; CHECK-NEXT:    shrl $8, %edx
+; CHECK-NEXT:    subb %dl, %al
+; CHECK-NEXT:    shrb %al
+; CHECK-NEXT:    addb %dl, %al
+; CHECK-NEXT:    shrb $5, %al
+; CHECK-NEXT:    orb %cl, %al
+; CHECK-NEXT:    # kill: def $al killed $al killed $eax
+; CHECK-NEXT:    retq
+  %lhs_div = udiv i8 %i, 3
+  %rhs_div = udiv i8 %i, 49
+  %lhs_shift = shl i8 %lhs_div,4
+  %out = or i8 %lhs_shift, %rhs_div
+  ret i8 %out
+}