[VPlan] Consider all recipes in replicate blocks as sink candidates.

[fhahn]

Summary

Update sinkScalarOperands to consider all operands of recipes in
replicate blocks as sink candidates This enables additional sinking
opportunities and is another step towards retiring LLVM IR-based
sinkScalarOperands.

Depends on D139788.

[Ayal]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

112–113

Following the documentation iterate over VPBlockUtils::blocksOnly<VPRegionBlock>(Iter)?

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

35

The iterative scan up use-def chains stops at GEPs?

[fhahn]

Adjust code to iterate over region blocks, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

112–113

Done, thanks!

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

35

At the moment only replicate & scalar-steps recipe can be sunk.

[Ayal]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

125

nit: Recipe.getParent() >> VPBB (independent of this patch).

Perhaps a Replicating Region, which represents an "if-then" structured-control-flow hammock, should provide an interface for retrieving its (then) "replicating (basic) block".

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

35

Right, but curious why the use-def scan failed to sink vp<[[STEPS]]> used by sunk REPLICATEs of GEPS while scanning all recipes in replicate block succeeded. Is this due to the now iterative nature of applying sinkScalarOperands()?

[fhahn]

This is no longer needed after aa2414729ebb

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

125

nit: Recipe.getParent() >> VPBB (independent of this patch).

Done in 435e220ba6a41afbeaef6019febddc1b89bf4214

Perhaps a Replicating Region, which represents an "if-then" structured-control-flow hammock, should provide an interface for retrieving its (then) "replicating (basic) block".

Sounds like a good follow up!

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

35

Ah right! I had another look and the issue was that operands of instructions that do not need sinking aren't added to the worklist. Should be fixed by aa2414729ebb

[Ayal]

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

35

Hmm, that may have been intentional - to prevent revisiting same candidates multiple times during a scan up use-def chains. But that assumed operands that do not need sinking were sunk in the "current" scan - when activated only once, starting with a single seed per replicate region. Whereas now the first scan starts with a single seed but repeated iterative scans should indeed consider all / more-than-one?

[fhahn]

Re-open the revision as after discussion this approach seems preferable to aa2414729ebb

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

35

As discussed, aa2414729ebb has been reverted and the current patch seems preferable;

Whereas now the first scan starts with a single seed but repeated iterative scans should indeed consider all / more-than-one?

Yes, now sinkScalarOperands may be called for triangles with multiple instructions.

[fhahn]

ping :)

[Ayal]

Looks good to me.
May indicate in the commit message that this addresses the iterative nature of sink scalar operands where it is invoked repeatedly.

[fhahn]

Thanks, rebase before landing.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

