[ARM][CodeGen] Add support for complex deinterleaving

[NickGuy]

Summary

Adds the Complex Deinterleaving Pass implementing support for complex numbers in a target-independent manner, deferring to the TargetLowering for the given target to create a target-specific intrinsic.

[huntergr]

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

483

I can't find any place where rotations are dealt with besides assignment and equality checks of 0,90,180,270 -- might an enum be preferable? Or do you anticipate doing arithmetic with them in a follow-up patch?

691

I think it would be worthwhile to add a comment about what the interleaving represents -- that you're looking for a shuffle that takes separate vectors of real and imaginary parts and combines them before they are stored to memory (or returned in registers), and that this is just for matching per-lane operations instead of cross-lane (like a reduction).

Or at least that's the behaviour I've observed when testing your patch with a loop like the following:

#define LEN (512)
float _Complex a[ LEN ];
float _Complex b[ LEN ];
float _Complex c[ LEN ];

void foo (void) {
#pragma clang loop vectorize(enable)
  for (int i = 0; i < LEN; ++i)
    a[i] = b[i] * c[i];
}

[NickGuy]

Since the last patch, I've redesigned the high-level approach; It now crawls through the instruction graph to find opportunities for complex deinterleaving before attempting to perform said deinterleaving. Doing it this way allows us to short-circuit, bailing out and preventing the heavy work from being performed if something isn't supported.
This iteration also implements support for complex operations with multiple steps/operands (e.g. a[i] * b[i] * c[i])

[dmgreen]

I haven't really looked to deeply into the meat of the pass yet - how it does the matching - but I had a chunk of comments for the rest.

What happened to the ideas of starting from a shuffle and working through a worklist of pairs of [Real, Imaginary] Values that we match to complex nodes? It would build up a graph of complex nodes to replace the original shuffle, providing that the leaves were all valid de-interleavings. At least on paper I feel we should just be able to perform the search without looking though a lot of uses (except for checking there are no extra uses, of course), and all the Unmatched instructions and what looks like matching of random unrelated snippets would be cleaned up.

llvm/lib/CodeGen/CMakeLists.txt

46

Formatting is off here

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

2–3

This looks like it got formatted incorrectly.

100

item -> Item

101

i -> I (or a better name, if I is already used)

150

Reciprocal Throughput is more common.

512

evaluateComplexDeinterleavingBasicBlock -> evaluateBasicBlock

992–993

It is better to structure things in a way where we decide whether to do something, then do it. Not get half way through doing it and decide we didn't want to in the end. In what ways would we expect createComplexDeinterleavingIR to return nullptr at the moment?

1018

Is this cost necessary at the moment, or will it always be profitable for the simple cases?

llvm/lib/Target/ARM/ARMISelLowering.cpp

21844–21848

Things like this can be a single if:

if (!VTy || VTy->getNumElements() * VTy->getScalarSizeInBits() != 128)
    return false;

I presume the == 128 can be removed if we teach it how to split the vectors up?

21879

Can this be an assert instead.

llvm/lib/Target/ARM/ARMTargetMachine.cpp

437

This doesn't need to add the new brackets.

llvm/test/CodeGen/ARM/ComplexArithmetic/complex-arithmetic-f32-mul.ll

32 ↗

