[VPlan] Turn VPReplicateRecipe into a VPValue.

[fhahn]

Summary

Update VPReplicateRecipe to inherit from VPValue. This still does not
update scalarizeInstruction to set the result for the VPValue of
VPReplicateRecipe, because this first requires tracking scalar values in
VPTransformState.

[reames]

I don't have sufficiently broad context, but to an uneducated eye, it looks really weird to have a class which can produce multiple independent instructions declared as subclass of a class named Value. Particularly since I don't think there was a required build vector step at the end of the instructions emitted?

[reames]

Had a long conversation w/Florian today; he was nice enough to give a lot of context and general direction which helped me understand where this is going. It also helps that e0c479cd, and 00a6601 landed recently showing alignment with the direction sketched here.

Given that, LGTM

llvm/lib/Transforms/Vectorize/VPlan.cpp

140

Out of scope for this patch, but these three really look like evidence of missing isa infrastructure for the types in question.

[fhahn]

rebased.

In D91500#2417433, @reames wrote:

Had a long conversation w/Florian today; he was nice enough to give a lot of context and general direction which helped me understand where this is going. It also helps that e0c479cd, and 00a6601 landed recently showing alignment with the direction sketched here.

Given that, LGTM

Thanks for taking a look!

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.cpp

140

Agreed. Currently the problem is that VPRecipeBase does not inherit from VPValue or VPUser. The toVPValue helpers are there to avoid casting between a base class and a different type that's not a subtype. Both of those helpers are only used during the transition (until all recipes have been updated) and should go away soon.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

for (unsigned op = 0, e = User.getNumOperands(); op != e; ++op) {
     auto *NewOp = State.get(User.getOperand(op), InputInstance);
     Cloned->setOperand(op, NewOp);
   }
   addNewMetadata(Cloned, Instr);
 
   // Place the cloned scalar in the new loop.
   Builder.Insert(Cloned);
 
-  // Add the cloned scalar to the scalar map entry.
+  // TODO: Set result for VPValue of VPReciplicateRecipe. This requires
+  // representing scalar values in VPTransformState. Add the cloned scalar to
+  // the scalar map entry.
   VectorLoopValueMap.setScalarValue(Instr, Instance, Cloned);
 
   // If we just cloned a new assumption, add it the assumption cache.
   if (auto *II = dyn_cast<IntrinsicInst>(Cloned))
     if (II->getIntrinsicID() == Intrinsic::assume)
       AC->registerAssumption(II);
 
   // End if-block.
VPBasicBlock *VPRecipeBuilder::handleReplication(
 
   bool IsPredicated = LoopVectorizationPlanner::getDecisionAndClampRange(
       [&](ElementCount VF) { return CM.isScalarWithPredication(I, VF); },
       Range);
 
   auto *Recipe = new VPReplicateRecipe(I, Plan->mapToVPValues(I->operands()),
                                        IsUniform, IsPredicated);
   setRecipe(I, Recipe);
+  Plan->addVPValue(I, Recipe);
 
   // Find if I uses a predicated instruction. If so, it will use its scalar
   // value. Avoid hoisting the insert-element which packs the scalar value into
   // a vector value, as that happens iff all users use the vector value.
   for (auto &Op : I->operands())
     if (auto *PredInst = dyn_cast<Instruction>(Op))
       if (PredInst2Recipe.find(PredInst) != PredInst2Recipe.end())
         PredInst2Recipe[PredInst]->setAlsoPack(false);
if (Kind == RecurrenceDescriptor::RK_IntegerMinMax ||
           PrevInChain);
     }
     State.set(this, getUnderlyingInstr(), NextInChain, Part);
   }
 }
 
 void VPReplicateRecipe::execute(VPTransformState &State) {
   if (State.Instance) { // Generate a single instance.
-    State.ILV->scalarizeInstruction(Ingredient, *this, *State.Instance,
-                                    IsPredicated, State);
+    State.ILV->scalarizeInstruction(getUnderlyingInstr(), *this,
+                                    *State.Instance, IsPredicated, State);
     // Insert scalar instance packing it into a vector.
     if (AlsoPack && State.VF.isVector()) {
       // If we're constructing lane 0, initialize to start from undef.
       if (State.Instance->Lane == 0) {
         assert(!State.VF.isScalable() && "VF is assumed to be non scalable.");
-        Value *Undef =
-            UndefValue::get(VectorType::get(Ingredient->getType(), State.VF));
-        State.ValueMap.setVectorValue(Ingredient, State.Instance->Part, Undef);
+        Value *Undef = UndefValue::get(
+            VectorType::get(getUnderlyingValue()->getType(), State.VF));
+        State.ValueMap.setVectorValue(getUnderlyingInstr(),
+                                      State.Instance->Part, Undef);
       }
-      State.ILV->packScalarIntoVectorValue(Ingredient, *State.Instance);
+      State.ILV->packScalarIntoVectorValue(getUnderlyingInstr(),
+                                           *State.Instance);
     }
     return;
   }
 
   // Generate scalar instances for all VF lanes of all UF parts, unless the
   // instruction is uniform inwhich case generate only the first lane for each
   // of the UF parts.
   unsigned EndLane = IsUniform ? 1 : State.VF.getKnownMinValue();
   for (unsigned Part = 0; Part < State.UF; ++Part)
     for (unsigned Lane = 0; Lane < EndLane; ++Lane)
-      State.ILV->scalarizeInstruction(Ingredient, *this, {Part, Lane},
+      State.ILV->scalarizeInstruction(getUnderlyingInstr(), *this, {Part, Lane},
                                       IsPredicated, State);
 }
 
 void VPBranchOnMaskRecipe::execute(VPTransformState &State) {
   assert(State.Instance && "Branch on Mask works only on single instance.");
 
   unsigned Part = State.Instance->Part;
   unsigned Lane = State.Instance->Lane;

llvm/lib/Transforms/Vectorize/VPlan.h

public:
   }
 
   /// Return true if it is legal to hoist instructions into this block.
   bool isLegalToHoistInto() {
     // There are currently no constraints that prevent an instruction to be
     // hoisted into a VPBlockBase.
     return true;
   }
+
+  /// Replace all operands of VPUsers in the block with \p NewValue and also
+  /// replaces all uses of VPValues defined in the block with NewValue.
+  virtual void dropAllReferences(VPValue *NewValue) = 0;
 };
 
 /// VPRecipeBase is a base class modeling a sequence of one or more output IR
 /// instructions.
 class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock> {
   friend VPBasicBlock;
   friend class VPBlockUtils;
 
VPValue *getCondOp() const {
     return getNumOperands() > 2 ? getOperand(2) : nullptr;
   }
 };
 
 /// 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 {
