[VPlan] Replace VPWidenRecipe with VPInstruction (WIP).

[fhahn]

Summary

This patch replaces VPWidenRecipe with VPInstructions. This is still WIP
and needs to handle a few additional cases, but I wanted to share this
early to make sure the direction makes sense.

With the current version, we get

Expected Passes    : 286
Unexpected Failures: 63

I introduced a new VPWidenInstruction, but maybe it would be better to
just use VPInstruction.

If the direction looks right, I'll also continue with other recipes.

[fhahn]

Still needs a way to get defs from other recipes.

[fhahn]

Move parts of to NFC patches, fix almost all failures.

[fhahn]

Use created VPInstructions directly for VPWidenInstruction operands, if available.

Fix most outstanding issues, down to failing tests.

There is still a bit of cleanup and bikeshedding required, but first it would be good to decide on the overall approach.

[Ayal]

Breaking the recipes into VPInstructions is indeed on the roadmap for evolving VPlan to support transformations, cost modeling, and more.

The approach we’ve taken so far is to first migrate the def-use dependencies between recipes, which originally rely on the underlying immutable def-use dependencies among their IR ingredient Instructions and their Operands, to VPlan VPValue-VPUser dependencies. Once two recipes feed each other via a VPValue-VPUser pair, new VPInstructions can be introduced freely between them. The primary motivation for this approach is to facilitate VPlan def-use analysis and transformations, including reordering recipes, replacing them, and introducing new VPInstructions. Once the uses of all recipes migrate to VPUsers, a rather mechanical process following D70865, any single-def recipe can be converted independently into a VPInstruction. VPWidenRecipe is indeed an easy first candidate, which would break up naturally at this time.

An approach that first breaks recipes into VPInstructions, will migrate all def-use dependencies when the *last* recipe is broken. Other recipes are however more challenging to break than VPWidenRecipe, because they have multiple defs, entail SCEV expansions, un/pack predicated scalars along a to-be-unrolled loop of VF*UF iterations, and more. These design challenges require careful attention, which should preferably be devoted in parallel to facilitating VPlan transformation rather than blocking it.

Breaking VPWidenRecipe into a VPInstruction at this time, by letting dependent recipes continue to rely on their underlying IR Operands, via a lookup for potential VPValues (VPInstructions) that cover their corresponding IR Value def, presumably builds a VPlan def-use graph but in effect does not support introducing a new VPInstruction between a VPWidenInstruction and its users. It seems preferable to first focus on migrating away from the original IR def-use relations, gradually and consistently.

Gil&Ayal.

[fhahn]

Rebased & updated to only use VPWidenInstruction in VPIRBuilder if there is an underlying value.

In D74695#1916542, @Ayal wrote:

Breaking the recipes into VPInstructions is indeed on the roadmap for evolving VPlan to support transformations, cost modeling, and more.

The approach we’ve taken so far is to first migrate the def-use dependencies between recipes, which originally rely on the underlying immutable def-use dependencies among their IR ingredient Instructions and their Operands, to VPlan VPValue-VPUser dependencies. Once two recipes feed each other via a VPValue-VPUser pair, new VPInstructions can be introduced freely between them. The primary motivation for this approach is to facilitate VPlan def-use analysis and transformations, including reordering recipes, replacing them, and introducing new VPInstructions. Once the uses of all recipes migrate to VPUsers, a rather mechanical process following D70865, any single-def recipe can be converted independently into a VPInstruction. VPWidenRecipe is indeed an easy first candidate, which would break up naturally at this time.

An approach that first breaks recipes into VPInstructions, will migrate all def-use dependencies when the *last* recipe is broken. Other recipes are however more challenging to break than VPWidenRecipe, because they have multiple defs, entail SCEV expansions, un/pack predicated scalars along a to-be-unrolled loop of VF*UF iterations, and more. These design challenges require careful attention, which should preferably be devoted in parallel to facilitating VPlan transformation rather than blocking it.

Breaking VPWidenRecipe into a VPInstruction at this time, by letting dependent recipes continue to rely on their underlying IR Operands, via a lookup for potential VPValues (VPInstructions) that cover their corresponding IR Value def, presumably builds a VPlan def-use graph but in effect does not support introducing a new VPInstruction between a VPWidenInstruction and its users. It seems preferable to first focus on migrating away from the original IR def-use relations, gradually and consistently.

Thanks for the detailed response! I agree we should focus on migrating the def-use dependencies of the existing recipes. I think doing so for VPWidenRecipe might be more tricky than other recipes, as VPWidenRecipe currently contains a list of instructions. To me it seems breaking VPWidenRecipe up into a new VPInstructions makes modeling the def-use chain easier (the operands are explicit per VPInstruction) and allows us to make progress on 2 fronts: migrating def-uses and getting rid of a recipe. It also should not hinder migrating the def-use dependencies for other recipes, but rather help because we can directly use the VPWidenInstruction as VPValue inputs for other recipes.

I thought a little bit about how to migrate the def-use dependencies for VPWidenRecipe without breaking it up, but couldn't come up with a more straight-forward approach. I might be missing something though and would also be happy to explore other directions. Given that the existing approach in this patch seems to work well in practice (and it makes progress in 2 directions), I think it would allow us to continue moving in the right direction, while we should continue to focus on migrating the def-use dependencies for recipes that cannot be broken up easily.

[gilr]

In D74695#1923526, @fhahn wrote:

I think doing so for VPWidenRecipe might be more tricky than other recipes, as VPWidenRecipe currently contains a list of instructions.
[snip]
I thought a little bit about how to migrate the def-use dependencies for VPWidenRecipe without breaking it up, but couldn't come up with a more straight-forward approach.

