[VPlan] Add VPUserID to distinguish between recipes and others.

[fhahn]

Summary

This allows cast/dyn_cast'ing from VPUser to recipes. This is needed
because there are VPUsers that are not recipes.

[a.elovikov]

llvm/lib/Transforms/Vectorize/VPlan.h

686

Can we make getVPUserID() protected instead of friendship above?

llvm/lib/Transforms/Vectorize/VPlanValue.h

281

1. Why is that important? Do we rely on it or is it simply to prevent uncontrolled growth?
2. Why do we expect it to be the same on 32/64-bit platforms? Don't we have any pointers inside the object? I'd expect the vtable itself would make it different...

[fhahn]

Add comment about the Other ID type, making clear that currently there are VPUsers in VPBlockBase, but in the future Other should only be used for live-outs.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.h

686

Unfortunately I don't think so. If it's protected, we can access it from inside a VPRecipeBase object, but here we need to access it from a VPUser pointer directly.

llvm/lib/Transforms/Vectorize/VPlanValue.h

281

Why is that important? Do we rely on it or is it simply to prevent uncontrolled growth?

It's just to prevent accidental growth, but it is not strictly necessary (and we don't have static asserts for other sizes yet), but it is a common pattern, e.g. in various key classes in Clang to prevent unnoticed size growth.

Why do we expect it to be the same on 32/64-bit platforms?

I think 48 should be the upper bound on 64 bit platforms (unless there are differences caused by different 64 bit operating systems) and on 32-bit platforms it should be less than or equal.

[fhahn]

ping :)

[a.elovikov]

LGTM.

llvm/lib/Transforms/Vectorize/VPlan.h

686

I'd rather make the enum/method public then, but it's very subjective.

[Ayal]

Non-recipe "other" VPUsers are quite exceptional ... would it suffice to have (native) VPlan hold all 'dangling' non-recipe VPUsers of its VPBasicBlocks, as an alternative, until these are cleaned up?

[fhahn]

In D100257#2718728, @Ayal wrote:

Non-recipe "other" VPUsers are quite exceptional ... would it suffice to have (native) VPlan hold all 'dangling' non-recipe VPUsers of its VPBasicBlocks, as an alternative, until these are cleaned up?

The blocks need to use the VPUsers to access the current value they hold I think, so I am not sure how the VPlan holding the VPUsers would look like unfortunately. It would be great if you could elaborate in a bit more detail, in case I am missing something.

[Ayal]

In D100257#2725020, @fhahn wrote:

In D100257#2718728, @Ayal wrote:

Non-recipe "other" VPUsers are quite exceptional ... would it suffice to have (native) VPlan hold all 'dangling' non-recipe VPUsers of its VPBasicBlocks, as an alternative, until these are cleaned up?

The blocks need to use the VPUsers to access the current value they hold I think, so I am not sure how the VPlan holding the VPUsers would look like unfortunately. It would be great if you could elaborate in a bit more detail, in case I am missing something.

The blocks will still have their VPUsers (in native; until this gets cleaned up). The thought is that whoever needs to distinguish between a block'd VPUser and a recipe'd one, would do so by consulting VPlan, rather than isa-ing the VPUser.

[fhahn]

In D100257#2725036, @Ayal wrote:

In D100257#2725020, @fhahn wrote:

In D100257#2718728, @Ayal wrote:

Non-recipe "other" VPUsers are quite exceptional ... would it suffice to have (native) VPlan hold all 'dangling' non-recipe VPUsers of its VPBasicBlocks, as an alternative, until these are cleaned up?

The blocks need to use the VPUsers to access the current value they hold I think, so I am not sure how the VPlan holding the VPUsers would look like unfortunately. It would be great if you could elaborate in a bit more detail, in case I am missing something.

The blocks will still have their VPUsers (in native; until this gets cleaned up). The thought is that whoever needs to distinguish between a block'd VPUser and a recipe'd one, would do so by consulting VPlan, rather than isa-ing the VPUser.

Oh I see what you mean now, thanks! That sounds like a viable alternative.

