[VPlan] Use VPDef for VPInterleaveRecipe.

[fhahn]

Summary

This patch turns updates VPInterleaveRecipe to manage the values it defines
using VPDef. The VPValue is used during VPlan construction and
codegeneration instead of the plain IR reference where possible.

[fhahn]

Update after VPDef does not inherit from VPUser directly.

[fhahn]

ping

[gilr]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8387

Could you elaborate on why applying the interleave groups is moved back to VPlan creation?

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8387

The current handling (create recipes for each instruction and remove & replace them with a single interleave recipe later) seems like a work-around and now that we can manage the VPValues for the members of the interleave groups directly, I think it makes sense to directly create them along with the other recipes.

Unfortunately this requires a bit more extra logic to skip interleave groups members when recording the sink-after points, which is not great. But I think this will go away in the future, if we start by building an initial VPlan and gradually lower to specialized recipes.

But I can also keep the VPInterleaveRecipe creation at the original position, if you prefer.

[gilr]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8387

Unfortunately this requires a bit more extra logic to skip interleave groups members when recording the sink-after points, which is not great.

Right. This dependence between sink-after and interleave groups which translates to careful bookkeeping is why LV applies them as ordered VPlan-VPlan transformations. Ayal presented this change at the 2017 Dev. Meeting as a motivating example for the general direction of an initial trivial VPlan gradually & immediately transformed as decisions are taken, replacing LV's decision-recording maps which make it difficult to compose decisions.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8387

I have a few patches to get us roughly there and D90712 applies sink-after before lowering to specialized recipes, which makes the recording of recipes redundant. So my preference would be to keep thing as-is in the current patch. But as I said I am more than happy to update the patch to do it the 'old' way for now if you think that's preferable.

[gilr]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8387

But as I said I am more than happy to update the patch to do it the 'old' way for now if you think that's preferable.

I think so, to avoid the bookkeeping and keep the patch's scope minimal.

[fhahn]

Thanks Gil! I restored the original code for creating/inserting VPInterleaveRecipe, to reduce diff.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8387

Done, its much cleaner now :)

[gilr]

LGTM!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8387

Indeed :), Tx Florian!

[john.brawn]

This commit is causing the following

int example(int n, int *arr)
{
 int ret = 0;

 for( int i = 0; i < n; i += 2 ) {
  ret = arr[i+1] + arr[i] + ret;
 }

 return ret;
}

to hit an assertion failure when compiled with --target=arm-none-eabi -march=armv8.1-m.main+mve -O2:

llvm-project/llvm/lib/Transforms/Vectorize/VPlan.h:1770: llvm::VPValue* llvm::VPlan::getVPValue(llvm::Value*): Assertion `Value2VPValue.count(V) && "Value does not exist in VPlan"' failed.

with the backtrace showing that the assert was hit in llvm::LoopVectorizationPlanner::adjustRecipesForInLoopReductions.

[fhahn]

In D90562#2477665, @john.brawn wrote:

This commit is causing the following

int example(int n, int *arr)
{
 int ret = 0;

 for( int i = 0; i < n; i += 2 ) {
  ret = arr[i+1] + arr[i] + ret;
 }

 return ret;
}

to hit an assertion failure when compiled with --target=arm-none-eabi -march=armv8.1-m.main+mve -O2:

llvm-project/llvm/lib/Transforms/Vectorize/VPlan.h:1770: llvm::VPValue* llvm::VPlan::getVPValue(llvm::Value*): Assertion `Value2VPValue.count(V) && "Value does not exist in VPlan"' failed.

with the backtrace showing that the assert was hit in llvm::LoopVectorizationPlanner::adjustRecipesForInLoopReductions.

Thanks for the report! Should be fixed in 8a47e6252ad43a2eb3238f9b36394571ba13f4a9

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

