[VPlan] Representing backedge def-use feeding reduction phis.

[fhahn]

Summary

This patch updates the code handling reduction recipes to also keep
track of the incoming value from the latch in the recipe. This is needed
to model the def-use chains completely in VPlan, so that it is possible
to replace the incoming value with an arbitrary VPValue.

[fhahn]

Rebase & ping.

I just pushed a small patch that prints prints VPWidenPHIRecipe using the VPValue operands, if there are operands for all incoming values (a6b06b785cda1bb94dd05f29d66892ccb44cf0cd).

Now the change in this patch (adding the incoming value from the loop backedge) is visible in the printing.

[fhahn]

Rebased. I also put up 2 additional patches that make use of the operand for the incoming value of the backedge in more places: D100102 & D100113.

[fhahn]

ping :)

[fhahn]

Update comment to clarify that the first operand of a VPWidenPHIRecipe for a reduction is the start value and the second operand is the incoming value from the backedge.

[Ayal]

Looks good to me!
Adding a couple of nits and thoughts.
Perhaps "[VPlan] Representing backedge def-use feeding reduction phi's" may be a more accurate title - "incoming" also (more-so?) applies to the operand from the preheader.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4323–4328

nit: worth hoisting LoopVectorLatch = LI->getLoopFor(LoopVectorBody)->getLoopLatch() here.
(admittedly independent of this patch)

4329–4330

nit: can continue to obtain the first-and-only VPValue defined by PhiR, by calling getVPValue() as before, which defaults to getVPValue(0), right?

8970

Worth a comment here explaining that source and destination of cross-iteration dependences are marked here in order to wire their recipes in VPlan later.

Current implementation looks fine. Raising a possible alternative, if preferred?
The wiring of header phi's could be delegated to RecipeBuilder: have it collect the 'partially constructed' widenPhiRecipes of reductions as it creates them, into a local "PhiRecipesToFix", along with recording the recipes of their latched-operands (only). Then have RecipeBuilder::fixHeaderPhi's() to complete the construction of its PhiRecipesToFix, via their underlying Phi's.

llvm/lib/Transforms/Vectorize/VPlan.h

997

Worth supplying another interface to retrieve 'preheadered' and 'latched' operands of a header phi recipe (by setting them as 0 and 1 enum values?) to increase the readability of 'getOperand(0)' and 'getOperand(1)'?

llvm/test/Transforms/LoopVectorize/vplan-printing.ll

82

Clean up the TODO in VPlan.cpp/ VPWidenPHIRecipe::print() ?

[fhahn]

Updated title, move logic to track phis-to-fix and fixup to VPRecipeBuilder.

[fhahn]

Add & use VPWidenRecipe::getBackedgeValue.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4323–4328

I'll do that in a separate commit.

4329–4330

Yep, changed it back.

8970

Thanks for the suggestion. Doing the tracking and fixup directly in VPRecipeBuilder seems preferable. I updated the patch and added the additional comments to the new code.

llvm/lib/Transforms/Vectorize/VPlan.h

997

I added a VPWidenPHIRecipe::getBackedgeValue(), similar to getStartValue. WDYT?

llvm/test/Transforms/LoopVectorize/vplan-printing.ll

82

Unfortunately there are still cases where we do not track the value from the back-edge (like first-order recurrences).

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4323–4328

Done in cb96d802d4d7

[fhahn]

rebased after cb96d802d4d7

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8771

can alternatively traverse over R : PhiRecipesToFix, and use R's underlying ingredient to retrieve its PN, etc.

8886

Instead of recording the recipe of Phi, which the next line creates, can do

auto *PhiRecipe = new VPWidenPHIRecipe(Phi, RdxDesc, *StartV);
PhiRecipesToFix.push_back(PhiRecipe);
return toVPRecipeResult(PhiRecipe);

llvm/lib/Transforms/Vectorize/VPlan.h

997

Great!

llvm/test/Transforms/LoopVectorize/vplan-printing.ll

82

Ah, right.

[fhahn]

Track VPWidenPhiRecipes directly in PhisToFix.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8771

excellent idea, updated!

[Ayal]

