//===- LoopVectorizationPlanner.cpp - VF selection and planning -----------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file implements VFSelectionContext methods for loop vectorization
/// VF selection, independent of cost-modeling decisions.
///
//===----------------------------------------------------------------------===//

#include "LoopVectorizationPlanner.h"
#include "VPlanUtils.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Transforms/Vectorize/LoopVectorizationLegality.h"
#include "llvm/Transforms/Vectorize/LoopVectorize.h"

using namespace llvm;
using namespace LoopVectorizationUtils;

#define DEBUG_TYPE "loop-vectorize"

static cl::opt<bool> MaximizeBandwidth(
    "vectorizer-maximize-bandwidth", cl::init(false), cl::Hidden,
    cl::desc("Maximize bandwidth when selecting vectorization factor which "
             "will be determined by the smallest type in loop."));

static cl::opt<bool> UseWiderVFIfCallVariantsPresent(
    "vectorizer-maximize-bandwidth-for-vector-calls", cl::init(true),
    cl::Hidden,
    cl::desc("Try wider VFs if they enable the use of vector variants"));

static cl::opt<bool> ConsiderRegPressure(
    "vectorizer-consider-reg-pressure", cl::init(false), cl::Hidden,
    cl::desc("Discard VFs if their register pressure is too high."));

static cl::opt<bool> ForceTargetSupportsScalableVectors(
    "force-target-supports-scalable-vectors", cl::init(false), cl::Hidden,
    cl::desc(
        "Pretend that scalable vectors are supported, even if the target does "
        "not support them. This flag should only be used for testing."));

static cl::opt<bool>
    PreferInLoopReductions("prefer-inloop-reductions", cl::init(false),
                           cl::Hidden,
                           cl::desc("Prefer in-loop vector reductions, "
                                    "overriding the targets preference."));

namespace llvm {
extern cl::opt<bool> VPlanBuildOuterloopStressTest;
} // namespace llvm

/// Note: This currently only applies to `llvm.masked.load` and
/// `llvm.masked.store`. TODO: Extend this to cover other operations as needed.
static cl::opt<bool> ForceTargetSupportsMaskedMemoryOps(
    "force-target-supports-masked-memory-ops", cl::init(false), cl::Hidden,
    cl::desc("Assume the target supports masked memory operations (used for "
             "testing)."));

static cl::opt<bool> ForceTargetSupportsGatherScatterOps(
    "force-target-supports-gather-scatter-ops", cl::init(false), cl::Hidden,
    cl::desc("Assume the target supports gather/scatter operations (used for "
             "testing)."));

static cl::opt<float> ScalableEpilogueVFCostScaleFactor(
    "scalable-epilogue-vf-cost-scale-factor", cl::init(2.0), cl::Hidden,
    cl::desc("Scale the cost of scalable epilogue VFs by this factor."));

/// Write a \p DebugMsg about vectorization to the debug output stream. If \p I
/// is passed, the message relates to that particular instruction.
#ifndef NDEBUG
static void debugVectorizationMessage(const StringRef Prefix,
                                      const StringRef DebugMsg,
                                      Instruction *I) {
  dbgs() << "LV: " << Prefix << DebugMsg;
  if (I != nullptr)
    dbgs() << " " << *I;
  else
    dbgs() << '.';
  dbgs() << '\n';
}
#endif

/// Create an analysis remark that explains why vectorization failed
/// \p RemarkName is the identifier for the remark.  If \p I is passed it is an
/// instruction that prevents vectorization.  Otherwise \p TheLoop is used for
/// the location of the remark. If \p DL is passed, use it as debug location for
/// the remark. \return the remark object that can be streamed to.
static OptimizationRemarkAnalysis createLVAnalysis(StringRef RemarkName,
                                                   const Loop *TheLoop,
                                                   Instruction *I,
                                                   DebugLoc DL = {}) {
  BasicBlock *CodeRegion = I ? I->getParent() : TheLoop->getHeader();
  // If debug location is attached to the instruction, use it. Otherwise if DL
  // was not provided, use the loop's.
  if (I && I->getDebugLoc())
    DL = I->getDebugLoc();
  else if (!DL)
    DL = TheLoop->getStartLoc();

  return OptimizationRemarkAnalysis(DEBUG_TYPE, RemarkName, DL, CodeRegion);
}

void LoopVectorizationUtils::reportVectorizationFailure(
    const StringRef DebugMsg, const StringRef OREMsg, const StringRef ORETag,
    OptimizationRemarkEmitter *ORE, const Loop *TheLoop, Instruction *I) {
  LLVM_DEBUG(debugVectorizationMessage("Not vectorizing: ", DebugMsg, I));
  ORE->emit(createLVAnalysis(ORETag, TheLoop, I)
            << "loop not vectorized: " << OREMsg);
}

void LoopVectorizationUtils::reportVectorizationInfo(
    const StringRef Msg, const StringRef ORETag, OptimizationRemarkEmitter *ORE,
    const Loop *TheLoop, Instruction *I, DebugLoc DL) {
  LLVM_DEBUG(debugVectorizationMessage("", Msg, I));
  ORE->emit(createLVAnalysis(ORETag, TheLoop, I, DL) << Msg);
}

