[VPlan] Manage scalarized values using VPValues.

[fhahn]

Summary

This patch updates codegen to use VPValues to manage the generated
scalarized instructions.

[fhahn]

Adjust vplan printing test and split off changes to use VPTransformState in a few more places to D95757. This is required to ensure we pick up the scalarized values managed directly in VPTransformState.

[a.elovikov]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

2697

nit: Should it be Builder.getInsertBlock() to avoid calling getParent on BasicBlock::end() iterator? It might be impossible to have the end iterator here, but the getInsertBlock version is generally safer, IMO.

2718–2719

nit: I think commenting it out would be misleading for the reader. Can we just remove it?

[fhahn]

Use GetInsertBlock, remove misleading comment, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

2697

Good point, adjusted!

2718–2719

Yes, the comment should be outdated now. I removed it.

[gilr]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8231

Call getOperand(0)->getUnderlyingValue() directly?

8232

Can this line be brought back under the comment to minimize the diff?

8239–8248

Can the then/else logic be reversed to minimize the diff?

[fhahn]

Updated code in VPPredInstPHIRecipe::execute to reduce diff as suggested. Thanks!

[gilr]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8089

No need to pass as arguments now that State itself is passed.

8253

This is porting the resetVectorValue to State operations, which I think is fine by itself (I tend to agree with passing nullptr as the underlying value to VPPredInstPHI), but something else bothers me: It seems VPPredInstPHI doesn't take over the VPReplicate as the VPValue mapped to the predicated IR value during VPlan construction, which means that recipes constructed for users of predicated instructions use the ReplicateRecipe although it doesn't dominate them. We get away with this by overriding the IR's vector value, but for correct VP def-use we should have VPPredInstPHI take over as the registered VPValue in VPlan during construction. Does all that make sense?

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8253

I think the problem here is how we generate code for a scalarization region, like the one below. Uses after the region use the PHI-PREDICATED-INSTRUCTION VPValue.

But when generating code for the region itself, we execute the same blocks once for each vector element. So in the second iteration "REPLICATE ir<%div> = udiv ir<16>, ir<%counter1.0> (S->V)\l" currently needs to pack its result in the result vector from the previous iteration. Currently that is done by overwriting the state of the def "REPLICATE ir<%div> = udiv ir<16>, ir<%counter1.0> (S->V)\l" with the predicated PHI from the previous iteration, so the vector-pack logic picks it up.

It might be possible to instead change the code to just have scalar phis and do the packing as part of the phi creation. I think for transformations, the VPValue def-use chain should be correct, and it is 'just' a code-gen improvement. Do you think we need to fix this before this one goes in?

subgraph cluster_N2 {
  fontname=Courier
  label="\<xVFxUF\> pred.udiv"
  N1 [label =
    "pred.udiv.entry:\n" +
      " +
      "BRANCH-ON-MASK vp<%4>\l"\l" +
       "CondBit: vp<%4> (for.body3)\l"
  ]
  N1 -> N3 [ label="T"]
  N1 -> N4 [ label="F"]
  N3 [label =
    "pred.udiv.if:\n" +
      "REPLICATE ir<%div> = udiv ir<16>, ir<%counter1.0> (S->V)\l"
  ]
  N3 -> N4 [ label=""]
  N4 [label =
    "pred.udiv.continue:\n" +
      "PHI-PREDICATED-INSTRUCTION vp<%6> = ir<%div>\l"
  ]
}

[fhahn]

Ping :)

Rebased and added a note about why we are re-setting the value for operands of VPPRedPHI. Also added a few comments to set/reset functions and assertions.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8253

@gilr I added a note explaining why we need to also update the operand. Do you think that is sufficient to move forward with this patch?

[gilr]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8089

No need to pass as arguments now that State itself is passed.

Does that make sense?

8253

Yes, thanks!

8253

Uses after the region use the PHI-PREDICATED-INSTRUCTION VPValue.

Right, I missed the part where you replace the predicated instruction's VPValue with the new PredInstRecipe.

It might be possible to instead change the code to just have scalar phis and do the packing as part of the phi creation. I think for transformations, the VPValue def-use chain should be correct, and it is 'just' a code-gen improvement. Do you think we need to fix this before this one goes in?

Not sure recipes should create values in other places than their designated location. Anyway, this shouldn't block this patch.

[fhahn]