VPWidenRecipe wrapped intervals of ingredients just to keep VPlan's memory footprint low. Now that we begin to model def-use relations this mechanism will have to go (it's already suppressed for sink-after). We can start by removing compression altogether in a preliminary patch, turning VPWidenRecipe into a single-ingredient recipe, ready to take VPValue operands.
A following patch can add VPValue operands to VPWidenRecipe by calling getOrAddVPValue() for each IR operand, similar to D70865.
The next patch (perhaps also in parts) can replace VPWidenRecipes with VPInstructions by
(a) binding VP defs to IR users, as proposed
(b) extending the usage of recordRecipe() to ingredients covered by VPInstructions such that calling getRecipe() will return either a VPInstruction, another Recipe or nullptr. For the latter two cases, call getOrAddVPValue().
(c) refactoring VPWidenRecipe's execute()
What do you think?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6982

Not sure why ExternalDef is needed, as Value2VPValue is used for both variant and invariant values.

llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h

93

Better reuse getRecipe(), allowing it to return nullptr in order to trivially support querying invariant values and ingredients whose recipes are not being recorded.

95

Requires recording the recipes for such ingredients.

llvm/lib/Transforms/Vectorize/VPlan.h

765

Better avoid subclassing VPInstruction until scalar/type is modelled.

[fhahn]

In D74695#1926674, @gilr wrote:

In D74695#1923526, @fhahn wrote:

I think doing so for VPWidenRecipe might be more tricky than other recipes, as VPWidenRecipe currently contains a list of instructions.
[snip]
I thought a little bit about how to migrate the def-use dependencies for VPWidenRecipe without breaking it up, but couldn't come up with a more straight-forward approach.

VPWidenRecipe wrapped intervals of ingredients just to keep VPlan's memory footprint low. Now that we begin to model def-use relations this mechanism will have to go (it's already suppressed for sink-after). We can start by removing compression altogether in a preliminary patch, turning VPWidenRecipe into a single-ingredient recipe, ready to take VPValue operands.
A following patch can add VPValue operands to VPWidenRecipe by calling getOrAddVPValue() for each IR operand, similar to D70865.
The next patch (perhaps also in parts) can replace VPWidenRecipes with VPInstructions by
(a) binding VP defs to IR users, as proposed
(b) extending the usage of recordRecipe() to ingredients covered by VPInstructions such that calling getRecipe() will return either a VPInstruction, another Recipe or nullptr. For the latter two cases, call getOrAddVPValue().
(c) refactoring VPWidenRecipe's execute()
What do you think?

That sounds good. I'll break up the patch along the lines suggested ASAP.

[fhahn]