void LoopVectorizationUtils::reportVectorization(OptimizationRemarkEmitter *ORE,
                                                 Loop *TheLoop,
                                                 ElementCount VFWidth,
                                                 unsigned IC) {
  LLVM_DEBUG(debugVectorizationMessage(
      "Vectorizing: ", TheLoop->isInnermost() ? "innermost loop" : "outer loop",
      nullptr));
  StringRef LoopType = TheLoop->isInnermost() ? "" : "outer ";
  ORE->emit([&]() {
    return OptimizationRemark(DEBUG_TYPE, "Vectorized", TheLoop->getStartLoc(),
                              TheLoop->getHeader())
           << "vectorized " << LoopType << "loop (vectorization width: "
           << ore::NV("VectorizationFactor", VFWidth)
           << ", interleaved count: " << ore::NV("InterleaveCount", IC) << ")";
  });
}

bool VFSelectionContext::isLegalMaskedLoadOrStore(bool IsLoad, Type *ScalarTy,
                                                  Align Alignment,
                                                  unsigned AddressSpace) const {
  return ForceTargetSupportsMaskedMemoryOps ||
         (IsLoad ? TTI.isLegalMaskedLoad(ScalarTy, Alignment, AddressSpace)
                 : TTI.isLegalMaskedStore(ScalarTy, Alignment, AddressSpace));
}

bool VFSelectionContext::isLegalGatherOrScatter(bool IsLoad, Type *ScalarTy,
                                                Align Alignment,
                                                ElementCount VF) const {
  Type *VectorTy = toVectorTy(ScalarTy, VF);
  return ForceTargetSupportsGatherScatterOps ||
         (IsLoad ? TTI.isLegalMaskedGather(VectorTy, Alignment)
                 : TTI.isLegalMaskedScatter(VectorTy, Alignment));
}

bool VFSelectionContext::supportsScalableVectors() const {
  return TTI.supportsScalableVectors() || ForceTargetSupportsScalableVectors ||
         VectorizerParams::VectorizationFactor.isScalable();
}

bool VFSelectionContext::useMaxBandwidth(bool IsScalable) const {
  TargetTransformInfo::RegisterKind RegKind =
      IsScalable ? TargetTransformInfo::RGK_ScalableVector
                 : TargetTransformInfo::RGK_FixedWidthVector;
  return MaximizeBandwidth || (MaximizeBandwidth.getNumOccurrences() == 0 &&
                               (TTI.shouldMaximizeVectorBandwidth(RegKind) ||
                                (UseWiderVFIfCallVariantsPresent &&
                                 Legal->hasVectorCallVariants())));
}

bool VFSelectionContext::shouldConsiderRegPressureForVF(ElementCount VF) const {
  if (ConsiderRegPressure.getNumOccurrences())
    return ConsiderRegPressure;

  // TODO: We should eventually consider register pressure for all targets. The
  // TTI hook is temporary whilst target-specific issues are being fixed.
  if (TTI.shouldConsiderVectorizationRegPressure())
    return true;

  if (!useMaxBandwidth(VF.isScalable()))
    return false;
  // Only calculate register pressure for VFs enabled by MaxBandwidth.
  return ElementCount::isKnownGT(
      VF, VF.isScalable() ? MaxPermissibleVFWithoutMaxBW.ScalableVF
                          : MaxPermissibleVFWithoutMaxBW.FixedVF);
}

ElementCount VFSelectionContext::clampVFByMaxTripCount(
    ElementCount VF, unsigned MaxTripCount, unsigned UserIC,
    bool FoldTailByMasking, bool RequiresScalarEpilogue) const {
  unsigned EstimatedVF = VF.getKnownMinValue();
  if (VF.isScalable() && F.hasFnAttribute(Attribute::VScaleRange)) {
    auto Attr = F.getFnAttribute(Attribute::VScaleRange);
    auto Min = Attr.getVScaleRangeMin();
    EstimatedVF *= Min;
  }

  // When a scalar epilogue is required, at least one iteration of the scalar
  // loop has to execute. Adjust MaxTripCount accordingly to avoid picking a
  // max VF that results in a dead vector loop.
  if (MaxTripCount > 0 && RequiresScalarEpilogue)
    MaxTripCount -= 1;

  // When the user specifies an interleave count, we need to ensure that
  // VF * UserIC <= MaxTripCount to avoid a dead vector loop.
  unsigned IC = UserIC > 0 ? UserIC : 1;
  unsigned EstimatedVFTimesIC = EstimatedVF * IC;

  if (MaxTripCount && MaxTripCount <= EstimatedVFTimesIC &&
      (!FoldTailByMasking || isPowerOf2_32(MaxTripCount))) {
    // If upper bound loop trip count (TC) is known at compile time there is no
    // point in choosing VF greater than TC / IC (as done in the loop below).
    // Select maximum power of two which doesn't exceed TC / IC. If VF is
    // scalable, we only fall back on a fixed VF when the TC is less than or
    // equal to the known number of lanes.
    auto ClampedUpperTripCount = llvm::bit_floor(MaxTripCount / IC);
    if (ClampedUpperTripCount == 0)
      ClampedUpperTripCount = 1;
    LLVM_DEBUG(dbgs() << "LV: Clamping the MaxVF to maximum power of two not "
                         "exceeding the constant trip count"
                      << (UserIC > 0 ? " divided by UserIC" : "") << ": "
                      << ClampedUpperTripCount << "\n");
    return ElementCount::get(ClampedUpperTripCount,
                             FoldTailByMasking ? VF.isScalable() : false);
  }
  return VF;
}

