[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

722

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

llvm/lib/Transforms/Vectorize/VPlanValue.h

280

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

722

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

280

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

722

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

215

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

192

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

722

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

+1

[gilr]

llvm/lib/Transforms/Vectorize/VPlanValue.h

280

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

722

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

280

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

struct VPTransformState {
 
   /// Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
   InnerLoopVectorizer *ILV;
 
   /// Pointer to the VPlan code is generated for.
   VPlan *Plan;
 };
 
+/// VPUsers instance used by VPBlockBase to manage CondBit and the block
+/// predicate. Currently VPBlockUsers are used in VPBlockBase for historical
+/// reasons, but in the future the only VPUsers should either be recipes or
+/// live-outs.VPBlockBase uses.
+class VPBlockUser : public VPUser {
+public:
+  VPBlockUser() : VPUser({}, VPUserID::Block) {}
+
+  VPValue *getSingleOperandOrNull() {
+    if (getNumOperands() == 1)
+      return getOperand(0);
+
+    return nullptr;
+  }
+  const VPValue *getSingleOperandOrNull() const {
+    if (getNumOperands() == 1)
+      return getOperand(0);
+
+    return nullptr;
+  }
+
+  void resetSingleOpUser(VPValue *NewVal) {
+    assert(getNumOperands() <= 1 && "Didn't expect more than one operand!");
+    if (!NewVal) {
+      if (getNumOperands() == 1)
+        removeLastOperand();
+      return;
+    }
+
+    if (getNumOperands() == 1)
+      setOperand(0, NewVal);
+    else
+      addOperand(NewVal);
+  }
+};
+
 /// VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
 /// A VPBlockBase can be either a VPBasicBlock or a VPRegionBlock.
 class VPBlockBase {
   friend class VPBlockUtils;
 
   const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
 
   /// An optional name for the block.
   std::string Name;
 
   /// The immediate VPRegionBlock which this VPBlockBase belongs to, or null if
   /// it is a topmost VPBlockBase.
   VPRegionBlock *Parent = nullptr;
 
   /// List of predecessor blocks.
   SmallVector<VPBlockBase *, 1> Predecessors;
 
   /// List of successor blocks.
   SmallVector<VPBlockBase *, 1> Successors;
 
   /// Successor selector managed by a VPUser. For blocks with zero or one
   /// successors, there is no operand. Otherwise there is exactly one operand
   /// which is the branch condition.
-  VPUser CondBitUser;
+  VPBlockUser CondBitUser;
 
   /// If the block is predicated, its predicate is stored as an operand of this
   /// VPUser to maintain the def-use relations. Otherwise there is no operand
   /// here.
-  VPUser PredicateUser;
+  VPBlockUser PredicateUser;
 
   /// VPlan containing the block. Can only be set on the entry block of the
   /// plan.
   VPlan *Plan = nullptr;
 
   /// Add \p Successor as the last successor to this block.
   void appendSuccessor(VPBlockBase *Successor) {
     assert(Successor && "Cannot add nullptr successor!");

 /// 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;
 
   /// Returns true for PHI-like recipes.
   bool isPhi() const {
     return getVPDefID() == VPWidenIntOrFpInductionSC || getVPDefID() == VPWidenPHISC ||
       getVPDefID() == VPPredInstPHISC || getVPDefID() == VPWidenCanonicalIVSC;
   }

llvm/lib/Transforms/Vectorize/VPlan.cpp

 VPBlockBase *VPBlockBase::getEnclosingBlockWithPredecessors() {
   if (!Predecessors.empty() || !Parent)
     return this;
   assert(Parent->getEntry() == this &&
          "Block w/o predecessors not the entry of its parent.");
   return Parent->getEnclosingBlockWithPredecessors();
 }
 
-static VPValue *getSingleOperandOrNull(VPUser &U) {
-  if (U.getNumOperands() == 1)
-    return U.getOperand(0);
-
-  return nullptr;
-}
-
-static const VPValue *getSingleOperandOrNull(const VPUser &U) {
-  if (U.getNumOperands() == 1)
-    return U.getOperand(0);
-
-  return nullptr;
-}
-
-static void resetSingleOpUser(VPUser &U, VPValue *NewVal) {
-  assert(U.getNumOperands() <= 1 && "Didn't expect more than one operand!");
-  if (!NewVal) {
-    if (U.getNumOperands() == 1)
-      U.removeLastOperand();
-    return;
-  }
-
-  if (U.getNumOperands() == 1)
-    U.setOperand(0, NewVal);
-  else
-    U.addOperand(NewVal);
-}
-
 VPValue *VPBlockBase::getCondBit() {
-  return getSingleOperandOrNull(CondBitUser);
+  return CondBitUser.getSingleOperandOrNull();
 }
 
 const VPValue *VPBlockBase::getCondBit() const {
-  return getSingleOperandOrNull(CondBitUser);
+  return CondBitUser.getSingleOperandOrNull();
 }
 
-void VPBlockBase::setCondBit(VPValue *CV) {
-  resetSingleOpUser(CondBitUser, CV);
-}
+void VPBlockBase::setCondBit(VPValue *CV) { CondBitUser.resetSingleOpUser(CV); }
 
 VPValue *VPBlockBase::getPredicate() {
-  return getSingleOperandOrNull(PredicateUser);
+  return PredicateUser.getSingleOperandOrNull();
 }
 
 const VPValue *VPBlockBase::getPredicate() const {
-  return getSingleOperandOrNull(PredicateUser);
+  return PredicateUser.getSingleOperandOrNull();
 }
 
 void VPBlockBase::setPredicate(VPValue *CV) {
-  resetSingleOpUser(PredicateUser, CV);
+  PredicateUser.resetSingleOpUser(CV);
 }
 
 void VPBlockBase::deleteCFG(VPBlockBase *Entry) {
   SmallVector<VPBlockBase *, 8> Blocks(depth_first(Entry));
 
   for (VPBlockBase *Block : Blocks)
     delete Block;
 }

llvm/lib/Transforms/Vectorize/VPlanValue.h

 
 // Forward declarations.
 class raw_ostream;
 class Value;
 class VPDef;
 class VPSlotTracker;
 class VPUser;
 class VPRecipeBase;
+class VPBlockUser;
 class VPWidenMemoryInstructionRecipe;
 
 // This is the base class of the VPlan Def/Use graph, used for modeling the data
 // flow into, within and out of the VPlan. VPValues can stand for live-ins
 // coming from the input IR, instructions which VPlan will generate if executed
 // and live-outs which the VPlan will need to fix accordingly.
 class VPValue {
   friend class VPBuilder;
#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 {
+public:
+  /// 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.
+    Block
+  };
+
+private:
   SmallVector<VPValue *, 2> Operands;
 
+  VPUserID 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(ArrayRef<VPValue *> Operands, VPUserID ID) : 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)
+      : VPUser(ArrayRef<VPValue *>(Operands), ID) {}
+
+  template <typename IterT>
+  VPUser(iterator_range<IterT> Operands, VPUserID ID) : ID(ID) {
     for (VPValue *Operand : Operands)
       addOperand(Operand);
   }
 
+public:
+  VPUser() = delete;
   VPUser(const VPUser &) = delete;
   VPUser &operator=(const VPUser &) = delete;
   virtual ~VPUser() {
     for (VPValue *Op : operands())
       Op->removeUser(*this);
   }
 
+  VPUserID getVPUserID() const { return ID; }
+
   void addOperand(VPValue *Operand) {
     Operands.push_back(Operand);
     Operand->addUser(*this);
   }
 
   unsigned getNumOperands() const { return Operands.size(); }
   inline VPValue *getOperand(unsigned N) const {
     assert(N < Operands.size() && "Operand index out of bounds");
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);
 };
 
 /// 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;
 
   /// Subclass identifier (for isa/dyn_cast).