Adding a couple of related thoughts. Thanks!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8775

while we're here: it may be useful to have a "getVPSingleValue()" which would take care of the assert (and the redundant 0)? In any case, the assert deserves an error message.

8889

while we're here: the use of toVPRecipeResult() and VPRecipeOrVPValueTy, if intended to solve D44800 Blend issue only, seem like an overkill - BlendRecipe pass-throughs a single-operand phi, having a full (null) mask; so it should be easy(ier) to have it pass-through an(y) operand also for a phi having multiple identical operands. I.e., tryToBlend() can always return a VPRecipe. Better to discuss this on a related review, if there is one available?

[fhahn]

In D99294#2720770, @Ayal wrote:

Adding a couple of related thoughts. Thanks!

Thanks! This also depends on D99293, but I think I'll re-order the patches a bit tomorrow so we can use phis() from D100101 from the start.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8775

Yes that sounds good. I'll push that as a separate commit before landing this change.

8889

Sure, let me take another look. Conceptually I think having a way to return a simplified value is convenient and cleaner, but it might be overkill for now.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8775

Added getVPSingleValue in a0e1313c2329

[fhahn]

update to use getVPSingleValue

[fhahn]

rebased ahead of committing

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8882

nit: "// Record the [PHI and the] incoming value"

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8882

Thanks, should be fixed in 75b9997760c6

[uabelho]

Hi,

I wrote a PR about a LV-crash that started happening with this patch:
https://bugs.llvm.org/show_bug.cgi?id=50298

[fhahn]

In D99294#2750159, @uabelho wrote:

Hi,

I wrote a PR about a LV-crash that started happening with this patch:
https://bugs.llvm.org/show_bug.cgi?id=50298

Thanks for the report! The problem was that we did not record the recipe if a simplified VPValue is used. I pushed faebc6bf108e to fix it for now, but as Ayal pointed out, it might be worth the simplify the handling, which I'll look into separately.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::fixReduction(VPWidenPHIRecipe *PhiR,
   Type *VecTy = State.get(LoopExitInstDef, 0)->getType();
 
   // Wrap flags are in general invalid after vectorization, clear them.
   clearReductionWrapFlags(RdxDesc, State);
 
   // Fix the vector-loop phi.
 
   // Reductions do not have to start at zero. They can start with
   // any loop invariant values.
-  BasicBlock *OrigLatch = OrigLoop->getLoopLatch();
-  Value *OrigLoopVal = OrigPhi->getIncomingValueForBlock(OrigLatch);
   BasicBlock *VectorLoopLatch = LI->getLoopFor(LoopVectorBody)->getLoopLatch();
 
   bool IsOrdered = State.VF.isVector() && IsInLoopReductionPhi &&
                    useOrderedReductions(RdxDesc);
 
   for (unsigned Part = 0; Part < UF; ++Part) {
     if (IsOrdered && Part > 0)
       break;
     Value *VecRdxPhi = State.get(PhiR->getVPSingleValue(), Part);
-    Value *Val = State.get(State.Plan->getVPValue(OrigLoopVal), Part);
+    Value *Val = State.get(PhiR->getBackedgeValue(), Part);
     if (IsOrdered)
-      Val = State.get(State.Plan->getVPValue(OrigLoopVal), UF - 1);
+      Val = State.get(PhiR->getBackedgeValue(), UF - 1);
+
     cast<PHINode>(VecRdxPhi)->addIncoming(Val, VectorLoopLatch);
   }
 
   // Before each round, move the insertion point right between
   // the PHIs and the values we are going to write.
   // This allows us to write both PHINodes and the extractelement
   // instructions.
   Builder.SetInsertPoint(&*LoopMiddleBlock->getFirstInsertionPt());
VPWidenRecipe *VPRecipeBuilder::tryToWiden(Instruction *I,
 
   if (!IsVectorizableOpcode(I->getOpcode()))
     return nullptr;
 
   // Success: widen this instruction.
   return new VPWidenRecipe(*I, make_range(Operands.begin(), Operands.end()));
 }
 