More broken down approach now available D84684

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

 
 /// VPlan-based builder utility analogous to IRBuilder.
 class VPBuilder {
 private:
   VPBasicBlock *BB = nullptr;
   VPBasicBlock::iterator InsertPt = VPBasicBlock::iterator();
 
   VPInstruction *createInstruction(unsigned Opcode,
-                                   ArrayRef<VPValue *> Operands) {
-    VPInstruction *Instr = new VPInstruction(Opcode, Operands);
+                                   ArrayRef<VPValue *> Operands,
+                                   bool ShouldWiden) {
+    VPInstruction *Instr = ShouldWiden
+                               ? new VPWidenInstruction(Opcode, Operands)
+                               : new VPInstruction(Opcode, Operands);
     if (BB)
       BB->insert(Instr, InsertPt);
     return Instr;
   }
 
   VPInstruction *createInstruction(unsigned Opcode,
-                                   std::initializer_list<VPValue *> Operands) {
-    return createInstruction(Opcode, ArrayRef<VPValue *>(Operands));
+                                   std::initializer_list<VPValue *> Operands,
+                                   bool ShouldWiden) {
+    return createInstruction(Opcode, ArrayRef<VPValue *>(Operands),
+                             ShouldWiden);
   }
 
 public:
   VPBuilder() {}
 
   /// Clear the insertion point: created instructions will not be inserted into
   /// a block.
   void clearInsertionPoint() {
VPInstruction *insert(VPInstruction *I) const {
     BB->insert(I, InsertPt);
     return I;
   }
 
   /// Create an N-ary operation with \p Opcode, \p Operands and set \p Inst as
   /// its underlying Instruction.
   VPValue *createNaryOp(unsigned Opcode, ArrayRef<VPValue *> Operands,
                         Instruction *Inst = nullptr) {
-    VPInstruction *NewVPInst = createInstruction(Opcode, Operands);
+    VPInstruction *NewVPInst =
+        createInstruction(Opcode, Operands, Inst != nullptr);
     NewVPInst->setUnderlyingValue(Inst);
     return NewVPInst;
   }
   VPValue *createNaryOp(unsigned Opcode,
                         std::initializer_list<VPValue *> Operands,
                         Instruction *Inst = nullptr) {
     return createNaryOp(Opcode, ArrayRef<VPValue *>(Operands), Inst);
   }
 
   VPValue *createNot(VPValue *Operand) {
-    return createInstruction(VPInstruction::Not, {Operand});
+    return createInstruction(VPInstruction::Not, {Operand}, false);
   }
 
   VPValue *createAnd(VPValue *LHS, VPValue *RHS) {
-    return createInstruction(Instruction::BinaryOps::And, {LHS, RHS});
+    return createInstruction(Instruction::BinaryOps::And, {LHS, RHS}, false);
   }
 
   VPValue *createOr(VPValue *LHS, VPValue *RHS) {
-    return createInstruction(Instruction::BinaryOps::Or, {LHS, RHS});
+    return createInstruction(Instruction::BinaryOps::Or, {LHS, RHS}, false);
   }
 
   //===--------------------------------------------------------------------===//
   // RAII helpers.
   //===--------------------------------------------------------------------===//
 
   /// RAII object that stores the current insertion point and restores it when
   /// the object is destroyed.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

void vectorizeMemoryInstruction(Instruction *Instr, VPTransformState &State,
                                   VPValue *BlockInMask = nullptr);
 
   /// Set the debug location in the builder using the debug location in
   /// the instruction.
   void setDebugLocFromInst(IRBuilder<> &B, const Value *Ptr);
 
   /// Fix the non-induction PHIs in the OrigPHIsToFix vector.
   void fixNonInductionPHIs(void);
+  /// Maps values from the original loop to their corresponding values in the
+  /// vectorized loop. A key value can map to either vector values, scalar
+  /// values or both kinds of values, depending on whether the key was
+  /// vectorized and scalarized.
+  VectorizerValueMap VectorLoopValueMap;
 
 protected:
   friend class LoopVectorizationPlanner;
   // Allow VPTransformState to expose a few ILV helper functions during the
   // transition period.
   friend struct VPTransformState;
 
   /// A small list of PHINodes.
protected:
   SmallVector<BasicBlock *, 4> LoopBypassBlocks;
 
   /// The new Induction variable which was added to the new block.
   PHINode *Induction = nullptr;
 
   /// The induction variable of the old basic block.
   PHINode *OldInduction = nullptr;
 
-  /// Maps values from the original loop to their corresponding values in the
-  /// vectorized loop. A key value can map to either vector values, scalar
-  /// values or both kinds of values, depending on whether the key was
-  /// vectorized and scalarized.
-  VectorizerValueMap VectorLoopValueMap;
-
   /// Store instructions that were predicated.
   SmallVector<Instruction *, 4> PredicatedInstructions;
 
   /// Trip count of the original loop.
   Value *TripCount = nullptr;
 
   /// Trip count of the widened loop (TripCount - TripCount % (VF*UF))
   Value *VectorTripCount = nullptr;
void InnerLoopVectorizer::emitMinimumIterationCountCheck(Loop *L,
 
   ReplaceInstWithInst(
       TCCheckBlock->getTerminator(),
       BranchInst::Create(Bypass, LoopVectorPreHeader, CheckMinIters));
   LoopBypassBlocks.push_back(TCCheckBlock);
 }
 
 void InnerLoopVectorizer::emitSCEVChecks(Loop *L, BasicBlock *Bypass) {
+
   // Reuse existing vector loop preheader for SCEV checks.
   // Note that new preheader block is generated for vector loop.
   BasicBlock *const SCEVCheckBlock = LoopVectorPreHeader;
 
   // Generate the code to check that the SCEV assumptions that we made.
   // We want the new basic block to start at the first instruction in a
   // sequence of instructions that form a check.
   SCEVExpander Exp(*PSE.getSE(), Bypass->getModule()->getDataLayout(),
void LoopVectorizationPlanner::executePlan(InnerLoopVectorizer &ILV,
 
   // 1. Create a new empty loop. Unlink the old loop and connect the new one.
   VPCallbackILV CallbackILV(ILV);
 
   VPTransformState State{BestVF,       BestUF,      LI,
                          DT,           TLI,         ILV.PSE,
                          ILV.OrigLoop, ILV.Builder, ILV.VectorLoopValueMap,
                          &ILV,         CallbackILV};
+
   State.CFG.PrevBB = ILV.createVectorizedLoopSkeleton();
   State.TripCount = ILV.getOrCreateTripCount(nullptr);
 
   //===------------------------------------------------===//
   //
   // Notice: any optimization or new instruction that go
   // into the code below should also be implemented in
   // the cost-model.
auto willWiden = [&](unsigned VF) -> bool {
     }
     return true;
   };
 
   if (!LoopVectorizationPlanner::getDecisionAndClampRange(willWiden, Range))
     return false;
   // If this ingredient's recipe is to be recorded, keep its recipe a singleton
   // to avoid having to split recipes later.
-  bool IsSingleton = Ingredient2Recipe.count(I);
 
   // Success: widen this instruction.
 
-  // Use the default widening recipe. We optimize the common case where
-  // consecutive instructions can be represented by a single recipe.
-  if (!IsSingleton && !VPBB->empty() && LastExtensibleRecipe == &VPBB->back() &&
-      LastExtensibleRecipe->appendInstruction(I))
-    return true;
+  VPlan &Plan = *VPBB->getPlan();
+  SmallVector<VPValue *, 4> Ops;
+  for (Value *Op : I->operands()) {
+    if (auto *VPI = getVPInstruction(Op)) {
+      Ops.push_back(VPI);
+      continue;
+    }
+    VPValue *VPV;
+    if (OrigLoop->isLoopInvariant(Op)) {
+      VPV = new VPValue(Op);
+      Plan.addExternalDef(VPV);
+    } else
+      VPV = Plan.getOrAddVPValue(Op);
+
+    Ops.push_back(VPV);
+  }
 
-  VPWidenRecipe *WidenRecipe = new VPWidenRecipe(I);
-  if (!IsSingleton)
-    LastExtensibleRecipe = WidenRecipe;
+  VPWidenInstruction *WidenRecipe = new VPWidenInstruction(I->getOpcode(), Ops);
+  WidenRecipe->setUnderlyingInstr(I);
   setRecipe(I, WidenRecipe);
   VPBB->appendRecipe(WidenRecipe);
   return true;
 }
 
 VPBasicBlock *VPRecipeBuilder::handleReplication(
     Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
     DenseMap<Instruction *, VPReplicateRecipe *> &PredInst2Recipe,
void VPInterleaveRecipe::print(raw_ostream &O, const Twine &Indent,
   }
   O << "\\l\"";
   for (unsigned i = 0; i < IG->getFactor(); ++i)
     if (Instruction *I = IG->getMember(i))
       O << " +\n"
         << Indent << "\"  " << VPlanIngredient(I) << " " << i << "\\l\"";
 }
 
-void VPWidenRecipe::execute(VPTransformState &State) {
-  for (auto &Instr : make_range(Begin, End))
-    State.ILV->widenInstruction(Instr);
+void VPTransformState::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;
+  if (auto VPI = dyn_cast<VPInstruction>(Def))
+    if (VPI->getUnderlyingInstr())
+      ILV->VectorLoopValueMap.setVectorValue(VPI->getUnderlyingInstr(), Part,
+                                             V);
 }
 
 void VPTransformState::addMetadata(ArrayRef<Value *> To, Instruction *From) {
   ILV->addMetadata(To, From);
 }
 
 void VPTransformState::setDebugLocFromInst(IRBuilder<> &B, const Value *Ptr) {
   ILV->setDebugLocFromInst(B, Ptr);

llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h

class VPRecipeBuilder {
   BlockMaskCacheTy BlockMaskCache;
 
   // VPlan-VPlan transformations support: Hold a mapping from ingredients to
   // their recipe. To save on memory, only do so for selected ingredients,
   // marked by having a nullptr entry in this map. If those ingredients get a
   // VPWidenRecipe, also avoid compressing other ingredients into it to avoid
   // having to split such recipes later.
   DenseMap<Instruction *, VPRecipeBase *> Ingredient2Recipe;
-  VPWidenRecipe *LastExtensibleRecipe = nullptr;
 
   /// Set the recipe created for given ingredient. This operation is a no-op for
   /// ingredients that were not marked using a nullptr entry in the map.
   void setRecipe(Instruction *I, VPRecipeBase *R) {
-    if (!Ingredient2Recipe.count(I))
-      return;
     assert(Ingredient2Recipe[I] == nullptr &&
            "Recipe already set for ingredient");
     Ingredient2Recipe[I] = R;
   }
 
 public:
   /// A helper function that computes the predicate of the block BB, assuming
   /// that the header block of the loop is set to True. It returns the *entry*
public:
   VPRecipeBase *getRecipe(Instruction *I) {
     assert(Ingredient2Recipe.count(I) &&
            "Recording this ingredients recipe was not requested");
     assert(Ingredient2Recipe[I] != nullptr &&
            "Ingredient doesn't have a recipe");
     return Ingredient2Recipe[I];
   }
 
+  /// Return the recipe created for given ingredient.
+  VPInstruction *getVPInstruction(Value *V) {
+    auto I = dyn_cast<Instruction>(V);
+    auto Iter = Ingredient2Recipe.find(I);
+    if (Iter == Ingredient2Recipe.end())
+      return nullptr;
+    return dyn_cast<VPInstruction>(Iter->second);
+  }
+
   /// Check if \I is a memory instruction to be widened for \p Range.Start and
   /// potentially masked. Such instructions are handled by a recipe that takes
   /// an additional VPInstruction for the mask.
   VPWidenMemoryInstructionRecipe *
   tryToWidenMemory(Instruction *I, VFRange &Range, VPlanPtr &Plan);
 
   /// Check if an induction recipe should be constructed for \I within the given
   /// VF \p Range. If so build and return it. If not, return null. \p Range.End

llvm/lib/Transforms/Vectorize/VPlan.h

struct VPTransformState {
   /// 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) {
     // If Values have been set for this Def return the one relevant for \p Part.
     if (Data.PerPartOutput.count(Def))
       return Data.PerPartOutput[Def][Part];
     // Def is managed by ILV: bring the Values from ValueMap.
+    if (VPValue2Value.count(Def))
       return Callback.getOrCreateVectorValues(VPValue2Value[Def], Part);
+    return Callback.getOrCreateVectorValues(Def->getUnderlyingValue(), Part);
   }
 
   /// Get the generated Value for a given VPValue and given Part and Lane. Note
   /// that as per-lane Defs are still created by ILV and managed in its ValueMap
   /// this method currently just delegates the call to ILV.
   Value *get(VPValue *Def, const VPIteration &Instance) {
     return Callback.getOrCreateScalarValue(VPValue2Value[Def], Instance);
   }
 
   /// Set the generated Value for a given VPValue and a given Part.
-  void set(VPValue *Def, Value *V, unsigned Part) {
-    if (!Data.PerPartOutput.count(Def)) {
-      DataState::PerPartValuesTy Entry(UF);
-      Data.PerPartOutput[Def] = Entry;
-    }
-    Data.PerPartOutput[Def][Part] = V;
-  }
+  void set(VPValue *Def, Value *V, unsigned Part);
 
   void addMetadata(ArrayRef<Value *> To, Instruction *From);
 
   void setDebugLocFromInst(IRBuilder<> &B, const Value *Ptr);
 
   unsigned getVectorCallCost(CallInst *CI, unsigned VF, bool &NeedToScalarize);
 
   unsigned getVectorIntrinsicCost(CallInst *CI, unsigned VF);
public:
   /// An enumeration for keeping track of the concrete subclass of VPRecipeBase
   /// that is actually instantiated. Values of this enumeration are kept in the
   /// SubclassID field of the VPRecipeBase objects. They are used for concrete
   /// type identification.
   using VPRecipeTy = enum {
     VPBlendSC,
     VPBranchOnMaskSC,
     VPInstructionSC,
+    VPWidenInstructionSC,
     VPInterleaveSC,
     VPPredInstPHISC,
     VPReplicateSC,
     VPWidenGEPSC,
     VPWidenIntOrFpInductionSC,
     VPWidenMemoryInstructionSC,
     VPWidenPHISC,
-    VPWidenSC,
   };
 
   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.
private:
   typedef unsigned char OpcodeTy;
   OpcodeTy Opcode;
 
   /// Utility method serving execute(): generates a single instance of the
   /// modeled instruction.
   void generateInstruction(VPTransformState &State, unsigned Part);
 
 protected:
+  VPInstruction(const unsigned char ValueSC, VPRecipeTy RecipeSC,
+                unsigned Opcode, ArrayRef<VPValue *> Operands)
+      : VPUser(ValueSC, Operands), VPRecipeBase(RecipeSC), Opcode(Opcode) {}
+
+public:
   Instruction *getUnderlyingInstr() {
     return cast_or_null<Instruction>(getUnderlyingValue());
   }
 
-  void setUnderlyingInstr(Instruction *I) { setUnderlyingValue(I); }
+  const Instruction *getUnderlyingInstr() const {
+    return cast_or_null<Instruction>(getUnderlyingValue());
+  }
 
-public:
+  void setUnderlyingInstr(Instruction *I) { setUnderlyingValue(I); }
   VPInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands)
-      : VPUser(VPValue::VPInstructionSC, Operands),
-        VPRecipeBase(VPRecipeBase::VPInstructionSC), Opcode(Opcode) {}
+      : VPInstruction(VPValue::VPInstructionSC, VPRecipeBase::VPInstructionSC,
+                      Opcode, Operands) {}
 
   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;
+    return V->getVPValueID() == VPValue::VPInstructionSC ||
+           V->getVPValueID() == VPValue::VPWidenInstructionSC;
   }
 
   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;
+    return R->getVPRecipeID() == VPRecipeBase::VPInstructionSC ||
+           R->getVPRecipeID() == VPRecipeBase::VPWidenInstructionSC;
   }
 
   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;
 
   /// Print the Recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 
   /// Print the VPInstruction.
   void print(raw_ostream &O) const;
   void print(raw_ostream &O, VPSlotTracker &SlotTracker) const;
 
   /// Return true if this instruction may modify memory.
   bool mayWriteToMemory() const {
     // TODO: we can use attributes of the called function to rule out memory
     //       modifications.
     return Opcode == Instruction::Store || Opcode == Instruction::Call ||
            Opcode == Instruction::Invoke || Opcode == SLPStore;
   }
-};
 
-/// VPWidenRecipe is a recipe for producing a copy of vector type for each
-/// Instruction in its ingredients independently, in order. This recipe covers
-/// most of the traditional vectorization cases where each ingredient transforms
-/// into a vectorized version of itself.
-class VPWidenRecipe : public VPRecipeBase {
-private:
-  /// Hold the ingredients by pointing to their original BasicBlock location.
-  BasicBlock::iterator Begin;
-  BasicBlock::iterator End;
+  DebugLoc getDebugLoc(unsigned Factor) const;
+};
 
+class VPWidenInstruction : public VPInstruction {
 public:
-  VPWidenRecipe(Instruction *I) : VPRecipeBase(VPWidenSC) {
-    End = I->getIterator();
-    Begin = End++;
-  }
+  VPWidenInstruction(unsigned Opcode, ArrayRef<VPValue *> Operands)
+      : VPInstruction(VPValue::VPWidenInstructionSC,
+                      VPRecipeBase::VPWidenInstructionSC, Opcode, Operands) {}
 
-  ~VPWidenRecipe() override = default;
+  VPWidenInstruction(unsigned Opcode, std::initializer_list<VPValue *> Operands)
+      : VPWidenInstruction(Opcode, ArrayRef<VPValue *>(Operands)) {}
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
-  static inline bool classof(const VPRecipeBase *V) {
-    return V->getVPRecipeID() == VPRecipeBase::VPWidenSC;
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() == VPValue::VPWidenInstructionSC;
   }
 
-  /// Produce widened copies of all Ingredients.
   void execute(VPTransformState &State) override;
-
-  /// Augment the recipe to include Instr, if it lies at its End.
-  bool appendInstruction(Instruction *Instr) {
-    if (End != Instr->getIterator())
-      return false;
-    End++;
-    return true;
-  }
-
-  /// Print the recipe.
-  void print(raw_ostream &O, const Twine &Indent,
-             VPSlotTracker &SlotTracker) const override;
 };
 
 /// A recipe for handling GEP instructions.
 class VPWidenGEPRecipe : public VPRecipeBase {
 private:
   GetElementPtrInst *GEP;
   bool IsPtrLoopInvariant;
   SmallBitVector IsIndexLoopInvariant;
public:
   void setName(const Twine &newName) { Name = newName.str(); }
 
   /// Add \p VPVal to the pool of external definitions if it's not already
   /// in the pool.
   void addExternalDef(VPValue *VPVal) {
     VPExternalDefs.insert(VPVal);
   }
 
+  bool isExternalDef(VPValue *VPVal) const {
+    return VPExternalDefs.find(VPVal) != VPExternalDefs.end();
+  }
+
   /// Add \p CBV to the vector of condition bit values.
   void addCBV(VPValue *CBV) {
     VPCBVs.push_back(CBV);
   }
 
   void addVPValue(Value *V) {
     assert(V && "Trying to add a null Value to VPlan");
     assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
-    Value2VPValue[V] = new VPValue();
+    Value2VPValue[V] = new VPValue(V);
   }
 
   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];
   }
 