IIUC we will have non-recipe users in the future (e.g. live-outs) so I think we need to be able to make this distinction in the future as well, once the current VPUsers in the native path get cleaned up. If that's true, I think having to consult a VPlan to check what type of user we are dealing with seems a bit clunky in the long term (and breaks with the common pattern used for other VP* classes and other places in LLVM). Unless we anticipate a more fine-grained distinction between VPUsers in the future, we could also just use a boolean flag instead of the enum, to make it less appealing to add new VPUser types.

If we don't anticipate having to distinguish between recipe and non-recipe VPUsers in the future, then I think using a map in the plan directly makes a lot of sense (and in that case we might want to get rid of the separate VPUser class completely?)

[a.elovikov]

IIUC we will have non-recipe users in the future (e.g. live-outs)

Not making a request or committing to implement myself in near future, but can we model live-outs as a recipe as well? I'm thinking about something like vplan-ret %val0, %val1, %val2 that would have VPValues as operands and corresponding llvm::Uses inside itself (like shufflevector contains mask argument or `PHINode' contains incoming blocks.

[gilr]

In D100257#2726688, @fhahn wrote:

In D100257#2725036, @Ayal wrote:

In D100257#2725020, @fhahn wrote:

In D100257#2718728, @Ayal wrote:

Non-recipe "other" VPUsers are quite exceptional ... would it suffice to have (native) VPlan hold all 'dangling' non-recipe VPUsers of its VPBasicBlocks, as an alternative, until these are cleaned up?

The blocks need to use the VPUsers to access the current value they hold I think, so I am not sure how the VPlan holding the VPUsers would look like unfortunately. It would be great if you could elaborate in a bit more detail, in case I am missing something.

The blocks will still have their VPUsers (in native; until this gets cleaned up). The thought is that whoever needs to distinguish between a block'd VPUser and a recipe'd one, would do so by consulting VPlan, rather than isa-ing the VPUser.

Oh I see what you mean now, thanks! That sounds like a viable alternative.

IIUC we will have non-recipe users in the future (e.g. live-outs) so I think we need to be able to make this distinction in the future as well, once the current VPUsers in the native path get cleaned up. If that's true, I think having to consult a VPlan to check what type of user we are dealing with seems a bit clunky in the long term (and breaks with the common pattern used for other VP* classes and other places in LLVM). Unless we anticipate a more fine-grained distinction between VPUsers in the future, we could also just use a boolean flag instead of the enum, to make it less appealing to add new VPUser types.

If we don't anticipate having to distinguish between recipe and non-recipe VPUsers in the future, then I think using a map in the plan directly makes a lot of sense (and in that case we might want to get rid of the separate VPUser class completely?)

The anticipated long-term need for non-recipe VPUsers is indeed to represent live-outs, along with their underlying IR Value, or rather Instruction; analogous to VPValue::getLiveInIRValue(). This would call for a derived VPLiveOut non-recipe subclass of VPUser.

VPUser class itself should probably be pure virtual, similar to User, to avoid having a potential kitchen sink of dangling opaque instances. Instead of representing arbitrary "other"/"non-recipe" instances, the current VPUsers of VPBasicBlock predicates and conditions could be represented as specific, concrete subclasses of VPUser, potentially until they are cleaned up. WDYT?

llvm/lib/Transforms/Vectorize/VPlanValue.h

217–218

Do we have to have a default constructor? If so, shouldn't the default ID be Other?

[Ayal]

In D100257#2733025, @gilr wrote:

The anticipated long-term need for non-recipe VPUsers is indeed to represent live-outs, along with their underlying IR Value, or rather Instruction; analogous to VPValue::getLiveInIRValue(). This would call for a derived VPLiveOut non-recipe subclass of VPUser.

VPUser class itself should probably be pure virtual, similar to User, to avoid having a potential kitchen sink of dangling opaque instances. Instead of representing arbitrary "other"/"non-recipe" instances, the current VPUsers of VPBasicBlock predicates and conditions could be represented as specific, concrete subclasses of VPUser, potentially until they are cleaned up. WDYT?

+1

llvm/lib/Transforms/Vectorize/VPlanValue.h

191

nit: above comment needs updating.

[fhahn]

Rebased and addressed comments:

1. Turn VPUser into a pure virtual class.
2. Add VPBlockUser, move update logic to that class
3. Remove default values for ID in constructors.
4. Remove default constructor.

[fhahn]

