[LV] Use PHI recipe instead of PredRecipe for subsequent uses.

[fhahn]

Summary

At the moment, the VPPRedInstPHIRecipe is not used in subsequent uses of
the predicate recipe. This incorrectly models the def-use chains, as all
later uses should use the phi recipe. Fix that by delaying recording of
the recipe.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8465

Above use of Op is unrelated to the fix, right?

8466

There seems to be some redundancy left here?

8469

Re-associating Instr with PHIRecipe instead of some previous VPValue (i.e., PredRecipe) via removeVPValueFor()/addVPValue() in order to affect subsequent get[OrAdd]VPValue()'s, seems aligned with re-associating setRecipe() to affect subsequent getRecipe()'s. Should we retain the initial setRecipe() which aligns with initial addVPValue(), and introduce the ability to resetRecipe() here? Can also replace removeVPValue()(+addVPValue()) with replaceVPValue(). The other (two) instances of removeVPValue()/addVPValue() pairs, namely adjustRecipesForReductions() and when transforming InterleaveGroups, should not resetRecipe(), right?

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

474

Should VPlan's def/use verification checks and/or splice/FOR/header-phi recipes assert that values across the backedge are indeed such?

[fhahn]

Simplify code.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8465

This is actually an unnecessary change in the latest version of the patch, removed! But it turns out that the call to getOrAddVPValue is actually unnecessary and we can use PredRecipe instead: 6f7347b888a4

8466

Yes, cleaned up! Only setRecipe remains.

8469

Adding a resetRecipe would be an option, but resetting a VPValue/recipe should only be an exception. In this case it seems cleaner to just delay setting it. WDYT?

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

474

I think a check that defs dominate uses would catch that in general without the need for special handling. It might be possible to extend the verifier without fully fledged VP dominator support.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8408–8409

This addVPValue was next to setRecipe; could it too sink to remain next to it?

8447–8450

nit: can avoid passing Instr given that it's underlying PredRecipe.

8469

Agreed, but would be good to align (re)setRecipe with (remove)addVPValue; could the latter also be delayed, considering the cleaned-up call to getOrAddVPValue?

[fhahn]

Address latest comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8408–8409

Ah yes, this can be sunk, removing the need for the later removeVPValue!

8447–8450

Simplified, thanks!

8469

In the latest version there's no need for resetting, as the addVPValue can also be delayed until this point.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8408–8409

Very well!

8447–8450

Very well!

8469

Even better.

Should also Plan->addVPValue(Instr, PredRecipe) here, retaining existing behavior? Or OTOH if Instr->getType()->isVoidTy() perhaps neither addVPValue nor setRecipe are needed for it?

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8469

Plan->addVPValue(Instr, PredRecipe)

Given that Instr doesn't have a result value (due to void type) there is no need to add the VPValue here. I think setRecipe is still needed, in case something needs to be moved after the recipe for Instr.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8408–8409

This patch deals with setRecipe() being done here too early w/o being reset later, erroneously. addVPValue is also done here too early - whether I defines a value or returns void, is predicated or not - but is reset correctly later. It would be good to keep the two together, so if the fix for setRecipe is to postpone it - move addVPValue as well. However, avoiding a redundant addVPValue when I returns void calls for a separate patch?

8469

ok, best for this patch to retain current addVPValue behavior and focus on fixing setRecipe bug only? Separating the potential removal of addVPValue for result-less Instr's, and possibly that of setRecipe as well (the two should arguably be merged) to a subsequent patch, as noted above?

[fhahn]

Also use addVPValue when type is void.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8408–8409

r. It would be good to keep the two together, so if the fix for setRecipe is to postpone it - move addVPValue as well. However, avoiding a redundant addVPValue when I returns void calls for a separate patch?

Sounds good, I added addVPValue in the else branch as well below, to be removed separately.

8469

Sounds good, I added the addVPValue to the else branch as well here.

[Ayal]

Thanks!!
LGTM, Ship it.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

