Page MenuHomePhabricator

[VPlan] Disconnect VPValue and VPUser.
ClosedPublic

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

Details

Summary

This refactors VPuser to not inherit from VPValue to facilitate
introducing operations that introduce multiple VPValues (e.g.
VPInterleaveRecipe).

Diff Detail

Event Timeline

fhahn created this revision.Jul 27 2020, 10:34 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 27 2020, 10:34 AM
Ayal added a comment.Sep 21 2020, 8:52 AM

This looks good to me, as part of the effort to support VPlan def-use modeling and traversals.
Note that top-down traversal from VPValue to its VPUsers, will now need to check if each VPUser isa single-def recipe/VPInstruction in order to continue downwards to its VPUsers, etc., facilitating multi-def recipes.

llvm/lib/Transforms/Vectorize/VPlanSLP.cpp
164–165

nit: maybe worth reiterating next to the cast that

// Currently we only support VPInstructions.
225

nit: worth simplifying by setting here:

auto I1 = dyn_cast<VPInstruction>(V1);
auto I2 = dyn_cast<VPInstruction>(V2);

and reuse them below instead of isa<> and cast<>'s?

llvm/lib/Transforms/Vectorize/VPlanValue.h
12–13

The documentation of this class hierarchy deserves an update, as does docs/Proposals/VectorizationPlan.rst

I was trying very recently to get VPlan to perform some vector combines. Things like recognizing vmulh patterns.

The code I had was still in a very rough state but I ended up going in completely the opposite direction. I had VPRecipeBase inherit from VPUser, which in turn inherited from VPValue. Like I said it was all very rough and I'm not sure yet if it was necessary, but I felt like it simplified things. It was useful to know you could inspect operands and uses of any recipe, and properly walk up and down the def-uses chain. Perform things like replaceAllUsesWith and recursively delete dead recipes after replacing them with others.

Perhaps I need to look at that again, as I certainly hadn't tried to tackle multiple producing values. My gut instinct would be to use something like the SDValue from ISel, but I hadn't looked at all into what that would really look like. This way might well be better in the long run, I'm not sure. I had gotten distracted into cost modelling instead..

This looks good to me, as part of the effort to support VPlan def-use modeling and traversals.
Note that top-down traversal from VPValue to its VPUsers, will now need to check if each VPUser isa single-def recipe/VPInstruction in order to continue downwards to its VPUsers, etc., facilitating multi-def recipes.

Thanks Ayal! I'll address the comments shortly.

I was trying very recently to get VPlan to perform some vector combines. Things like recognizing vmulh patterns.

The code I had was still in a very rough state but I ended up going in completely the opposite direction. I had VPRecipeBase inherit from VPUser, which in turn inherited from VPValue. Like I said it was all very rough and I'm not sure yet if it was necessary, but I felt like it simplified things. It was useful to know you could inspect operands and uses of any recipe, and properly walk up and down the def-uses chain. Perform things like replaceAllUsesWith and recursively delete dead recipes after replacing them with others.

I am not sure if it is completely the opposite direction.

With this patch, VPRecipeBase is also a VPUser and a VPValue, it just inherits from both directly, rather than indirectly through VPValue. Note that 'replacing all uses with & co' are provided by VPValue, so all instances that could previously be RAUW'd can still be RAUW'd. The only major difference should be that in the future we may need some extra code to get the uses of a VPUser.

This will help finishing the move to model the use-def chains entirely in VPlan, which in turn should make it possible to easily do VPlan-to-VPlan transformations, like the vector combines you mentioned.

Does that make sense?

With this patch, VPRecipeBase is also a VPUser and a VPValue, it just inherits from both directly, rather than indirectly through VPValue. Note that 'replacing all uses with & co' are provided by VPValue, so all instances that could previously be RAUW'd can still be RAUW'd. The only major difference should be that in the future we may need some extra code to get the uses of a VPUser.

Do you mean VPInstruction is a VPUser and a VPValue? I really meant that _all_ recipes were VPValues and VPUsers, moving it to VPRecipeBase.

Like I said, the code I have is very rough, and I'm not sure it's in any way mutually exclusive with going in this direction. I will try and rebase what I have onto your patches, working in the same way. This is the kind of transform it was doing (which was working pretty well it seemed, minus the costing not being accounted for):