llvm/lib/Transforms/Vectorize/VPlan.cpp

 #include "VPlanDominatorTree.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
+#include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
iplist<VPRecipeBase>::iterator VPRecipeBase::eraseFromParent() {
   return getParent()->getRecipeList().erase(getIterator());
 }
 
 void VPRecipeBase::moveAfter(VPRecipeBase *InsertPos) {
   removeFromParent();
   insertAfter(InsertPos);
 }
 
+void VPWidenInstruction::execute(VPTransformState &State) {
+  SmallVector<Value *, 4> VecOps;
+  auto *OriginalI = cast<Instruction>(getUnderlyingInstr());
+  State.setDebugLocFromInst(State.Builder, OriginalI);
+  switch (getOpcode()) {
+  case Instruction::Br:
+  case Instruction::PHI:
+  case Instruction::GetElementPtr:
+    llvm_unreachable("This instruction is handled by a different recipe.");
+  case Instruction::UDiv:
+  case Instruction::SDiv:
+  case Instruction::SRem:
+  case Instruction::URem:
+  case Instruction::Add:
+  case Instruction::FAdd:
+  case Instruction::Sub:
+  case Instruction::FSub:
+  case Instruction::FNeg:
+  case Instruction::Mul:
+  case Instruction::FMul:
+  case Instruction::FDiv:
+  case Instruction::FRem:
+  case Instruction::Shl:
+  case Instruction::LShr:
+  case Instruction::AShr:
+  case Instruction::And:
+  case Instruction::Or:
+  case Instruction::Xor: {
+    // Just widen unops and binops.
+    if (auto DL = getDebugLoc(State.VF * State.UF))
+      State.Builder.SetCurrentDebugLocation(DL);
+
+    for (unsigned Part = 0; Part < State.UF; ++Part) {
+      SmallVector<Value *, 2> Ops;
+      for (VPValue *Op : operands())
+        Ops.push_back(State.get(Op, Part));
+
+      Value *V = State.Builder.CreateNAryOp(getOpcode(), Ops);
+
+      // Use this vector value for all users of the original instruction.
+      State.set(this, V, Part);
+
+      if (auto VecOp = dyn_cast<Instruction>(V))
+        VecOp->copyIRFlags(OriginalI);
+
+      VecOps.push_back(V);
+    }
+    break;
+  }
+  case Instruction::Select: {
+    // Widen selects.
+    // If the selector is loop invariant we can create a select
+    // instruction with a scalar condition. Otherwise, use vector-select.
+    auto *SE = State.PSE.getSE();
+    bool InvariantCond =
+        getOperand(0)->getUnderlyingValue()
+            ? SE->isLoopInvariant(
+                  State.PSE.getSCEV(getOperand(0)->getUnderlyingValue()),
+                  State.OriginalLoop)
+            : false;
+
+    // The condition can be loop invariant  but still defined inside the
+    // loop. This means that we can't just use the original 'cond' value.
+    // We have to take the 'vectorized' value and pick the first lane.
+    // Instcombine will make this a no-op.
+    auto &Plan = *getParent()->getPlan();
+    auto *ScalarCond = Plan.isExternalDef(getOperand(0))
+                           ? getOperand(0)->getUnderlyingValue()
+                           : State.get(getOperand(0), 0);
+
+    for (unsigned Part = 0; Part < State.UF; ++Part) {
+      Value *Cond = State.get(getOperand(0), Part);
+      Value *Op0 = State.get(getOperand(1), Part);
+      Value *Op1 = State.get(getOperand(2), Part);
+      Value *Sel = State.Builder.CreateSelect(InvariantCond ? ScalarCond : Cond,
+                                              Op0, Op1);
+      State.set(this, Sel, Part);
+      VecOps.push_back(Sel);
+    }
+
+    break;
+  }
+
+  case Instruction::ICmp:
+  case Instruction::FCmp: {
+    // Widen compares. Generate vector compares.
+    bool FCmp = (getOpcode() == Instruction::FCmp);
+    auto *Cmp = cast<CmpInst>(getUnderlyingInstr());
+
+    for (unsigned Part = 0; Part < State.UF; ++Part) {
+      Value *A = State.get(getOperand(0), Part);
+      Value *B = State.get(getOperand(1), Part);
+      Value *C = nullptr;
+      if (FCmp) {
+        // Propagate fast math flags.
+        IRBuilder<>::FastMathFlagGuard FMFG(State.Builder);
+        State.Builder.setFastMathFlags(Cmp->getFastMathFlags());
+        C = State.Builder.CreateFCmp(Cmp->getPredicate(), A, B);
+      } else {
+        C = State.Builder.CreateICmp(Cmp->getPredicate(), A, B);
+      }
+      State.set(this, C, Part);
+      VecOps.push_back(C);
+    }
+
+    break;
+  }
+
+  case Instruction::ZExt:
+  case Instruction::SExt:
+  case Instruction::FPToUI:
+  case Instruction::FPToSI:
+  case Instruction::FPExt:
+  case Instruction::PtrToInt:
+  case Instruction::IntToPtr:
+  case Instruction::SIToFP:
+  case Instruction::UIToFP:
+  case Instruction::Trunc:
+  case Instruction::FPTrunc:
+  case Instruction::BitCast: {
+    /// Vectorize casts.
+    Type *DestTy = (State.VF == 1)
+                       ? OriginalI->getType()
+                       : VectorType::get(OriginalI->getType(), State.VF);
+
+    for (unsigned Part = 0; Part < State.UF; ++Part) {
+      Value *A = State.get(getOperand(0), Part);
+      Value *Cast = State.Builder.CreateCast(Instruction::CastOps(getOpcode()),
+                                             A, DestTy);
+      State.set(this, Cast, Part);
+      VecOps.push_back(Cast);
+    }
+    break;
+  }
+
+  case Instruction::Call: {
+    auto *CI = cast<CallInst>(getUnderlyingInstr());
+    // Ignore dbg intrinsics.
+    if (isa<DbgInfoIntrinsic>(CI))
+      break;
+
+    Module *M = CI->getParent()->getParent()->getParent();
+
+    SmallVector<Type *, 4> Tys;
+    for (Value *ArgOperand : CI->arg_operands())
+      Tys.push_back(ToVectorTy(ArgOperand->getType(), State.VF));
+
+    Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, State.TLI);
+
+    // The flag shows whether we use Intrinsic or a usual Call for vectorized
+    // version of the instruction.
+    // Is it beneficial to perform intrinsic call compared to lib call?
+    bool NeedToScalarize;
+    unsigned CallCost = State.getVectorCallCost(CI, State.VF, NeedToScalarize);
+    bool UseVectorIntrinsic =
+        ID && State.getVectorIntrinsicCost(CI, State.VF) <= CallCost;
+    assert((UseVectorIntrinsic || !NeedToScalarize) &&
+           "Instruction should be scalarized elsewhere.");
+
+    for (unsigned Part = 0; Part < State.UF; ++Part) {
+      SmallVector<Value *, 4> Args;
+      for (unsigned i = 0, ie = getNumOperands() - 1; i != ie; ++i) {
+        VPValue *VPArg = getOperand(i);
+        // Some intrinsics have a scalar argument - don't replace it with a
+        // vector.
+        Value *Arg = VPArg->getUnderlyingValue();
+        if (!UseVectorIntrinsic || !hasVectorInstrinsicScalarOpd(ID, i))
+          Arg = State.get(VPArg, Part);
+        Args.push_back(Arg);
+      }
+
+      Function *VectorF;
+      if (UseVectorIntrinsic) {
+        // Use vector version of the intrinsic.
+        Type *TysForDecl[] = {CI->getType()};
+        if (State.VF > 1)
+          TysForDecl[0] =
+              VectorType::get(CI->getType()->getScalarType(), State.VF);
+        VectorF = Intrinsic::getDeclaration(M, ID, TysForDecl);
+      } else {
+        // Use vector version of the function call.
+        const VFShape Shape = VFShape::get(*CI, {State.VF, false} /*EC*/,
+                                           false /*HasGlobalPred*/);
+#ifndef NDEBUG
+        const SmallVector<VFInfo, 8> Infos = VFDatabase::getMappings(*CI);
+        assert(std::find_if(Infos.begin(), Infos.end(),
+                            [&Shape](const VFInfo &Info) {
+                              return Info.Shape == Shape;
+                            }) != Infos.end() &&
+               "Vector function shape is missing from the database.");
+#endif
+        VectorF = VFDatabase(*CI).getVectorizedFunction(Shape);
+      }
+      assert(VectorF && "Can't create vector function.");
+
+      SmallVector<OperandBundleDef, 1> OpBundles;
+      CI->getOperandBundlesAsDefs(OpBundles);
+      CallInst *V = State.Builder.CreateCall(VectorF, Args, OpBundles);
+
+      if (isa<FPMathOperator>(V))
+        V->copyFastMathFlags(CI);
+
+      State.set(this, V, Part);
+      VecOps.push_back(V);
+    }
+
+    break;
+  }
+
+  default:
+    // This instruction is not vectorized by simple widening.
+    LLVM_DEBUG(dbgs() << "LV: Found an unhandled VPInstruction: " << *this);
+    llvm_unreachable("Unhandled instruction!");
+  } // end of switch.
+
+  State.addMetadata(VecOps, OriginalI);
+}
+
 void VPInstruction::generateInstruction(VPTransformState &State,
                                         unsigned Part) {
   IRBuilder<> &Builder = State.Builder;
 
   if (Instruction::isBinaryOp(getOpcode())) {
     Value *A = State.get(getOperand(0), Part);
     Value *B = State.get(getOperand(1), Part);
     Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);
void VPInstruction::print(raw_ostream &O, VPSlotTracker &SlotTracker) const {
   }
 
   for (const VPValue *Operand : operands()) {
     O << " ";
     Operand->printAsOperand(O, SlotTracker);
   }
 }
 
