1//===- SLPCostAnalysis.cpp - SLP Vectorizer free cost helpers -------------===//
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#include "SLPCostAnalysis.h"
10#include "SLPTypeUtils.h"
11#include "SLPUtils.h"
12
13#include "llvm/ADT/APInt.h"
14#include "llvm/ADT/STLExtras.h"
15#include "llvm/ADT/Sequence.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/Analysis/IVDescriptors.h"
18#include "llvm/IR/Constants.h"
19#include "llvm/IR/DerivedTypes.h"
20#include "llvm/IR/Instructions.h"
21#include "llvm/IR/IntrinsicInst.h"
22#include "llvm/IR/Operator.h"
23#include "llvm/IR/PatternMatch.h"
24#include "llvm/IR/Type.h"
25#include "llvm/IR/Value.h"
26#include "llvm/IR/VectorTypeUtils.h"
27#include "llvm/Support/Casting.h"
28
29#include <cassert>
30#include <utility>
31
32using namespace llvm;
33using namespace llvm::PatternMatch;
34
35namespace llvm::slpvectorizer {
36
37InstructionCost getShuffleCost(const TargetTransformInfo &TTI,
38 TTI::ShuffleKind Kind, VectorType *Tp,
39 const TTI::TargetCostKind CostKind,
40 ArrayRef<int> Mask, int Index, VectorType *SubTp,
41 ArrayRef<const Value *> Args) {
42 VectorType *DstTy = Tp;
43 if (!Mask.empty())
44 DstTy = FixedVectorType::get(ElementType: Tp->getScalarType(), NumElts: Mask.size());
45
46 if (Kind != TTI::SK_PermuteTwoSrc)
47 return TTI.getShuffleCost(Kind, DstTy, SrcTy: Tp, CostKind, Mask, Index, SubTp,
48 Args);
49 int NumSrcElts = Tp->getElementCount().getKnownMinValue();
50 int NumSubElts;
51 if (Mask.size() > 2 && ShuffleVectorInst::isInsertSubvectorMask(
52 Mask, NumSrcElts, NumSubElts, Index)) {
53 if (Index + NumSubElts > NumSrcElts &&
54 Index + NumSrcElts <= static_cast<int>(Mask.size()))
55 return TTI.getShuffleCost(Kind: TTI::SK_InsertSubvector, DstTy, SrcTy: Tp, CostKind,
56 Mask, Index, SubTp: Tp);
57 }
58 return TTI.getShuffleCost(Kind, DstTy, SrcTy: Tp, CostKind, Mask, Index, SubTp,
59 Args);
60}
61
62std::pair<InstructionCost, InstructionCost>
63getGEPCosts(const TargetTransformInfo &TTI, ArrayRef<Value *> Ptrs,
64 Value *BasePtr, unsigned Opcode, const TTI::TargetCostKind CostKind,
65 Type *ScalarTy, VectorType *VecTy) {
66 InstructionCost ScalarCost = 0;
67 InstructionCost VecCost = 0;
68 // Here we differentiate two cases: (1) when Ptrs represent a regular
69 // vectorization tree node (as they are pointer arguments of scattered
70 // loads) or (2) when Ptrs are the arguments of loads or stores being
71 // vectorized as plane wide unit-stride load/store since all the
72 // loads/stores are known to be from/to adjacent locations.
73 if (Opcode == Instruction::Load || Opcode == Instruction::Store) {
74 // Case 2: estimate costs for pointer related costs when vectorizing to
75 // a wide load/store.
76 // Scalar cost is estimated as a set of pointers with known relationship
77 // between them.
78 // For vector code we will use BasePtr as argument for the wide load/store
79 // but we also need to account all the instructions which are going to
80 // stay in vectorized code due to uses outside of these scalar
81 // loads/stores.
82 ScalarCost = TTI.getPointersChainCost(
83 Ptrs, Base: BasePtr, Info: TTI::PointersChainInfo::getUnitStride(), AccessTy: ScalarTy,
84 CostKind);
85
86 SmallVector<const Value *> PtrsRetainedInVecCode;
87 for (Value *V : Ptrs) {
88 if (V == BasePtr) {
89 PtrsRetainedInVecCode.push_back(Elt: V);
90 continue;
91 }
92 auto *Ptr = dyn_cast<GetElementPtrInst>(Val: V);
93 // For simplicity assume Ptr to stay in vectorized code if it's not a
94 // GEP instruction. We don't care since it's cost considered free.
95 // TODO: We should check for any uses outside of vectorizable tree
96 // rather than just single use.
97 if (!Ptr || !Ptr->hasOneUse())
98 PtrsRetainedInVecCode.push_back(Elt: V);
99 }
100
101 if (PtrsRetainedInVecCode.size() == Ptrs.size()) {
102 // If all pointers stay in vectorized code then we don't have
103 // any savings on that.
104 return std::make_pair(x: TTI::TCC_Free, y: TTI::TCC_Free);
105 }
106 VecCost = TTI.getPointersChainCost(Ptrs: PtrsRetainedInVecCode, Base: BasePtr,
107 Info: TTI::PointersChainInfo::getKnownStride(),
108 AccessTy: VecTy, CostKind);
109 } else {
110 // Case 1: Ptrs are the arguments of loads that we are going to transform
111 // into masked gather load intrinsic.
112 // All the scalar GEPs will be removed as a result of vectorization.
113 // For any external uses of some lanes extract element instructions will
114 // be generated (which cost is estimated separately).
115 TTI::PointersChainInfo PtrsInfo =
116 all_of(Range&: Ptrs,
117 P: [](const Value *V) {
118 auto *Ptr = dyn_cast<GetElementPtrInst>(Val: V);
119 return Ptr && !Ptr->hasAllConstantIndices();
120 })
121 ? TTI::PointersChainInfo::getUnknownStride()
122 : TTI::PointersChainInfo::getKnownStride();
123
124 ScalarCost =
125 TTI.getPointersChainCost(Ptrs, Base: BasePtr, Info: PtrsInfo, AccessTy: ScalarTy, CostKind);
126 auto *BaseGEP = dyn_cast<GEPOperator>(Val: BasePtr);
127 if (!BaseGEP) {
128 auto *It = find_if(Range&: Ptrs, P: IsaPred<GEPOperator>);
129 if (It != Ptrs.end())
130 BaseGEP = cast<GEPOperator>(Val: *It);
131 }
132 if (BaseGEP) {
133 SmallVector<const Value *> Indices(BaseGEP->indices());
134 VecCost = TTI.getGEPCost(PointeeType: BaseGEP->getSourceElementType(),
135 Ptr: BaseGEP->getPointerOperand(), Operands: Indices, CostKind,
136 AccessType: VecTy);
137 }
138 }
139
140 return std::make_pair(x&: ScalarCost, y&: VecCost);
141}
142
143InstructionCost getBlendedLoadCost(const TargetTransformInfo &TTI, Type *VecTy,
144 Align Alignment, unsigned AddressSpace,
145 const TTI::TargetCostKind CostKind) {
146 Type *CmpTy = CmpInst::makeCmpResultType(opnd_type: VecTy);
147 return 2 * TTI.getMemIntrinsicInstrCost(
148 MICA: MemIntrinsicCostAttributes(Intrinsic::masked_load, VecTy,
149 Alignment, AddressSpace),
150 CostKind) +
151 TTI.getArithmeticInstrCost(Opcode: Instruction::Xor, Ty: CmpTy, CostKind) +
152 TTI.getCmpSelInstrCost(Opcode: Instruction::Select, ValTy: VecTy, CondTy: CmpTy,
153 VecPred: CmpInst::BAD_ICMP_PREDICATE, CostKind);
154}
155
156InstructionCost getMaskedDivRemCost(const TargetTransformInfo &TTI, bool ReVec,
157 unsigned Opcode, Type *ScalarTy,
158 unsigned NumElts,
159 const TTI::TargetCostKind CostKind,
160 FixedVectorType **PaddedTy) {
161 FixedVectorType *PaddedVecTy =
162 getMaskedDivRemType(TTI, Opcode, ScalarTy, NumElts, ReVec);
163 if (!PaddedVecTy)
164 return InstructionCost::getInvalid();
165 // One mask bit per element of the padded vector, not per padded lane.
166 auto *MaskTy =
167 FixedVectorType::get(ElementType: IntegerType::getInt1Ty(C&: ScalarTy->getContext()),
168 NumElts: PaddedVecTy->getNumElements());
169 InstructionCost DirectCost = TTI.getArithmeticInstrCost(
170 Opcode, Ty: getWidenedType(ScalarTy, VF: NumElts), CostKind);
171 IntrinsicCostAttributes ICA(getMaskedDivRemIntrinsic(Opcode), PaddedVecTy,
172 {PaddedVecTy, PaddedVecTy, MaskTy});
173 InstructionCost MaskedCost = TTI.getIntrinsicInstrCost(ICA, CostKind);
174 if (!MaskedCost.isValid() || MaskedCost >= DirectCost)
175 return InstructionCost::getInvalid();
176 if (PaddedTy)
177 *PaddedTy = PaddedVecTy;
178 return MaskedCost;
179}
180
181InstructionCost
182getScalarizationOverhead(const TargetTransformInfo &TTI, bool ReVec,
183 Type *ScalarTy, VectorType *Ty,
184 const APInt &DemandedElts, bool Insert, bool Extract,
185 const TTI::TargetCostKind CostKind, bool ForPoisonSrc,
186 ArrayRef<Value *> VL, TTI::VectorInstrContext VIC) {
187 assert(!isa<ScalableVectorType>(Ty) &&
188 "ScalableVectorType is not supported.");
189 assert(getNumElements(ScalarTy) * DemandedElts.getBitWidth() ==
190 getNumElements(Ty) &&
191 "Incorrect usage.");
192 if (auto *VecTy = dyn_cast<FixedVectorType>(Val: ScalarTy)) {
193 assert(ReVec && "Only supported by REVEC.");
194 // If ScalarTy is FixedVectorType, we should use CreateInsertVector instead
195 // of CreateInsertElement.
196 unsigned ScalarTyNumElements = VecTy->getNumElements();
197 InstructionCost Cost = 0;
198 for (unsigned I : seq(Size: DemandedElts.getBitWidth())) {
199 if (!DemandedElts[I])
200 continue;
201 if (Insert)
202 Cost += getShuffleCost(TTI, Kind: TTI::SK_InsertSubvector, Tp: Ty, CostKind, Mask: {},
203 Index: I * ScalarTyNumElements, SubTp: VecTy);
204 if (Extract)
205 Cost += getShuffleCost(TTI, Kind: TTI::SK_ExtractSubvector, Tp: Ty, CostKind, Mask: {},
206 Index: I * ScalarTyNumElements, SubTp: VecTy);
207 }
208 return Cost;
209 }
210 return TTI.getScalarizationOverhead(Ty, DemandedElts, Insert, Extract,
211 CostKind, ForPoisonSrc, VL, VIC);
212}
213
214InstructionCost getVectorInstrCost(
215 const TargetTransformInfo &TTI, bool ReVec, Type *ScalarTy, unsigned Opcode,
216 Type *Val, const TTI::TargetCostKind CostKind, unsigned Index,
217 Value *Scalar,
218 ArrayRef<std::tuple<Value *, User *, int>> ScalarUserAndIdx) {
219 if (Opcode == Instruction::ExtractElement) {
220 if (auto *VecTy = dyn_cast<FixedVectorType>(Val: ScalarTy)) {
221 assert(ReVec && "Only supported by REVEC.");
222 assert(isa<VectorType>(Val) && "Val must be a vector type.");
223 return getShuffleCost(TTI, Kind: TTI::SK_ExtractSubvector,
224 Tp: cast<VectorType>(Val), CostKind, Mask: {},
225 Index: Index * VecTy->getNumElements(), SubTp: VecTy);
226 }
227 }
228 return TTI.getVectorInstrCost(Opcode, Val, CostKind, Index, Scalar,
229 ScalarUserAndIdx);
230}
231
232InstructionCost getExtractWithExtendCost(const TargetTransformInfo &TTI,
233 bool ReVec, unsigned Opcode, Type *Dst,
234 VectorType *VecTy, unsigned Index,
235 const TTI::TargetCostKind CostKind) {
236 if (isVectorizedTy(Ty: Dst)) {
237 assert(ReVec && "Only supported by REVEC.");
238 auto *SubTp = cast<FixedVectorType>(
239 Val: getWidenedType(ScalarTy: toScalarizedTy(Ty: VecTy), VF: getNumElements(Ty: Dst)));
240 return getShuffleCost(TTI, Kind: TTI::SK_ExtractSubvector, Tp: VecTy, CostKind, Mask: {},
241 Index: Index * getNumElements(Ty: Dst), SubTp) +
242 TTI.getCastInstrCost(Opcode, Dst, Src: SubTp, CCH: TTI::CastContextHint::None,
243 CostKind);
244 }
245 return TTI.getExtractWithExtendCost(Opcode, Dst, VecTy, Index, CostKind);
246}
247
248/// Returns the cast context hint for the trunc of the booleanized reduction
249/// result, which inherits the uses of the reduction root \p Root.
250static TTI::CastContextHint getBoolReduxResultCCH(const Value *Root) {
251 if (!Root->hasOneUse())
252 return TTI::CastContextHint::None;
253 const Value *U = *Root->user_begin();
254 if (isa<StoreInst>(Val: U))
255 return TTI::CastContextHint::Normal;
256 if (match(V: U, P: m_Intrinsic<Intrinsic::masked_store>()))
257 return TTI::CastContextHint::Masked;
258 if (match(V: U, P: m_Intrinsic<Intrinsic::masked_scatter>()))
259 return TTI::CastContextHint::GatherScatter;
260 return TTI::CastContextHint::None;
261}
262
263InstructionCost getBoolReduxWideRdxCost(const TargetTransformInfo &TTI,
264 RecurKind RdxKind,
265 FixedVectorType *VecTy,
266 const Value *Root, FastMathFlags FMF,
267 const TTI::TargetCostKind CostKind) {
268 Type *I1Ty = Type::getInt1Ty(C&: VecTy->getContext());
269 return TTI.getArithmeticReductionCost(
270 Opcode: RecurrenceDescriptor::getOpcode(Kind: RdxKind), Ty: VecTy, FMF, CostKind) +
271 TTI.getCastInstrCost(Opcode: Instruction::Trunc, Dst: I1Ty, Src: VecTy->getScalarType(),
272 CCH: getBoolReduxResultCCH(Root), CostKind);
273}
274
275InstructionCost getBoolReduxBitcastCmpCost(const TargetTransformInfo &TTI,
276 RecurKind RdxKind,
277 FixedVectorType *VecTy,
278 const Value *Root,
279 ArrayRef<Instruction *> ChainInsts,
280 const TTI::TargetCostKind CostKind) {
281 // The new instructions are costed in the context of the replaced cast chain
282 // instructions.
283 auto TruncIt =
284 find_if(Range&: ChainInsts, P: [](Instruction *I) { return isa<TruncInst>(Val: I); });
285 const Instruction *TruncI = TruncIt == ChainInsts.end() ? nullptr : *TruncIt;
286 auto CmpIt =
287 find_if(Range&: ChainInsts, P: [](Instruction *I) { return isa<ICmpInst>(Val: I); });
288 const Instruction *CmpI = CmpIt == ChainInsts.end() ? nullptr : *CmpIt;
289 unsigned VF = VecTy->getNumElements();
290 auto *I1VecTy =
291 FixedVectorType::get(ElementType: Type::getInt1Ty(C&: VecTy->getContext()), NumElts: VF);
292 Type *IntTy = IntegerType::get(C&: VecTy->getContext(), NumBits: VF);
293 Constant *CmpRHS = RdxKind == RecurKind::And
294 ? Constant::getAllOnesValue(Ty: IntTy)
295 : Constant::getNullValue(Ty: IntTy);
296 return TTI.getCastInstrCost(Opcode: Instruction::Trunc, Dst: I1VecTy, Src: VecTy,
297 CCH: TTI.getCastContextHint(I: TruncI), CostKind,
298 I: TruncI) +
299 TTI.getCastInstrCost(Opcode: Instruction::BitCast, Dst: IntTy, Src: I1VecTy,
300 CCH: TTI.getCastContextHint(I: TruncI), CostKind) +
301 TTI.getCmpSelInstrCost(Opcode: Instruction::ICmp, ValTy: IntTy, /*CondTy=*/nullptr,
302 VecPred: RdxKind == RecurKind::And ? CmpInst::ICMP_EQ
303 : CmpInst::ICMP_NE,
304 CostKind, Op1Info: TTI.getOperandInfo(V: Root),
305 Op2Info: TTI.getOperandInfo(V: CmpRHS), I: CmpI);
306}
307
308InstructionCost getBitPackCost(const TargetTransformInfo &TTI,
309 FixedVectorType *SrcTy, Type *ResultTy,
310 const BitPackInfo &Info, unsigned ZExtSrcWidth,
311 TTI::CastContextHint CCH,
312 TTI::TargetCostKind CostKind,
313 const TargetLibraryInfo *TLI,
314 const Instruction *CxtI, unsigned &ShiftWidth) {
315 unsigned BitWidth = SrcTy->getScalarSizeInBits();
316 unsigned NumElts = SrcTy->getNumElements();
317 uint64_t MaxAmt = *max_element(Range: Info.LShrAmts);
318 // The shift amounts form a constant vector.
319 TTI::OperandValueInfo ShiftAmtInfo = {
320 .Kind: all_equal(Range: Info.LShrAmts) ? TTI::OK_UniformConstantValue
321 : TTI::OK_NonUniformConstantValue,
322 .Properties: all_of(Range: Info.LShrAmts,
323 P: [](uint64_t A) { return A == 0 || isPowerOf2_64(Value: A); })
324 ? TTI::OP_PowerOf2
325 : TTI::OP_None};
326 // After the shift the field content of each lane sits in the low bits of
327 // the lane, so the packing is a single byte shuffle of the shifted lanes.
328 // Pick the cheapest shift width: the narrowest type still holding the field
329 // content is not always the cheapest (e.g. missing narrow variable shifts).
330 Type *Int8Ty = Type::getInt8Ty(C&: SrcTy->getContext());
331 assert(BitWidth % 8 == 0 &&
332 "The byte-multiple field width divides the result bit width.");
333 unsigned OutBytes = BitWidth / 8;
334 auto *PackTy = FixedVectorType::get(ElementType: Int8Ty, NumElts: OutBytes);
335 unsigned MinShiftWidth = 8;
336 while (MinShiftWidth < MaxAmt + Info.FieldWidth)
337 MinShiftWidth *= 2;
338 InstructionCost NewCost = InstructionCost::getInvalid();
339 ShiftWidth = 0;
340 for (unsigned W2 = MinShiftWidth; W2 <= BitWidth; W2 *= 2) {
341 auto *ShiftTy = FixedVectorType::get(
342 ElementType: IntegerType::get(C&: SrcTy->getContext(), NumBits: W2), NumElts);
343 unsigned BytesPerLane = W2 / 8;
344 unsigned InBytes = NumElts * BytesPerLane;
345 SmallVector<int> Mask =
346 getBitPackMask(Info, NumBytes: OutBytes, NumElts, BytesPerLane);
347 InstructionCost C = TTI.getCastInstrCost(Opcode: Instruction::BitCast, Dst: ResultTy,
348 Src: PackTy, CCH, CostKind);
349 // A plain byte reversal of the shifted lanes is a bswap, no shuffle.
350 if (ShuffleVectorInst::isReverseMask(Mask, NumSrcElts: InBytes)) {
351 IntrinsicCostAttributes CostAttrs(Intrinsic::bswap, ResultTy, {ResultTy});
352 C += TTI.getIntrinsicInstrCost(ICA: CostAttrs, CostKind);
353 } else if (!ShuffleVectorInst::isIdentityMask(Mask, NumSrcElts: InBytes)) {
354 C += TTI.getShuffleCost(
355 Kind: is_contained(Range: Info.LaneOfField, Element: BitPackInfo::NoLane)
356 ? TargetTransformInfo::SK_PermuteTwoSrc
357 : TargetTransformInfo::SK_PermuteSingleSrc,
358 DstTy: PackTy, SrcTy: FixedVectorType::get(ElementType: Int8Ty, NumElts: InBytes), CostKind, Mask,
359 /*Index=*/0, /*SubTp=*/nullptr, /*Args=*/{}, CxtI);
360 }
361 if (W2 != BitWidth && W2 != ZExtSrcWidth)
362 C += TTI.getCastInstrCost(Opcode: Instruction::Trunc, Dst: ShiftTy, Src: SrcTy, CCH,
363 CostKind);
364 if (Info.needsShift())
365 C += TTI.getArithmeticInstrCost(Opcode: Instruction::LShr, Ty: ShiftTy, CostKind,
366 /*Opd1Info=*/{}, Opd2Info: ShiftAmtInfo,
367 /*Args=*/{}, CxtI, TLibInfo: TLI);
368 if (C.isValid() && (!NewCost.isValid() || C < NewCost)) {
369 NewCost = C;
370 ShiftWidth = W2;
371 }
372 }
373 return NewCost;
374}
375
376} // namespace llvm::slpvectorizer
377