[VPlan] Make sure recurrence splice is not inserted between phis.

[fhahn]

Summary

All phi-like recipes should be at the beginning of a VPBasicBlock with
no other recipes in between. Ensure that the recurrence-splicing recipe
is not added between phi-like recipes, but after them.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9507

Hmm, PrevRecipe cannot be a header phi because that would result in 2nd order recurrence (or greater); but it may be a phi of a replicated region? Should blends be excluded here? Curious to see a test...

9511

How about setting the insertion point of Builder before creating the Op, instead of finding where to move it afterwards?

[fhahn]

Updated to set the insert point of the builder up-front, rather than moving the created recipies later. Also removed unnneded isPhi check.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9507

I thought there was a test case, but it looks like I remembered incorrectly. Removed the check.

9511

How about setting the insertion point of Builder before creating the Op, instead of finding where to move it afterwards?

Sounds good, updated!

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9506

This became an NFC patch, update its title and summary?
Assert that PrevRecipe is not a Phi, or have the verifier catch if it is (a Phi but not the last Phi)?

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9507

I thought there was a test case, but it looks like I remembered incorrectly. Removed the check.

Ok I now what phi-like case I originally hit: if the previous value is an induction value! So I think we still need the special handling?

[fhahn]

Restore code to set insert point for phi-like recipes.

Relevant test is something like trunc_with_first_order_recurrence in
test/Transforms/LoopVectorize/induction.ll

[fhahn]

ping :)

@Ayal does the clarification why this is needed make sense?

(from inline comment)
Ok I now what phi-like case I originally hit: if the previous value is an induction value! So I think we still need the special handling?

[Ayal]

In D111301#3108536, @fhahn wrote:

ping :)

@Ayal does the clarification why this is needed make sense?

(from inline comment)
Ok I now what phi-like case I originally hit: if the previous value is an induction value! So I think we still need the special handling?

Clarification indeed makes sense, induction feeding a FOR should presumably be handled, not being a 2nd-order recurrence (SOR).

So we may indeed still need the special handling - along with special test(s); perhaps using i-1 inside a "for i" loop? Would also be good to address/exclude/cover non-header phis - of replicated regions and blends.

[fhahn]

In D111301#3109192, @Ayal wrote:

In D111301#3108536, @fhahn wrote:

ping :)

@Ayal does the clarification why this is needed make sense?

(from inline comment)
Ok I now what phi-like case I originally hit: if the previous value is an induction value! So I think we still need the special handling?

Clarification indeed makes sense, induction feeding a FOR should presumably be handled, not being a 2nd-order recurrence (SOR).

So we may indeed still need the special handling - along with special test(s); perhaps using i-1 inside a "for i" loop?

There should be test coverage already for those cases, in Transforms/LoopVectorize/induction.ll, which fails verification from D111302 without the current patch.

Would also be good to address/exclude/cover non-header phis - of replicated regions and blends.

Should those be included in this patch here?

[Ayal]

In D111301#3112774, @fhahn wrote:

In D111301#3109192, @Ayal wrote:

In D111301#3108536, @fhahn wrote:

ping :)

@Ayal does the clarification why this is needed make sense?

(from inline comment)
Ok I now what phi-like case I originally hit: if the previous value is an induction value! So I think we still need the special handling?

Clarification indeed makes sense, induction feeding a FOR should presumably be handled, not being a 2nd-order recurrence (SOR).

So we may indeed still need the special handling - along with special test(s); perhaps using i-1 inside a "for i" loop?

There should be test coverage already for those cases, in Transforms/LoopVectorize/induction.ll, which fails verification from D111302 without the current patch.

ok; can a comment be added to these tests, mentioning that they exercise induction-feeding-a-FOR, and careful placement of the FOR splice?
Wonder how VPlan generated correct code, with splice placed in the midst of phi's(?)

Would also be good to address/exclude/cover non-header phis - of replicated regions and blends.

Should those be included in this patch here?

or left as a TODO?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9491–9501

nit: can tentatively set

VPBasicBlock *InsertBlock = PrevRecipe->getParent();

initially, and later override it with

InsertBlock = cast<VPBasicBlock>(Region->getSingleSuccessor());

[fhahn]

In D111301#3115048, @Ayal wrote:

In D111301#3112774, @fhahn wrote:

In D111301#3109192, @Ayal wrote:

In D111301#3108536, @fhahn wrote:

ping :)

@Ayal does the clarification why this is needed make sense?

(from inline comment)
Ok I now what phi-like case I originally hit: if the previous value is an induction value! So I think we still need the special handling?

Clarification indeed makes sense, induction feeding a FOR should presumably be handled, not being a 2nd-order recurrence (SOR).

So we may indeed still need the special handling - along with special test(s); perhaps using i-1 inside a "for i" loop?

