[VPlan][WIP] VMULH via multiple inheritance

[dmgreen]

Summary

This is not ready for review yet. At the very least, it will not do anything properly without adjusting the cost model for the adjusted vplan (it will currently just use the sum of the costs for the instructions in the original loop). It is probably several commits in one.

It is meant mostly as an illustration to show different ways of vplan working, between multiple inheritance and inheriting through VPRecipeBase. It sits on top of the patches linked to D84679, but is still in a very rough state.

The patch:

• Adds a adjustVPlanForVectorPatterns to transform VPlans to other vector patterns.
• Adds tryCombineToMulh to match trunc(lsr(mul(ext, ext)), BW)) and convert it to a VPInstruction::vmulh node in the vplan graph.
• It adds some simple vp_ pattern matchers.

In order to do this it makes the various VPRecipe's inherit from VPUser, VPValue and VPRecipe (where needed), as is done in D84679. It adds the extra casting logic needed, but I believe recursivelyDeleteUnusedRecipes does not work here (but probably could be made to with some extra love).

[dmgreen]

This is no longer needed. I think there are simpler ways to do it than this.

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

private:
   /// Build a VPlan according to the information gathered by Legal. \return a
   /// VPlan for vectorization factors \p Range.Start and up to \p Range.End
   /// exclusive, possibly decreasing \p Range.End.
   VPlanPtr buildVPlan(VFRange &Range);
 
   /// Build a VPlan using VPRecipes according to the information gather by
   /// Legal. This method is only used for the legacy inner loop vectorizer.
   VPlanPtr buildVPlanWithVPRecipes(
-      VFRange &Range, SmallPtrSetImpl<Value *> &NeedDef,
-      SmallPtrSetImpl<Instruction *> &DeadInstructions,
+      VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions,
       const DenseMap<Instruction *, Instruction *> &SinkAfter);
 
   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
   /// according to the information gathered by Legal when it checked if it is
   /// legal to vectorize the loop. This method creates VPlans using VPRecipes.
   void buildVPlansWithVPRecipes(unsigned MinVF, unsigned MaxVF);
 
   /// Adjust the recipes for any inloop reductions. The chain of instructions
   /// leading from the loop exit instr to the phi need to be converted to
   /// reductions, with one operand being vector and the other being the scalar
   /// reduction chain.
   void adjustRecipesForInLoopReductions(VPlanPtr &Plan,
                                         VPRecipeBuilder &RecipeBuilder);
+  bool adjustVPlanForVectorPatterns(VPlanPtr &Plan,
+                                    VPRecipeBuilder &RecipeBuilder);
 };
 
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

 #include <functional>
 #include <iterator>
 #include <limits>
 #include <memory>
 #include <string>
 #include <tuple>
 #include <utility>
 