case Intrinsic::lifetime_end:
       IsUniform = true;
       break;
     default:
       break;
     }
   }
 
   auto *Recipe = new VPReplicateRecipe(I, Plan->mapToVPValues(I->operands()),
                                        IsUniform, IsPredicated);
-  setRecipe(I, Recipe);
-  Plan->addVPValue(I, Recipe);
 
   // Find if I uses a predicated instruction. If so, it will use its scalar
   // value. Avoid hoisting the insert-element which packs the scalar value into
   // a vector value, as that happens iff all users use the vector value.
   for (VPValue *Op : Recipe->operands()) {
     auto *PredR = dyn_cast_or_null<VPPredInstPHIRecipe>(Op->getDef());
     if (!PredR)
       continue;
     auto *RepR =
         cast_or_null<VPReplicateRecipe>(PredR->getOperand(0)->getDef());
     assert(RepR->isPredicated() &&
            "expected Replicate recipe to be predicated");
     RepR->setAlsoPack(false);
   }
 
   // Finalize the recipe for Instr, first if it is not predicated.
   if (!IsPredicated) {
     LLVM_DEBUG(dbgs() << "LV: Scalarizing:" << *I << "\n");
+    setRecipe(I, Recipe);
+    Plan->addVPValue(I, Recipe);
     VPBB->appendRecipe(Recipe);
     return VPBB;
   }
   LLVM_DEBUG(dbgs() << "LV: Scalarizing and predicating:" << *I << "\n");
 
   VPBlockBase *SingleSucc = VPBB->getSingleSuccessor();
   assert(SingleSucc && "VPBB must have a single successor when handling "
                        "predicated replication.");
   VPBlockUtils::disconnectBlocks(VPBB, SingleSucc);
   // Record predicated instructions for above packing optimizations.
-  VPBlockBase *Region = createReplicateRegion(I, Recipe, Plan);
+  VPBlockBase *Region = createReplicateRegion(Recipe, Plan);
   VPBlockUtils::insertBlockAfter(Region, VPBB);
   auto *RegSucc = new VPBasicBlock();
   VPBlockUtils::insertBlockAfter(RegSucc, Region);
   VPBlockUtils::connectBlocks(RegSucc, SingleSucc);
   return RegSucc;
 }
 
