[LV] Split off code to create initial VPlan (NFC).

[fhahn]

Summary

Split up tryToBuildVPlanWithVPRecipes into intial plan creation and
optimizations.

Depends on D154640.

[Ayal]

Thanks for following-up with refactoring the excessive tryToBuildVPlanWithVPRecipes!
This raises several thoughts...

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9055

An alternative refactoring may be to outline the second "Now optimize the initial VPlan" part, rather than the first "build Initial VPlan" part. This could be done perhaps by introducing a new VPlanTransforms::process(VPlan) method which manages all passes, similar to the meta-pass createAndOptimizeReplicateRegions().

9073

Should this mark the completion of an initial VPlan, which now fully represents its scope and can be transformed w/o referring to original IR based relations?

9077

This is currently the only transformation which may bail out of building a VPlan entirely. Marking the optional completion of an initial VPlan here would enable separating it from transformations that only improve it w/o bailing out, as in having the caller do:

if (auto Plan = tryToBuildInitialVPlanWithVPRecipes(SubRange, DeadInstructions)) {
  transformVPlanWithRecipes(*Plan); // Or directly VPlanTransforms::process(*Plan);
  VPlans.push_back(std::move(*Plan));
}

which clearly indicates that DeadInstructions and SubRange are not used nor modified by the latter transforming phase.

9079–9080

Note that creating replicate regions is currently the only (meta) pass that is mandatory. It may be useful to have a minimal "-O0" path consisting of vital transforms only, which checks the functional correctness of the outcome.

[fhahn]

Restructure code as suggested by first only splitting off pure VPlan-to-VPlan optimizations.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9055

Adjusted, thanks!

9073

Sounds good as a start, updated!

9077

Adjusted, thanks!

9079–9080

This might be good in the future, not sure how we best model the options (would also be good to allow running individual optimizations)

[Ayal]

This looks good to me, thanks! Adding a couple of final nits.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9080

nit: is replacing return std::move(Plan) here with return Plan possible independent of all other changes?

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

416

Note: this search works around setting FindMyCast directly by retrieving it from Value2VPValue[IRCast], because the latter mapping should be avoided at this time. Perhaps Casts should be converted into CastRecipes and recorded in IV recipe after the latter is built and before Value2VPValue is abandoned.

792

nit: do the local calls above need the VPlanTransforms:: prefix?

[fhahn]

Address cleanups, thanks! I am planning to land this soon.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9080

Yep, split off in 39cf2104507a

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

792

Removed the prefix, thanks!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

void LoopVectorizationPlanner::buildVPlansWithVPRecipes(ElementCount MinVF,
   // control flow is preserved, we should keep them.
   SmallPtrSet<Instruction *, 4> DeadInstructions;
   auto &ConditionalAssumes = Legal->getConditionalAssumes();
   DeadInstructions.insert(ConditionalAssumes.begin(), ConditionalAssumes.end());
 
   auto MaxVFTimes2 = MaxVF * 2;
   for (ElementCount VF = MinVF; ElementCount::isKnownLT(VF, MaxVFTimes2);) {
     VFRange SubRange = {VF, MaxVFTimes2};
-    if (auto Plan = tryToBuildVPlanWithVPRecipes(SubRange, DeadInstructions))
+    if (auto Plan = tryToBuildVPlanWithVPRecipes(SubRange, DeadInstructions)) {
+      // Now optimize the initial VPlan.
+      VPlanTransforms::optimize(*Plan, *PSE.getSE());
+      assert(VPlanVerifier::verifyPlanIsValid(*Plan) && "VPlan is invalid");
       VPlans.push_back(std::move(Plan));
+    }
     VF = SubRange.End;
   }
 }
 
 // Add the necessary canonical IV and branch recipes required to control the
 // loop.
 static void addCanonicalIVRecipes(VPlan &Plan, Type *IdxTy, DebugLoc DL,
                                   TailFoldingStyle Style) {
for (unsigned i = 0; i < IG->getFactor(); ++i)
         MemberR->eraseFromParent();
       }
   }
 
   for (ElementCount VF : Range)
     Plan->addVF(VF);
   Plan->setName("Initial VPlan");
 
   // Replace VPValues for known constant strides guaranteed by predicate scalar
   // evolution.
   for (auto [_, Stride] : Legal->getLAI()->getSymbolicStrides()) {
     auto *StrideV = cast<SCEVUnknown>(Stride)->getValue();
     auto *ScevStride = dyn_cast<SCEVConstant>(PSE.getSCEV(StrideV));
     // Only handle constant strides for now.
     if (!ScevStride)
       continue;
     Constant *CI = ConstantInt::get(Stride->getType(), ScevStride->getAPInt());
 
     auto *ConstVPV = Plan->getVPValueOrAddLiveIn(CI);
     // The versioned value may not be used in the loop directly, so just add a
     // new live-in in those cases.
     Plan->getVPValueOrAddLiveIn(StrideV)->replaceAllUsesWith(ConstVPV);
   }
 
   // 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();
 
   // Sink users of fixed-order recurrence past the recipe defining the previous
   // value and introduce FirstOrderRecurrenceSplice VPInstructions.
   if (!VPlanTransforms::adjustFixedOrderRecurrences(*Plan, Builder))
     return nullptr;
 
