Page MenuHomePhabricator

[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

Repository
rL LLVM

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 ↗(On Diff #217050)

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

16434–16436 ↗(On Diff #217050)

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 ↗(On Diff #217050)

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

16452 ↗(On Diff #217050)

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

16453 ↗(On Diff #217050)

This could use a comment

test/CodeGen/X86/madd.ll
1901–1903 ↗(On Diff #217050)

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 ↗(On Diff #217050)

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 ↗(On Diff #217050)

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 ↗(On Diff #217050)

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

16452 ↗(On Diff #217050)

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

16453 ↗(On Diff #217050)

I'll add a few comments.

craig.topper added inline comments.Aug 25 2019, 11:44 AM
lib/CodeGen/SelectionDAG/DAGCombiner.cpp
16448–16450 ↗(On Diff #217050)

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 ↗(On Diff #217050)

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

16448–16450 ↗(On Diff #217050)

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 ↗(On Diff #217050)

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 ↗(On Diff #217064)

You already have this at line 16438:

ArrayRef<int> Mask = SVN->getMask()
16456 ↗(On Diff #217064)

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 ↗(On Diff #217064)

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 ↗(On Diff #217064)

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
16420 ↗(On Diff #217409)

Hm, please rename this to ExtractVal instead.

16423 ↗(On Diff #217409)

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

16447 ↗(On Diff #217409)

ExtrIndex

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

Actually, i have one concern.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp
16421 ↗(On Diff #217409)

OldShuffle

16431–16432 ↗(On Diff #217409)

Just x/y like in comments?

16437 ↗(On Diff #217409)

Maybe XOffset?

16441 ↗(On Diff #217409)

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
16421 ↗(On Diff #217409)

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

16441 ↗(On Diff #217409)

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

16447 ↗(On Diff #217409)

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
16421 ↗(On Diff #217409)

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
16441 ↗(On Diff #217409)

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
16435 ↗(On Diff #217666)

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.