+void VPRecipeBuilder::fixHeaderPhis() {
+  BasicBlock *OrigLatch = OrigLoop->getLoopLatch();
+  for (VPWidenPHIRecipe *R : PhisToFix) {
+    auto *PN = cast<PHINode>(R->getUnderlyingValue());
+    VPRecipeBase *IncR =
+        getRecipe(cast<Instruction>(PN->getIncomingValueForBlock(OrigLatch)));
+    R->addOperand(IncR->getVPSingleValue());
+  }
+}
+
 VPBasicBlock *VPRecipeBuilder::handleReplication(
     Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
     VPlanPtr &Plan) {
   bool IsUniform = LoopVectorizationPlanner::getDecisionAndClampRange(
       [&](ElementCount VF) { return CM.isUniformAfterVectorization(I, VF); },
       Range);
 
   bool IsPredicated = LoopVectorizationPlanner::getDecisionAndClampRange(
if (auto Phi = dyn_cast<PHINode>(Instr)) {
     if ((Recipe = tryToOptimizeInductionPHI(Phi, Operands)))
       return toVPRecipeResult(Recipe);
 
     if (Legal->isReductionVariable(Phi)) {
       RecurrenceDescriptor &RdxDesc = Legal->getReductionVars()[Phi];
       assert(RdxDesc.getRecurrenceStartValue() ==
              Phi->getIncomingValueForBlock(OrigLoop->getLoopPreheader()));
       VPValue *StartV = Operands[0];
-      return toVPRecipeResult(new VPWidenPHIRecipe(Phi, RdxDesc, *StartV));
+
+      // Record the PHI and the incoming value from the backedge, so we can add
+      // the incoming value from the backedge after all recipes have been
+      // created.
+      auto *PhiRecipe = new VPWidenPHIRecipe(Phi, RdxDesc, *StartV);
+      PhisToFix.push_back(PhiRecipe);
+      recordRecipeOf(cast<Instruction>(
+          Phi->getIncomingValueForBlock(OrigLoop->getLoopLatch())));
+      return toVPRecipeResult(PhiRecipe);
     }
 
     return toVPRecipeResult(new VPWidenPHIRecipe(Phi));
   }
 
   if (isa<TruncInst>(Instr) &&
       (Recipe = tryToOptimizeInductionTruncate(cast<TruncInst>(Instr), Operands,
                                                Range, *Plan)))
VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
   // ---------------------------------------------------------------------------
 
   // Mark instructions we'll need to sink later and their targets as
   // ingredients whose recipe we'll need to record.
   for (auto &Entry : SinkAfter) {
     RecipeBuilder.recordRecipeOf(Entry.first);
     RecipeBuilder.recordRecipeOf(Entry.second);
   }
   for (auto &Reduction : CM.getInLoopReductionChains()) {
     PHINode *Phi = Reduction.first;
     RecurKind Kind = Legal->getReductionVars()[Phi].getRecurrenceKind();
     const SmallVector<Instruction *, 4> &ReductionOperations = Reduction.second;
 
     RecipeBuilder.recordRecipeOf(Phi);
     for (auto &R : ReductionOperations) {
       RecipeBuilder.recordRecipeOf(R);
       // For min/max reducitons, where we have a pair of icmp/select, we also
for (Instruction &I : BB->instructionsWithoutDebug()) {
       if (NextVPBB != VPBB) {
         VPBB = NextVPBB;
         VPBB->setName(BB->hasName() ? BB->getName() + "." + Twine(VPBBsForBB++)
                                     : "");
       }
     }
   }
 
+  RecipeBuilder.fixHeaderPhis();
+
   // Discard empty dummy pre-entry VPBasicBlock. Note that other VPBasicBlocks
   // may also be empty, such as the last one VPBB, reflecting original
   // basic-blocks with no recipes.
   VPBasicBlock *PreEntry = cast<VPBasicBlock>(Plan->getEntry());
   assert(PreEntry->empty() && "Expecting empty pre-entry block.");
   VPBlockBase *Entry = Plan->setEntry(PreEntry->getSingleSuccessor());
   VPBlockUtils::disconnectBlocks(PreEntry, Entry);
   delete PreEntry;

llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h

class VPRecipeBuilder {
   EdgeMaskCacheTy EdgeMaskCache;
   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.
   DenseMap<Instruction *, VPRecipeBase *> Ingredient2Recipe;
 
+  /// Cross-iteration reduction phis for which we need to add the incoming value
+  /// from the backedge after all recipes have been created.
+  SmallVector<VPWidenPHIRecipe *, 4> PhisToFix;
+
   /// 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.
public:
   /// is predicated. \return \p VPBB augmented with this new recipe if \p I is
   /// not predicated, otherwise \return a new VPBasicBlock that succeeds the new
   /// Region. Update the packing decision of predicated instructions if they
   /// feed \p I. Range.End may be decreased to ensure same recipe behavior from
   /// \p Range.Start to \p Range.End.
   VPBasicBlock *handleReplication(
       Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
       VPlanPtr &Plan);
+
+  /// Add the incoming values from the backedge to reduction cross-iteration
+  /// phis.
+  void fixHeaderPhis();
 };
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H

llvm/lib/Transforms/Vectorize/VPlan.h

#endif
   }
   const TruncInst *getTruncInst() const {
     return dyn_cast_or_null<TruncInst>(getVPValue(0)->getUnderlyingValue());
   }
 };
 
 /// A recipe for handling all phi nodes except for integer and FP inductions.
 /// For reduction PHIs, RdxDesc must point to the corresponding recurrence
-/// descriptor and the start value is the first operand of the recipe.
-/// In the VPlan native path, all incoming VPValues & VPBasicBlock pairs are
-/// managed in the recipe directly.
+/// descriptor, the start value is the first operand of the recipe and the
+/// incoming value from the backedge is the second operand. In the VPlan native
+/// path, all incoming VPValues & VPBasicBlock pairs are managed in the recipe
+/// directly.
 class VPWidenPHIRecipe : public VPRecipeBase, public VPValue {
   /// Descriptor for a reduction PHI.
   RecurrenceDescriptor *RdxDesc = nullptr;
 
   /// List of incoming blocks. Only used in the VPlan native path.
   SmallVector<VPBasicBlock *, 2> IncomingBlocks;
 
 public:
void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 #endif
 
   /// Returns the start value of the phi, if it is a reduction.
   VPValue *getStartValue() {
     return getNumOperands() == 0 ? nullptr : getOperand(0);
   }
 
+  /// Returns the incoming value from the loop backedge, if it is a reduction.
+  VPValue *getBackedgeValue() {
+    assert(RdxDesc && "second incoming value is only guaranteed to be backedge "
+                      "value for reductions");
+    return getOperand(1);
+  }
+
   /// Adds a pair (\p IncomingV, \p IncomingBlock) to the phi.
   void addIncoming(VPValue *IncomingV, VPBasicBlock *IncomingBlock) {
     addOperand(IncomingV);
     IncomingBlocks.push_back(IncomingBlock);
   }
 
   /// Returns the \p I th incoming VPValue.
   VPValue *getIncomingValue(unsigned I) { return getOperand(I); }

llvm/test/Transforms/LoopVectorize/vplan-printing.ll

for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 define float @print_reduction(i64 %n, float* noalias %y) {
 ; CHECK-LABEL: Checking a loop in "print_reduction"
 ; CHECK:      VPlan 'Initial VPlan for VF={4},UF>=1' {
 ; CHECK-NEXT: for.body:
 ; CHECK-NEXT:   WIDEN-INDUCTION %iv = phi %iv.next, 0
-; CHECK-NEXT:   WIDEN-PHI %red = phi %red.next, 0.000000e+00
+; CHECK-NEXT:   WIDEN-PHI ir<%red> = phi ir<0.000000e+00>, ir<%red.next>
 ; CHECK-NEXT:   CLONE ir<%arrayidx> = getelementptr ir<%y>, ir<%iv>
 ; CHECK-NEXT:   WIDEN ir<%lv> = load ir<%arrayidx>
 ; CHECK-NEXT:   REDUCE ir<%red.next> = ir<%red> + reduce.fadd (ir<%lv>)
 ; CHECK-NEXT: No successors
 ; CHECK-NEXT: }
 ;
 entry:
   br label %for.body