+DebugLoc VPInstruction::getDebugLoc(unsigned Factor) const {
+  if (const Instruction *Inst =
+          dyn_cast_or_null<Instruction>(getUnderlyingInstr())) {
+    const DILocation *DIL = Inst->getDebugLoc();
+    if (DIL && Inst->getFunction()->isDebugInfoForProfiling() &&
+        !isa<DbgInfoIntrinsic>(Inst)) {
+      auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(Factor);
+      if (NewDIL)
+        return NewDIL.getValue();
+      else
+        LLVM_DEBUG(dbgs() << "Failed to create new discriminator: "
+                          << DIL->getFilename() << " Line: " << DIL->getLine());
+      return DebugLoc();
+    } else
+      return DIL;
+  } else
+    return DebugLoc();
+}
+
 /// Generate the code inside the body of the vectorized loop. Assumes a single
 /// LoopVectorBody basic-block was created for this. Introduce additional
 /// basic-blocks as needed, and fill them all.
 void VPlan::execute(VPTransformState *State) {
   // -1. Check if the backedge taken count is needed, and if so build it.
   if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
     Value *TC = State->TripCount;
     IRBuilder<> Builder(State->CFG.PrevBB->getTerminator());
if (E > 0) {
         Inst->getOperand(I)->printAsOperand(RSO << ", ", false);
     }
   } else // !Inst
     V->printAsOperand(RSO, false);
   RSO.flush();
   O << DOT::EscapeString(IngredientString);
 }
 
