[VPlan] Make VPUser a subclass of VPValue again (WIP).

[fhahn]

Summary

This should allow traversing the VPlan def-use chains in both
directions.

[fhahn]

rebase

[fhahn]

Another round of re-basing after recent changes to earlier patches.

[fhahn]

Superseded by the VPDef approach.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

for (Instruction &I : BB->instructionsWithoutDebug()) {
       if (isa<BranchInst>(Instr) || DeadInstructions.count(Instr) ||
           DeadInterleaveGroupMembers.contains(Instr))
         continue;
 
       if (auto Recipe =
               RecipeBuilder.tryToCreateWidenRecipe(Instr, Range, Plan)) {
         // Check if the recipe can be converted to a VPValue. We need the extra
         // down-casting step until VPRecipeBase inherits from VPValue.
-        VPValue *MaybeVPValue = Recipe->toVPValue();
-        if (!Instr->getType()->isVoidTy() && MaybeVPValue) {
+        if (!Instr->getType()->isVoidTy() && !Recipe->isVirtual()) {
           if (NeedDef.contains(Instr))
-            Plan->addOrReplaceVPValue(Instr, MaybeVPValue);
+            Plan->addOrReplaceVPValue(Instr, Recipe);
           else
-            Plan->addVPValue(Instr, MaybeVPValue);
+            Plan->addVPValue(Instr, Recipe);
         }
 
         RecipeBuilder.setRecipe(Instr, Recipe);
         VPBB->appendRecipe(Recipe);
         continue;
       }
 
       // Otherwise, if all widening options failed, Instruction is to be

llvm/lib/Transforms/Vectorize/VPlan.h

bool isLegalToHoistInto() {
     // hoisted into a VPBlockBase.
     return true;
   }
 };
 
 /// VPRecipeBase is a base class modeling a sequence of one or more output IR
 /// instructions.
 class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock>,
-                     public VPValue {
+                     public VPUser {
   friend VPBasicBlock;
   friend class VPBlockUtils;
 
   /// Each VPRecipe belongs to a single VPBasicBlock.
   VPBasicBlock *Parent = nullptr;
 
 public:
-  VPRecipeBase(const unsigned char SC, Value *V = nullptr) : VPValue(SC, V) {}
+  VPRecipeBase(const unsigned char SC, ArrayRef<VPValue *> Operands,
+               Value *V = nullptr)
+      : VPUser(SC, Operands, V) {}
+
+  template <typename IterT>
+  VPRecipeBase(const unsigned char SC, iterator_range<IterT> Operands,
+               Value *V = nullptr)
+      : VPUser(SC, Operands, V) {}
   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:
   /// This method unlinks 'this' from the containing basic block, but does not
   /// delete it.
   void removeFromParent();
 
   /// This method unlinks 'this' from the containing basic block and deletes it.
   ///
   /// \returns an iterator pointing to the element after the erased one
   iplist<VPRecipeBase>::iterator eraseFromParent();
-
-  /// Returns a pointer to a VPUser, if the recipe inherits from VPUser or
-  /// nullptr otherwise.
-  VPUser *toVPUser();
-
-  /// Returns a pointer to a VPValue, if the recipe inherits from VPValue or
-  /// nullptr otherwise.
-  VPValue *toVPValue();
-};
-
-inline bool VPUser::classof(const VPRecipeBase *Recipe) {
-  return Recipe->getVPValueID() == VPRecipeBase::VPInstructionSC ||
-         Recipe->getVPValueID() == VPRecipeBase::VPWidenSC ||
-         Recipe->getVPValueID() == VPRecipeBase::VPWidenCallSC ||
-         Recipe->getVPValueID() == VPRecipeBase::VPWidenSelectSC ||
-         Recipe->getVPValueID() == VPRecipeBase::VPWidenGEPSC ||
-         Recipe->getVPValueID() == VPRecipeBase::VPBlendSC ||
-         Recipe->getVPValueID() == VPRecipeBase::VPInterleaveSC ||
-         Recipe->getVPValueID() == VPRecipeBase::VPReplicateSC ||
-         Recipe->getVPValueID() == VPRecipeBase::VPBranchOnMaskSC ||
-         Recipe->getVPValueID() == VPRecipeBase::VPWidenMemoryInstructionSC;
-}
+};
 
 /// This is a concrete Recipe that models a single VPlan-level instruction.
 /// While as any Recipe it may generate a sequence of IR instructions when
 /// executed, these instructions would always form a single-def expression as
 /// the VPInstruction is also a single def-use vertex.
-class VPInstruction : public VPUser, public VPRecipeBase {
+class VPInstruction : public VPRecipeBase {
   friend class VPlanSlp;
 
 public:
   /// VPlan opcodes, extending LLVM IR with idiomatics instructions.
   enum {
     Not = Instruction::OtherOpsEnd + 1,
     ICmpULE,
     SLPLoad,
protected:
   Instruction *getUnderlyingInstr() {
     return cast_or_null<Instruction>(getUnderlyingValue());
   }
 
   void setUnderlyingInstr(Instruction *I) { setUnderlyingValue(I); }
 
 public:
   VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands)
-      : VPUser(Operands), VPRecipeBase(VPValue::VPInstructionSC),
-        Opcode(Opcode) {}
+      : VPRecipeBase(VPValue::VPInstructionSC, Operands), Opcode(Opcode) {}
 
   VPInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands)
       : VPInstruction(Opcode, ArrayRef<VPValue *>(Operands)) {}
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPValue *V) {
     return V->getVPValueID() == VPValue::VPInstructionSC;
   }
default:
       return true;
     }
   }
 };
 
 /// VPWidenRecipe is a recipe for producing a copy of vector type its
 /// ingredient. This recipe covers most of the traditional vectorization cases
 /// where each ingredient transforms into a vectorized version of itself.
