[VPlan] Introduce VPWidenIntOrFpInductionRecipes to original plan.

[fhahn]

Summary

Some VPInstructions are converted to recipes regardless of the
vectorization factor. Perform the conversion on the initial/original
plan. This patch does so for VPWidenIntOrFpInductionRecipes

[a.elovikov]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8763

nit: can we use make_early_inc_range here isntead?

8774

Are these modifications to OriginalPlan expected to be done in all the transformations that replace the recipes? If so, I'm afraid that it would be error-prone and would decrease readability of the code.

I'm not familiar with the code to understand why it's needed (yet) so my question might not make much sense, but still. Is it possible we can "hide" those details by making a higher-level interface? Or are we expecting that such maintenance wouldn't be needed once we uplift VPlan to full VPValue-based/more independent of the original LLVM IR?

[fhahn]

Rebased and simplified.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8774

Are these modifications to OriginalPlan expected to be done in all the transformations that replace the recipes? If so, I'm afraid that it would be error-prone and would decrease readability of the code.

Yes, unfortunately there are still a few places that rely on accessing the VPValue via the underlying value, mostly to fix up phis after executing the VPlan. The plan is to update those places to deal with recipes directly, hence not having to access the VPValue through the underlying value.

This means at the moment, the code is a bit bigger than it will be in the end but it is just temporary so we don't have to block progress in multiple directions. For example, D99293 removes the need to use getVPValue with an underlying IR value when fixing reduction PHIs (except for the value for the loop-exit instruction).

[fhahn]

Putting this on hold for now, to first focus on sinking scalar operands as VPlan-to-VPlan transform: D100258

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

ReversePostOrderTraversal<VPBlockBase *> RPOT(
       OriginalPlan.getEntry()->getEntryBasicBlock());
 
   DenseMap<Instruction *, VPInstruction *> Inst2VPInst;
   for (auto &Entry : SinkAfter) {
     Inst2VPInst[Entry.first] = nullptr;
     Inst2VPInst[Entry.second] = nullptr;
   }
 