ElementCount VFSelectionContext::getMaximizedVFForTarget(
    unsigned MaxTripCount, unsigned SmallestType, unsigned WidestType,
    ElementCount MaxSafeVF, unsigned UserIC, bool FoldTailByMasking,
    bool RequiresScalarEpilogue) {
  bool ComputeScalableMaxVF = MaxSafeVF.isScalable();
  const TypeSize WidestRegister = TTI.getRegisterBitWidth(
      ComputeScalableMaxVF ? TargetTransformInfo::RGK_ScalableVector
                           : TargetTransformInfo::RGK_FixedWidthVector);

  // Convenience function to return the minimum of two ElementCounts.
  auto MinVF = [](const ElementCount &LHS, const ElementCount &RHS) {
    assert((LHS.isScalable() == RHS.isScalable()) &&
           "Scalable flags must match");
    return ElementCount::isKnownLT(LHS, RHS) ? LHS : RHS;
  };

  // Ensure MaxVF is a power of 2; the dependence distance bound may not be.
  // Note that both WidestRegister and WidestType may not be a powers of 2.
  auto MaxVectorElementCount = ElementCount::get(
      llvm::bit_floor(WidestRegister.getKnownMinValue() / WidestType),
      ComputeScalableMaxVF);
  MaxVectorElementCount = MinVF(MaxVectorElementCount, MaxSafeVF);
  LLVM_DEBUG(dbgs() << "LV: The Widest register safe to use is: "
                    << (MaxVectorElementCount * WidestType) << " bits.\n");

  if (!MaxVectorElementCount) {
    LLVM_DEBUG(dbgs() << "LV: The target has no "
                      << (ComputeScalableMaxVF ? "scalable" : "fixed")
                      << " vector registers.\n");
    return ElementCount::getFixed(1);
  }

  ElementCount MaxVF =
      clampVFByMaxTripCount(MaxVectorElementCount, MaxTripCount, UserIC,
                            FoldTailByMasking, RequiresScalarEpilogue);
  // If the MaxVF was already clamped, there's no point in trying to pick a
  // larger one.
  if (MaxVF != MaxVectorElementCount)
    return MaxVF;

  if (MaxVF.isScalable())
    MaxPermissibleVFWithoutMaxBW.ScalableVF = MaxVF;
  else
    MaxPermissibleVFWithoutMaxBW.FixedVF = MaxVF;

  if (useMaxBandwidth(ComputeScalableMaxVF)) {
    auto MaxVectorElementCountMaxBW = ElementCount::get(
        llvm::bit_floor(WidestRegister.getKnownMinValue() / SmallestType),
        ComputeScalableMaxVF);
    MaxVF = MinVF(MaxVectorElementCountMaxBW, MaxSafeVF);

    if (ElementCount MinVF =
            TTI.getMinimumVF(SmallestType, ComputeScalableMaxVF)) {
      if (ElementCount::isKnownLT(MaxVF, MinVF)) {
        LLVM_DEBUG(dbgs() << "LV: Overriding calculated MaxVF(" << MaxVF
                          << ") with target's minimum: " << MinVF << '\n');
        MaxVF = MinVF;
      }
    }

    MaxVF = clampVFByMaxTripCount(MaxVF, MaxTripCount, UserIC,
                                  FoldTailByMasking, RequiresScalarEpilogue);
  }
  return MaxVF;
}

std::optional<unsigned> llvm::getMaxVScale(const Function &F) {
  if (F.hasFnAttribute(Attribute::VScaleRange))
    return F.getFnAttribute(Attribute::VScaleRange).getVScaleRangeMax();

  return std::nullopt;
}

std::optional<uint64_t>
llvm::getMaxRuntimeElementCount(ElementCount EC, const Function &F) {
  if (EC.isFixed())
    return EC.getFixedValue();

  if (std::optional<unsigned> MaxVScale = getMaxVScale(F))
    return uint64_t(EC.getKnownMinValue()) * *MaxVScale;

  return std::nullopt;
}