(On Diff #421520)

Add arm_aapcs_vfpcc to any tests that take or return vectors.
I think you can remove #0 too.

llvm/test/CodeGen/ARM/ComplexArithmetic/complex-arithmetic-f64-mul.ll

2 ↗

(On Diff #438664)

It might be a little cleaner to add +fp64 for all these f64 tests.

llvm/test/CodeGen/ARM/ComplexArithmetic/complex-arithmetic-rotations-add.ll

1 ↗

(On Diff #421520)

MVE tests can go into llvm/test/CodeGen/Thumb2/mve-complex-xyz.ll. So long as they are all updated by the test script, that should be fine to keep them with the rest.

[NickGuy]

In D114174#3601236, @dmgreen wrote:

What happened to the ideas of starting from a shuffle and working through a worklist of pairs of [Real, Imaginary] Values that we match to complex nodes?

While that would work "simply" enough for cases like a * b, more elaborate cases (e.g. (a * b) * c) would result in some ambiguity as to which add(mul, mul) pairs with which sub(mul, mul). This complexity inflates further the more operands are involved. The approach I've implemented here considers each complex node in isolation (with the exception of the accumulator value).

I presume the == 128 can be removed if we teach it how to split the vectors up?I presume the == 128 can be removed if we teach it how to split the vectors up?

Yep, vector splitting is something I decided to push out of this initial patch, and will be implemented in a follow-up. (Due to each node being treated in isolation, the vector splitting from previous iterations got overly complicated and unwieldy). The ideal solution that I can see would be to teach the intrinsic how to split, rather than the pass (somewhere like DAGTypeLegalizer::SplitVectorResult).

Is this cost necessary at the moment, or will it always be profitable for the simple cases?

Complex add has a few cases where I've observed performance regressions, and that's the sort of thing this rudimentary cost-modelling is intended to catch.

Remaining comments will be addressed in a follow-up patch.

[chill]

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

137

Here and elsewhere std::find -> llvm::find

594

Why are we scanning the whole block?
It looks to me (admittedly I don't understand what this pass does yet)
we can just walk over the Instructions vector (in reverse, if the order matters),
avoiding the quadratic complexity.

634

Here and in a few other places for (Value *V : Op0->operands()) {

[chill]

Do we have some broad overview of the approach and the algorithm? It'd be a good idea put something like this in the description and eventually the commit message. (I searched for LLVM complex RFCs, buy couldn't find anything useful).

[chill]

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

326

return std::make_shared<ComplexDeinterleavingCompositeNode>(Operation);

562

These could be, e.g.:

static const int RealMask[] = {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30};
auto RealMaskRef = ArrayRef<int>(RealMask, ShufleMask.size());

with an assertion/bounds check. Good enough for 512-bit vectors with 16-bit elements, can be extended.

llvm/test/CodeGen/ARM/ComplexArithmetic/complex-arithmetic-f32-add.ll

99 ↗

(On Diff #438664)

Shouldn't these be translated to a couple of vcadd.f32 instructions, like in the previous test?
And this amount of move instructions seems excessive.

[chill]

llvm/test/CodeGen/ARM/ComplexArithmetic/complex-arithmetic-f32-add.ll

99 ↗

(On Diff #438664)

And this amount of move instructions seems excessive.

I guess MVE does not have sensible swizzling instructions.

[dmgreen]

In D114174#3601263, @NickGuy wrote:

In D114174#3601236, @dmgreen wrote:

What happened to the ideas of starting from a shuffle and working through a worklist of pairs of [Real, Imaginary] Values that we match to complex nodes?

While that would work "simply" enough for cases like a * b, more elaborate cases (e.g. (a * b) * c) would result in some ambiguity as to which add(mul, mul) pairs with which sub(mul, mul). This complexity inflates further the more operands are involved. The approach I've implemented here considers each complex node in isolation (with the exception of the accumulator value).

Hmm, OK. I was thinking about a three way multiply when looking at that way of structuring the pass, but only one pattern and only ever on paper. I was worried that there were cases where it was ambiguous, but figured if it was it could always just try both possibilities. But I've not implemented it, it just sounded like an elegant way of treating this like slightly more complex pattern matcher, as opposed to all this findUnmatchedInstructions and looking through uses.

A broad overview of the algorithm would be useful, like Momchil mentioned, perhaps in the file description. I was trying to make a sketch before but got a bit lost in nested loops.

I presume the == 128 can be removed if we teach it how to split the vectors up?I presume the == 128 can be removed if we teach it how to split the vectors up?

Yep, vector splitting is something I decided to push out of this initial patch, and will be implemented in a follow-up. (Due to each node being treated in isolation, the vector splitting from previous iterations got overly complicated and unwieldy). The ideal solution that I can see would be to teach the intrinsic how to split, rather than the pass (somewhere like DAGTypeLegalizer::SplitVectorResult).

A separate addition sounds good. Lets try and get something that we happy with and extend it out.

Is this cost necessary at the moment, or will it always be profitable for the simple cases?

Complex add has a few cases where I've observed performance regressions, and that's the sort of thing this rudimentary cost-modelling is intended to catch.

Do you have a test-case where this happens? Cost modelling will probably be good to add in the long run, I'd just like to understand where it currently can make things worse.

llvm/test/CodeGen/ARM/ComplexArithmetic/complex-arithmetic-f32-add.ll

99 ↗

(On Diff #438664)

Yeah this is expected from shuffles that MVE cannot handle very well. It would look a lot better either with loads that could become interleaving loads, or under AArch64 where better shuffles are available.

[NickGuy]

Addressed comments, and added a file description that attempts to explain what the pass does.

[NickGuy]

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

594

The order of the CompositeNodes is important, this was a holdover from before we were sorting the nodes.

llvm/test/CodeGen/ARM/ComplexArithmetic/complex-arithmetic-f32-add.ll

99 ↗

(On Diff #438664)

Shouldn't these be translated to a couple of vcadd.f32 instructions, like in the previous test?

Not in this case, no. The IR vectors are too wide to fit into actual vector registers, and the follow-up vector splitting patch (D129067) is restricted to splitting in half.

[dmgreen]

Some of the comments looked like they didn't get resolved, and the latest version is missing context.

It would be good to get to the point where the tests are in a good place and we can commit those, allowing us to just show just the differences here. They need to be in the right place first though.

[NickGuy]

I've pre-committed the tests, and redesigned the core algorthm to operate on pairs of operands, rather than analysing the uses of a given instruction. The vector splitting has also been implemented on the target side

[dmgreen]

The tests are good, but they currently only cover each of the types for vcadd and vcmla0/90. I think we need more to show all the edgecases that should or should not be matched. They are not needed for all types, but we should try and make examples of each.

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

163

ConvergingI is the Root of the graph? Perhaps just call it RootValue.

529

What if the operands are FMul(A, A) and FMul (B, C)?
I think it needs to be more precise about which nodes are which.

564

I don't think it makes sense to treat these backwards. We know the CR part should be real and the CI is imaginary. It would only be valid to treat them the other way around if there was some sort of shuffle added.

593

Does this need to be calling identifyNode on the third argument too? The one derived from UncommonValues.

656

This looks like it needs to match:

• RealI and ImagI are both shuffles.
• They both have the same Operand0
• They both have "deinterleaving" masks.

I don't think the type of the value of Operand0 otherwise matters. It doesn't matter if it is a Load or a Argument, we can always just use it.

749

It's best not to use static data like this, we can make it more generic. The match can be m_Shuffle(..., m_Mask(Mask)), then check that the Mask is an isDeinterleavingMask. It does need to check _which_ deinterleaving mask it is though for the Real/Imaginary parts.

854

If the Operands that CN depends on are included in the Node, then we can just walk up the tree making sure we create the Operands before the Nodes that use them, using the Value's that the operands produce as the Input0/Input1/Accumulator below.
That avoids the need to "wrangle" any inputs at this stage, as we already know the nodes we need.

869

It might be simpler to remove anything Cost based from this revision, adding it back in if it is needed in followup patches.
All the identification that happens in this patch should always be cheaper, as far as I understand.

[NickGuy]

Addressed comments and improved case coverage,

[dmgreen]

Some of this seems to have returned to a previous version of the patch?

llvm/lib/CodeGen/CMakeLists.txt

46

This formatting again?

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

432

Similar to identifyPartialMul, this probably needs to be more careful about what it is selecting as which operands.

529

I still think this needs to be a more precise with regard to what is considered the CommonOperand and CommonOperand.

569–571

Is it valid to test the operands in the opposite order?

624

Should these be checking the subnodes?

if (!identifyNode(..))
  return nullptr;

647

CommonOperandI only seems to be important between identifyPartialMul and identifyNodeWithImplicitAdd

680–681

These need to check that the first is the real deinterleave with offset=0, and the imag has offset=1. And maybe that they only take elements from the first operand and don't change size.

724–732

I feel that this should be correct by construction. What cases are not correct?

791–793

I don't think this should be needed. The inputs should just be present from the ReplacementNode of the operands.

811

If the statistic is being awkward then it is probably not worth keeping (or keeping simple - just counting number of transforms, not the number of individual intrinsics that might become in the backend).

llvm/lib/Target/ARM/ARMISelLowering.cpp

21882

It is better not to use fixed sized arrays like this, just construct the array to be any needed size. If the values are continuous you can use iota.

llvm/test/CodeGen/ARM/ComplexArithmetic/complex-arithmetic-f16-add.ll

2 ↗

(On Diff #416915)

These tests seem to have moved back to the wrong place.

[NickGuy]

Addressed comments

[dmgreen]

OK great. It would be good to see a lot of test cases for pretty much anything that might go wrong. Things like the shuffles with incorrect masks, fadd's where there should be fsubs, patterns that cross basic blocks, any of the conditions that can currently return false that we can test.

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

128

Can we just use nullptr as the sentinel value for IsValid = false, removing the need for this struct? If we need some way to represent the last shuffle node then we could add a Shuffle or Leaf node type (which could itself have a ReplacementNode just set to the shuffle->operand(0)).

Hopefully that also simplifies resolveInputs / Elevate. Especially if Accumulator is treated in the same way as an Operand. Hopefully that is simpler.

438

Should this function be calling identifyNode on the inputs, similar to identifyPartialMul?

473

When can this be false?

590

I think I was expecting Operands to be the ComplexDeinterleavingCompositeNode* from identifyNode. That avoids the need to find the again later.

717

These seem to do recursive checks into the operands, but that is already being done again in identifyNode. Can we just remove them and rely on identifyNode?

776–777

This isn't used any more, which is good (I think there might be a better way to get a TTI if it was needed).

787–788

When can this return false?

[NickGuy]

Forgot to submit the comments adjoining the patch...

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

569–571

No, but it's also not invalid (the checks do what they're supposed to and don't produce a node). I've removed these.

647

It used to be needed all through, but that is no longer the case. Changed the signatures and such to reflect this.

724–732

The one that is easiest to see is when attempting to multiply by a value rotated by 270 (a[i] * (b[i] * I*I*I)), it produces the following IR which has the real and imaginary components reversed at %interleaved.vec

%a.real = shufflevector <8 x float> %a, <8 x float> poison, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
%a.imag = shufflevector <8 x float> %a, <8 x float> poison, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
%b.real = shufflevector <8 x float> %b, <8 x float> poison, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
%b.imag = shufflevector <8 x float> %b, <8 x float> poison, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
%0 = fmul fast <4 x float> %b.imag, %a.imag
%1 = fmul fast <4 x float> %b.real, %a.real
%2 = fsub fast <4 x float> %0, %1
%3 = fmul fast <4 x float> %b.imag, %a.real
%4 = fmul fast <4 x float> %b.real, %a.imag
%5 = fadd fast <4 x float> %4, %3
%interleaved.vec = shufflevector <4 x float> %5, <4 x float> %2, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>

787–788

It can be false if a shuffle hasn't been traversed properly. In hindsight though, this could be an assertion instead as it indicates a problem with the node construction.

791–793

It's more of a side effect of analysing the whole tree before actually performing the replacement (which we do in case the tree can't be transformed). With some of the recent changes however, this function can't return false so it's merely a step of the replacement now.

811

Changed to track the transforms rather than individual intrinsics.

[NickGuy]

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

438

Not here, no. The inputs need to be resolved as part of the whole pair, so the relevant one for the created node is passed back via CommonOperandI.

473

In it's current state, never. It was possible before moving to the implicitAdd approach

776–777

Good catch, removed.

[NickGuy]

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

590

Attempting to plumb something together that acceps both ComplexDeinterleavingCompositeNode* and Value* caused more bloat and made things more difficult to follow. And we can't simply use Node->ReplacementNode as the Value* because it hasn't been assigned yet.
Because of that constraint, I'm opting to find the nodes later, though I'm open to ideas.

[dmgreen]

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

169

Why is this needed? When are the Real and Imag values not already correct? It seems strange to be able to reverse them.

438

What about the other pair? They are not guaranteed to be the same as the operands from identifyPartialMul as far as I can see. I would probably make sure that the two operands are a valid match too. The second call to identifyNode with the same operands should just find the same node again. And that way this can have proper operands.

Currently this and identifyPartialMul are very much interlinked. I hope we can improve that in the future, but it sounds like an extension that can be thought about later.

590

I was expecting it to just accept ComplexDeinterleavingCompositeNode. If all the operands are ComplexDeinterleavingCompositeNode, then they just need to be visited in the correct order to assign ReplacementNode based on how they need to be transformed. (Which I believe is fine providing we visit them in reverse order, like is already done).

i.e. we construct a graph made up of ComplexDeinterleavingCompositeNode, then transform that graph. That seems like a simpler, more extensible design going forward. It gets more complicated if there is a mixing of values between the original IR and the newly constructed intrinsics. I could imagine that might make graphs (as opposed to DAGs) more difficult, but we don't yet support any cycles.

724–732

Sorry - I'm not sure what this was referring to now! Do you think that example should be transforming into complex intrinsics? It doesn't look valid to me.

Have you added it as a test case?

737–738

Can we move this into identifyNodes (or maybe at this point there will always be nodes?)

That would make replaceNodes always return true, which simplifies the getDeadRoots a little too.

[NickGuy]

Addressed comments, and redesigned the lookup list of nodes to now be represented as a graph.

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

169

It was a holdover function that I reused for the .Valid check. It's not used anywhere else so I've removed it (and the relevant struct), and moved the relevant check to here.

590

I've converted the pseudo-graph (a list with lookups) to an actual graph structure, with every node being a ComplexDeinterleavingCompositeNode*, meaning that we're no longer mixing Value*s and ComplexDeinterleavingCompositeNode*s.

[dmgreen]

Have you had any luck adding a larger corpus of tests cases yet? I see that uses have been added to the graph. I would hope that we could avoid that complication, but it is hard to see if we can or not without a larger set of tests.

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

762

Try not to overuse auto where the type isn't already obvious.

[NickGuy]

Added more interesting test cases, covering triangle and diamond multiply cases.

[dmgreen]

Thanks for adding all the extra tests. Here is another one, that is useful in itself, but more useful when we break it. It does a*b +90 a*c, and seems to work well for this example.

define arm_aapcs_vfpcc <4 x float> @test(<4 x float> %a, <4 x float> %b, <4 x float> %c) {
entry:
  %ar = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
  %ai = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
  %br = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
  %bi = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
  %cr = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 0, i32 2>
  %ci = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 1, i32 3>

  %i6 = fmul fast <2 x float> %br, %ar
  %i7 = fmul fast <2 x float> %bi, %ai
  %xr = fsub fast <2 x float> %i6, %i7
  %i9 = fmul fast <2 x float> %bi, %ar
  %i10 = fmul fast <2 x float> %br, %ai
  %xi = fadd fast <2 x float> %i9, %i10

  %j6 = fmul fast <2 x float> %cr, %ar
  %j7 = fmul fast <2 x float> %ci, %ai
  %yr = fsub fast <2 x float> %j6, %j7
  %j9 = fmul fast <2 x float> %ci, %ar
  %j10 = fmul fast <2 x float> %cr, %ai
  %yi = fadd fast <2 x float> %j9, %j10

  %zr = fsub fast <2 x float> %yr, %xi
  %zi = fadd fast <2 x float> %yi, %xr
  %interleaved.vec = shufflevector <2 x float> %zr, <2 x float> %zi, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
  ret <4 x float> %interleaved.vec
}

But this is a modification that alters the c*a to use part of the b*a mul's. It shouldn't be being transformed as it is, I don't believe.

define arm_aapcs_vfpcc <4 x float> @mul_triangle_addmul(<4 x float> %a, <4 x float> %b, <4 x float> %c) {
entry:
  %ar = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
  %ai = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
  %br = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
  %bi = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
  %cr = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 0, i32 2>
  %ci = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 1, i32 3>

  %i6 = fmul fast <2 x float> %br, %ar
  %i7 = fmul fast <2 x float> %bi, %ai
  %xr = fsub fast <2 x float> %i6, %i7
  %i9 = fmul fast <2 x float> %bi, %ar
  %i10 = fmul fast <2 x float> %br, %ai
  %xi = fadd fast <2 x float> %i9, %i10

  ;%j6 = fmul fast <2 x float> %cr, %ar
  %j7 = fmul fast <2 x float> %ci, %ai
  %yr = fsub fast <2 x float> %i6, %j7
  ;%j9 = fmul fast <2 x float> %ci, %ar
  %j10 = fmul fast <2 x float> %cr, %ai
  %yi = fadd fast <2 x float> %i9, %j10

  %zr = fsub fast <2 x float> %yr, %xi
  %zi = fadd fast <2 x float> %yi, %xr
  %interleaved.vec = shufflevector <2 x float> %zr, <2 x float> %zi, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
  ret <4 x float> %interleaved.vec
}

The Incomplete nodes worry me as it looks like a rich source of bugs. If the identifyPartialMul and identifyNodeWithImplicitAdd need to work together more closely for the time being, that is probably fine. We can always change it in the future if needed.

Some other issues are that we need to check for multiple uses. As in something like

define arm_aapcs_vfpcc <4 x float> @mul_triangle_multiuses(<4 x float> %a, <4 x float> %b, ptr %p) {
; CHECK-LABEL: mul_triangle_multiuses:
; CHECK:       @ %bb.0: @ %entry
; CHECK-NEXT:    .vsave {d14}
; CHECK-NEXT:    vpush {d14}
; CHECK-NEXT:    .vsave {d10, d11, d12}
; CHECK-NEXT:    vpush {d10, d11, d12}
; CHECK-NEXT:    .vsave {d8}
; CHECK-NEXT:    vpush {d8}
; CHECK-NEXT:    vmov q2, q0
; CHECK-NEXT:    vmov.f32 s16, s4
; CHECK-NEXT:    vmov.f32 s17, s6
; CHECK-NEXT:    vmov.i32 q0, #0x0
; CHECK-NEXT:    vmov.f32 s20, s9
; CHECK-NEXT:    vmov.f32 s21, s11
; CHECK-NEXT:    vmov.f32 s28, s5
; CHECK-NEXT:    vmul.f32 q3, q5, q4
; CHECK-NEXT:    vmov.f32 s29, s7
; CHECK-NEXT:    vmul.f32 q5, q7, q5
; CHECK-NEXT:    vmov.f32 s24, s8
; CHECK-NEXT:    vmov.f32 s25, s10
; CHECK-NEXT:    vneg.f32 q5, q5
; CHECK-NEXT:    vfma.f32 q3, q7, q6
; CHECK-NEXT:    vfma.f32 q5, q4, q6
; CHECK-NEXT:    vmov.f32 s22, s12
; CHECK-NEXT:    vmov.f32 s23, s13
; CHECK-NEXT:    vmov q3, q0
; CHECK-NEXT:    vcmla.f32 q3, q1, q2, #0
; CHECK-NEXT:    vstrw.32 q5, [r0]
; CHECK-NEXT:    vcmla.f32 q3, q1, q2, #90
; CHECK-NEXT:    vcmla.f32 q0, q2, q3, #0
; CHECK-NEXT:    vcmla.f32 q0, q2, q3, #90
; CHECK-NEXT:    vpop {d8}
; CHECK-NEXT:    vpop {d10, d11, d12}
; CHECK-NEXT:    vpop {d14}
; CHECK-NEXT:    bx lr
entry:
  %strided.vec = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
  %strided.vec35 = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
  %strided.vec37 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
  %strided.vec38 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
  %0 = fmul fast <2 x float> %strided.vec37, %strided.vec
  %1 = fmul fast <2 x float> %strided.vec38, %strided.vec35
  %2 = fsub fast <2 x float> %0, %1
  %3 = fmul fast <2 x float> %2, %strided.vec35
  %4 = fmul fast <2 x float> %strided.vec38, %strided.vec
  %5 = fmul fast <2 x float> %strided.vec35, %strided.vec37
  %6 = fadd fast <2 x float> %4, %5
  %otheruse = shufflevector <2 x float> %2, <2 x float> %6, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
  store <4 x float> %otheruse, ptr %p
  %7 = fmul fast <2 x float> %6, %strided.vec
  %8 = fadd fast <2 x float> %3, %7
  %9 = fmul fast <2 x float> %2, %strided.vec
  %10 = fmul fast <2 x float> %6, %strided.vec35
  %11 = fsub fast <2 x float> %9, %10
  %interleaved.vec = shufflevector <2 x float> %11, <2 x float> %8, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
  ret <4 x float> %interleaved.vec
}

And we probably need to check for fast-math flags, where we are generating fma. I also think that it is safer if nodes are uniquely identified from {real, imag} root pairs, not just from nodes that might contain either real or imag somewhere in them.

llvm/test/CodeGen/Thumb2/complex-deinterleaving-uniform-cases.ll

1 ↗

(On Diff #463541)

All the mve tests start with mve-

[NickGuy]

Thanks @dmgreen for the extra tests.

In D114174#3826540, @dmgreen wrote:

...
The Incomplete nodes worry me as it looks like a rich source of bugs. If the identifyPartialMul and identifyNodeWithImplicitAdd need to work together more closely for the time being, that is probably fine. We can always change it in the future if needed.
...

I've removed the late lookup/replacement of incomplete nodes, and moved it closer to where the incomplete nodes are created. I've also made it only check against a single node, one that we know should match

...
And we probably need to check for fast-math flags, where we are generating fma. I also think that it is safer if nodes are uniquely identified from {real, imag} root pairs, not just from nodes that might contain either real or imag somewhere in them.
...

Done, we're now checking the fast-math flags (specifically contract)

[dmgreen]

llvm/include/llvm/CodeGen/ComplexDeinterleavingPass.h

37

I don't think None is ever used, and from what I can see _Placeholder is a Shuffle? That might be a better name, either Shuffle or Leaf. I would also probably remove _Incomplete. They might make sense, but it is difficult to follow and very easy to get wrong.

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

106

I think it would be best to store the root Real and Imag values as part of the ComplexDeinterleavingCompositeNode. That way we can be sure we are matching a correct node from anything like getContainingComposite.
There can then be the TransientInstructions (maybe "ExtraInstructions"), which are also part of the pattern, but not the root nodes.

115

Could AccumulatorNode just be another Operand?

116

I think this would be best to avoid NodePtr, if that might keep a reference to a node alive. Avoiding shared_ptr entirely would be good, but I imagine any alternative might be difficult too. They needs to be stable values to avoid memory invalidation issues.

171

Formatting needs updating.

220

If NodeInstructions is used to calculate all the Instructions we have seen, to check that all the uses are inside the graph, it could be a SmallPtrSet which will have quicker contains().

288

It is hard to see how wrapping a Value as an _Incomplete node is always correct. It will have lost the information about whether V was real or imaginary.

576

Do you have any tests for fneg? This should probably be more like the code in identifyPartialMul where the rotation is chosen based on whether the Real/Imag parts are negated.

673

It's not the combination of rotates that is invalid really, although some might make less sense than others, and some might simplify to code that is difficult to match. The even rotations will define the real part of a, the odd rotations define the imag part. Between the two parts of the multiply we match we need to find both the real and imag halves of the value, to successfully match it further. (We may be able to do something with only half a match in some cases, like matching leafs, but that should probably be left for a later patch).

llvm/test/CodeGen/Thumb2/mve-complex-deinterleaving-mixed-cases.ll

79

Are you sure this is valid?
When we were doing the gather lowering, we found it useful to annotate the tests with OK/Bad, so if they change we could see the ones we thought shouldn't.

[NickGuy]

Addressed comments

[dmgreen]

Thanks for the updates. This is looking good now.

There are some extra comments below. I was trying some examples that have awkward orders and cross basicblocks, but couldn't find ways to make it break.

llvm/include/llvm/CodeGen/ComplexDeinterleavingPass.h

40–43

This can now be re-flowed.

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

20

Can this comment be updated now?

560

These can be // comments. They are very useful, but maybe it is not necessary to repeat them.

llvm/test/CodeGen/Thumb2/mve-complex-deinterleaving-mixed-cases.ll

4

Are there any tests with missing fast-math flags?

5

I managed to come up with this testcase that failed because of the vector size. It is probably larger than it needs to be. It could work or not, depending if the backend handles non-power-2 sizes. In either rate, it would be good to add this example. (Once integers are added too, some odd size integer width tests would be good too).

define arm_aapcs_vfpcc <12 x float> @abp90c12(<12 x float> %a, <12 x float> %b, <12 x float> %c) {
entry:
  %ar = shufflevector <12 x float> %a, <12 x float> poison, <6 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10>
  %ai = shufflevector <12 x float> %a, <12 x float> poison, <6 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11>
  %br = shufflevector <12 x float> %b, <12 x float> poison, <6 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10>
  %bi = shufflevector <12 x float> %b, <12 x float> poison, <6 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11>
  %cr = shufflevector <12 x float> %c, <12 x float> poison, <6 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10>
  %ci = shufflevector <12 x float> %c, <12 x float> poison, <6 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11>

  %i6 = fmul fast <6 x float> %br, %ar
  %i7 = fmul fast <6 x float> %bi, %ai
  %xr = fsub fast <6 x float> %i6, %i7
  %i9 = fmul fast <6 x float> %bi, %ar
  %i10 = fmul fast <6 x float> %br, %ai
  %xi = fadd fast <6 x float> %i9, %i10

  %zr = fsub fast <6 x float> %cr, %xi
  %zi = fadd fast <6 x float> %ci, %xr
  %interleaved.vec = shufflevector <6 x float> %zr, <6 x float> %zi, <12 x i32> <i32 0, i32 6, i32 1, i32 7, i32 2, i32 8, i32 3, i32 9, i32 4, i32 10, i32 5, i32 11>
  ret <12 x float> %interleaved.vec
}

llvm/test/CodeGen/Thumb2/mve-complex-deinterleaving-uniform-cases.ll

79

Is this just not transforming because of commutativity on the add? Can we add a test for fadd fast <2 x float> %strided.vec20, %strided.vec too, to show it does transform.

[SjoerdMeijer]

Came here to say that this looks nice and would be worthy a mention in the release notes, so that can be added, I think.

Then I started reading the patch again a bit and couldn't help myself writing down some nits.

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

17

Nit: perhaps just omit in parallel? Or if you want to keep it, it could benefit from a clarification.

26

I wouldn't mind a few more words/sentences about the internal datastructures, the graph, nodes, etc.

51

Nit: remove deinterleaving from this description?

60

Nit: newline

110

Can you say what these instructions could be?

174

I haven't looked carefully, but why do we also need to record all instructions here? I mean, the graph can be queried for existence of nodes/instructions, or is this bookkeeping duplication more efficient?

182

Nit: no validation going on here, only insertion?

182

Nit: no validation going on here, only insertion?

240

Nit: newline?

313

Nit: can omit the comparison with 1.

344

Nit: I am a fan of reducing indentation, e.g.:

auto *SVI = dyn_cast<ShuffleVectorInst>(&I);
if (!SVI)
  continue;
if (!isInterleavingMask(SVI->getShuffleMask())
  continue;

etc.

368

Nit: maybe I overlooked something, but this doesn't seem to use any state from the class so could be just a helper function?

468

Nit: I am wondering if these casts here and below are necessary.

484

nit: maybe some or all of these node setting things can be done in a constructor.

540

Nits:
Op -> Operand,
not Instruction -> not a Instruction?

[NickGuy]

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

174

The duplication makes it simpler to check the internal uses of a node (See ComplexDeinterleavingCompositeNode::hasAllInternalUses). Without it, we'd need to iterate over the nodes twice, and check the instructions of each node (All of Real, Imag, and the contents of InternalInstructions), while this approach allows us to simply say "Is this instruction known within the graph?".

182

Good catch, the validation that was here was moved to be more tied into the identification. Renamed

368

It populates the compositeNode structure through (formerly) validateAndSubmitCompositeNode, and also calls identifyNode further, which does use state from the class.

468

You are correct, good catch.

484

Not sure I agree with that, there are cases - such as a Shuffle - where none of the other settings are relevant. The operation type, real instruction, and imaginary instructions are the only settings relevant to all cases.

llvm/test/CodeGen/Thumb2/mve-complex-deinterleaving-mixed-cases.ll

5

Fixed this case (by checking on the backend whether the vector width is a power of 2), and added the test.

llvm/test/CodeGen/Thumb2/mve-complex-deinterleaving-uniform-cases.ll

79

Yep, it's the commutativity. I've added a note to this test stating this, and added another test with the fadd operands reversed.

[dmgreen]

llvm/include/llvm/InitializePasses.h

101

You can undo these

111

There is a newline here?

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

413

If you can turn some of these into better sentances that would be good. Perhaps "Mul instruction has multiple uses" like you have below.

482

Formatting is a bit long.

llvm/lib/Target/ARM/ARMTargetMachine.cpp

437

This again.

llvm/test/CodeGen/ARM/O3-pipeline.ll

2

This looks like it was incorrectly added for this test.

[dmgreen]

OK great. Thanks for the updates. I think this looks to be in a good state now. We can always do more nitpicking, and but it looks to be in a good state to get into tree. We can get this in now and add AArch64 support on top to increase the test coverage.

Some minor comments below but otherwise LGTM.

llvm/include/llvm/InitializePasses.h

108

You can undo these.

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

591

Formatting.

llvm/lib/Target/ARM/ARMISelLowering.cpp

21860

Formatting.

21868

Add a message to the assert

[SjoerdMeijer]

In D114174#3924650, @dmgreen wrote:

OK great. Thanks for the updates. I think this looks to be in a good state now. We can always do more nitpicking, and but it looks to be in a good state to get into tree. We can get this in now and add AArch64 support on top to increase the test coverage.

Some minor comments below but otherwise LGTM.

Agreed, and thanks for working on this.

Question about AArch64, is that something you are going to work on next?

[NickGuy]

In D114174#3924782, @SjoerdMeijer wrote:

In D114174#3924650, @dmgreen wrote:

OK great. Thanks for the updates. I think this looks to be in a good state now. We can always do more nitpicking, and but it looks to be in a good state to get into tree. We can get this in now and add AArch64 support on top to increase the test coverage.

Some minor comments below but otherwise LGTM.

Agreed, and thanks for working on this.

Question about AArch64, is that something you are going to work on next?

Yep, over at D129066. It's currently slightly behind this, but is mostly there already.

llvm/include/llvm/CodeGen/ComplexDeinterleavingPass.h

+//===- ComplexDeinterleavingPass.h - Complex Deinterleaving Pass *- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass implements generation of target-specific intrinsics to support
+// handling of complex number arithmetic and deinterleaving.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_COMPLEXDEINTERLEAVING_H
+#define LLVM_CODEGEN_COMPLEXDEINTERLEAVING_H
+
+#include "llvm/IR/PassManager.h"
+#include "llvm/IR/PatternMatch.h"
+
+namespace llvm {
+
+class Function;
+class TargetMachine;
+
+struct ComplexDeinterleavingPass
+    : public PassInfoMixin<ComplexDeinterleavingPass> {
+private:
+  TargetMachine *TM;
+
+public:
+  ComplexDeinterleavingPass(TargetMachine *TM) : TM(TM) {}
+
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+
+enum class ComplexDeinterleavingOperation {
+  CAdd,
+  CMulPartial,
+  // The following 'operations' are used to represent internal states. Backends
+  // are not expected to try and support these in any capacity.
+  Shuffle
+};
+
+enum class ComplexDeinterleavingRotation {
+  Rotation_0 = 0,
+  Rotation_90 = 1,
+  Rotation_180 = 2,
+  Rotation_270 = 3,
+};
+
+} // namespace llvm
+
+#endif // LLVM_CODEGEN_COMPLEXDEINTERLEAVING_H

llvm/include/llvm/CodeGen/Passes.h

 //===-- Passes.h - Target independent code generation passes ----*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines interfaces to access the target independent code generation
 // passes provided by the LLVM backend.
 //
 //===----------------------------------------------------------------------===//
 
namespace llvm {
   /// If AbortOnFailedISel is true, abort compilation instead of resetting.
   MachineFunctionPass *createResetMachineFunctionPass(bool EmitFallbackDiag,
                                                       bool AbortOnFailedISel);
 
   /// createCodeGenPreparePass - Transform the code to expose more pattern
   /// matching during instruction selection.
   FunctionPass *createCodeGenPreparePass();
 
+  /// This pass implements generation of target-specific intrinsics to support
+  /// handling of complex number arithmetic
+  FunctionPass *createComplexDeinterleavingPass(const TargetMachine *TM);
+
   /// AtomicExpandID -- Lowers atomic operations in terms of either cmpxchg
   /// load-linked/store-conditional loops.
   extern char &AtomicExpandID;
 
   /// MachineLoopInfo - This pass is a loop analysis pass.
   extern char &MachineLoopInfoID;
 
   /// MachineDominators - This pass is a machine dominators analysis pass.

llvm/include/llvm/CodeGen/TargetLowering.h

 ///  2. Which operations are supported for supported ValueTypes.
 ///  3. Cost thresholds for alternative implementations of certain operations.
 ///
 /// In addition it has a few other components, like information about FP
 /// immediates.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_TARGETLOWERING_H
 #define LLVM_CODEGEN_TARGETLOWERING_H
 
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/CodeGen/ComplexDeinterleavingPass.h"
 #include "llvm/CodeGen/DAGCombine.h"
 #include "llvm/CodeGen/ISDOpcodes.h"
 #include "llvm/CodeGen/LowLevelType.h"
 #include "llvm/CodeGen/RuntimeLibcalls.h"
 #include "llvm/CodeGen/SelectionDAG.h"
 #include "llvm/CodeGen/SelectionDAGNodes.h"
 #include "llvm/CodeGen/TargetCallingConv.h"
 #include "llvm/CodeGen/ValueTypes.h"
public:
   virtual bool shouldKeepZExtForFP16Conv() const { return false; }
 
   /// Should we generate fp_to_si_sat and fp_to_ui_sat from type FPVT to type VT
   /// from min(max(fptoi)) saturation patterns.
   virtual bool shouldConvertFpToSat(unsigned Op, EVT FPVT, EVT VT) const {
     return isOperationLegalOrCustom(Op, VT);
   }
 
+  /// Does this target support complex deinterleaving
+  virtual bool isComplexDeinterleavingSupported() const { return false; }
+
+  /// Does this target support complex deinterleaving with the given operation
+  /// and type
+  virtual bool isComplexDeinterleavingOperationSupported(
+      ComplexDeinterleavingOperation Operation, Type *Ty) const {
+    return false;
+  }
+
+  /// Create the IR node for the given complex deinterleaving operation.
+  /// If one cannot be created using all the given inputs, nullptr should be
+  /// returned.
+  virtual Value *createComplexDeinterleavingIR(
+      Instruction *I, ComplexDeinterleavingOperation OperationType,
+      ComplexDeinterleavingRotation Rotation, Value *InputA, Value *InputB,
+      Value *Accumulator = nullptr) const {
+    return nullptr;
+  }
+
   //===--------------------------------------------------------------------===//
   // Runtime Library hooks
   //
 
   /// Rename the default libcall routine name for the specified libcall.
   void setLibcallName(RTLIB::Libcall Call, const char *Name) {
     LibcallRoutineNames[Call] = Name;
   }

llvm/include/llvm/InitializePasses.h

 void initializeCFIFixupPass(PassRegistry&);
 void initializeCFIInstrInserterPass(PassRegistry&);
 void initializeCFLAndersAAWrapperPassPass(PassRegistry&);
 void initializeCFLSteensAAWrapperPassPass(PassRegistry&);
 void initializeCallGraphDOTPrinterPass(PassRegistry&);
 void initializeCallGraphPrinterLegacyPassPass(PassRegistry&);
 void initializeCallGraphViewerPass(PassRegistry&);
 void initializeCallGraphWrapperPassPass(PassRegistry&);
 void initializeCallSiteSplittingLegacyPassPass(PassRegistry&);
 void initializeCalledValuePropagationLegacyPassPass(PassRegistry &);
 void initializeCheckDebugMachineModulePass(PassRegistry &);
 void initializeCodeGenPreparePass(PassRegistry&);
+void initializeComplexDeinterleavingLegacyPassPass(PassRegistry&);
 void initializeConstantHoistingLegacyPassPass(PassRegistry&);
 void initializeConstantMergeLegacyPassPass(PassRegistry&);
 void initializeConstraintEliminationPass(PassRegistry &);
 void initializeCorrelatedValuePropagationPass(PassRegistry&);
 void initializeCostModelAnalysisPass(PassRegistry&);
 void initializeCrossDSOCFIPass(PassRegistry&);
 void initializeCycleInfoWrapperPassPass(PassRegistry &);
 void initializeDAEPass(PassRegistry&);
 void initializeDAHPass(PassRegistry&);
 void initializeDCELegacyPassPass(PassRegistry&);
 void initializeDFAJumpThreadingLegacyPassPass(PassRegistry &);
 void initializeDSELegacyPassPass(PassRegistry&);
 void initializeDeadMachineInstructionElimPass(PassRegistry&);
 void initializeDebugifyMachineModulePass(PassRegistry &);

llvm/lib/CodeGen/CMakeLists.txt

add_llvm_component_library(LLVMCodeGen
   CFGuardLongjmp.cpp
   CFIFixup.cpp
   CFIInstrInserter.cpp
   CodeGen.cpp
   CodeGenCommonISel.cpp
   CodeGenPassBuilder.cpp
   CodeGenPrepare.cpp
   CommandFlags.cpp
+  ComplexDeinterleavingPass.cpp
   CriticalAntiDepBreaker.cpp
   DeadMachineInstructionElim.cpp
   DetectDeadLanes.cpp
   DFAPacketizer.cpp
   DwarfEHPrepare.cpp
   EarlyIfConversion.cpp
   EdgeBundles.cpp
   EHContGuardCatchret.cpp

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

+//===- ComplexDeinterleavingPass.cpp --------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Identification:
+// This step is responsible for finding the patterns that can be lowered to
+// complex instructions, and building a graph to represent the complex
+// structures. Starting from the "Converging Shuffle" (a shuffle that
+// reinterleaves the complex components, with a mask of <0, 2, 1, 3>), the
+// operands are evaluated and identified as "Composite Nodes" (collections of
+// instructions that can potentially be lowered to a single complex
+// instruction). This is performed by checking the real and imaginary components
+// and tracking the data flow for each component while following the operand
+// pairs. Validity of each node is expected to be done upon creation, and any
+// validation errors should halt traversal and prevent further graph
+// construction.
+//
+// Replacement:
+// This step traverses the graph built up by identification, delegating to the
+// target to validate and generate the correct intrinsics, and plumbs them
+// together connecting each end of the new intrinsics graph to the existing
+// use-def chain. This step is assumed to finish successfully, as all
+// information is expected to be correct by this point.
+//
+//
+// Internal data structure:
+// ComplexDeinterleavingGraph:
+// Keeps references to all the valid CompositeNodes formed as part of the
+// transformation, and every Instruction contained within said nodes. It also
+// holds onto a reference to the root Instruction, and the root node that should
+// replace it.
+//
+// ComplexDeinterleavingCompositeNode:
+// A CompositeNode represents a single transformation point; each node should
+// transform into a single complex instruction (ignoring vector splitting, which
+// would generate more instructions per node). They are identified in a
+// depth-first manner, traversing and identifying the operands of each
+// instruction in the order they appear in the IR.
+// Each node maintains a reference  to its Real and Imaginary instructions,
+// as well as any additional instructions that make up the identified operation
+// (Internal instructions should only have uses within their containing node).
+// A Node also contains the rotation and operation type that it represents.
+// Operands contains pointers to other CompositeNodes, acting as the edges in
+// the graph. ReplacementValue is the transformed Value* that has been emitted
+// to the IR.
+//
+// Note: If the operation of a Node is Shuffle, only the Real, Imaginary, and
+// ReplacementValue fields of that Node are relevant, where the ReplacementValue
+// should be pre-populated.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/ComplexDeinterleavingPass.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/CodeGen/TargetLowering.h"
+#include "llvm/CodeGen/TargetPassConfig.h"
+#include "llvm/CodeGen/TargetSubtargetInfo.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Transforms/Utils/Local.h"
+#include <algorithm>
+
+using namespace llvm;
+using namespace PatternMatch;
+
+#define DEBUG_TYPE "complex-deinterleaving"
+
+STATISTIC(NumComplexTransformations, "Amount of complex patterns transformed");
+
+static cl::opt<bool> ComplexDeinterleavingEnabled(
+    "enable-complex-deinterleaving",
+    cl::desc("Enable generation of complex instructions"), cl::init(true),
+    cl::Hidden);
+
+/// Checks the given mask, and determines whether said mask is interleaving.
+///
+/// To be interleaving, a mask must alternate between `i` and `i + (Length /
+/// 2)`, and must contain all numbers within the range of `[0..Length)` (e.g. a
+/// 4x vector interleaving mask would be <0, 2, 1, 3>).
+static bool isInterleavingMask(ArrayRef<int> Mask);
+
+/// Checks the given mask, and determines whether said mask is deinterleaving.
+///
+/// To be deinterleaving, a mask must increment in steps of 2, and either start
+/// with 0 or 1.
+/// (e.g. an 8x vector deinterleaving mask would be either <0, 2, 4, 6> or
+/// <1, 3, 5, 7>).
+static bool isDeinterleavingMask(ArrayRef<int> Mask);
+
+namespace {
+
+class ComplexDeinterleavingLegacyPass : public FunctionPass {
+public:
+  static char ID;
+
+  ComplexDeinterleavingLegacyPass(const TargetMachine *TM = nullptr)
+      : FunctionPass(ID), TM(TM) {
+    initializeComplexDeinterleavingLegacyPassPass(
+        *PassRegistry::getPassRegistry());
+  }
+
+  StringRef getPassName() const override {
+    return "Complex Deinterleaving Pass";
+  }
+
+  bool runOnFunction(Function &F) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<TargetLibraryInfoWrapperPass>();
+    AU.setPreservesCFG();
+  }
+
+private:
+  const TargetMachine *TM;
+};
+
+class ComplexDeinterleavingGraph;
+struct ComplexDeinterleavingCompositeNode {
+
+  ComplexDeinterleavingCompositeNode(ComplexDeinterleavingOperation Op,
+                                     Instruction *R, Instruction *I)
+      : Operation(Op), Real(R), Imag(I) {}
+
+private:
+  friend class ComplexDeinterleavingGraph;
+  using NodePtr = std::shared_ptr<ComplexDeinterleavingCompositeNode>;
+  using RawNodePtr = ComplexDeinterleavingCompositeNode *;
+
+public:
+  ComplexDeinterleavingOperation Operation;
+  Instruction *Real;
+  Instruction *Imag;
+
+  // Instructions that should only exist within this node, there should be no
+  // users of these instructions outside the node. An example of these would be
+  // the multiply instructions of a partial multiply operation.
+  SmallVector<Instruction *> InternalInstructions;
+  ComplexDeinterleavingRotation Rotation;
+  SmallVector<RawNodePtr> Operands;
+  Value *ReplacementNode = nullptr;
+
+  void addInstruction(Instruction *I) { InternalInstructions.push_back(I); }
+  void addOperand(NodePtr Node) { Operands.push_back(Node.get()); }
+
+  bool hasAllInternalUses(SmallPtrSet<Instruction *, 16> &AllInstructions);
+
+  void dump() { dump(dbgs()); }
+  void dump(raw_ostream &OS) {
+    auto PrintValue = [&](Value *V) {
+      if (V) {
+        OS << "\"";
+        V->print(OS, true);
+        OS << "\"\n";
+      } else
+        OS << "nullptr\n";
+    };
+    auto PrintNodeRef = [&](RawNodePtr Ptr) {
+      if (Ptr)
+        OS << Ptr << "\n";
+      else
+        OS << "nullptr\n";
+    };
+
+    OS << "- CompositeNode: " << this << "\n";
+    OS << "  Real: ";
+    PrintValue(Real);
+    OS << "  Imag: ";
+    PrintValue(Imag);
+    OS << "  ReplacementNode: ";
+    PrintValue(ReplacementNode);
+    OS << "  Operation: " << (int)Operation << "\n";
+    OS << "  Rotation: " << ((int)Rotation * 90) << "\n";
+    OS << "  Operands: \n";
+    for (const auto &Op : Operands) {
+      OS << "    - ";
+      PrintNodeRef(Op);
+    }
+    OS << "  InternalInstructions:\n";
+    for (const auto &I : InternalInstructions) {
+      OS << "    - \"";
+      I->print(OS, true);
+      OS << "\"\n";
+    }
+  }
+};
+
+class ComplexDeinterleavingGraph {
+public:
+  using NodePtr = ComplexDeinterleavingCompositeNode::NodePtr;
+  using RawNodePtr = ComplexDeinterleavingCompositeNode::RawNodePtr;
+  explicit ComplexDeinterleavingGraph(const TargetLowering *tl) : TL(tl) {}
+
+private:
+  const TargetLowering *TL;
+  Instruction *RootValue;
+  NodePtr RootNode;
+  SmallVector<NodePtr> CompositeNodes;
+  SmallPtrSet<Instruction *, 16> AllInstructions;
+
+  NodePtr prepareCompositeNode(ComplexDeinterleavingOperation Operation,
+                               Instruction *R, Instruction *I) {
+    return std::make_shared<ComplexDeinterleavingCompositeNode>(Operation, R,
+                                                                I);
+  }
+
+  NodePtr submitCompositeNode(NodePtr Node) {
+    CompositeNodes.push_back(Node);
+    AllInstructions.insert(Node->Real);
+    AllInstructions.insert(Node->Imag);
+    for (auto *I : Node->InternalInstructions)
+      AllInstructions.insert(I);
+    return Node;
+  }
+
+  NodePtr getContainingComposite(Value *R, Value *I) {
+    for (const auto &CN : CompositeNodes) {
+      if (CN->Real == R && CN->Imag == I)
+        return CN;
+    }
+    return nullptr;
+  }
+
+  /// Identifies a complex partial multiply pattern and its rotation, based on
+  /// the following patterns
+  ///
+  ///  0:  r: cr + ar * br
+  ///      i: ci + ar * bi
+  /// 90:  r: cr - ai * bi
+  ///      i: ci + ai * br
+  /// 180: r: cr - ar * br
+  ///      i: ci - ar * bi
+  /// 270: r: cr + ai * bi
+  ///      i: ci - ai * br
+  NodePtr identifyPartialMul(Instruction *Real, Instruction *Imag);
+
+  /// Identify the other branch of a Partial Mul, taking the CommonOperandI that
+  /// is partially known from identifyPartialMul, filling in the other half of
+  /// the complex pair.
+  NodePtr identifyNodeWithImplicitAdd(
+      Instruction *I, Instruction *J,
+      std::pair<Instruction *, Instruction *> &CommonOperandI);
+
+  /// Identifies a complex add pattern and its rotation, based on the following
+  /// patterns.
+  ///
+  /// 90:  r: ar - bi
+  ///      i: ai + br
+  /// 270: r: ar + bi
+  ///      i: ai - br
+  NodePtr identifyAdd(Instruction *Real, Instruction *Imag);
+
+  NodePtr identifyNode(Instruction *I, Instruction *J);
+
+  Value *replaceNode(RawNodePtr Node);
+
+public:
+  void dump() { dump(dbgs()); }
+  void dump(raw_ostream &OS) {
+    for (const auto &Node : CompositeNodes)
+      Node->dump(OS);
+  }
+
+  /// Returns false if the deinterleaving operation should be cancelled for the
+  /// current graph.
+  bool identifyNodes(Instruction *RootI);
+
+  /// Perform the actual replacement of the underlying instruction graph.
+  /// Returns false if the deinterleaving operation should be cancelled for the
+  /// current graph.
+  void replaceNodes();
+};
+
+class ComplexDeinterleaving {
+public:
+  ComplexDeinterleaving(const TargetLowering *tl, const TargetLibraryInfo *tli)
+      : TL(tl), TLI(tli) {}
+  bool runOnFunction(Function &F);
+
+private:
+  bool evaluateBasicBlock(BasicBlock *B);
+
+  const TargetLowering *TL = nullptr;
+  const TargetLibraryInfo *TLI = nullptr;
+};
+
+} // namespace
+
+char ComplexDeinterleavingLegacyPass::ID = 0;
+
+INITIALIZE_PASS_BEGIN(ComplexDeinterleavingLegacyPass, DEBUG_TYPE,
+                      "Complex Deinterleaving", false, false)
+INITIALIZE_PASS_END(ComplexDeinterleavingLegacyPass, DEBUG_TYPE,
+                    "Complex Deinterleaving", false, false)
+
+PreservedAnalyses ComplexDeinterleavingPass::run(Function &F,
+                                                 FunctionAnalysisManager &AM) {
+  const TargetLowering *TL = TM->getSubtargetImpl(F)->getTargetLowering();
+  auto &TLI = AM.getResult<llvm::TargetLibraryAnalysis>(F);
+  if (!ComplexDeinterleaving(TL, &TLI).runOnFunction(F))
+    return PreservedAnalyses::all();
+
+  PreservedAnalyses PA;
+  PA.preserve<FunctionAnalysisManagerModuleProxy>();
+  return PA;
+}
+
+FunctionPass *llvm::createComplexDeinterleavingPass(const TargetMachine *TM) {
+  return new ComplexDeinterleavingLegacyPass(TM);
+}
+
+bool ComplexDeinterleavingLegacyPass::runOnFunction(Function &F) {
+  const auto *TL = TM->getSubtargetImpl(F)->getTargetLowering();
+  auto TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
+  return ComplexDeinterleaving(TL, &TLI).runOnFunction(F);
+}
+
+bool ComplexDeinterleaving::runOnFunction(Function &F) {
+  if (!ComplexDeinterleavingEnabled) {
+    LLVM_DEBUG(
+        dbgs() << "Complex deinterleaving has been explicitly disabled.\n");
+    return false;
+  }
+
+  if (!TL->isComplexDeinterleavingSupported()) {
+    LLVM_DEBUG(
+        dbgs() << "Complex deinterleaving has been disabled, target does "
+                  "not support lowering of complex number operations.\n");
+    return false;
+  }
+
+  bool Changed = false;
+  for (auto &B : F)
+    Changed |= evaluateBasicBlock(&B);
+
+  return Changed;
+}
+
+static bool isInterleavingMask(ArrayRef<int> Mask) {
+  // If the size is not even, it's not an interleaving mask
+  if ((Mask.size() & 1))
+    return false;
+
+  int HalfNumElements = Mask.size() / 2;
+  for (int Idx = 0; Idx < HalfNumElements; ++Idx) {
+    int MaskIdx = Idx * 2;
+    if (Mask[MaskIdx] != Idx || Mask[MaskIdx + 1] != (Idx + HalfNumElements))
+      return false;
+  }
+
+  return true;
+}
+
+static bool isDeinterleavingMask(ArrayRef<int> Mask) {
+  int Offset = Mask[0];
+  int HalfNumElements = Mask.size() / 2;
+
+  for (int Idx = 1; Idx < HalfNumElements; ++Idx) {
+    if (Mask[Idx] != (Idx * 2) + Offset)
+      return false;
+  }
+
+  return true;
+}
+
+bool ComplexDeinterleaving::evaluateBasicBlock(BasicBlock *B) {
+  bool Changed = false;
+
+  SmallVector<Instruction *> DeadInstrRoots;
+
+  for (auto &I : *B) {
+    auto *SVI = dyn_cast<ShuffleVectorInst>(&I);
+    if (!SVI)
+      continue;
+
+    // Look for a shufflevector that takes separate vectors of the real and
+    // imaginary components and recombines them into a single vector.
+    if (!isInterleavingMask(SVI->getShuffleMask()))
+      continue;
+
+    ComplexDeinterleavingGraph Graph(TL);
+    if (!Graph.identifyNodes(SVI))
+      continue;
+
+    Graph.replaceNodes();
+    DeadInstrRoots.push_back(SVI);
+    Changed = true;
+  }
+
+  for (const auto &I : DeadInstrRoots) {
+    if (!I || I->getParent() == nullptr)
+      continue;
+    llvm::RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
+  }
+
+  return Changed;
+}
+
+ComplexDeinterleavingGraph::NodePtr
+ComplexDeinterleavingGraph::identifyNodeWithImplicitAdd(
+    Instruction *Real, Instruction *Imag,
+    std::pair<Instruction *, Instruction *> &PartialMatch) {
+  LLVM_DEBUG(dbgs() << "identifyNodeWithImplicitAdd " << *Real << " / " << *Imag
+                    << "\n");
+
+  if (!Real->hasOneUse() || !Imag->hasOneUse()) {
+    LLVM_DEBUG(dbgs() << "  - Mul operand has multiple uses.\n");
+    return nullptr;
+  }
+
+  if (Real->getOpcode() != Instruction::FMul ||
+      Imag->getOpcode() != Instruction::FMul) {
+    LLVM_DEBUG(dbgs() << "  - Real or imaginary instruction is not fmul\n");
+    return nullptr;
+  }
+
+  Instruction *R0 = dyn_cast<Instruction>(Real->getOperand(0));
+  Instruction *R1 = dyn_cast<Instruction>(Real->getOperand(1));
+  Instruction *I0 = dyn_cast<Instruction>(Imag->getOperand(0));
+  Instruction *I1 = dyn_cast<Instruction>(Imag->getOperand(1));
+  if (!R0 || !R1 || !I0 || !I1) {
+    LLVM_DEBUG(dbgs() << "  - Mul operand not Instruction\n");
+    return nullptr;
+  }
+
+  // A +/+ has a rotation of 0. If any of the operands are fneg, we flip the
+  // rotations and use the operand.
+  unsigned Negs = 0;
+  SmallVector<Instruction *> FNegs;
+  if (R0->getOpcode() == Instruction::FNeg ||
+      R1->getOpcode() == Instruction::FNeg) {
+    Negs |= 1;
+    if (R0->getOpcode() == Instruction::FNeg) {
+      FNegs.push_back(R0);
+      R0 = dyn_cast<Instruction>(R0->getOperand(0));
+    } else {
+      FNegs.push_back(R1);
+      R1 = dyn_cast<Instruction>(R1->getOperand(0));
+    }
+    if (!R0 || !R1)
+      return nullptr;
+  }
+  if (I0->getOpcode() == Instruction::FNeg ||
+      I1->getOpcode() == Instruction::FNeg) {
+    Negs |= 2;
+    Negs ^= 1;
+    if (I0->getOpcode() == Instruction::FNeg) {
+      FNegs.push_back(I0);
+      I0 = dyn_cast<Instruction>(I0->getOperand(0));
+    } else {
+      FNegs.push_back(I1);
+      I1 = dyn_cast<Instruction>(I1->getOperand(0));
+    }
+    if (!I0 || !I1)
+      return nullptr;
+  }
+
+  ComplexDeinterleavingRotation Rotation = (ComplexDeinterleavingRotation)Negs;
+
+  Instruction *CommonOperand;
+  Instruction *UncommonRealOp;
+  Instruction *UncommonImagOp;
+
+  if (R0 == I0 || R0 == I1) {
+    CommonOperand = R0;
+    UncommonRealOp = R1;
+  } else if (R1 == I0 || R1 == I1) {
+    CommonOperand = R1;
+    UncommonRealOp = R0;
+  } else {
+    LLVM_DEBUG(dbgs() << "  - No equal operand\n");
+    return nullptr;
+  }
+
+  UncommonImagOp = (CommonOperand == I0) ? I1 : I0;
+  if (Rotation == ComplexDeinterleavingRotation::Rotation_90 ||
+      Rotation == ComplexDeinterleavingRotation::Rotation_270)
+    std::swap(UncommonRealOp, UncommonImagOp);
+
+  // Between identifyPartialMul and here we need to have found a complete valid
+  // pair from the CommonOperand of each part.
+  if (Rotation == ComplexDeinterleavingRotation::Rotation_0 ||
+      Rotation == ComplexDeinterleavingRotation::Rotation_180)
+    PartialMatch.first = CommonOperand;
+  else
+    PartialMatch.second = CommonOperand;
+
+  if (!PartialMatch.first || !PartialMatch.second) {
+    LLVM_DEBUG(dbgs() << "  - Incomplete partial match\n");
+    return nullptr;
+  }
+
+  NodePtr CommonNode = identifyNode(PartialMatch.first, PartialMatch.second);
+  if (!CommonNode) {
+    LLVM_DEBUG(dbgs() << "  - No CommonNode identified\n");
+    return nullptr;
+  }
+
+  NodePtr UncommonNode = identifyNode(UncommonRealOp, UncommonImagOp);
+  if (!UncommonNode) {
+    LLVM_DEBUG(dbgs() << "  - No UncommonNode identified\n");
+    return nullptr;
+  }
+
+  NodePtr Node = prepareCompositeNode(
+      ComplexDeinterleavingOperation::CMulPartial, Real, Imag);
+  Node->Rotation = Rotation;
+  Node->addOperand(CommonNode);
+  Node->addOperand(UncommonNode);
+  Node->InternalInstructions.append(FNegs);
+  return submitCompositeNode(Node);
+}
+
+ComplexDeinterleavingGraph::NodePtr
+ComplexDeinterleavingGraph::identifyPartialMul(Instruction *Real,
+                                               Instruction *Imag) {
+  LLVM_DEBUG(dbgs() << "identifyPartialMul " << *Real << " / " << *Imag
+                    << "\n");
+  // Determine rotation
+  ComplexDeinterleavingRotation Rotation;
+  if (Real->getOpcode() == Instruction::FAdd &&
+      Imag->getOpcode() == Instruction::FAdd)
+    Rotation = ComplexDeinterleavingRotation::Rotation_0;
+  else if (Real->getOpcode() == Instruction::FSub &&
+           Imag->getOpcode() == Instruction::FAdd)
+    Rotation = ComplexDeinterleavingRotation::Rotation_90;
+  else if (Real->getOpcode() == Instruction::FSub &&
+           Imag->getOpcode() == Instruction::FSub)
+    Rotation = ComplexDeinterleavingRotation::Rotation_180;
+  else if (Real->getOpcode() == Instruction::FAdd &&
+           Imag->getOpcode() == Instruction::FSub)
+    Rotation = ComplexDeinterleavingRotation::Rotation_270;
+  else {
+    LLVM_DEBUG(dbgs() << "  - Unhandled rotation.\n");
+    return nullptr;
+  }
+
+  if (!Real->getFastMathFlags().allowContract() ||
+      !Imag->getFastMathFlags().allowContract()) {
+    LLVM_DEBUG(dbgs() << "  - Contract is missing from the FastMath flags.\n");
+    return nullptr;
+  }
+
+  Value *CR = Real->getOperand(0);
+  Instruction *RealMulI = dyn_cast<Instruction>(Real->getOperand(1));
+  if (!RealMulI)
+    return nullptr;
+  Value *CI = Imag->getOperand(0);
+  Instruction *ImagMulI = dyn_cast<Instruction>(Imag->getOperand(1));
+  if (!ImagMulI)
+    return nullptr;
+
+  if (!RealMulI->hasOneUse() || !ImagMulI->hasOneUse()) {
+    LLVM_DEBUG(dbgs() << "  - Mul instruction has multiple uses\n");
+    return nullptr;
+  }
+
+  Instruction *R0 = dyn_cast<Instruction>(RealMulI->getOperand(0));
+  Instruction *R1 = dyn_cast<Instruction>(RealMulI->getOperand(1));
+  Instruction *I0 = dyn_cast<Instruction>(ImagMulI->getOperand(0));
+  Instruction *I1 = dyn_cast<Instruction>(ImagMulI->getOperand(1));
+  if (!R0 || !R1 || !I0 || !I1) {
+    LLVM_DEBUG(dbgs() << "  - Mul operand not Instruction\n");
+    return nullptr;
+  }
+
+  Instruction *CommonOperand;
+  Instruction *UncommonRealOp;
+  Instruction *UncommonImagOp;
+
+  if (R0 == I0 || R0 == I1) {
+    CommonOperand = R0;
+    UncommonRealOp = R1;
+  } else if (R1 == I0 || R1 == I1) {
+    CommonOperand = R1;
+    UncommonRealOp = R0;
+  } else {
+    LLVM_DEBUG(dbgs() << "  - No equal operand\n");
+    return nullptr;
+  }
+
+  UncommonImagOp = (CommonOperand == I0) ? I1 : I0;
+  if (Rotation == ComplexDeinterleavingRotation::Rotation_90 ||
+      Rotation == ComplexDeinterleavingRotation::Rotation_270)
+    std::swap(UncommonRealOp, UncommonImagOp);
+
+  std::pair<Instruction *, Instruction *> PartialMatch(
+      (Rotation == ComplexDeinterleavingRotation::Rotation_0 ||
+       Rotation == ComplexDeinterleavingRotation::Rotation_180)
+          ? CommonOperand
+          : nullptr,
+      (Rotation == ComplexDeinterleavingRotation::Rotation_90 ||
+       Rotation == ComplexDeinterleavingRotation::Rotation_270)
+          ? CommonOperand
+          : nullptr);
+  NodePtr CNode = identifyNodeWithImplicitAdd(
+      cast<Instruction>(CR), cast<Instruction>(CI), PartialMatch);
+  if (!CNode) {
+    LLVM_DEBUG(dbgs() << "  - No cnode identified\n");
+    return nullptr;
+  }
+
+  NodePtr UncommonRes = identifyNode(UncommonRealOp, UncommonImagOp);
+  if (!UncommonRes) {
+    LLVM_DEBUG(dbgs() << "  - No UncommonRes identified\n");
+    return nullptr;
+  }
+
+  assert(PartialMatch.first && PartialMatch.second);
+  NodePtr CommonRes = identifyNode(PartialMatch.first, PartialMatch.second);
+  if (!CommonRes) {
+    LLVM_DEBUG(dbgs() << "  - No CommonRes identified\n");
+    return nullptr;
+  }
+
+  NodePtr Node = prepareCompositeNode(
+      ComplexDeinterleavingOperation::CMulPartial, Real, Imag);
+  Node->addInstruction(RealMulI);
+  Node->addInstruction(ImagMulI);
+  Node->Rotation = Rotation;
+  Node->addOperand(CommonRes);
+  Node->addOperand(UncommonRes);
+  Node->addOperand(CNode);
+  return submitCompositeNode(Node);
+}
+
+ComplexDeinterleavingGraph::NodePtr
+ComplexDeinterleavingGraph::identifyAdd(Instruction *Real, Instruction *Imag) {
+  LLVM_DEBUG(dbgs() << "identifyAdd " << *Real << " / " << *Imag << "\n");
+
+  // Determine rotation
+  ComplexDeinterleavingRotation Rotation;
+  if (Real->getOpcode() == Instruction::FSub &&
+      Imag->getOpcode() == Instruction::FAdd)
+    Rotation = ComplexDeinterleavingRotation::Rotation_90;
+  else if (Real->getOpcode() == Instruction::FAdd &&
+           Imag->getOpcode() == Instruction::FSub)
+    Rotation = ComplexDeinterleavingRotation::Rotation_270;
+  else {
+    LLVM_DEBUG(dbgs() << " - Unhandled case, rotation is not assigned.\n");
+    return nullptr;
+  }
+
+  auto *AR = cast<Instruction>(Real->getOperand(0));
+  auto *BI = cast<Instruction>(Real->getOperand(1));
+  auto *AI = cast<Instruction>(Imag->getOperand(0));
+  auto *BR = cast<Instruction>(Imag->getOperand(1));
+
+  NodePtr ResA = identifyNode(AR, AI);
+  if (!ResA) {
+    LLVM_DEBUG(dbgs() << " - AR/AI is not identified as a composite node.\n");
+    return nullptr;
+  }
+  NodePtr ResB = identifyNode(BR, BI);
+  if (!ResB) {
+    LLVM_DEBUG(dbgs() << " - BR/BI is not identified as a composite node.\n");
+    return nullptr;
+  }
+
+  NodePtr Node =
+      prepareCompositeNode(ComplexDeinterleavingOperation::CAdd, Real, Imag);
+  Node->Rotation = Rotation;
+  Node->addOperand(ResA);
+  Node->addOperand(ResB);
+  return submitCompositeNode(Node);
+}
+
+static bool isInstructionPairAdd(Instruction *A, Instruction *B) {
+  unsigned OpcA = A->getOpcode();
+  unsigned OpcB = B->getOpcode();
+  return (OpcA == Instruction::FSub && OpcB == Instruction::FAdd) ||
+         (OpcA == Instruction::FAdd && OpcB == Instruction::FSub);
+}
+
+static bool isInstructionPairMul(Instruction *A, Instruction *B) {
+  auto Pattern =
+      m_BinOp(m_FMul(m_Value(), m_Value()), m_FMul(m_Value(), m_Value()));
+
+  return match(A, Pattern) && match(B, Pattern);
+}
+
+ComplexDeinterleavingGraph::NodePtr
+ComplexDeinterleavingGraph::identifyNode(Instruction *Real, Instruction *Imag) {
+  LLVM_DEBUG(dbgs() << "identifyNode on " << *Real << " / " << *Imag << "\n");
+  if (NodePtr CN = getContainingComposite(Real, Imag)) {
+    LLVM_DEBUG(dbgs() << " - Folding to existing node\n");
+    return CN;
+  }
+
+  auto *RealShuffle = dyn_cast<ShuffleVectorInst>(Real);
+  auto *ImagShuffle = dyn_cast<ShuffleVectorInst>(Imag);
+  if (RealShuffle && ImagShuffle) {
+    Value *RealOp1 = RealShuffle->getOperand(1);
+    if (!isa<UndefValue>(RealOp1) && !isa<ConstantAggregateZero>(RealOp1)) {
+      LLVM_DEBUG(dbgs() << " - RealOp1 is not undef or zero.\n");
+      return nullptr;
+    }
+    Value *ImagOp1 = ImagShuffle->getOperand(1);
+    if (!isa<UndefValue>(ImagOp1) && !isa<ConstantAggregateZero>(ImagOp1)) {
+      LLVM_DEBUG(dbgs() << " - ImagOp1 is not undef or zero.\n");
+      return nullptr;
+    }
+
+    Value *RealOp0 = RealShuffle->getOperand(0);
+    Value *ImagOp0 = ImagShuffle->getOperand(0);
+
+    if (RealOp0 != ImagOp0) {
+      LLVM_DEBUG(dbgs() << " - Shuffle operands are not equal.\n");
+      return nullptr;
+    }
+
+    ArrayRef<int> RealMask = RealShuffle->getShuffleMask();
+    ArrayRef<int> ImagMask = ImagShuffle->getShuffleMask();
+    if (!isDeinterleavingMask(RealMask) || !isDeinterleavingMask(ImagMask)) {
+      LLVM_DEBUG(dbgs() << " - Masks are not deinterleaving.\n");
+      return nullptr;
+    }
+
+    if (RealMask[0] != 0 || ImagMask[0] != 1) {
+      LLVM_DEBUG(dbgs() << " - Masks do not have the correct initial value.\n");
+      return nullptr;
+    }
+
+    // Type checking, the shuffle type should be a vector type of the same
+    // scalar type, but half the size
+    auto CheckType = [&](ShuffleVectorInst *Shuffle) {
+      Value *Op = Shuffle->getOperand(0);
+      auto *ShuffleTy = cast<FixedVectorType>(Shuffle->getType());
+      auto *OpTy = cast<FixedVectorType>(Op->getType());
+
+      if (OpTy->getScalarType() != ShuffleTy->getScalarType())
+        return false;
+      if ((ShuffleTy->getNumElements() * 2) != OpTy->getNumElements())
+        return false;
+
+      return true;
+    };
+
+    auto CheckDeinterleavingShuffle = [&](ShuffleVectorInst *Shuffle) -> bool {
+      if (!CheckType(Shuffle))
+        return false;
+
+      ArrayRef<int> Mask = Shuffle->getShuffleMask();
+      int Last = *Mask.rbegin();
+
+      Value *Op = Shuffle->getOperand(0);
+      auto *OpTy = cast<FixedVectorType>(Op->getType());
+      int NumElements = OpTy->getNumElements();
+
+      // Ensure that the deinterleaving shuffle only pulls from the first
+      // shuffle operand.
+      return Last < NumElements;
+    };
+
+    if (RealShuffle->getType() != ImagShuffle->getType()) {
+      LLVM_DEBUG(dbgs() << " - Shuffle types aren't equal.\n");
+      return nullptr;
+    }
+    if (!CheckDeinterleavingShuffle(RealShuffle)) {
+      LLVM_DEBUG(dbgs() << " - RealShuffle is invalid type.\n");
+      return nullptr;
+    }
+    if (!CheckDeinterleavingShuffle(ImagShuffle)) {
+      LLVM_DEBUG(dbgs() << " - ImagShuffle is invalid type.\n");
+      return nullptr;
+    }
+
+    NodePtr PlaceholderNode =
+        prepareCompositeNode(llvm::ComplexDeinterleavingOperation::Shuffle,
+                             RealShuffle, ImagShuffle);
+    PlaceholderNode->ReplacementNode = RealShuffle->getOperand(0);
+    return submitCompositeNode(PlaceholderNode);
+  }
+  if (RealShuffle || ImagShuffle)
+    return nullptr;
+
+  auto *VTy = cast<FixedVectorType>(Real->getType());
+  auto *NewVTy =
+      FixedVectorType::get(VTy->getScalarType(), VTy->getNumElements() * 2);
+
+  if (TL->isComplexDeinterleavingOperationSupported(
+          ComplexDeinterleavingOperation::CMulPartial, NewVTy) &&
+      isInstructionPairMul(Real, Imag)) {
+    return identifyPartialMul(Real, Imag);
+  }
+
+  if (TL->isComplexDeinterleavingOperationSupported(
+          ComplexDeinterleavingOperation::CAdd, NewVTy) &&
+      isInstructionPairAdd(Real, Imag)) {
+    return identifyAdd(Real, Imag);
+  }
+
+  return nullptr;
+}
+
+bool ComplexDeinterleavingGraph::identifyNodes(Instruction *RootI) {
+  Instruction *Real;
+  Instruction *Imag;
+  if (!match(RootI, m_Shuffle(m_Instruction(Real), m_Instruction(Imag))))
+    return false;
+
+  RootValue = RootI;
+  AllInstructions.insert(RootI);
+  RootNode = identifyNode(Real, Imag);
+
+  LLVM_DEBUG({
+    Function *F = RootI->getFunction();
+    BasicBlock *B = RootI->getParent();
+    dbgs() << "Complex deinterleaving graph for " << F->getName()
+           << "::" << B->getName() << ".\n";
+    dump(dbgs());
+    dbgs() << "\n";
+  });
+
+  // Check all instructions have internal uses
+  for (const auto &Node : CompositeNodes) {
+    if (!Node->hasAllInternalUses(AllInstructions)) {
+      LLVM_DEBUG(dbgs() << "  - Invalid internal uses\n");
+      return false;
+    }
+  }
+  return RootNode != nullptr;
+}
+
+Value *ComplexDeinterleavingGraph::replaceNode(
+    ComplexDeinterleavingGraph::RawNodePtr Node) {
+  if (Node->ReplacementNode)
+    return Node->ReplacementNode;
+
+  Value *Input0 = replaceNode(Node->Operands[0]);
+  Value *Input1 = replaceNode(Node->Operands[1]);
+  Value *Accumulator =
+      Node->Operands.size() > 2 ? replaceNode(Node->Operands[2]) : nullptr;
+
+  assert(Input0->getType() == Input1->getType() &&
+         "Node inputs need to be of the same type");
+
+  Node->ReplacementNode = TL->createComplexDeinterleavingIR(
+      Node->Real, Node->Operation, Node->Rotation, Input0, Input1, Accumulator);
+
+  assert(Node->ReplacementNode && "Target failed to create Intrinsic call.");
+  NumComplexTransformations += 1;
+  return Node->ReplacementNode;
+}
+
+void ComplexDeinterleavingGraph::replaceNodes() {
+  Value *R = replaceNode(RootNode.get());
+  assert(R && "Unable to find replacement for RootValue");
+  RootValue->replaceAllUsesWith(R);
+}
+
+bool ComplexDeinterleavingCompositeNode::hasAllInternalUses(
+    SmallPtrSet<Instruction *, 16> &AllInstructions) {
+  if (Operation == ComplexDeinterleavingOperation::Shuffle)
+    return true;
+
+  for (auto *User : Real->users()) {
+    if (!AllInstructions.contains(cast<Instruction>(User)))
+      return false;
+  }
+  for (auto *User : Imag->users()) {
+    if (!AllInstructions.contains(cast<Instruction>(User)))
+      return false;
+  }
+  for (auto *I : InternalInstructions) {
+    for (auto *User : I->users()) {
+      if (!AllInstructions.contains(cast<Instruction>(User)))
+        return false;
+    }
+  }
+  return true;
+}
 No newline at end of file

llvm/lib/Target/ARM/ARMISelLowering.h

public:
 
     bool shouldFoldConstantShiftPairToMask(const SDNode *N,
                                            CombineLevel Level) const override;
 
     bool preferIncOfAddToSubOfNot(EVT VT) const override;
 
     bool shouldConvertFpToSat(unsigned Op, EVT FPVT, EVT VT) const override;
 
+    bool isComplexDeinterleavingSupported() const override;
+    bool isComplexDeinterleavingOperationSupported(
+        ComplexDeinterleavingOperation Operation, Type *Ty) const override;
+
+    Value *createComplexDeinterleavingIR(
+        Instruction *I, ComplexDeinterleavingOperation OperationType,
+        ComplexDeinterleavingRotation Rotation, Value *InputA, Value *InputB,
+        Value *Accumulator = nullptr) const override;
+
   protected:
     std::pair<const TargetRegisterClass *, uint8_t>
     findRepresentativeClass(const TargetRegisterInfo *TRI,
                             MVT VT) const override;
 
   private:
     /// Subtarget - Keep a pointer to the ARMSubtarget around so that we can
     /// make the right decision when generating code for different targets.

llvm/lib/Target/ARM/ARMISelLowering.cpp

for (auto *Exit : Exits)
           .addReg(NewVR);
   }
 }
 
 void ARMTargetLowering::finalizeLowering(MachineFunction &MF) const {
   MF.getFrameInfo().computeMaxCallFrameSize(MF);
   TargetLoweringBase::finalizeLowering(MF);
 }
+
+bool ARMTargetLowering::isComplexDeinterleavingSupported() const {
+  return Subtarget->hasMVEFloatOps();
+}
+
+bool ARMTargetLowering::isComplexDeinterleavingOperationSupported(
+    ComplexDeinterleavingOperation Operation, Type *Ty) const {
+  auto *VTy = dyn_cast<FixedVectorType>(Ty);
+  if (!VTy)
+    return false;
+
+  auto *ScalarTy = VTy->getScalarType();
+  unsigned NumElements = VTy->getNumElements();
+
+  unsigned VTyWidth = VTy->getScalarSizeInBits() * NumElements;
+  if (VTyWidth < 128 || !llvm::isPowerOf2_32(VTyWidth))
+    return false;
+
+  // Both VCADD and VCMUL/VCMLA support the same types, F16 and F32
+  return ScalarTy->isHalfTy() || ScalarTy->isFloatTy();
+}
+
+Value *ARMTargetLowering::createComplexDeinterleavingIR(
+    Instruction *I, ComplexDeinterleavingOperation OperationType,
+    ComplexDeinterleavingRotation Rotation, Value *InputA, Value *InputB,
+    Value *Accumulator) const {
+
+  FixedVectorType *Ty = cast<FixedVectorType>(InputA->getType());
+
+  IRBuilder<> B(I);
+
+  unsigned TyWidth = Ty->getScalarSizeInBits() * Ty->getNumElements();
+
+  assert(TyWidth >= 128 && "Width of vector type must be at least 128 bits");
+
+  if (TyWidth > 128) {
+    int Stride = Ty->getNumElements() / 2;
+    auto SplitSeq = llvm::seq<int>(0, Ty->getNumElements());
+    auto SplitSeqVec = llvm::to_vector(SplitSeq);
+    ArrayRef<int> LowerSplitMask(&SplitSeqVec[0], Stride);
+    ArrayRef<int> UpperSplitMask(&SplitSeqVec[Stride], Stride);
+
+    auto *LowerSplitA = B.CreateShuffleVector(InputA, LowerSplitMask);
+    auto *LowerSplitB = B.CreateShuffleVector(InputB, LowerSplitMask);
+    auto *UpperSplitA = B.CreateShuffleVector(InputA, UpperSplitMask);
+    auto *UpperSplitB = B.CreateShuffleVector(InputB, UpperSplitMask);
+    Value *LowerSplitAcc = nullptr;
+    Value *UpperSplitAcc = nullptr;
+
+    if (Accumulator) {
+      LowerSplitAcc = B.CreateShuffleVector(Accumulator, LowerSplitMask);
+      UpperSplitAcc = B.CreateShuffleVector(Accumulator, UpperSplitMask);
+    }
+
+    auto *LowerSplitInt = createComplexDeinterleavingIR(
+        I, OperationType, Rotation, LowerSplitA, LowerSplitB, LowerSplitAcc);
+    auto *UpperSplitInt = createComplexDeinterleavingIR(
+        I, OperationType, Rotation, UpperSplitA, UpperSplitB, UpperSplitAcc);
+
+    ArrayRef<int> JoinMask(&SplitSeqVec[0], Ty->getNumElements());
+    return B.CreateShuffleVector(LowerSplitInt, UpperSplitInt, JoinMask);
+  }
+
+  auto *IntTy = Type::getInt32Ty(B.getContext());
+
+  ConstantInt *ConstRotation = nullptr;
+  if (OperationType == ComplexDeinterleavingOperation::CMulPartial) {
+    ConstRotation = ConstantInt::get(IntTy, (int)Rotation);
+
+    if (Accumulator)
+      return B.CreateIntrinsic(Intrinsic::arm_mve_vcmlaq, Ty,
+                               {ConstRotation, Accumulator, InputB, InputA});
+    return B.CreateIntrinsic(Intrinsic::arm_mve_vcmulq, Ty,
+                             {ConstRotation, InputB, InputA});
+  }
+
+  if (OperationType == ComplexDeinterleavingOperation::CAdd) {
+    // 1 means the value is not halved.
+    auto *ConstHalving = ConstantInt::get(IntTy, 1);
+
+    if (Rotation == ComplexDeinterleavingRotation::Rotation_90)
+      ConstRotation = ConstantInt::get(IntTy, 0);
+    else if (Rotation == ComplexDeinterleavingRotation::Rotation_270)
+      ConstRotation = ConstantInt::get(IntTy, 1);
+
+    if (!ConstRotation)
+      return nullptr; // Invalid rotation for arm_mve_vcaddq
+
+    return B.CreateIntrinsic(Intrinsic::arm_mve_vcaddq, Ty,
+                             {ConstHalving, ConstRotation, InputA, InputB});
+  }
+
+  return nullptr;
+}

llvm/lib/Target/ARM/ARMTargetMachine.cpp

addPass(createCFGSimplificationPass(
         }));
 
   addPass(createMVEGatherScatterLoweringPass());
   addPass(createMVELaneInterleavingPass());
 
   TargetPassConfig::addIRPasses();
 
   // Run the parallel DSP pass.
-  if (getOptLevel() == CodeGenOpt::Aggressive) 
+  if (getOptLevel() == CodeGenOpt::Aggressive)
     addPass(createARMParallelDSPPass());
 
+  // Match complex arithmetic patterns
+  if (TM->getOptLevel() >= CodeGenOpt::Default)
+    addPass(createComplexDeinterleavingPass(TM));
+
   // Match interleaved memory accesses to ldN/stN intrinsics.
   if (TM->getOptLevel() != CodeGenOpt::None)
     addPass(createInterleavedAccessPass());
 
   // Add Control Flow Guard checks.
   if (TM->getTargetTriple().isOSWindows())
     addPass(createCFGuardCheckPass());
 
   if (TM->Options.JMCInstrument)
     addPass(createJMCInstrumenterPass());

llvm/test/CodeGen/ARM/O3-pipeline.ll

 ; RUN: llc -mtriple=arm -O3 -debug-pass=Structure < %s -o /dev/null 2>&1 | grep -v "Verify generated machine code" | FileCheck %s
 
 ; REQUIRES: asserts
 
 ; CHECK:       ModulePass Manager
 ; CHECK-NEXT:    Pre-ISel Intrinsic Lowering
 ; CHECK-NEXT:    FunctionPass Manager
 ; CHECK-NEXT:      Expand large div/rem
 ; CHECK-NEXT:      Expand Atomic instructions
 ; CHECK-NEXT:      Simplify the CFG

 ; CHECK-NEXT:      Scalarize Masked Memory Intrinsics
 ; CHECK-NEXT:      Expand reduction intrinsics
 ; CHECK-NEXT:      Natural Loop Information
 ; CHECK-NEXT:      TLS Variable Hoist
 ; CHECK-NEXT:      Scalar Evolution Analysis
 ; CHECK-NEXT:      Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:      Function Alias Analysis Results
 ; CHECK-NEXT:      Transform functions to use DSP intrinsics
+; CHECK-NEXT:      Complex Deinterleaving Pass
 ; CHECK-NEXT:      Interleaved Access Pass
 ; CHECK-NEXT:      Type Promotion
 ; CHECK-NEXT:      CodeGen Prepare
 ; CHECK-NEXT:      Dominator Tree Construction
 ; CHECK-NEXT:      Exception handling preparation
 ; CHECK-NEXT:      Merge internal globals
 ; CHECK-NEXT:      Natural Loop Information
 ; CHECK-NEXT:      Scalar Evolution Analysis

llvm/test/CodeGen/Thumb2/mve-complex-deinterleaving-f16-add.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s --mattr=+mve.fp -o - | FileCheck %s
+
+target triple = "thumbv8.1m.main-none-none-eabi"
+
+
+; Expected to not transform
+define arm_aapcs_vfpcc <2 x half> @complex_add_v2f16(<2 x half> %a, <2 x half> %b) {
+; CHECK-LABEL: complex_add_v2f16:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vmovx.f16 s2, s4
+; CHECK-NEXT:    vadd.f16 s2, s2, s0
+; CHECK-NEXT:    vmovx.f16 s0, s0
+; CHECK-NEXT:    vsub.f16 s0, s4, s0
+; CHECK-NEXT:    vins.f16 s0, s2
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real = shufflevector <2 x half> %a, <2 x half> zeroinitializer, <1 x i32> <i32 0>
+  %a.imag = shufflevector <2 x half> %a, <2 x half> zeroinitializer, <1 x i32> <i32 1>
+  %b.real = shufflevector <2 x half> %b, <2 x half> zeroinitializer, <1 x i32> <i32 0>
+  %b.imag = shufflevector <2 x half> %b, <2 x half> zeroinitializer, <1 x i32> <i32 1>
+  %0 = fsub fast <1 x half> %b.real, %a.imag
+  %1 = fadd fast <1 x half> %b.imag, %a.real
+  %interleaved.vec = shufflevector <1 x half> %0, <1 x half> %1, <2 x i32> <i32 0, i32 1>
+  ret <2 x half> %interleaved.vec
+}
+
+; Expected to not transform
+define arm_aapcs_vfpcc <4 x half> @complex_add_v4f16(<4 x half> %a, <4 x half> %b) {
+; CHECK-LABEL: complex_add_v4f16:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vmovx.f16 s12, s4
+; CHECK-NEXT:    vmovx.f16 s2, s5
+; CHECK-NEXT:    vmovx.f16 s8, s0
+; CHECK-NEXT:    vins.f16 s12, s2
+; CHECK-NEXT:    vmovx.f16 s2, s1
+; CHECK-NEXT:    vins.f16 s0, s1
+; CHECK-NEXT:    vins.f16 s8, s2
+; CHECK-NEXT:    vins.f16 s4, s5
+; CHECK-NEXT:    vadd.f16 q3, q3, q0
+; CHECK-NEXT:    vsub.f16 q0, q1, q2
+; CHECK-NEXT:    vmovx.f16 s1, s0
+; CHECK-NEXT:    vmovx.f16 s2, s12
+; CHECK-NEXT:    vins.f16 s0, s12
+; CHECK-NEXT:    vins.f16 s1, s2
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real = shufflevector <4 x half> %a, <4 x half> zeroinitializer, <2 x i32> <i32 0, i32 2>
+  %a.imag = shufflevector <4 x half> %a, <4 x half> zeroinitializer, <2 x i32> <i32 1, i32 3>
+  %b.real = shufflevector <4 x half> %b, <4 x half> zeroinitializer, <2 x i32> <i32 0, i32 2>
+  %b.imag = shufflevector <4 x half> %b, <4 x half> zeroinitializer, <2 x i32> <i32 1, i32 3>
+  %0 = fsub fast <2 x half> %b.real, %a.imag
+  %1 = fadd fast <2 x half> %b.imag, %a.real
+  %interleaved.vec = shufflevector <2 x half> %0, <2 x half> %1, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x half> %interleaved.vec
+}
+
+; Expected to transform
+define arm_aapcs_vfpcc <8 x half> @complex_add_v8f16(<8 x half> %a, <8 x half> %b) {
+; CHECK-LABEL: complex_add_v8f16:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vcadd.f16 q0, q1, q0, #90
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real = shufflevector <8 x half> %a, <8 x half> zeroinitializer, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+  %a.imag = shufflevector <8 x half> %a, <8 x half> zeroinitializer, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+  %b.real = shufflevector <8 x half> %b, <8 x half> zeroinitializer, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+  %b.imag = shufflevector <8 x half> %b, <8 x half> zeroinitializer, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+  %0 = fsub fast <4 x half> %b.real, %a.imag
+  %1 = fadd fast <4 x half> %b.imag, %a.real
+  %interleaved.vec = shufflevector <4 x half> %0, <4 x half> %1, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>
+  ret <8 x half> %interleaved.vec
+}
+
+; Expected to transform
+define arm_aapcs_vfpcc <16 x half> @complex_add_v16f16(<16 x half> %a, <16 x half> %b) {
+; CHECK-LABEL: complex_add_v16f16:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vcadd.f16 q0, q2, q0, #90
+; CHECK-NEXT:    vcadd.f16 q1, q3, q1, #90
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real = shufflevector <16 x half> %a, <16 x half> zeroinitializer, <8 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10, i32 12, i32 14>
+  %a.imag = shufflevector <16 x half> %a, <16 x half> zeroinitializer, <8 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15>
+  %b.real = shufflevector <16 x half> %b, <16 x half> zeroinitializer, <8 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10, i32 12, i32 14>
+  %b.imag = shufflevector <16 x half> %b, <16 x half> zeroinitializer, <8 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15>
+  %0 = fsub fast <8 x half> %b.real, %a.imag
+  %1 = fadd fast <8 x half> %b.imag, %a.real
+  %interleaved.vec = shufflevector <8 x half> %0, <8 x half> %1, <16 x i32> <i32 0, i32 8, i32 1, i32 9, i32 2, i32 10, i32 3, i32 11, i32 4, i32 12, i32 5, i32 13, i32 6, i32 14, i32 7, i32 15>
+  ret <16 x half> %interleaved.vec
+}
+
+; Expected to transform
+define arm_aapcs_vfpcc <32 x half> @complex_add_v32f16(<32 x half> %a, <32 x half> %b) {
+; CHECK-LABEL: complex_add_v32f16:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9}
+; CHECK-NEXT:    vpush {d8, d9}
+; CHECK-NEXT:    add r0, sp, #16
+; CHECK-NEXT:    vldrw.u32 q4, [r0]
+; CHECK-NEXT:    add r0, sp, #32
+; CHECK-NEXT:    vcadd.f16 q0, q4, q0, #90
+; CHECK-NEXT:    vldrw.u32 q4, [r0]
+; CHECK-NEXT:    add r0, sp, #48
+; CHECK-NEXT:    vcadd.f16 q1, q4, q1, #90
+; CHECK-NEXT:    vldrw.u32 q4, [r0]
+; CHECK-NEXT:    add r0, sp, #64
+; CHECK-NEXT:    vcadd.f16 q2, q4, q2, #90
+; CHECK-NEXT:    vldrw.u32 q4, [r0]
+; CHECK-NEXT:    vcadd.f16 q3, q4, q3, #90
+; CHECK-NEXT:    vpop {d8, d9}
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real = shufflevector <32 x half> %a, <32 x half> zeroinitializer, <16 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10, i32 12, i32 14, i32 16, i32 18, i32 20, i32 22, i32 24, i32 26, i32 28, i32 30>
+  %a.imag = shufflevector <32 x half> %a, <32 x half> zeroinitializer, <16 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15, i32 17, i32 19, i32 21, i32 23, i32 25, i32 27, i32 29, i32 31>
+  %b.real = shufflevector <32 x half> %b, <32 x half> zeroinitializer, <16 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10, i32 12, i32 14, i32 16, i32 18, i32 20, i32 22, i32 24, i32 26, i32 28, i32 30>
+  %b.imag = shufflevector <32 x half> %b, <32 x half> zeroinitializer, <16 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15, i32 17, i32 19, i32 21, i32 23, i32 25, i32 27, i32 29, i32 31>
+  %0 = fsub fast <16 x half> %b.real, %a.imag
+  %1 = fadd fast <16 x half> %b.imag, %a.real
+  %interleaved.vec = shufflevector <16 x half> %0, <16 x half> %1, <32 x i32> <i32 0, i32 16, i32 1, i32 17, i32 2, i32 18, i32 3, i32 19, i32 4, i32 20, i32 5, i32 21, i32 6, i32 22, i32 7, i32 23, i32 8, i32 24, i32 9, i32 25, i32 10, i32 26, i32 11, i32 27, i32 12, i32 28, i32 13, i32 29, i32 14, i32 30, i32 15, i32 31>
+  ret <32 x half> %interleaved.vec
+}

llvm/test/CodeGen/Thumb2/mve-complex-deinterleaving-f16-mul.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s --mattr=+mve.fp -o - | FileCheck %s
+
+target triple = "thumbv8.1m.main-none-none-eabi"
+
+; Expected to not transform
+define arm_aapcs_vfpcc <2 x half> @complex_mul_v2f16(<2 x half> %a, <2 x half> %b) {
+; CHECK-LABEL: complex_mul_v2f16:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vmovx.f16 s2, s4
+; CHECK-NEXT:    vmovx.f16 s8, s0
+; CHECK-NEXT:    vmul.f16 s6, s2, s0
+; CHECK-NEXT:    vfma.f16 s6, s4, s8
+; CHECK-NEXT:    vmul.f16 s8, s8, s2
+; CHECK-NEXT:    vfnms.f16 s8, s4, s0
+; CHECK-NEXT:    vins.f16 s8, s6
+; CHECK-NEXT:    vmov q0, q2
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real   = shufflevector <2 x half> %a, <2 x half> poison, <1 x i32> <i32 0>
+  %a.imag = shufflevector <2 x half> %a, <2 x half> poison, <1 x i32> <i32 1>
+  %b.real = shufflevector <2 x half> %b, <2 x half> poison, <1 x i32> <i32 0>
+  %b.imag = shufflevector <2 x half> %b, <2 x half> poison, <1 x i32> <i32 1>
+  %0 = fmul fast <1 x half> %b.imag, %a.real
+  %1 = fmul fast <1 x half> %b.real, %a.imag
+  %2 = fadd fast <1 x half> %1, %0
+  %3 = fmul fast <1 x half> %b.real, %a.real
+  %4 = fmul fast <1 x half> %a.imag, %b.imag
+  %5 = fsub fast <1 x half> %3, %4
+  %interleaved.vec = shufflevector <1 x half> %5, <1 x half> %2, <2 x i32> <i32 0, i32 1>
+  ret <2 x half> %interleaved.vec
+}
+
+; Expected to not transform
+define arm_aapcs_vfpcc <4 x half> @complex_mul_v4f16(<4 x half> %a, <4 x half> %b) {
+; CHECK-LABEL: complex_mul_v4f16:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9}
+; CHECK-NEXT:    vpush {d8, d9}
+; CHECK-NEXT:    vmovx.f16 s8, s0
+; CHECK-NEXT:    vmovx.f16 s2, s1
+; CHECK-NEXT:    vins.f16 s8, s2
+; CHECK-NEXT:    vmovx.f16 s12, s4
+; CHECK-NEXT:    vmovx.f16 s2, s5
+; CHECK-NEXT:    vins.f16 s0, s1
+; CHECK-NEXT:    vins.f16 s12, s2
+; CHECK-NEXT:    vins.f16 s4, s5
+; CHECK-NEXT:    vmul.f16 q4, q3, q0
+; CHECK-NEXT:    vfma.f16 q4, q1, q2
+; CHECK-NEXT:    vmul.f16 q2, q2, q3
+; CHECK-NEXT:    vneg.f16 q2, q2
+; CHECK-NEXT:    vfma.f16 q2, q1, q0
+; CHECK-NEXT:    vmovx.f16 s0, s16
+; CHECK-NEXT:    vmovx.f16 s9, s8
+; CHECK-NEXT:    vins.f16 s8, s16
+; CHECK-NEXT:    vins.f16 s9, s0
+; CHECK-NEXT:    vmov q0, q2
+; CHECK-NEXT:    vpop {d8, d9}
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real   = shufflevector <4 x half> %a, <4 x half> poison, <2 x i32> <i32 0, i32 2>
+  %a.imag = shufflevector <4 x half> %a, <4 x half> poison, <2 x i32> <i32 1, i32 3>
+  %b.real = shufflevector <4 x half> %b, <4 x half> poison, <2 x i32> <i32 0, i32 2>
+  %b.imag = shufflevector <4 x half> %b, <4 x half> poison, <2 x i32> <i32 1, i32 3>
+  %0 = fmul fast <2 x half> %b.imag, %a.real
+  %1 = fmul fast <2 x half> %b.real, %a.imag
+  %2 = fadd fast <2 x half> %1, %0
+  %3 = fmul fast <2 x half> %b.real, %a.real
+  %4 = fmul fast <2 x half> %a.imag, %b.imag
+  %5 = fsub fast <2 x half> %3, %4
+  %interleaved.vec = shufflevector <2 x half> %5, <2 x half> %2, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x half> %interleaved.vec
+}
+
+; Expected to transform
+define arm_aapcs_vfpcc <8 x half> @complex_mul_v8f16(<8 x half> %a, <8 x half> %b) {
+; CHECK-LABEL: complex_mul_v8f16:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vcmul.f16 q2, q0, q1, #0
+; CHECK-NEXT:    vcmla.f16 q2, q0, q1, #90
+; CHECK-NEXT:    vmov q0, q2
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real   = shufflevector <8 x half> %a, <8 x half> poison, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+  %a.imag = shufflevector <8 x half> %a, <8 x half> poison, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+  %b.real = shufflevector <8 x half> %b, <8 x half> poison, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+  %b.imag = shufflevector <8 x half> %b, <8 x half> poison, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+  %0 = fmul fast <4 x half> %b.imag, %a.real
+  %1 = fmul fast <4 x half> %b.real, %a.imag
+  %2 = fadd fast <4 x half> %1, %0
+  %3 = fmul fast <4 x half> %b.real, %a.real
+  %4 = fmul fast <4 x half> %a.imag, %b.imag
+  %5 = fsub fast <4 x half> %3, %4
+  %interleaved.vec = shufflevector <4 x half> %5, <4 x half> %2, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>
+  ret <8 x half> %interleaved.vec
+}
+
+; Expected to transform
+define arm_aapcs_vfpcc <16 x half> @complex_mul_v16f16(<16 x half> %a, <16 x half> %b) {
+; CHECK-LABEL: complex_mul_v16f16:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9}
+; CHECK-NEXT:    vpush {d8, d9}
+; CHECK-NEXT:    vcmul.f16 q4, q0, q2, #0
+; CHECK-NEXT:    vcmla.f16 q4, q0, q2, #90
+; CHECK-NEXT:    vcmul.f16 q2, q1, q3, #0
+; CHECK-NEXT:    vcmla.f16 q2, q1, q3, #90
+; CHECK-NEXT:    vmov q0, q4
+; CHECK-NEXT:    vmov q1, q2
+; CHECK-NEXT:    vpop {d8, d9}
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real   = shufflevector <16 x half> %a, <16 x half> poison, <8 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10, i32 12, i32 14>
+  %a.imag = shufflevector <16 x half> %a, <16 x half> poison, <8 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15>
+  %b.real = shufflevector <16 x half> %b, <16 x half> poison, <8 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10, i32 12, i32 14>
+  %b.imag = shufflevector <16 x half> %b, <16 x half> poison, <8 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15>
+  %0 = fmul fast <8 x half> %b.imag, %a.real
+  %1 = fmul fast <8 x half> %b.real, %a.imag
+  %2 = fadd fast <8 x half> %1, %0
+  %3 = fmul fast <8 x half> %b.real, %a.real
+  %4 = fmul fast <8 x half> %a.imag, %b.imag
+  %5 = fsub fast <8 x half> %3, %4
+  %interleaved.vec = shufflevector <8 x half> %5, <8 x half> %2, <16 x i32> <i32 0, i32 8, i32 1, i32 9, i32 2, i32 10, i32 3, i32 11, i32 4, i32 12, i32 5, i32 13, i32 6, i32 14, i32 7, i32 15>
+  ret <16 x half> %interleaved.vec
+}
+
+; Expected to transform
+define arm_aapcs_vfpcc <32 x half> @complex_mul_v32f16(<32 x half> %a, <32 x half> %b) {
+; CHECK-LABEL: complex_mul_v32f16:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9, d10, d11, d12, d13}
+; CHECK-NEXT:    vpush {d8, d9, d10, d11, d12, d13}
+; CHECK-NEXT:    add r0, sp, #48
+; CHECK-NEXT:    vmov q4, q0
+; CHECK-NEXT:    vldrw.u32 q5, [r0]
+; CHECK-NEXT:    add r0, sp, #64
+; CHECK-NEXT:    vcmul.f16 q0, q0, q5, #0
+; CHECK-NEXT:    vcmla.f16 q0, q4, q5, #90
+; CHECK-NEXT:    vldrw.u32 q5, [r0]
+; CHECK-NEXT:    add r0, sp, #80
+; CHECK-NEXT:    vcmul.f16 q4, q1, q5, #0
+; CHECK-NEXT:    vcmla.f16 q4, q1, q5, #90
+; CHECK-NEXT:    vldrw.u32 q1, [r0]
+; CHECK-NEXT:    add r0, sp, #96
+; CHECK-NEXT:    vcmul.f16 q5, q2, q1, #0
+; CHECK-NEXT:    vcmla.f16 q5, q2, q1, #90
+; CHECK-NEXT:    vldrw.u32 q1, [r0]
+; CHECK-NEXT:    vmov q2, q5
+; CHECK-NEXT:    vcmul.f16 q6, q3, q1, #0
+; CHECK-NEXT:    vcmla.f16 q6, q3, q1, #90
+; CHECK-NEXT:    vmov q1, q4
+; CHECK-NEXT:    vmov q3, q6
+; CHECK-NEXT:    vpop {d8, d9, d10, d11, d12, d13}
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real   = shufflevector <32 x half> %a, <32 x half> poison, <16 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10, i32 12, i32 14, i32 16, i32 18, i32 20, i32 22, i32 24, i32 26, i32 28, i32 30>
+  %a.imag = shufflevector <32 x half> %a, <32 x half> poison, <16 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15, i32 17, i32 19, i32 21, i32 23, i32 25, i32 27, i32 29, i32 31>
+  %b.real = shufflevector <32 x half> %b, <32 x half> poison, <16 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10, i32 12, i32 14, i32 16, i32 18, i32 20, i32 22, i32 24, i32 26, i32 28, i32 30>
+  %b.imag = shufflevector <32 x half> %b, <32 x half> poison, <16 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15, i32 17, i32 19, i32 21, i32 23, i32 25, i32 27, i32 29, i32 31>
+  %0 = fmul fast <16 x half> %b.imag, %a.real
+  %1 = fmul fast <16 x half> %b.real, %a.imag
+  %2 = fadd fast <16 x half> %1, %0
+  %3 = fmul fast <16 x half> %b.real, %a.real
+  %4 = fmul fast <16 x half> %a.imag, %b.imag
+  %5 = fsub fast <16 x half> %3, %4
+  %interleaved.vec = shufflevector <16 x half> %5, <16 x half> %2, <32 x i32> <i32 0, i32 16, i32 1, i32 17, i32 2, i32 18, i32 3, i32 19, i32 4, i32 20, i32 5, i32 21, i32 6, i32 22, i32 7, i32 23, i32 8, i32 24, i32 9, i32 25, i32 10, i32 26, i32 11, i32 27, i32 12, i32 28, i32 13, i32 29, i32 14, i32 30, i32 15, i32 31>
+  ret <32 x half> %interleaved.vec
+}

llvm/test/CodeGen/Thumb2/mve-complex-deinterleaving-f32-add.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s --mattr=+mve.fp -o - | FileCheck %s
+
+target triple = "thumbv8.1m.main-none-none-eabi"
+
+
+; Expected to not transform
+define arm_aapcs_vfpcc <2 x float> @complex_add_v2f32(<2 x float> %a, <2 x float> %b) {
+; CHECK-LABEL: complex_add_v2f32:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vadd.f32 s5, s5, s0
+; CHECK-NEXT:    vsub.f32 s4, s4, s1
+; CHECK-NEXT:    vmov q0, q1
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real = shufflevector <2 x float> %a, <2 x float> zeroinitializer, <1 x i32> <i32 0>
+  %a.imag = shufflevector <2 x float> %a, <2 x float> zeroinitializer, <1 x i32> <i32 1>
+  %b.real = shufflevector <2 x float> %b, <2 x float> zeroinitializer, <1 x i32> <i32 0>
+  %b.imag = shufflevector <2 x float> %b, <2 x float> zeroinitializer, <1 x i32> <i32 1>
+  %0 = fsub fast <1 x float> %b.real, %a.imag
+  %1 = fadd fast <1 x float> %b.imag, %a.real
+  %interleaved.vec = shufflevector <1 x float> %0, <1 x float> %1, <2 x i32> <i32 0, i32 1>
+  ret <2 x float> %interleaved.vec
+}
+
+; Expected to transform
+define arm_aapcs_vfpcc <4 x float> @complex_add_v4f32(<4 x float> %a, <4 x float> %b) {
+; CHECK-LABEL: complex_add_v4f32:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vcadd.f32 q2, q1, q0, #90
+; CHECK-NEXT:    vmov q0, q2
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real = shufflevector <4 x float> %a, <4 x float> zeroinitializer, <2 x i32> <i32 0, i32 2>
+  %a.imag = shufflevector <4 x float> %a, <4 x float> zeroinitializer, <2 x i32> <i32 1, i32 3>
+  %b.real = shufflevector <4 x float> %b, <4 x float> zeroinitializer, <2 x i32> <i32 0, i32 2>
+  %b.imag = shufflevector <4 x float> %b, <4 x float> zeroinitializer, <2 x i32> <i32 1, i32 3>
+  %0 = fsub fast <2 x float> %b.real, %a.imag
+  %1 = fadd fast <2 x float> %b.imag, %a.real
+  %interleaved.vec = shufflevector <2 x float> %0, <2 x float> %1, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}
+
+; Expected to transform
+define arm_aapcs_vfpcc <8 x float> @complex_add_v8f32(<8 x float> %a, <8 x float> %b) {
+; CHECK-LABEL: complex_add_v8f32:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9}
+; CHECK-NEXT:    vpush {d8, d9}
+; CHECK-NEXT:    vcadd.f32 q4, q2, q0, #90
+; CHECK-NEXT:    vcadd.f32 q2, q3, q1, #90
+; CHECK-NEXT:    vmov q0, q4
+; CHECK-NEXT:    vmov q1, q2
+; CHECK-NEXT:    vpop {d8, d9}
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real = shufflevector <8 x float> %a, <8 x float> zeroinitializer, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+  %a.imag = shufflevector <8 x float> %a, <8 x float> zeroinitializer, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+  %b.real = shufflevector <8 x float> %b, <8 x float> zeroinitializer, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+  %b.imag = shufflevector <8 x float> %b, <8 x float> zeroinitializer, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+  %0 = fsub fast <4 x float> %b.real, %a.imag
+  %1 = fadd fast <4 x float> %b.imag, %a.real
+  %interleaved.vec = shufflevector <4 x float> %0, <4 x float> %1, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>
+  ret <8 x float> %interleaved.vec
+}
+
+; Expected to transform
+define arm_aapcs_vfpcc <16 x float> @complex_add_v16f32(<16 x float> %a, <16 x float> %b) {
+; CHECK-LABEL: complex_add_v16f32:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9, d10, d11, d12, d13, d14, d15}
+; CHECK-NEXT:    vpush {d8, d9, d10, d11, d12, d13, d14, d15}
+; CHECK-NEXT:    add r3, sp, #64
+; CHECK-NEXT:    add r2, sp, #80
+; CHECK-NEXT:    vldrw.u32 q5, [r3]
+; CHECK-NEXT:    add r1, sp, #96
+; CHECK-NEXT:    add r0, sp, #112
+; CHECK-NEXT:    vcadd.f32 q4, q5, q0, #90
+; CHECK-NEXT:    vldrw.u32 q0, [r2]
+; CHECK-NEXT:    vcadd.f32 q5, q0, q1, #90
+; CHECK-NEXT:    vldrw.u32 q0, [r1]
+; CHECK-NEXT:    vmov q1, q5
+; CHECK-NEXT:    vcadd.f32 q6, q0, q2, #90
+; CHECK-NEXT:    vldrw.u32 q0, [r0]
+; CHECK-NEXT:    vmov q2, q6
+; CHECK-NEXT:    vcadd.f32 q7, q0, q3, #90
+; CHECK-NEXT:    vmov q0, q4
+; CHECK-NEXT:    vmov q3, q7
+; CHECK-NEXT:    vpop {d8, d9, d10, d11, d12, d13, d14, d15}
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real = shufflevector <16 x float> %a, <16 x float> zeroinitializer, <8 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10, i32 12, i32 14>
+  %a.imag = shufflevector <16 x float> %a, <16 x float> zeroinitializer, <8 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15>
+  %b.real = shufflevector <16 x float> %b, <16 x float> zeroinitializer, <8 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10, i32 12, i32 14>
+  %b.imag = shufflevector <16 x float> %b, <16 x float> zeroinitializer, <8 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15>
+  %0 = fsub fast <8 x float> %b.real, %a.imag
+  %1 = fadd fast <8 x float> %b.imag, %a.real
+  %interleaved.vec = shufflevector <8 x float> %0, <8 x float> %1, <16 x i32> <i32 0, i32 8, i32 1, i32 9, i32 2, i32 10, i32 3, i32 11, i32 4, i32 12, i32 5, i32 13, i32 6, i32 14, i32 7, i32 15>
+  ret <16 x float> %interleaved.vec
+}

llvm/test/CodeGen/Thumb2/mve-complex-deinterleaving-f32-mul.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s --mattr=+mve.fp -o - | FileCheck %s
+
+target triple = "thumbv8.1m.main-none-none-eabi"
+
+; Expected to not transform
+define arm_aapcs_vfpcc <2 x float> @complex_mul_v2f32(<2 x float> %a, <2 x float> %b) {
+; CHECK-LABEL: complex_mul_v2f32:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vmul.f32 s9, s5, s0
+; CHECK-NEXT:    vmul.f32 s8, s1, s5
+; CHECK-NEXT:    vfma.f32 s9, s4, s1
+; CHECK-NEXT:    vfnms.f32 s8, s4, s0
+; CHECK-NEXT:    vmov q0, q2
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real   = shufflevector <2 x float> %a, <2 x float> poison, <1 x i32> <i32 0>
+  %a.imag = shufflevector <2 x float> %a, <2 x float> poison, <1 x i32> <i32 1>
+  %b.real = shufflevector <2 x float> %b, <2 x float> poison, <1 x i32> <i32 0>
+  %b.imag = shufflevector <2 x float> %b, <2 x float> poison, <1 x i32> <i32 1>
+  %0 = fmul fast <1 x float> %b.imag, %a.real
+  %1 = fmul fast <1 x float> %b.real, %a.imag
+  %2 = fadd fast <1 x float> %1, %0
+  %3 = fmul fast <1 x float> %b.real, %a.real
+  %4 = fmul fast <1 x float> %a.imag, %b.imag
+  %5 = fsub fast <1 x float> %3, %4
+  %interleaved.vec = shufflevector <1 x float> %5, <1 x float> %2, <2 x i32> <i32 0, i32 1>
+  ret <2 x float> %interleaved.vec
+}
+
+; Expected to transform
+define arm_aapcs_vfpcc <4 x float> @complex_mul_v4f32(<4 x float> %a, <4 x float> %b) {
+; CHECK-LABEL: complex_mul_v4f32:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vcmul.f32 q2, q0, q1, #0
+; CHECK-NEXT:    vcmla.f32 q2, q0, q1, #90
+; CHECK-NEXT:    vmov q0, q2
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real   = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %a.imag = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %b.real = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %b.imag = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %0 = fmul fast <2 x float> %b.imag, %a.real
+  %1 = fmul fast <2 x float> %b.real, %a.imag
+  %2 = fadd fast <2 x float> %1, %0
+  %3 = fmul fast <2 x float> %b.real, %a.real
+  %4 = fmul fast <2 x float> %a.imag, %b.imag
+  %5 = fsub fast <2 x float> %3, %4
+  %interleaved.vec = shufflevector <2 x float> %5, <2 x float> %2, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}
+
+; Expected to transform
+define arm_aapcs_vfpcc <8 x float> @complex_mul_v8f32(<8 x float> %a, <8 x float> %b) {
+; CHECK-LABEL: complex_mul_v8f32:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9}
+; CHECK-NEXT:    vpush {d8, d9}
+; CHECK-NEXT:    vcmul.f32 q4, q0, q2, #0
+; CHECK-NEXT:    vcmla.f32 q4, q0, q2, #90
+; CHECK-NEXT:    vcmul.f32 q2, q1, q3, #0
+; CHECK-NEXT:    vcmla.f32 q2, q1, q3, #90
+; CHECK-NEXT:    vmov q0, q4
+; CHECK-NEXT:    vmov q1, q2
+; CHECK-NEXT:    vpop {d8, d9}
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real   = shufflevector <8 x float> %a, <8 x float> poison, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+  %a.imag = shufflevector <8 x float> %a, <8 x float> poison, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+  %b.real = shufflevector <8 x float> %b, <8 x float> poison, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+  %b.imag = shufflevector <8 x float> %b, <8 x float> poison, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+  %0 = fmul fast <4 x float> %b.imag, %a.real
+  %1 = fmul fast <4 x float> %b.real, %a.imag
+  %2 = fadd fast <4 x float> %1, %0
+  %3 = fmul fast <4 x float> %b.real, %a.real
+  %4 = fmul fast <4 x float> %a.imag, %b.imag
+  %5 = fsub fast <4 x float> %3, %4
+  %interleaved.vec = shufflevector <4 x float> %5, <4 x float> %2, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>
+  ret <8 x float> %interleaved.vec
+}
+
+; Expected to transform
+define arm_aapcs_vfpcc <16 x float> @complex_mul_v16f32(<16 x float> %a, <16 x float> %b) {
+; CHECK-LABEL: complex_mul_v16f32:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9, d10, d11, d12, d13, d14, d15}
+; CHECK-NEXT:    vpush {d8, d9, d10, d11, d12, d13, d14, d15}
+; CHECK-NEXT:    add r3, sp, #64
+; CHECK-NEXT:    add r2, sp, #80
+; CHECK-NEXT:    vldrw.u32 q5, [r3]
+; CHECK-NEXT:    add r1, sp, #96
+; CHECK-NEXT:    add r0, sp, #112
+; CHECK-NEXT:    vcmul.f32 q4, q0, q5, #0
+; CHECK-NEXT:    vcmla.f32 q4, q0, q5, #90
+; CHECK-NEXT:    vldrw.u32 q0, [r2]
+; CHECK-NEXT:    vcmul.f32 q5, q1, q0, #0
+; CHECK-NEXT:    vcmla.f32 q5, q1, q0, #90
+; CHECK-NEXT:    vldrw.u32 q0, [r1]
+; CHECK-NEXT:    vmov q1, q5
+; CHECK-NEXT:    vcmul.f32 q6, q2, q0, #0
+; CHECK-NEXT:    vcmla.f32 q6, q2, q0, #90
+; CHECK-NEXT:    vldrw.u32 q0, [r0]
+; CHECK-NEXT:    vmov q2, q6
+; CHECK-NEXT:    vcmul.f32 q7, q3, q0, #0
+; CHECK-NEXT:    vcmla.f32 q7, q3, q0, #90
+; CHECK-NEXT:    vmov q0, q4
+; CHECK-NEXT:    vmov q3, q7
+; CHECK-NEXT:    vpop {d8, d9, d10, d11, d12, d13, d14, d15}
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real   = shufflevector <16 x float> %a, <16 x float> poison, <8 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10, i32 12, i32 14>
+  %a.imag = shufflevector <16 x float> %a, <16 x float> poison, <8 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15>
+  %b.real = shufflevector <16 x float> %b, <16 x float> poison, <8 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10, i32 12, i32 14>
+  %b.imag = shufflevector <16 x float> %b, <16 x float> poison, <8 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15>
+  %0 = fmul fast <8 x float> %b.imag, %a.real
+  %1 = fmul fast <8 x float> %b.real, %a.imag
+  %2 = fadd fast <8 x float> %1, %0
+  %3 = fmul fast <8 x float> %b.real, %a.real
+  %4 = fmul fast <8 x float> %a.imag, %b.imag
+  %5 = fsub fast <8 x float> %3, %4
+  %interleaved.vec = shufflevector <8 x float> %5, <8 x float> %2, <16 x i32> <i32 0, i32 8, i32 1, i32 9, i32 2, i32 10, i32 3, i32 11, i32 4, i32 12, i32 5, i32 13, i32 6, i32 14, i32 7, i32 15>
+  ret <16 x float> %interleaved.vec
+}

llvm/test/CodeGen/Thumb2/mve-complex-deinterleaving-f64-add.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s --mattr=+mve.fp,+fp64 -o - | FileCheck %s
+
+target triple = "thumbv8.1m.main-none-none-eabi"
+
+
+; Expected to not transform
+define arm_aapcs_vfpcc <2 x double> @complex_add_v2f64(<2 x double> %a, <2 x double> %b) {
+; CHECK-LABEL: complex_add_v2f64:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vadd.f64 d3, d3, d0
+; CHECK-NEXT:    vsub.f64 d2, d2, d1
+; CHECK-NEXT:    vmov q0, q1
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real = shufflevector <2 x double> %a, <2 x double> zeroinitializer, <1 x i32> <i32 0>
+  %a.imag = shufflevector <2 x double> %a, <2 x double> zeroinitializer, <1 x i32> <i32 1>
+  %b.real = shufflevector <2 x double> %b, <2 x double> zeroinitializer, <1 x i32> <i32 0>
+  %b.imag = shufflevector <2 x double> %b, <2 x double> zeroinitializer, <1 x i32> <i32 1>
+  %0 = fsub fast <1 x double> %b.real, %a.imag
+  %1 = fadd fast <1 x double> %b.imag, %a.real
+  %interleaved.vec = shufflevector <1 x double> %0, <1 x double> %1, <2 x i32> <i32 0, i32 1>
+  ret <2 x double> %interleaved.vec
+}
+
+; Expected to not transform
+define arm_aapcs_vfpcc <4 x double> @complex_add_v4f64(<4 x double> %a, <4 x double> %b) {
+; CHECK-LABEL: complex_add_v4f64:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vadd.f64 d5, d5, d0
+; CHECK-NEXT:    vsub.f64 d4, d4, d1
+; CHECK-NEXT:    vadd.f64 d7, d7, d2
+; CHECK-NEXT:    vmov q0, q2
+; CHECK-NEXT:    vsub.f64 d6, d6, d3
+; CHECK-NEXT:    vmov q1, q3
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real = shufflevector <4 x double> %a, <4 x double> zeroinitializer, <2 x i32> <i32 0, i32 2>
+  %a.imag = shufflevector <4 x double> %a, <4 x double> zeroinitializer, <2 x i32> <i32 1, i32 3>
+  %b.real = shufflevector <4 x double> %b, <4 x double> zeroinitializer, <2 x i32> <i32 0, i32 2>
+  %b.imag = shufflevector <4 x double> %b, <4 x double> zeroinitializer, <2 x i32> <i32 1, i32 3>
+  %0 = fsub fast <2 x double> %b.real, %a.imag
+  %1 = fadd fast <2 x double> %b.imag, %a.real
+  %interleaved.vec = shufflevector <2 x double> %0, <2 x double> %1, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x double> %interleaved.vec
+}
+
+; Expected to not transform
+define arm_aapcs_vfpcc <8 x double> @complex_add_v8f64(<8 x double> %a, <8 x double> %b) {
+; CHECK-LABEL: complex_add_v8f64:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9, d10, d11}
+; CHECK-NEXT:    vpush {d8, d9, d10, d11}
+; CHECK-NEXT:    add r0, sp, #32
+; CHECK-NEXT:    vmov q4, q1
+; CHECK-NEXT:    vmov q1, q0
+; CHECK-NEXT:    vldrw.u32 q0, [r0]
+; CHECK-NEXT:    add r0, sp, #48
+; CHECK-NEXT:    vadd.f64 d1, d1, d2
+; CHECK-NEXT:    vsub.f64 d0, d0, d3
+; CHECK-NEXT:    vldrw.u32 q1, [r0]
+; CHECK-NEXT:    add r0, sp, #64
+; CHECK-NEXT:    vadd.f64 d3, d3, d8
+; CHECK-NEXT:    vsub.f64 d2, d2, d9
+; CHECK-NEXT:    vldrw.u32 q4, [r0]
+; CHECK-NEXT:    add r0, sp, #80
+; CHECK-NEXT:    vadd.f64 d9, d9, d4
+; CHECK-NEXT:    vsub.f64 d8, d8, d5
+; CHECK-NEXT:    vldrw.u32 q2, [r0]
+; CHECK-NEXT:    vadd.f64 d11, d5, d6
+; CHECK-NEXT:    vsub.f64 d10, d4, d7
+; CHECK-NEXT:    vmov q2, q4
+; CHECK-NEXT:    vmov q3, q5
+; CHECK-NEXT:    vpop {d8, d9, d10, d11}
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real = shufflevector <8 x double> %a, <8 x double> zeroinitializer, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+  %a.imag = shufflevector <8 x double> %a, <8 x double> zeroinitializer, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+  %b.real = shufflevector <8 x double> %b, <8 x double> zeroinitializer, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+  %b.imag = shufflevector <8 x double> %b, <8 x double> zeroinitializer, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+  %0 = fsub fast <4 x double> %b.real, %a.imag
+  %1 = fadd fast <4 x double> %b.imag, %a.real
+  %interleaved.vec = shufflevector <4 x double> %0, <4 x double> %1, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>
+  ret <8 x double> %interleaved.vec
+}

