[LV] Move reduction PHI node fixup to VPlan::execute (NFC).

[fhahn]

Summary

All information to fix-up the reduction phi nodes in the vectorized loop
is available in VPlan now. This patch moves the code to do so, to make
this clearer. Fixing up the loop exit value still relies on other
information and remains outside of VPlan for now.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9688

better turn on an IsOrdered bit inside VPReductionRecipe during its creation or planning, than during its execute? Admittedly goes back to D98435.

There are 3 types of reductions: (1) parallel lanes: each lane computes an independent partial-sum; (2) parallel parts: each vector computes an independent partial sum, in-loop within vectors but not across parts, and (3) serial: in-loop across vectors and parts, the header phi operates on a single scalar. Would be good to explicitly indicate which type of reduction is chosen, in both ReductionRecipe(s) and the header phi; it effects their code-gen.

llvm/lib/Transforms/Vectorize/VPlan.cpp

63

Defining a method of LVP inside VPlan.cpp seems odd, at best.

The use of a gating EnableStrictReductions knob (in contrast to a CM cost-based decision), belongs to Legal rather than CM or Planner? I.e., Legal should bail out from vectorizing a loop having an ordered reduction, when !EnableStrictReductions? Admittedly goes back to D98435.

892

Moving this to VPlan::execute is great!
Can use getSingleVPValue(), getBackedgeValue().
May be worth explaining that Val is first set per-part supporting parallel partial sums, either vector/per-lane (1) or scalar/per-part (2), and then set to last-part supporting serial reduction (3).
Admittedly goes back to D98435.

[fhahn]

Rebased and updated the code to check whether to use ordered reductions during codegen to get the VPReductionRecipe and check isOrdered on the reduction descriptr. This builds on the code to determine whether a VPWidenPHI is part of an in-loop reduction.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9688

better turn on an IsOrdered bit inside VPReductionRecipe during its creation or planning, than during its execute? Admittedly goes back to D98435.

I think we already have all the required information available with the existing pieces. I updated the patch to check isOrdered on the recurrence descriptor of the VPReductionRecipe and a helper to get the VPReductionRecipe for a VPWidenPHIRecipe, if there's any.

llvm/lib/Transforms/Vectorize/VPlan.cpp

63

Agreed! I updated the code to check isOrdered on the reduction recurrence descriptor directly during code generation. To do so, I evolved the isInLoopReduction helper to an getInLoopReduction member that returns the VPReductionRecipe, if there's one.

892

I rebased the code, and it now uses getVPSingleValue/getBackedgeValue. I can add the additional comments separately or in this change.

[fhahn]

Rebased after recent changes, should be much simpler now :)

[Ayal]

llvm/lib/Transforms/Vectorize/VPlan.cpp

880

Place this next to hooking up incoming of FOR header phi's above, or even fuse both into a common loop over header phi's? The isOrdered case does behave quite similar to FOR phi's.

[fhahn]

Merge FOR and reduction handling loops as suggested, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.cpp

880

done, thanks!

[Ayal]

llvm/lib/Transforms/Vectorize/VPlan.cpp

823

The isOrdered case does behave quite similar to FOR phi's.

How about having a common treatment, e.g.,

for (VPRecipeBase &R : Header->phis()) {
  auto *PhiR = dyn_cast<VPWidenPHIRecipe>(&R);
  if (!PhiR)
    continue;
  // For first-order recurrences and in-order reduction phis, only a single part
  // is generated, which provides the last part from the previous iteration.
  // Otherwise all UF parts are generated.
  bool IsOrdered = (isa<VPFirstOrderRecurrencePHIRecipe>(&R)
                    || cast<VPReductionPHIRecipe>(&R)->isOrdered());
  unsigned LastPartForNewPhi = IsOrdered ? 1 : State->UF;
  for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
    Value *VecPhi = State->get(PhiR->getVPSingleValue(), Part);
      // Or suffice State->get(PhiR, Part)?
    Value *Val = State->get(PhiR->getBackedgeValue(),
                            IsOrdered ? State->UF - 1 : Part);
    cast<PHINode>(VecPhi)->addIncoming(Val, VectorLatchBB);
  }

?

[fhahn]

Merge FOR & reduction phi handling as suggested, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.cpp