There should be test coverage already for those cases, in Transforms/LoopVectorize/induction.ll, which fails verification from D111302 without the current patch.

ok; can a comment be added to these tests, mentioning that they exercise induction-feeding-a-FOR, and careful placement of the FOR splice?
Wonder how VPlan generated correct code, with splice placed in the midst of phi's(?)

Done in the committed version. The issue in the test case were other induction recipes after the splice. The existing widenIntOrFpInduction inserts new phis at the beginning of the BB, so it did not cause any issues during actual codegen.

Would also be good to address/exclude/cover non-header phis - of replicated regions and blends.

Should those be included in this patch here?

or left as a TODO?

I did not add a TODO in the committed version, because unfortunately I am not sure where to best add one :(

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9491–9501

Done in the committed version, thanks!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
   adjustRecipesForReductions(VPBB, Plan, RecipeBuilder, Range.Start);
 
   // Introduce a recipe to combine the incoming and previous values of a
   // first-order recurrence.
   for (VPRecipeBase &R : Plan->getEntry()->getEntryBasicBlock()->phis()) {
     auto *RecurPhi = dyn_cast<VPFirstOrderRecurrencePHIRecipe>(&R);
     if (!RecurPhi)
       continue;
 
+    VPRecipeBase *PrevRecipe = RecurPhi->getBackedgeRecipe();
+    VPBasicBlock *InsertBlock = PrevRecipe->getParent();
+    auto *Region = GetReplicateRegion(PrevRecipe);
+    if (Region)
+      InsertBlock = cast<VPBasicBlock>(Region->getSingleSuccessor());
+    if (Region || PrevRecipe->isPhi())
+      Builder.setInsertPoint(InsertBlock, InsertBlock->getFirstNonPhi());
+    else
+      Builder.setInsertPoint(InsertBlock, std::next(PrevRecipe->getIterator()));
+
     auto *RecurSplice = cast<VPInstruction>(
         Builder.createNaryOp(VPInstruction::FirstOrderRecurrenceSplice,
                              {RecurPhi, RecurPhi->getBackedgeValue()}));
 
-    VPRecipeBase *PrevRecipe = RecurPhi->getBackedgeRecipe();
-    if (auto *Region = GetReplicateRegion(PrevRecipe)) {
-      VPBasicBlock *Succ = cast<VPBasicBlock>(Region->getSingleSuccessor());
-      RecurSplice->moveBefore(*Succ, Succ->getFirstNonPhi());
-    } else
-      RecurSplice->moveAfter(PrevRecipe);
     RecurPhi->replaceAllUsesWith(RecurSplice);
     // Set the first operand of RecurSplice to RecurPhi again, after replacing
     // all users.
     RecurSplice->setOperand(0, RecurPhi);
   }
 
   // Interleave memory: for each Interleave Group we marked earlier as relevant
   // for this VPlan, replace the Recipes widening its memory instructions with a
   // single VPInterleaveRecipe at its insertion point.
   for (auto IG : InterleaveGroups) {
     auto *Recipe = cast<VPWidenMemoryInstructionRecipe>(
         RecipeBuilder.getRecipe(IG->getInsertPos()));
     SmallVector<VPValue *, 4> StoredValues;
     for (unsigned i = 0; i < IG->getFactor(); ++i)

llvm/test/Transforms/LoopVectorize/induction.ll

for.inc:
   br i1 %cond, label %for.end, label %for.body
 
 for.end:
   %tmp7 = phi i32 [ %tmp6, %for.inc ]
   ret i32 %tmp7
 }
 
 ; Ensure that the shuffle vector for first order recurrence is inserted
-; correctly after all the phis. These new phis correspond to new IVs 
-; that are generated by optimizing non-free truncs of IVs to IVs themselves 
+; correctly after all the phis. These new phis correspond to new IVs
+; that are generated by optimizing non-free truncs of IVs to IVs themselves.
+; This also ensures the first-order recurrence splice recipe is placed
+; correctly if it is fed by an induction.
 define i64 @trunc_with_first_order_recurrence() {
 ; CHECK-LABEL: trunc_with_first_order_recurrence
 ; CHECK-LABEL: vector.body:
 ; CHECK-NEXT:    %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
 ; CHECK-NEXT:    %vec.phi = phi <2 x i64>
 ; CHECK-NEXT:    %vec.ind = phi <2 x i64> [ <i64 1, i64 2>, %vector.ph ], [ %vec.ind.next, %vector.body ]
 ; CHECK-NEXT:    %vec.ind2 = phi <2 x i32> [ <i32 1, i32 2>, %vector.ph ], [ %vec.ind.next3, %vector.body ]
 ; CHECK-NEXT:    %vector.recur = phi <2 x i32> [ <i32 poison, i32 42>, %vector.ph ], [ %vec.ind4, %vector.body ]