[VPlan] Use VPValue def for VPMemoryInstructionRecipe.

[fhahn]

Summary

This patch turns VPMemoryInstructionRecipe into a VPValue and uses it
during VPlan construction and codegeneration instead of the plain IR
reference where possible.

[dmgreen]

I could not find a review for VPWidenRecipe, so I put one up in D88447, that also has some adjustment for how VPValues are registered.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

560–561

There's an extra newline here, that looks like it came from a merge conflict.

7328

It might be worth thinking about doing this after the call to RecipeBuilder.tryToCreateWidenRecipe, so that it's done for all recipes at once.

llvm/lib/Transforms/Vectorize/VPlan.h

1225–1228

Would we want to make this inherit from VPUser as well?

1640

Most variables here have a comment.

[fhahn]

Rebased & addressed comments, thanks!

In D84680#2299210, @dmgreen wrote:

I could not find a review for VPWidenRecipe, so I put one up in D88447, that also has some adjustment for how VPValues are registered.

That was indeed missing, thanks for putting up the patch.

[fhahn]

Move adding VPValue to plan up.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

560–561

That's odd, it seems like clang-format did miss this one. Should be fixed now.

7328

We should definitely do that, but I'd thought it would be best to do so once we migrated most/all recipes.

I updated the code to try to convert the recipe to a VPValue after tryToCreateWidenRecipe. Unfortunately we won't eb able to use isa/cast/dyn_cast until VPRecipeBase inherits from VPValue, because otherwise we would cast between types that are not connected through inheritance. The main advantage would be to have a single place to update after the switch.

llvm/lib/Transforms/Vectorize/VPlan.h

1225–1228

I've pushed a commit updating all classes that have a VPUser member to instead inherit from VPUser, which we should be able to do independently now that VPuser is not a VPValue (for now)

1640

I added a comment.

[dmgreen]

Thanks. This looks good to me, and I like the direction we are heading towards.

You might of course want to wait a day or two in case others disagree.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7328

The new code looks OK I think, at least in the sort term.

llvm/lib/Transforms/Vectorize/VPlan.h

1225–1228

Yeah I saw. Looks good.

[fhahn]

Thanks for taking a look! I rebased the patch and updated it with a change to replace all uses of VPWidenMemoryInstructionRecipe VPValues when replacing it with a VPInterleaveRecipe.

I'll update the follow-on patches shortly as well, they should now be finished in terms of functionality.

[fhahn]

Add getUnderlyingInstr to VPRecipeBase, using toVPValue.

[dmgreen]

llvm/lib/Transforms/Vectorize/VPlan.cpp

932–933

This looks like it will print mask twice.

llvm/lib/Transforms/Vectorize/VPlan.h

696

Hmm. I had not considered exposing getUnderlyingInstr at this level. I suppose that should work. Not all recipes with have Instructions and some of them might want different accessors returning the correct type (Phi's or GEP's etc).

The cast<Instruction> below should be dyn_cast_or_null<Instruction> if the method is expected to return nullptr.

There is a comment above getUnderlyingValue that says

// DESIGN PRINCIPLE: Access to the underlying IR must be strictly limited to
// the front-end and back-end of VPlan so that the middle-end is as
// independent as possible of the underlying IR. We grant access to the
// underlying IR using friendship. In that way, we should be able to use VPlan
// for multiple underlying IRs (Polly?) by providing a new VPlan front-end,
// back-end and analysis information for the new IR.

I'm not sure if I agree with that design principle, and wouldn't mind that comment being removed and getUnderlyingValue being exposed as public (it can make matching things like constants easier to recognise). If not then the same would apply here.

[fhahn]

Remove additional printing of the mask. Should be included when printing all operands

[fhahn]

make getUnderlyingInstr protected.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.cpp

932–933

Oh right, that's not need any more.

llvm/lib/Transforms/Vectorize/VPlan.h

696

Hmm. I had not considered exposing getUnderlyingInstr at this level. I suppose that should work. Not all recipes with have Instructions and some of them might want different accessors returning the correct type (Phi's or GEP's etc).

The cast<Instruction> below should be dyn_cast_or_null<Instruction> if the method is expected to return nullptr.

I think this should only be called from inside recipes that actually set the underlying value. I think it's fine to crash/assert otherwise. I think we can even push the responsibility to the caller to only use it for VPValues with an underlying value that is an instruction.