In D100257#2733027, @Ayal wrote:

In D100257#2733025, @gilr wrote:

The anticipated long-term need for non-recipe VPUsers is indeed to represent live-outs, along with their underlying IR Value, or rather Instruction; analogous to VPValue::getLiveInIRValue(). This would call for a derived VPLiveOut non-recipe subclass of VPUser.

VPUser class itself should probably be pure virtual, similar to User, to avoid having a potential kitchen sink of dangling opaque instances. Instead of representing arbitrary "other"/"non-recipe" instances, the current VPUsers of VPBasicBlock predicates and conditions could be represented as specific, concrete subclasses of VPUser, potentially until they are cleaned up. WDYT?

+1

Thanks, I updated the code to turn VPUser in a virtual base class and added s subclass for the uses in VPBlockBase. WDYT?

(For now I used a dummy function VPUser::makeVPUserVirtual to turn VPUser into a pure virtual class. Not sure if there's a different way?)

[fhahn]

@gilr @Ayal what are your thoughts on the latest changes? Would you prefer a different direction?

[gilr]

Thanks, I updated the code to turn VPUser in a virtual base class and added s subclass for the uses in VPBlockBase. WDYT?

Looks good!

(For now I used a dummy function VPUser::makeVPUserVirtual to turn VPUser into a pure virtual class. Not sure if there's a different way?)

Wouldn't making the constructors protected suffice?

llvm/lib/Transforms/Vectorize/VPlan.h

686

I'd rather make the enum/method public then, but it's very subjective.

+1

[gilr]

llvm/lib/Transforms/Vectorize/VPlanValue.h

281

This seems a bit premature. Perhaps better to have this discussion separate of this patch.

[fhahn]

Update to make getVPUserID() and the ID enum public, make constructors protected and remove static assert.

In D100257#2747524, @gilr wrote:

Thanks, I updated the code to turn VPUser in a virtual base class and added s subclass for the uses in VPBlockBase. WDYT?
(For now I used a dummy function VPUser::makeVPUserVirtual to turn VPUser into a pure virtual class. Not sure if there's a different way?)

Wouldn't making the constructors protected suffice?

Yeah, I guess we do not need it to be pure virtual, updated!

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.h

686

I don't mind either way, I made it public. But this has the dis-advantage that the IDs themselves are exposed to users, which should never use them. Probably not a very big deal though.

llvm/lib/Transforms/Vectorize/VPlanValue.h

281

It is just an extra guard which make unintended size changes visible (similar to other places in LLVM/Clang), but it can be a separate patch. I removed it for now.

[fhahn]

Remove another unnecessary friendship relation.

[fhahn]

@gilr I think your comments should be addressed and I am planning land this in the next few days, unless there are any additional comments :)

[gilr]

In D100257#2761910, @fhahn wrote:

@gilr I think your comments should be addressed and I am planning land this in the next few days, unless there are any additional comments :)

Yes they are, and no further comments :) ... LGTM!

llvm/lib/Transforms/Vectorize/VPlan.h

 /// and is responsible for deleting its defined values. Single-value
 /// VPRecipeBases that also inherit from VPValue must make sure to inherit from
 /// VPRecipeBase before VPValue.
 class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock>,
                      public VPDef,
                      public VPUser {
   friend VPBasicBlock;
   friend class VPBlockUtils;
-
+  friend class VPUser;
 
   /// Each VPRecipe belongs to a single VPBasicBlock.
   VPBasicBlock *Parent = nullptr;
 
 public:
   VPRecipeBase(const unsigned char SC, ArrayRef<VPValue *> Operands)
-      : VPDef(SC), VPUser(Operands) {}
+      : VPDef(SC), VPUser(Operands, VPUser::VPUserID::Recipe) {}
 
   template <typename IterT>
   VPRecipeBase(const unsigned char SC, iterator_range<IterT> Operands)
-      : VPDef(SC), VPUser(Operands) {}
+      : VPDef(SC), VPUser(Operands, VPUser::VPUserID::Recipe) {}
   virtual ~VPRecipeBase() = default;
 
   /// \return the VPBasicBlock which this VPRecipe belongs to.
   VPBasicBlock *getParent() { return Parent; }
   const VPBasicBlock *getParent() const { return Parent; }
 
   /// The method which generates the output IR instructions that correspond to
   /// this VPRecipe, thereby "executing" the VPlan.
public:
   }
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPDef *D) {
     // All VPDefs are also VPRecipeBases.
     return true;
   }
 