-void VPWidenRecipe::print(raw_ostream &O, const Twine &Indent,
-                          VPSlotTracker &SlotTracker) const {
-  O << " +\n" << Indent << "\"WIDEN\\l\"";
-  for (auto &Instr : make_range(Begin, End))
-    O << " +\n" << Indent << "\"  " << VPlanIngredient(&Instr) << "\\l\"";
-}
-
 void VPWidenIntOrFpInductionRecipe::print(raw_ostream &O, const Twine &Indent,
                                           VPSlotTracker &SlotTracker) const {
   O << " +\n" << Indent << "\"WIDEN-INDUCTION";
   if (Trunc) {
     O << "\\l\"";
     O << " +\n" << Indent << "\"  " << VPlanIngredient(IV) << "\\l\"";
     O << " +\n" << Indent << "\"  " << VPlanIngredient(Trunc) << "\\l\"";
   } else

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

for (auto I = VPBB->begin(), E = VPBB->end(); I != E;) {
         if (II.getKind() == InductionDescriptor::IK_IntInduction ||
             II.getKind() == InductionDescriptor::IK_FpInduction) {
           NewRecipe = new VPWidenIntOrFpInductionRecipe(Phi);
         } else
           NewRecipe = new VPWidenPHIRecipe(Phi);
       } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
         NewRecipe = new VPWidenGEPRecipe(GEP, OrigLoop);
       } else {
-        // If the last recipe is a VPWidenRecipe, add Inst to it instead of
-        // creating a new recipe.
-        if (VPWidenRecipe *WidenRecipe =
-                dyn_cast_or_null<VPWidenRecipe>(LastRecipe)) {
-          WidenRecipe->appendInstruction(Inst);
-          Ingredient->eraseFromParent();
-          continue;
-        }
-        NewRecipe = new VPWidenRecipe(Inst);
-      }
 