-class VPWidenRecipe : public VPRecipeBase, public VPUser {
+class VPWidenRecipe : public VPRecipeBase {
   /// Hold the instruction to be widened.
   Instruction &Ingredient;
 
 public:
   template <typename IterT>
   VPWidenRecipe(Instruction &I, iterator_range<IterT> Operands)
-      : VPRecipeBase(VPWidenSC), VPUser(Operands), Ingredient(I) {}
+      : VPRecipeBase(VPWidenSC, Operands, &I), Ingredient(I) {}
 
   ~VPWidenRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPValue *V) {
     return V->getVPValueID() == VPRecipeBase::VPWidenSC;
   }
 
   /// Produce widened copies of all Ingredients.
   void execute(VPTransformState &State) override;
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 };
 
 /// A recipe for widening Call instructions.
-class VPWidenCallRecipe : public VPRecipeBase, public VPUser {
+class VPWidenCallRecipe : public VPRecipeBase {
 
 public:
   template <typename IterT>
   VPWidenCallRecipe(CallInst &I, iterator_range<IterT> CallArguments)
-      : VPRecipeBase(VPWidenCallSC, &I), VPUser(CallArguments) {}
+      : VPRecipeBase(VPWidenCallSC, CallArguments, &I) {}
 
   ~VPWidenCallRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPValue *V) {
     return V->getVPValueID() == VPRecipeBase::VPWidenCallSC;
   }
 
   /// Produce a widened version of the call instruction.
   void execute(VPTransformState &State) override;
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 
   CallInst *getUnderlyingCall() { return cast<CallInst>(getUnderlyingValue()); }
   const CallInst *getUnderlyingCall() const {
     return cast<CallInst>(getUnderlyingValue());
   }
 };
 
 /// A recipe for widening select instructions.
-class VPWidenSelectRecipe : public VPRecipeBase, public VPUser {
+class VPWidenSelectRecipe : public VPRecipeBase {
 
   /// Is the condition of the select loop invariant?
   bool InvariantCond;
 
 public:
   template <typename IterT>
   VPWidenSelectRecipe(SelectInst &I, iterator_range<IterT> Operands,
                       bool InvariantCond)
-      : VPRecipeBase(VPValue::VPWidenSelectSC, &I), VPUser(Operands),
+      : VPRecipeBase(VPValue::VPWidenSelectSC, Operands, &I),
         InvariantCond(InvariantCond) {}
 
   ~VPWidenSelectRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPValue *V) {
     return V->getVPValueID() == VPRecipeBase::VPWidenSelectSC;
   }
 
   /// Produce a widened version of the select instruction.
   void execute(VPTransformState &State) override;
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 
   SelectInst *getUnderlyingInstruction() {
     return cast<SelectInst>(getUnderlyingValue());
   }
 };
 
 /// A recipe for handling GEP instructions.
