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
34namespace llvm {
35class APInt;
36class BasicBlock;
37class CallInst;
38class DataLayout;
39class FastMathFlags;
40class FixedVectorType;
41class Function;
42class Instruction;
43class TargetLibraryInfo;
44class Type;
45class User;
46class Value;
47class VectorType;
48enum class RecurKind;
49} // namespace llvm
50
51namespace 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.
56InstructionCost
57getShuffleCost(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.
66std::pair<InstructionCost, InstructionCost>
67getGEPCosts(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.
76InstructionCost
77getBlendedLoadCost(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.
83InstructionCost
84getWidenedStridedCastCost(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.
93InstructionCost
94getMaskedDivRemCost(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.
102InstructionCost
103getBoolReduxWideRdxCost(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.
111InstructionCost
112getBoolReduxBitcastCmpCost(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.
121InstructionCost
122getBoolBitmaskCost(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.
130InstructionCost 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.
139InstructionCost
140getScalarizationOverhead(const TargetTransformInfo &TTI, bool ReVec,
141 Type *ScalarTy, VectorType *Ty,
142 const APInt &DemandedElts, bool Insert, bool Extract,
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.
150InstructionCost
151getVectorInstrCost(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.
160InstructionCost
161getExtractWithExtendCost(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.
171InstructionCost 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.
184std::pair<InstructionCost, bool>
185getI1ReductionCost(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.
192SmallVector<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.
200std::pair<InstructionCost, InstructionCost>
201getVectorCallCosts(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.
206struct 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.
217bool 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.
227bool 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.
233bool 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.
244SmallBitVector 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