Split out unrelated changes, added more tests, unified the common logic, and renamed Passthrough to Symmetric.

I've changed the approach to not be so focused on "complex addition with zero rotation", and instead common operations applied to both sides (dubbed "symmetric operations"). The current implementation doesn't allow for targets to define their own supported operations, but also I'm not sure if there are many (if any at all) operations that wouldn't be common.

Addressed comments, and added more tests

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?

This was pushed over to be the responsibility of the target. Therefore this approach is no longer relevant.

Addressed comments, and rebased to align with latest revision of D114174 (Diff 16)

Addressed comments

Thanks @dmgreen for the extra tests.

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

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

Forgot to submit the comments adjoining the patch...

Addressed comments

Addressed comments and improved case coverage,

Addressed comments, cleaned up debug outputs, and implemented vector splitting

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

Looks like I messed up my git-fu somewhere in preparing these patches. There are a few cleanup changes in this patch that should've been in a previous one. I'll try and clean that up when addressing other comments.

Added context missing from initial patch

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

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.

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

LGTM

LGTM

Code looks good to me, but a small nitpick on the function name

It's been longer than I would've liked before I've gotten back to this, but I've;

I wasn't aware of the implicit truncation. In that case, LGTM

Looks good overall, with potential wins in both performance and codesize. Just 1 minor thing (and a nitpick about a comment).

Thanks all for the comments so far (And thanks Dave for taking on the evening shift, as it were)

In D114174#3307302, @dnsampaio wrote:

...
I'm not exactly sure why to do target specific pattern matching here. We could simply add generic complex intrinsics and the different patterns could be matched at each archs ISEL, no? I do agree that it should check in the backend if it should generate a complex operation of a given vector type.
...
Is there any strong reason to create target specific intrinsics instead of having generic intrinsics with polymorphism? Such as llvm.complex.add.v2f32?

The supportsComplexArithmetic method doesn't add a lot on its own. It would probably be better to represent it in terms of asking the backend if it has certain patterns of certain types available. An f32 fcadd, for example, or a i16 fcmul_with_rotate (I'm not sure what to name them).
The ComplexArithmeticGraph seems like internal details to the pass. It would be best not to pass it over the TTI interface boundary if we can. The backend just needs to create the correct intrinsics of the correct type.
Equally I would keep all the matching logic in the pass, not through matchComplexArithmeticIR. That would be similar to, for example, the MachineCombiner pass which has its own enum of a set of patterns.

Unfortunately, not all architectures/intrinsics follow the same patterns, so this was done to provide a way for architecture-specific stuff to be handled as needed. The MVE halving complex add (which I only now realise was included in this patch) is a good example of this; It only works on integers, and requires some extra instructions to be matched. This instruction is only in MVE, it is not part of NEON in any way.
The intrinsics that are common are also constructed differently; While the NEON intrinsics are separated out by their rotations (aarch64_neon_vcmla_rot0, aarch64_neon_vcmla_rot90), MVE squishes them into one and determines the rotation based on a parameter.
ComplexArithmeticGraph is used to encapsulate all the data the TTI might need in order to correctly generate the right intrinsic. It could be replaced by something a bit lighter (and that doesn't expose the implementation detail of the node list), but something will be needed to provide this info.

Applied feedback received offline, redesigned the interface/implementation, and fixed up a number of fundamental issues in the previous iteration.

Fixes the test to pass with this patch in isolation (i.e. without the child revision on top)

In D114590#3166112, @dmgreen wrote:

It may be better to fold this into D114879 so that there is a single patch that can be tested properly.

In D114590#3163780, @SjoerdMeijer wrote:

Okay, that's fine. Perhaps upload your WIP patches too then, stack them, so that we can actually see the (full) approach?

I've got a follow-up patch nearly ready with tests, yep. I want to settle on an approach here before implementing the other side of it.

In D114590#3153774, @dmgreen wrote:

Do we really want to add this to the base Align class? Or should it just be part of whatever controls the code alignment?

In D114174#3142048, @SjoerdMeijer wrote:

Nice one Nick.
Can you first run clang-format on this patch? It is pretty much unreadable with all these lint messages.

LGTM

Updated test

In D109323#2985421, @dmgreen wrote:

OK. Can you add a test? Something that would schedule instructions apart before and keep them together now.