This is an archive of the discontinued LLVM Phabricator instance.

[DAGCombiner] (insert_vector_elt (vector_shuffle X, Y), (extract_vector_elt X, N), IdxC) -> (vector_shuffle X, Y)
ClosedPublic

Authored by deadalnix on Aug 25 2019, 9:36 AM.

Details

Summary

This is beneficial when the shuffle is only used once and end up being generated in a few places when some node is combined into a shuffle.

Diff Detail

Event Timeline

deadalnix created this revision.Aug 25 2019, 9:36 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 25 2019, 9:36 AM
lebedev.ri added inline comments.Aug 25 2019, 11:03 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
16432–16433

Do you check that both vector_shuffle and extract_vector_elt have the same first argument?

16434–16436

Here we have two instructions, and only require that the first one is single-use.
Observation: we only create a single new instruction.
Do we want to either require both of them be single-use, the first one, either one of them, or none of them?

Another observation - you end up keeping (using) the instruction you just checked for extra uses.
Did you mean to check the other one instead?

16448–16450

So NewMask is simply inited as a copy of SVN->getMask()?
Would something like SmallVector<int, 16> NewMask(SVN->getMask()); just work?

16452

You either need to check that the cast succeeded, or drop dyn_ prefix

16453

This could use a comment

test/CodeGen/X86/madd.ll
1901–1903

If i'm reading this correctly this does showcase the need to handle this in backend - it can be introduced there?

deadalnix marked 5 inline comments as done.Aug 25 2019, 11:33 AM
deadalnix added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
16432–16433

This is checked bellow. It is because we can match either the first or the second argument, as vector_shuffle does in fact shuffle two vectors together.

16434–16436

Even if InsertVal is reused, this transform reduces data dependencies, but indeed do not save anything on the instruction count from. Removing data dependencies is beneficial on its own.

16448–16450

I asked mys elf the same question. This doesn't seem to work.

16452

The cast must succeed, as we check for it in the if guarding this code, so I'll remove dyn_

16453

I'll add a few comments.

craig.topper added inline comments.Aug 25 2019, 11:44 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
16448–16450

Yeah SmallVector doesn't take an ArrayRef, but you can do

SmallVector<int, 16> NewMask(Mask.begin(), Mask.end());

lebedev.ri added inline comments.Aug 25 2019, 11:45 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
16434–16436

So, do we need that one-use restriction here then?

16448–16450

SmallVector<int, 16> NewMask(SVN->getMask().begin(), SVN->getMask().end()); then.

deadalnix updated this revision to Diff 217061.Aug 25 2019, 1:38 PM
  • Add comments
  • dyn_cast -> cast
deadalnix updated this revision to Diff 217064.Aug 25 2019, 2:43 PM
deadalnix marked an inline comment as done.

Build NewMask using iterators

lebedev.ri added inline comments.Aug 25 2019, 11:20 PM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
16448–16450

Please mark comments as resolved as appropriate.

deadalnix marked 9 inline comments as done.Aug 26 2019, 3:31 AM

Comments amrked as done.

RKSimon added inline comments.Aug 26 2019, 10:01 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
16451

You already have this at line 16438:

ArrayRef<int> Mask = SVN->getMask()
16456

You need to check NewMask is legal: if (!TLI.isShuffleMaskLegal(NewMask, Vec.getValueType()))

deadalnix marked an inline comment as done.Aug 26 2019, 10:16 AM
deadalnix added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
16456

There are a few places where isShuffleMaskLegal is used. Some try to flip operands inc ase it isn't legal. Should that be an idiom?

Looks like the link was incorrect, this didn't auto-close?

Looks like the link was incorrect, this didn't auto-close?

Why should this auto close?

It wasn't landed yet. I was wondering if the creation of vector shuffles should be normalized. I think it may be worth doing.

Looks like the link was incorrect, this didn't auto-close?

Why should this auto close?

It wasn't landed yet. I was wondering if the creation of vector shuffles should be normalized. I think it may be worth doing.

Sorry, i got confused by "commits" tab

RKSimon added inline comments.Aug 27 2019, 6:09 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
16456

I've no objection to you creating a static helper that tries isShuffleMaskLegal with original and commuted masks, and call DAG.getVectorShuffle on success.

deadalnix updated this revision to Diff 217409.Aug 27 2019, 8:01 AM

Rebase on top of D66804

deadalnix marked 3 inline comments as done.Aug 27 2019, 8:04 AM

This looks good to me but i find naming choice really confusing here.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
16429–16465

Hm, please rename this to ExtractVal instead.

16432

Comment is wrong i think, should be
s/IdxC/InsIndex/

16456

ExtrIndex

lebedev.ri requested changes to this revision.Aug 27 2019, 4:34 PM

Actually, i have one concern.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
16430

OldShuffle

16440–16441

Just x/y like in comments?

16446

Maybe XOffset?

16450

Actually, this is not correct.
While both shuffle inputs must have same types,
the shuffle mask can have different dimensions.
So this should be closer to Offset = X.getType().getVectorNumElements().

https://llvm.org/docs/LangRef.html#shufflevector-instruction

This revision now requires changes to proceed.Aug 27 2019, 4:34 PM
RKSimon added inline comments.Aug 28 2019, 3:52 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
16430

There's no need to rename - tbh we don't know its a shuffle at this stage!

16450

That is only true for IR - in the DAG, the result must have the same type as the shuffle operands - so the number of mask elts must match the number of result/operand elts - see SelectionDAG::getVectorShuffle

16456

Please can you assert that IndexX's value (and InsIndex come to that) are both in bounds (0 <= idx < Mask.size())?

deadalnix marked an inline comment as done.Aug 28 2019, 5:02 AM
deadalnix added inline comments.
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
16430

That is true, and this is why the names are what they are. But I have to agree with @lebedev.ri here, the name are very confusing. I'll try to see if I can come up with better names.

lebedev.ri added inline comments.Aug 28 2019, 5:06 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
16450

Oh, forgot about that, sorry. An assert later on will be fine then.

deadalnix updated this revision to Diff 217666.Aug 28 2019, 9:05 AM

IndexC => ExtrIndex

deadalnix marked 5 inline comments as done.Aug 28 2019, 9:06 AM
lebedev.ri accepted this revision.Aug 28 2019, 9:15 AM

I still find naming choices to be actively misleading.
LG otherwise.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
16430

There's no need to rename - tbh we don't know its a shuffle at this stage!

But we will only proceed *if* it will be a shuffle. This is a common pattern everywhere else in the code.

This revision is now accepted and ready to land.Aug 28 2019, 9:15 AM
This revision was automatically updated to reflect the committed changes.