bool VFSelectionContext::isScalableVectorizationAllowed() {
  if (IsScalableVectorizationAllowed)
    return *IsScalableVectorizationAllowed;

  IsScalableVectorizationAllowed = false;
  if (!supportsScalableVectors())
    return false;

  if (Hints->isScalableVectorizationDisabled()) {
    reportVectorizationInfo("Scalable vectorization is explicitly disabled",
                            "ScalableVectorizationDisabled", ORE, TheLoop);
    return false;
  }

  LLVM_DEBUG(dbgs() << "LV: Scalable vectorization is available\n");

  auto MaxScalableVF = ElementCount::getScalable(
      std::numeric_limits<ElementCount::ScalarTy>::max());

  // Test that the loop-vectorizer can legalize all operations for this MaxVF.
  // FIXME: While for scalable vectors this is currently sufficient, this should
  // be replaced by a more detailed mechanism that filters out specific VFs,
  // instead of invalidating vectorization for a whole set of VFs based on the
  // MaxVF.

  // Disable scalable vectorization if the loop contains unsupported reductions.
  if (!all_of(Legal->getReductionVars(), [&](const auto &Reduction) -> bool {
        return TTI.isLegalToVectorizeReduction(Reduction.second, MaxScalableVF);
      })) {
    reportVectorizationInfo(
        "Scalable vectorization not supported for the reduction "
        "operations found in this loop.",
        "ScalableVFUnfeasible", ORE, TheLoop);
    return false;
  }

  // Disable scalable vectorization if the loop contains any instructions
  // with element types not supported for scalable vectors.
  if (any_of(ElementTypesInLoop, [&](Type *Ty) {
        return !Ty->isVoidTy() && !TTI.isElementTypeLegalForScalableVector(Ty);
      })) {
    reportVectorizationInfo("Scalable vectorization is not supported "
                            "for all element types found in this loop.",
                            "ScalableVFUnfeasible", ORE, TheLoop);
    return false;
  }

  if (!Legal->isSafeForAnyVectorWidth() && !getMaxVScale(F)) {
    reportVectorizationInfo("The target does not provide maximum vscale value "
                            "for safe distance analysis.",
                            "ScalableVFUnfeasible", ORE, TheLoop);
    return false;
  }

  IsScalableVectorizationAllowed = true;
  return true;
}

ElementCount
VFSelectionContext::getMaxLegalScalableVF(unsigned MaxSafeElements) {
  if (!isScalableVectorizationAllowed())
    return ElementCount::getScalable(0);

  auto MaxScalableVF = ElementCount::getScalable(
      std::numeric_limits<ElementCount::ScalarTy>::max());
  if (Legal->isSafeForAnyVectorWidth())
    return MaxScalableVF;

  std::optional<unsigned> MaxVScale = getMaxVScale(F);
  // Limit MaxScalableVF by the maximum safe dependence distance.
  MaxScalableVF = ElementCount::getScalable(MaxSafeElements / *MaxVScale);

  if (!MaxScalableVF)
    reportVectorizationInfo(
        "Max legal vector width too small, scalable vectorization "
        "unfeasible.",
        "ScalableVFUnfeasible", ORE, TheLoop);

  return MaxScalableVF;
}