Thanks Gil! I removed the UF/VF arguments from widenPHIInstruction, I totally missed that I did not address this comment originally.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8089

Does that make sense?

Yes, sorry I totally missed that I did not update this so far! Fixed now.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

public:
   /// decisions taken during planning.
   void widenGEP(GetElementPtrInst *GEP, VPValue *VPDef, VPUser &Indices,
                 unsigned UF, ElementCount VF, bool IsPtrLoopInvariant,
                 SmallBitVector &IsIndexLoopInvariant, VPTransformState &State);
 
   /// Vectorize a single PHINode in a block. This method handles the induction
   /// variable canonicalization. It supports both VF = 1 for unrolled loops and
   /// arbitrary length vectors.
-  void widenPHIInstruction(Instruction *PN, unsigned UF, ElementCount VF);
+  void widenPHIInstruction(Instruction *PN, unsigned UF, ElementCount VF,
+                           VPValue *Def, VPTransformState &State);
 
   /// A helper function to scalarize a single Instruction in the innermost loop.
   /// Generates a sequence of scalar instances for each lane between \p MinLane
   /// and \p MaxLane, times each part between \p MinPart and \p MaxPart,
   /// inclusive. Uses the VPValue operands from \p Operands instead of \p
   /// Instr's operands.
-  void scalarizeInstruction(Instruction *Instr, VPUser &Operands,
+  void scalarizeInstruction(Instruction *Instr, VPValue *Def, VPUser &Operands,
                             const VPIteration &Instance, bool IfPredicateInstr,
                             VPTransformState &State);
 
   /// Widen an integer or floating-point induction variable \p IV. If \p Trunc
   /// is provided, the integer induction variable will first be truncated to
   /// the corresponding type.
   void widenIntOrFpInduction(PHINode *IV, TruncInst *Trunc, VPValue *Def,
                              VPValue *CastDef, VPTransformState &State);
if (CreateGatherScatter) {
       if (Reverse)
         NewLI = reverseVector(NewLI);
     }
 
     State.set(Def, Instr, NewLI, Part);
   }
 }
 