-class VPWidenGEPRecipe : public VPRecipeBase, public VPUser {
+class VPWidenGEPRecipe : public VPRecipeBase {
   GetElementPtrInst *GEP;
 
   bool IsPtrLoopInvariant;
   SmallBitVector IsIndexLoopInvariant;
 
 public:
   template <typename IterT>
   VPWidenGEPRecipe(GetElementPtrInst *GEP, iterator_range<IterT> Operands)
-      : VPRecipeBase(VPWidenGEPSC), VPUser(Operands), GEP(GEP),
+      : VPRecipeBase(VPWidenGEPSC, Operands, GEP), GEP(GEP),
         IsIndexLoopInvariant(GEP->getNumIndices(), false) {}
 
   template <typename IterT>
   VPWidenGEPRecipe(GetElementPtrInst *GEP, iterator_range<IterT> Operands,
                    Loop *OrigLoop)
-      : VPRecipeBase(VPValue::VPWidenGEPSC, GEP), VPUser(Operands),
+      : VPRecipeBase(VPValue::VPWidenGEPSC, Operands, GEP),
         IsIndexLoopInvariant(GEP->getNumIndices(), false) {
     IsPtrLoopInvariant = OrigLoop->isLoopInvariant(GEP->getPointerOperand());
     for (auto Index : enumerate(GEP->indices()))
       IsIndexLoopInvariant[Index.index()] =
           OrigLoop->isLoopInvariant(Index.value().get());
   }
   ~VPWidenGEPRecipe() override = default;
 

 /// A recipe for handling phi nodes of integer and floating-point inductions,
 /// producing their vector and scalar values.
 class VPWidenIntOrFpInductionRecipe : public VPRecipeBase {
   PHINode *IV;
   TruncInst *Trunc;
 
 public:
   VPWidenIntOrFpInductionRecipe(PHINode *IV, TruncInst *Trunc = nullptr)
-      : VPRecipeBase(VPWidenIntOrFpInductionSC), IV(IV), Trunc(Trunc) {}
+      : VPRecipeBase(VPWidenIntOrFpInductionSC, {}, IV), IV(IV), Trunc(Trunc) {}
   ~VPWidenIntOrFpInductionRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPValue *V) {
     return V->getVPValueID() == VPRecipeBase::VPWidenIntOrFpInductionSC;
   }
 
   /// Generate the vectorized and scalarized versions of the phi node as
   /// needed by their users.
   void execute(VPTransformState &State) override;
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 };
 
 /// A recipe for handling all phi nodes except for integer and FP inductions.
 class VPWidenPHIRecipe : public VPRecipeBase {
   PHINode *Phi;
 
 public:
-  VPWidenPHIRecipe(PHINode *Phi) : VPRecipeBase(VPWidenPHISC), Phi(Phi) {}
+  VPWidenPHIRecipe(PHINode *Phi)
+      : VPRecipeBase(VPWidenPHISC, {}, Phi), Phi(Phi) {}
   ~VPWidenPHIRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPValue *V) {
     return V->getVPValueID() == VPRecipeBase::VPWidenPHISC;
   }
 
   /// Generate the phi/select nodes.
   void execute(VPTransformState &State) override;
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 };
 
 /// A recipe for vectorizing a phi-node as a sequence of mask-based select
 /// instructions.