I'm not sure if I agree with that design principle, and wouldn't mind that comment being removed and getUnderlyingValue being exposed as public (it can make matching things like constants easier to recognise). If not then the same would apply here.

yeah, we should probably at least make those helpers protected, so they can only be used from within recipes. I think the long term goal is to de-couple the vpvalues/recipes so far from IR that we can generate IR without relying on references to the original IR.

Unfortunately, many recipes rely on some information attached to the original IR instructions (mostly for type info, but some other things too). I think it is beneficial to use VPValue's underlying value for the related IR instruction, as it allows us to get rid of the duplicated recipe-specific IR pointer and we also do not have to worry about the underlying value and other reference to diverge.

I made the functions protected, so the comment above still kind-of applies (and we were doing the same thing for VPInstruction already).

[fhahn]

use cast_or_null in getUnderlyingInstr.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.h

696

I think this should only be called from inside recipes that actually set the underlying value. I think it's fine to crash/assert otherwise. I think we can even push the responsibility to the caller to only use it for VPValues with an underlying value that is an instruction.

On second though, I think in some later patches actually make use of getUnderlyingInstr to return nullptr for non-VPValue. This should lead to slightly simpler code during the transition. Also made it cast_or_null.

[fhahn]

Rebased again. I plan to land this shortly to get things rolling.

[vitalybuka]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7821

this is a memory leak
http://lab.llvm.org:8014/#/builders/68/builds/1/steps/12/logs/stdio

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7821

Thanks! Recommitted with a fix and it seems like the staging msan bit is happy now

[fhahn]

Just realized I never closed this one with the re-commit. Recommitted a while ago as 93f6c6b79c500

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

public:
   /// the corresponding vector entry in VectorLoopValueMap is returned. If,
   /// however, the value has a scalar entry in VectorLoopValueMap, we construct
   /// a new vector value on-demand by inserting the scalar values into a vector
   /// with an insertelement sequence. If the value has been neither vectorized
   /// nor scalarized, it must be loop invariant, so we simply broadcast the
   /// value into a vector.
   Value *getOrCreateVectorValue(Value *V, unsigned Part);
 
+  void setVectorValue(Value *Scalar, unsigned Part, Value *Vector) {
+    VectorLoopValueMap.setVectorValue(Scalar, Part, Vector);
+  }
+
   /// Return a value in the new loop corresponding to \p V from the original
   /// loop at unroll and vector indices \p Instance. If the value has been
   /// vectorized but not scalarized, the necessary extractelement instruction
   /// will be generated.
   Value *getOrCreateScalarValue(Value *V, const VPIteration &Instance);
 
   /// Construct the vector value of a scalarized value \p V one lane at a time.
   void packScalarIntoVectorValue(Value *V, const VPIteration &Instance);
 
   /// Try to vectorize interleaved access group \p Group with the base address
   /// given in \p Addr, optionally masking the vector operations if \p
   /// BlockInMask is non-null. Use \p State to translate given VPValues to IR
   /// values in the vectorized loop.
   void vectorizeInterleaveGroup(const InterleaveGroup<Instruction> *Group,
                                 VPTransformState &State, VPValue *Addr,
                                 VPValue *BlockInMask = nullptr);
 
   /// Vectorize Load and Store instructions with the base address given in \p
   /// Addr, optionally masking the vector operations if \p BlockInMask is
   /// non-null. Use \p State to translate given VPValues to IR values in the
   /// vectorized loop.
   void vectorizeMemoryInstruction(Instruction *Instr, VPTransformState &State,
-                                  VPValue *Addr, VPValue *StoredValue,
-                                  VPValue *BlockInMask);
+                                  VPValue *Def, VPValue *Addr,
+                                  VPValue *StoredValue, VPValue *BlockInMask);
 
   /// Set the debug location in the builder using the debug location in
   /// the instruction.
   void setDebugLocFromInst(IRBuilder<> &B, const Value *Ptr);
 
   /// Fix the non-induction PHIs in the OrigPHIsToFix vector.
   void fixNonInductionPHIs(void);
 