-void InnerLoopVectorizer::scalarizeInstruction(Instruction *Instr, VPUser &User,
+void InnerLoopVectorizer::scalarizeInstruction(Instruction *Instr, VPValue *Def,
+                                               VPUser &User,
                                                const VPIteration &Instance,
                                                bool IfPredicateInstr,
                                                VPTransformState &State) {
   assert(!Instr->getType()->isAggregateType() && "Can't handle vectors");
 
   setDebugLocFromInst(Builder, Instr);
 
   // Does this instruction return a value ?
   bool IsVoidRetTy = Instr->getType()->isVoidTy();
 
   Instruction *Cloned = Instr->clone();
   if (!IsVoidRetTy)
     Cloned->setName(Instr->getName() + ".cloned");
 
+  State.Builder.SetInsertPoint(Builder.GetInsertPoint()->getParent(),
+                               Builder.GetInsertPoint());
   // Replace the operands of the cloned instructions with their scalar
   // equivalents in the new loop.
   for (unsigned op = 0, e = User.getNumOperands(); op != e; ++op) {
     auto *Operand = dyn_cast<Instruction>(Instr->getOperand(op));
     auto InputInstance = Instance;
     if (!Operand || !OrigLoop->contains(Operand) ||
         (Cost->isUniformAfterVectorization(Operand, State.VF)))
       InputInstance.Lane = 0;
     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);
 
   // 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);
+  // VectorLoopValueMap.setScalarValue(Instr, Instance, Cloned);
+  State.set(Def, Instr, Cloned, Instance);
 
   // 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.
   if (IfPredicateInstr)
for (unsigned Part = 0; Part < UF; ++Part) {
              "NewGEP is not a pointer vector");
       State.set(VPDef, GEP, NewGEP, Part);
       addMetadata(NewGEP, GEP);
     }
   }
 }
 
 void InnerLoopVectorizer::widenPHIInstruction(Instruction *PN, unsigned UF,
-                                              ElementCount VF) {
+                                              ElementCount VF, VPValue *Def,
+                                              VPTransformState &State) {
   assert(!VF.isScalable() && "scalable vectors not yet supported.");
   PHINode *P = cast<PHINode>(PN);
   if (EnableVPlanNativePath) {
     // Currently we enter here in the VPlan-native path for non-induction
     // PHIs where all control flow is uniform. We simply widen these PHIs.
     // Create a vector phi with no operands - the vector phi operands will be
     // set at the end of vector code generation.
     Type *VecTy =
         (VF.isScalar()) ? PN->getType() : VectorType::get(PN->getType(), VF);
     Value *VecPhi = Builder.CreatePHI(VecTy, PN->getNumOperands(), "vec.phi");
-    VectorLoopValueMap.setVectorValue(P, 0, VecPhi);
+    State.set(Def, P, VecPhi, 0);
     OrigPHIsToFix.push_back(P);
 
     return;
   }
 
   assert(PN->getParent() == OrigLoop->getHeader() &&
          "Non-header phis should have been handled elsewhere");
 
   // In order to support recurrences we need to be able to vectorize Phi nodes.
   // Phi nodes have cycles, so we need to vectorize them in two stages. This is
   // stage #1: We create a new vector PHI node with no incoming edges. We'll use
   // this value when we vectorize all of the instructions that use the PHI.
   if (Legal->isReductionVariable(P) || Legal->isFirstOrderRecurrence(P)) {
     for (unsigned Part = 0; Part < UF; ++Part) {
       // This is phase one of vectorizing PHIs.
       bool ScalarPHI =
           (VF.isScalar()) || Cost->isInLoopReduction(cast<PHINode>(PN));
       Type *VecTy =
           ScalarPHI ? PN->getType() : VectorType::get(PN->getType(), VF);
       Value *EntryPart = PHINode::Create(
           VecTy, 2, "vec.phi", &*LoopVectorBody->getFirstInsertionPt());
-      VectorLoopValueMap.setVectorValue(P, Part, EntryPart);
+      State.set(Def, P, EntryPart, Part);
     }
     return;
   }
 
   setDebugLocFromInst(Builder, P);
 
   // This PHINode must be an induction variable.
   // Make sure that we know about it.
if (Cost->isScalarAfterVectorization(P, VF)) {
       for (unsigned Part = 0; Part < UF; ++Part) {
         for (unsigned Lane = 0; Lane < Lanes; ++Lane) {
           Constant *Idx = ConstantInt::get(PtrInd->getType(),
                                            Lane + Part * VF.getKnownMinValue());
           Value *GlobalIdx = Builder.CreateAdd(PtrInd, Idx);
           Value *SclrGep =
               emitTransformedIndex(Builder, GlobalIdx, PSE.getSE(), DL, II);
           SclrGep->setName("next.gep");
-          VectorLoopValueMap.setScalarValue(P, {Part, Lane}, SclrGep);
+          State.set(Def, P, SclrGep, {Part, Lane});
         }
       }
       return;
     }
     assert(isa<SCEVConstant>(II.getStep()) &&
            "Induction step not a SCEV constant!");
     Type *PhiType = II.getStep()->getType();
 
for (unsigned Part = 0; Part < UF; ++Part) {
       Constant *StartOffset = ConstantVector::get(Indices);
 
       Value *GEP = Builder.CreateGEP(
           ScStValueType->getPointerElementType(), NewPointerPhi,
           Builder.CreateMul(
               StartOffset,
               Builder.CreateVectorSplat(VF.getKnownMinValue(), ScalarStepValue),
               "vector.gep"));
-      VectorLoopValueMap.setVectorValue(P, Part, GEP);
+      State.set(Def, P, GEP, Part);
     }
   }
   }
 }
 
 /// A helper function for checking whether an integer division-related
 /// instruction may divide by zero (in which case it must be predicated if
 /// executed conditionally in the scalar code).
void VPWidenIntOrFpInductionRecipe::execute(VPTransformState &State) {
   State.ILV->widenIntOrFpInduction(
       IV,
       IsTrunc ? cast<TruncInst>(getVPValue(0)->getUnderlyingValue()) : nullptr,
       getVPValue(0), getNumDefinedValues() == 2 ? getVPValue(1) : nullptr,
       State);
 }
 
 void VPWidenPHIRecipe::execute(VPTransformState &State) {
-  State.ILV->widenPHIInstruction(Phi, State.UF, State.VF);
+  State.ILV->widenPHIInstruction(Phi, State.UF, State.VF, this, State);
 }
 
 void VPBlendRecipe::execute(VPTransformState &State) {
   State.ILV->setDebugLocFromInst(State.Builder, Phi);
   // We know that all PHIs in non-header blocks are converted into
   // selects, so we don't have to worry about the insertion order and we
   // can just use the builder.
   // At this point we generate the predication tree. There may be
   // duplications since this is a simple recursive scan, but future
for (unsigned Part = 0; Part < State.UF; ++Part) {
         // based on the incoming mask.
         Value *Cond = State.get(getMask(In), Part);
         Entry[Part] =
             State.Builder.CreateSelect(Cond, In0, Entry[Part], "predphi");
       }
     }
   }
   for (unsigned Part = 0; Part < State.UF; ++Part)