+  static inline bool classof(const VPUser *U) {
+    return U->getVPUserID() == VPUser::VPUserID::Recipe;
+  }
+
   /// Returns true if the recipe may have side-effects.
   bool mayHaveSideEffects() const;
 };
 
 inline bool VPUser::classof(const VPDef *Def) {
   return Def->getVPDefID() == VPRecipeBase::VPInstructionSC ||
          Def->getVPDefID() == VPRecipeBase::VPWidenSC ||
          Def->getVPDefID() == VPRecipeBase::VPWidenCallSC ||

llvm/lib/Transforms/Vectorize/VPlanValue.h

#endif
   }
 };
 
 typedef DenseMap<Value *, VPValue *> Value2VPValueTy;
 typedef DenseMap<VPValue *, Value *> VPValue2ValueTy;
 
 raw_ostream &operator<<(raw_ostream &OS, const VPValue &V);
 
 /// This class augments VPValue with operands which provide the inverse def-use
 /// edges from VPValue's users to their defs.
 class VPUser {
+  friend class VPRecipeBase;
+
   SmallVector<VPValue *, 2> Operands;
 
+  /// Subclass identifier (for isa/dyn_cast).
+  enum class VPUserID {
+    Recipe,
+    // TODO: Currently VPUsers are used in VPBlockBase, but in the future the
+    // only VPUsers should either be recipes or live-outs.
+    Other
+  };
+
+  VPUserID ID;
+
+  VPUserID getVPUserID() const { return ID; }
+
 protected:
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print the operands to \p O.
   void printOperands(raw_ostream &O, VPSlotTracker &SlotTracker) const;
 #endif
 
 public:
-  VPUser() {}
-  VPUser(ArrayRef<VPValue *> Operands) {
+  VPUser() : ID(VPUserID::Recipe) {}
+  VPUser(ArrayRef<VPValue *> Operands, VPUserID ID = VPUserID::Other) : ID(ID) {
     for (VPValue *Operand : Operands)
       addOperand(Operand);
   }
 
-  VPUser(std::initializer_list<VPValue *> Operands)
-      : VPUser(ArrayRef<VPValue *>(Operands)) {}
-  template <typename IterT> VPUser(iterator_range<IterT> Operands) {
+  VPUser(std::initializer_list<VPValue *> Operands,
+         VPUserID ID = VPUserID::Other)
+      : VPUser(ArrayRef<VPValue *>(Operands), ID) {}
+
+  template <typename IterT>
+  VPUser(iterator_range<IterT> Operands, VPUserID ID = VPUserID::Other)
+      : ID(ID) {
     for (VPValue *Operand : Operands)
       addOperand(Operand);
   }
 
   VPUser(const VPUser &) = delete;
   VPUser &operator=(const VPUser &) = delete;
   virtual ~VPUser() {
     for (VPValue *Op : operands())
public:
   const_operand_range operands() const {
     return const_operand_range(op_begin(), op_end());
   }
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPDef *Recipe);
 };
 
+static_assert(sizeof(VPUser) <= 48, "size of VPUser changed");
+
 /// This class augments a recipe with a set of VPValues defined by the recipe.
 /// It allows recipes to define zero, one or multiple VPValues. A VPDef owns
 /// the VPValues it defines and is responsible for deleting its defined values.
 /// Single-value VPDefs that also inherit from VPValue must make sure to inherit
 /// from VPDef before VPValue.
 class VPDef {
   friend class VPValue;
 

 
 /// This class can be used to assign consecutive numbers to all VPValues in a
 /// VPlan and allows querying the numbering for printing, similar to the
 /// ModuleSlotTracker for IR values.
 class VPSlotTracker {
   DenseMap<const VPValue *, unsigned> Slots;
   unsigned NextSlot = 0;
 
   void assignSlot(const VPValue *V);
   void assignSlots(const VPlan &Plan);
 
 public:
   VPSlotTracker(const VPlan *Plan = nullptr) {
     if (Plan)
       assignSlots(*Plan);
   }