823

Looks good, updated with a small re-naming. of IsOrdered -> SinglePartNeeded and a check to limit to FOR and reduction PHIs only.

[Ayal]

Thanks! This looks good to me ;-)

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4309

nit: place above comment about start value where it belongs?

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4309

I'll move it to VPReductionPHIRecipe::execute, which creates & sets the start value.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

protected:
 
   /// Handle all cross-iteration phis in the header.
   void fixCrossIterationPHIs(VPTransformState &State);
 
   /// Create the exit value of first order recurrences in the middle block and
   /// update their users.
   void fixFirstOrderRecurrence(VPWidenPHIRecipe *PhiR, VPTransformState &State);
 
-  /// Fix a reduction cross-iteration phi. This is the second phase of
-  /// vectorizing this phi node.
+  /// Create code for the loop exit value of the reduction.
   void fixReduction(VPReductionPHIRecipe *Phi, VPTransformState &State);
 
   /// Clear NSW/NUW flags from reduction instructions if necessary.
   void clearReductionWrapFlags(const RecurrenceDescriptor &RdxDesc,
                                VPTransformState &State);
 
   /// Fixup the LCSSA phi nodes in the unique exit block.  This simply
   /// means we need to add the appropriate incoming value from the middle
void InnerLoopVectorizer::fixReduction(VPReductionPHIRecipe *PhiR,
 
   VPValue *LoopExitInstDef = State.Plan->getVPValue(LoopExitInst);
   // This is the vector-clone of the value that leaves the loop.
   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 *VectorLoopLatch = LI->getLoopFor(LoopVectorBody)->getLoopLatch();
-
-  unsigned LastPartForNewPhi = PhiR->isOrdered() ? 1 : UF;
-  for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
-    Value *VecRdxPhi = State.get(PhiR->getVPSingleValue(), Part);
-    Value *Val = State.get(PhiR->getBackedgeValue(), Part);
-    if (PhiR->isOrdered())
-      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());
 
   setDebugLocFromInst(LoopExitInst);
 