for (VPRecipeBase &Ingredient :
       }
     }
   }
 }
 
 bool VPlanTransforms::sinkScalarOperands(VPlan &Plan) {
   auto Iter = vp_depth_first_deep(Plan.getEntry());
   bool Changed = false;
-  // First, collect the operands of all predicated replicate recipes as seeds
-  // for sinking.
+  // First, collect the operands of all recipes in replicate blocks as seeds for
+  // sinking.
   SetVector<std::pair<VPBasicBlock *, VPRecipeBase *>> WorkList;
-  for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Iter)) {
-    for (auto &Recipe : *VPBB) {
-      auto *RepR = dyn_cast<VPReplicateRecipe>(&Recipe);
-      if (!RepR || !RepR->isPredicated())
-        continue;
-      for (VPValue *Op : RepR->operands())
+  for (VPRegionBlock *VPR : VPBlockUtils::blocksOnly<VPRegionBlock>(Iter)) {
+    VPBasicBlock *EntryVPBB = VPR->getEntryBasicBlock();
+    if (!VPR->isReplicator() || EntryVPBB->getSuccessors().size() != 2)
+      continue;
+    VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(EntryVPBB->getSuccessors()[0]);
+    if (!VPBB || VPBB->getSingleSuccessor() != VPR->getExitingBasicBlock())
+    for (auto &Recipe : *VPBB) {
+      for (VPValue *Op : Recipe.operands())
         if (auto *Def = Op->getDefiningRecipe())
           WorkList.insert(std::make_pair(VPBB, Def));
     }
   }
 
   bool ScalarVFOnly = Plan.hasScalarVFOnly();
   // Try to sink each replicate or scalar IV steps recipe in the worklist.
   for (unsigned I = 0; I != WorkList.size(); ++I) {
     VPBasicBlock *SinkTo;
     VPRecipeBase *SinkCandidate;

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

 ; 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<%recur> = phi ir<0>, ir<%recur.next>
 ; CHECK-NEXT:   WIDEN-INDUCTION %iv = phi 0, %iv.next, ir<1>
-; CHECK-NEXT:   vp<[[STEPS:%.+]]> = SCALAR-STEPS vp<[[CAN_IV]]>, ir<1>
 ; CHECK-NEXT:   EMIT vp<[[MASK:%.+]]> = icmp ule ir<%iv> vp<[[BTC]]>
 ; CHECK-NEXT:   WIDEN ir<%recur.next> = sext ir<%y>
 ; CHECK-NEXT:   EMIT vp<[[SPLICE:%.+]]> = first-order splice ir<%recur> ir<%recur.next>
 ; 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]]>
 ; CHECK-NEXT:   Successor(s): pred.store.if, pred.store.continue
 ; CHECK-EMPTY:
 ; CHECK-NEXT:   pred.store.if:
 ; CHECK-NEXT:     REPLICATE ir<%rem> = srem vp<[[SPLICE]]>, ir<%x>
+; CHECK-NEXT:     vp<[[STEPS:%.+]]> = SCALAR-STEPS vp<[[CAN_IV]]>, ir<1>
 ; CHECK-NEXT:     REPLICATE ir<%rem.div> = sdiv ir<20>, ir<%rem>
 ; CHECK-NEXT:     REPLICATE ir<%gep> = getelementptr ir<%ptr>, vp<[[STEPS]]>
 ; CHECK-NEXT:     REPLICATE store ir<%rem.div>, ir<%gep>
 ; CHECK-NEXT:     REPLICATE ir<%gep.2> = getelementptr ir<%dst.2>, vp<[[STEPS]]>
 ; CHECK-NEXT:     REPLICATE store ir<%rem.div>, ir<%gep.2>
 ; CHECK-NEXT:   Successor(s): pred.store.continue
 ; CHECK-EMPTY:
 ; CHECK-NEXT:   pred.store.continue:

llvm/test/Transforms/LoopVectorize/interleave-and-scalarize-only.ll

 ; DBG-NEXT: vector.ph:
 ; DBG-NEXT: Successor(s): vector loop
 ; DBG-EMPTY:
 ; DBG-NEXT: <x1> vector loop: {
 ; DBG-NEXT:   vector.body:
 ; DBG-NEXT:     EMIT vp<[[CAN_IV:%.+]]> = CANONICAL-INDUCTION
 ; DBG-NEXT:     vp<[[DERIVED_IV:%.+]]> = DERIVED-IV ir<false> + vp<[[CAN_IV]]> * ir<true>
 ; DBG-NEXT:     vp<[[STEPS1:%.+]]>    = SCALAR-STEPS vp<[[DERIVED_IV]]>, ir<true>
-; DBG-NEXT:     vp<[[STEPS2:%.+]]>    = SCALAR-STEPS vp<[[CAN_IV]]>, ir<1>
 ; DBG-NEXT:   Successor(s): pred.store
 ; DBG-EMPTY:
 ; DBG-NEXT:   <xVFxUF> pred.store: {
 ; DBG-NEXT:     pred.store.entry:
 ; DBG-NEXT:       BRANCH-ON-MASK vp<[[STEPS1]]>
 ; DBG-NEXT:     Successor(s): pred.store.if, pred.store.continue
 ; DBG-EMPTY:
 ; DBG-NEXT:     pred.store.if:
+; DBG-NEXT:       vp<[[STEPS2:%.+]]>    = SCALAR-STEPS vp<[[CAN_IV]]>, ir<1>
 ; DBG-NEXT:       CLONE ir<%gep.src> = getelementptr ir<%src>, vp<[[STEPS2]]>
 ; DBG-NEXT:       CLONE ir<%l> = load ir<%gep.src>
 ; DBG-NEXT:       CLONE ir<%gep.dst> = getelementptr ir<%dst>, vp<[[STEPS2]]>
 ; DBG-NEXT:       CLONE store ir<%l>, ir<%gep.dst>
 ; DBG-NEXT:     Successor(s): pred.store.continue
 ; DBG-EMPTY:
 ; DBG-NEXT:     pred.store.continue:
 ; DBG-NEXT:       PHI-PREDICATED-INSTRUCTION vp<{{.+}}> = ir<%l>

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:   vp<[[STEPS:%.+]]> = SCALAR-STEPS vp<[[CAN_IV]]>, ir<1>
 ; CHECK-NEXT:   EMIT vp<[[MASK:%.+]]> = icmp ule ir<%iv> vp<[[BTC]]>
 ; CHECK-NEXT: Successor(s): pred.store
 
 ; CHECK:      <xVFxUF> pred.store: {
 ; CHECK-NEXT:   pred.store.entry:
 ; CHECK-NEXT:     BRANCH-ON-MASK vp<[[MASK]]>
 ; CHECK-NEXT:   Successor(s): pred.store.if, pred.store.continue
 
 ; CHECK:      pred.store.if:
+; CHECK-NEXT:     vp<[[STEPS:%.+]]> = SCALAR-STEPS vp<[[CAN_IV]]>, ir<1>
 ; CHECK-NEXT:     REPLICATE ir<%gep.b> = getelementptr ir<@b>, ir<0>, vp<[[STEPS]]>
 ; CHECK-NEXT:     REPLICATE ir<%lv.b> = load ir<%gep.b>
 ; CHECK-NEXT:     REPLICATE ir<%add> = add ir<%lv.b>, ir<10>
 ; CHECK-NEXT:     REPLICATE ir<%gep.a> = getelementptr ir<@a>, ir<0>, vp<[[STEPS]]
 ; CHECK-NEXT:     REPLICATE ir<%mul> = mul ir<2>, ir<%add>
 ; CHECK-NEXT:     REPLICATE store ir<%mul>, ir<%gep.a>
 ; CHECK-NEXT:   Successor(s): pred.store.continue
 
 ; CHECK:      pred.store.continue:

 ; 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:     vp<[[DERIVED_IV:%.+]]> = DERIVED-IV ir<%n> + vp<[[CAN_IV]]> * ir<-1>
-; CHECK-NEXT:     vp<[[SCALAR_STEPS:%.+]]>    = SCALAR-STEPS vp<[[DERIVED_IV]]>, ir<-1>
 ; CHECK-NEXT:     EMIT vp<[[WIDE_IV:%.+]]> = WIDEN-CANONICAL-INDUCTION vp<[[CAN_IV]]>
 ; CHECK-NEXT:     EMIT vp<[[MASK:%.+]]> = icmp ule vp<[[WIDE_IV]]> vp<[[BTC]]>
 ; 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]]>
 ; CHECK-NEXT:     Successor(s): pred.store.if, pred.store.continue
 ; CHECK-EMPTY:
 ; CHECK-NEXT:     pred.store.if:
+; CHECK-NEXT:       vp<[[SCALAR_STEPS:%.+]]>    = SCALAR-STEPS vp<[[DERIVED_IV]]>, ir<-1>
 ; CHECK-NEXT:       REPLICATE ir<%gep.src> = getelementptr ir<%src>, vp<[[SCALAR_STEPS]]>
 ; CHECK-NEXT:       REPLICATE ir<%l> = load ir<%gep.src>
 ; CHECK-NEXT:       REPLICATE ir<%gep.dst> = getelementptr ir<%dst>, vp<[[SCALAR_STEPS]]>
 ; CHECK-NEXT:       REPLICATE store ir<%l>, ir<%gep.dst>
 ; CHECK-NEXT:     Successor(s): pred.store.continue
 ; CHECK-EMPTY:
 ; CHECK-NEXT:     pred.store.continue:
 ; CHECK-NEXT:       PHI-PREDICATED-INSTRUCTION vp<[[P_LOAD:%.+]]> = ir<%l>