static bool tryCombineToMulh(VPBasicBlock::reverse_iterator &It, VPlanPtr &Plan,
                             VPRecipeBuilder &RecipeBuilder) {
  VPWidenRecipe *RV = dyn_cast<VPWidenRecipe>(&*It);
  if (!RV)
    return false;

  // trunc(lsr(mul(ext, ext)), BW)) -> mulhs/mulhu
  Type *Ty = RV->getType();
  unsigned BW = Ty->getScalarSizeInBits();

  VPValue *Mul;
  // TODOD: One use checks?
  if (!match(RV, vp_Trunc(vp_LShr(vp_Value(Mul), vp_SpecificInt(BW)))))
    return false;

  VPValue *A, *B;
  unsigned Opcode = 0;
  if (match(Mul, vp_Mul(vp_SExt(vp_Value(A)), vp_SExt(vp_Value(B)))))
    Opcode = VPInstruction::Mulhs;
  else if (match(Mul, vp_Mul(vp_ZExt(vp_Value(A)), vp_ZExt(vp_Value(B)))))
    Opcode = VPInstruction::Mulhu;
  else
    return false;

  unsigned MulBW = Mul->getType()->getScalarSizeInBits();
  if (MulBW > BW * 2)
    return false;

  if (A->getType() != Ty || B->getType() != Ty) // TODOD: Generalize
    return false;

  auto *Mulh = new VPInstruction(Opcode, {A, B});
  RV->getParent()->insert(Mulh, RV->getIterator());
  RV->replaceAllUsesWith(Mulh);
  RV->recursivelyDeleteUnusedRecipes();
  It = Mulh->getReverseIterator();
  return true;
}

bool LoopVectorizationPlanner::adjustVPlanForVectorPatterns(
    VPlanPtr &Plan, VPRecipeBuilder &RecipeBuilder) {
  bool Changed = false;
  for (VPBlockBase *Block : depth_first(Plan->getEntry())) {
    if (auto *BB = dyn_cast<VPBasicBlock>(Block)) {
      for(VPBasicBlock::reverse_iterator It = BB->rbegin(), E = BB->rend(); It != E; ++It) {
        if (true /*TODOD: TTI->hasVectorPattern(Mulh)*/)
          Changed |= tryCombineToMulh(It, Plan, RecipeBuilder);
      }
    }
  }

  return Changed;
}

As all the vp_Mul etc are really looking at VPWidenRecipe, perhaps this can work simply enough. The idea was to probably make them match VPWidenRecipe or VPInstruction. recursivelyDeleteUnusedRecipes might be tougher, but perhaps still possible. I will see.

fhahn added a comment.Sep 21 2020, 1:17 PM

With this patch, VPRecipeBase is also a VPUser and a VPValue, it just inherits from both directly, rather than indirectly through VPValue. Note that 'replacing all uses with & co' are provided by VPValue, so all instances that could previously be RAUW'd can still be RAUW'd. The only major difference should be that in the future we may need some extra code to get the uses of a VPUser.

Do you mean VPInstruction is a VPUser and a VPValue? I really meant that _all_ recipes were VPValues and VPUsers, moving it to VPRecipeBase.

Sorry, I did not mean that everything will be changed in this patch. But the linked patches gradually turn all the recipes into VPValues and update VPInterleaveRecipe to produce multiple values (and moves VPlan codegen to use that). So with the current patch alone, it is not yet possible to traverse def-use chains in recipes, but once the transition is done, it should be possible to traverse in both directions. (I think most recipes should already be ready to be turned into VPUser, let me check which ones are still missing)

As Ayal mentioned, when walking from defs to users there walker may need to check the user in order to continue traversing, but it should be relatively straight forward to provide some nice helpers for that.

It would be great to have some concrete simple transforms using it as soon as its ready to make sure everything works well together, so if we could collaborate on that, that would be great!

It would be great to have some concrete simple transforms using it as soon as its ready to make sure everything works well together, so if we could collaborate on that, that would be great!

Yeah, that sounds good. vmulh worked well I though, but I ended up making some fairly major modifications. And it did need to handle costing through vplan to really get anywhere. I will see if I can come up with anything for that too. I think just having a conversation about some of these design details is helpful in itself.

Sorry, I did not mean that everything will be changed in this patch. But the linked patches gradually turn all the recipes into VPValues and update VPInterleaveRecipe to produce multiple values (and moves VPlan codegen to use that). So with the current patch alone, it is not yet possible to traverse def-use chains in recipes, but once the transition is done, it should be possible to traverse in both directions. (I think most recipes should already be ready to be turned into VPUser, let me check which ones are still missing)

