Page MenuHomePhabricator

[VPlan] Use VPValue def for VPInterleaveRecipe.
AbandonedPublic

Authored by fhahn on Jul 27 2020, 10:42 AM.

Details

Reviewers
Ayal
gilr
rengolin
Summary

This patch turns VPInterleaveRecipe into a VPValue and uses it
during VPlan construction and codegeneration instead of the plain IR
reference where possible.

VPInterleaveRecipe produces multiple result values (one for each group
member). This patch introduces a very simple VPMultiUse class.

VPInterleaveRecipe is a VPValue itself, to track all uses of any result
value. For each member, it also has an individual VPMultiUse which is
used for each member result.

This is mostly a straight-forward initial approach to model operations
with multiple results and I am sure this can be much improved.

Diff Detail

Event Timeline

fhahn created this revision.Jul 27 2020, 10:42 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 27 2020, 10:42 AM
fhahn updated this revision to Diff 292160.Sep 16 2020, 2:48 AM

Split off multi-value parts to D87752

dmgreen added a subscriber: dmgreen.Oct 2 2020, 9:09 AM

Would this now be based upon D88380 now instead?

I was thinking about interleaving a little. Trying some experiments to do with "de-interleaving" code. (Much like the VPlanSLP stuff I think).

The LLVM-IR equivalent of this would be an extract from a struct? Would it be worth representing this in a similar way? There could be a VPInterleaveRecipe which was a VPValue, with multiple "VPExtractElementRecipe"'s or something similar. Those would have 1 operand - the VPInterleaveRecipe and act as the "real" VPValues. They could have a 0 cost and possible hold the index for which element they are getting out of the interleaving group. Maybe there would be a validate method to make sure they remain as the only users of a VPInterleaveRecipe.

It is essentially equivalent to these other ways of handling it as a new type of VPValue, but isn't as tied into the lower levels of the class. What do you think? There might be something about it that wouldn't work, but it might be a simple way to handle these multiple-result nodes.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
7328

Should this be surrounded by some sort of "if it's a load IG" check?

Equally, do we need to be adding the operands for a store IG group?

llvm/lib/Transforms/Vectorize/VPlan.h
1065

This looks left over from something.

fhahn updated this revision to Diff 296186.Oct 5 2020, 7:58 AM

Thanks for taking a look. Addressed comments.

Would this now be based upon D88380 now instead?

Yep, let me update the links in Phab.

I was thinking about interleaving a little. Trying some experiments to do with "de-interleaving" code. (Much like the VPlanSLP stuff I think).

The LLVM-IR equivalent of this would be an extract from a struct? Would it be worth representing this in a similar way? There could be a VPInterleaveRecipe which was a VPValue, with multiple "VPExtractElementRecipe"'s or something similar. Those would have 1 operand - the VPInterleaveRecipe and act as the "real" VPValues. They could have a 0 cost and possible hold the index for which element they are getting out of the interleaving group. Maybe there would be a validate method to make sure they remain as the only users of a VPInterleaveRecipe.

It is essentially equivalent to these other ways of handling it as a new type of VPValue, but isn't as tied into the lower levels of the class. What do you think? There might be something about it that wouldn't work, but it might be a simple way to handle these multiple-result nodes.

Agreed, we could also model it so that VPInterleaveRecipe creates a single vector with all loaded values and then use extract instructions for the different parts of the interleave group. This keeps the modeling in the VPValue classes & co a bit simpler. But it has the cost that we need to add additional instructions/recipes to the plan, which need to be considered by other analyses and transformations. Another problem is that we would have to materialize a vector with all loaded values, which is completely artificial.

I think we have the make the following trade-off. Either we add additional complexity to VPValue & co to model recipes that produce multiple VPValues or we add additional instructions/recipes to the plans we generate.

Personally I think the additional complexity in VPValue & co is worth having simpler plans. Also, there might be additional complex recipes that produce multiple values in the future, which would also benefit from dedicated multi-value support.

fhahn added inline comments.Oct 5 2020, 8:44 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
7328

Right, we only need to add VPValues for load groups, updated. I should probably also add a check that we do not add VPValues to a plan with underlying instructions/values of type void.

llvm/lib/Transforms/Vectorize/VPlan.h
1065

Indeed, that should be gone now, thanks!

Agreed, we could also model it so that VPInterleaveRecipe creates a single vector with all loaded values and then use extract instructions for the different parts of the interleave group. This keeps the modeling in the VPValue classes & co a bit simpler. But it has the cost that we need to add additional instructions/recipes to the plan, which need to be considered by other analyses and transformations. Another problem is that we would have to materialize a vector with all loaded values, which is completely artificial.

I was considering that the VPInterleaveRecipe and the VPExtract's would work in tandem. You would never get the "all loaded values" vector, it would just create the interleaving gorup as it does at the moment, with the VPExtracts representing the values for each item. They would still be special values, VPExtracts would be the only type of recipe that could use a VPInterleave, and the VPExtract would not really contain anything in it's execute method.

