[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

8874

nit: can we use make_early_inc_range here isntead?

8885

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

8885

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

for (Instruction *I : DeadInstructions)
     SinkAfter.erase(I);
 
   DenseMap<Instruction *, VPInstruction *> Inst2VPInst;
   for (auto &Entry : SinkAfter) {
     Inst2VPInst[Entry.first] = nullptr;
     Inst2VPInst[Entry.second] = nullptr;
   }
 
+  VPRecipeBuilder RecipeBuilder(OrigLoop, TLI, Legal, CM, PSE, Builder);
+
+  // First, try to convert VPInstructions to recipes, if the conversion does not
+  // depend on the VF. At the moment, only VPIntOrFpInductionRecipes are
+  // created here.
+  for (VPRecipeBase &R :
+       make_early_inc_range(*TopRegion->getEntryBasicBlock())) {
+    auto *VPhi = dyn_cast<VPWidenPHIRecipe>(&R);
+    if (!VPhi)
+      break;
+
+    auto *Phi = cast<PHINode>(VPhi->getUnderlyingValue());
+    if (auto *NewPhi = RecipeBuilder.tryToOptimizeInductionPHI(
+            Phi, ArrayRef<VPValue *>(R.op_begin(), R.op_end()))) {
+      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 from original VPlan.
   auto *DummyVal = new VPValue();
   OriginalPlan.addExternalDef(DummyVal);
   for (VPBlockBase *Base :
        depth_first<VPBlockBase *>(TopRegion->getEntryBasicBlock())) {
     VPBasicBlock *OriginalVPBB = Base->getEntryBasicBlock();
     for (VPRecipeBase &Ingredient :
          make_early_inc_range(reverse(*OriginalVPBB))) {
       VPInstruction *VPInst = dyn_cast<VPInstruction>(&Ingredient);
       if (!VPInst)
         continue;
       Instruction *Instr = VPInst->getUnderlyingInstr();
 
       if (DeadInstructions.contains(Instr) || isa<DbgInfoIntrinsic>(Instr)) {
         Ingredient.getVPValue()->replaceAllUsesWith(DummyVal);
         Ingredient.eraseFromParent();
       }
 
       auto Iter = Inst2VPInst.find(Instr);
       if (Iter != Inst2VPInst.end())
         Iter->second = VPInst;
     }
   }
 
   for (auto &Entry : SinkAfter) {
     VPRecipeBase *Sink = Inst2VPInst.find(Entry.first)->second;
     VPRecipeBase *Target = Inst2VPInst.find(Entry.second)->second;
     Sink->moveAfter(Target);
   }
VPlanPtr LoopVectorizationPlanner::convertToVPRecipes(VPlan &OriginalPlan,
   // ---------------------------------------------------------------------------
   // Build initial VPlan: Scan the body of the loop in a topological order to
   // 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>();
 
-  ReversePostOrderTraversal<VPBlockBase *> RPOT(
-      OriginalPlan.getEntry()->getEntryBasicBlock());
+  VPBasicBlock *Header = OriginalPlan.getEntry()->getEntryBasicBlock();
+  ReversePostOrderTraversal<VPBlockBase *> RPOT(Header);
 
   VPBasicBlock *VPBB = nullptr;
   for (VPBlockBase *Base : RPOT) {
     VPBasicBlock *OriginalVPBB = Base->getEntryBasicBlock();
 
     // Relevant instructions from basic block BB will be grouped into VPRecipe
     // 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++;
+      // First, clone & add the recipes introduced earlier.
+      if (isa<VPWidenIntOrFpInductionRecipe>(Ingredient)) {
+        auto *C = Ingredient->clone();
+        for (unsigned I = 0, E = C->getNumDefinedValues(); I != E; ++I) {
+          auto *NewDef = C->getVPValue(I);
+          auto *UV = NewDef->getUnderlyingValue();
+          Plan->addVPValue(UV, NewDef);
+          Ingredient->getVPValue(I)->replaceAllUsesWith(NewDef);
+        }
+        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, ArrayRef<VPValue *> Operands,
                                  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, ArrayRef<VPValue *> Operands) const;
-
   /// Optimize the special case where the operand of \p I is a constant integer
   /// induction variable.
   VPWidenIntOrFpInductionRecipe *
   tryToOptimizeInductionTruncate(TruncInst *I, ArrayRef<VPValue *> Operands,
                                  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,
                                              ArrayRef<VPValue *> Operands,
                                              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, ArrayRef<VPValue *> Operands) 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

for (auto *Phi : PhisToFix) {
     assert(IRDef2VPValue.count(Phi) && "Missing VPInstruction for PHINode.");
     VPValue *VPVal = IRDef2VPValue[Phi];
     assert(isa<VPWidenPHIRecipe>(VPVal) &&
            "Expected WidenPHIRecipe for phi node.");
     auto *VPPhi = cast<VPWidenPHIRecipe>(VPVal);
     assert(VPPhi->getNumOperands() == 0 &&
            "Expected VPInstruction with no operands.");
 
+    if (Phi->getParent() == TheLoop->getHeader()) {
+      VPPhi->addIncoming(getOrCreateVPOperand(Phi->getIncomingValueForBlock(
+                             TheLoop->getLoopPreheader())),
+                         BB2VPBB[TheLoop->getLoopPreheader()]);
+      for (BasicBlock *IncBlock : Phi->blocks()) {
+        if (IncBlock == TheLoop->getLoopPreheader())
+          continue;
+        VPPhi->addIncoming(
+            getOrCreateVPOperand(Phi->getIncomingValueForBlock(IncBlock)),
+            BB2VPBB[IncBlock]);
+      }
+      continue;
+    }
     for (unsigned I = 0; I != Phi->getNumOperands(); ++I)
       VPPhi->addIncoming(getOrCreateVPOperand(Phi->getIncomingValue(I)),
                          BB2VPBB[Phi->getIncomingBlock(I)]);
   }
 }
 
 // Create a new empty VPBasicBlock for an incoming BasicBlock or retrieve an
 // existing one if it was already created.
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.