Ok. It sounds like you envision eventually that all VPRecipeBases' are VPValues then. I was jumping to that goal in one step. I liked making is part of VPRecipeBases as it simplifies the inheritance a lot.

I will try to at least update VPReductionRecipe, and we can see where we can go from there.

fhahn updated this revision to Diff 293467.Sep 22 2020, 8:37 AM
fhahn marked 2 inline comments as done.

Address Ayal's comments, thanks!

It would be great to have some concrete simple transforms using it as soon as its ready to make sure everything works well together, so if we could collaborate on that, that would be great!

Yeah, that sounds good. vmulh worked well I though, but I ended up making some fairly major modifications. And it did need to handle costing through vplan to really get anywhere. I will see if I can come up with anything for that too. I think just having a conversation about some of these design details is helpful in itself.

Yes, VPlan based cost modeling is another big missing piece! But it should be possible to make progress in relatively small steps I think starting with the pattern matching & transformations?

Sorry, I did not mean that everything will be changed in this patch. But the linked patches gradually turn all the recipes into VPValues and update VPInterleaveRecipe to produce multiple values (and moves VPlan codegen to use that). So with the current patch alone, it is not yet possible to traverse def-use chains in recipes, but once the transition is done, it should be possible to traverse in both directions. (I think most recipes should already be ready to be turned into VPUser, let me check which ones are still missing)

Ok. It sounds like you envision eventually that all VPRecipeBases' are VPValues then. I was jumping to that goal in one step. I liked making is part of VPRecipeBases as it simplifies the inheritance a lot.

*Almost* all recipes can be VPValues (which the linked patches do), but some might not be VPValues directly but something that produces multiple VPValues (like an interleave group currently but there may be more in the future, the modeling should be able to capture this naturally). But that should make traversing only slightly more complicated. When you are just interested in recipes that are also VPValues, nothing should really change.

Ayal accepted this revision.Sep 22 2020, 3:35 PM

This looks good to me, thanks!

This revision is now accepted and ready to land.Sep 22 2020, 3:35 PM
This revision was landed with ongoing or failed builds.Sep 23 2020, 6:55 AM
This revision was automatically updated to reflect the committed changes.

Hmm. OK. I do strong believe that we should be moving towards def-use chains, so in general I'm glad to see that happening.

I'm less convinced about the multiple inheritance. That seems like an antipattern. We can likely make it work either way, but can you try and explain why you think that way is better? As opposed to making all VPRecipe's inherit from VPValue from VPRecipeBase? Perhaps I'm too stuck in the "llvm-ir" way of thinking, with VPValue being Value, VPUser being User, VPRecipeBase being Instruction and the individual recipes being the different instructions.