-  VPlanTransforms::removeRedundantCanonicalIVs(*Plan);
-  VPlanTransforms::removeRedundantInductionCasts(*Plan);
-
-  VPlanTransforms::optimizeInductions(*Plan, *PSE.getSE());
-  VPlanTransforms::removeDeadRecipes(*Plan);
-
-  VPlanTransforms::createAndOptimizeReplicateRegions(*Plan);
-
-  VPlanTransforms::removeRedundantExpandSCEVRecipes(*Plan);
-  VPlanTransforms::mergeBlocksIntoPredecessors(*Plan);
-
-  assert(VPlanVerifier::verifyPlanIsValid(*Plan) && "VPlan is invalid");
   return Plan;
 }
 
 VPlanPtr LoopVectorizationPlanner::buildVPlan(VFRange &Range) {
   // Outer loop handling: They may require CFG and instruction level
   // transformations before even evaluating whether vectorization is profitable.
   // Since we cannot modify the incoming IR, we need to build VPlan upfront in
   // the vectorization pipeline.
   assert(!OrigLoop->isInnermost());

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

struct VPlanTransforms {
   /// Replaces the VPInstructions in \p Plan with corresponding
   /// widen recipes.
   static void
   VPInstructionsToVPRecipes(VPlanPtr &Plan,
                             function_ref<const InductionDescriptor *(PHINode *)>
                                 GetIntOrFpInductionDescriptor,
                             ScalarEvolution &SE, const TargetLibraryInfo &TLI);
 
+  /// Sink users of fixed-order recurrences after the recipe defining their
+  /// previous value. Then introduce FirstOrderRecurrenceSplice VPInstructions
+  /// to combine the value from the recurrence phis and previous values. The
+  /// current implementation assumes all users can be sunk after the previous
+  /// value, which is enforced by earlier legality checks.
+  /// \returns true if all users of fixed-order recurrences could be re-arranged
+  /// as needed or false if it is not possible. In the latter case, \p Plan is
+  /// not valid.
+  static bool adjustFixedOrderRecurrences(VPlan &Plan, VPBuilder &Builder);
+
+  /// Clear NSW/NUW flags from reduction instructions if necessary.
+  static void clearReductionWrapFlags(VPlan &Plan);
+
+  /// Optimize \p Plan based on \p BestVF and \p BestUF. This may restrict the
+  /// resulting plan to \p BestVF and \p BestUF.
+  static void optimizeForVFAndUF(VPlan &Plan, ElementCount BestVF,
+                                 unsigned BestUF,
+                                 PredicatedScalarEvolution &PSE);
+
+  /// Apply VPlan-to-VPlan optimizations to \p Plan, including induction recipe
+  /// optimizations, dead recipe removal, replicate region optimizations and
+  /// block merging.
+  static void optimize(VPlan &Plan, ScalarEvolution &SE);
+
   /// Wrap predicated VPReplicateRecipes with a mask operand in an if-then
   /// region block and remove the mask operand. Optimize the created regions by
   /// iteratively sinking scalar operands into the region, followed by merging
   /// regions until no improvements are remaining.
   static void createAndOptimizeReplicateRegions(VPlan &Plan);
 
+private:
   /// Remove redundant VPBasicBlocks by merging them into their predecessor if
   /// the predecessor has a single successor.
   static bool mergeBlocksIntoPredecessors(VPlan &Plan);
 
   /// Remove redundant casts of inductions.
   ///
   /// Such redundant casts are casts of induction variables that can be ignored,
   /// because we already proved that the casted phi is equal to the uncasted phi
private:
   /// update the original IV's users. This is an optional optimization to reduce
   /// the needs of vector extracts.
   static void optimizeInductions(VPlan &Plan, ScalarEvolution &SE);
 
   /// Remove redundant EpxandSCEVRecipes in \p Plan's entry block by replacing
   /// them with already existing recipes expanding the same SCEV expression.
   static void removeRedundantExpandSCEVRecipes(VPlan &Plan);
 
-  /// Sink users of fixed-order recurrences after the recipe defining their
-  /// previous value. Then introduce FirstOrderRecurrenceSplice VPInstructions
-  /// to combine the value from the recurrence phis and previous values. The
-  /// current implementation assumes all users can be sunk after the previous
-  /// value, which is enforced by earlier legality checks.
-  /// \returns true if all users of fixed-order recurrences could be re-arranged
-  /// as needed or false if it is not possible. In the latter case, \p Plan is
-  /// not valid.
-  static bool adjustFixedOrderRecurrences(VPlan &Plan, VPBuilder &Builder);
-
-  /// Clear NSW/NUW flags from reduction instructions if necessary.
-  static void clearReductionWrapFlags(VPlan &Plan);
-
-  /// Optimize \p Plan based on \p BestVF and \p BestUF. This may restrict the
-  /// resulting plan to \p BestVF and \p BestUF.
-  static void optimizeForVFAndUF(VPlan &Plan, ElementCount BestVF,
-                                 unsigned BestUF,
-                                 PredicatedScalarEvolution &PSE);
 };
 
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLANTRANSFORMS_H

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

for (auto &Phi : Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis()) {
     auto *IV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
     if (!IV || IV->getTruncInst())
       continue;
 
     // A sequence of IR Casts has potentially been recorded for IV, which
     // *must be bypassed* when the IV is vectorized, because the vectorized IV
     // will produce the desired casted value. This sequence forms a def-use
     // chain and is provided in reverse order, ending with the cast that uses
     // the IV phi. Search for the recipe of the last cast in the chain and
     // replace it with the original IV. Note that only the final cast is
     // expected to have users outside the cast-chain and the dead casts left
     // over will be cleaned up later.
     auto &Casts = IV->getInductionDescriptor().getCastInsts();
     VPValue *FindMyCast = IV;
     for (Instruction *IRCast : reverse(Casts)) {
       VPRecipeBase *FoundUserCast = nullptr;
       for (auto *U : FindMyCast->users()) {
for (unsigned I = 0; I != Worklist.size(); ++I) {
         if (!UserRecipe)
           continue;
         for (VPValue *V : UserRecipe->definedValues())
           Worklist.insert(V);
       }
     }
   }
 }
+
+void VPlanTransforms::optimize(VPlan &Plan, ScalarEvolution &SE) {
+  removeRedundantCanonicalIVs(Plan);
+  removeRedundantInductionCasts(Plan);
+
+  optimizeInductions(Plan, SE);
+  removeDeadRecipes(Plan);
+
+  createAndOptimizeReplicateRegions(Plan);
+
+  removeRedundantExpandSCEVRecipes(Plan);
+  mergeBlocksIntoPredecessors(Plan);
+}