FixedScalableVFPair VFSelectionContext::computeFeasibleMaxVF(
    unsigned MaxTripCount, ElementCount UserVF, unsigned UserIC,
    bool FoldTailByMasking, bool RequiresScalarEpilogue) {
  auto [SmallestType, WidestType] = getSmallestAndWidestTypes();

  // Get the maximum safe dependence distance in bits computed by LAA.
  // It is computed by MaxVF * sizeOf(type) * 8, where type is taken from
  // the memory accesses that is most restrictive (involved in the smallest
  // dependence distance).
  unsigned MaxSafeElementsPowerOf2 =
      llvm::bit_floor(Legal->getMaxSafeVectorWidthInBits() / WidestType);
  if (!Legal->isSafeForAnyStoreLoadForwardDistances()) {
    unsigned SLDist = Legal->getMaxStoreLoadForwardSafeDistanceInBits();
    MaxSafeElementsPowerOf2 =
        std::min(MaxSafeElementsPowerOf2, SLDist / WidestType);
  }

  auto MaxSafeFixedVF = ElementCount::getFixed(MaxSafeElementsPowerOf2);
  auto MaxSafeScalableVF = getMaxLegalScalableVF(MaxSafeElementsPowerOf2);

  if (!Legal->isSafeForAnyVectorWidth())
    MaxSafeElements = MaxSafeElementsPowerOf2;

  LLVM_DEBUG(dbgs() << "LV: The max safe fixed VF is: " << MaxSafeFixedVF
                    << ".\n");
  LLVM_DEBUG(dbgs() << "LV: The max safe scalable VF is: " << MaxSafeScalableVF
                    << ".\n");

  // First analyze the UserVF, fall back if the UserVF should be ignored.
  if (UserVF) {
    auto MaxSafeUserVF =
        UserVF.isScalable() ? MaxSafeScalableVF : MaxSafeFixedVF;

    if (ElementCount::isKnownLE(UserVF, MaxSafeUserVF)) {
      // If `VF=vscale x N` is safe, then so is `VF=N`
      if (UserVF.isScalable())
        return FixedScalableVFPair(
            ElementCount::getFixed(UserVF.getKnownMinValue()), UserVF);

      return UserVF;
    }

    assert(ElementCount::isKnownGT(UserVF, MaxSafeUserVF));

    // Only clamp if the UserVF is not scalable. If the UserVF is scalable, it
    // is better to ignore the hint and let the compiler choose a suitable VF.
    if (!UserVF.isScalable()) {
      LLVM_DEBUG(dbgs() << "LV: User VF=" << UserVF
                        << " is unsafe, clamping to max safe VF="
                        << MaxSafeFixedVF << ".\n");
      ORE->emit([&]() {
        return OptimizationRemarkAnalysis(DEBUG_TYPE, "VectorizationFactor",
                                          TheLoop->getStartLoc(),
                                          TheLoop->getHeader())
               << "User-specified vectorization factor "
               << ore::NV("UserVectorizationFactor", UserVF)
               << " is unsafe, clamping to maximum safe vectorization factor "
               << ore::NV("VectorizationFactor", MaxSafeFixedVF);
      });
      return MaxSafeFixedVF;
    }

    if (!supportsScalableVectors()) {
      LLVM_DEBUG(dbgs() << "LV: User VF=" << UserVF
                        << " is ignored because scalable vectors are not "
                           "available.\n");
      ORE->emit([&]() {
        return OptimizationRemarkAnalysis(DEBUG_TYPE, "VectorizationFactor",
                                          TheLoop->getStartLoc(),
                                          TheLoop->getHeader())
               << "User-specified vectorization factor "
               << ore::NV("UserVectorizationFactor", UserVF)
               << " is ignored because the target does not support scalable "
                  "vectors. The compiler will pick a more suitable value.";
      });
    } else {
      LLVM_DEBUG(dbgs() << "LV: User VF=" << UserVF
                        << " is unsafe. Ignoring scalable UserVF.\n");
      ORE->emit([&]() {
        return OptimizationRemarkAnalysis(DEBUG_TYPE, "VectorizationFactor",
                                          TheLoop->getStartLoc(),
                                          TheLoop->getHeader())
               << "User-specified vectorization factor "
               << ore::NV("UserVectorizationFactor", UserVF)
               << " is unsafe. Ignoring the hint to let the compiler pick a "
                  "more suitable value.";
      });
    }
  }

  LLVM_DEBUG(dbgs() << "LV: The Smallest and Widest types: " << SmallestType
                    << " / " << WidestType << " bits.\n");

  FixedScalableVFPair Result(ElementCount::getFixed(1),
                             ElementCount::getScalable(0));
  if (auto MaxVF = getMaximizedVFForTarget(
          MaxTripCount, SmallestType, WidestType, MaxSafeFixedVF, UserIC,
          FoldTailByMasking, RequiresScalarEpilogue))
    Result.FixedVF = MaxVF;

  if (auto MaxVF = getMaximizedVFForTarget(
          MaxTripCount, SmallestType, WidestType, MaxSafeScalableVF, UserIC,
          FoldTailByMasking, RequiresScalarEpilogue))
    if (MaxVF.isScalable()) {
      Result.ScalableVF = MaxVF;
      LLVM_DEBUG(dbgs() << "LV: Found feasible scalable VF = " << MaxVF
                        << "\n");
    }

  return Result;
}

std::pair<unsigned, unsigned>
VFSelectionContext::getSmallestAndWidestTypes() const {
  unsigned MinWidth = -1U;
  unsigned MaxWidth = 8;
  const DataLayout &DL = F.getDataLayout();
  // For in-loop reductions, no element types are added to ElementTypesInLoop
  // if there are no loads/stores in the loop. In this case, check through the
  // reduction variables to determine the maximum width.
  if (ElementTypesInLoop.empty() && !Legal->getReductionVars().empty()) {
    for (const auto &[_, RdxDesc] : Legal->getReductionVars()) {
      // When finding the min width used by the recurrence we need to account
      // for casts on the input operands of the recurrence.
      MinWidth = std::min(
          MinWidth,
          std::min(RdxDesc.getMinWidthCastToRecurrenceTypeInBits(),
                   RdxDesc.getRecurrenceType()->getScalarSizeInBits()));
      MaxWidth = std::max(MaxWidth,
                          RdxDesc.getRecurrenceType()->getScalarSizeInBits());
    }
  } else {
    for (Type *T : ElementTypesInLoop) {
      MinWidth = std::min<unsigned>(
          MinWidth, DL.getTypeSizeInBits(T->getScalarType()).getFixedValue());
      MaxWidth = std::max<unsigned>(
          MaxWidth, DL.getTypeSizeInBits(T->getScalarType()).getFixedValue());
    }
  }

  // If the loop has no loads/stores or reductions (e.g. a search loop with an
  // early exit), MinWidth is never updated and is left at its sentinel value.
  // Fall back to MaxWidth to keep the SmallestType <= WidestType invariant, so
  // callers such as the max-bandwidth VF computation don't divide by the
  // sentinel and collapse the VF to zero.
  if (MinWidth == -1U)
    MinWidth = MaxWidth;

  return {MinWidth, MaxWidth};
}