-  /// The instruction being replicated.
-  Instruction *Ingredient;
-
+class VPReplicateRecipe : public VPRecipeBase, public VPUser, public VPValue {
   /// 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),
-        IsUniform(IsUniform), IsPredicated(IsPredicated) {
+      : VPRecipeBase(VPReplicateSC), VPUser(Operands),
+        VPValue(VPVReplicateSC, 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();
   }
 
   ~VPReplicateRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == VPRecipeBase::VPReplicateSC;
   }
 
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() == VPValue::VPVReplicateSC;
+  }
+
   /// Generate replicas of the desired Ingredient. Replicas will be generated
   /// for all parts and lanes unless a specific part and lane are specified in
   /// the \p State.
   void execute(VPTransformState &State) override;
 
   void setAlsoPack(bool Pack) { AlsoPack = Pack; }
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
+
+  bool isUniform() const { return IsUniform; }
 };
 
 /// A recipe for generating conditional branches on the bits of a mask.
 class VPBranchOnMaskRecipe : public VPRecipeBase, public VPUser {
 public:
   VPBranchOnMaskRecipe(VPValue *BlockInMask) : VPRecipeBase(VPBranchOnMaskSC) {
     if (BlockInMask) // nullptr means all-one mask.
       addOperand(BlockInMask);
public:
   /// Augment the existing recipes of a VPBasicBlock with an additional
   /// \p Recipe as the last recipe.
   void appendRecipe(VPRecipeBase *Recipe) { insert(Recipe, end()); }
 
   /// The method which generates the output IR instructions that correspond to
   /// this VPBasicBlock, thereby "executing" the VPlan.
   void execute(struct VPTransformState *State) override;
 
-  /// Replace all operands of VPUsers in the block with \p NewValue and also
-  /// replaces all uses of VPValues defined in the block with NewValue.
-  void dropAllReferences(VPValue *NewValue);
-
   /// Return the position of the first non-phi node recipe in the block.
   iterator getFirstNonPhi();
 
+  void dropAllReferences(VPValue *NewValue) override;
+
 private:
   /// Create an IR BasicBlock to hold the output instructions generated by this
   /// VPBasicBlock, and return it. Update the CFGState accordingly.
   BasicBlock *createEmptyBasicBlock(VPTransformState::CFGState &CFG);
 };
 
 /// VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks
 /// which form a Single-Entry-Single-Exit subgraph of the output IR CFG.
VPRegionBlock(VPBlockBase *Entry, VPBlockBase *Exit,
     Entry->setParent(this);
     Exit->setParent(this);
   }
   VPRegionBlock(const std::string &Name = "", bool IsReplicator = false)
       : VPBlockBase(VPRegionBlockSC, Name), Entry(nullptr), Exit(nullptr),
         IsReplicator(IsReplicator) {}
 
   ~VPRegionBlock() override {
-    if (Entry)
+    if (Entry) {
+      VPValue DummyValue;
+      Entry->dropAllReferences(&DummyValue);
       deleteCFG(Entry);
     }
+  }
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPBlockBase *V) {
     return V->getVPBlockID() == VPBlockBase::VPRegionBlockSC;
   }
 
   const VPBlockBase *getEntry() const { return Entry; }
   VPBlockBase *getEntry() { return Entry; }
public:
 
   /// An indicator whether this region is to generate multiple replicated
   /// instances of output IR corresponding to its VPBlockBases.
   bool isReplicator() const { return IsReplicator; }
 
   /// The method which generates the output IR instructions that correspond to
   /// this VPRegionBlock, thereby "executing" the VPlan.
   void execute(struct VPTransformState *State) override;
