[VPlan] Compute costs for plans directly after construction.

[fhahn]

Summary

Directly compute the cost of a VPlan after construction and track it
together with a plan. This allows moving selecting the best VF to the
planner. This seems to be a good fit anyways, and removes code from the
cost-model that is not directly related to assigning costs to a specific
plan/VF. Later this can be swapped out with computing the cost for a
plan directly.

This may help to simplify D142015.

[tschuett]

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

388

Could you add a comment /// Returns true when Factor A is more profitable than Factor B ? I was unclear about the direction A v.s B.

[fhahn]

Rebase, remove commented out code, improve structure.

[fhahn]

rebase

[fhahn]

Remove unnecessary code, add comment as suggested.

[fhahn]

Ping. I think the latest version should be cleaned up and ready for review.

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

388

Thanks, added the comment!

[fhahn]

Rebase on top of current main

[fhahn]

Rebase on top of current main.

[fhahn]

rebase and ping :)

[Ayal]

Good move towards getting Planning and eventually VPlans involved with their cost.

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

283

Perhaps the following would be better, at-least when first moving VectorizationFactors from CM to LVP: keep VPlans as a vector of all VPlanPtrs, as its name suggests; hold all VectorizationFactors in a separate vector or set indexed by their ElementCount Width (as in LVP::plan()'s CandidateVFs)? Can also hold a map associating each VectorizationFactor with its VPlan, if needed; is the reverse mapping useful?

(Independent of this patch): Hold the boolean IsVec as a field inside VectorizationFactor, rename VectorizationFactor more accurately.

285–288

/// ...

326

nit (independent of this patch): "all the vectorization factors in question"?

345–348

nit: comment deserves update - CandidateVFs is no longer a parameter. (Independent of this patch:) UserVF is irrelevant, behavior of ForceVectorization should be explained.

350

/// ... (independent of this patch)

385

/// ... (independent of this patch)

399

nit (independent of this patch): above needs L but below needs not?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5439

nit (independent of this patch): cache RTCost in VectorizationFactor if TripCount is known and Width isn't scalable?

5461

nit (independent of this patch): comment for multiplying instead of dividing should appear above, before favoring scalable A.

5463

This is independent of Plan, right?

5485

Thought (independent of patch): would a Plan/VectorizationFactor of Width VF with !HasVec be similar to a Plan of Width 1 and UF=VF? If so, is HasVec redundant (when !ForceVectorization)?

5632

nit: can assert there's a Plan that has NextVF.Width?

6333

nit: change independent of this patch?

6785

ditto

8753

nit: also prevents unrolling, hence no need to retain even the scalar VPlan of VF=1 for unrolling UF>1.

[fhahn]

Address comments directly for the patch, will address the independent nits separately, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

283

Thanks, I updated the code to use a separate mapping from VPlan->vector of pair<VectorizationFactor, bool>. This ensures that the costs are associated with a specific VPlan. WDYT?

As for the IsVec field, I am going to investigate if this is actually needed or if we can get the information from the existing VPlan.

285–288

Not needed in the latest version, I removed the code.

345–348

Thanks, updated the comment!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5463

Yes. I think actually filtering out the unprofitable VFs is not really needed, as the loop below should handle all cases already. Removed the code. Could arguably also be split off.

5632

Added, thanks!

8753

Will update this independently.

[fhahn]

Remove need for IsVec boolean flag in LVP.

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

283

As for the IsVec field, I am going to investigate if this is actually needed or if we can get the information from the existing VPlan.

We don't need it at this stage any longer, we can instead just avoid adding such VFs to CandidateVFs. Removed the boolean flag from LVP.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

281

nit: retain initial size of 4?

283

hold all VectorizationFactors in a separate vector or set indexed by their ElementCount Width (as in LVP::plan()'s CandidateVFs)? Can also hold a map associating each VectorizationFactor with its VPlan, if needed; is the reverse mapping useful?

Thanks, I updated the code to use a separate mapping from VPlan->vector of pair<VectorizationFactor, bool>. This ensures that the costs are associated with a specific VPlan. WDYT?

A single cost is currently computed and associated with a specific VF as indicated by expectedCost(), select[Epilogue]VectorizationFactor() and LVP::plan()'s CandidateVFs; a single Plan is expected for each VF including 1 and BestVF. So LVP can hold all VectorizationFactors in a vector for now, or in a set indexed by Width, regardless of their Plans.
Can revisit this if/when the Plan associated with each VectorizationFactor and/or the set of VectorizationFactors corresponding to a Plan's VFs are needed. Sounds reasonable?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5463

Very well. Comment was to clarify that the association with Plans is not needed and if so to remove the named variable Plan.

5489

Worth a comment: all VectorizationFactors cache the same ScalarCost, so pick the first one? It need not represent the scalar VF=1.
Can retain the current call to expectedCost(ScalarFactor) and replace it independent of this patch.

5492

Retain condition that there is more than a (i.e., the scalar) single VFCandidate?
Always initialize ChosenFactor to getMax() and then skip considering scalar VF only if ForceVectorization? (Or else compute ScalarCost and set ChosenFactor to it.)

5493–5494

5496

Simply traverse all VFCandidates in a single loop as before?

5497

nit: retrain comment that scalar cost was already computed?

5628

Simpler to retain single loop over all VectorizationFactors? VPlan used only in assert.

7589

Worth continuing to pass VFCandidates to selectVectorizationFactor()? The former is still initialized to span range of all possible VF's, before trying to build VPlans, which will possibly exclude VF's. Passing VFCandidates to buildVPlansWithVPRecipes() would allow the latter to filter out non candidates (Fixed/Scalable), and then have selectVectorizationFactor() compute costs and select VF from within the remaining candidates? Can also introduce a separate LVP::computeCosts(VFCandidates).

7628

nit: change to auto independent of this patch.

8083–8084

nit: change from push_back to emplace_back independent of this patch?

8084

Where/Are CandidateVFs filled when building w/o recipes?

8736

Could SubRange be excluded from VFCandidates here, for the latter to be traversed subsequently to compute costs independently, rather than fusing it with the construction of each Plan and its SubRange?

8748

Place this dbgs dump and continue after the #ifndef NDEBUG dump below, as done now?

llvm/lib/Transforms/Vectorize/VPlan.h

2323 ↗

(On Diff #518259)

This is redundant?

llvm/test/Transforms/LoopVectorize/AArch64/no_vector_instructions.ll

10 ↗

(On Diff #518259)

Could the error message "Not considering vector loop of width 2 because it will not generate any vector instructions" be retained, even when filtering these options?

[fhahn]

Address latest comments, thanks!

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

281

Retained, thanks!

283

Follow-up patches will break the 1-1 mapping from VFs->Cost e.g. when planning with multiple cost models there may be different plans for the same VFs but with different costs. For that, the VPlan->costs mapping seems to be required; happy to have VF->Cost mapping as intermediate step, but it might lead to less churn to use the Plan->costs mapping in this patch already?

326

Updated in 9fce1fc6f8344871b86.

345–348

Updated in 0b24436591e1bbea5943d7ef816544f2d90d26d2

350

added comment in 6fa07a87abc96c3b924be07ce446e79691a7f186 and moved it here in the patch.

385

add comment, thanks! I also removed the definition in the cost model

399

Removed loop argument in a431402fd262ca54a923842148be6cdcef7ab636

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5489

Thanks, for now the version retained expectedCost(ScalarFactor), to be replaced in a follow-on patch.

5492

Retained the condition for now

5493–5494

Updated, thanks!

5496

There's now no single vector condition all candidate VFs and costs. We either need to iterate over the entries in the map or over the plans, the latter seeming slightly preferable, as it will make it easy to return the associated plan as well (instead of later looking it up)

5497

retained, thanks!

5628

Same as above, there's now no single vector condition all candidate VFs and costs.

7589

I am not sure; the main motivation of the patch is to compute the cost on construction and delaying cost computation until selectVectorizationFactor would still mostly retain the original behavior? AFAICT the original selectVectorizationFactor doesn't filter out candidates before computing the cost; Scalable VFs are only added to VFCandidates below depending on MaxFactors.ScalableVF. So if the target doesn't support scalable VFs, no VPlans with scalable VFs should be generated.

7628

Changed it back to VPlanPtr to retain type info.

8083–8084

Changed back to push_back, emplace_back as only beneficial in earlier versions that created a pair here.

8084

Do you mean for the native path? In that case selectVectorizationFactor isn't used yet, so CandidateVFs isn't used.

Once the change is in we could build on top and try to converge the native and ILV paths at this point and create plans for inner and outer loops and associate costs with the outer loop versions as well.

8736

Updated to retain the original loop and then compute the costs by iterating over all plans and computing costs for all VFs associated with them

8748

moved, thanks!

llvm/lib/Transforms/Vectorize/VPlan.h

2323 ↗

(On Diff #518259)

The latest version uses this to iterate over the VFs of a plan. I changed it to return ArrayRef<> though.

llvm/test/Transforms/LoopVectorize/AArch64/no_vector_instructions.ll

10 ↗

(On Diff #518259)

Yes, this works as expected with the latest version, I undid the change.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

283

This may indeed lead to less churn, but it would be good to reason about which mapping is needed along with a usage that needs it, such as planning with multiple cost models. Given that CM currently holds ProfitableVFs as a vector of VectorizationFactors, suffice for this patch to focus on moving such a vector to LVP?

350

Thanks!

Replace ::Disabled with null/optional? (Independent of this patch. Along with finding a better name for VectorizationFactor)

391

nit (independent of this patch): \p VF is not needed either.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5496

There's now no single vector condition all candidate VFs and costs. We either need to iterate over the entries in the map or over the plans, the latter seeming slightly preferable, as it will make it easy to return the associated plan as well (instead of later looking it up)

OK, but we currently do look it up later.

7589

Agreed, cost should in the long term be computed as part of VPlan2VPlan transformations, which currently take place inside (the excessive) tryToBuildVPlanWithVPRecipes().

8084

Worth a comment when defining VFCandidates that they serve only 'legacy' path.

8736

OK, then worth keeping the original simpler if (auto Plan = ... version?

Or perhaps something like

if (auto Plan = tryToBuildVPlanWithVPRecipes(SubRange, DeadInstructions)) {
  VPlans.push_back(std::move(*Plan));
  computePlanCosts(Plan, SubRange, Costs);
}

where the latter may some day turn into Costs.push_back(Plan->computeCost());

8780

Bailing out of vectorizing a loop due to disallowed conditional stores should better be done by buildVPlansWithVPRecipes() "before" computing their costs / independent of CM? (Independent of this patch).

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

283

Good point, I split off the parts of only moving the selectVectorizationFactor logic to LVP to D150197.

I'll update this patch once that is in, which should also drastically reduce the diff here.

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

class LoopVectorizationPlanner {
   InterleavedAccessInfo &IAI;
 
   PredicatedScalarEvolution &PSE;
 
   const LoopVectorizeHints &Hints;
 
   OptimizationRemarkEmitter *ORE;
 
-  SmallVector<VPlanPtr, 4> VPlans;
+  SmallVector<std::pair<VPlanPtr, SmallVector<VectorizationFactor>>, 4> VPlans;
 
   /// A builder used to construct the current plan.
   VPBuilder Builder;
 
+  using InstructionVFPair = std::pair<Instruction *, ElementCount>;
+  SmallVector<InstructionVFPair> InvalidCosts;
+
 public:
   LoopVectorizationPlanner(Loop *L, LoopInfo *LI, const TargetLibraryInfo *TLI,
                            const TargetTransformInfo *TTI,
                            LoopVectorizationLegality *Legal,
                            LoopVectorizationCostModel &CM,
                            InterleavedAccessInfo &IAI,
                            PredicatedScalarEvolution &PSE,
                            const LoopVectorizeHints &Hints,
void executePlan(ElementCount VF, unsigned UF, VPlan &BestPlan,
                    InnerLoopVectorizer &LB, DominatorTree *DT,
                    bool IsEpilogueVectorization);
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   void printPlans(raw_ostream &O);
 #endif
 
   /// Look through the existing plans and return true if we have one with all
   /// the vectorization factors in question.
   bool hasPlanWithVF(ElementCount VF) const {
-    return any_of(VPlans,
-                  [&](const VPlanPtr &Plan) { return Plan->hasVF(VF); });
+    return any_of(
+        VPlans,
+        [&](const std::pair<VPlanPtr, SmallVector<VectorizationFactor>> &Plan) {
+          return Plan.first->hasVF(VF);
+        });
   }
 
   /// Test a \p Predicate on a \p Range of VF's. Return the value of applying
   /// \p Predicate on Range.Start, possibly decreasing Range.End such that the
   /// returned value holds for the entire \p Range.
   static bool
   getDecisionAndClampRange(const std::function<bool(ElementCount)> &Predicate,
                            VFRange &Range);
 
   /// Check if the number of runtime checks exceeds the threshold.
   bool requiresTooManyRuntimeChecks() const;
 
+  /// \return The most profitable vectorization factor and the cost of that VF.
+  /// This method checks every VF in \p CandidateVFs. If UserVF is not ZERO
+  /// then this vectorization factor will be selected if vectorization is
+  /// possible.
+  VectorizationFactor selectVectorizationFactor();
+
+  VectorizationFactor
+  selectEpilogueVectorizationFactor(const ElementCount MaxVF);
+
 protected:
   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
   /// according to the information gathered by Legal when it checked if it is
   /// legal to vectorize the loop.
   void buildVPlans(ElementCount MinVF, ElementCount MaxVF);
 
 private:
   /// Build a VPlan according to the information gathered by Legal. \return a
private:
   // Adjust the recipes for reductions. For in-loop reductions the chain of
   // instructions leading from the loop exit instr to the phi need to be
   // converted to reductions, with one operand being vector and the other being
   // the scalar reduction chain. For other reductions, a select is introduced
   // between the phi and live-out recipes when folding the tail.
   void adjustRecipesForReductions(VPBasicBlock *LatchVPBB, VPlanPtr &Plan,
                                   VPRecipeBuilder &RecipeBuilder,
                                   ElementCount MinVF);
+
+  std::optional<unsigned> getVScaleForTuning() const;
+
+  bool isMoreProfitable(const VectorizationFactor &A,
+                        const VectorizationFactor &B) const;
+  /// Determines if we have the infrastructure to vectorize loop \p L and its
+  /// epilogue, assuming the main loop is vectorized by \p VF.
+  bool isCandidateForEpilogueVectorization(const Loop &L,
+                                           const ElementCount VF) const;
+
+  /// Returns true if epilogue vectorization is considered profitable, and
+  /// false otherwise.
+  /// \p VF is the vectorization factor chosen for the original loop.
+  bool isEpilogueVectorizationProfitable(const ElementCount VF) const;
 };
 
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

public:
   /// scalable). If the factors are 0, vectorization and interleaving should be
   /// avoided up front.
   FixedScalableVFPair computeMaxVF(ElementCount UserVF, unsigned UserIC);
 
   /// \return True if runtime checks are required for vectorization, and false
   /// otherwise.
   bool runtimeChecksRequired();
 
-  /// \return The most profitable vectorization factor and the cost of that VF.
-  /// This method checks every VF in \p CandidateVFs. If UserVF is not ZERO
-  /// then this vectorization factor will be selected if vectorization is
-  /// possible.
-  VectorizationFactor
-  selectVectorizationFactor(const ElementCountSet &CandidateVFs);
-
-  VectorizationFactor
-  selectEpilogueVectorizationFactor(const ElementCount MaxVF,
-                                    const LoopVectorizationPlanner &LVP);
-
   /// Setup cost-based decisions for user vectorization factor.
   /// \return true if the UserVF is a feasible VF to be chosen.
   bool selectUserVectorizationFactor(ElementCount UserVF) {
     collectUniformsAndScalars(UserVF);
     collectInstsToScalarize(UserVF);
     return expectedCost(UserVF).first.isValid();
   }
 
void invalidateCostModelingDecisions() {
     Scalars.clear();
   }
 
   /// Convenience function that returns the value of vscale_range iff
   /// vscale_range.min == vscale_range.max or otherwise returns the value
   /// returned by the corresponding TLI method.
   std::optional<unsigned> getVScaleForTuning() const;
 
+  using VectorizationCostTy = std::pair<InstructionCost, bool>;
+
+  /// Returns the expected execution cost. The unit of the cost does
+  /// not matter because we use the 'cost' units to compare different
+  /// vector widths. The cost that is returned is *not* normalized by
+  /// the factor width. If \p Invalid is not nullptr, this function
+  /// will add a pair(Instruction*, ElementCount) to \p Invalid for
+  /// each instruction that has an Invalid cost for the given VF.
+  using InstructionVFPair = std::pair<Instruction *, ElementCount>;
+  VectorizationCostTy
+  expectedCost(ElementCount VF,
+               SmallVectorImpl<InstructionVFPair> *Invalid = nullptr);
+
 private:
   unsigned NumPredStores = 0;
 
   /// \return An upper bound for the vectorization factors for both
   /// fixed and scalable vectorization, where the minimum-known number of
   /// elements is a power-of-2 larger than zero. If scalable vectorization is
   /// disabled or unsupported, then the scalable part will be equal to
   /// ElementCount::getScalable(0).
private:
   /// of elements.
   ElementCount getMaxLegalScalableVF(unsigned MaxSafeElements);
 
   /// The vectorization cost is a combination of the cost itself and a boolean
   /// indicating whether any of the contributing operations will actually
   /// operate on vector values after type legalization in the backend. If this
   /// latter value is false, then all operations will be scalarized (i.e. no
   /// vectorization has actually taken place).
-  using VectorizationCostTy = std::pair<InstructionCost, bool>;
-
-  /// Returns the expected execution cost. The unit of the cost does
-  /// not matter because we use the 'cost' units to compare different
-  /// vector widths. The cost that is returned is *not* normalized by
-  /// the factor width. If \p Invalid is not nullptr, this function
-  /// will add a pair(Instruction*, ElementCount) to \p Invalid for
-  /// each instruction that has an Invalid cost for the given VF.
-  VectorizationCostTy
-  expectedCost(ElementCount VF,
-               SmallVectorImpl<InstructionVFPair> *Invalid = nullptr);
 
   /// Returns the execution time cost of an instruction for a given vector
   /// width. Vector width of one means scalar.
   VectorizationCostTy getInstructionCost(Instruction *I, ElementCount VF);
 
   /// The cost-computation logic from getInstructionCost which provides
   /// the vector type as an output parameter.
   InstructionCost getInstructionCost(Instruction *I, ElementCount VF,
private:
 
   /// Returns a range containing only operands needing to be extracted.
   SmallVector<Value *, 4> filterExtractingOperands(Instruction::op_range Ops,
                                                    ElementCount VF) const {
     return SmallVector<Value *, 4>(make_filter_range(
         Ops, [this, VF](Value *V) { return this->needsExtract(V, VF); }));
   }
 
-  /// Determines if we have the infrastructure to vectorize loop \p L and its
-  /// epilogue, assuming the main loop is vectorized by \p VF.
-  bool isCandidateForEpilogueVectorization(const Loop &L,
-                                           const ElementCount VF) const;
-
-  /// Returns true if epilogue vectorization is considered profitable, and
-  /// false otherwise.
-  /// \p VF is the vectorization factor chosen for the original loop.
-  bool isEpilogueVectorizationProfitable(const ElementCount VF) const;
-
 public:
   /// The loop that we evaluate.
   Loop *TheLoop;
 
   /// Predicated scalar evolution analysis.
   PredicatedScalarEvolution &PSE;
 
   /// Loop Info analysis.
if (Subset == Tail || Tail[Subset.size()].first != I) {
       Tail = Tail.drop_front(Subset.size());
       Subset = {};
     } else
       // Grow the subset by one element
       Subset = Tail.take_front(Subset.size() + 1);
   } while (!Tail.empty());
 }
 
-VectorizationFactor LoopVectorizationCostModel::selectVectorizationFactor(
-    const ElementCountSet &VFCandidates) {
-  InstructionCost ExpectedCost = expectedCost(ElementCount::getFixed(1)).first;
-  LLVM_DEBUG(dbgs() << "LV: Scalar loop costs: " << ExpectedCost << ".\n");
-  assert(ExpectedCost.isValid() && "Unexpected invalid cost for scalar loop");
-  assert(VFCandidates.count(ElementCount::getFixed(1)) &&
-         "Expected Scalar VF to be a candidate");
+bool LoopVectorizationPlanner::isMoreProfitable(
+    const VectorizationFactor &A, const VectorizationFactor &B) const {
+  InstructionCost CostA = A.Cost;
+  InstructionCost CostB = B.Cost;
+
+  unsigned MaxTripCount = PSE.getSE()->getSmallConstantMaxTripCount(OrigLoop);
+
+  if (!A.Width.isScalable() && !B.Width.isScalable() &&
+      CM.foldTailByMasking() && MaxTripCount) {
+    // If we are folding the tail and the trip count is a known (possibly small)
+    // constant, the trip count will be rounded up to an integer number of
+    // iterations. The total cost will be PerIterationCost*ceil(TripCount/VF),
+    // which we compare directly. When not folding the tail, the total cost will
+    // be PerIterationCost*floor(TC/VF) + Scalar remainder cost, and so is
+    // approximated with the per-lane cost below instead of using the tripcount
+    // as here.
+    auto RTCostA = CostA * divideCeil(MaxTripCount, A.Width.getFixedValue());
+    auto RTCostB = CostB * divideCeil(MaxTripCount, B.Width.getFixedValue());
+    return RTCostA < RTCostB;
+  }
+
+  // Improve estimate for the vector width if it is scalable.
+  unsigned EstimatedWidthA = A.Width.getKnownMinValue();
+  unsigned EstimatedWidthB = B.Width.getKnownMinValue();
+  if (std::optional<unsigned> VScale = getVScaleForTuning()) {
+    if (A.Width.isScalable())
+      EstimatedWidthA *= *VScale;
+    if (B.Width.isScalable())
+      EstimatedWidthB *= *VScale;
+  }
+
+  // Assume vscale may be larger than 1 (or the value being tuned for),
+  // so that scalable vectorization is slightly favorable over fixed-width
+  // vectorization.
+  if (A.Width.isScalable() && !B.Width.isScalable())
+    return (CostA * B.Width.getFixedValue()) <= (CostB * EstimatedWidthA);
+
+  // To avoid the need for FP division:
+  //      (CostA / A.Width) < (CostB / B.Width)
+  // <=>  (CostA * B.Width) < (CostB * A.Width)
+  return (CostA * EstimatedWidthB) < (CostB * EstimatedWidthA);
+}
+
+std::optional<unsigned> LoopVectorizationPlanner::getVScaleForTuning() const {
+  Function *TheFunction = OrigLoop->getHeader()->getParent();
+  if (TheFunction->hasFnAttribute(Attribute::VScaleRange)) {
+    auto Attr = TheFunction->getFnAttribute(Attribute::VScaleRange);
+    auto Min = Attr.getVScaleRangeMin();
+    auto Max = Attr.getVScaleRangeMax();
+    if (Max && Min == Max)
+      return Max;
+  }
+
+  return TTI->getVScaleForTuning();
+}
+VectorizationFactor LoopVectorizationPlanner::selectVectorizationFactor() {
+  assert(!VPlans.empty());
 
+  InstructionCost ExpectedCost = VPlans[0].second[0].ScalarCost;
   const VectorizationFactor ScalarCost(ElementCount::getFixed(1), ExpectedCost,
                                        ExpectedCost);
   VectorizationFactor ChosenFactor = ScalarCost;
+  LLVM_DEBUG(dbgs() << "LV: Scalar loop costs: " << ExpectedCost << ".\n");
+  assert(hasPlanWithVF(ElementCount::getFixed(1)) &&
+         "Expected Scalar VF to be a candidate");
 
-  bool ForceVectorization = Hints->getForce() == LoopVectorizeHints::FK_Enabled;
-  if (ForceVectorization && VFCandidates.size() > 1) {
+  bool ForceVectorization = Hints.getForce() == LoopVectorizeHints::FK_Enabled;
+  if (ForceVectorization && VPlans.size() > 1) {
     // Ignore scalar width, because the user explicitly wants vectorization.
     // Initialize cost to max so that VF = 2 is, at least, chosen during cost
     // evaluation.
     ChosenFactor.Cost = InstructionCost::getMax();
   }
 
-  SmallVector<InstructionVFPair> InvalidCosts;
-  for (const auto &i : VFCandidates) {
-    // The cost for scalar VF=1 is already calculated, so ignore it.
-    if (i.isScalar())
-      continue;
-
-    VectorizationCostTy C = expectedCost(i, &InvalidCosts);
-    VectorizationFactor Candidate(i, C.first, ScalarCost.ScalarCost);
+  // Filter out unprofitable VFs.
+  for (auto &[_, VFsAndCosts] : VPlans) {
+    erase_if(VFsAndCosts, [this, &ScalarCost](const auto &Candidate) {
+      return !isMoreProfitable(Candidate, ScalarCost);
+    });
 
+    for (const auto &Candidate : VFsAndCosts) {
 #ifndef NDEBUG
     unsigned AssumedMinimumVscale = 1;
     if (std::optional<unsigned> VScale = getVScaleForTuning())
       AssumedMinimumVscale = *VScale;
     unsigned Width =
         Candidate.Width.isScalable()
             ? Candidate.Width.getKnownMinValue() * AssumedMinimumVscale
             : Candidate.Width.getFixedValue();
-    LLVM_DEBUG(dbgs() << "LV: Vector loop of width " << i
+    LLVM_DEBUG(dbgs() << "LV: Vector loop of width " << Candidate.Width
                       << " costs: " << (Candidate.Cost / Width));
-    if (i.isScalable())
+    if (Candidate.Width.isScalable())
       LLVM_DEBUG(dbgs() << " (assuming a minimum vscale of "
                         << AssumedMinimumVscale << ")");
     LLVM_DEBUG(dbgs() << ".\n");
 #endif
 
-    if (!C.second && !ForceVectorization) {
-      LLVM_DEBUG(
-          dbgs() << "LV: Not considering vector loop of width " << i
-                 << " because it will not generate any vector instructions.\n");
-      continue;
-    }
-
-    // If profitable add it to ProfitableVF list.
-    if (isMoreProfitable(Candidate, ScalarCost))
-      ProfitableVFs.push_back(Candidate);
+    /*    if (!C.second && !ForceVectorization) {*/
+    /*LLVM_DEBUG(*/
+    /*dbgs() << "LV: Not considering vector loop of width " << i*/
+    /*<< " because it will not generate any vector instructions.\n");*/
+    /*continue;*/
+    /*}*/
 
     if (isMoreProfitable(Candidate, ChosenFactor))
       ChosenFactor = Candidate;
     }
+  }
 
-  emitInvalidCostRemarks(InvalidCosts, ORE, TheLoop);
+  emitInvalidCostRemarks(InvalidCosts, ORE, OrigLoop);
 
-  if (!EnableCondStoresVectorization && NumPredStores) {
-    reportVectorizationFailure(
-        "There are conditional stores.",
-        "store that is conditionally executed prevents vectorization",
-        "ConditionalStore", ORE, TheLoop);
-    ChosenFactor = ScalarCost;
-  }
+  /*  if (!EnableCondStoresVectorization && NumPredStores) {*/
+  /*reportVectorizationFailure(*/
+  /*"There are conditional stores.",*/
+  /*"store that is conditionally executed prevents vectorization",*/
+  /*"ConditionalStore", ORE, TheLoop);*/
+  /*ChosenFactor = ScalarCost;*/
+  /*}*/
 
   LLVM_DEBUG(if (ForceVectorization && !ChosenFactor.Width.isScalar() &&
                  !isMoreProfitable(ChosenFactor, ScalarCost)) dbgs()
              << "LV: Vectorization seems to be not beneficial, "
              << "but was forced by a user.\n");
   LLVM_DEBUG(dbgs() << "LV: Selecting VF: " << ChosenFactor.Width << ".\n");
   return ChosenFactor;
 }
 
-bool LoopVectorizationCostModel::isCandidateForEpilogueVectorization(
+bool LoopVectorizationPlanner::isCandidateForEpilogueVectorization(
     const Loop &L, ElementCount VF) const {
   // Cross iteration phis such as reductions need special handling and are
   // currently unsupported.
   if (any_of(L.getHeader()->phis(),
              [&](PHINode &Phi) { return Legal->isFixedOrderRecurrence(&Phi); }))
     return false;
 
   // Phis with uses outside of the loop require special handling and are
bool LoopVectorizationPlanner::isCandidateForEpilogueVectorization(
   // non-latch exits properly.  It may be fine, but it needs auditted and
   // tested.
   if (L.getExitingBlock() != L.getLoopLatch())
     return false;
 
   return true;
 }
 
-bool LoopVectorizationCostModel::isEpilogueVectorizationProfitable(
+bool LoopVectorizationPlanner::isEpilogueVectorizationProfitable(
     const ElementCount VF) const {
   // FIXME: We need a much better cost-model to take different parameters such
   // as register pressure, code size increase and cost of extra branches into
   // account. For now we apply a very crude heuristic and only consider loops
   // with vectorization factors larger than a certain value.
 
   // Allow the target to opt out entirely.
-  if (!TTI.preferEpilogueVectorization())
+  if (!TTI->preferEpilogueVectorization())
     return false;
 
   // We also consider epilogue vectorization unprofitable for targets that don't
   // consider interleaving beneficial (eg. MVE).
-  if (TTI.getMaxInterleaveFactor(VF.getKnownMinValue()) <= 1)
+  if (TTI->getMaxInterleaveFactor(VF.getKnownMinValue()) <= 1)
     return false;
   // FIXME: We should consider changing the threshold for scalable
   // vectors to take VScaleForTuning into account.
   if (VF.getKnownMinValue() >= EpilogueVectorizationMinVF)
     return true;
   return false;
 }
 
-VectorizationFactor
-LoopVectorizationCostModel::selectEpilogueVectorizationFactor(
-    const ElementCount MainLoopVF, const LoopVectorizationPlanner &LVP) {
+VectorizationFactor LoopVectorizationPlanner::selectEpilogueVectorizationFactor(
+    const ElementCount MainLoopVF) {
   VectorizationFactor Result = VectorizationFactor::Disabled();
   if (!EnableEpilogueVectorization) {
     LLVM_DEBUG(dbgs() << "LEV: Epilogue vectorization is disabled.\n";);
     return Result;
   }
 
-  if (!isScalarEpilogueAllowed()) {
+  if (!CM.isScalarEpilogueAllowed()) {
     LLVM_DEBUG(
         dbgs() << "LEV: Unable to vectorize epilogue because no epilogue is "
                   "allowed.\n";);
     return Result;
   }
 
   // Not really a cost consideration, but check for unsupported cases here to
   // simplify the logic.
-  if (!isCandidateForEpilogueVectorization(*TheLoop, MainLoopVF)) {
+  if (!isCandidateForEpilogueVectorization(*OrigLoop, MainLoopVF)) {
     LLVM_DEBUG(
         dbgs() << "LEV: Unable to vectorize epilogue because the loop is "
                   "not a supported candidate.\n";);
     return Result;
   }
 
   if (EpilogueVectorizationForceVF > 1) {
     LLVM_DEBUG(dbgs() << "LEV: Epilogue vectorization factor is forced.\n";);
     ElementCount ForcedEC = ElementCount::getFixed(EpilogueVectorizationForceVF);
-    if (LVP.hasPlanWithVF(ForcedEC))
+    if (hasPlanWithVF(ForcedEC))
       return {ForcedEC, 0, 0};
     else {
       LLVM_DEBUG(
           dbgs()
               << "LEV: Epilogue vectorization forced factor is not viable.\n";);
       return Result;
     }
   }
 
-  if (TheLoop->getHeader()->getParent()->hasOptSize() ||
-      TheLoop->getHeader()->getParent()->hasMinSize()) {
+  if (OrigLoop->getHeader()->getParent()->hasOptSize() ||
+      OrigLoop->getHeader()->getParent()->hasMinSize()) {
     LLVM_DEBUG(
         dbgs()
             << "LEV: Epilogue vectorization skipped due to opt for size.\n";);
     return Result;
   }
 
   if (!isEpilogueVectorizationProfitable(MainLoopVF)) {
     LLVM_DEBUG(dbgs() << "LEV: Epilogue vectorization is not profitable for "
                          "this loop\n");
     return Result;
   }
 
   // If MainLoopVF = vscale x 2, and vscale is expected to be 4, then we know
   // the main loop handles 8 lanes per iteration. We could still benefit from
   // vectorizing the epilogue loop with VF=4.
   ElementCount EstimatedRuntimeVF = MainLoopVF;
   if (MainLoopVF.isScalable()) {
     EstimatedRuntimeVF = ElementCount::getFixed(MainLoopVF.getKnownMinValue());
     if (std::optional<unsigned> VScale = getVScaleForTuning())
       EstimatedRuntimeVF *= *VScale;
   }
 
-  for (auto &NextVF : ProfitableVFs)
+  for (auto &[_, VFsAndCosts] : VPlans) {
+    for (const auto &NextVF : VFsAndCosts) {
       if (((!NextVF.Width.isScalable() && MainLoopVF.isScalable() &&
             ElementCount::isKnownLT(NextVF.Width, EstimatedRuntimeVF)) ||
            ElementCount::isKnownLT(NextVF.Width, MainLoopVF)) &&
-        (Result.Width.isScalar() || isMoreProfitable(NextVF, Result)) &&
-        LVP.hasPlanWithVF(NextVF.Width))
+          (Result.Width.isScalar() || isMoreProfitable(NextVF, Result)))
         Result = NextVF;
+    }
+  }
 
   if (Result != VectorizationFactor::Disabled())
     LLVM_DEBUG(dbgs() << "LEV: Vectorizing epilogue loop with VF = "
                       << Result.Width << "\n";);
   return Result;
 }
 
 std::pair<unsigned, unsigned>
while (!Worklist.empty()) {
     Discount += VectorCost - ScalarCost;
     ScalarCosts[I] = ScalarCost;
   }
 
   return Discount;
 }
 
 LoopVectorizationCostModel::VectorizationCostTy
 LoopVectorizationCostModel::expectedCost(
     ElementCount VF, SmallVectorImpl<InstructionVFPair> *Invalid) {
   VectorizationCostTy Cost;
 
   // For each block.
   for (BasicBlock *BB : TheLoop->blocks()) {
     VectorizationCostTy BlockCost;
 
     // For each instruction in the old loop.
if (VF.isScalar()) {
     TTI::OperandValueInfo OpInfo = TTI::getOperandInfo(I->getOperand(0));
     return TTI.getAddressComputationCost(ValTy) +
            TTI.getMemoryOpCost(I->getOpcode(), ValTy, Alignment, AS,
                                TTI::TCK_RecipThroughput, OpInfo, I);
   }
   return getWideningCost(I, VF);
 }
 
 LoopVectorizationCostModel::VectorizationCostTy
 LoopVectorizationCostModel::getInstructionCost(Instruction *I,
                                                ElementCount VF) {
   // If we know that this instruction will remain uniform, check the cost of
   // the scalar version.
   if (isUniformAfterVectorization(I, VF))
     VF = ElementCount::getFixed(1);
 
   if (VF.isVector() && isProfitableToScalarize(I, VF))
if (CM.selectUserVectorizationFactor(UserVF)) {
       LLVM_DEBUG(printPlans(dbgs()));
       return {{UserVF, 0, 0}};
     } else
       reportVectorizationInfo("UserVF ignored because of invalid costs.",
                               "InvalidCost", ORE, OrigLoop);
   }
 
   // Populate the set of Vectorization Factor Candidates.
   ElementCountSet VFCandidates;
   for (auto VF = ElementCount::getFixed(1);
        ElementCount::isKnownLE(VF, MaxFactors.FixedVF); VF *= 2)
     VFCandidates.insert(VF);
   for (auto VF = ElementCount::getScalable(1);
        ElementCount::isKnownLE(VF, MaxFactors.ScalableVF); VF *= 2)
     VFCandidates.insert(VF);
 
   for (const auto &VF : VFCandidates) {
LoopVectorizationPlanner::plan(ElementCount UserVF, unsigned UserIC) {
   buildVPlansWithVPRecipes(ElementCount::getFixed(1), MaxFactors.FixedVF);
   buildVPlansWithVPRecipes(ElementCount::getScalable(1), MaxFactors.ScalableVF);
 
   LLVM_DEBUG(printPlans(dbgs()));
   if (!MaxFactors.hasVector())
     return VectorizationFactor::Disabled();
 
   // Select the optimal vectorization factor.
-  VectorizationFactor VF = CM.selectVectorizationFactor(VFCandidates);
+  VectorizationFactor VF = selectVectorizationFactor();
   assert((VF.Width.isScalar() || VF.ScalarCost > 0) && "when vectorizing, the scalar cost must be non-zero.");
   return VF;
 }
 
 VPlan &LoopVectorizationPlanner::getBestPlanFor(ElementCount VF) const {
-  assert(count_if(VPlans,
-                  [VF](const VPlanPtr &Plan) { return Plan->hasVF(VF); }) ==
-             1 &&
-         "Best VF has not a single VPlan.");
+  assert(
+      count_if(VPlans,
+               [VF](const std::pair<VPlanPtr, SmallVector<VectorizationFactor>>
+                        &Plan) { return Plan.first->hasVF(VF); }) == 1 &&
 
-  for (const VPlanPtr &Plan : VPlans) {
+  for (const auto &[Plan, _] : VPlans) {
     if (Plan->hasVF(VF))
       return *Plan.get();
   }
   llvm_unreachable("No plan found!");
 }
 
 static void AddRuntimeUnrollDisableMetaData(Loop *L) {
   SmallVector<Metadata *, 4> MDs;
void LoopVectorizationPlanner::executePlan(ElementCount BestVF, unsigned BestUF,
   //    predication, updating analyses.
   ILV.fixVectorizedLoop(State, BestVPlan);
 
   ILV.printDebugTracesAtEnd();
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 void LoopVectorizationPlanner::printPlans(raw_ostream &O) {
-  for (const auto &Plan : VPlans)
+  for (const auto &[Plan, _] : VPlans)
     if (PrintVPlansInDotFormat)
       Plan->printDOT(O);
     else
       Plan->print(O);
 }
 #endif
 
 Value *InnerLoopUnroller::getBroadcastInstrs(Value *V) { return V; }

 /// of VF's starting at a given VF and extending it as much as possible. Each
 /// vectorization decision can potentially shorten this sub-range during
 /// buildVPlan().
 void LoopVectorizationPlanner::buildVPlans(ElementCount MinVF,
                                            ElementCount MaxVF) {
   auto MaxVFPlusOne = MaxVF.getWithIncrement(1);
   for (ElementCount VF = MinVF; ElementCount::isKnownLT(VF, MaxVFPlusOne);) {
     VFRange SubRange = {VF, MaxVFPlusOne};
-    VPlans.push_back(buildVPlan(SubRange));
+    VPlans.emplace_back(buildVPlan(SubRange),
+                        SmallVector<VectorizationFactor>());
     VF = SubRange.End;
   }
 }
 
 VPValue *VPRecipeBuilder::createEdgeMask(BasicBlock *Src, BasicBlock *Dst,
                                          VPlan &Plan) {
   assert(is_contained(predecessors(Dst), Src) && "Invalid edge");
 
void LoopVectorizationPlanner::buildVPlansWithVPRecipes(ElementCount MinVF,
   // Add assume instructions we need to drop to DeadInstructions, to prevent
   // them from being added to the VPlan.
   // TODO: We only need to drop assumes in blocks that get flattend. If the
   // control flow is preserved, we should keep them.
   SmallPtrSet<Instruction *, 4> DeadInstructions;
   auto &ConditionalAssumes = Legal->getConditionalAssumes();
   DeadInstructions.insert(ConditionalAssumes.begin(), ConditionalAssumes.end());
 
+  InstructionCost ScalarCost = CM.expectedCost(ElementCount::getFixed(1)).first;
   auto MaxVFPlusOne = MaxVF.getWithIncrement(1);
   for (ElementCount VF = MinVF; ElementCount::isKnownLT(VF, MaxVFPlusOne);) {
     VFRange SubRange = {VF, MaxVFPlusOne};
-    VPlans.push_back(buildVPlanWithVPRecipes(SubRange, DeadInstructions));
+    auto Plan = buildVPlanWithVPRecipes(SubRange, DeadInstructions);
+    SmallVector<VectorizationFactor> Costs;
+    for (ElementCount CostVF = VF;
+         ElementCount::isKnownLT(CostVF, SubRange.End); CostVF *= 2) {
+      InstructionCost VecCost = CM.expectedCost(CostVF, &InvalidCosts).first;
+      Costs.emplace_back(CostVF, VecCost, ScalarCost);
+    }
+    VPlans.emplace_back(std::move(Plan), Costs);
     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) {
   Value *StartIdx = ConstantInt::get(IdxTy, 0);
   auto *StartV = Plan.getOrAddVPValue(StartIdx);
 
   // Add a VPCanonicalIVPHIRecipe starting at 0 to the header.
   auto *CanonicalIVPHI = new VPCanonicalIVPHIRecipe(StartV, DL);
   VPRegionBlock *TopRegion = Plan.getVectorLoopRegion();
   VPBasicBlock *Header = TopRegion->getEntryBasicBlock();
   Header->insert(CanonicalIVPHI, Header->begin());
 
static void addCanonicalIVRecipes(VPlan &Plan, Type *IdxTy, DebugLoc DL,
   EB->appendRecipe(CanonicalIVIncrement);
 
   if (Style == TailFoldingStyle::DataAndControlFlow) {
     // Create the active lane mask instruction in the vplan preheader.
     VPBasicBlock *Preheader = Plan.getEntry()->getEntryBasicBlock();
 
     // We can't use StartV directly in the ActiveLaneMask VPInstruction, since
     // we have to take unrolling into account. Each part needs to start at
     //   Part * VF
     auto *CanonicalIVIncrementParts =
         new VPInstruction(HasNUW ? VPInstruction::CanonicalIVIncrementForPartNUW
                                  : VPInstruction::CanonicalIVIncrementForPart,
                           {StartV}, DL, "index.part.next");
     Preheader->appendRecipe(CanonicalIVIncrementParts);
 
     // Create the ActiveLaneMask instruction using the correct start values.
     VPValue *TC = Plan.getOrCreateTripCount();
if (!VectorizeLoop) {
                << "interleaved loop (interleaved count: "
                << NV("InterleaveCount", IC) << ")";
       });
     } else {
       // If we decided that it is *legal* to vectorize the loop, then do it.
 
       // Consider vectorizing the epilogue too if it's profitable.
       VectorizationFactor EpilogueVF =
-          CM.selectEpilogueVectorizationFactor(VF.Width, LVP);
+          LVP.selectEpilogueVectorizationFactor(VF.Width);
       if (EpilogueVF.Width.isVector()) {
 
         // The first pass vectorizes the main loop and creates a scalar epilogue
         // to be vectorized by executing the plan (potentially with a different
         // factor) again shortly afterwards.
         EpilogueLoopVectorizationInfo EPI(VF.Width, IC, EpilogueVF.Width, 1);
         EpilogueVectorizerMainLoop MainILV(L, PSE, LI, DT, TLI, TTI, AC, ORE,
                                            EPI, &LVL, &CM, BFI, PSI, Checks);