void VFSelectionContext::collectElementTypesForWidening(
    const SmallPtrSetImpl<const Value *> *ValuesToIgnore) {
  ElementTypesInLoop.clear();
  // For each block.
  for (BasicBlock *BB : TheLoop->blocks()) {
    // For each instruction in the loop.
    for (Instruction &I : *BB) {
      Type *T = I.getType();

      // Skip ignored values.
      if (ValuesToIgnore && ValuesToIgnore->contains(&I))
        continue;

      // Only examine Loads, Stores and PHINodes.
      if (!isa<LoadInst, StoreInst, PHINode>(I))
        continue;

      // Examine PHI nodes that are reduction variables. Update the type to
      // account for the recurrence type.
      if (auto *PN = dyn_cast<PHINode>(&I)) {
        if (!Legal->isReductionVariable(PN))
          continue;
        const RecurrenceDescriptor &RdxDesc =
            Legal->getRecurrenceDescriptor(PN);
        if (PreferInLoopReductions || useOrderedReductions(RdxDesc) ||
            TTI.preferInLoopReduction(RdxDesc.getRecurrenceKind(),
                                      RdxDesc.getRecurrenceType()))
          continue;
        T = RdxDesc.getRecurrenceType();
      }

      // Examine the stored values.
      if (auto *ST = dyn_cast<StoreInst>(&I))
        T = ST->getValueOperand()->getType();

      assert(T->isSized() &&
             "Expected the load/store/recurrence type to be sized");

      ElementTypesInLoop.insert(T);
    }
  }
}

void VFSelectionContext::initializeVScaleForTuning() {
  if (!supportsScalableVectors())
    return;

  if (F.hasFnAttribute(Attribute::VScaleRange)) {
    auto Attr = F.getFnAttribute(Attribute::VScaleRange);
    auto Min = Attr.getVScaleRangeMin();
    auto Max = Attr.getVScaleRangeMax();
    if (Max && Min == Max) {
      VScaleForTuning = Max;
      return;
    }
  }

  VScaleForTuning = TTI.getVScaleForTuning();
}

bool VFSelectionContext::useOrderedReductions(
    const RecurrenceDescriptor &RdxDesc) const {
  return !Hints->allowReordering() && RdxDesc.isOrdered();
}

bool VFSelectionContext::runtimeChecksRequired() {
  LLVM_DEBUG(dbgs() << "LV: Performing code size checks.\n");

  Loop *L = const_cast<Loop *>(TheLoop);
  if (Legal->getRuntimePointerChecking()->Need) {
    reportVectorizationFailure(
        "Runtime ptr check is required with -Os/-Oz",
        "runtime pointer checks needed. Enable vectorization of this "
        "loop with '#pragma clang loop vectorize(enable)' when "
        "compiling with -Os/-Oz",
        "CantVersionLoopWithOptForSize", ORE, L);
    return true;
  }

  if (!PSE.getPredicate().isAlwaysTrue()) {
    reportVectorizationFailure(
        "Runtime SCEV check is required with -Os/-Oz",
        "runtime SCEV checks needed. Enable vectorization of this "
        "loop with '#pragma clang loop vectorize(enable)' when "
        "compiling with -Os/-Oz",
        "CantVersionLoopWithOptForSize", ORE, L);
    return true;
  }

  // FIXME: Avoid specializing for stride==1 instead of bailing out.
  if (!Legal->getLAI()->getSymbolicStrides().empty()) {
    reportVectorizationFailure(
        "Runtime stride check for small trip count",
        "runtime stride == 1 checks needed. Enable vectorization of "
        "this loop without such check by compiling with -Os/-Oz",
        "CantVersionLoopWithOptForSize", ORE, L);
    return true;
  }

  return false;
}

void VFSelectionContext::computeMinimalBitwidths() {
  MinBWs = computeMinimumValueSizes(TheLoop->getBlocks(), *DB, &TTI);
}

void VFSelectionContext::collectInLoopReductions() {
  // Avoid duplicating work finding in-loop reductions.
  if (!InLoopReductions.empty())
    return;

  for (const auto &Reduction : Legal->getReductionVars()) {
    PHINode *Phi = Reduction.first;
    const RecurrenceDescriptor &RdxDesc = Reduction.second;

    // Multi-use reductions (e.g., used in FindLastIV patterns) are handled
    // separately and should not be considered for in-loop reductions.
    if (RdxDesc.hasUsesOutsideReductionChain())
      continue;

    // We don't collect reductions that are type promoted (yet).
    if (RdxDesc.getRecurrenceType() != Phi->getType())
      continue;

    // In-loop AnyOf and FindIV reductions are not yet supported.
    RecurKind Kind = RdxDesc.getRecurrenceKind();
    if (RecurrenceDescriptor::isAnyOfRecurrenceKind(Kind) ||
        RecurrenceDescriptor::isFindIVRecurrenceKind(Kind) ||
        RecurrenceDescriptor::isFindLastRecurrenceKind(Kind))
      continue;

    // If the target would prefer this reduction to happen "in-loop", then we
    // want to record it as such.
    if (!PreferInLoopReductions && !useOrderedReductions(RdxDesc) &&
        !TTI.preferInLoopReduction(Kind, Phi->getType()))
      continue;

    // Check that we can correctly put the reductions into the loop, by
    // finding the chain of operations that leads from the phi to the loop
    // exit value.
    SmallVector<Instruction *, 4> ReductionOperations =
        RdxDesc.getReductionOpChain(Phi, const_cast<Loop *>(TheLoop));
    bool InLoop = !ReductionOperations.empty();

    if (InLoop)
      InLoopReductions.insert(Phi);
    LLVM_DEBUG(dbgs() << "LV: Using " << (InLoop ? "inloop" : "out of loop")
                      << " reduction for phi: " << *Phi << "\n");
  }
}

