[VPlan] Add VPReductionPHIRecipe (NFC).

[fhahn]

Summary

This patch is a first step towards splitting up VPWidenPHIRecipe into
separate recipes for the 3 distinct cases they model:

1. reduction phis,
2. first-order recurrence phis,
3. pointer induction phis.

This allows untangling the code generation and allows us to reduce the
reliance on LoopVectorizationCostModel during VPlan code generation.

Discussed/suggested in D100102, D100113, D104197.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4138–4139

use dyn_cast instead of isa&cast?

4334–4335

bool IsInLoopReductionPhi = PhiR->isInLoop()?

4348–4349

(unrelated to this patch, but:

• isOrdered() implies isInLoop()
• IsOrdered here should be IsOrderedAndVectorized
• another place worth defining LastPartForVecRdxPhi
• wonder what happens when isOrdered()&NotVectorized wires UF parts(?)

)

4752–4753

Drop Cost->isInLoopReduction, this now deals w/ FOR only

(wonder if FOR works well for VF=1, e.g., w/o sinkAfter(?))

4762–4763

Drop isFOR, we now know it is

4767

"above" >> "elsewhere"

8053

Are both PrevBB and VectorPreHeader needed?

llvm/lib/Transforms/Vectorize/VPlan.cpp

1140

IsOrdered applies to VF=1 as well, right? Rename variable to IsOrderedAndVectorized?

llvm/lib/Transforms/Vectorize/VPlan.h

308–315

Comment?

739–740

Introduce a base class common to all phi recipes to ask isa<> instead of isPhi?

Check range of SC's (from FirstPHI to LastPHI) instead of multiple ||'s, or make sure they compile down to a range check?

1062

VPWidenPHIRecipe(VPVID, VPDefID, Phi) constructor should be 'protected'? Else drop 'protected'.

1132

Implies reduction is also in-loop.

1147–1173

Add bool isInLoop()?

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

237

&& !isa<VPReductionPHIRecipe>(UI) ?

llvm/lib/Transforms/Vectorize/VPlanValue.h

100

keep lexical order?
or keep all Phi's together?

329

ditto

[kmclaughlin]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4349

Hi @fhahn, I recently created D104533 to fix ordered reductions where the VF = 1. After this change, the State.VF.isVector() check here (and in VPReductionPHIRecipe::execute) is no longer required.

[fhahn]

Address comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4138–4139

Done, thanks!

4334–4335

I updated the code to just use PhiR->isInLoop.

4348–4349

isOrdered() implies isInLoop()

Now only isOrdered is check. The VPReductionPHIRecipe constructor ensures IsInLoop is set whenever IsOrdered is true.

IsOrdered here should be IsOrderedAndVectorized

Removed the variable, use isOrdered instead.

another place worth defining LastPartForVecRdxPhi

Done!

wonder what happens when isOrdered()&NotVectorized wires UF parts(?)

After recent changes, there's no need to check for isVector.

4349

Thanks, removed!

8053

Not really, we can use LoopInfo to get the pre-header block. Updated the code.

llvm/lib/Transforms/Vectorize/VPlan.cpp

1140

No need to check for isVector, as @kmclaughlin mentioned. I just replaced the variable with isOrdered() checks.

llvm/lib/Transforms/Vectorize/VPlan.h

308–315

The member is now gone again.

739–740

Introduce a base class common to all phi recipes to ask isa<> instead of isPhi?

Sounds like a good idea. I think it would be best to split up the existing WidenPHIRecipe first, to avoid moving too much at the same time.

Check range of SC's (from FirstPHI to LastPHI) instead of multiple ||'s, or make sure they compile down to a range check?

Done, added First/Last values to the enum.

1062

Moved, thanks!

1132

Added that IsOrdered also requires IsInLoop.

1147–1173

Done, also added doc-comments.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

237

Yes, updated! But I don't think it is possible to create a test case that shows the issue, because it would require a non-widenable reduction instruction I think.

llvm/lib/Transforms/Vectorize/VPlanValue.h

100

I moved them together, so the range check is more efficient. Also added VPFirstPHISC/VPLastPHISC to facilitate the range check.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

505–506

Above comment deserves an update?

4138–4139

dyn_cast<VPReductionPHIRecipe>(PhiR) or directly dyn_cast<VPReductionPHIRecipe>(&R), instead of going from PhiR to its VPValue base class and back via getDef()?

8053

Are both PrevBB and VectorPreHeader needed?

Ahh, it indeed seems more logical to set State.CFG.VectorPreHeader = ILV.createVectorizedLoopSkeleton(); here; and then have VPlan::execute() retrieve this VectorPreHeader and set/reset State.CFG.PrevBB, LastBB during code-gen of the vector loop's basic blocks.

But this issue of having to record the preheader in an additional State field, or look for it via LoopInfo, raises a more general thought regarding VPlan generating preheader code, noted below.

llvm/lib/Transforms/Vectorize/VPlan.cpp

1167

Code that VPlan is to generate inside the vector preheader, should ideally (/arguably?) be represented by recipes that reside inside a VPBasicBlock which represents this preheader, thereby properly extending the scope of VPlan; rather than redirecting Builder's insertion point. Sounds reasonable, perhaps as a follow-up?

[fhahn]

Addressed latest comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

505–506

