Florian Hahn
0ba95d65d8
computeVPlanOuterloopVF computes the VF as max(1, RegSize / WidestType). WidestType may not be a power of two, which resulted in a non-power-of-2 VF. Round down like in the inner loop path.
833 lines
34 KiB
C++
833 lines
34 KiB
C++
//===- 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 "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"
|
|
|
|
extern cl::opt<bool> VPlanBuildOuterloopStressTest;
|
|
|
|
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."));
|
|
|
|
cl::opt<bool> llvm::PreferInLoopReductions(
|
|
"prefer-inloop-reductions", cl::init(false), cl::Hidden,
|
|
cl::desc("Prefer in-loop vector reductions, "
|
|
"overriding the targets preference."));
|
|
|
|
/// 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)."));
|
|
|
|
/// 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(Instruction *I,
|
|
ElementCount VF) const {
|
|
assert(isa<LoadInst>(I) || isa<StoreInst>(I));
|
|
auto *Ty = getLoadStoreType(I);
|
|
const unsigned AS = getLoadStoreAddressSpace(I);
|
|
const Align Alignment = getLoadStoreAlignment(I);
|
|
|
|
return ForceTargetSupportsMaskedMemoryOps ||
|
|
(isa<LoadInst>(I) ? TTI.isLegalMaskedLoad(Ty, Alignment, AS)
|
|
: TTI.isLegalMaskedStore(Ty, Alignment, AS));
|
|
}
|
|
|
|
bool VFSelectionContext::isLegalGatherOrScatter(Value *V,
|
|
ElementCount VF) const {
|
|
bool LI = isa<LoadInst>(V);
|
|
bool SI = isa<StoreInst>(V);
|
|
if (!LI && !SI)
|
|
return false;
|
|
auto *Ty = getLoadStoreType(V);
|
|
Align Align = getLoadStoreAlignment(V);
|
|
if (VF.isVector())
|
|
Ty = VectorType::get(Ty, VF);
|
|
return ForceTargetSupportsGatherScatterOps ||
|
|
(LI && TTI.isLegalMaskedGather(Ty, Align)) ||
|
|
(SI && TTI.isLegalMaskedScatter(Ty, Align));
|
|
}
|
|
|
|
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,
|
|
const TargetTransformInfo &TTI) {
|
|
if (std::optional<unsigned> MaxVScale = TTI.getMaxVScale())
|
|
return MaxVScale;
|
|
|
|
if (F.hasFnAttribute(Attribute::VScaleRange))
|
|
return F.getFnAttribute(Attribute::VScaleRange).getVScaleRangeMax();
|
|
|
|
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, TTI)) {
|
|
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, TTI);
|
|
// 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());
|
|
}
|
|
}
|
|
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);
|
|
// Add the elements to InLoopReductionImmediateChains for cost modelling.
|
|
Instruction *LastChain = Phi;
|
|
for (auto *I : ReductionOperations) {
|
|
InLoopReductionImmediateChains[I] = LastChain;
|
|
LastChain = I;
|
|
}
|
|
}
|
|
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 (Hints.isScalableVectorizationAlwaysPreferred())
|
|
if (A.Width.isScalable() && CostA.isValid() && !B.Width.isScalable() &&
|
|
!B.Width.isScalar())
|
|
return true;
|
|
|
|
// 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(IsEpilogue) &&
|
|
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);
|
|
}
|