public:
   /// Construct the vector value of a scalarized value \p V one lane at a time.
   void packScalarIntoVectorValue(Value *V, const VPIteration &Instance);
 
   /// Try to vectorize interleaved access group \p Group 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 vectorizeInterleaveGroup(const InterleaveGroup<Instruction> *Group,
+                                ArrayRef<VPValue *> VPDefs,
                                 VPTransformState &State, VPValue *Addr,
                                 ArrayRef<VPValue *> StoredValues,
                                 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.

 //   }
 // To:
 //   %R_G.vec = shuffle %R.vec, %G.vec, <0, 1, 2, ..., 7>
 //   %B_U.vec = shuffle %B.vec, undef, <0, 1, 2, 3, u, u, u, u>
 //   %interleaved.vec = shuffle %R_G.vec, %B_U.vec,
 //        <0, 4, 8, 1, 5, 9, 2, 6, 10, 3, 7, 11>    ; Interleave R,G,B elements
 //   store <12 x i32> %interleaved.vec              ; Write 4 tuples of R,G,B
 void InnerLoopVectorizer::vectorizeInterleaveGroup(
-    const InterleaveGroup<Instruction> *Group, VPTransformState &State,
-    VPValue *Addr, ArrayRef<VPValue *> StoredValues, VPValue *BlockInMask) {
+    const InterleaveGroup<Instruction> *Group, ArrayRef<VPValue *> VPDefs,
+    VPTransformState &State, VPValue *Addr, ArrayRef<VPValue *> StoredValues,
+    VPValue *BlockInMask) {
   Instruction *Instr = Group->getInsertPos();
   const DataLayout &DL = Instr->getModule()->getDataLayout();
 
   // Prepare for the vector type of the interleaved load/store.
   Type *ScalarTy = getMemInstValueType(Instr);
   unsigned InterleaveFactor = Group->getFactor();
   assert(!VF.isScalable() && "scalable vectors not yet supported.");
   auto *VecTy = VectorType::get(ScalarTy, VF * InterleaveFactor);
for (unsigned Part = 0; Part < UF; Part++) {
         NewLoad = Builder.CreateAlignedLoad(VecTy, AddrParts[Part],
                                             Group->getAlign(), "wide.vec");
       Group->addMetadata(NewLoad);
       NewLoads.push_back(NewLoad);
     }
 
     // For each member in the group, shuffle out the appropriate data from the
     // wide loads.
+    unsigned J = 0;
     for (unsigned I = 0; I < InterleaveFactor; ++I) {
       Instruction *Member = Group->getMember(I);
 
       // Skip the gaps in the group.
       if (!Member)
         continue;
 
       assert(!VF.isScalable() && "scalable vectors not yet supported.");
       auto StrideMask =
           createStrideMask(I, InterleaveFactor, VF.getKnownMinValue());
       for (unsigned Part = 0; Part < UF; Part++) {
         Value *StridedVec = Builder.CreateShuffleVector(
             NewLoads[Part], StrideMask, "strided.vec");
 
         // If this member has different type, cast the result type.
         if (Member->getType() != ScalarTy) {
           assert(!VF.isScalable() && "VF is assumed to be non scalable.");
           VectorType *OtherVTy = VectorType::get(Member->getType(), VF);
           StridedVec = createBitOrPointerCast(StridedVec, OtherVTy, DL);
         }
 
         if (Group->isReverse())
           StridedVec = reverseVector(StridedVec);
 
-        VectorLoopValueMap.setVectorValue(Member, Part, StridedVec);
+        State.set(VPDefs[J], Member, StridedVec, Part);
       }
+      ++J;
     }
     return;
   }
 
   // The sub vector type for current instruction.
   assert(!VF.isScalable() && "VF is assumed to be non scalable.");
   auto *SubVT = VectorType::get(ScalarTy, VF);
 
for (auto *Predecessor : predecessors(BB)) {
     }
 
     BlockMask = Builder.createOr(BlockMask, EdgeMask);
   }
 
   return BlockMaskCache[BB] = BlockMask;
 }
 