bool LoopVectorizationPlanner::isMoreProfitable(const VectorizationFactor &A,
                                                const VectorizationFactor &B,
                                                const unsigned MaxTripCount,
                                                bool HasTail,
                                                bool IsEpilogue) const {
  InstructionCost CostA = A.Cost;
  InstructionCost CostB = B.Cost;

  // When there is a hint to always prefer scalable vectors, honour that hint.
  if (Config.getHints().isScalableVectorizationAlwaysPreferred())
    if (A.Width.isScalable() && CostA.isValid() && !B.Width.isScalable() &&
        !B.Width.isScalar())
      return true;

  // Favor fixed VFs for epilogue loops by scaling the costs of scalable VFs
  // 'ScalableEpilogueVFCostScaleFactor' (default 2.0). This is intended to
  // model that fixed VFs are more likely to be fully unrolled (or optimized
  // out) post vectorization. TODO: Reconsider this restriction for predicated
  // epilogues (once supported).
  if (IsEpilogue && A.Width.isScalable() != B.Width.isScalable() &&
      A.Cost.isValid() && B.Cost.isValid()) {
    auto [FixedCost, ScalableCost] = std::make_pair(CostA, CostB);
    if (B.Width.isFixed())
      std::swap(FixedCost, ScalableCost);

    ScalableCost *= ScalableEpilogueVFCostScaleFactor;

    if (FixedCost <= ScalableCost)
      return A.Width.isFixed();
  }

  // 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 = Config.getVScaleForTuning()) {
    if (A.Width.isScalable())
      EstimatedWidthA *= *VScale;
    if (B.Width.isScalable())
      EstimatedWidthB *= *VScale;
  }

  // When optimizing for size choose whichever is smallest, which will be the
  // one with the smallest cost for the whole loop. On a tie pick the larger
  // vector width, on the assumption that throughput will be greater.
  if (Config.CostKind == TTI::TCK_CodeSize)
    return CostA < CostB ||
           (CostA == CostB && EstimatedWidthA > EstimatedWidthB);

  // Assume vscale may be larger than 1 (or the value being tuned for),
  // so that scalable vectorization is slightly favorable over fixed-width
  // vectorization.
  bool PreferScalable = !TTI.preferFixedOverScalableIfEqualCost() &&
                        A.Width.isScalable() && !B.Width.isScalable();

  auto CmpFn = [PreferScalable](const InstructionCost &LHS,
                                const InstructionCost &RHS) {
    return PreferScalable ? LHS <= RHS : LHS < RHS;
  };

  // To avoid the need for FP division:
  //      (CostA / EstimatedWidthA) < (CostB / EstimatedWidthB)
  // <=>  (CostA * EstimatedWidthB) < (CostB * EstimatedWidthA)
  bool LowerCostWithoutTC =
      CmpFn(CostA * EstimatedWidthB, CostB * EstimatedWidthA);
  if (!MaxTripCount)
    return LowerCostWithoutTC;

  auto GetCostForTC = [MaxTripCount, HasTail](unsigned VF,
                                              InstructionCost VectorCost,
                                              InstructionCost ScalarCost) {
    // If the trip count is a known (possibly small) constant, the trip count
    // will be rounded up to an integer number of iterations under
    // FoldTailByMasking. The total cost in that case will be
    // VecCost*ceil(TripCount/VF). When not folding the tail, the total
    // cost will be VecCost*floor(TC/VF) + ScalarCost*(TC%VF). There will be
    // some extra overheads, but for the purpose of comparing the costs of
    // different VFs we can use this to compare the total loop-body cost
    // expected after vectorization.
    if (HasTail)
      return VectorCost * (MaxTripCount / VF) +
             ScalarCost * (MaxTripCount % VF);
    return VectorCost * divideCeil(MaxTripCount, VF);
  };

  auto RTCostA = GetCostForTC(EstimatedWidthA, CostA, A.ScalarCost);
  auto RTCostB = GetCostForTC(EstimatedWidthB, CostB, B.ScalarCost);
  bool LowerCostWithTC = CmpFn(RTCostA, RTCostB);
  LLVM_DEBUG(if (LowerCostWithTC != LowerCostWithoutTC) {
    dbgs() << "LV: VF " << (LowerCostWithTC ? A.Width : B.Width)
           << " has lower cost than VF "
           << (LowerCostWithTC ? B.Width : A.Width)
           << " when taking the cost of the remaining scalar loop iterations "
              "into consideration for a maximum trip count of "
           << MaxTripCount << ".\n";
  });
  return LowerCostWithTC;
}