llvm/test/CodeGen/Thumb2/mve-complex-deinterleaving-f64-mul.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s --mattr=+mve.fp,+fp64 -o - | FileCheck %s
+
+target triple = "thumbv8.1m.main-none-none-eabi"
+
+; Expected to not transform
+define arm_aapcs_vfpcc <2 x double> @complex_mul_v2f64(<2 x double> %a, <2 x double> %b) {
+; CHECK-LABEL: complex_mul_v2f64:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vmul.f64 d5, d3, d0
+; CHECK-NEXT:    vmul.f64 d4, d1, d3
+; CHECK-NEXT:    vfma.f64 d5, d2, d1
+; CHECK-NEXT:    vfnms.f64 d4, d2, d0
+; CHECK-NEXT:    vmov q0, q2
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real   = shufflevector <2 x double> %a, <2 x double> poison, <1 x i32> <i32 0>
+  %a.imag = shufflevector <2 x double> %a, <2 x double> poison, <1 x i32> <i32 1>
+  %b.real = shufflevector <2 x double> %b, <2 x double> poison, <1 x i32> <i32 0>
+  %b.imag = shufflevector <2 x double> %b, <2 x double> poison, <1 x i32> <i32 1>
+  %0 = fmul fast <1 x double> %b.imag, %a.real
+  %1 = fmul fast <1 x double> %b.real, %a.imag
+  %2 = fadd fast <1 x double> %1, %0
+  %3 = fmul fast <1 x double> %b.real, %a.real
+  %4 = fmul fast <1 x double> %a.imag, %b.imag
+  %5 = fsub fast <1 x double> %3, %4
+  %interleaved.vec = shufflevector <1 x double> %5, <1 x double> %2, <2 x i32> <i32 0, i32 1>
+  ret <2 x double> %interleaved.vec
+}
+
+; Expected to not transform
+define arm_aapcs_vfpcc <4 x double> @complex_mul_v4f64(<4 x double> %a, <4 x double> %b) {
+; CHECK-LABEL: complex_mul_v4f64:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9, d10, d11}
+; CHECK-NEXT:    vpush {d8, d9, d10, d11}
+; CHECK-NEXT:    vmul.f64 d9, d7, d2
+; CHECK-NEXT:    vmov q5, q0
+; CHECK-NEXT:    vmul.f64 d8, d3, d7
+; CHECK-NEXT:    vfma.f64 d9, d6, d3
+; CHECK-NEXT:    vfnms.f64 d8, d6, d2
+; CHECK-NEXT:    vmul.f64 d1, d5, d10
+; CHECK-NEXT:    vmov q1, q4
+; CHECK-NEXT:    vmul.f64 d0, d11, d5
+; CHECK-NEXT:    vfma.f64 d1, d4, d11
+; CHECK-NEXT:    vfnms.f64 d0, d4, d10
+; CHECK-NEXT:    vpop {d8, d9, d10, d11}
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real   = shufflevector <4 x double> %a, <4 x double> poison, <2 x i32> <i32 0, i32 2>
+  %a.imag = shufflevector <4 x double> %a, <4 x double> poison, <2 x i32> <i32 1, i32 3>
+  %b.real = shufflevector <4 x double> %b, <4 x double> poison, <2 x i32> <i32 0, i32 2>
+  %b.imag = shufflevector <4 x double> %b, <4 x double> poison, <2 x i32> <i32 1, i32 3>
+  %0 = fmul fast <2 x double> %b.imag, %a.real
+  %1 = fmul fast <2 x double> %b.real, %a.imag
+  %2 = fadd fast <2 x double> %1, %0
+  %3 = fmul fast <2 x double> %b.real, %a.real
+  %4 = fmul fast <2 x double> %a.imag, %b.imag
+  %5 = fsub fast <2 x double> %3, %4
+  %interleaved.vec = shufflevector <2 x double> %5, <2 x double> %2, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x double> %interleaved.vec
+}
+
+; Expected to not transform
+define arm_aapcs_vfpcc <8 x double> @complex_mul_v8f64(<8 x double> %a, <8 x double> %b) {
+; CHECK-LABEL: complex_mul_v8f64:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9, d10, d11, d12, d13, d14, d15}
+; CHECK-NEXT:    vpush {d8, d9, d10, d11, d12, d13, d14, d15}
+; CHECK-NEXT:    .pad #64
+; CHECK-NEXT:    sub sp, #64
+; CHECK-NEXT:    add r0, sp, #128
+; CHECK-NEXT:    vmov q7, q1
+; CHECK-NEXT:    vldrw.u32 q4, [r0]
+; CHECK-NEXT:    add r0, sp, #160
+; CHECK-NEXT:    vldrw.u32 q1, [r0]
+; CHECK-NEXT:    vmov q6, q0
+; CHECK-NEXT:    vmov q0, q2
+; CHECK-NEXT:    add r0, sp, #176
+; CHECK-NEXT:    vmov q5, q3
+; CHECK-NEXT:    vstrw.32 q2, [sp, #32] @ 16-byte Spill
+; CHECK-NEXT:    vmul.f64 d5, d3, d0
+; CHECK-NEXT:    vstrw.32 q1, [sp, #48] @ 16-byte Spill
+; CHECK-NEXT:    vstrw.32 q5, [sp] @ 16-byte Spill
+; CHECK-NEXT:    vmul.f64 d4, d1, d3
+; CHECK-NEXT:    vldrw.u32 q1, [r0]
+; CHECK-NEXT:    vmov q0, q5
+; CHECK-NEXT:    add r0, sp, #144
+; CHECK-NEXT:    vstrw.32 q1, [sp, #16] @ 16-byte Spill
+; CHECK-NEXT:    vmul.f64 d11, d3, d0
+; CHECK-NEXT:    vmul.f64 d10, d1, d3
+; CHECK-NEXT:    vldrw.u32 q0, [r0]
+; CHECK-NEXT:    vmul.f64 d7, d9, d12
+; CHECK-NEXT:    vmul.f64 d2, d15, d1
+; CHECK-NEXT:    vmul.f64 d3, d1, d14
+; CHECK-NEXT:    vmul.f64 d6, d13, d9
+; CHECK-NEXT:    vfma.f64 d7, d8, d13
+; CHECK-NEXT:    vfnms.f64 d6, d8, d12
+; CHECK-NEXT:    vldrw.u32 q4, [sp, #32] @ 16-byte Reload
+; CHECK-NEXT:    vfma.f64 d3, d0, d15
+; CHECK-NEXT:    vfnms.f64 d2, d0, d14
+; CHECK-NEXT:    vldrw.u32 q0, [sp, #48] @ 16-byte Reload
+; CHECK-NEXT:    vfma.f64 d5, d0, d9
+; CHECK-NEXT:    vfnms.f64 d4, d0, d8
+; CHECK-NEXT:    vldrw.u32 q0, [sp, #16] @ 16-byte Reload
+; CHECK-NEXT:    vldrw.u32 q4, [sp] @ 16-byte Reload
+; CHECK-NEXT:    vfma.f64 d11, d0, d9
+; CHECK-NEXT:    vfnms.f64 d10, d0, d8
+; CHECK-NEXT:    vmov q0, q3
+; CHECK-NEXT:    vmov q3, q5
+; CHECK-NEXT:    add sp, #64
+; CHECK-NEXT:    vpop {d8, d9, d10, d11, d12, d13, d14, d15}
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real   = shufflevector <8 x double> %a, <8 x double> poison, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+  %a.imag = shufflevector <8 x double> %a, <8 x double> poison, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+  %b.real = shufflevector <8 x double> %b, <8 x double> poison, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
+  %b.imag = shufflevector <8 x double> %b, <8 x double> poison, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
+  %0 = fmul fast <4 x double> %b.imag, %a.real
+  %1 = fmul fast <4 x double> %b.real, %a.imag
+  %2 = fadd fast <4 x double> %1, %0
+  %3 = fmul fast <4 x double> %b.real, %a.real
+  %4 = fmul fast <4 x double> %a.imag, %b.imag
+  %5 = fsub fast <4 x double> %3, %4
+  %interleaved.vec = shufflevector <4 x double> %5, <4 x double> %2, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i32 2, i32 6, i32 3, i32 7>
+  ret <8 x double> %interleaved.vec
+}

llvm/test/CodeGen/Thumb2/mve-complex-deinterleaving-mixed-cases.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s --mattr=+mve.fp,+fp64 -o - | FileCheck %s
+
+target triple = "thumbv8.1m.main-none-none-eabi"
+
+; Expected to transform
+define arm_aapcs_vfpcc <4 x float> @mul_mul(<4 x float> %a, <4 x float> %b, <4 x float> %c) {
+; CHECK-LABEL: mul_mul:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vcmul.f32 q3, q0, q1, #0
+; CHECK-NEXT:    vcmla.f32 q3, q0, q1, #90
+; CHECK-NEXT:    vcmul.f32 q0, q3, q2, #0
+; CHECK-NEXT:    vcmla.f32 q0, q3, q2, #90
+; CHECK-NEXT:    bx lr
+entry:
+  %strided.vec = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec151 = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %strided.vec153 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec154 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %0 = fmul fast <2 x float> %strided.vec154, %strided.vec151
+  %1 = fmul fast <2 x float> %strided.vec153, %strided.vec
+  %2 = fmul fast <2 x float> %strided.vec154, %strided.vec
+  %3 = fmul fast <2 x float> %strided.vec153, %strided.vec151
+  %4 = fadd fast <2 x float> %3, %2
+  %5 = fsub fast <2 x float> %1, %0
+  %strided.vec156 = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec157 = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %6 = fmul fast <2 x float> %4, %strided.vec156
+  %7 = fmul fast <2 x float> %5, %strided.vec157
+  %8 = fadd fast <2 x float> %6, %7
+  %9 = fmul fast <2 x float> %strided.vec156, %5
+  %10 = fmul fast <2 x float> %4, %strided.vec157
+  %11 = fsub fast <2 x float> %9, %10
+  %interleaved.vec = shufflevector <2 x float> %11, <2 x float> %8, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}
+
+; Expected to not transform
+define arm_aapcs_vfpcc <4 x float> @add_mul(<4 x float> %a, <4 x float> %b, <4 x float> %c) {
+; CHECK-LABEL: add_mul:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9}
+; CHECK-NEXT:    vpush {d8, d9}
+; CHECK-NEXT:    vsub.f32 q3, q1, q2
+; CHECK-NEXT:    vsub.f32 q0, q1, q0
+; CHECK-NEXT:    vmov.f32 s16, s9
+; CHECK-NEXT:    vmov.f32 s13, s14
+; CHECK-NEXT:    vmov.f32 s17, s11
+; CHECK-NEXT:    vmov.f32 s0, s1
+; CHECK-NEXT:    vmul.f32 q1, q3, q4
+; CHECK-NEXT:    vmov.f32 s1, s3
+; CHECK-NEXT:    vmov.f32 s9, s10
+; CHECK-NEXT:    vfma.f32 q1, q2, q0
+; CHECK-NEXT:    vmul.f32 q0, q4, q0
+; CHECK-NEXT:    vneg.f32 q4, q0
+; CHECK-NEXT:    vmov.f32 s1, s4
+; CHECK-NEXT:    vfma.f32 q4, q2, q3
+; CHECK-NEXT:    vmov.f32 s3, s5
+; CHECK-NEXT:    vmov.f32 s0, s16
+; CHECK-NEXT:    vmov.f32 s2, s17
+; CHECK-NEXT:    vpop {d8, d9}
+; CHECK-NEXT:    bx lr
+entry:
+  %0 = fsub fast <4 x float> %b, %c
+  %1 = shufflevector <4 x float> %0, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec58 = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec59 = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %2 = fmul fast <2 x float> %1, %strided.vec59
+  %3 = fsub fast <4 x float> %b, %a
+  %4 = shufflevector <4 x float> %3, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %5 = fmul fast <2 x float> %strided.vec58, %4
+  %6 = fadd fast <2 x float> %5, %2
+  %7 = fmul fast <2 x float> %strided.vec58, %1
+  %8 = fmul fast <2 x float> %strided.vec59, %4
+  %9 = fsub fast <2 x float> %7, %8
+  %interleaved.vec = shufflevector <2 x float> %9, <2 x float> %6, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}
+
+; Expected to not transform
+define arm_aapcs_vfpcc <4 x float> @mul_mul270_mul(<4 x float> %a, <4 x float> %b, <4 x float> %c) {
+; CHECK-LABEL: mul_mul270_mul:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d12}
+; CHECK-NEXT:    vpush {d12}
+; CHECK-NEXT:    .vsave {d10}
+; CHECK-NEXT:    vpush {d10}
+; CHECK-NEXT:    .vsave {d8}
+; CHECK-NEXT:    vpush {d8}
+; CHECK-NEXT:    vmov.f32 s20, s4
+; CHECK-NEXT:    vmov.f32 s16, s8
+; CHECK-NEXT:    vmov.f32 s17, s10
+; CHECK-NEXT:    vmov.f32 s21, s6
+; CHECK-NEXT:    vmul.f32 q3, q5, q4
+; CHECK-NEXT:    vmov.f32 s4, s5
+; CHECK-NEXT:    vneg.f32 q3, q3
+; CHECK-NEXT:    vmov.f32 s24, s9
+; CHECK-NEXT:    vmov.f32 s25, s11
+; CHECK-NEXT:    vmov.f32 s5, s7
+; CHECK-NEXT:    vmul.f32 q2, q1, q4
+; CHECK-NEXT:    vmov.f32 s16, s0
+; CHECK-NEXT:    vfma.f32 q3, q1, q6
+; CHECK-NEXT:    vmov.f32 s17, s2
+; CHECK-NEXT:    vmov.f32 s0, s1
+; CHECK-NEXT:    vfma.f32 q2, q5, q6
+; CHECK-NEXT:    vmul.f32 q1, q3, q4
+; CHECK-NEXT:    vmov.f32 s1, s3
+; CHECK-NEXT:    vfma.f32 q1, q2, q0
+; CHECK-NEXT:    vmul.f32 q0, q3, q0
+; CHECK-NEXT:    vneg.f32 q3, q0
+; CHECK-NEXT:    vmov.f32 s1, s4
+; CHECK-NEXT:    vfma.f32 q3, q2, q4
+; CHECK-NEXT:    vmov.f32 s3, s5
+; CHECK-NEXT:    vmov.f32 s0, s12
+; CHECK-NEXT:    vmov.f32 s2, s13
+; CHECK-NEXT:    vpop {d8}
+; CHECK-NEXT:    vpop {d10}
+; CHECK-NEXT:    vpop {d12}
+; CHECK-NEXT:    bx lr
+entry:
+  %strided.vec = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec81 = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %strided.vec83 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec84 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %0 = fmul fast <2 x float> %strided.vec84, %strided.vec
+  %1 = fmul fast <2 x float> %strided.vec83, %strided.vec81
+  %2 = fadd fast <2 x float> %1, %0
+  %strided.vec86 = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec87 = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %3 = fmul fast <2 x float> %2, %strided.vec87
+  %4 = fmul fast <2 x float> %strided.vec84, %strided.vec81
+  %5 = fmul fast <2 x float> %strided.vec83, %strided.vec
+  %6 = fsub fast <2 x float> %4, %5
+  %7 = fmul fast <2 x float> %6, %strided.vec86
+  %8 = fadd fast <2 x float> %3, %7
+  %9 = fmul fast <2 x float> %2, %strided.vec86
+  %10 = fmul fast <2 x float> %6, %strided.vec87
+  %11 = fsub fast <2 x float> %9, %10
+  %interleaved.vec = shufflevector <2 x float> %11, <2 x float> %8, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}
+
+; (a * b) * a
+; Expected to transform
+define arm_aapcs_vfpcc <4 x float> @mul_triangle(<4 x float> %a, <4 x float> %b) {
+; CHECK-LABEL: mul_triangle:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vcmul.f32 q2, q1, q0, #0
+; CHECK-NEXT:    vcmla.f32 q2, q1, q0, #90
+; CHECK-NEXT:    vcmul.f32 q1, q0, q2, #0
+; CHECK-NEXT:    vcmla.f32 q1, q0, q2, #90
+; CHECK-NEXT:    vmov q0, q1
+; CHECK-NEXT:    bx lr
+entry:
+  %strided.vec = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec35 = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %strided.vec37 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec38 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %0 = fmul fast <2 x float> %strided.vec37, %strided.vec
+  %1 = fmul fast <2 x float> %strided.vec38, %strided.vec35
+  %2 = fsub fast <2 x float> %0, %1
+  %3 = fmul fast <2 x float> %2, %strided.vec35
+  %4 = fmul fast <2 x float> %strided.vec38, %strided.vec
+  %5 = fmul fast <2 x float> %strided.vec35, %strided.vec37
+  %6 = fadd fast <2 x float> %4, %5
+  %7 = fmul fast <2 x float> %6, %strided.vec
+  %8 = fadd fast <2 x float> %3, %7
+  %9 = fmul fast <2 x float> %2, %strided.vec
+  %10 = fmul fast <2 x float> %6, %strided.vec35
+  %11 = fsub fast <2 x float> %9, %10
+  %interleaved.vec = shufflevector <2 x float> %11, <2 x float> %8, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}
+
+
+; d * (b * a) * (c * a)
+; Expected to transform
+define arm_aapcs_vfpcc <4 x float> @mul_diamond(<4 x float> %a, <4 x float> %b, <4 x float> %c, <4 x float> %d) {
+; CHECK-LABEL: mul_diamond:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9}
+; CHECK-NEXT:    vpush {d8, d9}
+; CHECK-NEXT:    vcmul.f32 q4, q1, q0, #0
+; CHECK-NEXT:    vcmla.f32 q4, q1, q0, #90
+; CHECK-NEXT:    vcmul.f32 q1, q4, q3, #0
+; CHECK-NEXT:    vcmla.f32 q1, q4, q3, #90
+; CHECK-NEXT:    vcmul.f32 q3, q2, q0, #0
+; CHECK-NEXT:    vcmla.f32 q3, q2, q0, #90
+; CHECK-NEXT:    vcmul.f32 q0, q3, q1, #0
+; CHECK-NEXT:    vcmla.f32 q0, q3, q1, #90
+; CHECK-NEXT:    vpop {d8, d9}
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %a.imag = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %b.real = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %b.imag = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %c.real = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %c.imag = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %d.real = shufflevector <4 x float> %d, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %d.imag = shufflevector <4 x float> %d, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %0 = fmul fast <2 x float> %a.imag, %b.real
+  %1 = fmul fast <2 x float> %a.real, %b.imag
+  %2 = fadd fast <2 x float> %1, %0
+  %3 = fmul fast <2 x float> %a.real, %b.real
+  %4 = fmul fast <2 x float> %b.imag, %a.imag
+  %5 = fsub fast <2 x float> %3, %4
+  %6 = fmul fast <2 x float> %d.real, %5
+  %7 = fmul fast <2 x float> %2, %d.imag
+  %8 = fmul fast <2 x float> %d.real, %2
+  %9 = fmul fast <2 x float> %5, %d.imag
+  %10 = fsub fast <2 x float> %6, %7
+  %11 = fadd fast <2 x float> %8, %9
+  %12 = fmul fast <2 x float> %c.real, %a.imag
+  %13 = fmul fast <2 x float> %c.imag, %a.real
+  %14 = fadd fast <2 x float> %13, %12
+  %15 = fmul fast <2 x float> %14, %10
+  %16 = fmul fast <2 x float> %c.real, %a.real
+  %17 = fmul fast <2 x float> %c.imag, %a.imag
+  %18 = fsub fast <2 x float> %16, %17
+  %19 = fmul fast <2 x float> %18, %11
+  %20 = fadd fast <2 x float> %15, %19
+  %21 = fmul fast <2 x float> %18, %10
+  %22 = fmul fast <2 x float> %14, %11
+  %23 = fsub fast <2 x float> %21, %22
+  %interleaved.vec = shufflevector <2 x float> %23, <2 x float> %20, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}
+
+; Expected to transform
+define arm_aapcs_vfpcc <4 x float> @mul_add90_mul(<4 x float> %a, <4 x float> %b, <4 x float> %c) {
+; CHECK-LABEL: mul_add90_mul:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9}
+; CHECK-NEXT:    vpush {d8, d9}
+; CHECK-NEXT:    vcmul.f32 q3, q2, q0, #0
+; CHECK-NEXT:    vcmul.f32 q4, q1, q0, #0
+; CHECK-NEXT:    vcmla.f32 q4, q1, q0, #90
+; CHECK-NEXT:    vcmla.f32 q3, q2, q0, #90
+; CHECK-NEXT:    vcadd.f32 q0, q3, q4, #90
+; CHECK-NEXT:    vpop {d8, d9}
+; CHECK-NEXT:    bx lr
+entry:
+  %ar = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %ai = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %br = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %bi = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %cr = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %ci = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+
+  %i6 = fmul fast <2 x float> %br, %ar
+  %i7 = fmul fast <2 x float> %bi, %ai
+  %xr = fsub fast <2 x float> %i6, %i7
+  %i9 = fmul fast <2 x float> %bi, %ar
+  %i10 = fmul fast <2 x float> %br, %ai
+  %xi = fadd fast <2 x float> %i9, %i10
+
+  %j6 = fmul fast <2 x float> %cr, %ar
+  %j7 = fmul fast <2 x float> %ci, %ai
+  %yr = fsub fast <2 x float> %j6, %j7
+  %j9 = fmul fast <2 x float> %ci, %ar
+  %j10 = fmul fast <2 x float> %cr, %ai
+  %yi = fadd fast <2 x float> %j9, %j10
+
+  %zr = fsub fast <2 x float> %yr, %xi
+  %zi = fadd fast <2 x float> %yi, %xr
+  %interleaved.vec = shufflevector <2 x float> %zr, <2 x float> %zi, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}
+
+; Expected to not transform
+define arm_aapcs_vfpcc <4 x float> @mul_triangle_addmul(<4 x float> %a, <4 x float> %b, <4 x float> %c) {
+; CHECK-LABEL: mul_triangle_addmul:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9, d10, d11, d12, d13, d14, d15}
+; CHECK-NEXT:    vpush {d8, d9, d10, d11, d12, d13, d14, d15}
+; CHECK-NEXT:    vmov.f32 s16, s0
+; CHECK-NEXT:    vmov.f32 s20, s5
+; CHECK-NEXT:    vmov.f32 s17, s2
+; CHECK-NEXT:    vmov.f32 s21, s7
+; CHECK-NEXT:    vmov.f32 s5, s6
+; CHECK-NEXT:    vmul.f32 q3, q5, q4
+; CHECK-NEXT:    vmul.f32 q4, q1, q4
+; CHECK-NEXT:    vmov.f32 s0, s1
+; CHECK-NEXT:    vmov.f32 s1, s3
+; CHECK-NEXT:    vmov q6, q4
+; CHECK-NEXT:    vfms.f32 q6, q5, q0
+; CHECK-NEXT:    vmov q7, q3
+; CHECK-NEXT:    vfma.f32 q3, q1, q0
+; CHECK-NEXT:    vmov.f32 s20, s8
+; CHECK-NEXT:    vmov.f32 s21, s10
+; CHECK-NEXT:    vmov.f32 s4, s9
+; CHECK-NEXT:    vfma.f32 q7, q5, q0
+; CHECK-NEXT:    vmov.f32 s5, s11
+; CHECK-NEXT:    vadd.f32 q5, q7, q6
+; CHECK-NEXT:    vfms.f32 q4, q1, q0
+; CHECK-NEXT:    vmov.f32 s1, s20
+; CHECK-NEXT:    vsub.f32 q1, q4, q3
+; CHECK-NEXT:    vmov.f32 s3, s21
+; CHECK-NEXT:    vmov.f32 s0, s4
+; CHECK-NEXT:    vmov.f32 s2, s5
+; CHECK-NEXT:    vpop {d8, d9, d10, d11, d12, d13, d14, d15}
+; CHECK-NEXT:    bx lr
+entry:
+  %ar = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %ai = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %br = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %bi = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %cr = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %ci = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+
+  %i6 = fmul fast <2 x float> %br, %ar
+  %i7 = fmul fast <2 x float> %bi, %ai
+  %xr = fsub fast <2 x float> %i6, %i7
+  %i9 = fmul fast <2 x float> %bi, %ar
+  %i10 = fmul fast <2 x float> %br, %ai
+  %xi = fadd fast <2 x float> %i9, %i10
+
+  ;%j6 = fmul fast <2 x float> %cr, %ar
+  %j7 = fmul fast <2 x float> %ci, %ai
+  %yr = fsub fast <2 x float> %i6, %j7
+  ;%j9 = fmul fast <2 x float> %ci, %ar
+  %j10 = fmul fast <2 x float> %cr, %ai
+  %yi = fadd fast <2 x float> %i9, %j10
+
+  %zr = fsub fast <2 x float> %yr, %xi
+  %zi = fadd fast <2 x float> %yi, %xr
+  %interleaved.vec = shufflevector <2 x float> %zr, <2 x float> %zi, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}
+
+; Expected to not transform
+define arm_aapcs_vfpcc <4 x float> @mul_triangle_multiuses(<4 x float> %a, <4 x float> %b, ptr %p) {
+; CHECK-LABEL: mul_triangle_multiuses:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9}
+; CHECK-NEXT:    vpush {d8, d9}
+; CHECK-NEXT:    vmov.f32 s16, s4
+; CHECK-NEXT:    vmov.f32 s8, s1
+; CHECK-NEXT:    vmov.f32 s17, s6
+; CHECK-NEXT:    vmov.f32 s9, s3
+; CHECK-NEXT:    vmov.f32 s4, s5
+; CHECK-NEXT:    vmul.f32 q3, q2, q4
+; CHECK-NEXT:    vmov.f32 s1, s2
+; CHECK-NEXT:    vmov.f32 s5, s7
+; CHECK-NEXT:    vfma.f32 q3, q1, q0
+; CHECK-NEXT:    vmul.f32 q1, q1, q2
+; CHECK-NEXT:    vneg.f32 q1, q1
+; CHECK-NEXT:    vfma.f32 q1, q4, q0
+; CHECK-NEXT:    vmov.f32 s18, s12
+; CHECK-NEXT:    vmov.f32 s16, s4
+; CHECK-NEXT:    vmov.f32 s17, s5
+; CHECK-NEXT:    vmov.f32 s19, s13
+; CHECK-NEXT:    vstrw.32 q4, [r0]
+; CHECK-NEXT:    vmul.f32 q4, q3, q0
+; CHECK-NEXT:    vfma.f32 q4, q1, q2
+; CHECK-NEXT:    vmul.f32 q2, q3, q2
+; CHECK-NEXT:    vneg.f32 q2, q2
+; CHECK-NEXT:    vfma.f32 q2, q1, q0
+; CHECK-NEXT:    vmov.f32 s1, s16
+; CHECK-NEXT:    vmov.f32 s0, s8
+; CHECK-NEXT:    vmov.f32 s2, s9
+; CHECK-NEXT:    vmov.f32 s3, s17
+; CHECK-NEXT:    vpop {d8, d9}
+; CHECK-NEXT:    bx lr
+entry:
+  %strided.vec = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec35 = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %strided.vec37 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec38 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %0 = fmul fast <2 x float> %strided.vec37, %strided.vec
+  %1 = fmul fast <2 x float> %strided.vec38, %strided.vec35
+  %2 = fsub fast <2 x float> %0, %1
+  %3 = fmul fast <2 x float> %2, %strided.vec35
+  %4 = fmul fast <2 x float> %strided.vec38, %strided.vec
+  %5 = fmul fast <2 x float> %strided.vec35, %strided.vec37
+  %6 = fadd fast <2 x float> %4, %5
+  %otheruse = shufflevector <2 x float> %2, <2 x float> %6, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
+  store <4 x float> %otheruse, ptr %p
+  %7 = fmul fast <2 x float> %6, %strided.vec
+  %8 = fadd fast <2 x float> %3, %7
+  %9 = fmul fast <2 x float> %2, %strided.vec
+  %10 = fmul fast <2 x float> %6, %strided.vec35
+  %11 = fsub fast <2 x float> %9, %10
+  %interleaved.vec = shufflevector <2 x float> %11, <2 x float> %8, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}