-VPWidenMemoryInstructionRecipe *
-VPRecipeBuilder::tryToWidenMemory(Instruction *I, VFRange &Range,
+VPRecipeBase *VPRecipeBuilder::tryToWidenMemory(Instruction *I, VFRange &Range,
                                                 VPlanPtr &Plan) {
   assert((isa<LoadInst>(I) || isa<StoreInst>(I)) &&
          "Must be called with either a load or store");
 
   auto willWiden = [&](ElementCount VF) -> bool {
     if (VF.isScalar())
       return false;
     LoopVectorizationCostModel::InstWidening Decision =
         CM.getWideningDecision(I, VF);
for (InterleaveGroup<Instruction> *IG : IAI.getInterleaveGroups()) {
     if (!getDecisionAndClampRange(applyIG, Range))
       continue;
     InterleaveGroups.insert(IG);
     for (unsigned i = 0; i < IG->getFactor(); i++)
       if (Instruction *Member = IG->getMember(i))
         RecipeBuilder.recordRecipeOf(Member);
   };
 
   // ---------------------------------------------------------------------------
   // 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>();
   VPBasicBlock *VPBB = new VPBasicBlock("Pre-Entry");
   Plan->setEntry(VPBB);
VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
   for (auto IG : InterleaveGroups) {
     auto *Recipe = cast<VPWidenMemoryInstructionRecipe>(
         RecipeBuilder.getRecipe(IG->getInsertPos()));
     SmallVector<VPValue *, 4> StoredValues;
     for (unsigned i = 0; i < IG->getFactor(); ++i)
       if (auto *SI = dyn_cast_or_null<StoreInst>(IG->getMember(i)))
         StoredValues.push_back(Plan->getOrAddVPValue(SI->getOperand(0)));
 
-    (new VPInterleaveRecipe(IG, Recipe->getAddr(), StoredValues,
-                            Recipe->getMask()))
-        ->insertBefore(Recipe);
-
+    auto *VPIG = new VPInterleaveRecipe(IG, Recipe->getAddr(), StoredValues,
+                                        Recipe->getMask());
+    VPIG->insertBefore(Recipe);
+    unsigned J = 0;
     for (unsigned i = 0; i < IG->getFactor(); ++i)
       if (Instruction *Member = IG->getMember(i)) {
         if (!Member->getType()->isVoidTy()) {
           VPValue *OriginalV = Plan->getVPValue(Member);
           Plan->removeVPValueFor(Member);
-          OriginalV->replaceAllUsesWith(Plan->getOrAddVPValue(Member));
+          OriginalV->replaceAllUsesWith(VPIG->getVPValue(J));
+          J++;
         }
         RecipeBuilder.getRecipe(Member)->eraseFromParent();
       }
   }
 
   // Adjust the recipes for any inloop reductions.
   if (Range.Start.isVector())
     adjustRecipesForInLoopReductions(Plan, RecipeBuilder);
for (unsigned In = 0; In < NumIncoming; ++In) {
     }
   }
   for (unsigned Part = 0; Part < State.UF; ++Part)
     State.ValueMap.setVectorValue(Phi, Part, Entry[Part]);
 }
 
 void VPInterleaveRecipe::execute(VPTransformState &State) {
   assert(!State.Instance && "Interleave group being replicated.");
-  State.ILV->vectorizeInterleaveGroup(IG, State, getAddr(), getStoredValues(),
-                                      getMask());
+  State.ILV->vectorizeInterleaveGroup(IG, definedValues(), State, getAddr(),
+                                      getStoredValues(), 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(getVecOp(), Part);
     if (VPValue *Cond = getCondOp()) {

llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h

class VPRecipeBuilder {
   /// Check if \p I can be widened at the start of \p Range and possibly
   /// decrease the range such that the returned value holds for the entire \p
   /// Range. The function should not be called for memory instructions or calls.
   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.
-  VPWidenMemoryInstructionRecipe *
-  tryToWidenMemory(Instruction *I, VFRange &Range, VPlanPtr &Plan);
+  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) const;
 
   /// Optimize the special case where the operand of \p I is a constant integer
   /// induction variable.
   VPWidenIntOrFpInductionRecipe *

llvm/lib/Transforms/Vectorize/VPlan.h

public:
   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. The first operand of a
 /// VPInterleave recipe is the address, followed by the stored values, followed
 /// by an optional mask.
-class VPInterleaveRecipe : public VPRecipeBase, public VPUser {
+class VPInterleaveRecipe : public VPRecipeBase, public VPDef, public VPUser {
   const InterleaveGroup<Instruction> *IG;
 
   bool HasMask = false;
 
 public:
   VPInterleaveRecipe(const InterleaveGroup<Instruction> *IG, VPValue *Addr,
                      ArrayRef<VPValue *> StoredValues, VPValue *Mask)
-      : VPRecipeBase(VPInterleaveSC), VPUser({Addr}), IG(IG) {
+      : VPRecipeBase(VPInterleaveSC), VPUser(Addr), IG(IG) {
+    for (unsigned i = 0; i < IG->getFactor(); ++i)
+      if (Instruction *I = IG->getMember(i)) {
+        if (I->getType()->isVoidTy())
+          continue;
+        new VPValue(I, this);
+      }
+
     for (auto *SV : StoredValues)
       addOperand(SV);
     if (Mask) {
       HasMask = true;
       addOperand(Mask);
     }
   }
   ~VPInterleaveRecipe() override = default;

llvm/lib/Transforms/Vectorize/VPlan.cpp

if (EnableVPlanNativePath && (CBV = getCondBit())) {
     ReplaceInstWithInst(CurrentTerminator, CondBr);
   }
 
   LLVM_DEBUG(dbgs() << "LV: filled BB:" << *NewBB);
 }
 
 void VPBasicBlock::dropAllReferences(VPValue *NewValue) {
   for (VPRecipeBase &R : Recipes) {
-    if (auto *VPV = R.toVPValue())
-      VPV->replaceAllUsesWith(NewValue);
+    if (VPValue *Def = R.toVPValue())
+      Def->replaceAllUsesWith(NewValue);
+    else if (auto *IR = dyn_cast<VPInterleaveRecipe>(&R)) {
+      for (auto *Def : IR->definedValues())
+        Def->replaceAllUsesWith(NewValue);
+    }
 
     if (auto *User = R.toVPUser())
       for (unsigned I = 0, E = User->getNumOperands(); I != E; I++)
         User->setOperand(I, NewValue);
   }
 }
 
 void VPRegionBlock::dropAllReferences(VPValue *NewValue) {

llvm/unittests/Transforms/Vectorize/VPlanTest.cpp

 //===- llvm/unittests/Transforms/Vectorize/VPlanTest.cpp - VPlan tests ----===//
 //
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "../lib/Transforms/Vectorize/VPlan.h"
+#include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "gtest/gtest.h"
 #include <string>
 
 namespace llvm {
 namespace {
 
TEST(VPRecipeTest, CastVPBlendRecipeToVPUser) {
   delete Phi;
 }
 
 TEST(VPRecipeTest, CastVPInterleaveRecipeToVPUser) {
   LLVMContext C;
 
   VPValue Addr;
   VPValue Mask;
-  VPInterleaveRecipe Recipe(nullptr, &Addr, {}, &Mask);
+  InterleaveGroup<Instruction> IG(4, false, Align(4));
+  VPInterleaveRecipe Recipe(&IG, &Addr, {}, &Mask);
   EXPECT_TRUE(isa<VPUser>(&Recipe));
   VPRecipeBase *BaseR = &Recipe;
   EXPECT_TRUE(isa<VPUser>(BaseR));
   EXPECT_EQ(&Recipe, BaseR->toVPUser());
 }
 
 TEST(VPRecipeTest, CastVPReplicateRecipeToVPUser) {
   LLVMContext C;