+  VPRecipeBuilder RecipeBuilder(OrigLoop, TLI, Legal, CM, PSE, Builder);
+
   auto *DummyVal = new VPValue();
   OriginalPlan.addExternalDef(DummyVal);
   for (VPBlockBase *Base : RPOT) {
     VPBasicBlock *OriginalVPBB = Base->getEntryBasicBlock();
-    // Introduce each ingredient into VPlan.
+
+    // First, convert some VPInstructions to recipes, if the conversion does not
+    // depend on the VF. At the moment, only VPIntOrFpInductionRecipes are
+    // created here.
+    for (auto I = OriginalVPBB->begin(), E = OriginalVPBB->end(); I != E;) {
+      VPRecipeBase *Ingredient = &*I++;
+      auto *VPhi = dyn_cast<VPWidenPHIRecipe>(Ingredient);
+      if (!VPhi)
+        break;
+
+      auto *Phi = cast<PHINode>(VPhi->getUnderlyingValue());
+      if (auto *NewPhi =
+              RecipeBuilder.tryToOptimizeInductionPHI(Phi, OriginalPlan)) {
+        for (auto *NewVPV : NewPhi->definedValues()) {
+          Value *UV = NewVPV->getUnderlyingValue();
+          VPValue *OldVPV = OriginalPlan.getVPValue(UV);
+          OldVPV->replaceAllUsesWith(NewVPV);
+          OriginalPlan.removeVPValueFor(UV);
+          OriginalPlan.addVPValue(UV, NewVPV);
+        }
+        NewPhi->insertBefore(VPhi);
+        VPhi->eraseFromParent();
+      }
+    }
+
+    // Remove dead instructions.
     for (auto I = OriginalVPBB->rbegin(), E = OriginalVPBB->rend(); I != E;) {
       VPRecipeBase *Ingredient = &*I++;
       VPInstruction *VPInst = dyn_cast<VPInstruction>(Ingredient);
       if (!VPInst)
         continue;
       Instruction *Instr = VPInst->getUnderlyingInstr();
 
       if (DeadInstructions.contains(Instr) || isa<DbgInfoIntrinsic>(Instr)) {
for (VPBlockBase *Base : RPOT) {
     // ingredients and fill a new VPBasicBlock.
     unsigned VPBBsForBB = 0;
     auto *FirstVPBBForBB = new VPBasicBlock(OriginalVPBB->getName());
     if (VPBB)
       VPBlockUtils::insertBlockAfter(FirstVPBBForBB, VPBB);
     else
       Plan->setEntry(FirstVPBBForBB);
     VPBB = FirstVPBBForBB;
     Builder.setInsertPoint(VPBB);
 
     // Introduce each ingredient into VPlan.
     for (auto I = OriginalVPBB->begin(), E = OriginalVPBB->end(); I != E;) {
       VPRecipeBase *Ingredient = &*I++;
+      if (isa<VPWidenIntOrFpInductionRecipe>(Ingredient)) {
+        auto *C = Ingredient->clone();
+        for (auto *Def : C->definedValues()) {
+          auto *UV = Def->getUnderlyingValue();
+          Plan->addVPValue(UV, Def);
+        }
+        for (unsigned I = 0, E = Ingredient->getNumOperands(); I != E; ++I)
+          C->setOperand(I, Plan->getOrAddVPValue(
+                               Ingredient->getOperand(I)->getLiveInIRValue()));
+        VPBB->appendRecipe(C);
+        continue;
+      }
       VPInstruction *VPInst = dyn_cast<VPInstruction>(Ingredient);
       Instruction *Instr =
           VPInst
               ? VPInst->getUnderlyingInstr()
               : cast<PHINode>(
                     cast<VPWidenPHIRecipe>(Ingredient)->getUnderlyingInstr());
 
       // First filter out irrelevant instructions, to ensure no recipes are

llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h

class VPRecipeBuilder {
   bool shouldWiden(Instruction *I, VFRange &Range) const;
 
   /// Check if the load or store instruction \p I should widened for \p
   /// Range.Start and potentially masked. Such instructions are handled by a
   /// recipe that takes an additional VPInstruction for the mask.
   VPRecipeBase *tryToWidenMemory(Instruction *I, VFRange &Range,
                                  VPlanPtr &Plan);
 
-  /// Check if an induction recipe should be constructed for \I. If so build and
-  /// return it. If not, return null.
-  VPWidenIntOrFpInductionRecipe *tryToOptimizeInductionPHI(PHINode *Phi,
-                                                           VPlan &Plan) const;
-
   /// Optimize the special case where the operand of \p I is a constant integer
   /// induction variable.
   VPWidenIntOrFpInductionRecipe *
   tryToOptimizeInductionTruncate(TruncInst *I, VFRange &Range,
                                  VPlan &Plan) const;
 
   /// Handle non-loop phi nodes. Return a VPValue, if all incoming values match
   /// or a new VPBlendRecipe otherwise. Currently all such phi nodes are turned
public:
 
   /// Check if an existing VPValue can be used for \p Instr or a recipe can be
   /// create for \p I withing the given VF \p Range. If an existing VPValue can
   /// be used or if a recipe can be created, return it. Otherwise return a
   /// VPRecipeOrVPValueTy with nullptr.
   VPRecipeOrVPValueTy tryToCreateWidenRecipe(Instruction *Instr, VFRange &Range,
                                              VPlanPtr &Plan);
 
+  /// Check if an induction recipe should be constructed for \I. If so build and
+  /// return it. If not, return null.
+  VPWidenIntOrFpInductionRecipe *tryToOptimizeInductionPHI(PHINode *Phi,
+                                                           VPlan &Plan) const;
+
   /// 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;

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

if (auto *Phi = dyn_cast<PHINode>(Inst)) {
 
       // Build VPInstruction for any arbitraty Instruction without specific
       // representation in VPlan.
       NewVPV = cast<VPInstruction>(
           VPIRBuilder.createNaryOp(Inst->getOpcode(), VPOperands, Inst));
     }
 
     IRDef2VPValue[Inst] = NewVPV;
+    Plan.addVPValue(Inst, NewVPV);
   }
 }
 
 // Main interface to build the plain CFG.
 VPRegionBlock *PlainCFGBuilder::buildPlainCFG() {
   // 1. Create the Top Region. It will be the parent of all VPBBs.
   TopRegion = new VPRegionBlock("TopRegion", false /*isReplicator*/);
 

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

for (auto I = VPBB->begin(), E = VPBB->end(); I != E;) {
       if (auto *VPPhi = dyn_cast<VPWidenPHIRecipe>(Ingredient)) {
         auto *Phi = cast<PHINode>(VPPhi->getUnderlyingValue());
         InductionDescriptor II = Inductions.lookup(Phi);
         if (II.getKind() == InductionDescriptor::IK_IntInduction ||
             II.getKind() == InductionDescriptor::IK_FpInduction) {
           VPValue *Start = Plan->getOrAddVPValue(II.getStartValue());
           NewRecipe = new VPWidenIntOrFpInductionRecipe(Phi, Start, nullptr);
         } else {
+          Plan->removeVPValueFor(Phi);
           Plan->addVPValue(Phi, VPPhi);
           continue;
         }
       } else {
         assert(isa<VPInstruction>(Ingredient) &&
                "only VPInstructions expected here");
         assert(!isa<PHINode>(Inst) && "phis should be handled above");
         // Create VPWidenMemoryInstructionRecipe for loads and stores.

llvm/unittests/Transforms/Vectorize/VPlanTest.cpp

struct VPDoubleValueDef : public VPRecipeBase {
   VPDoubleValueDef(ArrayRef<VPValue *> Operands) : VPRecipeBase(99, Operands) {
     new VPValue(nullptr, this);
     new VPValue(nullptr, this);
   }
 
   void execute(struct VPTransformState &State) override{};
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override {}
+
+  VPRecipeBase *clone() override { return nullptr; }
 };
 
 TEST(VPDoubleValueDefTest, traverseUseLists) {
   // Check that the def-use chains of a multi-def can be traversed in both
   // directions.
 
   // Create a new VPDef which defines 2 values and has 2 operands.
   VPInstruction Op0(20, {});