bool LoopVectorizationPlanner::isMoreProfitable(const VectorizationFactor &A,
                                                const VectorizationFactor &B,
                                                bool HasTail,
                                                bool IsEpilogue) const {
  const unsigned MaxTripCount = PSE.getSmallConstantMaxTripCount();
  return LoopVectorizationPlanner::isMoreProfitable(A, B, MaxTripCount, HasTail,
                                                    IsEpilogue);
}

// TODO: we could return a pair of values that specify the max VF and
// min VF, to be used in `buildVPlans(MinVF, MaxVF)` instead of
// `buildVPlans(VF, VF)`. We cannot do it because VPLAN at the moment
// doesn't have a cost model that can choose which plan to execute if
// more than one is generated.
FixedScalableVFPair
VFSelectionContext::computeVPlanOuterloopVF(ElementCount UserVF) {
  if (UserVF.isScalable() && !supportsScalableVectors()) {
    reportVectorizationFailure(
        "Scalable vectorization requested but not supported by the target",
        "the scalable user-specified vectorization width for outer-loop "
        "vectorization cannot be used because the target does not support "
        "scalable vectors.",
        "ScalableVFUnfeasible", ORE, TheLoop);
    return FixedScalableVFPair::getNone();
  }

  ElementCount VF = UserVF;
  if (VF.isZero()) {
    auto [_, WidestType] = getSmallestAndWidestTypes();

    auto RegKind = TTI.enableScalableVectorization()
                       ? TargetTransformInfo::RGK_ScalableVector
                       : TargetTransformInfo::RGK_FixedWidthVector;

    TypeSize RegSize = TTI.getRegisterBitWidth(RegKind);
    // The widest type may be wider than the register width and WidestType may
    // not be a power of two; round the element count down to a power of two.
    unsigned N = std::max<uint64_t>(
        1, llvm::bit_floor(RegSize.getKnownMinValue() / WidestType));
    VF = ElementCount::get(N, RegSize.isScalable());
    LLVM_DEBUG(dbgs() << "LV: VPlan computed VF " << VF << ".\n");

    // Make sure we have a VF > 1 for stress testing.
    if (VPlanBuildOuterloopStressTest && VF.isScalar()) {
      LLVM_DEBUG(dbgs() << "LV: VPlan stress testing: "
                        << "overriding computed VF.\n");
      VF = ElementCount::getFixed(4);
    }
  }
  assert(isPowerOf2_32(VF.getKnownMinValue()) &&
         "VF needs to be a power of two");
  if (VF.isScalar())
    return FixedScalableVFPair::getNone();
  LLVM_DEBUG(dbgs() << "LV: Using " << (!UserVF.isZero() ? "user " : "")
                    << "VF " << VF << " to build VPlans.\n");
  return FixedScalableVFPair(VF);
}

/// \returns true if the VPlan contains header phi recipes that are not
/// currently supported for epilogue vectorization.
static bool hasUnsupportedHeaderPhiRecipe(VPlan &Plan) {
  return any_of(
      Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis(),
      [](VPRecipeBase &R) {
        switch (R.getVPRecipeID()) {
        case VPRecipeBase::VPFirstOrderRecurrencePHISC:
          // TODO: Add support for fixed-order recurrences.
          return true;
        case VPRecipeBase::VPWidenIntOrFpInductionSC:
          return !cast<VPWidenIntOrFpInductionRecipe>(&R)->getPHINode();
        case VPRecipeBase::VPReductionPHISC: {
          auto *RedPhi = cast<VPReductionPHIRecipe>(&R);
          // TODO: Support FMinNum/FMaxNum, FindLast reductions, and reductions
          // without underlying values.
          RecurKind Kind = RedPhi->getRecurrenceKind();
          if (RecurrenceDescriptor::isFPMinMaxNumRecurrenceKind(Kind) ||
              RecurrenceDescriptor::isFindLastRecurrenceKind(Kind) ||
              !RedPhi->getUnderlyingValue())
            return true;
          // TODO: Add support for FindIV reductions with sunk expressions: the
          // resume value from the main loop is in expression domain (e.g.,
          // mul(ReducedIV, 3)), but the epilogue tracks raw IV values. A sunk
          // expression is identified by a non-VPInstruction user of
          // ComputeReductionResult.
          if (RecurrenceDescriptor::isFindIVRecurrenceKind(Kind))
            return RedPhi->isExpressionSunk();
          return false;
        }
        default:
          return false;
        };
      });
}

bool LoopVectorizationPlanner::isCandidateForEpilogueVectorization(
    VPlan &MainPlan) const {
  // Bail out if the plan contains header phi recipes not yet supported
  // for epilogue vectorization.
  if (hasUnsupportedHeaderPhiRecipe(MainPlan))
    return false;

  // Epilogue vectorization code has not been auditted to ensure it handles
  // non-latch exits properly.  It may be fine, but it needs auditted and
  // tested.
  // TODO: Add support for loops with an early exit.
  if (OrigLoop->getExitingBlock() != OrigLoop->getLoopLatch() ||
      Legal->hasUncountableEarlyExit())
    return false;

  return true;
}