-class VPBlendRecipe : public VPRecipeBase, public VPUser {
+class VPBlendRecipe : public VPRecipeBase {
   PHINode *Phi;
 
 public:
   /// The blend operation is a User of the incoming values and of their
   /// respective masks, ordered [I0, M0, I1, M1, ...]. Note that a single value
   /// might be incoming with a full mask for which there is no VPValue.
   VPBlendRecipe(PHINode *Phi, ArrayRef<VPValue *> Operands)
-      : VPRecipeBase(VPBlendSC), VPUser(Operands), Phi(Phi) {
+      : VPRecipeBase(VPBlendSC, Operands, Phi), Phi(Phi) {
     assert(Operands.size() > 0 &&
            ((Operands.size() == 1) || (Operands.size() % 2 == 0)) &&
            "Expected either a single incoming value or a positive even number "
            "of operands");
   }
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPValue *V) {
public:
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 };
 
 /// VPInterleaveRecipe is a recipe for transforming an interleave group of load
 /// or stores into one wide load/store and shuffles.
-class VPInterleaveRecipe : public VPRecipeBase, public VPUser {
+class VPInterleaveRecipe : public VPRecipeBase {
   const InterleaveGroup<Instruction> *IG;
 
 public:
   SmallVector<VPValue *, 4> Defs;
 
   VPInterleaveRecipe(const InterleaveGroup<Instruction> *IG, VPValue *Addr,
                      VPValue *Mask)
-      : VPRecipeBase(VPValue::VPInterleaveSC), VPUser({Addr}), IG(IG) {
+      : VPRecipeBase(VPValue::VPInterleaveSC, {Addr}), IG(IG) {
     if (Mask)
       addOperand(Mask);
     for (unsigned i = 0; i < IG->getNumMembers(); i++)
       Defs.push_back(new VPValue(this));
   }
   ~VPInterleaveRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
class VPReductionRecipe : public VPRecipeBase {
   /// Fast math flags to use for the resulting reduction operation.
   bool NoNaN;
   /// Pointer to the TTI, needed to create the target reduction
   const TargetTransformInfo *TTI;
 
 public:
   VPReductionRecipe(RecurrenceDescriptor *R, Instruction *I, VPValue *ChainOp,
                     VPValue *VecOp, bool NoNaN, const TargetTransformInfo *TTI)
-      : VPRecipeBase(VPReductionSC), RdxDesc(R), I(I), VecOp(VecOp),
+      : VPRecipeBase(VPReductionSC, {}, I), RdxDesc(R), I(I), VecOp(VecOp),
         ChainOp(ChainOp), NoNaN(NoNaN), TTI(TTI) {}
 
   ~VPReductionRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPValue *V) {
     return V->getVPValueID() == VPRecipeBase::VPReductionSC;
   }
 
   /// Generate the reduction in the loop
   void execute(VPTransformState &State) override;
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 };
 
 /// VPReplicateRecipe replicates a given instruction producing multiple scalar
 /// copies of the original scalar type, one per lane, instead of producing a
 /// single copy of widened type for all lanes. If the instruction is known to be
 /// uniform only one copy, per lane zero, will be generated.
-class VPReplicateRecipe : public VPRecipeBase, public VPUser {
+class VPReplicateRecipe : public VPRecipeBase {
   /// The instruction being replicated.
   Instruction *Ingredient;
 
   /// Indicator if only a single replica per lane is needed.
   bool IsUniform;
 
   /// Indicator if the replicas are also predicated.
   bool IsPredicated;
 
   /// Indicator if the scalar values should also be packed into a vector.
   bool AlsoPack;
 
 public:
   template <typename IterT>
   VPReplicateRecipe(Instruction *I, iterator_range<IterT> Operands,
                     bool IsUniform, bool IsPredicated = false)
-      : VPRecipeBase(VPReplicateSC), VPUser(Operands), Ingredient(I),
+      : VPRecipeBase(VPReplicateSC, Operands, I), Ingredient(I),
         IsUniform(IsUniform), IsPredicated(IsPredicated) {
     // Retain the previous behavior of predicateInstructions(), where an
     // insert-element of a predicated instruction got hoisted into the
     // predicated basic block iff it was its only user. This is achieved by
     // having predicated instructions also pack their values into a vector by
     // default unless they have a replicated user which uses their scalar value.
     AlsoPack = IsPredicated && !I->use_empty();
   }
public:
   void setAlsoPack(bool Pack) { AlsoPack = Pack; }
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 };
 
 /// A recipe for generating conditional branches on the bits of a mask.
-class VPBranchOnMaskRecipe : public VPRecipeBase, public VPUser {
+class VPBranchOnMaskRecipe : public VPRecipeBase {
 public:
-  VPBranchOnMaskRecipe(VPValue *BlockInMask) : VPRecipeBase(VPBranchOnMaskSC) {
+  VPBranchOnMaskRecipe(VPValue *BlockInMask)
+      : VPRecipeBase(VPBranchOnMaskSC, {}) {
     if (BlockInMask) // nullptr means all-one mask.
       addOperand(BlockInMask);
   }
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPValue *V) {
     return V->getVPValueID() == VPRecipeBase::VPBranchOnMaskSC;
   }

 /// This recipe works in concert with VPBranchOnMaskRecipe.
 class VPPredInstPHIRecipe : public VPRecipeBase {
   Instruction *PredInst;
 
 public:
   /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi
   /// nodes after merging back from a Branch-on-Mask.
   VPPredInstPHIRecipe(Instruction *PredInst)
-      : VPRecipeBase(VPPredInstPHISC), PredInst(PredInst) {}
+      : VPRecipeBase(VPPredInstPHISC, {}, PredInst), PredInst(PredInst) {}
   ~VPPredInstPHIRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPValue *V) {
     return V->getVPValueID() == VPRecipeBase::VPPredInstPHISC;
   }
 
   /// Generates phi nodes for live-outs as needed to retain SSA form.
   void execute(VPTransformState &State) override;
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 };
 
 /// A Recipe for widening load/store operations.
 /// The recipe uses the following VPValues:
 /// - For load: Address, optional mask
 /// - For store: Address, stored value, optional mask
 /// TODO: We currently execute only per-part unless a specific instance is
 /// provided.
-class VPWidenMemoryInstructionRecipe : public VPRecipeBase, public VPUser {
+class VPWidenMemoryInstructionRecipe : public VPRecipeBase {
 
   void setMask(VPValue *Mask) {
     if (!Mask)
       return;
     addOperand(Mask);
   }
 
   bool isMasked() const {
     return (isa<LoadInst>(getUnderlyingInstr()) && getNumOperands() == 2) ||
            (isa<StoreInst>(getUnderlyingInstr()) && getNumOperands() == 3);
   }
 
 public:
   VPWidenMemoryInstructionRecipe(LoadInst &Load, VPValue *Addr, VPValue *Mask)
-      : VPRecipeBase(VPWidenMemoryInstructionSC, &Load), VPUser({Addr}) {
+      : VPRecipeBase(VPWidenMemoryInstructionSC, Addr, &Load) {
     setMask(Mask);
   }
 
   VPWidenMemoryInstructionRecipe(StoreInst &Store, VPValue *Addr,
                                  VPValue *StoredValue, VPValue *Mask)
-      : VPRecipeBase(VPWidenMemoryInstructionSC, &Store),
-        VPUser({Addr, StoredValue}) {
+      : VPRecipeBase(VPWidenMemoryInstructionSC, {Addr, StoredValue}, &Store) {
     setMask(Mask);
   }
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPValue *V) {
     return V->getVPValueID() == VPRecipeBase::VPWidenMemoryInstructionSC;
   }
 

 };
 
 /// A Recipe for widening the canonical induction variable of the vector loop.
 class VPWidenCanonicalIVRecipe : public VPRecipeBase {
   /// A VPValue representing the canonical vector IV.
   VPValue Val;
 
 public:
-  VPWidenCanonicalIVRecipe() : VPRecipeBase(VPWidenCanonicalIVSC) {}
+  VPWidenCanonicalIVRecipe() : VPRecipeBase(VPWidenCanonicalIVSC, {}) {}
   ~VPWidenCanonicalIVRecipe() override = default;
 
   /// Return the VPValue representing the canonical vector induction variable of
   /// the vector loop.
   const VPValue *getVPValue() const { return &Val; }
   VPValue *getVPValue() { return &Val; }
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.

llvm/lib/Transforms/Vectorize/VPlan.cpp

 }
 
 void VPRecipeBase::dump() const {
   VPSlotTracker SlotTracker(nullptr);
   print(dbgs(), "", SlotTracker);
   dbgs() << "\n";
 }
 
-VPUser *VPRecipeBase::toVPUser() {
-  if (auto *U = dyn_cast<VPInstruction>(this))
-    return U;
-  if (auto *U = dyn_cast<VPWidenRecipe>(this))
-    return U;
-  if (auto *U = dyn_cast<VPWidenCallRecipe>(this))
-    return U;
-  if (auto *U = dyn_cast<VPWidenSelectRecipe>(this))
-    return U;
-  if (auto *U = dyn_cast<VPWidenGEPRecipe>(this))
-    return U;
-  if (auto *U = dyn_cast<VPBlendRecipe>(this))
-    return U;
-  if (auto *U = dyn_cast<VPInterleaveRecipe>(this))
-    return U;
-  if (auto *U = dyn_cast<VPReplicateRecipe>(this))
-    return U;
-  if (auto *U = dyn_cast<VPBranchOnMaskRecipe>(this))
-    return U;
-  if (auto *U = dyn_cast<VPWidenMemoryInstructionRecipe>(this))
-    return U;
-  return nullptr;
-}
-
-VPValue *VPRecipeBase::toVPValue() {
-  if (auto *Widen = dyn_cast<VPInstruction>(this))
-    return Widen;
-  if (auto *Widen = dyn_cast<VPWidenMemoryInstructionRecipe>(this))
-    return Widen;
-  if (auto *V = dyn_cast<VPWidenCallRecipe>(this))
-    return V;
-  if (auto *V = dyn_cast<VPWidenSelectRecipe>(this))
-    return V;
-  if (auto *V = dyn_cast<VPWidenGEPRecipe>(this))
-    return V;
-  return nullptr;
-}
 // Get the top-most entry block of \p Start. This is the entry block of the
 // containing VPlan. This function is templated to support both const and non-const blocks
 template <typename T> static T *getPlanEntry(T *Start) {
   T *Next = Start;
   T *Current = Start;
   while ((Next = Next->getParent()))
     Current = Next;
 
if (EnableVPlanNativePath && (CBV = getCondBit())) {
     ReplaceInstWithInst(CurrentTerminator, CondBr);
   }
 
   LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB);
 }
 
 void VPBasicBlock::dropAllReferences(VPValue *NewValue) {
   for (VPRecipeBase &R : Recipes) {
-    if (auto *VPV = R.toVPValue())
-      VPV->replaceAllUsesWith(NewValue);
-
-    if (auto *User = R.toVPUser())
-      for (unsigned I = 0, E = User->getNumOperands(); I != E; I++)
-        User->setOperand(I, NewValue);
+    R.replaceAllUsesWith(NewValue);
+    for (unsigned I = 0, E = R.getNumOperands(); I != E; I++)
+      R.setOperand(I, NewValue);
   }
 }
 
 void VPRegionBlock::execute(VPTransformState *State) {
   ReversePostOrderTraversal<VPBlockBase *> RPOT(Entry);
 
   if (!isReplicator()) {
     // Visit the VPBlocks connected to "this", starting from it.
void VPRecipeBase::removeFromParent() {
   getParent()->getRecipeList().remove(getIterator());
   Parent = nullptr;
 }
 
 iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() {
   assert(getParent() && "Recipe not in any VPBasicBlock");
   // If the recipe is a VPValue and has been added to the containing VPlan,
   // remove the mapping.
-  if (VPValue *VPV = toVPValue())
-    if (Value *UV = VPV->getUnderlyingValue())
-      if (!UV->getType()->isVoidTy())
-        if (auto *Plan = getParent()->getPlan())
-          Plan->removeVPValueFor(UV);
+  if (Value *UV = getUnderlyingValue())
 
   return getParent()->getRecipeList().erase(getIterator());
 }
 
 void VPRecipeBase::moveAfter(VPRecipeBase *InsertPos) {
   removeFromParent();
   insertAfter(InsertPos);
 }

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

for (auto I = VPBB->begin(), E = VPBB->end(); I != E;) {
         } else
           NewRecipe = new VPWidenPHIRecipe(Phi);
       } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
         NewRecipe = new VPWidenGEPRecipe(
             GEP, Plan->mapToVPValues(GEP->operands()), OrigLoop);
       } else
         NewRecipe =
             new VPWidenRecipe(*Inst, Plan->mapToVPValues(Inst->operands()));
-
+      Plan->addVPValue(Inst, NewRecipe);
       NewRecipe->insertBefore(Ingredient);
       VPInst->replaceAllUsesWith(&DummyValue);
       Ingredient->eraseFromParent();
     }
   }
 }

llvm/lib/Transforms/Vectorize/VPlanValue.h

 
 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 {
+class VPUser : public VPValue {
   SmallVector<VPValue *, 2> Operands;
 
 public:
   VPUser() {}
-  VPUser(ArrayRef<VPValue *> Operands) {
+  VPUser(const unsigned char SC, ArrayRef<VPValue *> Operands,
+         Value *V = nullptr)
+      : VPValue(SC, V) {
     for (VPValue *Operand : Operands) {
       assert(!Operand->isVirtual() &&
              "cannot use a virtual VPValue as operand");
       addOperand(Operand);
     }
   }
 
-  VPUser(std::initializer_list<VPValue *> Operands)
-      : VPUser(ArrayRef<VPValue *>(Operands)) {}
-  template <typename IterT> VPUser(iterator_range<IterT> Operands) {
+  VPUser(const unsigned char SC, std::initializer_list<VPValue *> Operands,
+         Value *V = nullptr)
+      : VPUser(SC, ArrayRef<VPValue *>(Operands), V) {}
+  template <typename IterT>
+  VPUser(const unsigned char SC, iterator_range<IterT> Operands,
+         Value *V = nullptr)
+      : VPValue(SC, V) {
     for (VPValue *Operand : Operands) {
       assert(!Operand->isVirtual() &&
              "cannot use a virtual VPValue as operand");
+
       addOperand(Operand);
     }
   }
 
   VPUser(const VPUser &) = delete;
   VPUser &operator=(const VPUser &) = delete;
   virtual ~VPUser() {
     for (VPValue *Op : operands())
public:
   operand_iterator op_begin() { return Operands.begin(); }
   const_operand_iterator op_begin() const { return Operands.begin(); }
   operand_iterator op_end() { return Operands.end(); }
   const_operand_iterator op_end() const { return Operands.end(); }
   operand_range operands() { return operand_range(op_begin(), op_end()); }
   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 VPRecipeBase *Recipe);
 };
 class VPlan;
 class VPBasicBlock;
 class VPRegionBlock;
 
 /// 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.

llvm/unittests/Transforms/Vectorize/VPlanHCFGTest.cpp

TEST_F(VPlanHCFGTest, testVPInstructionToVPRecipesInner) {
   EXPECT_NE(nullptr, dyn_cast<VPWidenMemoryInstructionRecipe>(&*Iter++));
   EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));
   EXPECT_NE(nullptr, dyn_cast<VPWidenMemoryInstructionRecipe>(&*Iter++));
   EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));
   EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));
   EXPECT_EQ(VecBB->end(), Iter);
 }
 
+TEST_F(VPlanHCFGTest, testDefUseTraversal) {
+  const char *ModuleString =
+      "define void @f(i32* %A, i64 %N) {\n"
+      "entry:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]\n"
+      "  %arr.idx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv\n"
+      "  %l1 = load i32, i32* %arr.idx, align 4\n"
+      "  %res = add i32 %l1, 10\n"
+      "  store i32 %res, i32* %arr.idx, align 4\n"
+      "  %indvars.iv.next = add i64 %indvars.iv, 1\n"
+      "  %exitcond = icmp ne i64 %indvars.iv.next, %N\n"
+      "  br i1 %exitcond, label %for.body, label %for.end\n"
+      "for.end:\n"
+      "  ret void\n"
+      "}\n";
+
+  Module &M = parseModule(ModuleString);
+
+  Function *F = M.getFunction("f");
+  BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
+  auto Plan = buildHCFG(LoopHeader);
+
+  LoopVectorizationLegality::InductionList Inductions;
+  SmallPtrSet<Instruction *, 1> DeadInstructions;
+  VPlanTransforms::VPInstructionsToVPRecipes(LI->getLoopFor(LoopHeader), Plan,
+                                             Inductions, DeadInstructions);
+
+  VPBlockBase *Entry = Plan->getEntry()->getEntryBasicBlock();
+  EXPECT_NE(nullptr, Entry->getSingleSuccessor());
+  EXPECT_EQ(0u, Entry->getNumPredecessors());
+  EXPECT_EQ(1u, Entry->getNumSuccessors());
+
+  VPBasicBlock *VecBB = Entry->getSingleSuccessor()->getEntryBasicBlock();
+  EXPECT_EQ(7u, VecBB->size());
+  EXPECT_EQ(2u, VecBB->getNumPredecessors());
+  EXPECT_EQ(2u, VecBB->getNumSuccessors());
+
+  auto Iter = VecBB->begin();
+  VPRecipeBase *PHI = &*Iter++;
+  EXPECT_TRUE(isa<VPUser>(PHI));
+  EXPECT_TRUE(isa<VPValue>(PHI));
+  VPUser *PHIAsUser = PHI;
+  EXPECT_TRUE(isa<VPWidenPHIRecipe>(PHIAsUser));
+  EXPECT_FALSE(isa<VPWidenRecipe>(PHIAsUser));
+
+  VPRecipeBase *GEP = &*Iter++;
+  EXPECT_TRUE(isa<VPUser>(GEP));
+  EXPECT_TRUE(isa<VPValue>(GEP));
+  VPUser *GEPAsUser = GEP;
+  EXPECT_TRUE(isa<VPWidenGEPRecipe>(GEPAsUser));
+  EXPECT_FALSE(isa<VPWidenRecipe>(GEPAsUser));
+
+  // Check operands upwards.
+  EXPECT_EQ(2u, GEP->getNumOperands());
+  EXPECT_EQ(PHI, GEP->getOperand(1));
+  EXPECT_TRUE(isa<VPWidenPHIRecipe>(GEP->getOperand(1)));
+
+  // Check users downward.
+  SmallVector<VPUser *, 2> GEPUsers(GEP->user_begin(), GEP->user_end());
+  EXPECT_EQ(2u, GEPUsers.size());
+  EXPECT_TRUE(isa<VPWidenMemoryInstructionRecipe>(GEPUsers[0]));
+  EXPECT_TRUE(isa<VPWidenMemoryInstructionRecipe>(GEPUsers[1]));
+
+  // TODO: add missing.
+  /*  EXPECT_NE(nullptr, dyn_cast<VPWidenMemoryInstructionRecipe>(&*Iter++));*/
+  // EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));
+  // EXPECT_NE(nullptr, dyn_cast<VPWidenMemoryInstructionRecipe>(&*Iter++));
+  // EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));
+  // EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));
+  /*EXPECT_EQ(VecBB->end(), Iter);*/
+}
+
 } // namespace
 } // namespace llvm