You could just consider the VPExtract as a new type of VPUser, not a VPRecipe directly. It's really a convenient way of using the operands to join up the two elements, not having to rely upon UnderlyingOrProducerTy. I guess that's a lot like the VPMultiValue concept. Using a new type of VPUser removes the complexity from VPValue at least!

I think we have the make the following trade-off. Either we add additional complexity to VPValue & co to model recipes that produce multiple VPValues or we add additional instructions/recipes to the plans we generate.

Personally I think the additional complexity in VPValue & co is worth having simpler plans. Also, there might be additional complex recipes that produce multiple values in the future, which would also benefit from dedicated multi-value support.

It feels like we have one type system (VPValueSC/VPInstructionSC/VPWidenSC/etc), and we are adding another system on top of it, for different types of VPValue via UnderlyingOrProducerTy being virtual or subvalues or concrete.

Is there a nice way at the moment of detecting _which_ output you are seeing from a subvalue VPValue? As in which member index it would be from a interleaved group.

llvm/lib/Transforms/Vectorize/VPlan.cpp
966 ↗(On Diff #296186)

Is this used at the moment? Should we be blindly replacing all the different uses with the same value?

llvm/lib/Transforms/Vectorize/VPlan.h
1023–1024

-> VPRecipeBase::VPInterleaveSC

1028

Does anything delete these Defs?

fhahn added a comment.Oct 6 2020, 7:50 AM

Agreed, we could also model it so that VPInterleaveRecipe creates a single vector with all loaded values and then use extract instructions for the different parts of the interleave group. This keeps the modeling in the VPValue classes & co a bit simpler. But it has the cost that we need to add additional instructions/recipes to the plan, which need to be considered by other analyses and transformations. Another problem is that we would have to materialize a vector with all loaded values, which is completely artificial.

I was considering that the VPInterleaveRecipe and the VPExtract's would work in tandem. You would never get the "all loaded values" vector, it would just create the interleaving gorup as it does at the moment, with the VPExtracts representing the values for each item. They would still be special values, VPExtracts would be the only type of recipe that could use a VPInterleave, and the VPExtract would not really contain anything in it's execute method.

You could just consider the VPExtract as a new type of VPUser, not a VPRecipe directly. It's really a convenient way of using the operands to join up the two elements, not having to rely upon UnderlyingOrProducerTy. I guess that's a lot like the VPMultiValue concept. Using a new type of VPUser removes the complexity from VPValue at least!

IICU conceptually the suggested VPExtract and the 'sub-value' are effectively the same thing, just slightly different in terms where exactly they are defined.

I think most of the trade-offs are still similar, with a VPExtract version probably ending up slightly simpler and the sub-value one being a bit more complex but also a bit more explicit in the modeling and more flexible in the future. I think as-is, the 'sub-value' approach is relatively lightweight and does not add too much complexity and the difference between the VPExtract alternative should be relatively small. But if people generally prefer this approach I am happy to update the patches.

I think we have the make the following trade-off. Either we add additional complexity to VPValue & co to model recipes that produce multiple VPValues or we add additional instructions/recipes to the plans we generate.

Personally I think the additional complexity in VPValue & co is worth having simpler plans. Also, there might be additional complex recipes that produce multiple values in the future, which would also benefit from dedicated multi-value support.

It feels like we have one type system (VPValueSC/VPInstructionSC/VPWidenSC/etc), and we are adding another system on top of it, for different types of VPValue via UnderlyingOrProducerTy being virtual or subvalues or concrete.

That definitely can be improved. We should probably just rely on the VPValueID and use that to extract the right value from a union instead of sum type.

Is there a nice way at the moment of detecting _which_ output you are seeing from a subvalue VPValue? As in which member index it would be from a interleaved group.

Currently there's no nice way, but it can easily be done by getting the defining value and then checking which def corresponds to the sub-value. It should be possible to add a convenient interface once there's a need for it.

fhahn updated this revision to Diff 296516.Oct 6 2020, 12:30 PM

Delete sub-value defs in VPInterleaveRecipe, handle virtual values in dropAllReferences, assert that repalceAllUses is not called with virtual VPValues.

fhahn updated this revision to Diff 296519.Oct 6 2020, 12:32 PM
fhahn marked an inline comment as done.

Use VPRecipeBase::VPInterleaveSC.

llvm/lib/Transforms/Vectorize/VPlan.cpp
966 ↗(On Diff #296186)

No it's not used (also not in follow-ups). I added an assert.

llvm/lib/Transforms/Vectorize/VPlan.h
1028

They should be freed in the destructor. Done now.

fhahn abandoned this revision.Wed, Nov 25, 3:13 AM

Superseded by VPDef approach.