[VPlan] Move remove dead recipes before merging regions.

[fhahn]

Summary

This can enable additional region merging, while not losing
opportunities as region merging does not produce dead recipes.

[Ayal]

This minimal improvement is fine, thanks! Adding some optional nits:

Would "[VPlan] Move remove dead recipes before merging regions." be a clearer title?

This can enable additional region merging.

while OTOH not losing opportunities as region merging does not produce dead recipes?

Note that it may be useful for VPlan2VPlan transforms to return an indication if they made any changes.

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

1106

Should removeDeadRecipes also run after mergeReplicateRegions, to clean-up such phi recipes it leaves behind?

1143

Hmm, this dead_gep may indeed prevent regions to merge, but is it visible in VPlan?

[fhahn]

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

1106

Yes, those should also be removed, what is missing is handling in mayHaveSideeffects, which I am also planning on adding as follow-up.

1143

Yes it should be, but we only print the plans once, after all transforms have been applied, so it is not shown in the dump

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
   Plan->setName(PlanName);
 
   // From this point onwards, VPlan-to-VPlan transformations may change the plan
   // in ways that accessing values using original IR values is incorrect.
   Plan->disableValue2VPValue();
 
   VPlanTransforms::optimizeInductions(*Plan, *PSE.getSE());
   VPlanTransforms::sinkScalarOperands(*Plan);
-  VPlanTransforms::mergeReplicateRegions(*Plan);
   VPlanTransforms::removeDeadRecipes(*Plan);
+  VPlanTransforms::mergeReplicateRegions(*Plan);
   VPlanTransforms::removeRedundantExpandSCEVRecipes(*Plan);
 
   // Fold Exit block into its predecessor if possible.
   // TODO: Fold block earlier once all VPlan transforms properly maintain a
   // VPBasicBlock as exit.
   VPBlockUtils::tryToMergeBlockIntoPredecessor(TopRegion->getExiting());
 
   assert(VPlanVerifier::verifyPlanIsValid(*Plan) && "VPlan is invalid");

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

 ; 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<[[SCALAR_STEPS:%.+]]>    = SCALAR-STEPS vp<[[CAN_IV]]>, ir<%n>, 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.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<%gep.src> = getelementptr ir<%src>, vp<[[SCALAR_STEPS]]>
-; CHECK-NEXT:       REPLICATE ir<%l> = load ir<%gep.src>
-; CHECK-NEXT:     Successor(s): pred.load.continue
-; CHECK-EMPTY:
-; CHECK-NEXT:     pred.load.continue:
-; CHECK-NEXT:       PHI-PREDICATED-INSTRUCTION vp<[[P_LOAD:%.+]]> = ir<%l>
-; CHECK-NEXT:     No successors
-; CHECK-NEXT:   }
 ; CHECK-NEXT:   Successor(s): loop.0
 ; CHECK-EMPTY:
 ; CHECK-NEXT:   loop.0:
 ; 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<%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 vp<[[P_LOAD]]>, ir<%gep.dst>
+; 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>
 ; CHECK-NEXT:     No successors
 ; CHECK-NEXT:   }
 ; CHECK-NEXT:   Successor(s): loop.1
 ; CHECK-EMPTY:
 ; CHECK-NEXT:   loop.1:
 ; CHECK-NEXT:     EMIT vp<[[CAN_IV_NEXT:%.+]]> = VF * UF +  vp<[[CAN_IV]]>
 ; CHECK-NEXT:     EMIT branch-on-count  vp<[[CAN_IV_NEXT]]> vp<[[VEC_TC]]>
 ; CHECK-NEXT:   No successors
 ; CHECK-NEXT: }
 ; CHECK-NEXT: Successor(s): middle.block
 ; CHECK-EMPTY:
 ; CHECK-NEXT: middle.block:
 ; CHECK-NEXT: No successors
 ; CHECK-NEXT: }
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32[ %n, %entry ], [ %iv.next, %loop ]
   %iv.next = add nsw i32 %iv, -1
   %gep.src = getelementptr inbounds i32, i32* %src, i32 %iv
   %l = load i32, i32* %gep.src, align 16
   %dead_gep = getelementptr inbounds i32, i32* %dst, i64 1
   %gep.dst = getelementptr inbounds i32, i32* %dst, i32 %iv
   store i32 %l, i32* %gep.dst, align 16
   %ec = icmp eq i32 %iv.next, 0
   br i1 %ec, label %exit, label %loop
 
 exit:
   ret void
 }