+
+  void dropAllReferences(VPValue *NewValue) override;
 };
 
 //===----------------------------------------------------------------------===//
 // GraphTraits specializations for VPlan Hierarchical Control-Flow Graphs     //
 //===----------------------------------------------------------------------===//
 
 // The following set of template specializations implement GraphTraits to treat
 // any VPBlockBase as a node in a graph of VPBlockBases. It's important to note

 
 public:
   VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {
     if (Entry)
       Entry->setPlan(this);
   }
 
   ~VPlan() {
-    if (Entry)
+    if (Entry) {
+      VPValue DummyValue;
+      for (VPBlockBase *Block : depth_first(Entry))
+        Block->dropAllReferences(&DummyValue);
+
       VPBlockBase::deleteCFG(Entry);
+    }
     for (VPValue *VPV : VPValuesToFree)
       delete VPV;
     if (BackedgeTakenCount)
       delete BackedgeTakenCount;
     for (VPValue *Def : VPExternalDefs)
       delete Def;
     for (VPValue *CBV : VPCBVs)
       delete CBV;

llvm/lib/Transforms/Vectorize/VPlan.cpp

VPValue *VPRecipeBase::toVPValue() {
   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;
   if (auto *V = dyn_cast<VPWidenRecipe>(this))
     return V;
+  if (auto *V = dyn_cast<VPReplicateRecipe>(this))
+    return V;
   return nullptr;
 }
 
 const VPValue *VPRecipeBase::toVPValue() const {
   if (auto *V = dyn_cast<VPInstruction>(this))
     return V;
   if (auto *V = dyn_cast<VPReductionRecipe>(this))
     return V;
   if (auto *V = dyn_cast<VPWidenMemoryInstructionRecipe>(this))
     return V;
   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;
   if (auto *V = dyn_cast<VPWidenRecipe>(this))
     return V;
+  if (auto *V = dyn_cast<VPReplicateRecipe>(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;
VPBlockBase *VPBlockBase::getEnclosingBlockWithPredecessors() {
   assert(Parent->getEntry() == this &&
          "Block w/o predecessors not the entry of its parent.");
   return Parent->getEnclosingBlockWithPredecessors();
 }
 
 void VPBlockBase::deleteCFG(VPBlockBase *Entry) {
   SmallVector<VPBlockBase *, 8> Blocks;
 
-  VPValue DummyValue;
-  for (VPBlockBase *Block : depth_first(Entry)) {
-    // Drop all references in VPBasicBlocks and replace all uses with
-    // DummyValue.
-    if (auto *VPBB = dyn_cast<VPBasicBlock>(Block))
-      VPBB->dropAllReferences(&DummyValue);
+  for (VPBlockBase *Block : depth_first(Entry))
     Blocks.push_back(Block);
-  }
 
   for (VPBlockBase *Block : Blocks)
     delete Block;
 }
 
 VPBasicBlock::iterator VPBasicBlock::getFirstNonPhi() {
   iterator It = begin();
   while (It != end() && (isa<VPWidenPHIRecipe>(&*It) ||
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);
   }
 }
 
+void VPRegionBlock::dropAllReferences(VPValue *NewValue) {
+  for (VPBlockBase *Block : depth_first(Entry))
+    // Drop all references in VPBasicBlocks and replace all uses with
+    // DummyValue.
+    Block->dropAllReferences(NewValue);
+}
+
 void VPRegionBlock::execute(VPTransformState *State) {
   ReversePostOrderTraversal<VPBlockBase *> RPOT(Entry);
 
   if (!isReplicator()) {
     // Visit the VPBlocks connected to "this", starting from it.
     for (VPBlockBase *Block : RPOT) {
       if (EnableVPlanNativePath) {
         // The inner loop vectorization path does not represent loop preheader
if (getCondOp()) {
     getCondOp()->printAsOperand(O, SlotTracker);
   }
   O << ")";
 }
 
 void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent,
                               VPSlotTracker &SlotTracker) const {
   O << "\"" << (IsUniform ? "CLONE " : "REPLICATE ")
-    << VPlanIngredient(Ingredient);
+    << VPlanIngredient(getUnderlyingInstr());
   if (AlsoPack)
     O << " (S->V)";
 }
 
 void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent,
                                 VPSlotTracker &SlotTracker) const {
   O << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst);
 }

llvm/lib/Transforms/Vectorize/VPlanValue.h

public:
   /// are actually instantiated. Values of this enumeration are kept in the
   /// SubclassID field of the VPValue objects. They are used for concrete
   /// type identification.
   enum {
     VPValueSC,
     VPVInstructionSC,
     VPVMemoryInstructionSC,
     VPVReductionSC,
+    VPVReplicateSC,
     VPVWidenSC,
     VPVWidenCallSC,
     VPVWidenGEPSC,
     VPVWidenSelectSC,
   };
 
   VPValue(Value *UV = nullptr, VPDef *Def = nullptr)
       : VPValue(VPValueSC, UV, Def) {}