This is an archive of the discontinued LLVM Phabricator instance.

[ARM][CodeGen] Add support for complex deinterleaving
ClosedPublic

Authored by NickGuy on Nov 18 2021, 10:29 AM.

Details

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.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
mgabka added a subscriber: mgabka.Apr 14 2022, 3:25 AM
huntergr added inline comments.May 30 2022, 2:03 AM
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 updated this revision to Diff 438664.Jun 21 2022, 5:55 AM
NickGuy marked 2 inline comments as done.

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])

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 added a comment.EditedJun 22 2022, 4:02 AM

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 added a subscriber: chill.Jun 28 2022, 3:28 AM
chill added inline comments.
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 added a comment.Jun 28 2022, 3:30 AM

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 added inline comments.Jun 28 2022, 7:42 AM
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 added inline comments.Jun 28 2022, 7:46 AM
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.

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 updated this revision to Diff 442045.Jul 4 2022, 2:55 AM
NickGuy marked 6 inline comments as done.
NickGuy retitled this revision from [ARM][CodeGen] Add support for complex addition and multiplication to [ARM][CodeGen] Add support for complex deinterleaving.

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

NickGuy marked 15 inline comments as done.Jul 4 2022, 3:42 AM
NickGuy added inline comments.
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.

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 updated this revision to Diff 449946.Aug 4 2022, 6:00 AM
NickGuy added a comment.EditedAug 4 2022, 6:01 AM

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

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 updated this revision to Diff 457993.Sep 5 2022, 7:32 AM
NickGuy marked 8 inline comments as done.

Addressed comments and improved case coverage,

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 updated this revision to Diff 458481.Sep 7 2022, 9:40 AM
NickGuy marked 12 inline comments as done.

Addressed comments

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?

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 updated this revision to Diff 459432.Sep 12 2022, 5:58 AM
NickGuy marked 7 inline comments as done.
NickGuy added inline comments.
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 added inline comments.Sep 12 2022, 5:58 AM
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 added inline comments.Sep 13 2022, 2:22 AM
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 updated this revision to Diff 461829.Sep 21 2022, 2:51 AM
NickGuy marked 4 inline comments as done.

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.

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 updated this revision to Diff 463541.Sep 28 2022, 7:03 AM
NickGuy marked an inline comment as done and 2 inline comments as not done.

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

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 updated this revision to Diff 467159.Oct 12 2022, 8:38 AM
NickGuy marked an inline comment as done.

Thanks @dmgreen for the extra tests.

...
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 added inline comments.Oct 14 2022, 10:54 AM
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 updated this revision to Diff 469583.Oct 21 2022, 6:47 AM
NickGuy marked 10 inline comments as done.

Addressed comments

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 added a comment.EditedOct 26 2022, 3:14 AM

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 updated this revision to Diff 473955.Nov 8 2022, 4:10 AM
NickGuy marked 23 inline comments as done.
NickGuy added inline comments.
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 added inline comments.Nov 10 2022, 9:19 AM
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.

khchen added a subscriber: khchen.Nov 10 2022, 10:06 AM
NickGuy updated this revision to Diff 474743.Nov 11 2022, 6:39 AM
NickGuy marked 6 inline comments as done.
dmgreen accepted this revision.Nov 14 2022, 5:39 AM

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

This revision is now accepted and ready to land.Nov 14 2022, 5:39 AM
This revision was landed with ongoing or failed builds.Nov 14 2022, 6:04 AM
This revision was automatically updated to reflect the committed changes.
NickGuy marked 4 inline comments as done.

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?

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.