Yes, I updated it in the latest version. Should only generate code for first-order recurrence phis and pointer inductions.

4138–4139

Done! Needed to add a classof implementation for VPWidenPHIRecipe to VPReductionPHIRecipe, to resolve multiple available overloads.

8053

Ok, I went back to having a separate field for the vector preheader. I kept the code to set both VectorPreHeader and PrevBB to the block returned by createVectorizedLoopSkeleton.

llvm/lib/Transforms/Vectorize/VPlan.cpp

1167

Sounds reasonable, perhaps as a follow-up?

+1, I'll look into modeling & generating the code in the pre-header as a follow-up patch.

[Ayal]

Looks good to me, adding a few minor optional last comments.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8053

On second thought, considering that State.CFG.VectorPreHeader may be temporary, it may be simpler to set it locally (and temporarily) inside VPlan::execute() as mentioned below.

llvm/lib/Transforms/Vectorize/VPlan.cpp

765–766

Another option, to keep this change local, is to keep
BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
and set here
State->CFG.VectorPreHeader = VectorPreHeaderBB;

1125

This TODO and associated if block below can be removed for VPReductionPHIRecipe?

1150

L used only in assert?

llvm/lib/Transforms/Vectorize/VPlan.h

1053

Mention that VPWidenPHIRecipe also serves as a base class for reduction phis?

[fhahn]

Thanks Ayal, I addressed the remaining comments in the committed version.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

public:
   /// new unrolled loop, where UF is the unroll factor.
   using VectorParts = SmallVector<Value *, 2>;
 
   /// Vectorize a single GetElementPtrInst based on information gathered and
   /// decisions taken during planning.
   void widenGEP(GetElementPtrInst *GEP, VPValue *VPDef, VPUser &Indices,
                 unsigned UF, ElementCount VF, bool IsPtrLoopInvariant,
                 SmallBitVector &IsIndexLoopInvariant, VPTransformState &State);
 