State.ILV->vectorizeInterleaveGroup(IG, definedValues(), State, getAddr(),
                                       getStoredValues(), getMask());
 }
 
 void VPReductionRecipe::execute(VPTransformState &State) {
   assert(!State.Instance && "Reduction being replicated.");
   Value *PrevInChain = State.get(getChainOp(), 0);
   for (unsigned Part = 0; Part < State.UF; ++Part) {
     RecurKind Kind = RdxDesc->getRecurrenceKind();
     bool IsOrdered = State.ILV->useOrderedReductions(*RdxDesc);
     Value *NewVecOp = State.get(getVecOp(), Part);
     if (VPValue *Cond = getCondOp()) {
       Value *NewCond = State.get(Cond, Part);
       VectorType *VecTy = cast<VectorType>(NewVecOp->getType());
       Constant *Iden = RecurrenceDescriptor::getRecurrenceIdentity(
           Kind, VecTy->getElementType(), RdxDesc->getFastMathFlags());
       Constant *IdenVec =
           ConstantVector::getSplat(VecTy->getElementCount(), Iden);

llvm/lib/Transforms/Vectorize/VPlan.cpp

raw_ostream &llvm::operator<<(raw_ostream &OS, const VPValue &V) {
   const VPInstruction *Instr = dyn_cast<VPInstruction>(&V);
   VPSlotTracker SlotTracker(
       (Instr && Instr->getParent()) ? Instr->getParent()->getPlan() : nullptr);
   V.print(OS, SlotTracker);
   return OS;
 }
 #endif
 
 Value *VPLane::getAsRuntimeExpr(IRBuilder<> &Builder,
                                 const ElementCount &VF) const {
   switch (LaneKind) {
   case VPLane::Kind::ScalableLast:
     // Lane = RuntimeVF - VF.getKnownMinValue() + Lane
     return Builder.CreateSub(getRuntimeVF(Builder, Builder.getInt32Ty(), VF),
                              Builder.getInt32(VF.getKnownMinValue() - Lane));
   case VPLane::Kind::First:
     return Builder.getInt32(Lane);
void VPlan::execute(VPTransformState *State) {
   // 2. Generate code in loop body.
   State->CFG.PrevVPBB = nullptr;
   State->CFG.PrevBB = VectorHeaderBB;
   State->CFG.LastBB = VectorLatchBB;
 
   for (VPBlockBase *Block : depth_first(Entry))
     Block->execute(State);
 
-  // Fix the latch value of the first-order recurrences in the vector loop. Only
-  // a single part is generated, regardless of the UF.
+  // Fix the latch value of reduction and first-order recurrences phis in the
+  // vector loop.
   VPBasicBlock *Header = Entry->getEntryBasicBlock();
   for (VPRecipeBase &R : Header->phis()) {
-    if (auto *FOR = dyn_cast<VPFirstOrderRecurrencePHIRecipe>(&R)) {
-      auto *VecPhi = cast<PHINode>(State->get(FOR, 0));
-
-      VPValue *PreviousDef = FOR->getBackedgeValue();
-      Value *Incoming = State->get(PreviousDef, State->UF - 1);
-      VecPhi->addIncoming(Incoming, VectorLatchBB);
+    auto *PhiR = dyn_cast<VPWidenPHIRecipe>(&R);
+    if (!PhiR || !(isa<VPFirstOrderRecurrencePHIRecipe>(&R) ||
+                   isa<VPReductionPHIRecipe>(&R)))
+      continue;
+    // For first-order recurrences and in-order reduction phis, only a single
+    // part is generated, which provides the last part from the previous
+    // iteration. Otherwise all UF parts are generated.
+    bool SinglePartNeeded = isa<VPFirstOrderRecurrencePHIRecipe>(&R) ||
+                            cast<VPReductionPHIRecipe>(&R)->isOrdered();
+    unsigned LastPartForNewPhi = SinglePartNeeded ? 1 : State->UF;
+    for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
+      Value *VecPhi = State->get(PhiR, Part);
+      Value *Val = State->get(PhiR->getBackedgeValue(),
+                              SinglePartNeeded ? State->UF - 1 : Part);
+      cast<PHINode>(VecPhi)->addIncoming(Val, VectorLatchBB);
     }
   }
 
   // Setup branch terminator successors for VPBBs in VPBBsToFix based on
   // VPBB's successors.
   for (auto VPBB : State->CFG.VPBBsToFix) {
     assert(EnableVPlanNativePath &&
            "Unexpected VPBBsToFix in non VPlan-native path");
void VPlan::execute(VPTransformState *State) {
   assert(Merged && "Could not merge last basic block with latch.");
   VectorLatchBB = LastBB;
 
   // We do not attempt to preserve DT for outer loop vectorization currently.
   if (!EnableVPlanNativePath)
     updateDominatorTree(State->DT, VectorPreHeaderBB, VectorLatchBB,
                         L->getExitBlock());
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD
 void VPlan::print(raw_ostream &O) const {
   VPSlotTracker SlotTracker(this);
 
   O << "VPlan '" << Name << "' {";
   for (const VPBlockBase *Block : depth_first(getEntry())) {
     O << '\n';
     Block->print(O, "", SlotTracker);
   }
   O << "}\n";
 }
 
 LLVM_DUMP_METHOD
 void VPlan::printDOT(raw_ostream &O) const {
   VPlanPrinter Printer(O, *this);
   Printer.dump();
 }
 
 LLVM_DUMP_METHOD
void VPReductionPHIRecipe::execute(VPTransformState &State) {
   assert(State.LI->getLoopFor(HeaderBB)->getHeader() == HeaderBB &&
          "recipe must be in the vector loop header");
   unsigned LastPartForNewPhi = isOrdered() ? 1 : State.UF;
   for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
     Value *EntryPart =
         PHINode::Create(VecTy, 2, "vec.phi", &*HeaderBB->getFirstInsertionPt());
     State.set(this, EntryPart, Part);
   }
+
+  // Reductions do not have to start at zero. They can start with
+  // any loop invariant values.
   VPValue *StartVPV = getStartValue();
   Value *StartV = StartVPV->getLiveInIRValue();
 
   Value *Iden = nullptr;
   RecurKind RK = RdxDesc.getRecurrenceKind();
   if (RecurrenceDescriptor::isMinMaxRecurrenceKind(RK)) {
     // MinMax reduction have the start value as their identify.
     if (ScalarPHI) {