llvm/unittests/Transforms/Vectorize/VPlanTest.cpp

 
 TEST(VPRecipeTest, CastVPInstructionToVPUser) {
   VPValue Op1;
   VPValue Op2;
   VPInstruction Recipe(Instruction::Add, {&Op1, &Op2});
   EXPECT_TRUE(isa<VPUser>(&Recipe));
   VPRecipeBase *BaseR = &Recipe;
   EXPECT_TRUE(isa<VPUser>(BaseR));
-  EXPECT_EQ(&Recipe, BaseR->toVPUser());
 }
 
 TEST(VPRecipeTest, CastVPWidenRecipeToVPUser) {
   LLVMContext C;
 
   IntegerType *Int32 = IntegerType::get(C, 32);
   auto *AI =
       BinaryOperator::CreateAdd(UndefValue::get(Int32), UndefValue::get(Int32));
   VPValue Op1;
   VPValue Op2;
   SmallVector<VPValue *, 2> Args;
   Args.push_back(&Op1);
   Args.push_back(&Op1);
   VPWidenRecipe WidenR(*AI, make_range(Args.begin(), Args.end()));
   EXPECT_TRUE(isa<VPUser>(&WidenR));
   VPRecipeBase *WidenRBase = &WidenR;
   EXPECT_TRUE(isa<VPUser>(WidenRBase));
-  EXPECT_EQ(&WidenR, WidenRBase->toVPUser());
   delete AI;
 }
 
 TEST(VPRecipeTest, CastVPWidenCallRecipeToVPUser) {
   LLVMContext C;
 
   IntegerType *Int32 = IntegerType::get(C, 32);
   FunctionType *FTy = FunctionType::get(Int32, false);
   auto *Call = CallInst::Create(FTy, UndefValue::get(FTy));
   VPValue Op1;
   VPValue Op2;
   SmallVector<VPValue *, 2> Args;
   Args.push_back(&Op1);
   Args.push_back(&Op2);
   VPWidenCallRecipe Recipe(*Call, make_range(Args.begin(), Args.end()));
   EXPECT_TRUE(isa<VPUser>(&Recipe));
   VPRecipeBase *BaseR = &Recipe;
   EXPECT_TRUE(isa<VPUser>(BaseR));
-  EXPECT_EQ(&Recipe, BaseR->toVPUser());
   delete Call;
 }
 
 TEST(VPRecipeTest, CastVPWidenSelectRecipeToVPUser) {
   LLVMContext C;
 
   IntegerType *Int1 = IntegerType::get(C, 1);
   IntegerType *Int32 = IntegerType::get(C, 32);
   auto *SelectI = SelectInst::Create(
       UndefValue::get(Int1), UndefValue::get(Int32), UndefValue::get(Int32));
   VPValue Op1;
   VPValue Op2;
   VPValue Op3;
   SmallVector<VPValue *, 4> Args;
   Args.push_back(&Op1);
   Args.push_back(&Op2);
   Args.push_back(&Op3);
   VPWidenSelectRecipe WidenSelectR(*SelectI,
                                    make_range(Args.begin(), Args.end()), false);
   EXPECT_TRUE(isa<VPUser>(&WidenSelectR));
   VPRecipeBase *BaseR = &WidenSelectR;
   EXPECT_TRUE(isa<VPUser>(BaseR));
-  EXPECT_EQ(&WidenSelectR, BaseR->toVPUser());
   delete SelectI;
 }
 
 TEST(VPRecipeTest, CastVPWidenGEPRecipeToVPUser) {
   LLVMContext C;
 
   IntegerType *Int32 = IntegerType::get(C, 32);
   PointerType *Int32Ptr = PointerType::get(Int32, 0);
   auto *GEP = GetElementPtrInst::Create(Int32, UndefValue::get(Int32Ptr),
                                         UndefValue::get(Int32));
   VPValue Op1;
   VPValue Op2;
   SmallVector<VPValue *, 4> Args;
   Args.push_back(&Op1);
   Args.push_back(&Op2);
   VPWidenGEPRecipe Recipe(GEP, make_range(Args.begin(), Args.end()));
   EXPECT_TRUE(isa<VPUser>(&Recipe));
   VPRecipeBase *BaseR = &Recipe;
   EXPECT_TRUE(isa<VPUser>(BaseR));
-  EXPECT_EQ(&Recipe, BaseR->toVPUser());
   delete GEP;
 }
 
 TEST(VPRecipeTest, CastVPBlendRecipeToVPUser) {
   LLVMContext C;
 
   IntegerType *Int32 = IntegerType::get(C, 32);
   auto *Phi = PHINode::Create(Int32, 1);
   VPValue Op1;
   VPValue Op2;
   SmallVector<VPValue *, 4> Args;
   Args.push_back(&Op1);
   Args.push_back(&Op2);
   VPBlendRecipe Recipe(Phi, Args);
   EXPECT_TRUE(isa<VPUser>(&Recipe));
   VPRecipeBase *BaseR = &Recipe;
   EXPECT_TRUE(isa<VPUser>(BaseR));
   delete Phi;
 }
 
 TEST(VPRecipeTest, CastVPInterleaveRecipeToVPUser) {
-  LLVMContext C;
+  /*  LLVMContext C;*/
 
-  VPValue Addr;
-  VPValue Mask;
-  VPInterleaveRecipe Recipe(nullptr, &Addr, &Mask);
-  EXPECT_TRUE(isa<VPUser>(&Recipe));
-  VPRecipeBase *BaseR = &Recipe;
-  EXPECT_TRUE(isa<VPUser>(BaseR));
-  EXPECT_EQ(&Recipe, BaseR->toVPUser());
+  // VPValue Addr;
+  // VPValue Mask;
+  // VPInterleaveRecipe Recipe(nullptr, &Addr, &Mask);
+  // EXPECT_TRUE(isa<VPUser>(&Recipe));
+  // VPRecipeBase *BaseR = &Recipe;
+  /*EXPECT_TRUE(isa<VPUser>(BaseR));*/
 }
 
 TEST(VPRecipeTest, CastVPReplicateRecipeToVPUser) {
   LLVMContext C;
 
   VPValue Op1;
   VPValue Op2;
   SmallVector<VPValue *, 4> Args;

 TEST(VPRecipeTest, CastVPBranchOnMaskRecipeToVPUser) {
   LLVMContext C;
 
   VPValue Mask;
   VPBranchOnMaskRecipe Recipe(&Mask);
   EXPECT_TRUE(isa<VPUser>(&Recipe));
   VPRecipeBase *BaseR = &Recipe;
   EXPECT_TRUE(isa<VPUser>(BaseR));
-  EXPECT_EQ(&Recipe, BaseR->toVPUser());
 }
 
 TEST(VPRecipeTest, CastVPWidenMemoryInstructionRecipeToVPUser) {
   LLVMContext C;
 
   IntegerType *Int32 = IntegerType::get(C, 32);
   PointerType *Int32Ptr = PointerType::get(Int32, 0);
   auto *Load =
       new LoadInst(Int32, UndefValue::get(Int32Ptr), "", false, Align(1));
   VPValue Addr;
   VPValue Mask;
   VPWidenMemoryInstructionRecipe Recipe(*Load, &Addr, &Mask);
   EXPECT_TRUE(isa<VPUser>(&Recipe));
   VPRecipeBase *BaseR = &Recipe;
   EXPECT_TRUE(isa<VPUser>(BaseR));
-  EXPECT_EQ(&Recipe, BaseR->toVPUser());
   delete Load;
 }
 
-struct VPTestMultiValueDef : public VPUser, public VPValue {
+struct VPTestMultiValueDef : public VPUser {
   SmallVector<VPValue *, 4> Defs;
 
-  VPTestMultiValueDef() : VPValue(VPValue::VPVirtualValueSC) {}
+  VPTestMultiValueDef() : VPUser(VPValue::VPVirtualValueSC, {}) {}
 };
 
 TEST(VPMultiValueTest, traverseUseLists) {
   // Check that the def-use chains of a multi-def can be traversed in both
   // directions.
 
   // Create a multi-value def which defines 2 values.
   VPTestMultiValueDef MultiDef;