+#include <llvm/IR/PatternMatch.h>
+
 using namespace llvm;
 
 #define LV_NAME "loop-vectorize"
 #define DEBUG_TYPE LV_NAME
 
 /// @{
 /// Metadata attribute names
 static const char *const LLVMLoopVectorizeFollowupAll =
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 *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.
VPValue *VPRecipeBuilder::createEdgeMask(BasicBlock *Src, BasicBlock *Dst,
 
   // The terminator has to be a branch inst!
   BranchInst *BI = dyn_cast<BranchInst>(Src->getTerminator());
   assert(BI && "Unexpected terminator found");
 
   if (!BI->isConditional() || BI->getSuccessor(0) == BI->getSuccessor(1))
     return EdgeMaskCache[Edge] = SrcMask;
 
-  VPValue *EdgeMask = Plan->getVPValue(BI->getCondition());
+  VPValue *EdgeMask = Plan->getOrAddVPValue(BI->getCondition());
   assert(EdgeMask && "No Edge Mask found for condition");
 
   if (BI->getSuccessor(0) != Dst)
     EdgeMask = Builder.createNot(EdgeMask);
 
   if (SrcMask) // Otherwise block in-mask is all-one, no need to AND.
     EdgeMask = Builder.createAnd(EdgeMask, SrcMask);
 
if (OrigLoop->getHeader() == BB) {
     auto NewInsertionPoint = Builder.getInsertBlock()->getFirstNonPhi();
     Builder.setInsertPoint(Builder.getInsertBlock(), NewInsertionPoint);
 
     // Introduce the early-exit compare IV <= BTC to form header block mask.
     // This is used instead of IV < TC because TC may wrap, unlike BTC.
     // Start by constructing the desired canonical IV.
     VPValue *IV = nullptr;
     if (Legal->getPrimaryInduction())
-      IV = Plan->getVPValue(Legal->getPrimaryInduction());
+      IV = Plan->getOrAddVPValue(Legal->getPrimaryInduction());
     else {
       auto IVRecipe = new VPWidenCanonicalIVRecipe();
       Builder.getInsertBlock()->insert(IVRecipe, NewInsertionPoint);
-      IV = IVRecipe->getVPValue();
+      IV = IVRecipe;
     }
     VPValue *BTC = Plan->getOrCreateBackedgeTakenCount();
     bool TailFolded = !CM.isScalarEpilogueAllowed();
 
     if (TailFolded && CM.TTI.emitGetActiveLaneMask()) {
       // While ActiveLaneMask is a binary op that consumes the loop tripcount
       // as a second argument, we only pass the IV here and extract the
       // tripcount from the transform state where codegen of the VP instructions
auto IsVectorizableOpcode = [](unsigned Opcode) {
     }
     return false;
   };
 
   if (!IsVectorizableOpcode(I->getOpcode()))
     return nullptr;
 
   // Success: widen this instruction.
-  return new VPWidenRecipe(*I, Plan.mapToVPValues(I->operands()));
+  VPWidenRecipe *Recipe =
+      new VPWidenRecipe(*I, Plan.mapToVPValues(I->operands()));
+  Plan.addVPValue(I, Recipe);
+  return Recipe;
 }
 
 VPBasicBlock *VPRecipeBuilder::handleReplication(
     Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
     DenseMap<Instruction *, VPReplicateRecipe *> &PredInst2Recipe,
     VPlanPtr &Plan) {
   bool IsUniform = LoopVectorizationPlanner::getDecisionAndClampRange(
       [&](ElementCount VF) { return CM.isUniformAfterVectorization(I, VF); },
VPRecipeBase *VPRecipeBuilder::tryToCreateWidenRecipe(Instruction *Instr,
 
   return tryToWiden(Instr, *Plan);
 }
 
 void LoopVectorizationPlanner::buildVPlansWithVPRecipes(unsigned MinVF,
                                                         unsigned MaxVF) {
   assert(OrigLoop->empty() && "Inner loop expected.");
 
-  // Collect conditions feeding internal conditional branches; they need to be
-  // represented in VPlan for it to model masking.
-  SmallPtrSet<Value *, 1> NeedDef;
-
-  auto *Latch = OrigLoop->getLoopLatch();
-  for (BasicBlock *BB : OrigLoop->blocks()) {
-    if (BB == Latch)
-      continue;
-    BranchInst *Branch = dyn_cast<BranchInst>(BB->getTerminator());
-    if (Branch && Branch->isConditional())
-      NeedDef.insert(Branch->getCondition());
-  }
-
-  // If the tail is to be folded by masking, the primary induction variable, if
-  // exists needs to be represented in VPlan for it to model early-exit masking.
-  // Also, both the Phi and the live-out instruction of each reduction are
-  // required in order to introduce a select between them in VPlan.
-  if (CM.foldTailByMasking()) {
-    if (Legal->getPrimaryInduction())
-      NeedDef.insert(Legal->getPrimaryInduction());
-    for (auto &Reduction : Legal->getReductionVars()) {
-      NeedDef.insert(Reduction.first);
-      NeedDef.insert(Reduction.second.getLoopExitInstr());
-    }
-  }
-
   // Collect instructions from the original loop that will become trivially dead
   // in the vectorized loop. We don't need to vectorize these instructions. For
   // example, original induction update instructions can become dead because we
   // separately emit induction "steps" when generating code for the new loop.
   // Similarly, we create a new latch condition when setting up the structure
   // of the new loop, so the old one can become dead.
   SmallPtrSet<Instruction *, 4> DeadInstructions;
   collectTriviallyDeadInstructions(DeadInstructions);
 
   // Add assume instructions we need to drop to DeadInstructions, to prevent
   // them from being added to the VPlan.
   // TODO: We only need to drop assumes in blocks that get flattend. If the
   // control flow is preserved, we should keep them.
   auto &ConditionalAssumes = Legal->getConditionalAssumes();
   DeadInstructions.insert(ConditionalAssumes.begin(), ConditionalAssumes.end());
 
   DenseMap<Instruction *, Instruction *> &SinkAfter = Legal->getSinkAfter();
   // Dead instructions do not need sinking. Remove them from SinkAfter.
   for (Instruction *I : DeadInstructions)
     SinkAfter.erase(I);
 
   for (unsigned VF = MinVF; VF < MaxVF + 1;) {
     VFRange SubRange = {VF, MaxVF + 1};
-    VPlans.push_back(buildVPlanWithVPRecipes(SubRange, NeedDef,
-                                             DeadInstructions, SinkAfter));
+    VPlans.push_back(
+        buildVPlanWithVPRecipes(SubRange, DeadInstructions, SinkAfter));
     VF = SubRange.End;
   }
 }
 
 VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
-    VFRange &Range, SmallPtrSetImpl<Value *> &NeedDef,
-    SmallPtrSetImpl<Instruction *> &DeadInstructions,
+    VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions,
     const DenseMap<Instruction *, Instruction *> &SinkAfter) {
 
   // Hold a mapping from predicated instructions to their recipes, in order to
   // fix their AlsoPack behavior if a user is determined to replicate and use a
   // scalar instead of vector value.
   DenseMap<Instruction *, VPReplicateRecipe *> PredInst2Recipe;
 
   SmallPtrSet<const InterleaveGroup<Instruction> *, 1> InterleaveGroups;
VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
   // visit each basic block after having visited its predecessor basic blocks.
   // ---------------------------------------------------------------------------
 
   // Create a dummy pre-entry VPBasicBlock to start building the VPlan.
   auto Plan = std::make_unique<VPlan>();
   VPBasicBlock *VPBB = new VPBasicBlock("Pre-Entry");
   Plan->setEntry(VPBB);
 
-  // Represent values that will have defs inside VPlan.
-  for (Value *V : NeedDef)
-    Plan->addVPValue(V);
-
   // Scan the body of the loop in a topological order to visit each basic block
   // after having visited its predecessor basic blocks.
   LoopBlocksDFS DFS(OrigLoop);
   DFS.perform(LI);
 
   for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO())) {
     // Relevant instructions from basic block BB will be grouped into VPRecipe
     // ingredients and fill a new VPBasicBlock.
for (auto &Entry : SinkAfter) {
     VPRecipeBase *Sink =
         RecipeBuilder.getRecipe(skipDeadInterleaveMembers(Entry.first));
     VPRecipeBase *Target =
         RecipeBuilder.getRecipe(skipDeadInterleaveMembers(Entry.second));
     Sink->moveAfter(Target);
   }
 
   // Adjust the recipes for any inloop reductions.
-  if (Range.Start > 1)
+  if (Range.Start > 1) {
     adjustRecipesForInLoopReductions(Plan, RecipeBuilder);
+    adjustVPlanForVectorPatterns(Plan, RecipeBuilder);
+  }
 
   // Finally, if tail is folded by masking, introduce selects between the phi
   // and the live-out instruction of each reduction, at the end of the latch.
   if (CM.foldTailByMasking() && !Legal->getReductionVars().empty()) {
     Builder.setInsertPoint(VPBB);
     auto *Cond = RecipeBuilder.createBlockInMask(OrigLoop->getHeader(), Plan);
     for (auto &Reduction : Legal->getReductionVars()) {
       if (CM.isInLoopReduction(Reduction.first))
         continue;
-      VPValue *Phi = Plan->getVPValue(Reduction.first);
-      VPValue *Red = Plan->getVPValue(Reduction.second.getLoopExitInstr());
+      VPValue *Phi = Plan->getOrAddVPValue(Reduction.first);
+      VPValue *Red = Plan->getOrAddVPValue(Reduction.second.getLoopExitInstr());
       Builder.createNaryOp(Instruction::Select, {Cond, Red, Phi});
     }
   }
 
   std::string PlanName;
   raw_string_ostream RSO(PlanName);
   ElementCount VF = ElementCount::getFixed(Range.Start);
   Plan->addVF(VF);
for (auto &Reduction : CM.getInLoopReductionChains()) {
     // LoopExitValue. We keep a track of the previous item (the Chain) to tell
     // which of the two operands will remain scalar and which will be reduced.
     // For minmax the chain will be the select instructions.
     Instruction *Chain = Phi;
     for (Instruction *R : ReductionOperations) {
       VPRecipeBase *WidenRecipe = RecipeBuilder.getRecipe(R);
       RecurrenceDescriptor::RecurrenceKind Kind = RdxDesc.getRecurrenceKind();
 
-      VPValue *ChainOp = Plan->getVPValue(Chain);
+      VPValue *ChainOp = Plan->getOrAddVPValue(Chain);
       unsigned FirstOpId;
       if (Kind == RecurrenceDescriptor::RK_IntegerMinMax ||
           Kind == RecurrenceDescriptor::RK_FloatMinMax) {
         assert(WidenRecipe->getVPRecipeID() == VPRecipeBase::VPWidenSelectSC &&
                "Expected to replace a VPWidenSelectSC");
         FirstOpId = 1;
       } else {
         assert(WidenRecipe->getVPRecipeID() == VPRecipeBase::VPWidenSC &&
                "Expected to replace a VPWidenSC");
         FirstOpId = 0;
       }
       unsigned VecOpId =
           R->getOperand(FirstOpId) == Chain ? FirstOpId + 1 : FirstOpId;
-      VPValue *VecOp = Plan->getVPValue(R->getOperand(VecOpId));
+      VPValue *VecOp = Plan->getOrAddVPValue(R->getOperand(VecOpId));
 
       bool UseReductionIntrinsic = TTI->useReductionIntrinsic(
           RdxDesc.getRecurrenceBinOp(Kind), RdxDesc.getRecurrenceType(),
           RdxDesc.getReductionFlags(Legal->hasFunNoNaNAttr()));
       auto *CondOp = CM.foldTailByMasking()
                          ? RecipeBuilder.createBlockInMask(R->getParent(), Plan)
                          : nullptr;
       VPReductionRecipe *RedRecipe = new VPReductionRecipe(
           &RdxDesc, R, ChainOp, VecOp, CondOp, Legal->hasFunNoNaNAttr(),
           UseReductionIntrinsic);
       WidenRecipe->getParent()->insert(RedRecipe, WidenRecipe->getIterator());
       WidenRecipe->eraseFromParent();
+      Plan->addOrReplaceVPValue(R, RedRecipe);
 
       if (Kind == RecurrenceDescriptor::RK_IntegerMinMax ||
           Kind == RecurrenceDescriptor::RK_FloatMinMax) {
         VPRecipeBase *CompareRecipe =
             RecipeBuilder.getRecipe(cast<Instruction>(R->getOperand(0)));
         assert(CompareRecipe->getVPRecipeID() == VPRecipeBase::VPWidenSC &&
                "Expected to replace a VPWidenSC");
         CompareRecipe->eraseFromParent();
       }
       Chain = R;
     }
   }
 }
 
+using namespace PatternMatch;
+
+template <typename LHS_t, typename RHS_t, unsigned Opcode>
+struct VPBinaryOp_match {
+  LHS_t L;
+  RHS_t R;
+
+  VPBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
+
+  template <typename OpTy> bool match(OpTy *V) {
+    const VPWidenRecipe *VW = dyn_cast<VPWidenRecipe>(V);
+    if (VW && VW->getOpcode() == Opcode)
+      return L.match(VW->getOperand(0)) && R.match(VW->getOperand(1));
+    // TODOD: VPInstruction?
+    return false;
+  }
+};
+template <typename LHS, typename RHS>
+inline VPBinaryOp_match<LHS, RHS, Instruction::Mul> vp_Mul(const LHS &L,
+                                                           const RHS &R) {
+  return VPBinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
+}
+template <typename LHS, typename RHS>
+inline VPBinaryOp_match<LHS, RHS, Instruction::LShr> vp_LShr(const LHS &L,
+                                                             const RHS &R) {
+  return VPBinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
+}
+
+template <typename LHS_t, unsigned Opcode> struct VPUnaryOp_match {
+  LHS_t L;
+
+  VPUnaryOp_match(const LHS_t &LHS) : L(LHS) {}
+
+  template <typename OpTy> bool match(OpTy *V) {
+    const VPWidenRecipe *VW = dyn_cast<VPWidenRecipe>(V);
+    if (VW && VW->getOpcode() == Opcode)
+      return L.match(VW->getOperand(0));
+    return false;
+  }
+};
+template <typename LHS>
+inline VPUnaryOp_match<LHS, Instruction::Trunc> vp_Trunc(const LHS &L) {
+  return VPUnaryOp_match<LHS, Instruction::Trunc>(L);
+}
+template <typename LHS>
+inline VPUnaryOp_match<LHS, Instruction::SExt> vp_SExt(const LHS &L) {
+  return VPUnaryOp_match<LHS, Instruction::SExt>(L);
+}
+template <typename LHS>
+inline VPUnaryOp_match<LHS, Instruction::ZExt> vp_ZExt(const LHS &L) {
+  return VPUnaryOp_match<LHS, Instruction::ZExt>(L);
+}
+
+inline bind_ty<VPValue> vp_Value(VPValue *&V) { return V; }
+inline bind_ty<const VPValue> vp_Value(const VPValue *&V) { return V; }
+
+struct VPspecific_intval {
+  APInt Val;
+
+  VPspecific_intval(APInt V) : Val(std::move(V)) {}
+
+  template <typename ITy> bool match(ITy *V) {
+    const auto *CI = dyn_cast<ConstantInt>(V->getUnderlyingValue());
+    return CI && APInt::isSameValue(CI->getValue(), Val);
+  }
+};
+inline VPspecific_intval vp_SpecificInt(uint64_t V) {
+  return VPspecific_intval(APInt(64, V));
+}
+
+// trunc(lsr(mul(ext, ext)), BW)) -> mulhs/mulhu
+static bool tryCombineToMulh(VPBasicBlock::reverse_iterator &It, VPlanPtr &Plan,
+                             VPRecipeBuilder &RecipeBuilder) {
+  VPWidenRecipe *RV = dyn_cast<VPWidenRecipe>(&*It);
+  if (!RV)
+    return false;
+
+  Type *Ty = RV->getType();
+  unsigned BW = Ty->getScalarSizeInBits();
+
+  VPValue *Mul;
+  // TODOD: One use checks?
+  if (!match(RV, vp_Trunc(vp_LShr(vp_Value(Mul), vp_SpecificInt(BW)))))
+    return false;
+
+  VPValue *A, *B;
+  unsigned Opcode = 0;
+  if (match(Mul, vp_Mul(vp_SExt(vp_Value(A)), vp_SExt(vp_Value(B)))))
+    Opcode = VPInstruction::Mulhs;
+  else if (match(Mul, vp_Mul(vp_ZExt(vp_Value(A)), vp_ZExt(vp_Value(B)))))
+    Opcode = VPInstruction::Mulhu;
+  else
+    return false;
+
+  unsigned MulBW = Mul->getType()->getScalarSizeInBits();
+  if (MulBW > BW * 2)
+    return false;
+
+  if (A->getType() != Ty || B->getType() != Ty) // TODOD: Generalize
+    return false;
+
+  auto *Mulh = new VPInstruction(Opcode, {A, B});
+  RV->getParent()->insert(Mulh, RV->getIterator());
+  RV->replaceAllUsesWith(Mulh);
+  RV->recursivelyDeleteUnusedRecipes();
+  It = Mulh->getReverseIterator();
+  return true;
+}
+
+bool LoopVectorizationPlanner::adjustVPlanForVectorPatterns(
+    VPlanPtr &Plan, VPRecipeBuilder &RecipeBuilder) {
+  bool Changed = false;
+  for (VPBlockBase *Block : depth_first(Plan->getEntry())) {
+    if (auto *BB = dyn_cast<VPBasicBlock>(Block)) {
+      for (VPBasicBlock::reverse_iterator It = BB->rbegin(), E = BB->rend();
+           It != E; ++It) {
+        if (true /*TODOD: TTI->hasVectorPattern(Mulh)*/)
+          Changed |= tryCombineToMulh(It, Plan, RecipeBuilder);
+      }
+    }
+  }
+
+  return Changed;
+}
+
 Value* LoopVectorizationPlanner::VPCallbackILV::
 getOrCreateVectorValues(Value *V, unsigned Part) {
       return ILV.getOrCreateVectorValue(V, Part);
 }
 
 Value *LoopVectorizationPlanner::VPCallbackILV::getOrCreateScalarValue(
     Value *V, const VPIteration &Instance) {
   return ILV.getOrCreateScalarValue(V, Instance);
if (Mask) {
     Mask->printAsOperand(O, SlotTracker);
   }
   for (unsigned i = 0; i < IG->getFactor(); ++i)
     if (Instruction *I = IG->getMember(i))
       O << "\\l\" +\n" << Indent << "\"  " << VPlanIngredient(I) << " " << i;
 }
 
 void VPWidenCallRecipe::execute(VPTransformState &State) {
-  State.ILV->widenCallInstruction(*getUnderlyingCall(), this, User, State);
+  State.ILV->widenCallInstruction(*getUnderlyingCall(), this, *this, State);
 }
 
 void VPWidenSelectRecipe::execute(VPTransformState &State) {
-  State.ILV->widenSelectInstruction(*getUnderlyingInstruction(), this, User,
+  State.ILV->widenSelectInstruction(*getUnderlyingInstruction(), this, *this,
                                     InvariantCond, State);
 }
 
 void VPWidenRecipe::execute(VPTransformState &State) {
-  State.ILV->widenInstruction(Ingredient, User, State);
+  State.ILV->widenInstruction(*getUnderlyingInstruction(), *this,
+                              State);
 }
 
 void VPWidenGEPRecipe::execute(VPTransformState &State) {
-  State.ILV->widenGEP(getUnderlyingInstruction(), this, User, State.UF,
+  State.ILV->widenGEP(getUnderlyingInstruction(), this, *this, State.UF,
                       State.VF, IsPtrLoopInvariant, IsIndexLoopInvariant,
                       State);
 }
 
 void VPWidenIntOrFpInductionRecipe::execute(VPTransformState &State) {
   assert(!State.Instance && "Int or FP induction being replicated.");
-  State.ILV->widenIntOrFpInduction(IV, Trunc);
+  State.ILV->widenIntOrFpInduction(getIV(), Trunc);
 }
 
 void VPWidenPHIRecipe::execute(VPTransformState &State) {
-  State.ILV->widenPHIInstruction(Phi, State.UF, State.VF);
+  State.ILV->widenPHIInstruction(getPhi(), State.UF, State.VF);
 }
 
 void VPBlendRecipe::execute(VPTransformState &State) {
-  State.ILV->setDebugLocFromInst(State.Builder, Phi);
+  State.ILV->setDebugLocFromInst(State.Builder, getPhi());
   // 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
   // optimizations will clean it up.
 
   unsigned NumIncoming = getNumIncomingValues();
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.ValueMap.setVectorValue(getPhi(), Part, Entry[Part]);
 }
 
 void VPInterleaveRecipe::execute(VPTransformState &State) {
   assert(!State.Instance && "Interleave group being replicated.");
   State.ILV->vectorizeInterleaveGroup(IG, getDefs(), State, getAddr(),
                                       getMask());
 }
 
 void VPReductionRecipe::execute(VPTransformState &State) {
   assert(!State.Instance && "Reduction being replicated.");
   for (unsigned Part = 0; Part < State.UF; ++Part) {
     RecurrenceDescriptor::RecurrenceKind Kind = RdxDesc->getRecurrenceKind();
-    Value *NewVecOp = State.get(VecOp, Part);
-    if (CondOp) {
-      Value *NewCond = State.get(CondOp, Part);
+    Value *NewVecOp = State.get(getVecOp(), Part);
+    if (getCondOp()) {
+      Value *NewCond = State.get(getCondOp(), Part);
       VectorType *VecTy = cast<VectorType>(NewVecOp->getType());
       Constant *Iden = RecurrenceDescriptor::getRecurrenceIdentity(
           Kind, RdxDesc->getMinMaxRecurrenceKind(), VecTy->getElementType());
       Constant *IdenVec =
           ConstantVector::getSplat(VecTy->getElementCount(), Iden);
       Value *Select = State.Builder.CreateSelect(NewCond, NewVecOp, IdenVec);
       NewVecOp = Select;
     }
     Value *NewRed = createTargetReduction(State.Builder, *RdxDesc, NewVecOp,
                                           UseReductionIntrinsic, NoNaN);
-    Value *PrevInChain = State.get(ChainOp, Part);
+    Value *PrevInChain = State.get(getChainOp(), Part);
     Value *NextInChain;
     if (Kind == RecurrenceDescriptor::RK_IntegerMinMax ||
         Kind == RecurrenceDescriptor::RK_FloatMinMax) {
       NextInChain =
           createMinMaxOp(State.Builder, RdxDesc->getMinMaxRecurrenceKind(),
                          NewRed, PrevInChain);
     } else {
       NextInChain = State.Builder.CreateBinOp(
-          (Instruction::BinaryOps)I->getOpcode(), NewRed, PrevInChain);
+          (Instruction::BinaryOps)cast<Instruction>(getUnderlyingValue())
+              ->getOpcode(),
+          NewRed, PrevInChain);
     }
-    State.ValueMap.setVectorValue(I, Part, NextInChain);
+    State.ValueMap.setVectorValue(getUnderlyingValue(), Part, NextInChain);
   }
 }
 
 void VPReplicateRecipe::execute(VPTransformState &State) {
   if (State.Instance) { // Generate a single instance.
-    State.ILV->scalarizeInstruction(Ingredient, User, *State.Instance,
+
+    State.ILV->scalarizeInstruction(getIngredient(), *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(getIngredient()->getType(), State.VF));
+        State.ValueMap.setVectorValue(getIngredient(), State.Instance->Part,
+                                      Undef);
       }
-      State.ILV->packScalarIntoVectorValue(Ingredient, *State.Instance);
+      State.ILV->packScalarIntoVectorValue(getIngredient(), *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, User, {Part, Lane},
+      State.ILV->scalarizeInstruction(getIngredient(), *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 VPBranchOnMaskRecipe::execute(VPTransformState &State) {
   auto *CondBr = BranchInst::Create(State.CFG.PrevBB, nullptr, ConditionBit);
   CondBr->setSuccessor(0, nullptr);
   ReplaceInstWithInst(CurrentTerminator, CondBr);
 }
 
 void VPPredInstPHIRecipe::execute(VPTransformState &State) {
   assert(State.Instance && "Predicated instruction PHI works per instance.");
   Instruction *ScalarPredInst = cast<Instruction>(
-      State.ValueMap.getScalarValue(PredInst, *State.Instance));
+      State.ValueMap.getScalarValue(getPredInst(), *State.Instance));
   BasicBlock *PredicatedBB = ScalarPredInst->getParent();
   BasicBlock *PredicatingBB = PredicatedBB->getSinglePredecessor();
   assert(PredicatingBB && "Predicated block has no single predecessor.");
 
   // 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;
-  if (State.ValueMap.hasVectorValue(PredInst, Part)) {
-    Value *VectorValue = State.ValueMap.getVectorValue(PredInst, Part);
+  if (State.ValueMap.hasVectorValue(getPredInst(), Part)) {
+    Value *VectorValue = State.ValueMap.getVectorValue(getPredInst(), 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.
+    State.ValueMap.resetVectorValue(getPredInst(), Part, VPhi); // Update cache.
   } else {
-    Type *PredInstType = PredInst->getType();
+    Type *PredInstType = getPredInst()->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.ValueMap.resetScalarValue(getPredInst(), *State.Instance, Phi);
   }
 }
 
 void VPWidenMemoryInstructionRecipe::execute(VPTransformState &State) {
   Instruction *Instr = getUnderlyingInstruction();
   VPValue *StoredValue = isa<StoreInst>(Instr) ? getStoredValue() : nullptr;
   State.ILV->vectorizeMemoryInstruction(Instr, State,
                                         StoredValue ? nullptr : this, getAddr(),

llvm/lib/Transforms/Vectorize/VPlan.h

using VPRecipeTy = enum {
     VPWidenPHISC,
     VPWidenSC,
     VPWidenSelectSC
   };
 
   VPRecipeBase(const unsigned char SC) : SubclassID(SC) {}
   virtual ~VPRecipeBase() = default;
 
-  /// \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.
   unsigned getVPRecipeID() const { return SubclassID; }
 
   /// \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();
+
+  void recursivelyDeleteUnusedRecipes();
+
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() >= VPValue::VPInstructionSC;
+  }
 };
 
 /// 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 VPValue, public VPRecipeBase {
   friend class VPlanSlp;
 
 public:
   /// VPlan opcodes, extending LLVM IR with idiomatics instructions.
   enum {
     Not = Instruction::OtherOpsEnd + 1,
     ICmpULE,
     SLPLoad,
     SLPStore,
     ActiveLaneMask,
+    Mulhs,
+    Mulhu,
   };
 
 private:
   typedef unsigned char OpcodeTy;
   OpcodeTy Opcode;
 
   /// Utility method serving execute(): generates a single instance of the
   /// modeled instruction.
public:
 
   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;
   }
-
-  VPInstruction *clone() const {
-    SmallVector<VPValue *, 2> Operands(operands());
-    return new VPInstruction(Opcode, Operands);
-  }
-
-  /// Method to support type inquiry through isa, cast, and dyn_cast.
-  static inline bool classof(const VPRecipeBase *R) {
-    return R->getVPRecipeID() == VPRecipeBase::VPInstructionSC;
+  static inline bool classof(const VPRecipeBase *V) {
+    return V->getVPRecipeID() == VPRecipeBase::VPInstructionSC;
   }
 
   unsigned getOpcode() const { return Opcode; }
 
   /// Generate the instruction.
   /// TODO: We currently execute only per-part unless a specific instance is
   /// provided.
   void execute(VPTransformState &State) override;
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 {
-  /// Hold the instruction to be widened.
-  Instruction &Ingredient;
-
-  /// Hold VPValues for the operands of the ingredient.
-  VPUser User;
-
+class VPWidenRecipe : public VPRecipeBase, public VPValue, public VPUser {
 public:
   template <typename IterT>
   VPWidenRecipe(Instruction &I, iterator_range<IterT> Operands)
-      : VPRecipeBase(VPWidenSC), Ingredient(I), User(Operands) {}
+      : VPRecipeBase(VPRecipeBase::VPWidenSC), VPValue(VPValue::VPWidenSC, &I),
+        VPUser(Operands) {}
 
   ~VPWidenRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() == VPValue::VPWidenSC;
+  }
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == 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;
+
+  Instruction *getUnderlyingInstruction() {
+    return cast<Instruction>(getUnderlyingValue());
+  }
+  const Instruction *getUnderlyingInstruction() const {
+    return cast<Instruction>(getUnderlyingValue());
+  }
+  unsigned getOpcode() const { return getUnderlyingInstruction()->getOpcode(); }
 };
 
 /// A recipe for widening Call instructions.
-class VPWidenCallRecipe : public VPRecipeBase, public VPValue {
-  /// Hold VPValues for the arguments of the call.
-  VPUser User;
-
+class VPWidenCallRecipe : public VPRecipeBase, public VPValue, public VPUser {
 public:
   template <typename IterT>
   VPWidenCallRecipe(CallInst &I, iterator_range<IterT> CallArguments)
-      : VPRecipeBase(VPWidenCallSC), VPValue(VPValue::VPVWidenCallSC, &I),
-        User(CallArguments) {}
+      : VPRecipeBase(VPRecipeBase::VPWidenCallSC),
+        VPValue(VPValue::VPWidenCallSC, &I), VPUser(CallArguments) {}
 
   ~VPWidenCallRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() == VPValue::VPWidenCallSC;
+  }
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == 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 VPValue {
+class VPWidenSelectRecipe : public VPRecipeBase, public VPValue, public VPUser {
 private:
-  /// Hold VPValues for the operands of the select.
-  VPUser User;
-
   /// Is the condition of the select loop invariant?
   bool InvariantCond;
 
 public:
   template <typename IterT>
   VPWidenSelectRecipe(SelectInst &I, iterator_range<IterT> Operands,
                       bool InvariantCond)
-      : VPRecipeBase(VPWidenSelectSC), VPValue(VPValue::VPVWidenSelectSC, &I),
-        User(Operands), InvariantCond(InvariantCond) {}
+      : VPRecipeBase(VPRecipeBase::VPWidenSelectSC),
+        VPValue(VPValue::VPWidenSelectSC, &I), VPUser(Operands),
+        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() == VPValue::VPWidenSelectSC;
+  }
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == 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 VPValue {
-  /// Hold VPValues for the base and indices of the GEP.
-  VPUser User;
-
+class VPWidenGEPRecipe : public VPRecipeBase, public VPValue, public VPUser {
   bool IsPtrLoopInvariant;
   SmallBitVector IsIndexLoopInvariant;
 
 public:
   template <typename IterT>
   VPWidenGEPRecipe(GetElementPtrInst *GEP, iterator_range<IterT> Operands,
                    Loop *OrigLoop)
-      : VPRecipeBase(VPWidenGEPSC), VPValue(VPValue::VPVWidenGEPSC, GEP),
-        User(Operands), IsIndexLoopInvariant(GEP->getNumIndices(), false) {
+      : VPRecipeBase(VPRecipeBase::VPWidenGEPSC),
+        VPValue(VPValue::VPWidenGEPSC, GEP), VPUser(Operands),
+        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;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() == VPValue::VPWidenGEPSC;
+  }
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == VPRecipeBase::VPWidenGEPSC;
   }
 
   /// Generate the gep nodes.
   void execute(VPTransformState &State) override;
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 
   GetElementPtrInst *getUnderlyingInstruction() {
     return cast<GetElementPtrInst>(getUnderlyingValue());
   }
   const GetElementPtrInst *getUnderlyingInstruction() const {
     return cast<GetElementPtrInst>(getUnderlyingValue());
   }
 };
 
 /// A recipe for handling phi nodes of integer and floating-point inductions,
 /// producing their vector and scalar values.
-class VPWidenIntOrFpInductionRecipe : public VPRecipeBase {
-  PHINode *IV;
+class VPWidenIntOrFpInductionRecipe : public VPRecipeBase, public VPValue {
   TruncInst *Trunc;
 
 public:
   VPWidenIntOrFpInductionRecipe(PHINode *IV, TruncInst *Trunc = nullptr)
-      : VPRecipeBase(VPWidenIntOrFpInductionSC), IV(IV), Trunc(Trunc) {}
+      : VPRecipeBase(VPRecipeBase::VPWidenIntOrFpInductionSC),
+        VPValue(VPValue::VPWidenIntOrFpInductionSC, 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() == VPValue::VPWidenIntOrFpInductionSC;
+  }
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == 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;
+
+  PHINode *getIV() { return cast<PHINode>(getUnderlyingValue()); }
+  const PHINode *getIV() const { return cast<PHINode>(getUnderlyingValue()); }
 };
 
 /// A recipe for handling all phi nodes except for integer and FP inductions.
-class VPWidenPHIRecipe : public VPRecipeBase {
-  PHINode *Phi;
-
+class VPWidenPHIRecipe : public VPRecipeBase, public VPValue {
 public:
-  VPWidenPHIRecipe(PHINode *Phi) : VPRecipeBase(VPWidenPHISC), Phi(Phi) {}
+  VPWidenPHIRecipe(PHINode *Phi)
+      : VPRecipeBase(VPRecipeBase::VPWidenPHISC),
+        VPValue(VPValue::VPWidenPHISC, 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() == VPValue::VPWidenPHISC;
+  }
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == 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;
+
+  PHINode *getPhi() { return cast<PHINode>(getUnderlyingValue()); }
+  const PHINode *getPhi() const { return cast<PHINode>(getUnderlyingValue()); }
 };
 
 /// A recipe for vectorizing a phi-node as a sequence of mask-based select
 /// instructions.
-class VPBlendRecipe : public VPRecipeBase {
-  PHINode *Phi;
-
-  /// 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.
-  VPUser User;
-
+class VPBlendRecipe : public VPRecipeBase, public VPValue, public VPUser {
 public:
   VPBlendRecipe(PHINode *Phi, ArrayRef<VPValue *> Operands)
-      : VPRecipeBase(VPBlendSC), Phi(Phi), User(Operands) {
+      : VPRecipeBase(VPRecipeBase::VPBlendSC), VPValue(VPValue::VPBlendSC, Phi),
+        VPUser(Operands) {
     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) {
+    return V->getVPValueID() == VPValue::VPBlendSC;
+  }
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == VPRecipeBase::VPBlendSC;
   }
 
   /// Return the number of incoming values, taking into account that a single
   /// incoming value has no mask.
-  unsigned getNumIncomingValues() const {
-    return (User.getNumOperands() + 1) / 2;
-  }
+  unsigned getNumIncomingValues() const { return (getNumOperands() + 1) / 2; }
 
   /// Return incoming value number \p Idx.
-  VPValue *getIncomingValue(unsigned Idx) const {
-    return User.getOperand(Idx * 2);
-  }
+  VPValue *getIncomingValue(unsigned Idx) const { return getOperand(Idx * 2); }
 
   /// Return mask number \p Idx.
-  VPValue *getMask(unsigned Idx) const { return User.getOperand(Idx * 2 + 1); }
+  VPValue *getMask(unsigned Idx) const { return getOperand(Idx * 2 + 1); }
+
+  PHINode *getPhi() { return cast<PHINode>(getUnderlyingValue()); }
+  const PHINode *getPhi() const { return cast<PHINode>(getUnderlyingValue()); }
 
   /// 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;
 };
 
 /// 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 VPValue {
+class VPInterleaveRecipe : public VPRecipeBase, public VPValue, public VPUser {
   const InterleaveGroup<Instruction> *IG;
-  VPUser User;
   SmallVector<VPMultiValue *, 4> Defs;
 
 public:
   VPInterleaveRecipe(const InterleaveGroup<Instruction> *IG, VPValue *Addr,
                      VPValue *Mask)
-      : VPRecipeBase(VPInterleaveSC), VPValue(VPValue::VPVInterleaveSC), IG(IG),
-        User({Addr}) {
+      : VPRecipeBase(VPRecipeBase::VPInterleaveSC),
+        VPValue(VPValue::VPInterleaveSC), VPUser({Addr}), IG(IG) {
     if (Mask)
-      User.addOperand(Mask);
+      addOperand(Mask);
     for (unsigned i = 0; i < IG->getNumMembers(); i++)
       Defs.push_back(new VPMultiValue(this));
   }
   ~VPInterleaveRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() == VPValue::VPInterleaveSC;
+  }
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == VPRecipeBase::VPInterleaveSC;
   }
-  static inline bool classof(const VPValue *V) {
-    return V->getVPValueID() == VPValue::VPVInterleaveSC;
-  }
 
   /// Return the address accessed by this recipe.
   VPValue *getAddr() const {
-    return User.getOperand(0); // Address is the 1st, mandatory operand.
+    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, currently 2nd operand.
-    return User.getNumOperands() == 2 ? User.getOperand(1) : nullptr;
+    return getNumOperands() == 2 ? getOperand(1) : nullptr;
   }
 
   /// Generate the wide load or store, and shuffles.
   void execute(VPTransformState &State) override;
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 
   const InterleaveGroup<Instruction> *getInterleaveGroup() { return IG; }
 
   VPMultiValue *getResult(unsigned Idx) { return Defs[Idx]; }
   ArrayRef<VPMultiValue *> getDefs() { return Defs; }
 };
 
-/*template <> struct simplify_type<VPMultiValue> {*/
-// using SimpleType = VPValue *;
-
-// static SimpleType getSimplifiedValue(VPMultiValue &Val) {
-// return Val.getProducer();
-//}
-//};
-
-// template <> struct simplify_type<VPMultiValue *> {
-// using SimpleType = VPValue *;
-
-// static SimpleType getSimplifiedValue(VPMultiValue *&Val) {
-// return Val->getProducer();
-//}
-//};
-
 /// A recipe to represent inloop reduction operations, performing a reduction on
 /// a vector operand into a scalar value, and adding the result to a chain.
-class VPReductionRecipe : public VPRecipeBase {
+class VPReductionRecipe : public VPRecipeBase, public VPValue, public VPUser {
   /// The recurrence decriptor for the reduction in question.
   RecurrenceDescriptor *RdxDesc;
-  /// The original instruction being converted to a reduction.
-  Instruction *I;
-  /// The VPValue of the vector value to be reduced.
-  VPValue *VecOp;
-  /// The VPValue of the scalar Chain being accumulated.
-  VPValue *ChainOp;
-  /// The VPValue of the condition for the block.
-  VPValue *CondOp;
   /// Fast math flags to use for the resulting reduction operation.
   bool NoNaN;
   /// Flag for whether to use reduction intrinsics vs shuffle expansions.
   bool UseReductionIntrinsic;
 
 public:
   VPReductionRecipe(RecurrenceDescriptor *R, Instruction *I, VPValue *ChainOp,
                     VPValue *VecOp, VPValue *CondOp, bool NoNaN,
                     bool UseReductionIntrinsic)
-      : VPRecipeBase(VPReductionSC), RdxDesc(R), I(I), VecOp(VecOp),
-        ChainOp(ChainOp), CondOp(CondOp), NoNaN(NoNaN),
-        UseReductionIntrinsic(UseReductionIntrinsic) {}
+      : VPRecipeBase(VPRecipeBase::VPReductionSC),
+        VPValue(VPValue::VPReductionSC, I), VPUser({ChainOp, VecOp}),
+        RdxDesc(R), NoNaN(NoNaN), UseReductionIntrinsic(UseReductionIntrinsic) {
+    if (CondOp)
+      addOperand(CondOp);
+  }
 
   ~VPReductionRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() == VPValue::VPReductionSC;
+  }
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == VPRecipeBase::VPReductionSC;
   }
 
+  VPValue *getChainOp() const { return getOperand(0); }
+  VPValue *getVecOp() const { return getOperand(1); }
+  VPValue *getCondOp() const {
+    return getNumOperands() > 2 ? getOperand(2) : nullptr;
+  }
+
   /// 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 {
-  /// The instruction being replicated.
-  Instruction *Ingredient;
-
-  /// Hold VPValues for the operands of the ingredient.
-  VPUser User;
-
+class VPReplicateRecipe : public VPRecipeBase, public VPValue, public VPUser {
   /// 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), Ingredient(I), User(Operands),
+      : VPRecipeBase(VPRecipeBase::VPReplicateSC),
+        VPValue(VPValue::VPReplicateSC, I), VPUser(Operands),
         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 VPValue *V) {
+    return V->getVPValueID() == VPValue::VPReplicateSC;
+  }
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == VPRecipeBase::VPReplicateSC;
   }
 
   /// 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;
 
+  Instruction *getIngredient() {
+    return cast<Instruction>(getUnderlyingValue());
+  }
+  const Instruction *getIngredient() const {
+    return cast<Instruction>(getUnderlyingValue());
+  }
+
   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 {
-  VPUser User;
-
-public:
-  VPBranchOnMaskRecipe(VPValue *BlockInMask) : VPRecipeBase(VPBranchOnMaskSC) {
+class VPBranchOnMaskRecipe : public VPRecipeBase,
+                             public VPValue,
+                             public VPUser {
+public:
+  VPBranchOnMaskRecipe(VPValue *BlockInMask)
+      : VPRecipeBase(VPRecipeBase::VPBranchOnMaskSC),
+        VPValue(VPValue::VPBranchOnMaskSC) {
     if (BlockInMask) // nullptr means all-one mask.
-      User.addOperand(BlockInMask);
+      addOperand(BlockInMask);
   }
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() == VPValue::VPBranchOnMaskSC;
+  }
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == VPRecipeBase::VPBranchOnMaskSC;
   }
 
   /// Generate the extraction of the appropriate bit from the block mask and the
   /// conditional branch.
   void execute(VPTransformState &State) override;
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override {
     O << " +\n" << Indent << "\"BRANCH-ON-MASK ";
     if (VPValue *Mask = getMask())
       Mask->print(O, SlotTracker);
     else
       O << " All-One";
     O << "\\l\"";
   }
 
   /// Return the mask used by this recipe. Note that a full mask is represented
   /// by a nullptr.
   VPValue *getMask() const {
-    assert(User.getNumOperands() <= 1 && "should have either 0 or 1 operands");
+    assert(getNumOperands() <= 1 && "should have either 0 or 1 operands");
     // Mask is optional.
-    return User.getNumOperands() == 1 ? User.getOperand(0) : nullptr;
+    return getNumOperands() == 1 ? getOperand(0) : nullptr;
   }
 };
 
 /// 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 {
-  Instruction *PredInst;
-
+class VPPredInstPHIRecipe : public VPRecipeBase, public VPValue {
 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(VPRecipeBase::VPPredInstPHISC),
+        VPValue(VPValue::VPPredInstPHISC, 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() == VPValue::VPPredInstPHISC;
+  }
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == 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;
+
+  Instruction *getPredInst() { return cast<Instruction>(getUnderlyingValue()); }
+  const Instruction *getPredInst() const {
+    return cast<Instruction>(getUnderlyingValue());
+  }
 };
 
 /// 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 VPValue {
-  VPUser User;
-
+class VPWidenMemoryInstructionRecipe : public VPRecipeBase,
+                                       public VPValue,
+                                       public VPUser {
   void setMask(VPValue *Mask) {
     if (!Mask)
       return;
-    User.addOperand(Mask);
+    addOperand(Mask);
   }
 
   bool isMasked() const {
     return (isa<LoadInst>(getUnderlyingInstruction()) &&
-            User.getNumOperands() == 2) ||
+            getNumOperands() == 2) ||
            (isa<StoreInst>(getUnderlyingInstruction()) &&
-            User.getNumOperands() == 3);
+            getNumOperands() == 3);
   }
 
 public:
   VPWidenMemoryInstructionRecipe(LoadInst &Load, VPValue *Addr, VPValue *Mask)
-      : VPRecipeBase(VPWidenMemoryInstructionSC),
-        VPValue(VPValue::VPMemoryInstructionSC, &Load), User({Addr}) {
+      : VPRecipeBase(VPRecipeBase::VPWidenMemoryInstructionSC),
+        VPValue(VPValue::VPWidenMemoryInstructionSC, &Load), VPUser({Addr}) {
     setMask(Mask);
   }
 
   VPWidenMemoryInstructionRecipe(StoreInst &Store, VPValue *Addr,
                                  VPValue *StoredValue, VPValue *Mask)
-      : VPRecipeBase(VPWidenMemoryInstructionSC),
-        VPValue(VPValue::VPMemoryInstructionSC, &Store),
-        User({Addr, StoredValue}) {
+      : VPRecipeBase(VPRecipeBase::VPWidenMemoryInstructionSC),
+        VPValue(VPValue::VPWidenMemoryInstructionSC, &Store),
+        VPUser({Addr, StoredValue}) {
     setMask(Mask);
   }
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() == VPValue::VPWidenMemoryInstructionSC;
+  }
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == VPRecipeBase::VPWidenMemoryInstructionSC;
   }
 
   /// Return the address accessed by this recipe.
   VPValue *getAddr() const {
-    return User.getOperand(0); // Address is the 1st, mandatory operand.
+    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() ? User.getOperand(User.getNumOperands() - 1) : nullptr;
+    return isMasked() ? getOperand(getNumOperands() - 1) : nullptr;
   }
 
   /// Return the address accessed by this recipe.
   VPValue *getStoredValue() const {
     assert(isa<StoreInst>(getUnderlyingInstruction()) &&
            "Stored value only available for store instructions");
-    return User.getOperand(1); // Stored value is the 2nd, mandatory operand.
+    return getOperand(1); // Stored value is the 2nd, mandatory operand.
   }
 
   /// Generate the wide load/store.
   void execute(VPTransformState &State) override;
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 
   Instruction *getUnderlyingInstruction() {
     return cast<Instruction>(getUnderlyingValue());
   }
   const Instruction *getUnderlyingInstruction() const {
     return cast<Instruction>(getUnderlyingValue());
   }
 };
 
 /// 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;
-
+class VPWidenCanonicalIVRecipe : public VPRecipeBase, public VPValue {
 public:
-  VPWidenCanonicalIVRecipe() : VPRecipeBase(VPWidenCanonicalIVSC) {}
+  VPWidenCanonicalIVRecipe()
+      : VPRecipeBase(VPRecipeBase::VPWidenCanonicalIVSC),
+        VPValue(VPValue::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.
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() == VPValue::VPWidenCanonicalIVSC;
+  }
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == VPRecipeBase::VPWidenCanonicalIVSC;
   }
 
   /// Generate a canonical vector induction variable of the vector loop, with
   /// start = {<Part*VF, Part*VF+1, ..., Part*VF+VF-1> for 0 <= Part < UF}, and
   /// step = <VF*UF, VF*UF, ..., VF*UF>.
   void execute(VPTransformState &State) override;
public:
   }
 
   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 get or add the VPValue of a null Value");
+    if (!Value2VPValue.count(V)) {
+      addVPValue(V, VPV);
+      return;
+    }
+    VPValue *OldVPV = Value2VPValue[V];
+    Value2VPValue[V] = VPV;
+    auto It = find(VPValuesToFree, OldVPV);
+    if (It != VPValuesToFree.end()) {
+      delete OldVPV;
+      VPValuesToFree.erase(It);
+    }
+  }
+
   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");

llvm/lib/Transforms/Vectorize/VPlan.cpp

void VPRecipeBase::removeFromParent() {
   Parent = nullptr;
 }
 
 iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() {
   assert(getParent() && "Recipe not in any VPBasicBlock");
   return getParent()->getRecipeList().erase(getIterator());
 }
 
+/// Obviously needs to change
+static VPUser *getVPUser(VPRecipeBase *Base) {
+  switch (Base->getVPRecipeID()) {
+  case VPRecipeBase::VPBlendSC:
+  case VPRecipeBase::VPBranchOnMaskSC:
+  case VPRecipeBase::VPInstructionSC:
+  case VPRecipeBase::VPInterleaveSC:
+  case VPRecipeBase::VPPredInstPHISC:
+  case VPRecipeBase::VPReductionSC:
+  case VPRecipeBase::VPReplicateSC:
+  case VPRecipeBase::VPWidenCallSC:
+  case VPRecipeBase::VPWidenCanonicalIVSC:
+  case VPRecipeBase::VPWidenGEPSC:
+  case VPRecipeBase::VPWidenIntOrFpInductionSC:
+  case VPRecipeBase::VPWidenMemoryInstructionSC:
+  case VPRecipeBase::VPWidenPHISC:
+  case VPRecipeBase::VPWidenSC:
+  case VPRecipeBase::VPWidenSelectSC:
+    return (VPUser *)Base; // Not quite right
+  }
+  return nullptr;
+}
+
+void VPRecipeBase::recursivelyDeleteUnusedRecipes() {
+  // TODOD: This doesn't work yet...
+  VPUser *ThisUser = getVPUser(this);
+  if (ThisUser &&
+      cast<VPValue>(this)->getNumUsers() == 0 /* && isSafeToRemove()*/) {
+    for (auto *Op : ThisUser->operands()) {
+      Op->removeUser(ThisUser);
+      if (VPRecipeBase *R = dyn_cast<VPRecipeBase>(Op))
+        R->recursivelyDeleteUnusedRecipes();
+    }
+    ThisUser->clearOperands();
+    eraseFromParent();
+  }
+}
+
 void VPRecipeBase::moveAfter(VPRecipeBase *InsertPos) {
   removeFromParent();
   insertAfter(InsertPos);
 }
 
 void VPInstruction::generateInstruction(VPTransformState &State,
                                         unsigned Part) {
   IRBuilder<> &Builder = State.Builder;
case VPInstruction::ActiveLaneMask: {
     auto *Int1Ty = Type::getInt1Ty(Builder.getContext());
     auto *PredTy = FixedVectorType::get(Int1Ty, State.VF.getKnownMinValue());
     Instruction *Call = Builder.CreateIntrinsic(
         Intrinsic::get_active_lane_mask, {PredTy, ScalarTC->getType()},
         {VIVElem0, ScalarTC}, nullptr, "active.lane.mask");
     State.set(this, Call, Part);
     break;
   }
+  case VPInstruction::Mulhs:
+  case VPInstruction::Mulhu: {
+    // TODOD: Create a Mulh instrinsic instead?
+    Value *A = State.get(getOperand(0), Part);
+    Value *B = State.get(getOperand(1), Part);
+
+    auto Ty = cast<VectorType>(A->getType());
+    unsigned BW = Ty->getScalarSizeInBits();
+    auto *WidenTy = VectorType::getExtendedElementVectorType(Ty);
+
+    auto *ExtA = getOpcode() == VPInstruction::Mulhs
+                     ? Builder.CreateSExt(A, WidenTy)
+                     : Builder.CreateZExt(A, WidenTy);
+    auto *ExtB = getOpcode() == VPInstruction::Mulhs
+                     ? Builder.CreateSExt(B, WidenTy)
+                     : Builder.CreateZExt(B, WidenTy);
+    auto *Mul = Builder.CreateMul(ExtA, ExtB);
+    auto *Shift = Builder.CreateLShr(
+        Mul, ConstantDataVector::getSplat(
+                 State.VF.getKnownMinValue(),
+                 ConstantInt::get(WidenTy->getElementType(), BW)));
+    auto *Trunc = Builder.CreateTrunc(Shift, Ty);
+
+    State.set(this, Trunc, Part);
+    break;
+  }
   default:
     llvm_unreachable("Unsupported opcode for instruction");
   }
 }
 
 void VPInstruction::execute(VPTransformState &State) {
   assert(!State.Instance && "VPInstruction executing an Instance");
   for (unsigned Part = 0; Part < State.UF; ++Part)
case VPInstruction::SLPLoad:
     O << "combined load";
     break;
   case VPInstruction::SLPStore:
     O << "combined store";
     break;
   case VPInstruction::ActiveLaneMask:
     O << "active lane mask";
     break;
+  case VPInstruction::Mulhs:
+    O << "mulhs";
+    break;
+  case VPInstruction::Mulhu:
+    O << "mulhu";
+    break;
 
   default:
     O << Instruction::getOpcodeName(getOpcode());
   }
 
   for (const VPValue *Operand : operands()) {
     O << " ";
     Operand->printAsOperand(O, SlotTracker);
void VPWidenCallRecipe::print(raw_ostream &O, const Twine &Indent,
   O << "\"WIDEN-CALL " << VPlanIngredient(getUnderlyingCall());
 }
 
 void VPWidenSelectRecipe::print(raw_ostream &O, const Twine &Indent,
                                 VPSlotTracker &SlotTracker) const {
   O << "\"WIDEN ";
   printAsOperand(O, SlotTracker);
   O << " = select ";
-  User.getOperand(0)->printAsOperand(O, SlotTracker);
+  getOperand(0)->printAsOperand(O, SlotTracker);
   O << ", ";
-  User.getOperand(1)->printAsOperand(O, SlotTracker);
+  getOperand(1)->printAsOperand(O, SlotTracker);
   O << ", ";
-  User.getOperand(2)->printAsOperand(O, SlotTracker);
+  getOperand(2)->printAsOperand(O, SlotTracker);
   O << (InvariantCond ? " (condition is loop invariant)" : "");
 }
 
 void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent,
                           VPSlotTracker &SlotTracker) const {
   O << "\"WIDEN\\l\"";
-  O << "\"  " << VPlanIngredient(&Ingredient);
+  O << "\"  " << VPlanIngredient(getUnderlyingInstruction());
 }
 
 void VPWidenIntOrFpInductionRecipe::print(raw_ostream &O, const Twine &Indent,
                                           VPSlotTracker &SlotTracker) const {
   O << "\"WIDEN-INDUCTION";
   if (Trunc) {
     O << "\\l\"";
-    O << " +\n" << Indent << "\"  " << VPlanIngredient(IV) << "\\l\"";
+    O << " +\n" << Indent << "\"  " << VPlanIngredient(getIV()) << "\\l\"";
     O << " +\n" << Indent << "\"  " << VPlanIngredient(Trunc);
   } else
-    O << " " << VPlanIngredient(IV);
+    O << " " << VPlanIngredient(getIV());
 }
 
 void VPWidenGEPRecipe::print(raw_ostream &O, const Twine &Indent,
                              VPSlotTracker &SlotTracker) const {
   O << "\"WIDEN-GEP ";
   O << (IsPtrLoopInvariant ? "Inv" : "Var");
   size_t IndicesNumber = IsIndexLoopInvariant.size();
   for (size_t I = 0; I < IndicesNumber; ++I)
     O << "[" << (IsIndexLoopInvariant[I] ? "Inv" : "Var") << "]";
   O << "\\l\"";
   O << " +\n"
     << Indent << "\"  " << VPlanIngredient(getUnderlyingInstruction());
 }
 
 void VPWidenPHIRecipe::print(raw_ostream &O, const Twine &Indent,
                              VPSlotTracker &SlotTracker) const {
-  O << "\"WIDEN-PHI " << VPlanIngredient(Phi);
+  O << "\"WIDEN-PHI " << VPlanIngredient(getPhi());
 }
 
 void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent,
                           VPSlotTracker &SlotTracker) const {
   O << "\"BLEND ";
-  Phi->printAsOperand(O, false);
+  getPhi()->printAsOperand(O, false);
   O << " =";
   if (getNumIncomingValues() == 1) {
     // Not a User of any mask: not really blending, this is a
     // single-predecessor phi.
     O << " ";
     getIncomingValue(0)->printAsOperand(O, SlotTracker);
   } else {
     for (unsigned I = 0, E = getNumIncomingValues(); I < E; ++I) {
       O << " ";
       getIncomingValue(I)->printAsOperand(O, SlotTracker);
       O << "/";
       getMask(I)->printAsOperand(O, SlotTracker);
     }
   }
 }
 
 void VPReductionRecipe::print(raw_ostream &O, const Twine &Indent,
                               VPSlotTracker &SlotTracker) const {
-  O << "\"REDUCE of" << *I << " as ";
-  ChainOp->printAsOperand(O, SlotTracker);
+  O << "\"REDUCE of" << *getUnderlyingValue() << " as ";
+  getChainOp()->printAsOperand(O, SlotTracker);
   O << " + reduce(";
-  VecOp->printAsOperand(O, SlotTracker);
-  if (CondOp) {
+  getVecOp()->printAsOperand(O, SlotTracker);
+  if (getCondOp()) {
     O << ", ";
-    CondOp->printAsOperand(O, SlotTracker);
+    getCondOp()->printAsOperand(O, SlotTracker);
   }
   O << ")";
 }
 
 void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent,
                               VPSlotTracker &SlotTracker) const {
   O << "\"" << (IsUniform ? "CLONE " : "REPLICATE ")
-    << VPlanIngredient(Ingredient);
+    << VPlanIngredient(getIngredient());
   if (AlsoPack)
     O << " (S->V)";
 }
 
 void VPPredInstPHIRecipe::print(raw_ostream &O, const Twine &Indent,
                                 VPSlotTracker &SlotTracker) const {
-  O << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(PredInst);
+  O << "\"PHI-PREDICATED-INSTRUCTION " << VPlanIngredient(getPredInst());
 }
 
 void VPWidenMemoryInstructionRecipe::print(raw_ostream &O, const Twine &Indent,
                                            VPSlotTracker &SlotTracker) const {
   O << "\"WIDEN " << VPlanIngredient(getUnderlyingInstruction());
   O << ", ";
   getAddr()->printAsOperand(O, SlotTracker);
   VPValue *Mask = getMask();
for (unsigned Part = 0, UF = State.UF; Part < UF; ++Part) {
     for (unsigned Lane = 0; Lane < VF.getKnownMinValue(); ++Lane)
       Indices.push_back(
           ConstantInt::get(STy, Part * VF.getKnownMinValue() + Lane));
     // If VF == 1, there is only one iteration in the loop above, thus the
     // element pushed back into Indices is ConstantInt::get(STy, Part)
     Constant *VStep = VF == 1 ? Indices.back() : ConstantVector::get(Indices);
     // Add the consecutive indices to the vector value.
     Value *CanonicalVectorIV = Builder.CreateAdd(VStart, VStep, "vec.iv");
-    State.set(getVPValue(), CanonicalVectorIV, Part);
+    State.set(this, CanonicalVectorIV, Part);
   }
 }
 
 void VPWidenCanonicalIVRecipe::print(raw_ostream &O, const Twine &Indent,
                                      VPSlotTracker &SlotTracker) const {
   O << "\"EMIT ";
-  getVPValue()->printAsOperand(O, SlotTracker);
+  printAsOperand(O, SlotTracker);
   O << " = WIDEN-CANONICAL-INDUCTION";
 }
 
 template void DomTreeBuilder::Calculate<VPDominatorTree>(VPDominatorTree &DT);
 
 void VPValue::replaceAllUsesWith(VPValue *New) {
   for (VPUser *User : users())
     for (unsigned I = 0, E = User->getNumOperands(); I < E; ++I)
       if (User->getOperand(I) == this)
         User->setOperand(I, New);
+  Users.clear();
 }
 
 void VPValue::printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const {
   if (const Value *UV = getUnderlyingValue()) {
     OS << "ir<";
     UV->printAsOperand(OS, false);
     OS << ">";
     return;
for (const VPBlockBase *Block : RPOT)
     assignSlots(Block);
 }
 
 void VPSlotTracker::assignSlots(const VPBasicBlock *VPBB) {
   for (const VPRecipeBase &Recipe : *VPBB) {
     if (const auto *VPI = dyn_cast<VPInstruction>(&Recipe))
       assignSlot(VPI);
     else if (const auto *VPIV = dyn_cast<VPWidenCanonicalIVRecipe>(&Recipe))
-      assignSlot(VPIV->getVPValue());
+      assignSlot(VPIV);
   }
 }
 
 void VPSlotTracker::assignSlots(const VPlan &Plan) {
 
   for (const VPValue *V : Plan.VPExternalDefs)
     assignSlot(V);
 

llvm/lib/Transforms/Vectorize/VPlanValue.h

 
 namespace llvm {
 
 // Forward declarations.
 class raw_ostream;
 class Value;
 class VPSlotTracker;
 class VPUser;
+class VPRecipeBase;
 
 // This is the base class of the VPlan Def/Use graph, used for modeling the data
 // flow into, within and out of the VPlan. VPValues can stand for live-ins
 // coming from the input IR, instructions which VPlan will generate if executed
 // and live-outs which the VPlan will need to fix accordingly.
 class VPValue {
   friend class VPBuilder;
   friend struct VPlanTransforms;
protected:
 
   // 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.
 
+public:
   /// Return the underlying Value attached to this VPValue.
   Value *getUnderlyingValue() { return UnderlyingVal; }
   const Value *getUnderlyingValue() const { return UnderlyingVal; }
 
+protected:
   // Set \p Val as the underlying Value of this VPValue.
   void setUnderlyingValue(Value *Val) {
     assert(!UnderlyingVal && "Underlying Value is already set.");
     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,
     VPMultiValueSC,
+
+    VPBlendSC, // All following ID's should be VPRecipes.
+    VPBranchOnMaskSC,
     VPInstructionSC,
-    VPMemoryInstructionSC,
-    VPVWidenCallSC,
-    VPVWidenSelectSC,
-    VPVWidenGEPSC,
-    VPVInterleaveSC
+    VPInterleaveSC,
+    VPPredInstPHISC,
+    VPReductionSC,
+    VPReplicateSC,
+    VPWidenCallSC,
+    VPWidenCanonicalIVSC,
+    VPWidenGEPSC,
+    VPWidenIntOrFpInductionSC,
+    VPWidenMemoryInstructionSC,
+    VPWidenPHISC,
+    VPWidenSC,
+    VPWidenSelectSC
   };
 
   VPValue(Value *UV = nullptr) : VPValue(VPValueSC, UV) {}
   VPValue(const VPValue &) = delete;
   VPValue &operator=(const VPValue &) = delete;
   virtual ~VPValue() {}
 
   /// \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.
   unsigned getVPValueID() const { return SubclassID; }
 
   virtual VPValue *getDefiningValue() { return this; }
   virtual VPValue const *getDefiningValue() const { return this; }
 
+  Type *getType() {
+    if (UnderlyingVal)
+      return UnderlyingVal->getType();
+    return nullptr;
+  }
+
   void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const;
   void print(raw_ostream &OS, VPSlotTracker &Tracker) const;
 
   unsigned getNumUsers() const { return Users.size(); }
   virtual void addUser(VPUser &User) { Users.push_back(&User); }
+  void removeUser(VPUser *User) {
+    auto It = find(Users, User);
+    assert(It != Users.end() && "Expected User in Users");
+    Users.erase(It);
+  }
 
   typedef SmallVectorImpl<VPUser *>::iterator user_iterator;
   typedef SmallVectorImpl<VPUser *>::const_iterator const_user_iterator;
   typedef iterator_range<user_iterator> user_range;
   typedef iterator_range<const_user_iterator> const_user_range;
 
   user_iterator user_begin() { return Users.begin(); }
   const_user_iterator user_begin() const { return Users.begin(); }
bool hasMoreThanOneUniqueUser() {
     // Check if all users match the first user.
     auto Current = std::next(user_begin());
     while (Current != user_end() && *user_begin() == *Current)
       Current++;
     return Current != user_end();
   }
 
   void replaceAllUsesWith(VPValue *New);
+
+  static inline bool classof(const VPRecipeBase *V) { return true; }
 };
 
 /// This class can be used to reference a VPValue produced by a recipe that
 /// defines multiple VPValues.
 class VPMultiValue : public VPValue {
   VPValue *DefiningValue;
 
 public:
public:
 
   unsigned getNumOperands() const { return Operands.size(); }
   inline VPValue *getOperand(unsigned N) const {
     assert(N < Operands.size() && "Operand index out of bounds");
     return Operands[N];
   }
 
   void setOperand(unsigned I, VPValue *New) { Operands[I] = New; }
+  void clearOperands() { Operands.clear(); }
 
   typedef SmallVectorImpl<VPValue *>::iterator operand_iterator;
   typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator;
   typedef iterator_range<operand_iterator> operand_range;
   typedef iterator_range<const_operand_iterator> const_operand_range;
 
   operand_iterator op_begin() { return Operands.begin(); }
   const_operand_iterator op_begin() const { return Operands.begin(); }