+      auto *VPResultV = Plan->getOrAddVPValue(Inst);
+      VPInst->replaceAllUsesWith(VPResultV);
       NewRecipe->insertBefore(Ingredient);
       LastRecipe = NewRecipe;
       Ingredient->eraseFromParent();
     }
   }
 }

llvm/lib/Transforms/Vectorize/VPlanValue.h

 
 // 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 class VPlanTransforms;
+  friend struct VPTransformState;
   friend class VPBasicBlock;
   friend class VPInterleavedAccessInfo;
+  friend class VPWidenInstruction;
+  friend class VPlan;
 
 private:
   const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
 
   SmallVector<VPUser *, 1> Users;
 
 protected:
   // Hold the underlying Value, if any, attached to this VPValue.
   Value *UnderlyingVal;
 
   VPValue(const unsigned char SC, Value *UV = nullptr)
       : SubclassID(SC), UnderlyingVal(UV) {}
 
   // 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.
 
   /// Return the underlying Value attached to this VPValue.
   Value *getUnderlyingValue() { return UnderlyingVal; }
+  const Value *getUnderlyingValue() const { return UnderlyingVal; }
 
   // 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, VPUserSC, VPInstructionSC };
+  enum { VPValueSC, VPUserSC, VPInstructionSC, VPWidenInstructionSC };
 
   VPValue(Value *UV = nullptr) : VPValue(VPValueSC, UV) {}
   VPValue(const VPValue &) = delete;
   VPValue &operator=(const VPValue &) = delete;
 
   /// \return an ID for the concrete type of this object.
   /// This is used to implement the classof checks. This should not be used
   /// for any other purpose, as the values may change as LLVM evolves.