-    State.ValueMap.setVectorValue(Phi, Part, Entry[Part]);
+    State.set(this, Phi, Entry[Part], Part);
 }
 
 void VPInterleaveRecipe::execute(VPTransformState &State) {
   assert(!State.Instance && "Interleave group being replicated.");
   State.ILV->vectorizeInterleaveGroup(IG, definedValues(), State, getAddr(),getStoredValues(),
                                       getMask());
 }
 
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(getUnderlyingInstr(), *this,
+    State.ILV->scalarizeInstruction(getUnderlyingInstr(), this, *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(getUnderlyingValue()->getType(), State.VF));
-        State.ValueMap.setVectorValue(getUnderlyingInstr(),
-                                      State.Instance->Part, Undef);
+        State.set(this, getUnderlyingInstr(), Undef, State.Instance->Part);
       }
-      State.ILV->packScalarIntoVectorValue(getUnderlyingInstr(),
-                                           *State.Instance);
+      State.ILV->packScalarIntoVectorValue(this, *State.Instance, State);
     }
     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(getUnderlyingInstr(), *this, {Part, Lane},
-                                      IsPredicated, State);
+      State.ILV->scalarizeInstruction(getUnderlyingInstr(), this, *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;
 

 void VPPredInstPHIRecipe::execute(VPTransformState &State) {
   assert(State.Instance && "Predicated instruction PHI works per instance.");
   Instruction *ScalarPredInst =
       cast<Instruction>(State.get(getOperand(0), *State.Instance));
   BasicBlock *PredicatedBB = ScalarPredInst->getParent();
   BasicBlock *PredicatingBB = PredicatedBB->getSinglePredecessor();
   assert(PredicatingBB && "Predicated block has no single predecessor.");
 
+  auto *RepR = dyn_cast<VPReplicateRecipe>(getOperand(0));
+  unsigned Part = State.Instance->Part;
   // By current pack/unpack logic we need to generate only a single phi node: if
   // a vector value for the predicated instruction exists at this point it means
   // the instruction has vector users only, and a phi for the vector value is
   // needed. In this case the recipe of the predicated instruction is marked to
   // also do that packing, thereby "hoisting" the insert-element sequence.
   // Otherwise, a phi node for the scalar value is needed.
-  unsigned Part = State.Instance->Part;
-  Instruction *PredInst =
-      cast<Instruction>(getOperand(0)->getUnderlyingValue());
-  if (State.ValueMap.hasVectorValue(PredInst, Part)) {
-    Value *VectorValue = State.ValueMap.getVectorValue(PredInst, Part);
+  if (!State.hasVectorValue(getOperand(0), Part)) {
+    Type *PredInstType = RepR->getUnderlyingInstr()->getType();
+    PHINode *Phi = State.Builder.CreatePHI(PredInstType, 2);
+    Phi->addIncoming(UndefValue::get(ScalarPredInst->getType()), PredicatingBB);
+    Phi->addIncoming(ScalarPredInst, PredicatedBB);
+    State.set(this, Phi, *State.Instance);
+    State.set(getOperand(0), Phi, *State.Instance);
+
+  } else {
+    Value *VectorValue = State.get(getOperand(0), Part);
     InsertElementInst *IEI = cast<InsertElementInst>(VectorValue);
     PHINode *VPhi = State.Builder.CreatePHI(IEI->getType(), 2);
     VPhi->addIncoming(IEI->getOperand(0), PredicatingBB); // Unmodified vector.
     VPhi->addIncoming(IEI, PredicatedBB); // New vector with inserted element.
-    State.ValueMap.resetVectorValue(PredInst, Part, VPhi); // Update cache.
-  } else {
-    Type *PredInstType = PredInst->getType();
-    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);
+    State.set(this, VPhi, VPhi, Part);
+    State.set(getOperand(0), VPhi, Part);
   }
 }
 
 void VPWidenMemoryInstructionRecipe::execute(VPTransformState &State) {
   VPValue *StoredValue = isStore() ? getStoredValue() : nullptr;
   State.ILV->vectorizeMemoryInstruction(getUnderlyingInstr(), State,
                                         StoredValue ? nullptr : this, getAddr(),
                                         StoredValue, getMask());

llvm/lib/Transforms/Vectorize/VPlan.h

struct VPTransformState {
   /// Get the generated Value for a given VPValue and a given Part. Note that
   /// as some Defs are still created by ILV and managed in its ValueMap, this
   /// method will delegate the call to ILV in such cases in order to provide
   /// callers a consistent API.
   /// \see set.
   Value *get(VPValue *Def, unsigned Part);
 
   /// Get the generated Value for a given VPValue and given Part and Lane.
+
   Value *get(VPValue *Def, VPIteration Instance);
 
   bool hasVectorValue(VPValue *Def, unsigned Part) {
     auto I = Data.PerPartOutput.find(Def);
     return I != Data.PerPartOutput.end() && Part < I->second.size() &&
            I->second[Part];
   }
 
struct VPTransformState {
   /// 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);
 
   void set(VPValue *Def, Value *IRDef, Value *V, const VPIteration &Instance);
 
   void set(VPValue *Def, Value *V, const VPIteration &Instance) {
     auto Iter = Data.PerPartScalars.insert({Def, {}});
     auto &PerPartVec = Iter.first->second;
     while (PerPartVec.size() <= Instance.Part)

 class VPWidenIntOrFpInductionRecipe : public VPRecipeBase {
   PHINode *IV;
   bool IsTrunc;
 
 public:
   VPWidenIntOrFpInductionRecipe(PHINode *IV, Instruction *Cast,
                                 TruncInst *Trunc = nullptr)
       : VPRecipeBase(VPWidenIntOrFpInductionSC), IV(IV), IsTrunc(false) {
-
     if (Trunc) {
       new VPValue(VPValue::VPValueSubSC, Trunc, this);
       IsTrunc = true;
     } else
       new VPValue(VPValue::VPValueSubSC, IV, this);
 
     if (Cast)
       new VPValue(VPValue::VPValueSubSC, Cast, this);
public:
   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 {
+class VPWidenPHIRecipe : public VPRecipeBase, public VPValue {
   PHINode *Phi;
 
 public:
-  VPWidenPHIRecipe(PHINode *Phi) : VPRecipeBase(VPWidenPHISC), Phi(Phi) {
-    new VPValue(VPValue::VPValueSubSC, Phi, this);
-  }
+  VPWidenPHIRecipe(PHINode *Phi)
+      : VPRecipeBase(VPWidenPHISC), VPValue(VPValue::VPVWidenPHISC, Phi, this),
+        Phi(Phi) {}
   ~VPWidenPHIRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPDef *D) {
     return D->getVPDefID() == 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, public VPUser, public VPValue {
   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) {
-    new VPValue(VPValue::VPValueSubSC, Phi, this);
+      : VPRecipeBase(VPBlendSC), VPUser(Operands),
+        VPValue(VPValue::VPVBlendSC, Phi, this), 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 VPDef *D) {
public:
 
   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; }
+
+  bool isPacked() const { return AlsoPack; }
 };
 
 /// 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:
   }
 };
 
 /// VPPredInstPHIRecipe is a recipe for generating the phi nodes needed when
 /// control converges back from a Branch-on-Mask. The phi nodes are needed in
 /// order to merge values that are set under such a branch and feed their uses.
 /// The phi nodes can be scalar or vector depending on the users of the value.
 /// This recipe works in concert with VPBranchOnMaskRecipe.
-class VPPredInstPHIRecipe : public VPRecipeBase, public VPUser {
-
+class VPPredInstPHIRecipe : public VPRecipeBase, public VPUser, public VPValue {
 public:
   /// Construct a VPPredInstPHIRecipe given \p PredInst whose value needs a phi
   /// nodes after merging back from a Branch-on-Mask.
   VPPredInstPHIRecipe(VPValue *PredV)
-      : VPRecipeBase(VPPredInstPHISC), VPUser(PredV) {
-    new VPValue(VPValue::VPValueSubSC, PredV->getUnderlyingValue(), this);
-  }
+      : VPRecipeBase(VPPredInstPHISC), VPUser(PredV),
+        VPValue(VPValue::VPVPredInstPHI, nullptr, this) {}
   ~VPPredInstPHIRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPDef *D) {
     return D->getVPDefID() == VPRecipeBase::VPPredInstPHISC;
   }
 
   /// Generates phi nodes for live-outs as needed to retain SSA form.

llvm/lib/Transforms/Vectorize/VPlan.cpp

Value *VPTransformState::get(VPValue *Def, VPIteration Instance) {
   if (auto *C = Def->getOutOfScopeIRValue())
     return C;
 
   // For uniform definitions, all lanes produce the same value, so we can always
   // return the first lane.
   if (auto *ReplicateR = dyn_cast<VPReplicateRecipe>(Def))
     if (ReplicateR->isUniform())
       Instance.Lane = 0;
-
   if (hasScalarValue(Def, Instance))
     return Data.PerPartScalars[Def][Instance.Part][Instance.Lane];
 
   if (hasVectorValue(Def, Instance.Part)) {
     assert(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.
     auto *Extract =
         Builder.CreateExtractElement(VecPart, Builder.getInt32(Instance.Lane));
     // set(Def, Extract, Instance);
     return Extract;
   }
 
-  return Callback.getOrCreateScalarValue(VPValue2Value[Def], Instance);
+  if (hasScalarValue(Def, Instance))
+    return Data.PerPartScalars[Def][Instance.Part][Instance.Lane];
+
+  assert(hasVectorValue(Def, Instance.Part));
+  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.
+  auto *Extract =
+      Builder.CreateExtractElement(VecPart, Builder.getInt32(Instance.Lane));
+  // set(Def, Extract, Instance);
+  return Extract;
 }
 
 BasicBlock *
 VPBasicBlock::createEmptyBasicBlock(VPTransformState::CFGState &CFG) {
   // BB stands for IR BasicBlocks. VPBB stands for VPlan VPBasicBlocks.
   // Pred stands for Predessor. Prev stands for Previous - last visited/created.
   BasicBlock *PrevBB = CFG.PrevBB;
   BasicBlock *NewBB = BasicBlock::Create(PrevBB->getContext(), getName(),
void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent,
 
   if (AlsoPack)
     O << " (S->V)";
 }
 
 void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent,
                                 VPSlotTracker &SlotTracker) const {
   O << "\"PHI-PREDICATED-INSTRUCTION ";
+  printAsOperand(O, SlotTracker);
+  O << " = ";
   printOperands(O, SlotTracker);
 }
 
 void VPWidenMemoryInstructionRecipe::print(raw_ostream &O, const Twine &Indent,
                                            VPSlotTracker &SlotTracker) const {
   O << "\"WIDEN ";
 
   if (!isStore()) {

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

for (auto I = VPBB->begin(), E = VPBB->end(); I != E;) {
             GEP, Plan->mapToVPValues(GEP->operands()), OrigLoop);
       } else
         NewRecipe =
             new VPWidenRecipe(*Inst, Plan->mapToVPValues(Inst->operands()));
 
       NewRecipe->insertBefore(Ingredient);
       VPInst->replaceAllUsesWith(&DummyValue);
       Ingredient->eraseFromParent();
+      Plan->removeVPValueFor(Inst);
+      for (auto *Def : NewRecipe->definedValues()) {
+        Plan->addVPValue(Inst, Def);
+      }
     }
   }
 }

llvm/lib/Transforms/Vectorize/VPlanValue.h

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,    /// VPValue defined outside of VPlan.
     VPValueSubSC, // VPValue defined by a VPDef that defines multiple VPValues.
+    VPVBlendSC,
     VPVInstructionSC,
     VPVMemoryInstructionSC,
+    VPVPredInstPHI,
     VPVReductionSC,
     VPVReplicateSC,
     VPVWidenSC,
     VPVWidenCallSC,
     VPVWidenGEPSC,
+    VPVWidenIntOrFpIndcutionSC,
+    VPVWidenPHISC,
     VPVWidenSelectSC,
   };
 
   VPValue(Value *UV = nullptr, VPDef *Def = nullptr)
       : VPValue(VPValueSC, UV, Def) {}
   VPValue(const VPValue &) = delete;
   VPValue &operator=(const VPValue &) = delete;