-VPRegionBlock *VPRecipeBuilder::createReplicateRegion(
-    Instruction *Instr, VPReplicateRecipe *PredRecipe, VPlanPtr &Plan) {
+VPRegionBlock *
+VPRecipeBuilder::createReplicateRegion(VPReplicateRecipe *PredRecipe,
+                                       VPlanPtr &Plan) {
+  Instruction *Instr = PredRecipe->getUnderlyingInstr();
   // Instructions marked for predication are replicated and placed under an
   // if-then construct to prevent side-effects.
-
   // Generate recipes to compute the block mask for this region.
   VPValue *BlockInMask = createBlockInMask(Instr->getParent(), Plan);
 
   // Build the triangular if-then region.
   std::string RegionName = (Twine("pred.") + Instr->getOpcodeName()).str();
   assert(Instr->getParent() && "Predicated instruction not in any basic block");
   auto *BOMRecipe = new VPBranchOnMaskRecipe(BlockInMask);
   auto *Entry = new VPBasicBlock(Twine(RegionName) + ".entry", BOMRecipe);
   auto *PHIRecipe = Instr->getType()->isVoidTy()
                         ? nullptr
                         : new VPPredInstPHIRecipe(PredRecipe);
   if (PHIRecipe) {
-    Plan->removeVPValueFor(Instr);
+    setRecipe(Instr, PHIRecipe);
     Plan->addVPValue(Instr, PHIRecipe);
-  }
+  } else
+    setRecipe(Instr, PredRecipe);
+
   auto *Exiting = new VPBasicBlock(Twine(RegionName) + ".continue", PHIRecipe);
   auto *Pred = new VPBasicBlock(Twine(RegionName) + ".if", PredRecipe);
   VPRegionBlock *Region = new VPRegionBlock(Entry, Exiting, RegionName, true);
 
   // Note: first set Entry as region entry and then connect successors starting
   // from it in order, to propagate the "parent" of each VPBasicBlock.
   VPBlockUtils::insertTwoBlocksAfter(Pred, Exiting, Entry);
   VPBlockUtils::connectBlocks(Pred, Exiting);

llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h

public:
   VPRecipeBase *getRecipe(Instruction *I) {
     assert(Ingredient2Recipe.count(I) &&
            "Recording this ingredients recipe was not requested");
     assert(Ingredient2Recipe[I] != nullptr &&
            "Ingredient doesn't have a recipe");
     return Ingredient2Recipe[I];
   }
 
-  /// Create a replicating region for instruction \p I that requires
-  /// predication. \p PredRecipe is a VPReplicateRecipe holding \p I.
-  VPRegionBlock *createReplicateRegion(Instruction *I,
-                                       VPReplicateRecipe *PredRecipe,
+  /// Create a replicating region for \p PredRecipe.
+  VPRegionBlock *createReplicateRegion(VPReplicateRecipe *PredRecipe,
                                        VPlanPtr &Plan);
 
   /// Build a VPReplicationRecipe for \p I and enclose it within a Region if it
   /// 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.

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

 ; CHECK-NEXT: Live-in vp<[[BTC:%.+]]> = backedge-taken count
 ; CHECK-EMPTY:
 ; CHECK-NEXT: vector.ph:
 ; CHECK-NEXT: Successor(s): vector loop
 ; CHECK-EMPTY:
 ; CHECK-NEXT: <x1> vector loop: {
 ; CHECK-NEXT:   vector.body:
 ; CHECK-NEXT:     EMIT vp<[[CAN_IV:%.+]]> = CANONICAL-INDUCTION
-; CHECK-NEXT:     FIRST-ORDER-RECURRENCE-PHI ir<%.pn> = phi ir<0>, ir<%l>
+; CHECK-NEXT:     FIRST-ORDER-RECURRENCE-PHI ir<%.pn> = phi ir<0>, vp<[[P_L:%.+]]>
 ; CHECK-NEXT:     EMIT vp<[[WIDE_IV:%.+]]> = WIDEN-CANONICAL-INDUCTION vp<[[CAN_IV]]>
 ; CHECK-NEXT:     EMIT vp<[[CMP:%.+]]> = icmp ule vp<[[WIDE_IV]]> vp<[[BTC]]>
 ; CHECK-NEXT:   Successor(s): loop.0
 ; CHECK-EMPTY:
 ; CHECK-NEXT:   loop.0:
 ; CHECK-NEXT:   Successor(s): pred.load
 ; CHECK-EMPTY:
 ; CHECK-NEXT:   <xVFxUF> pred.load: {
 ; CHECK-NEXT:     pred.load.entry:
 ; CHECK-NEXT:       BRANCH-ON-MASK vp<[[CMP]]>
 ; CHECK-NEXT:     Successor(s): pred.load.if, pred.load.continue
 ; CHECK-EMPTY:
 ; CHECK-NEXT:     pred.load.if:
 ; CHECK-NEXT:       REPLICATE ir<%l> = load ir<%src> (S->V)
 ; CHECK-NEXT:     Successor(s): pred.load.continue
 ; CHECK-EMPTY:
 ; CHECK-NEXT:     pred.load.continue:
-; CHECK-NEXT:       PHI-PREDICATED-INSTRUCTION vp<[[P_L:%.+]]> = ir<%l>
+; CHECK-NEXT:       PHI-PREDICATED-INSTRUCTION vp<[[P_L]]> = ir<%l>
 ; CHECK-NEXT:     No successors
 ; CHECK-NEXT:   }
 ; CHECK-NEXT:   Successor(s): pred.load.succ
 ; CHECK-EMPTY:
 ; CHECK-NEXT:   pred.load.succ:
-; CHECK-NEXT:     EMIT vp<[[SPLICE:%.+]]> = first-order splice ir<%.pn> ir<%l>
+; CHECK-NEXT:     EMIT vp<[[SPLICE:%.+]]> = first-order splice ir<%.pn> vp<[[P_L]]>
 ; CHECK-NEXT:   Successor(s): pred.sdiv
 ; CHECK-EMPTY:
 ; CHECK-NEXT:   <xVFxUF> pred.sdiv: {
 ; CHECK-NEXT:     pred.sdiv.entry:
 ; CHECK-NEXT:       BRANCH-ON-MASK vp<[[CMP]]>
 ; CHECK-NEXT:     Successor(s): pred.sdiv.if, pred.sdiv.continue
 ; CHECK-EMPTY:
 ; CHECK-NEXT:     pred.sdiv.if:

llvm/test/Transforms/LoopVectorize/vplan-sink-scalars-and-merge.ll

 ; CHECK-EMPTY:
 ; CHECK-NEXT: vector.ph:
 ; CHECK-NEXT: Successor(s): vector loop
 ; CHECK-EMPTY:
 ; CHECK-NEXT: <x1> vector loop: {
 ; CHECK-NEXT: vector.body:
 ; CHECK-NEXT:   EMIT vp<[[CAN_IV:%.+]]> = CANONICAL-INDUCTION
 ; CHECK-NEXT:   WIDEN-INDUCTION %iv = phi 0, %iv.next, ir<1>
-; CHECK-NEXT:   FIRST-ORDER-RECURRENCE-PHI ir<%for> = phi ir<0>, ir<%lv.a>
+; CHECK-NEXT:   FIRST-ORDER-RECURRENCE-PHI ir<%for> = phi ir<0>, vp<[[PRED:%.+]]>
 ; CHECK-NEXT:   vp<[[STEPS:%.+]]> = SCALAR-STEPS vp<[[CAN_IV]]>, ir<0>, ir<1>
 ; CHECK-NEXT:   EMIT vp<[[MASK:%.+]]> = icmp ule ir<%iv> vp<[[BTC]]>
 ; CHECK-NEXT:   REPLICATE ir<%gep.a> = getelementptr ir<@a>, ir<0>, vp<[[STEPS]]>
 ; CHECK-NEXT: Successor(s): pred.load
 ; CHECK-EMPTY:
 ; CHECK-NEXT: <xVFxUF> pred.load: {
 ; CHECK-NEXT:   pred.load.entry:
 ; CHECK-NEXT:     BRANCH-ON-MASK vp<[[MASK]]>
 ; CHECK-NEXT:   Successor(s): pred.load.if, pred.load.continue
 ; CHECK-EMPTY:
 ; CHECK-NEXT:   pred.load.if:
 ; CHECK-NEXT:     REPLICATE ir<%lv.a> = load ir<%gep.a>
 ; CHECK-NEXT:   Successor(s): pred.load.continue
 ; CHECK-EMPTY:
 ; CHECK-NEXT:   pred.load.continue:
-; CHECK-NEXT:     PHI-PREDICATED-INSTRUCTION vp<[[PRED:%.+]]> = ir<%lv.a>
+; CHECK-NEXT:     PHI-PREDICATED-INSTRUCTION vp<[[PRED]]> = ir<%lv.a>
 ; CHECK-NEXT:   No successors
 ; CHECK-NEXT: }
 ; CHECK-NEXT: Successor(s): loop.0
 ; CHECK-EMPTY:
 ; CHECK-NEXT: loop.0:
-; CHECK-NEXT:   EMIT vp<[[SPLICE:%.+]]> = first-order splice ir<%for> ir<%lv.a>
+; CHECK-NEXT:   EMIT vp<[[SPLICE:%.+]]> = first-order splice ir<%for> vp<[[PRED]]>
 ; CHECK-NEXT: Successor(s): loop.1
 ; CHECK-EMPTY:
 ; CHECK-NEXT: loop.1:
 ; CHECK-NEXT: Successor(s): pred.store
 ; CHECK-EMPTY:
 ; CHECK-NEXT: <xVFxUF> pred.store: {
 ; CHECK-NEXT:   pred.store.entry:
 ; CHECK-NEXT:     BRANCH-ON-MASK vp<[[MASK]]>