| 1 | //===- SLPCostAnalysis.h - SLP Vectorizer free cost helpers ----*- C++ -*-===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | // |
| 9 | // Internal header used by SLPVectorizer.cpp. It declares free cost helpers |
| 10 | // that do not depend on BoUpSLP or any other SLP-private type. The bulk of |
| 11 | // the SLP cost model still lives in SLPVectorizer.cpp because it references |
| 12 | // BoUpSLP internals. |
| 13 | // |
| 14 | //===----------------------------------------------------------------------===// |
| 15 | |
| 16 | #ifndef LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPCOSTANALYSIS_H |
| 17 | #define LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPCOSTANALYSIS_H |
| 18 | |
| 19 | #include "SLPUtils.h" |
| 20 | #include "llvm/ADT/ArrayRef.h" |
| 21 | #include "llvm/ADT/DenseMap.h" |
| 22 | #include "llvm/ADT/DenseSet.h" |
| 23 | #include "llvm/ADT/STLFunctionalExtras.h" |
| 24 | #include "llvm/ADT/SmallBitVector.h" |
| 25 | #include "llvm/ADT/SmallVector.h" |
| 26 | #include "llvm/Analysis/TargetTransformInfo.h" |
| 27 | #include "llvm/IR/Intrinsics.h" |
| 28 | #include "llvm/Support/InstructionCost.h" |
| 29 | |
| 30 | #include <optional> |
| 31 | #include <tuple> |
| 32 | #include <utility> |
| 33 | |
| 34 | namespace llvm { |
| 35 | class APInt; |
| 36 | class BasicBlock; |
| 37 | class CallInst; |
| 38 | class DataLayout; |
| 39 | class FastMathFlags; |
| 40 | class FixedVectorType; |
| 41 | class Function; |
| 42 | class Instruction; |
| 43 | class TargetLibraryInfo; |
| 44 | class Type; |
| 45 | class User; |
| 46 | class Value; |
| 47 | class VectorType; |
| 48 | enum class RecurKind; |
| 49 | } // namespace llvm |
| 50 | |
| 51 | namespace llvm::slpvectorizer { |
| 52 | |
| 53 | /// Returns the cost of the shuffle instructions with the given \p Kind, vector |
| 54 | /// type \p Tp and optional \p Mask. Adds SLP-specific cost estimation for |
| 55 | /// insert subvector pattern. |
| 56 | InstructionCost |
| 57 | getShuffleCost(const TargetTransformInfo &TTI, |
| 58 | TargetTransformInfo::ShuffleKind Kind, VectorType *Tp, |
| 59 | const TargetTransformInfo::TargetCostKind CostKind, |
| 60 | ArrayRef<int> Mask = {}, int Index = 0, |
| 61 | VectorType *SubTp = nullptr, ArrayRef<const Value *> Args = {}, |
| 62 | TargetTransformInfo::VectorInstrContext VIC = |
| 63 | TargetTransformInfo::VectorInstrContext::None); |
| 64 | |
| 65 | /// Calculate the scalar and the vector costs from vectorizing set of GEPs. |
| 66 | std::pair<InstructionCost, InstructionCost> |
| 67 | getGEPCosts(const TargetTransformInfo &TTI, ArrayRef<Value *> Ptrs, |
| 68 | Value *BasePtr, unsigned Opcode, |
| 69 | const TargetTransformInfo::TargetCostKind CostKind, Type *ScalarTy, |
| 70 | VectorType *VecTy); |
| 71 | |
| 72 | /// Returns the cost of a BlendedLoadVectorize node loading \p VecTy: two masked |
| 73 | /// loads (one per candidate base), a xor to negate the false-lane mask and a |
| 74 | /// select. The blend mask is a separate operand node, so its cost is counted |
| 75 | /// there, not here. |
| 76 | InstructionCost |
| 77 | getBlendedLoadCost(const TargetTransformInfo &TTI, Type *VecTy, Align Alignment, |
| 78 | unsigned AddressSpace, |
| 79 | const TargetTransformInfo::TargetCostKind CostKind); |
| 80 | |
| 81 | /// Returns the cost of the cast between the widened strided access type and |
| 82 | /// the entry vector type. |
| 83 | InstructionCost |
| 84 | getWidenedStridedCastCost(const TargetTransformInfo &TTI, Type *SrcTy, |
| 85 | Type *DstTy, const DataLayout &DL, |
| 86 | TargetTransformInfo::CastContextHint CCH, |
| 87 | TargetTransformInfo::TargetCostKind CostKind); |
| 88 | |
| 89 | /// For a non-power-of-2 \p NumElts-wide integer div/rem \p Opcode, checks if |
| 90 | /// padding to a full register and using the masked div/rem intrinsic is |
| 91 | /// cheaper than the direct vector op. Returns the cost of the masked |
| 92 | /// alternative, or an invalid cost if it is not applicable or not cheaper. |
| 93 | InstructionCost |
| 94 | getMaskedDivRemCost(const TargetTransformInfo &TTI, bool ReVec, unsigned Opcode, |
| 95 | Type *ScalarTy, unsigned NumElts, |
| 96 | const TargetTransformInfo::TargetCostKind CostKind, |
| 97 | FixedVectorType **PaddedTy = nullptr); |
| 98 | |
| 99 | /// Returns the cost of the booleanized logical and/or reduction of a vector |
| 100 | /// of type \p VecTy with the i1 root \p Root, emitted as the wide reduction |
| 101 | /// plus the result trunc. |
| 102 | InstructionCost |
| 103 | getBoolReduxWideRdxCost(const TargetTransformInfo &TTI, RecurKind RdxKind, |
| 104 | FixedVectorType *VecTy, const Value *Root, |
| 105 | FastMathFlags FMF, |
| 106 | TargetTransformInfo::TargetCostKind CostKind); |
| 107 | |
| 108 | /// Returns the cost of the booleanized logical and/or reduction of a vector |
| 109 | /// of type \p VecTy with the i1 root \p Root, emitted as trunc+bitcast+cmp, |
| 110 | /// estimated in the context of the replaced cast chain \p ChainInsts. |
| 111 | InstructionCost |
| 112 | getBoolReduxBitcastCmpCost(const TargetTransformInfo &TTI, RecurKind RdxKind, |
| 113 | FixedVectorType *VecTy, const Value *Root, |
| 114 | ArrayRef<Instruction *> ChainInsts, |
| 115 | TargetTransformInfo::TargetCostKind CostKind); |
| 116 | |
| 117 | /// Returns the cost of the boolean bitmask reduction of a vector of boolean |
| 118 | /// leaves of type \p NarrowScalarTy, emitted as [and] + [lane permutation |
| 119 | /// \p PermMask] + zero test + bitcast [+ zext] to \p WideTy. \p Root is the |
| 120 | /// reduction root, used as the context of the emitted instructions. |
| 121 | InstructionCost |
| 122 | getBoolBitmaskCost(const TargetTransformInfo &TTI, bool NeedMask, |
| 123 | Type *NarrowScalarTy, Type *WideTy, unsigned VF, |
| 124 | ArrayRef<int> PermMask, const Value *Root, |
| 125 | TargetTransformInfo::TargetCostKind CostKind); |
| 126 | |
| 127 | /// Returns the cost of the per-lane operations on the narrowed leaves |
| 128 | /// \p NarrowedLeafShifts: the shl in the wide vector type if any leaf is |
| 129 | /// shifted and the and in the narrow vector type if any leaf is masked. |
| 130 | InstructionCost getNarrowedLeafOpsCost( |
| 131 | const TargetTransformInfo &TTI, |
| 132 | const SmallDenseMap<Value *, NarrowedLeafInfo> &NarrowedLeafShifts, |
| 133 | VectorType *NarrowVecTy, VectorType *WideVecTy, const Instruction *CtxI, |
| 134 | TargetTransformInfo::TargetCostKind CostKind); |
| 135 | |
| 136 | /// This is similar to TargetTransformInfo::getScalarizationOverhead, but if |
| 137 | /// ScalarTy is a FixedVectorType, a vector will be inserted or extracted |
| 138 | /// instead of a scalar. |
| 139 | InstructionCost |
| 140 | (const TargetTransformInfo &TTI, bool ReVec, |
| 141 | Type *ScalarTy, VectorType *Ty, |
| 142 | const APInt &DemandedElts, bool Insert, bool , |
| 143 | const TargetTransformInfo::TargetCostKind CostKind, |
| 144 | bool ForPoisonSrc = true, ArrayRef<Value *> VL = {}, |
| 145 | TargetTransformInfo::VectorInstrContext VIC = |
| 146 | TargetTransformInfo::VectorInstrContext::None); |
| 147 | |
| 148 | /// This is similar to TargetTransformInfo::getVectorInstrCost, but if ScalarTy |
| 149 | /// is a FixedVectorType, a vector will be extracted instead of a scalar. |
| 150 | InstructionCost |
| 151 | getVectorInstrCost(const TargetTransformInfo &TTI, bool ReVec, Type *ScalarTy, |
| 152 | unsigned Opcode, Type *Val, |
| 153 | const TargetTransformInfo::TargetCostKind CostKind, |
| 154 | unsigned Index, Value *Scalar, |
| 155 | ArrayRef<std::tuple<Value *, User *, int>> ScalarUserAndIdx, |
| 156 | TTI::VectorInstrContext VIC = TTI::VectorInstrContext::None); |
| 157 | |
| 158 | /// This is similar to TargetTransformInfo::getExtractWithExtendCost, but if Dst |
| 159 | /// is a FixedVectorType, a vector will be extracted instead of a scalar. |
| 160 | InstructionCost |
| 161 | (const TargetTransformInfo &TTI, bool ReVec, |
| 162 | unsigned Opcode, Type *Dst, VectorType *VecTy, |
| 163 | unsigned Index, |
| 164 | const TargetTransformInfo::TargetCostKind CostKind); |
| 165 | |
| 166 | /// Returns the cost of the bitfield packing of \p SrcTy into \p ResultTy, |
| 167 | /// picking the cheapest shift width. The packing is a trunc, an lshr, a byte |
| 168 | /// shuffle and a bitcast. \p ZExtSrcWidth is the source width of the lanes if |
| 169 | /// they are a plain zext (0 otherwise), so compacting them back to it is free. |
| 170 | /// \p CCH is the context of the pack's source operand. |
| 171 | InstructionCost getBitPackCost(const TargetTransformInfo &TTI, |
| 172 | FixedVectorType *SrcTy, Type *ResultTy, |
| 173 | const BitPackInfo &Info, unsigned ZExtSrcWidth, |
| 174 | TargetTransformInfo::CastContextHint CCH, |
| 175 | TargetTransformInfo::TargetCostKind CostKind, |
| 176 | const TargetLibraryInfo *TLI, |
| 177 | const Instruction *CtxI, unsigned &ShiftWidth); |
| 178 | |
| 179 | /// i1 reductions can be emitted as the plain target reduction or in the |
| 180 | /// bitcast-based form (bitcast to a scalar integer type plus a compare for |
| 181 | /// and/or, plus ctpop for add). Returns the cost of the cheaper form and |
| 182 | /// whether it is the bitcast-based one. Ties keep the historically default |
| 183 | /// form: plain for and/or, bitcast-based for add. |
| 184 | std::pair<InstructionCost, bool> |
| 185 | getI1ReductionCost(RecurKind Kind, const TargetTransformInfo &TTI, |
| 186 | FixedVectorType *VectorTy, Type *ScalarTy, |
| 187 | TargetTransformInfo::CastContextHint Ctx, |
| 188 | TargetTransformInfo::TargetCostKind CostKind); |
| 189 | |
| 190 | /// Builds the arguments types vector for the given call instruction with the |
| 191 | /// given \p ID for the specified vector factor. |
| 192 | SmallVector<Type *> buildIntrinsicArgTypes(const CallInst *CI, |
| 193 | const Intrinsic::ID ID, |
| 194 | const unsigned VF, unsigned MinBW, |
| 195 | const TargetTransformInfo &TTI); |
| 196 | |
| 197 | /// Calculates the costs of vectorized intrinsic (if possible) and vectorized |
| 198 | /// function (if possible) calls. Returns invalid cost for the corresponding |
| 199 | /// calls, if they cannot be vectorized/will be scalarized. |
| 200 | std::pair<InstructionCost, InstructionCost> |
| 201 | getVectorCallCosts(CallInst *CI, Type *VecTy, const TargetTransformInfo &TTI, |
| 202 | const TargetLibraryInfo &TLI, ArrayRef<Type *> ArgTys, |
| 203 | const TargetTransformInfo::TargetCostKind CostKind); |
| 204 | |
| 205 | /// Memoizes opcode / intrinsic / callee kinds already ruled out as seeds. |
| 206 | struct PoorThroughputOpCache { |
| 207 | SmallDenseSet<std::pair<unsigned, unsigned>> CheapOpcodes; |
| 208 | SmallDenseSet<std::pair<Intrinsic::ID, unsigned>> CheapIntrinsics; |
| 209 | // Keyed on the callee alone: a Function's signature is fixed, so its type |
| 210 | // never varies between calls. |
| 211 | SmallDenseSet<const Function *> CheapCallees; |
| 212 | }; |
| 213 | |
| 214 | /// Returns true if \p I is an expensive scalar op whose vector form is cheaper |
| 215 | /// per lane (e.g. fdiv, frem, fsqrt). If \p MaxVecRegSize is non-zero, the |
| 216 | /// widest vector fitting into it is checked too. |
| 217 | bool isPoorThroughputOp(bool ReVec, Instruction *I, |
| 218 | const TargetTransformInfo &TTI, |
| 219 | const TargetLibraryInfo &TLI, |
| 220 | PoorThroughputOpCache &Cache, |
| 221 | const TargetTransformInfo::TargetCostKind CostKind, |
| 222 | unsigned MaxVecRegSize = 0); |
| 223 | |
| 224 | /// \returns true if \p Op is a contractable single-use fmul, which the backend |
| 225 | /// fuses with its fadd/fsub user \p I: \p Op is in the block of \p I or the |
| 226 | /// target sinks it there. |
| 227 | bool isFusableFMulOperand(Value *Op, Instruction *I, |
| 228 | const TargetTransformInfo &TTI); |
| 229 | |
| 230 | /// \returns true if more values with the scalar type \p Ty than registers are |
| 231 | /// live at some point of the block \p BB. The blocks larger than the scheduling |
| 232 | /// budget \p ScheduleBudget are skipped to save compile time. |
| 233 | bool hasHighRegisterPressure(unsigned ScheduleBudget, const BasicBlock &BB, |
| 234 | Type *Ty, const TargetTransformInfo &TTI); |
| 235 | |
| 236 | /// Selects the gathers of \p GatheredScalars, which fully reverse the bytes of |
| 237 | /// a scalar and are emitted as a byte swap of the scalar, if it is not more |
| 238 | /// expensive than the permutation of the bytes. The permutation of the scalar |
| 239 | /// extracted from a vector folds the extraction, the byte swap does not, so the |
| 240 | /// byte swaps of the scalars extracted from the same vector are estimated |
| 241 | /// together with all these extractions. \p GetVectorizedSource returns the key |
| 242 | /// and the type of the vector the vectorized scalar is extracted from, and its |
| 243 | /// lane. \returns the mask of the selected gathers. |
| 244 | SmallBitVector selectBSwapGathers( |
| 245 | ArrayRef<SmallVector<Value *>> GatheredScalars, const DataLayout &DL, |
| 246 | const TargetTransformInfo &TTI, bool ReVec, |
| 247 | TargetTransformInfo::TargetCostKind CostKind, |
| 248 | function_ref<std::optional< |
| 249 | std::tuple<const void *, FixedVectorType *, unsigned>>(Value *)> |
| 250 | GetVectorizedSource); |
| 251 | |
| 252 | } // namespace llvm::slpvectorizer |
| 253 | |
| 254 | #endif // LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPCOSTANALYSIS_H |
| 255 | |