for (unsigned Part = 0; Part < UF; Part++) {
     else
       NewStoreInstr =
           Builder.CreateAlignedStore(IVec, AddrParts[Part], Group->getAlign());
 
     Group->addMetadata(NewStoreInstr);
   }
 }
 
-void InnerLoopVectorizer::vectorizeMemoryInstruction(Instruction *Instr,
-                                                     VPTransformState &State,
-                                                     VPValue *Addr,
-                                                     VPValue *StoredValue,
-                                                     VPValue *BlockInMask) {
+void InnerLoopVectorizer::vectorizeMemoryInstruction(
+    Instruction *Instr, VPTransformState &State, VPValue *Def, VPValue *Addr,
+    VPValue *StoredValue, VPValue *BlockInMask) {
   // Attempt to issue a wide load.
   LoadInst *LI = dyn_cast<LoadInst>(Instr);
   StoreInst *SI = dyn_cast<StoreInst>(Instr);
 
   assert((LI || SI) && "Invalid Load/Store instruction");
   assert((!SI || StoredValue) && "No stored value provided for widened store");
   assert((!LI || !StoredValue) && "Stored value provided for widened load");
 
if (CreateGatherScatter) {
         NewLI =
             Builder.CreateAlignedLoad(DataTy, VecPtr, Alignment, "wide.load");
 
       // Add metadata to the load, but setVectorValue to the reverse shuffle.
       addMetadata(NewLI, LI);
       if (Reverse)
         NewLI = reverseVector(NewLI);
     }
-    VectorLoopValueMap.setVectorValue(Instr, Part, NewLI);
+
+    State.set(Def, Instr, NewLI, Part);
   }
 }
 
 void InnerLoopVectorizer::scalarizeInstruction(Instruction *Instr, VPUser &User,
                                                const VPIteration &Instance,
                                                bool IfPredicateInstr,
                                                VPTransformState &State) {
   assert(!Instr->getType()->isAggregateType() && "Can't handle vectors");
VPRecipeBuilder::tryToWidenMemory(Instruction *I, VFRange &Range,
   VPValue *Mask = nullptr;
   if (Legal->isMaskRequired(I))
     Mask = createBlockInMask(I->getParent(), Plan);
 
   VPValue *Addr = Plan->getOrAddVPValue(getLoadStorePointerOperand(I));
   if (LoadInst *Load = dyn_cast<LoadInst>(I))
     return new VPWidenMemoryInstructionRecipe(*Load, Addr, Mask);
 
   StoreInst *Store = cast<StoreInst>(I);
   VPValue *StoredValue = Plan->getOrAddVPValue(Store->getValueOperand());
   return new VPWidenMemoryInstructionRecipe(*Store, Addr, StoredValue, Mask);
 }
 
 VPWidenIntOrFpInductionRecipe *
 VPRecipeBuilder::tryToOptimizeInductionPHI(PHINode *Phi) const {
   // Check if this is an integer or fp induction. If so, build the recipe that
   // produces its scalar and vector values.
for (Instruction &I : BB->instructionsWithoutDebug()) {
 
       // First filter out irrelevant instructions, to ensure no recipes are
       // built for them.
       if (isa<BranchInst>(Instr) || DeadInstructions.count(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 (NeedDef.contains(Instr))
+            Plan->addOrReplaceVPValue(Instr, MaybeVPValue);
+          else
+            Plan->addVPValue(Instr, MaybeVPValue);
+        }
+
         RecipeBuilder.setRecipe(Instr, Recipe);
         VPBB->appendRecipe(Recipe);
         continue;
       }
 
       // Otherwise, if all widening options failed, Instruction is to be
       // replicated. This may create a successor for VPBB.
       VPBasicBlock *NextVPBB = RecipeBuilder.handleReplication(
VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
   for (auto IG : InterleaveGroups) {
     auto *Recipe = cast<VPWidenMemoryInstructionRecipe>(
         RecipeBuilder.getRecipe(IG->getInsertPos()));
     (new VPInterleaveRecipe(IG, Recipe->getAddr(), Recipe->getMask()))
         ->insertBefore(Recipe);
 
     for (unsigned i = 0; i < IG->getFactor(); ++i)
       if (Instruction *Member = IG->getMember(i)) {
+        VPValue *NewVPV = nullptr;
+        if (!Member->getType()->isVoidTy()) {
+          NewVPV = new VPValue(Member);
+          Plan->getVPValue(Member)->replaceAllUsesWith(NewVPV);
+        }
         RecipeBuilder.getRecipe(Member)->eraseFromParent();
+        if (NewVPV)
+          Plan->addVPValue(Member, NewVPV);
       }
   }
 
   // Adjust the recipes for any inloop reductions.
   if (Range.Start > 1)
     adjustRecipesForInLoopReductions(Plan, RecipeBuilder);
 
   // Finally, if tail is folded by masking, introduce selects between the phi
if (State.ValueMap.hasVectorValue(PredInst, Part)) {
     PHINode *Phi = State.Builder.CreatePHI(PredInstType, 2);
     Phi->addIncoming(UndefValue::get(ScalarPredInst->getType()), PredicatingBB);
     Phi->addIncoming(ScalarPredInst, PredicatedBB);
     State.ValueMap.resetScalarValue(PredInst, *State.Instance, Phi);
   }
 }
 
 void VPWidenMemoryInstructionRecipe::execute(VPTransformState &State) {
+  Instruction *Instr = getUnderlyingInstr();
   VPValue *StoredValue = isa<StoreInst>(Instr) ? getStoredValue() : nullptr;
-  State.ILV->vectorizeMemoryInstruction(&Instr, State, getAddr(), StoredValue,
-                                        getMask());
+  State.ILV->vectorizeMemoryInstruction(Instr, State,
+                                        StoredValue ? nullptr : this, getAddr(),
+                                        StoredValue, getMask());
 }
 
 // Determine how to lower the scalar epilogue, which depends on 1) optimising
 // for minimum code-size, 2) predicate compiler options, 3) loop hints forcing
 // predication, and 4) a TTI hook that analyses whether the loop is suitable
 // for predication.
 static ScalarEpilogueLowering getScalarEpilogueLowering(
     Function *F, Loop *L, LoopVectorizeHints &Hints, ProfileSummaryInfo *PSI,
if (PreferPredicateOverEpilogue ||
       (TTI->preferPredicateOverEpilogue(L, LI, *SE, *AC, TLI, DT,
                                         LVL.getLAI()) &&
        Hints.getPredicate() != LoopVectorizeHints::FK_Disabled))
     return CM_ScalarEpilogueNotNeededUsePredicate;
 
   return CM_ScalarEpilogueAllowed;
 }
 
+void VPTransformState::set(VPValue *Def, Value *IRDef, Value *V,
+                           unsigned Part) {
+  set(Def, V, Part);
+  ILV->setVectorValue(IRDef, Part, V);
+}
+
 // Process the loop in the VPlan-native vectorization path. This path builds
 // VPlan upfront in the vectorization pipeline, which allows to apply
 // VPlan-to-VPlan transformations from the very beginning without modifying the
 // input LLVM IR.
 static bool processLoopInVPlanNativePath(
     Loop *L, PredicatedScalarEvolution &PSE, LoopInfo *LI, DominatorTree *DT,
     LoopVectorizationLegality *LVL, TargetTransformInfo *TTI,
     TargetLibraryInfo *TLI, DemandedBits *DB, AssumptionCache *AC,

llvm/lib/Transforms/Vectorize/VPlan.h

struct VPTransformState {
   Value *get(VPValue *Def, const VPIteration &Instance) {
     // If the Def is managed directly by VPTransformState, extract the lane from
     // the relevant part. Note that currently only VPInstructions and external
     // defs are managed by VPTransformState. Other Defs are still created by ILV
     // and managed in its ValueMap. For those this method currently just
     // delegates the call to ILV below.
     if (Data.PerPartOutput.count(Def)) {
       auto *VecPart = Data.PerPartOutput[Def][Instance.Part];
+      if (!VecPart->getType()->isVectorTy()) {
+        assert(Instance.Lane == 0 && "cannot get lane > 0 for scalar");
+        return VecPart;
+      }
       // TODO: Cache created scalar values.
       return Builder.CreateExtractElement(VecPart,
                                           Builder.getInt32(Instance.Lane));
     }
 
     return Callback.getOrCreateScalarValue(VPValue2Value[Def], Instance);
   }
 
   /// Set the generated Value for a given VPValue and a given Part.
   void set(VPValue *Def, Value *V, unsigned Part) {
     if (!Data.PerPartOutput.count(Def)) {
       DataState::PerPartValuesTy Entry(UF);
       Data.PerPartOutput[Def] = Entry;
     }
     Data.PerPartOutput[Def][Part] = V;
   }
+  void set(VPValue *Def, Value *IRDef, Value *V, unsigned Part);
 
   /// Hold state information used when constructing the CFG of the output IR,
   /// traversing the VPBasicBlocks and generating corresponding IR BasicBlocks.
   struct CFGState {
     /// The previous VPBasicBlock visited. Initially set to null.
     VPBasicBlock *PrevVPBB = nullptr;
 
     /// The previous IR BasicBlock created or used. Initially set to the new
public:
 
   /// 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();
+  const VPValue *toVPValue() const;
+
+  /// Returns the underlying instruction, if the recipe is a VPValue or nullptr
+  /// otherwise.
+  Instruction *getUnderlyingInstr() {
+    if (auto *VPV = toVPValue())
+      return cast_or_null<Instruction>(VPV->getUnderlyingValue());
+    return nullptr;
+  }
+  const Instruction *getUnderlyingInstr() const {
+    if (auto *VPV = toVPValue())
+      return cast_or_null<Instruction>(VPV->getUnderlyingValue());
+    return nullptr;
+  }
 };
 
 inline bool VPUser::classof(const VPRecipeBase *Recipe) {
   return Recipe->getVPRecipeID() == VPRecipeBase::VPInstructionSC ||
          Recipe->getVPRecipeID() == VPRecipeBase::VPWidenSC ||
          Recipe->getVPRecipeID() == VPRecipeBase::VPWidenCallSC ||
          Recipe->getVPRecipeID() == VPRecipeBase::VPWidenSelectSC ||
          Recipe->getVPRecipeID() == VPRecipeBase::VPWidenGEPSC ||
private:
   typedef unsigned char OpcodeTy;
   OpcodeTy Opcode;
 
   /// Utility method serving execute(): generates a single instance of the
   /// modeled instruction.
   void generateInstruction(VPTransformState &State, unsigned Part);
 
 protected:
-  Instruction *getUnderlyingInstr() {
-    return cast_or_null<Instruction>(getUnderlyingValue());
-  }
-
   void setUnderlyingInstr(Instruction *I) { setUnderlyingValue(I); }
 
 public:
   VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands)
       : VPUser(Operands), VPValue(VPValue::VPInstructionSC),
         VPRecipeBase(VPRecipeBase::VPInstructionSC), Opcode(Opcode) {}
 
   VPInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands)

 };
 
 /// 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 {
-  Instruction &Instr;
+class VPWidenMemoryInstructionRecipe : public VPRecipeBase,
+                                       public VPValue,
+                                       public VPUser {
 
   void setMask(VPValue *Mask) {
     if (!Mask)
       return;
     addOperand(Mask);
   }
 
   bool isMasked() const {
-    return (isa<LoadInst>(Instr) && getNumOperands() == 2) ||
-           (isa<StoreInst>(Instr) && getNumOperands() == 3);
+    return (isa<LoadInst>(getUnderlyingInstr()) && getNumOperands() == 2) ||
+           (isa<StoreInst>(getUnderlyingInstr()) && getNumOperands() == 3);
   }
 
 public:
   VPWidenMemoryInstructionRecipe(LoadInst &Load, VPValue *Addr, VPValue *Mask)
-      : VPRecipeBase(VPWidenMemoryInstructionSC), VPUser({Addr}), Instr(Load) {
+      : VPRecipeBase(VPWidenMemoryInstructionSC),
+        VPValue(VPValue::VPMemoryInstructionSC, &Load), VPUser({Addr}) {
     setMask(Mask);
   }
 
   VPWidenMemoryInstructionRecipe(StoreInst &Store, VPValue *Addr,
                                  VPValue *StoredValue, VPValue *Mask)
-      : VPRecipeBase(VPWidenMemoryInstructionSC), VPUser({Addr, StoredValue}),
-        Instr(Store) {
+      : VPRecipeBase(VPWidenMemoryInstructionSC),
+        VPValue(VPValue::VPMemoryInstructionSC, &Store),
+        VPUser({Addr, StoredValue}) {
     setMask(Mask);
   }
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == VPRecipeBase::VPWidenMemoryInstructionSC;
   }
 
   /// Return the address accessed by this recipe.
   VPValue *getAddr() const {
     return getOperand(0); // Address is the 1st, mandatory operand.
   }
 
   /// Return the mask used by this recipe. Note that a full mask is represented
   /// by a nullptr.
   VPValue *getMask() const {
     // Mask is optional and therefore the last operand.
     return isMasked() ? getOperand(getNumOperands() - 1) : nullptr;
   }
 
   /// Return the address accessed by this recipe.
   VPValue *getStoredValue() const {
-    assert(isa<StoreInst>(Instr) &&
+    assert(isa<StoreInst>(getUnderlyingInstr()) &&
            "Stored value only available for store instructions");
     return getOperand(1); // Stored value is the 2nd, mandatory operand.
   }
 
   /// Generate the wide load/store.
   void execute(VPTransformState &State) override;
 
   /// Print the recipe.
class VPlan {
   /// Represents the backedge taken count of the original loop, for folding
   /// the tail.
   VPValue *BackedgeTakenCount = nullptr;
 
   /// Holds a mapping between Values and their corresponding VPValue inside
   /// VPlan.
   Value2VPValueTy Value2VPValue;
 
+  /// Contains all VPValues that been allocated by addVPValue directly and need
+  /// to be free when the plan's destructor is called.
+  SmallVector<VPValue *, 16> VPValuesToFree;
+
   /// Holds the VPLoopInfo analysis for this VPlan.
   VPLoopInfo VPLInfo;
 
   /// Holds the condition bit values built during VPInstruction to VPRecipe transformation.
   SmallVector<VPValue *, 4> VPCBVs;
 
 public:
   VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {
     if (Entry)
       Entry->setPlan(this);
   }
 
   ~VPlan() {
     if (Entry)
       VPBlockBase::deleteCFG(Entry);
-    for (auto &MapEntry : Value2VPValue)
-      delete MapEntry.second;
+    for (VPValue *VPV : VPValuesToFree)
+      delete VPV;
     if (BackedgeTakenCount)
       delete BackedgeTakenCount;
     for (VPValue *Def : VPExternalDefs)
       delete Def;
     for (VPValue *CBV : VPCBVs)
       delete CBV;
   }
 
public:
   /// Add \p CBV to the vector of condition bit values.
   void addCBV(VPValue *CBV) {
     VPCBVs.push_back(CBV);
   }
 
   void addVPValue(Value *V) {
     assert(V && "Trying to add a null Value to VPlan");
     assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
-    Value2VPValue[V] = new VPValue(V);
+    VPValue *VPV = new VPValue(V);
+    Value2VPValue[V] = VPV;
+    VPValuesToFree.push_back(VPV);
+  }
+
+  void addVPValue(Value *V, VPValue *VPV) {
+    assert(V && "Trying to add a null Value to VPlan");
+    assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
+    Value2VPValue[V] = VPV;
+  }
+
+  void addOrReplaceVPValue(Value *V, VPValue *VPV) {
+    assert(V && "Trying to add a null Value to VPlan");
+    auto I = Value2VPValue.find(V);
+    if (I == Value2VPValue.end())
+      Value2VPValue[V] = VPV;
+    else
+      I->second = VPV;
   }
 
   VPValue *getVPValue(Value *V) {
     assert(V && "Trying to get the VPValue of a null Value");
     assert(Value2VPValue.count(V) && "Value does not exist in VPlan");
     return Value2VPValue[V];
   }
 
   VPValue *getOrAddVPValue(Value *V) {
     assert(V && "Trying to get or add the VPValue of a null Value");
     if (!Value2VPValue.count(V))
       addVPValue(V);
     return getVPValue(V);
   }
 
+  void removeVPValueFor(Value *V) { Value2VPValue.erase(V); }
+
   /// Return the VPLoopInfo analysis for this VPlan.
   VPLoopInfo &getVPLoopInfo() { return VPLInfo; }
   const VPLoopInfo &getVPLoopInfo() const { return VPLInfo; }
 
   /// Dump the plan to stderr (for debugging).
   void dump() const;
 
   /// Returns a range mapping the values the range \p Operands to their
void drawEdge(const VPBlockBase *From, const VPBlockBase *To, bool Hidden,
                 const Twine &Label);
 
   void dump();
 
   static void printAsIngredient(raw_ostream &O, const Value *V);
 };
 
 struct VPlanIngredient {
-  Value *V;
+  const Value *V;
 
-  VPlanIngredient(Value *V) : V(V) {}
+  VPlanIngredient(const Value *V) : V(V) {}
 };
 
 inline raw_ostream &operator<<(raw_ostream &OS, const VPlanIngredient &I) {
   VPlanPrinter::printAsIngredient(OS, I.V);
   return OS;
 }
 
 inline raw_ostream &operator<<(raw_ostream &OS, const VPlan &Plan) {

llvm/lib/Transforms/Vectorize/VPlan.cpp

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 *V = dyn_cast<VPInstruction>(this))
+    return V;
+  if (auto *V = dyn_cast<VPWidenMemoryInstructionRecipe>(this))
+    return V;
+  return nullptr;
+}
+
+const VPValue *VPRecipeBase::toVPValue() const {
+  if (auto *V = dyn_cast<VPInstruction>(this))
+    return V;
+  if (auto *V = dyn_cast<VPWidenMemoryInstructionRecipe>(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;
 

 }
 
 void VPRecipeBase::removeFromParent() {
   assert(getParent() && "Recipe not in any VPBasicBlock");
   getParent()->getRecipeList().remove(getIterator());
   Parent = nullptr;
 }
 
-VPValue *VPRecipeBase::toVPValue() {
-  if (auto *V = dyn_cast<VPInstruction>(this))
-    return V;
-  return 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 (Value *UV = getUnderlyingInstr())
+    if (!UV->getType()->isVoidTy())
+      if (auto *Plan = getParent()->getPlan())
+        Plan->removeVPValueFor(UV);
+
   return getParent()->getRecipeList().erase(getIterator());
 }
 
 void VPRecipeBase::moveAfter(VPRecipeBase *InsertPos) {
   removeFromParent();
   insertAfter(InsertPos);
 }
 

 
 void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent,
                                 VPSlotTracker &SlotTracker) const {
   O << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst);
 }
 
 void VPWidenMemoryInstructionRecipe::print(raw_ostream &O, const Twine &Indent,
                                            VPSlotTracker &SlotTracker) const {
-  O << "\"WIDEN " << Instruction::getOpcodeName(Instr.getOpcode()) << " ";
+  O << "\"WIDEN "
+    << Instruction::getOpcodeName(getUnderlyingInstr()->getOpcode()) << " ";
 
   bool First = true;
   for (VPValue *Op : operands()) {
     if (!First)
       O << ", ";
     Op->printAsOperand(O, SlotTracker);
     First = false;
   }
 }
 
 void VPWidenCanonicalIVRecipe::execute(VPTransformState &State) {
   Value *CanonicalIV = State.CanonicalIV;
   Type *STy = CanonicalIV->getType();
   IRBuilder<> Builder(State.CFG.PrevBB->getTerminator());
   ElementCount VF = State.VF;
   assert(!VF.isScalable() && "the code following assumes non scalables ECs");
   Value *VStart = VF.isScalar()

llvm/lib/Transforms/Vectorize/VPlanValue.h

 // 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;
   friend struct VPlanTransforms;
   friend class VPBasicBlock;
   friend class VPInterleavedAccessInfo;
   friend class VPSlotTracker;
+  friend class VPRecipeBase;
 
   const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
 
   SmallVector<VPUser *, 1> Users;
 
 protected:
   // Hold the underlying Value, if any, attached to this VPValue.
   Value *UnderlyingVal;
void setUnderlyingValue(Value *Val) {
     UnderlyingVal = Val;
   }
 
 public:
   /// An enumeration for keeping track of the concrete subclass of VPValue that
   /// 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, VPInstructionSC };
+  enum { VPValueSC, VPInstructionSC, VPMemoryInstructionSC };
 
   VPValue(Value *UV = nullptr) : VPValue(VPValueSC, UV) {}
   VPValue(const VPValue &) = delete;
   VPValue &operator=(const VPValue &) = delete;
 
   /// \return an ID for the concrete type of this object.
   /// This is used to implement the classof checks. This should not be used
   /// for any other purpose, as the values may change as LLVM evolves.