| //===- 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 "VectorizeOptions.h" | |
| #include "llvm/Analysis/LoopInfo.h" | |
| #include "llvm/Analysis/OptimizationRemarkEmitter.h" | |
| #include "llvm/Analysis/ScalarEvolution.h" | |
| #include "llvm/IR/DiagnosticInfo.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" | |
| /// 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 Opts.force_target_supports_masked_memory_ops || | |
| (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 Opts.force_target_supports_gather_scatter_ops || | |
| (IsLoad ? TTI.isLegalMaskedGather(VectorTy, Alignment) | |
| : TTI.isLegalMaskedScatter(VectorTy, Alignment)); | |
| } | |
| bool VFSelectionContext::supportsScalableVectors() const { | |
| return TTI.supportsScalableVectors() || | |
| Opts.force_target_supports_scalable_vectors || | |
| VectorizerParams::VectorizationFactor.isScalable(); | |
| } | |
| bool VFSelectionContext::useMaxBandwidth(bool IsScalable) const { | |
| TargetTransformInfo::RegisterKind RegKind = | |
| IsScalable ? TargetTransformInfo::RGK_ScalableVector | |
| : TargetTransformInfo::RGK_FixedWidthVector; | |
| return valueOr(Opts.vectorizer_maximize_bandwidth, | |
| TTI.shouldMaximizeVectorBandwidth(RegKind) || | |
| (Opts.vectorizer_maximize_bandwidth_for_vector_calls && | |
| Legal->hasVectorCallVariants())); | |
| } | |
| bool VFSelectionContext::shouldConsiderRegPressureForVF(ElementCount VF) const { | |
| if (Opts.vectorizer_consider_reg_pressure != BoolOrDefault::Default) | |
| return Opts.vectorizer_consider_reg_pressure == BoolOrDefault::True; | |
| // 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()) { | |
| for (const RecurrenceDescriptor &RdxDesc : | |
| Legal->getReductionVars().values()) { | |
| // 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 (Opts.prefer_inloop_reductions || 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 (!Opts.prefer_inloop_reductions && !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 *= Opts.scalable_epilogue_vf_cost_scale_factor; | |
| 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 (Opts.vplan_build_outerloop_stress_test && 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; | |
| } |