I have put up D88152 and D88153, to try and show the difference between what I came up with for the two approaches. (They are still very rough. Both can probably be made to work, I'm just not sure what the advantage of the multiple inheritance version is)

fhahn added a comment.Sep 23 2020, 8:36 AM

Hmm. OK. I do strong believe that we should be moving towards def-use chains, so in general I'm glad to see that happening.

I'm less convinced about the multiple inheritance. That seems like an antipattern. We can likely make it work either way, but can you try and explain why you think that way is better? As opposed to making all VPRecipe's inherit from VPValue from VPRecipeBase? Perhaps I'm too stuck in the "llvm-ir" way of thinking, with VPValue being Value, VPUser being User, VPRecipeBase being Instruction and the individual recipes being the different instructions.

The main reason for migrating a recipe at a time is to keep the reviews small so we can make sure we properly update all places in the code that previously referenced the underlying instruction, e.g. during codegen. Another example is VPUser. I think we only want to make VPRecipeBase inherit from VPUser once *all* recipes manage their operands via VPUser. Otherwise you cannot rely on the VPUser operands being the source of truth.

In particular, just making VPRecipeBase inherit from VPValue without updating the existing code will result in subtle problems, e.g. when updating VPValue operands of a recipe, but codegen still using the original IR references.

Once all recipes are updated and inherit from VPValue we can move it to VPRecipeBase. The main caveat is VPInterleaveRecipe, which is not really a VPValue, but rather something that produces multiple values. We can also make that a VPValue, but not reference that particular value anywhere else, add all users of sub-values to the users of the 'virtual' VPValue and treat it as a convenient way to access all users of all sub-values. That's not completely clean, but we could also extract the user part into something else that can be inherited more cleanly from VPRecipeBase

I have put up D88152 and D88153, to try and show the difference between what I came up with for the two approaches. (They are still very rough. Both can probably be made to work, I'm just not sure what the advantage of the multiple inheritance version is)

Thanks for sharing. As mentioned earlier, the main reason at the moment is to ensure a step-by-step transition and once all recipes are migrated the common class can be hoisted to VPRecipeBase. I hope the explanation makes sense.

The main reason for migrating a recipe at a time is to keep the reviews small so we can make sure we properly update all places in the code that previously referenced the underlying instruction, e.g. during codegen. Another example is VPUser. I think we only want to make VPRecipeBase inherit from VPUser once *all* recipes manage their operands via VPUser. Otherwise you cannot rely on the VPUser operands being the source of truth.

Splitting things up sounds very smart. My question was less about doing that and more about whether we are heading towards the correct final design. And trying to show how that might look, when we work it though in a real problem. After all, the longer we go on using it, the harder it will become to change.

We could consider removing the VPUser concept entirely, for example. If there is only ever one thing that inherits from it (unlike llvm's User), the Operands could just be could be folded into VPRecipeBase.

In particular, just making VPRecipeBase inherit from VPValue without updating the existing code will result in subtle problems, e.g. when updating VPValue operands of a recipe, but codegen still using the original IR references.

Yep. That will certainly be very important for replacing recipes, as the vmulh patch does. Some ways to test some of the invariants would be useful as well.

Once all recipes are updated and inherit from VPValue we can move it to VPRecipeBase. The main caveat is VPInterleaveRecipe, which is not really a VPValue, but rather something that produces multiple values. We can also make that a VPValue, but not reference that particular value anywhere else, add all users of sub-values to the users of the 'virtual' VPValue and treat it as a convenient way to access all users of all sub-values. That's not completely clean, but we could also extract the user part into something else that can be inherited more cleanly from VPRecipeBase

I was thinking of complex nodes too, which may have multiple outputs. It will depend on how they are represented though, they may just remain as single output nodes, but you match them to operate differently on different lanes.

Thanks for sharing. As mentioned earlier, the main reason at the moment is to ensure a step-by-step transition and once all recipes are migrated the common class can be hoisted to VPRecipeBase. I hope the explanation makes sense.

Like I said I'm happy that we are moving towards the ability to do this better. It will be good to see VPlan being able to start to make some real improvements! If we are happy enough with this way of doing things, at least currently, then I can go and make some more sensibly sized patches :)

fhahn added a comment.Sep 27 2020, 9:33 AM

Thanks for sharing. As mentioned earlier, the main reason at the moment is to ensure a step-by-step transition and once all recipes are migrated the common class can be hoisted to VPRecipeBase. I hope the explanation makes sense.

Like I said I'm happy that we are moving towards the ability to do this better. It will be good to see VPlan being able to start to make some real improvements! If we are happy enough with this way of doing things, at least currently, then I can go and make some more sensibly sized patches :)

I experimented a bit more and came up with another alternative: allow VPValue to model 3 different things: 1) concrete VPValues, 2) sub VPValues and 3) virtual VPValue: D88380

Managing those 3 in VPValue directly simplifies things further down a bit and I put up 2 more follow-on patches that turn VPReciepBase into a VPValue (D88379) and then also a VPUser (D88378). The last one also contains a unit test that looks upwards & downwards along the def-use chains. Note that we should probably move most/all remaining recipes to be VPValues and manage operands as VPUser before the last 2 patches.

Overall this probably results in a simpler structure overall. If we want, we could then also fold VPUser into VPRecipeBase.

I experimented a bit more and came up with another alternative: allow VPValue to model 3 different things: 1) concrete VPValues, 2) sub VPValues and 3) virtual VPValue: D88380

Managing those 3 in VPValue directly simplifies things further down a bit and I put up 2 more follow-on patches that turn VPReciepBase into a VPValue (D88379) and then also a VPUser (D88378). The last one also contains a unit test that looks upwards & downwards along the def-use chains. Note that we should probably move most/all remaining recipes to be VPValues and manage operands as VPUser before the last 2 patches.

Overall this probably results in a simpler structure overall. If we want, we could then also fold VPUser into VPRecipeBase.

Sounds good. Multiple results certainly does complicate things a bit. I have not thought a lot about them, but I agree this will be simpler overall from the things I was trying to write.

I've put up D88382 for VPReductionRecipe.