llvm/unittests/Transforms/Vectorize/VPlanHCFGTest.cpp

TEST_F(VPlanHCFGTest, testVPInstructionToVPRecipesInner) {
   EXPECT_NE(nullptr, Phi);
 
   auto *Idx = dyn_cast<VPWidenGEPRecipe>(&*Iter++);
   EXPECT_NE(nullptr, Idx);
 
   auto *Load = dyn_cast<VPWidenMemoryInstructionRecipe>(&*Iter++);
   EXPECT_NE(nullptr, Load);
 
-  auto *Add = dyn_cast<VPWidenRecipe>(&*Iter++);
-  EXPECT_NE(nullptr, Add);
+  /*  auto *Add = dyn_cast<VPWidenRecipe>(&*Iter++);*/
+  // EXPECT_NE(nullptr, Add);
 
-  auto *Store = dyn_cast<VPWidenMemoryInstructionRecipe>(&*Iter++);
-  EXPECT_NE(nullptr, Store);
+  // auto *Store = dyn_cast<VPWidenMemoryInstructionRecipe>(&*Iter++);
+  // EXPECT_NE(nullptr, Store);
 
-  auto *LastWiden = dyn_cast<VPWidenRecipe>(&*Iter++);
-  EXPECT_NE(nullptr, LastWiden);
-  EXPECT_EQ(VecBB->end(), Iter);
+  // auto *LastWiden = dyn_cast<VPWidenRecipe>(&*Iter++);
+  // EXPECT_NE(nullptr, LastWiden);
+  /*EXPECT_EQ(VecBB->end(), Iter);*/
 }
 
 } // namespace
 } // namespace llvm