llvm/test/CodeGen/Thumb2/mve-complex-deinterleaving-uniform-cases.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s --mattr=+mve.fp,+fp64 -o - | FileCheck %s
+
+target triple = "thumbv8.1m.main-none-none-eabi"
+
+; Expected to transform
+define arm_aapcs_vfpcc <4 x float> @simple_mul(<4 x float> %a, <4 x float> %b) {
+; CHECK-LABEL: simple_mul:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vcmul.f32 q2, q0, q1, #0
+; CHECK-NEXT:    vcmla.f32 q2, q0, q1, #90
+; CHECK-NEXT:    vmov q0, q2
+; CHECK-NEXT:    bx lr
+entry:
+  %strided.vec = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec17 = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %strided.vec19 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec20 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %0 = fmul fast <2 x float> %strided.vec20, %strided.vec
+  %1 = fmul fast <2 x float> %strided.vec19, %strided.vec17
+  %2 = fadd fast <2 x float> %1, %0
+  %3 = fmul fast <2 x float> %strided.vec19, %strided.vec
+  %4 = fmul fast <2 x float> %strided.vec17, %strided.vec20
+  %5 = fsub fast <2 x float> %3, %4
+  %interleaved.vec = shufflevector <2 x float> %5, <2 x float> %2, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}
+
+; Expected to not transform
+define arm_aapcs_vfpcc <4 x float> @simple_mul_no_contract(<4 x float> %a, <4 x float> %b) {
+; CHECK-LABEL: simple_mul_no_contract:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9, d10, d11}
+; CHECK-NEXT:    vpush {d8, d9, d10, d11}
+; CHECK-NEXT:    vmov.f32 s8, s5
+; CHECK-NEXT:    vmov.f32 s12, s1
+; CHECK-NEXT:    vmov.f32 s9, s7
+; CHECK-NEXT:    vmov.f32 s13, s3
+; CHECK-NEXT:    vmov.f32 s1, s2
+; CHECK-NEXT:    vmul.f32 q4, q3, q2
+; CHECK-NEXT:    vmov.f32 s5, s6
+; CHECK-NEXT:    vmul.f32 q2, q2, q0
+; CHECK-NEXT:    vmul.f32 q5, q1, q0
+; CHECK-NEXT:    vfma.f32 q2, q1, q3
+; CHECK-NEXT:    vsub.f32 q4, q5, q4
+; CHECK-NEXT:    vmov.f32 s1, s8
+; CHECK-NEXT:    vmov.f32 s0, s16
+; CHECK-NEXT:    vmov.f32 s2, s17
+; CHECK-NEXT:    vmov.f32 s3, s9
+; CHECK-NEXT:    vpop {d8, d9, d10, d11}
+; CHECK-NEXT:    bx lr
+entry:
+  %strided.vec = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec17 = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %strided.vec19 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec20 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %0 = fmul fast <2 x float> %strided.vec20, %strided.vec
+  %1 = fmul fast <2 x float> %strided.vec19, %strided.vec17
+  %2 = fadd fast <2 x float> %1, %0
+  %3 = fmul fast <2 x float> %strided.vec19, %strided.vec
+  %4 = fmul fast <2 x float> %strided.vec17, %strided.vec20
+  %5 = fsub <2 x float> %3, %4
+  %interleaved.vec = shufflevector <2 x float> %5, <2 x float> %2, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}
+
+; Expected to transform
+define arm_aapcs_vfpcc <4 x float> @three_way_mul(<4 x float> %a, <4 x float> %b, <4 x float> %c) {
+; CHECK-LABEL: three_way_mul:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vcmul.f32 q3, q1, q0, #0
+; CHECK-NEXT:    vcmla.f32 q3, q1, q0, #90
+; CHECK-NEXT:    vcmul.f32 q0, q2, q3, #0
+; CHECK-NEXT:    vcmla.f32 q0, q2, q3, #90
+; CHECK-NEXT:    bx lr
+entry:
+  %strided.vec = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec39 = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %strided.vec41 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec42 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %strided.vec44 = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec45 = shufflevector <4 x float> %c, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %0 = fmul fast <2 x float> %strided.vec41, %strided.vec
+  %1 = fmul fast <2 x float> %strided.vec42, %strided.vec39
+  %2 = fsub fast <2 x float> %0, %1
+  %3 = fmul fast <2 x float> %2, %strided.vec45
+  %4 = fmul fast <2 x float> %strided.vec42, %strided.vec
+  %5 = fmul fast <2 x float> %strided.vec39, %strided.vec41
+  %6 = fadd fast <2 x float> %4, %5
+  %7 = fmul fast <2 x float> %6, %strided.vec44
+  %8 = fadd fast <2 x float> %3, %7
+  %9 = fmul fast <2 x float> %2, %strided.vec44
+  %10 = fmul fast <2 x float> %6, %strided.vec45
+  %11 = fsub fast <2 x float> %9, %10
+  %interleaved.vec = shufflevector <2 x float> %11, <2 x float> %8, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}
+
+; Expected to transform
+define arm_aapcs_vfpcc <4 x float> @simple_add_90(<4 x float> %a, <4 x float> %b) {
+; CHECK-LABEL: simple_add_90:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vcadd.f32 q2, q1, q0, #90
+; CHECK-NEXT:    vmov q0, q2
+; CHECK-NEXT:    bx lr
+entry:
+  %strided.vec = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec17 = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %strided.vec19 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec20 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %0 = fsub fast <2 x float> %strided.vec19, %strided.vec17
+  %1 = fadd fast <2 x float> %strided.vec20, %strided.vec
+  %interleaved.vec = shufflevector <2 x float> %0, <2 x float> %1, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}
+
+; Expected to not transform, fadd commutativity is not yet implemented
+define arm_aapcs_vfpcc <4 x float> @simple_add_270_false(<4 x float> %a, <4 x float> %b) {
+; CHECK-LABEL: simple_add_270_false:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vmov.f32 s8, s4
+; CHECK-NEXT:    vmov.f32 s12, s1
+; CHECK-NEXT:    vmov.f32 s4, s5
+; CHECK-NEXT:    vmov.f32 s9, s6
+; CHECK-NEXT:    vmov.f32 s13, s3
+; CHECK-NEXT:    vmov.f32 s1, s2
+; CHECK-NEXT:    vsub.f32 q2, q3, q2
+; CHECK-NEXT:    vmov.f32 s5, s7
+; CHECK-NEXT:    vadd.f32 q1, q1, q0
+; CHECK-NEXT:    vmov.f32 s1, s8
+; CHECK-NEXT:    vmov.f32 s0, s4
+; CHECK-NEXT:    vmov.f32 s2, s5
+; CHECK-NEXT:    vmov.f32 s3, s9
+; CHECK-NEXT:    bx lr
+entry:
+  %strided.vec = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec17 = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %strided.vec19 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec20 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %0 = fadd fast <2 x float> %strided.vec20, %strided.vec
+  %1 = fsub fast <2 x float> %strided.vec17, %strided.vec19
+  %interleaved.vec = shufflevector <2 x float> %0, <2 x float> %1, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}
+
+; Expected to transform
+define arm_aapcs_vfpcc <4 x float> @simple_add_270_true(<4 x float> %a, <4 x float> %b) {
+; CHECK-LABEL: simple_add_270_true:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vcadd.f32 q2, q0, q1, #270
+; CHECK-NEXT:    vmov q0, q2
+; CHECK-NEXT:    bx lr
+entry:
+  %strided.vec = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec17 = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %strided.vec19 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %strided.vec20 = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %0 = fadd fast <2 x float> %strided.vec, %strided.vec20
+  %1 = fsub fast <2 x float> %strided.vec17, %strided.vec19
+  %interleaved.vec = shufflevector <2 x float> %0, <2 x float> %1, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}
+
+; Expected to not transform
+define arm_aapcs_vfpcc <4 x float> @add_external_use(<4 x float> %a, <4 x float> %b) {
+; CHECK-LABEL: add_external_use:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vmov.f32 s8, s4
+; CHECK-NEXT:    vmov.f32 s12, s1
+; CHECK-NEXT:    vmov.f32 s4, s5
+; CHECK-NEXT:    vmov.f32 s9, s6
+; CHECK-NEXT:    vmov.f32 s13, s3
+; CHECK-NEXT:    vmov.f32 s5, s7
+; CHECK-NEXT:    vadd.f32 q2, q3, q2
+; CHECK-NEXT:    vmov.f32 s1, s2
+; CHECK-NEXT:    vsub.f32 q1, q0, q1
+; CHECK-NEXT:    vmov.f32 s1, s8
+; CHECK-NEXT:    vmov.f32 s0, s4
+; CHECK-NEXT:    vmov.f32 s2, s5
+; CHECK-NEXT:    vmov.f32 s3, s9
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %a.imag = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %b.real = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %b.imag = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %0 = fsub fast <2 x float> %a.real, %b.imag
+  %1 = fadd fast <2 x float> %a.imag, %b.real
+  %interleaved.vec = shufflevector <2 x float> %0, <2 x float> %1, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  %dup = shufflevector <2 x float> %0, <2 x float> poison, <4 x i32> <i32 0, i32 1, i32 0, i32 1>
+  %interleaved.vec2 = shufflevector <4 x float> %interleaved.vec, <4 x float> %dup, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
+  ret <4 x float> %interleaved.vec2
+}
+
+define arm_aapcs_vfpcc <4 x float> @mul_mul_with_fneg(<4 x float> %a, <4 x float> %b) {
+; CHECK-LABEL: mul_mul_with_fneg:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    vcmul.f32 q2, q1, q0, #270
+; CHECK-NEXT:    vcmla.f32 q2, q1, q0, #180
+; CHECK-NEXT:    vmov q0, q2
+; CHECK-NEXT:    bx lr
+entry:
+  %a.real = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %a.imag = shufflevector <4 x float> %a, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %b.real = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 0, i32 2>
+  %b.imag = shufflevector <4 x float> %b, <4 x float> poison, <2 x i32> <i32 1, i32 3>
+  %0 = fneg fast <2 x float> %a.imag
+  %1 = fmul fast <2 x float> %b.real, %0
+  %2 = fmul fast <2 x float> %a.real, %b.imag
+  %3 = fsub fast <2 x float> %1, %2
+  %4 = fmul fast <2 x float> %b.imag, %a.imag
+  %5 = fmul fast <2 x float> %a.real, %b.real
+  %6 = fsub fast <2 x float> %4, %5
+  %interleaved.vec = shufflevector <2 x float> %6, <2 x float> %3, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  ret <4 x float> %interleaved.vec
+}
+
+; Expected to not transform
+define arm_aapcs_vfpcc <12 x float> @abp90c12(<12 x float> %a, <12 x float> %b, <12 x float> %c) {
+; CHECK-LABEL: abp90c12:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    .vsave {d8, d9, d10, d11, d12, d13, d14, d15}
+; CHECK-NEXT:    vpush {d8, d9, d10, d11, d12, d13, d14, d15}
+; CHECK-NEXT:    .pad #48
+; CHECK-NEXT:    sub sp, #48
+; CHECK-NEXT:    vldr s23, [sp, #124]
+; CHECK-NEXT:    vmov.f32 s20, s13
+; CHECK-NEXT:    vldr s22, [sp, #116]
+; CHECK-NEXT:    vmov.f32 s25, s11
+; CHECK-NEXT:    vmov.f32 s13, s10
+; CHECK-NEXT:    vldr s19, [sp, #120]
+; CHECK-NEXT:    vmov.f32 s11, s6
+; CHECK-NEXT:    vldr s18, [sp, #112]
+; CHECK-NEXT:    vmov.f32 s6, s5
+; CHECK-NEXT:    vldr s31, [sp, #172]
+; CHECK-NEXT:    vmov.f32 s10, s4
+; CHECK-NEXT:    vldr s30, [sp, #164]
+; CHECK-NEXT:    vmov.f32 s21, s15
+; CHECK-NEXT:    vldr s29, [sp, #156]
+; CHECK-NEXT:    vmov.f32 s5, s3
+; CHECK-NEXT:    vldr s28, [sp, #148]
+; CHECK-NEXT:    vmov.f32 s4, s1
+; CHECK-NEXT:    vmov.f32 s24, s9
+; CHECK-NEXT:    vmov.f32 s16, s12
+; CHECK-NEXT:    vstrw.32 q6, [sp, #16] @ 16-byte Spill
+; CHECK-NEXT:    vmov.f32 s12, s8
+; CHECK-NEXT:    vldr s27, [sp, #168]
+; CHECK-NEXT:    vmov.f32 s17, s14
+; CHECK-NEXT:    vldr s26, [sp, #160]
+; CHECK-NEXT:    vmov.f32 s9, s2
+; CHECK-NEXT:    vldr s25, [sp, #152]
+; CHECK-NEXT:    vmov.f32 s8, s0
+; CHECK-NEXT:    vmul.f32 q0, q5, q1
+; CHECK-NEXT:    vmul.f32 q1, q4, q1
+; CHECK-NEXT:    vneg.f32 q0, q0
+; CHECK-NEXT:    vldr s24, [sp, #144]
+; CHECK-NEXT:    vfma.f32 q1, q5, q2
+; CHECK-NEXT:    vstrw.32 q0, [sp] @ 16-byte Spill
+; CHECK-NEXT:    vstrw.32 q3, [sp, #32] @ 16-byte Spill
+; CHECK-NEXT:    vsub.f32 q6, q6, q1
+; CHECK-NEXT:    vldrw.u32 q1, [sp] @ 16-byte Reload
+; CHECK-NEXT:    vldr s13, [sp, #140]
+; CHECK-NEXT:    vfma.f32 q1, q4, q2
+; CHECK-NEXT:    vldr s12, [sp, #132]
+; CHECK-NEXT:    vadd.f32 q1, q7, q1
+; CHECK-NEXT:    vldrw.u32 q7, [sp, #16] @ 16-byte Reload
+; CHECK-NEXT:    vldr s1, [sp, #136]
+; CHECK-NEXT:    vstrw.32 q3, [sp, #16] @ 16-byte Spill
+; CHECK-NEXT:    vmul.f32 q2, q3, q7
+; CHECK-NEXT:    vldr s0, [sp, #128]
+; CHECK-NEXT:    vldrw.u32 q3, [sp, #32] @ 16-byte Reload
+; CHECK-NEXT:    vneg.f32 q2, q2
+; CHECK-NEXT:    vldr s21, [sp, #184]
+; CHECK-NEXT:    vfma.f32 q2, q0, q3
+; CHECK-NEXT:    vmul.f32 q0, q0, q7
+; CHECK-NEXT:    vldrw.u32 q7, [sp, #16] @ 16-byte Reload
+; CHECK-NEXT:    vldr s20, [sp, #176]
+; CHECK-NEXT:    vldr s17, [sp, #188]
+; CHECK-NEXT:    vldr s16, [sp, #180]
+; CHECK-NEXT:    vfma.f32 q0, q7, q3
+; CHECK-NEXT:    vsub.f32 q3, q5, q0
+; CHECK-NEXT:    vmov.f32 s1, s4
+; CHECK-NEXT:    vadd.f32 q4, q4, q2
+; CHECK-NEXT:    vmov.f32 s3, s5
+; CHECK-NEXT:    vmov.f32 s5, s6
+; CHECK-NEXT:    vmov.f32 s0, s24
+; CHECK-NEXT:    vmov.f32 s2, s25
+; CHECK-NEXT:    vmov.f32 s4, s26
+; CHECK-NEXT:    vmov.f32 s6, s27
+; CHECK-NEXT:    vmov.f32 s8, s12
+; CHECK-NEXT:    vmov.f32 s9, s16
+; CHECK-NEXT:    vmov.f32 s10, s13
+; CHECK-NEXT:    vmov.f32 s11, s17
+; CHECK-NEXT:    add sp, #48
+; CHECK-NEXT:    vpop {d8, d9, d10, d11, d12, d13, d14, d15}
+; CHECK-NEXT:    bx lr
+entry:
+  %ar = shufflevector <12 x float> %a, <12 x float> poison, <6 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10>
+  %ai = shufflevector <12 x float> %a, <12 x float> poison, <6 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11>
+  %br = shufflevector <12 x float> %b, <12 x float> poison, <6 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10>
+  %bi = shufflevector <12 x float> %b, <12 x float> poison, <6 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11>
+  %cr = shufflevector <12 x float> %c, <12 x float> poison, <6 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10>
+  %ci = shufflevector <12 x float> %c, <12 x float> poison, <6 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11>
+
+  %i6 = fmul fast <6 x float> %br, %ar
+  %i7 = fmul fast <6 x float> %bi, %ai
+  %xr = fsub fast <6 x float> %i6, %i7
+  %i9 = fmul fast <6 x float> %bi, %ar
+  %i10 = fmul fast <6 x float> %br, %ai
+  %xi = fadd fast <6 x float> %i9, %i10
+
+  %zr = fsub fast <6 x float> %cr, %xi
+  %zi = fadd fast <6 x float> %ci, %xr
+  %interleaved.vec = shufflevector <6 x float> %zr, <6 x float> %zi, <12 x i32> <i32 0, i32 6, i32 1, i32 7, i32 2, i32 8, i32 3, i32 9, i32 4, i32 10, i32 5, i32 11>
+  ret <12 x float> %interleaved.vec
+}