-  /// Vectorize a single PHINode in a block. This method handles the induction
-  /// variable canonicalization. It supports both VF = 1 for unrolled loops and
-  /// arbitrary length vectors.
-  void widenPHIInstruction(Instruction *PN, RecurrenceDescriptor *RdxDesc,
-                           VPWidenPHIRecipe *PhiR, VPTransformState &State);
+  /// Vectorize a single first-order recurrence or pointer induction PHINode in
+  /// a block. This method handles the induction variable canonicalization. It
+  /// supports both VF = 1 for unrolled loops and arbitrary length vectors.
+  void widenPHIInstruction(Instruction *PN, VPWidenPHIRecipe *PhiR,
+                           VPTransformState &State);
 
   /// A helper function to scalarize a single Instruction in the innermost loop.
   /// Generates a sequence of scalar instances for each lane between \p MinLane
   /// and \p MaxLane, times each part between \p MinPart and \p MaxPart,
   /// inclusive. Uses the VPValue operands from \p Operands instead of \p
   /// Instr's operands.
   void scalarizeInstruction(Instruction *Instr, VPValue *Def, VPUser &Operands,
                             const VPIteration &Instance, bool IfPredicateInstr,
protected:
   void fixCrossIterationPHIs(VPTransformState &State);
 
   /// Fix a first-order recurrence. This is the second phase of vectorizing
   /// this phi node.
   void fixFirstOrderRecurrence(VPWidenPHIRecipe *PhiR, VPTransformState &State);
 
   /// Fix a reduction cross-iteration phi. This is the second phase of
   /// vectorizing this phi node.
-  void fixReduction(VPWidenPHIRecipe *Phi, VPTransformState &State);
+  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
   /// block as exiting edges from the scalar epilogue loop (if present) are
void InnerLoopVectorizer::fixCrossIterationPHIs(VPTransformState &State) {
   // original loop is widened to a vector form so we can use them to construct
   // the incoming edges.
   VPBasicBlock *Header = State.Plan->getEntry()->getEntryBasicBlock();
   for (VPRecipeBase &R : Header->phis()) {
     auto *PhiR = dyn_cast<VPWidenPHIRecipe>(&R);
     if (!PhiR)
       continue;
     auto *OrigPhi = cast<PHINode>(PhiR->getUnderlyingValue());
-    if (PhiR->getRecurrenceDescriptor()) {
-      fixReduction(PhiR, State);
+    if (auto *ReductionPhi = dyn_cast<VPReductionPHIRecipe>(PhiR)) {
+      fixReduction(ReductionPhi, State);
     } else if (Legal->isFirstOrderRecurrence(OrigPhi))
       fixFirstOrderRecurrence(PhiR, State);
   }
 }
 
 void InnerLoopVectorizer::fixFirstOrderRecurrence(VPWidenPHIRecipe *PhiR,
                                                   VPTransformState &State) {
   // This is the second phase of vectorizing first-order recurrences. An
void InnerLoopVectorizer::fixFirstOrderRecurrence(VPWidenPHIRecipe *PhiR,
   // scalar epilogue); in that case, the exiting path through middle will be
   // dynamically dead and the value picked for the phi doesn't matter.
   for (PHINode &LCSSAPhi : LoopExitBlock->phis())
     if (any_of(LCSSAPhi.incoming_values(),
                [Phi](Value *V) { return V == Phi; }))
       LCSSAPhi.addIncoming(ExtractForPhiUsedOutsideLoop, LoopMiddleBlock);
 }
 
-void InnerLoopVectorizer::fixReduction(VPWidenPHIRecipe *PhiR,
+void InnerLoopVectorizer::fixReduction(VPReductionPHIRecipe *PhiR,
                                        VPTransformState &State) {
   PHINode *OrigPhi = cast<PHINode>(PhiR->getUnderlyingValue());
   // Get it's reduction variable descriptor.
   assert(Legal->isReductionVariable(OrigPhi) &&
          "Unable to find the reduction variable");
-  const RecurrenceDescriptor &RdxDesc = *PhiR->getRecurrenceDescriptor();
+  const RecurrenceDescriptor &RdxDesc = PhiR->getRecurrenceDescriptor();
 
   RecurKind RK = RdxDesc.getRecurrenceKind();
   TrackingVH<Value> ReductionStartValue = RdxDesc.getRecurrenceStartValue();
   Instruction *LoopExitInst = RdxDesc.getLoopExitInstr();
   setDebugLocFromInst(ReductionStartValue);
-  bool IsInLoopReductionPhi = Cost->isInLoopReduction(OrigPhi);
 
   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();
 
-  bool IsOrdered = IsInLoopReductionPhi && Cost->useOrderedReductions(RdxDesc);
-
-  for (unsigned Part = 0; Part < UF; ++Part) {
-    if (IsOrdered && Part > 0)
-      break;
+  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 (IsOrdered)
+    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);
 
   Type *PhiTy = OrigPhi->getType();
   // If tail is folded by masking, the vector value to leave the loop should be
   // a Select choosing between the vectorized LoopExitInst and vectorized Phi,
   // instead of the former. For an inloop reduction the reduction will already
   // be predicated, and does not need to be handled here.
-  if (Cost->foldTailByMasking() && !IsInLoopReductionPhi) {
+  if (Cost->foldTailByMasking() && !PhiR->isInLoop()) {
     for (unsigned Part = 0; Part < UF; ++Part) {
       Value *VecLoopExitInst = State.get(LoopExitInstDef, Part);
       Value *Sel = nullptr;
       for (User *U : VecLoopExitInst->users()) {
         if (isa<SelectInst>(U)) {
           assert(!Sel && "Reduction exit feeding two selects");
           Sel = U;
         } else
for (unsigned Part = 0; Part < UF; ++Part) {
       }
     }
   }
 
   // If the vector reduction can be performed in a smaller type, we truncate
   // then extend the loop exit value to enable InstCombine to evaluate the
   // entire expression in the smaller type.
   if (VF.isVector() && PhiTy != RdxDesc.getRecurrenceType()) {
-    assert(!IsInLoopReductionPhi && "Unexpected truncated inloop reduction!");
+    assert(!PhiR->isInLoop() && "Unexpected truncated inloop reduction!");
     Type *RdxVecTy = VectorType::get(RdxDesc.getRecurrenceType(), VF);
     Builder.SetInsertPoint(
         LI->getLoopFor(LoopVectorBody)->getLoopLatch()->getTerminator());
     VectorParts RdxParts(UF);
     for (unsigned Part = 0; Part < UF; ++Part) {
       RdxParts[Part] = State.get(LoopExitInstDef, Part);
       Value *Trunc = Builder.CreateTrunc(RdxParts[Part], RdxVecTy);
       Value *Extnd = RdxDesc.isSigned() ? Builder.CreateSExt(Trunc, VecTy)
void InnerLoopVectorizer::fixReduction(VPReductionPHIRecipe *PhiR,
   // The middle block terminator has already been assigned a DebugLoc here (the
   // OrigLoop's single latch terminator). We want the whole middle block to
   // appear to execute on this line because: (a) it is all compiler generated,
   // (b) these instructions are always executed after evaluating the latch
   // conditional branch, and (c) other passes may add new predecessors which
   // terminate on this line. This is the easiest way to ensure we don't
   // accidentally cause an extra step back into the loop while debugging.
   setDebugLocFromInst(LoopMiddleBlock->getTerminator());
-  if (IsOrdered)
+  if (PhiR->isOrdered())
     ReducedPartRdx = State.get(LoopExitInstDef, UF - 1);
   else {
     // Floating-point operations should have some FMF to enable the reduction.
     IRBuilderBase::FastMathFlagGuard FMFG(Builder);
     Builder.setFastMathFlags(RdxDesc.getFastMathFlags());
     for (unsigned Part = 1; Part < UF; ++Part) {
       Value *RdxPart = State.get(LoopExitInstDef, Part);
       if (Op != Instruction::ICmp && Op != Instruction::FCmp) {
         ReducedPartRdx = Builder.CreateBinOp(
             (Instruction::BinaryOps)Op, RdxPart, ReducedPartRdx, "bin.rdx");
       } else {
         ReducedPartRdx = createMinMaxOp(Builder, RK, ReducedPartRdx, RdxPart);
       }
     }
   }
 
   // Create the reduction after the loop. Note that inloop reductions create the
   // target reduction in the loop using a Reduction recipe.
-  if (VF.isVector() && !IsInLoopReductionPhi) {
+  if (VF.isVector() && !PhiR->isInLoop()) {
     ReducedPartRdx =
         createTargetReduction(Builder, TTI, RdxDesc, ReducedPartRdx);
     // If the reduction can be performed in a smaller type, we need to extend
     // the reduction to the wider type before we branch to the original loop.
     if (PhiTy != RdxDesc.getRecurrenceType())
       ReducedPartRdx = RdxDesc.isSigned()
                            ? Builder.CreateSExt(ReducedPartRdx, PhiTy)
                            : Builder.CreateZExt(ReducedPartRdx, PhiTy);
for (unsigned Part = 0; Part < UF; ++Part) {
              "NewGEP is not a pointer vector");
       State.set(VPDef, NewGEP, Part);
       addMetadata(NewGEP, GEP);
     }
   }
 }
 
 void InnerLoopVectorizer::widenPHIInstruction(Instruction *PN,
-                                              RecurrenceDescriptor *RdxDesc,
                                               VPWidenPHIRecipe *PhiR,
                                               VPTransformState &State) {
   PHINode *P = cast<PHINode>(PN);
   if (EnableVPlanNativePath) {
     // Currently we enter here in the VPlan-native path for non-induction
     // PHIs where all control flow is uniform. We simply widen these PHIs.
     // Create a vector phi with no operands - the vector phi operands will be
     // set at the end of vector code generation.
     Type *VecTy = (State.VF.isScalar())
                       ? PN->getType()
                       : VectorType::get(PN->getType(), State.VF);
     Value *VecPhi = Builder.CreatePHI(VecTy, PN->getNumOperands(), "vec.phi");
     State.set(PhiR, VecPhi, 0);
     OrigPHIsToFix.push_back(P);
 
     return;
   }
 
   assert(PN->getParent() == OrigLoop->getHeader() &&
          "Non-header phis should have been handled elsewhere");
 
   // In order to support recurrences we need to be able to vectorize Phi nodes.
   // Phi nodes have cycles, so we need to vectorize them in two stages. This is
   // stage #1: We create a new vector PHI node with no incoming edges. We'll use
   // this value when we vectorize all of the instructions that use the PHI.
-  if (RdxDesc || Legal->isFirstOrderRecurrence(P)) {
-    bool ScalarPHI =
-        (State.VF.isScalar()) || Cost->isInLoopReduction(cast<PHINode>(PN));
-    Type *VecTy =
-        ScalarPHI ? PN->getType() : VectorType::get(PN->getType(), State.VF);
-
-    bool IsOrdered = Cost->isInLoopReduction(cast<PHINode>(PN)) &&
-                     Cost->useOrderedReductions(*RdxDesc);
-    unsigned LastPartForNewPhi = IsOrdered ? 1 : State.UF;
-    for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
+  if (Legal->isFirstOrderRecurrence(P)) {
+    Type *VecTy = State.VF.isScalar()
+                      ? PN->getType()
+                      : VectorType::get(PN->getType(), State.VF);
+
+    for (unsigned Part = 0; Part < State.UF; ++Part) {
       Value *EntryPart = PHINode::Create(
           VecTy, 2, "vec.phi", &*LoopVectorBody->getFirstInsertionPt());
       State.set(PhiR, EntryPart, Part);
     }
-    if (Legal->isFirstOrderRecurrence(P))
-      return;
-    VPValue *StartVPV = PhiR->getStartValue();
-    Value *StartV = StartVPV->getLiveInIRValue();
-
-    Value *Iden = nullptr;
-
-    assert(Legal->isReductionVariable(P) && StartV &&
-           "RdxDesc should only be set for reduction variables; in that case "
-           "a StartV is also required");
-    RecurKind RK = RdxDesc->getRecurrenceKind();
-    if (RecurrenceDescriptor::isMinMaxRecurrenceKind(RK)) {
-      // MinMax reduction have the start value as their identify.
-      if (ScalarPHI) {
-        Iden = StartV;
-      } else {
-        IRBuilderBase::InsertPointGuard IPBuilder(Builder);
-        Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator());
-        StartV = Iden =
-            Builder.CreateVectorSplat(State.VF, StartV, "minmax.ident");
-      }
-    } else {
-      Constant *IdenC = RecurrenceDescriptor::getRecurrenceIdentity(
-          RK, VecTy->getScalarType(), RdxDesc->getFastMathFlags());
-      Iden = IdenC;
-
-      if (!ScalarPHI) {
-        Iden = ConstantVector::getSplat(State.VF, IdenC);
-        IRBuilderBase::InsertPointGuard IPBuilder(Builder);
-        Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator());
-        Constant *Zero = Builder.getInt32(0);
-        StartV = Builder.CreateInsertElement(Iden, StartV, Zero);
-      }
-    }
-
-    for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
-      Value *EntryPart = State.get(PhiR, Part);
-      // Make sure to add the reduction start value only to the
-      // first unroll part.
-      Value *StartVal = (Part == 0) ? StartV : Iden;
-      cast<PHINode>(EntryPart)->addIncoming(StartVal, LoopVectorPreHeader);
-    }
-
       return;
   }
 
   assert(!Legal->isReductionVariable(P) &&
-         "reductions should be handled above");
+         "reductions should be handled elsewhere");
 
   setDebugLocFromInst(P);
 
   // This PHINode must be an induction variable.
   // Make sure that we know about it.
   assert(Legal->getInductionVars().count(P) && "Not an induction variable");
 
   InductionDescriptor II = Legal->getInductionVars().lookup(P);
void LoopVectorizationPlanner::executePlan(InnerLoopVectorizer &ILV,
 
   // 1. Create a new empty loop. Unlink the old loop and connect the new one.
   assert(BestVF.hasValue() && "Vectorization Factor is missing");
   assert(VPlans.size() == 1 && "Not a single VPlan to execute.");
 
   VPTransformState State{
       *BestVF, BestUF, LI, DT, ILV.Builder, &ILV, VPlans.front().get()};
   State.CFG.PrevBB = ILV.createVectorizedLoopSkeleton();
   State.TripCount = ILV.getOrCreateTripCount(nullptr);
   State.CanonicalIV = ILV.Induction;
 
   ILV.printDebugTracesAtStart();
 
   //===------------------------------------------------===//
   //
   // Notice: any optimization or new instruction that go
   // into the code below should also be implemented in
if (auto Phi = dyn_cast<PHINode>(Instr)) {
 
     VPWidenPHIRecipe *PhiRecipe = nullptr;
     if (Legal->isReductionVariable(Phi) || Legal->isFirstOrderRecurrence(Phi)) {
       VPValue *StartV = Operands[0];
       if (Legal->isReductionVariable(Phi)) {
         RecurrenceDescriptor &RdxDesc = Legal->getReductionVars()[Phi];
         assert(RdxDesc.getRecurrenceStartValue() ==
                Phi->getIncomingValueForBlock(OrigLoop->getLoopPreheader()));
-        PhiRecipe = new VPWidenPHIRecipe(Phi, RdxDesc, *StartV);
+        PhiRecipe = new VPReductionPHIRecipe(Phi, RdxDesc, *StartV,
+                                             CM.isInLoopReduction(Phi),
+                                             CM.useOrderedReductions(RdxDesc));
       } else {
         PhiRecipe = new VPWidenPHIRecipe(Phi, *StartV);
       }
 
       // Record the incoming value from the backedge, so we can add the incoming
       // value from the backedge after all recipes have been created.
       recordRecipeOf(cast<Instruction>(
           Phi->getIncomingValueForBlock(OrigLoop->getLoopLatch())));

 void VPWidenIntOrFpInductionRecipe::execute(VPTransformState &State) {
   assert(!State.Instance && "Int or FP induction being replicated.");
   State.ILV->widenIntOrFpInduction(IV, getStartValue()->getLiveInIRValue(),
                                    getTruncInst(), getVPValue(0),
                                    getCastValue(), State);
 }
 
 void VPWidenPHIRecipe::execute(VPTransformState &State) {
-  State.ILV->widenPHIInstruction(cast<PHINode>(getUnderlyingValue()), RdxDesc,
-                                 this, State);
+  State.ILV->widenPHIInstruction(cast<PHINode>(getUnderlyingValue()), this,
+                                 State);
 }
 
 void VPBlendRecipe::execute(VPTransformState &State) {
   State.ILV->setDebugLocFromInst(Phi, &State.Builder);
   // We know that all PHIs in non-header blocks are converted into
   // selects, so we don't have to worry about the insertion order and we
   // can just use the builder.
   // At this point we generate the predication tree. There may be

llvm/lib/Transforms/Vectorize/VPlan.h

struct CFGState {
 
     /// The previous IR BasicBlock created or used. Initially set to the new
     /// header BasicBlock.
     BasicBlock *PrevBB = nullptr;
 
     /// The last IR BasicBlock in the output IR. Set to the new latch
     /// BasicBlock, used for placing the newly created BasicBlocks.
     BasicBlock *LastBB = nullptr;
 
+    /// The IR BasicBlock that is the preheader of the vector loop in the output
+    /// IR.
+    /// FIXME: The vector preheader should also be modeled in VPlan, so any code
+    /// that needs to be added to the preheader gets directly generated by
+    /// VPlan. There should be no need to manage a pointer to the IR BasicBlock.
+    BasicBlock *VectorPreHeader = nullptr;
+
     /// A mapping of each VPBasicBlock to the corresponding BasicBlock. In case
     /// of replication, maps the BasicBlock of the last replica created.
     SmallDenseMap<VPBasicBlock *, BasicBlock *> VPBB2IRBB;
 
     /// Vector of VPBasicBlocks whose terminator instruction needs to be fixed
     /// up at the end of vector code generation.
     SmallVector<VPBasicBlock *, 8> VPBBsToFix;
 
public:
   static inline bool classof(const VPUser *U) {
     return U->getVPUserID() == VPUser::VPUserID::Recipe;
   }
 
   /// Returns true if the recipe may have side-effects.
   bool mayHaveSideEffects() const;
 
   /// Returns true for PHI-like recipes.
   bool isPhi() const {
-    return getVPDefID() == VPWidenIntOrFpInductionSC || getVPDefID() == VPWidenPHISC ||
-      getVPDefID() == VPPredInstPHISC || getVPDefID() == VPWidenCanonicalIVSC;
+    return getVPDefID() >= VPFirstPHISC && getVPDefID() <= VPLastPHISC;
   }
 
   /// Returns true if the recipe may read from memory.
   bool mayReadFromMemory() const;
 
   /// Returns true if the recipe may write to memory.
   bool mayWriteToMemory() const;
 
#endif
   TruncInst *getTruncInst() {
     return dyn_cast_or_null<TruncInst>(getVPValue(0)->getUnderlyingValue());
   }
   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. For reductions and first-order recurrences, 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.
+/// A recipe for handling first order recurrences and pointer inductions. For
+/// first-order recurrences, the start value is the first operand of the recipe
+/// and the incoming value from the backedge is the second operand. It also
+/// serves as base class for VPReductionPHIRecipe. 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;
 
+protected:
+  VPWidenPHIRecipe(unsigned char VPVID, unsigned char VPDefID, PHINode *Phi)
+      : VPRecipeBase(VPDefID, {}), VPValue(VPVID, Phi, this) {}
+
 public:
-  /// Create a new VPWidenPHIRecipe for the reduction \p Phi described by \p
-  /// RdxDesc.
-  VPWidenPHIRecipe(PHINode *Phi, RecurrenceDescriptor &RdxDesc, VPValue &Start)
-      : VPWidenPHIRecipe(Phi) {
-    this->RdxDesc = &RdxDesc;
-    addOperand(&Start);
-  }
+  /// Create a VPWidenPHIRecipe for \p Phi
+  VPWidenPHIRecipe(PHINode *Phi)
+      : VPWidenPHIRecipe(VPVWidenPHISC, VPWidenPHISC, Phi) {}
 
   /// Create a new VPWidenPHIRecipe for \p Phi with start value \p Start.
   VPWidenPHIRecipe(PHINode *Phi, VPValue &Start) : VPWidenPHIRecipe(Phi) {
     addOperand(&Start);
   }
 
-  /// Create a VPWidenPHIRecipe for \p Phi
-  VPWidenPHIRecipe(PHINode *Phi)
-      : VPRecipeBase(VPWidenPHISC, {}),
-        VPValue(VPValue::VPVWidenPHISC, Phi, this) {}
   ~VPWidenPHIRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
-  static inline bool classof(const VPDef *D) {
-    return D->getVPDefID() == VPRecipeBase::VPWidenPHISC;
+  static inline bool classof(const VPRecipeBase *B) {
+    return B->getVPDefID() == VPRecipeBase::VPWidenPHISC ||
+           B->getVPDefID() == VPRecipeBase::VPReductionPHISC;
   }
   static inline bool classof(const VPValue *V) {
-    return V->getVPValueID() == VPValue::VPVWidenPHISC;
+    return V->getVPValueID() == VPValue::VPVWidenPHISC ||
+           V->getVPValueID() == VPValue::VPVReductionPHISC;
   }
 
   /// Generate the phi/select nodes.
   void execute(VPTransformState &State) override;
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
void addIncoming(VPValue *IncomingV, VPBasicBlock *IncomingBlock) {
     IncomingBlocks.push_back(IncomingBlock);
   }
 
   /// Returns the \p I th incoming VPValue.
   VPValue *getIncomingValue(unsigned I) { return getOperand(I); }
 
   /// Returns the \p I th incoming VPBasicBlock.
   VPBasicBlock *getIncomingBlock(unsigned I) { return IncomingBlocks[I]; }
+};
+
+/// A recipe for handling reduction phis. The start value is the first operand
+/// of the recipe and the incoming value from the backedge is the second
+/// operand.
+class VPReductionPHIRecipe : public VPWidenPHIRecipe {
+  /// Descriptor for the reduction.
+  RecurrenceDescriptor &RdxDesc;
+
+  /// The phi is part of an in-loop reduction.
+  bool IsInLoop;
+
+  /// The phi is part of an ordered reduction. Requires IsInLoop to be true.
+  bool IsOrdered;
+
+public:
+  /// Create a new VPReductionPHIRecipe for the reduction \p Phi described by \p
+  /// RdxDesc.
+  VPReductionPHIRecipe(PHINode *Phi, RecurrenceDescriptor &RdxDesc,
+                       VPValue &Start, bool IsInLoop = false,
+                       bool IsOrdered = false)
+      : VPWidenPHIRecipe(VPVReductionPHISC, VPReductionPHISC, Phi),
+        RdxDesc(RdxDesc), IsInLoop(IsInLoop), IsOrdered(IsOrdered) {
+    assert((!IsOrdered || IsInLoop) && "IsOrdered requires IsInLoop");
+    addOperand(&Start);
+  }
 
-  RecurrenceDescriptor *getRecurrenceDescriptor() { return RdxDesc; }
+  /// Method to support type inquiry through isa, cast, and dyn_cast.
+  static inline bool classof(const VPRecipeBase *R) {
+    return R->getVPDefID() == VPRecipeBase::VPReductionPHISC;
+  }
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() == VPValue::VPVReductionPHISC;
+  }
+  static inline bool classof(const VPWidenPHIRecipe *R) {
+    return R->getVPDefID() == VPRecipeBase::VPReductionPHISC;
+  }
+
+  /// Generate the phi/select nodes.
+  void execute(VPTransformState &State) override;
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  /// Print the recipe.
+  void print(raw_ostream &O, const Twine &Indent,
+             VPSlotTracker &SlotTracker) const override;
+#endif
+
+  RecurrenceDescriptor &getRecurrenceDescriptor() { return RdxDesc; }
+
+  /// Returns true, if the phi is part of an ordered reduction.
+  bool isOrdered() const { return IsOrdered; }
+
+  /// Returns true, if the phi is part of an in-loop reduction.
+  bool isInLoop() const { return IsInLoop; }
 };
 
 /// A recipe for vectorizing a phi-node as a sequence of mask-based select
 /// instructions.
 class VPBlendRecipe : public VPRecipeBase, public VPValue {
   PHINode *Phi;
 
 public:
public:
 
   ~VPReductionRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPValue *V) {
     return V->getVPValueID() == VPValue::VPVReductionSC;
   }
 
-  static inline bool classof(const VPDef *D) {
-    return D->getVPDefID() == VPRecipeBase::VPReductionSC;
-  }
-
   /// Generate the reduction in the loop
   void execute(VPTransformState &State) override;
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 #endif

llvm/lib/Transforms/Vectorize/VPlan.cpp

if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
     for (unsigned Part = 0, UF = State->UF; Part < UF; ++Part)
       State->set(BackedgeTakenCount, VTCMO, Part);
   }
 
   // 0. Set the reverse mapping from VPValues to Values for code generation.
   for (auto &Entry : Value2VPValue)
     State->VPValue2Value[Entry.second] = Entry.first;
 
   BasicBlock *VectorPreHeaderBB = State->CFG.PrevBB;
+  State->CFG.VectorPreHeader = VectorPreHeaderBB;
   BasicBlock *VectorHeaderBB = VectorPreHeaderBB->getSingleSuccessor();
   assert(VectorHeaderBB && "Loop preheader does not have a single successor.");
 
   // 1. Make room to generate basic-blocks inside loop body if needed.
   BasicBlock *VectorLatchBB = VectorHeaderBB->splitBasicBlock(
       VectorHeaderBB->getFirstInsertionPt(), "vector.body.latch");
   Loop *L = State->LI->getLoopFor(VectorHeaderBB);
   L->addBasicBlockToLoop(VectorLatchBB, *State->LI);
if (getNumOperands() != OriginalPhi->getNumOperands()) {
     return;
   }
 
   printAsOperand(O, SlotTracker);
   O << " = phi ";
   printOperands(O, SlotTracker);
 }
 
+void VPReductionPHIRecipe::print(raw_ostream &O, const Twine &Indent,
+                                 VPSlotTracker &SlotTracker) const {
+  O << Indent << "WIDEN-REDUCTION-PHI ";
+
+  printAsOperand(O, SlotTracker);
+  O << " = phi ";
+  printOperands(O, SlotTracker);
+}
+
+void VPReductionPHIRecipe::execute(VPTransformState &State) {
+  PHINode *PN = cast<PHINode>(getUnderlyingValue());
+  auto &Builder = State.Builder;
+
+  // In order to support recurrences we need to be able to vectorize Phi nodes.
+  // Phi nodes have cycles, so we need to vectorize them in two stages. This is
+  // stage #1: We create a new vector PHI node with no incoming edges. We'll use
+  // this value when we vectorize all of the instructions that use the PHI.
+  bool ScalarPHI = State.VF.isScalar() || IsInLoop;
+  Type *VecTy =
+      ScalarPHI ? PN->getType() : VectorType::get(PN->getType(), State.VF);
+
+  BasicBlock *HeaderBB = State.CFG.PrevBB;
+  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);
+  }
+  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) {
+      Iden = StartV;
+    } else {
+      IRBuilderBase::InsertPointGuard IPBuilder(Builder);
+      Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
+      StartV = Iden =
+          Builder.CreateVectorSplat(State.VF, StartV, "minmax.ident");
+    }
+  } else {
+    Constant *IdenC = RecurrenceDescriptor::getRecurrenceIdentity(
+        RK, VecTy->getScalarType(), RdxDesc.getFastMathFlags());
+    Iden = IdenC;
+
+    if (!ScalarPHI) {
+      Iden = ConstantVector::getSplat(State.VF, IdenC);
+      IRBuilderBase::InsertPointGuard IPBuilder(Builder);
+      Builder.SetInsertPoint(State.CFG.VectorPreHeader->getTerminator());
+      Constant *Zero = Builder.getInt32(0);
+      StartV = Builder.CreateInsertElement(Iden, StartV, Zero);
+    }
+  }
+
+  for (unsigned Part = 0; Part < LastPartForNewPhi; ++Part) {
+    Value *EntryPart = State.get(this, Part);
+    // Make sure to add the reduction start value only to the
+    // first unroll part.
+    Value *StartVal = (Part == 0) ? StartV : Iden;
+    cast<PHINode>(EntryPart)->addIncoming(StartVal, State.CFG.VectorPreHeader);
+  }
+}
+
 void VPBlendRecipe::print(raw_ostream &O, const Twine &Indent,
                           VPSlotTracker &SlotTracker) const {
   O << Indent << "BLEND ";
   Phi->printAsOperand(O, false);
   O << " =";
   if (getNumIncomingValues() == 1) {
     // Not a User of any mask: not really blending, this is a
     // single-predecessor phi.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

for (VPRegionBlock *Region1 : CandidateRegions) {
     // R not be moved at all.
     auto IsImmovableRecipe = [](VPRecipeBase &R) {
       assert(R.getNumDefinedValues() <= 1 &&
              "no multi-defs are expected in predicated blocks");
       for (VPUser *U : R.getVPValue()->users()) {
         auto *UI = dyn_cast<VPRecipeBase>(U);
         if (!UI)
           continue;
-        auto *PhiR = dyn_cast<VPWidenPHIRecipe>(UI);
-        if (PhiR && !PhiR->getRecurrenceDescriptor())
+        if (isa<VPWidenPHIRecipe>(UI) && !isa<VPReductionPHIRecipe>(UI))
           return true;
       }
       return false;
     };
     if (any_of(*Then1, IsImmovableRecipe))
       continue;
 
     // Move recipes to the successor region.

llvm/lib/Transforms/Vectorize/VPlanValue.h

public:
   const Value *getUnderlyingValue() const { return UnderlyingVal; }
 
   /// An enumeration for keeping track of the concrete subclass of VPValue that
   /// are actually instantiated. Values of this enumeration are kept in the
   /// SubclassID field of the VPValue objects. They are used for concrete
   /// type identification.
   enum {
     VPValueSC,
-    VPVBlendSC,
     VPVInstructionSC,
     VPVMemoryInstructionSC,
-    VPVPredInstPHI,
     VPVReductionSC,
     VPVReplicateSC,
     VPVWidenSC,
     VPVWidenCallSC,
     VPVWidenGEPSC,
-    VPVWidenIntOrFpIndcutionSC,
-    VPVWidenPHISC,
     VPVWidenSelectSC,
+
+    // Phi-like VPValues. Need to be kept together.
+    VPVBlendSC,
+    VPVWidenPHISC,
+    VPVWidenCanonicalIVSC,
+    VPVWidenIntOrFpInductionSC,
+    VPVPredInstPHI,
+    VPVReductionPHISC,
   };
 
   VPValue(Value *UV = nullptr, VPDef *Def = nullptr)
       : VPValue(VPValueSC, UV, Def) {}
   VPValue(const VPValue &) = delete;
   VPValue &operator=(const VPValue &) = delete;
 
   virtual ~VPValue();
class VPDef {
   }
 
 public:
   /// An enumeration for keeping track of the concrete subclass of VPRecipeBase
   /// that is actually instantiated. Values of this enumeration are kept in the
   /// SubclassID field of the VPRecipeBase objects. They are used for concrete
   /// type identification.
   using VPRecipeTy = enum {
-    VPBlendSC,
     VPBranchOnMaskSC,
     VPInstructionSC,
     VPInterleaveSC,
-    VPPredInstPHISC,
     VPReductionSC,
     VPReplicateSC,
     VPWidenCallSC,
-    VPWidenCanonicalIVSC,
     VPWidenGEPSC,
-    VPWidenIntOrFpInductionSC,
     VPWidenMemoryInstructionSC,
-    VPWidenPHISC,
     VPWidenSC,
-    VPWidenSelectSC
+    VPWidenSelectSC,
+
+    // Phi-like recipes. Need to be kept together.
+    VPBlendSC,
+    VPWidenPHISC,
+    VPWidenCanonicalIVSC,
+    VPWidenIntOrFpInductionSC,
+    VPPredInstPHISC,
+    VPReductionPHISC,
+    VPFirstPHISC = VPBlendSC,
+    VPLastPHISC = VPReductionPHISC,
   };
 
   VPDef(const unsigned char SC) : SubclassID(SC) {}
 
   virtual ~VPDef() {
     for (VPValue *D : make_early_inc_range(DefinedValues)) {
       assert(D->Def == this &&
              "all defined VPValues should point to the containing VPDef");

llvm/test/Transforms/LoopVectorize/first-order-recurrence-sink-replicate-region.ll

 }
 
 define i32 @sink_replicate_region_3_reduction(i32 %x, i8 %y, i32* %ptr) optsize {
 ; CHECK-LABEL: sink_replicate_region_3_reduction
 ; CHECK:      VPlan 'Initial VPlan for VF={2},UF>=1' {
 ; CHECK-NEXT: loop:
 ; CHECK-NEXT:   WIDEN-PHI ir<%recur> = phi ir<0>, ir<%recur.next>
 ; CHECK-NEXT:   WIDEN-INDUCTION %iv = phi 0, %iv.next
-; CHECK-NEXT:   WIDEN-PHI ir<%and.red> = phi ir<1234>, ir<%and.red.next>
+; CHECK-NEXT:   WIDEN-REDUCTION-PHI ir<%and.red> = phi ir<1234>, ir<%and.red.next>
 ; CHECK-NEXT:   EMIT vp<%4> = icmp ule ir<%iv> vp<%0>
 ; CHECK-NEXT: Successor(s): loop.0
 ; CHECK-EMPTY:
 ; CHECK-NEXT: loop.0:
 ; CHECK-NEXT:   WIDEN ir<%recur.next> = sext ir<%y>
 ; CHECK-NEXT: Successor(s): pred.srem
 ; CHECK-EMPTY:
 ; CHECK-NEXT: <xVFxUF> pred.srem: {

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 ir<%red> = phi ir<0.000000e+00>, ir<%red.next>
+; CHECK-NEXT:   WIDEN-REDUCTION-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