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/DataLayout.h"
20#include "llvm/IR/DerivedTypes.h"
21#include "llvm/IR/Instructions.h"
22#include "llvm/IR/IntrinsicInst.h"
23#include "llvm/IR/Intrinsics.h"
24#include "llvm/IR/Operator.h"
25#include "llvm/IR/PatternMatch.h"
26#include "llvm/IR/Type.h"
27#include "llvm/IR/Value.h"
28#include "llvm/IR/VectorTypeUtils.h"
29#include "llvm/Support/Casting.h"
30#include "llvm/Support/MathExtras.h"
31
32#include <cassert>
33#include <utility>
34
35using namespace llvm;
36using namespace llvm::PatternMatch;
37
38namespace llvm::slpvectorizer {
39
40InstructionCost getShuffleCost(const TargetTransformInfo &TTI,
41 TTI::ShuffleKind Kind, VectorType *Tp,
42 const TTI::TargetCostKind CostKind,
43 ArrayRef<int> Mask, int Index, VectorType *SubTp,
44 ArrayRef<const Value *> Args,
45 TTI::VectorInstrContext VIC) {
46 VectorType *DstTy = Tp;
47 if (!Mask.empty())
48 DstTy = FixedVectorType::get(ElementType: Tp->getScalarType(), NumElts: Mask.size());
49
50 if (Kind != TTI::SK_PermuteTwoSrc)
51 return TTI.getShuffleCost(Kind, DstTy, SrcTy: Tp, CostKind, Mask, Index, SubTp,
52 Args, /*CtxI=*/nullptr, VIC);
53 int NumSrcElts = Tp->getElementCount().getKnownMinValue();
54 int NumSubElts;
55 if (Mask.size() > 2 && ShuffleVectorInst::isInsertSubvectorMask(
56 Mask, NumSrcElts, NumSubElts, Index)) {
57 if (Index + NumSubElts > NumSrcElts &&
58 Index + NumSrcElts <= static_cast<int>(Mask.size()))
59 return TTI.getShuffleCost(Kind: TTI::SK_InsertSubvector, DstTy, SrcTy: Tp, CostKind,
60 Mask, Index, SubTp: Tp);
61 }
62 return TTI.getShuffleCost(Kind, DstTy, SrcTy: Tp, CostKind, Mask, Index, SubTp, Args,
63 /*CtxI=*/nullptr, VIC);
64}
65
66std::pair<InstructionCost, InstructionCost>
67getGEPCosts(const TargetTransformInfo &TTI, ArrayRef<Value *> Ptrs,
68 Value *BasePtr, unsigned Opcode, const TTI::TargetCostKind CostKind,
69 Type *ScalarTy, VectorType *VecTy) {
70 InstructionCost ScalarCost = 0;
71 InstructionCost VecCost = 0;
72 // Here we differentiate two cases: (1) when Ptrs represent a regular
73 // vectorization tree node (as they are pointer arguments of scattered
74 // loads) or (2) when Ptrs are the arguments of loads or stores being
75 // vectorized as plane wide unit-stride load/store since all the
76 // loads/stores are known to be from/to adjacent locations.
77 if (Opcode == Instruction::Load || Opcode == Instruction::Store) {
78 // Case 2: estimate costs for pointer related costs when vectorizing to
79 // a wide load/store.
80 // Scalar cost is estimated as a set of pointers with known relationship
81 // between them.
82 // For vector code we will use BasePtr as argument for the wide load/store
83 // but we also need to account all the instructions which are going to
84 // stay in vectorized code due to uses outside of these scalar
85 // loads/stores.
86 ScalarCost = TTI.getPointersChainCost(
87 Ptrs, Base: BasePtr, Info: TTI::PointersChainInfo::getUnitStride(), AccessTy: ScalarTy,
88 CostKind);
89
90 SmallVector<const Value *> PtrsRetainedInVecCode;
91 for (Value *V : Ptrs) {
92 if (V == BasePtr) {
93 PtrsRetainedInVecCode.push_back(Elt: V);
94 continue;
95 }
96 auto *Ptr = dyn_cast<GetElementPtrInst>(Val: V);
97 // For simplicity assume Ptr to stay in vectorized code if it's not a
98 // GEP instruction. We don't care since it's cost considered free.
99 // TODO: We should check for any uses outside of vectorizable tree
100 // rather than just single use.
101 if (!Ptr || !Ptr->hasOneUse())
102 PtrsRetainedInVecCode.push_back(Elt: V);
103 }
104
105 if (PtrsRetainedInVecCode.size() == Ptrs.size()) {
106 // If all pointers stay in vectorized code then we don't have
107 // any savings on that.
108 return std::make_pair(x: TTI::TCC_Free, y: TTI::TCC_Free);
109 }
110 VecCost = TTI.getPointersChainCost(Ptrs: PtrsRetainedInVecCode, Base: BasePtr,
111 Info: TTI::PointersChainInfo::getKnownStride(),
112 AccessTy: VecTy, CostKind);
113 } else {
114 // Case 1: Ptrs are the arguments of loads that we are going to transform
115 // into masked gather load intrinsic.
116 // All the scalar GEPs will be removed as a result of vectorization.
117 // For any external uses of some lanes extract element instructions will
118 // be generated (which cost is estimated separately).
119 TTI::PointersChainInfo PtrsInfo =
120 all_of(Range&: Ptrs,
121 P: [](const Value *V) {
122 auto *Ptr = dyn_cast<GetElementPtrInst>(Val: V);
123 return Ptr && !Ptr->hasAllConstantIndices();
124 })
125 ? TTI::PointersChainInfo::getUnknownStride()
126 : TTI::PointersChainInfo::getKnownStride();
127
128 const bool IsSameBase =
129 !all_of(Range&: Ptrs, P: IsaPred<GetElementPtrInst>) ||
130 all_equal(Range: map_range(C&: Ptrs, F: [](Value *V) {
131 return cast<GetElementPtrInst>(Val: V)->getPointerOperand();
132 }));
133 // The GEPs of the masked gather loads are accessed with the loaded type
134 // and form a chain only if the lanes share the base.
135 Type *AccessTy = ScalarTy;
136 if (all_of(Range&: Ptrs, P: [](const Value *V) {
137 auto *Ptr = dyn_cast<GetElementPtrInst>(Val: V);
138 return Ptr && Ptr->hasOneUse() && isa<LoadInst>(Val: Ptr->user_back());
139 })) {
140 PtrsInfo.IsSameBaseAddress = IsSameBase;
141 AccessTy = Ptrs.front()->user_back()->getType();
142 }
143 ScalarCost =
144 TTI.getPointersChainCost(Ptrs, Base: BasePtr, Info: PtrsInfo, AccessTy, CostKind);
145 auto *BaseGEP = dyn_cast<GEPOperator>(Val: BasePtr);
146 if (!BaseGEP) {
147 auto *It = find_if(Range&: Ptrs, P: IsaPred<GEPOperator>);
148 if (It != Ptrs.end())
149 BaseGEP = cast<GEPOperator>(Val: *It);
150 }
151 if (!IsSameBase) {
152 // The different bases are not folded into the addressing of the vector
153 // access, the scaled indices are added to them.
154 const DataLayout &DL = cast<Instruction>(Val: Ptrs.front())->getDataLayout();
155 Type *IdxTy = DL.getIndexType(PtrTy: VecTy);
156 VecCost = TTI.getArithmeticInstrCost(Opcode: Instruction::Add, Ty: IdxTy, CostKind);
157 uint64_t Stride = DL.getTypeAllocSize(Ty: BaseGEP->getSourceElementType())
158 .getKnownMinValue();
159 if (Stride != 1 && !all_of(Range&: Ptrs, P: [](Value *V) {
160 return isa<Constant>(Val: cast<GetElementPtrInst>(Val: V)->getOperand(i_nocapture: 1));
161 }))
162 VecCost += TTI.getArithmeticInstrCost(
163 Opcode: isPowerOf2_64(Value: Stride) ? Instruction::Shl : Instruction::Mul, Ty: IdxTy,
164 CostKind, Opd1Info: {}, Opd2Info: {.Kind: TTI::OK_UniformConstantValue, .Properties: TTI::OP_None});
165 } else if (BaseGEP) {
166 SmallVector<const Value *> Indices(BaseGEP->indices());
167 VecCost = TTI.getGEPCost(PointeeType: BaseGEP->getSourceElementType(),
168 Ptr: BaseGEP->getPointerOperand(), Operands: Indices, CostKind,
169 AccessType: VecTy);
170 }
171 }
172
173 return std::make_pair(x&: ScalarCost, y&: VecCost);
174}
175
176InstructionCost getBlendedLoadCost(const TargetTransformInfo &TTI, Type *VecTy,
177 Align Alignment, unsigned AddressSpace,
178 const TTI::TargetCostKind CostKind) {
179 Type *CmpTy = CmpInst::makeCmpResultType(opnd_type: VecTy);
180 return 2 * TTI.getMemIntrinsicInstrCost(
181 MICA: MemIntrinsicCostAttributes(Intrinsic::masked_load, VecTy,
182 Alignment, AddressSpace),
183 CostKind) +
184 TTI.getArithmeticInstrCost(Opcode: Instruction::Xor, Ty: CmpTy, CostKind) +
185 TTI.getCmpSelInstrCost(Opcode: Instruction::Select, ValTy: VecTy, CondTy: CmpTy,
186 VecPred: CmpInst::BAD_ICMP_PREDICATE, CostKind);
187}
188
189InstructionCost getWidenedStridedCastCost(const TargetTransformInfo &TTI,
190 Type *SrcTy, Type *DstTy,
191 const DataLayout &DL,
192 TTI::CastContextHint CCH,
193 TTI::TargetCostKind CostKind) {
194 bool ToPtr = cast<VectorType>(Val: DstTy)->getElementType()->isPointerTy();
195 if (ToPtr == cast<VectorType>(Val: SrcTy)->getElementType()->isPointerTy())
196 return TTI.getCastInstrCost(Opcode: Instruction::BitCast, Dst: DstTy, Src: SrcTy, CCH,
197 CostKind);
198 // The ptr/int conversion keeps the vector shape, the bitcast transforms the
199 // resulting integer vector.
200 if (ToPtr) {
201 Type *IntVecTy = DL.getIntPtrType(DstTy);
202 return TTI.getCastInstrCost(Opcode: Instruction::IntToPtr, Dst: DstTy, Src: IntVecTy, CCH,
203 CostKind) +
204 TTI.getCastInstrCost(Opcode: Instruction::BitCast, Dst: IntVecTy, Src: SrcTy, CCH,
205 CostKind);
206 }
207 Type *IntVecTy = DL.getIntPtrType(SrcTy);
208 return TTI.getCastInstrCost(Opcode: Instruction::PtrToInt, Dst: IntVecTy, Src: SrcTy, CCH,
209 CostKind) +
210 TTI.getCastInstrCost(Opcode: Instruction::BitCast, Dst: DstTy, Src: IntVecTy, CCH,
211 CostKind);
212}
213
214InstructionCost getMaskedDivRemCost(const TargetTransformInfo &TTI, bool ReVec,
215 unsigned Opcode, Type *ScalarTy,
216 unsigned NumElts,
217 const TTI::TargetCostKind CostKind,
218 FixedVectorType **PaddedTy) {
219 FixedVectorType *PaddedVecTy =
220 getMaskedDivRemType(TTI, Opcode, ScalarTy, NumElts, ReVec);
221 if (!PaddedVecTy)
222 return InstructionCost::getInvalid();
223 // One mask bit per element of the padded vector, not per padded lane.
224 auto *MaskTy =
225 FixedVectorType::get(ElementType: IntegerType::getInt1Ty(C&: ScalarTy->getContext()),
226 NumElts: PaddedVecTy->getNumElements());
227 InstructionCost DirectCost = TTI.getArithmeticInstrCost(
228 Opcode, Ty: getWidenedType(ScalarTy, VF: NumElts), CostKind);
229 IntrinsicCostAttributes ICA(getMaskedDivRemIntrinsic(Opcode), PaddedVecTy,
230 {PaddedVecTy, PaddedVecTy, MaskTy});
231 InstructionCost MaskedCost = TTI.getIntrinsicInstrCost(ICA, CostKind);
232 if (!MaskedCost.isValid() || MaskedCost >= DirectCost)
233 return InstructionCost::getInvalid();
234 if (PaddedTy)
235 *PaddedTy = PaddedVecTy;
236 return MaskedCost;
237}
238
239InstructionCost
240getScalarizationOverhead(const TargetTransformInfo &TTI, bool ReVec,
241 Type *ScalarTy, VectorType *Ty,
242 const APInt &DemandedElts, bool Insert, bool Extract,
243 const TTI::TargetCostKind CostKind, bool ForPoisonSrc,
244 ArrayRef<Value *> VL, TTI::VectorInstrContext VIC) {
245 assert(!isa<ScalableVectorType>(Ty) &&
246 "ScalableVectorType is not supported.");
247 assert(getNumElements(ScalarTy) * DemandedElts.getBitWidth() ==
248 getNumElements(Ty) &&
249 "Incorrect usage.");
250 if (auto *VecTy = dyn_cast<FixedVectorType>(Val: ScalarTy)) {
251 assert(ReVec && "Only supported by REVEC.");
252 // If ScalarTy is FixedVectorType, we should use CreateInsertVector instead
253 // of CreateInsertElement.
254 unsigned ScalarTyNumElements = VecTy->getNumElements();
255 InstructionCost Cost = 0;
256 for (unsigned I : seq(Size: DemandedElts.getBitWidth())) {
257 if (!DemandedElts[I])
258 continue;
259 if (Insert)
260 Cost += getShuffleCost(TTI, Kind: TTI::SK_InsertSubvector, Tp: Ty, CostKind, Mask: {},
261 Index: I * ScalarTyNumElements, SubTp: VecTy);
262 if (Extract)
263 Cost += getShuffleCost(TTI, Kind: TTI::SK_ExtractSubvector, Tp: Ty, CostKind, Mask: {},
264 Index: I * ScalarTyNumElements, SubTp: VecTy);
265 }
266 return Cost;
267 }
268 return TTI.getScalarizationOverhead(Ty, DemandedElts, Insert, Extract,
269 CostKind, ForPoisonSrc, VL, VIC);
270}
271
272InstructionCost getVectorInstrCost(
273 const TargetTransformInfo &TTI, bool ReVec, Type *ScalarTy, unsigned Opcode,
274 Type *Val, const TTI::TargetCostKind CostKind, unsigned Index,
275 Value *Scalar, ArrayRef<std::tuple<Value *, User *, int>> ScalarUserAndIdx,
276 TTI::VectorInstrContext VIC) {
277 if (Opcode == Instruction::ExtractElement) {
278 if (auto *VecTy = dyn_cast<FixedVectorType>(Val: ScalarTy)) {
279 assert(ReVec && "Only supported by REVEC.");
280 assert(isa<VectorType>(Val) && "Val must be a vector type.");
281 return getShuffleCost(TTI, Kind: TTI::SK_ExtractSubvector,
282 Tp: cast<VectorType>(Val), CostKind, Mask: {},
283 Index: Index * VecTy->getNumElements(), SubTp: VecTy);
284 }
285 }
286 return TTI.getVectorInstrCost(Opcode, Val, CostKind, Index, Scalar,
287 ScalarUserAndIdx, VIC);
288}
289
290InstructionCost getExtractWithExtendCost(const TargetTransformInfo &TTI,
291 bool ReVec, unsigned Opcode, Type *Dst,
292 VectorType *VecTy, unsigned Index,
293 const TTI::TargetCostKind CostKind) {
294 if (isVectorizedTy(Ty: Dst)) {
295 assert(ReVec && "Only supported by REVEC.");
296 auto *SubTp = cast<FixedVectorType>(
297 Val: getWidenedType(ScalarTy: toScalarizedTy(Ty: VecTy), VF: getNumElements(Ty: Dst)));
298 return getShuffleCost(TTI, Kind: TTI::SK_ExtractSubvector, Tp: VecTy, CostKind, Mask: {},
299 Index: Index * getNumElements(Ty: Dst), SubTp) +
300 TTI.getCastInstrCost(Opcode, Dst, Src: SubTp, CCH: TTI::CastContextHint::None,
301 CostKind);
302 }
303 return TTI.getExtractWithExtendCost(Opcode, Dst, VecTy, Index, CostKind);
304}
305
306/// Returns the cast context hint for the trunc of the booleanized reduction
307/// result, which inherits the uses of the reduction root \p Root.
308static TTI::CastContextHint getBoolReduxResultCCH(const Value *Root) {
309 if (!Root->hasOneUse())
310 return TTI::CastContextHint::None;
311 const Value *U = *Root->user_begin();
312 if (isa<StoreInst>(Val: U))
313 return TTI::CastContextHint::Normal;
314 if (match(V: U, P: m_Intrinsic<Intrinsic::masked_store>()))
315 return TTI::CastContextHint::Masked;
316 if (match(V: U, P: m_Intrinsic<Intrinsic::masked_scatter>()))
317 return TTI::CastContextHint::GatherScatter;
318 return TTI::CastContextHint::None;
319}
320
321InstructionCost getBoolReduxWideRdxCost(const TargetTransformInfo &TTI,
322 RecurKind RdxKind,
323 FixedVectorType *VecTy,
324 const Value *Root, FastMathFlags FMF,
325 const TTI::TargetCostKind CostKind) {
326 Type *I1Ty = Type::getInt1Ty(C&: VecTy->getContext());
327 return TTI.getArithmeticReductionCost(
328 Opcode: RecurrenceDescriptor::getOpcode(Kind: RdxKind), Ty: VecTy, FMF, CostKind) +
329 TTI.getCastInstrCost(Opcode: Instruction::Trunc, Dst: I1Ty, Src: VecTy->getScalarType(),
330 CCH: getBoolReduxResultCCH(Root), CostKind);
331}
332
333InstructionCost getBoolReduxBitcastCmpCost(const TargetTransformInfo &TTI,
334 RecurKind RdxKind,
335 FixedVectorType *VecTy,
336 const Value *Root,
337 ArrayRef<Instruction *> ChainInsts,
338 const TTI::TargetCostKind CostKind) {
339 // The new instructions are costed in the context of the replaced cast chain
340 // instructions.
341 auto TruncIt =
342 find_if(Range&: ChainInsts, P: [](Instruction *I) { return isa<TruncInst>(Val: I); });
343 const Instruction *TruncI = TruncIt == ChainInsts.end() ? nullptr : *TruncIt;
344 auto CmpIt =
345 find_if(Range&: ChainInsts, P: [](Instruction *I) { return isa<ICmpInst>(Val: I); });
346 const Instruction *CmpI = CmpIt == ChainInsts.end() ? nullptr : *CmpIt;
347 unsigned VF = VecTy->getNumElements();
348 auto *I1VecTy =
349 FixedVectorType::get(ElementType: Type::getInt1Ty(C&: VecTy->getContext()), NumElts: VF);
350 Type *IntTy = IntegerType::get(C&: VecTy->getContext(), NumBits: VF);
351 Constant *CmpRHS = RdxKind == RecurKind::And
352 ? Constant::getAllOnesValue(Ty: IntTy)
353 : Constant::getNullValue(Ty: IntTy);
354 return TTI.getCastInstrCost(Opcode: Instruction::Trunc, Dst: I1VecTy, Src: VecTy,
355 CCH: TTI.getCastContextHint(I: TruncI), CostKind,
356 I: TruncI) +
357 TTI.getCastInstrCost(Opcode: Instruction::BitCast, Dst: IntTy, Src: I1VecTy,
358 CCH: TTI.getCastContextHint(I: TruncI), CostKind) +
359 TTI.getCmpSelInstrCost(
360 Opcode: Instruction::ICmp, ValTy: IntTy, CondTy: CmpInst::makeCmpResultType(opnd_type: IntTy),
361 VecPred: RdxKind == RecurKind::And ? CmpInst::ICMP_EQ : CmpInst::ICMP_NE,
362 CostKind, Op1Info: TTI.getOperandInfo(V: Root), Op2Info: TTI.getOperandInfo(V: CmpRHS),
363 I: CmpI);
364}
365
366static InstructionCost
367getBoolLogicRdxBitcastCost(RecurKind Kind, const TargetTransformInfo &TTI,
368 FixedVectorType *VectorTy, TTI::CastContextHint Ctx,
369 TTI::TargetCostKind CostKind) {
370 assert((Kind == RecurKind::And || Kind == RecurKind::Or) &&
371 VectorTy->getElementType()->isIntegerTy(1) &&
372 "Expected and/or reduction of i1");
373 auto *IntTy =
374 IntegerType::get(C&: VectorTy->getContext(), NumBits: getNumElements(Ty: VectorTy));
375 CmpInst::Predicate Pred =
376 Kind == RecurKind::And ? CmpInst::ICMP_EQ : CmpInst::ICMP_NE;
377 // The compare is against the all-ones (and) or zero (or) constant.
378 return TTI.getCastInstrCost(Opcode: Instruction::BitCast, Dst: IntTy, Src: VectorTy, CCH: Ctx,
379 CostKind) +
380 TTI.getCmpSelInstrCost(Opcode: Instruction::ICmp, ValTy: IntTy,
381 CondTy: CmpInst::makeCmpResultType(opnd_type: IntTy), VecPred: Pred,
382 CostKind, /*Op1Info=*/{},
383 Op2Info: {.Kind: TTI::OK_UniformConstantValue, .Properties: TTI::OP_None});
384}
385
386std::pair<InstructionCost, bool>
387getI1ReductionCost(RecurKind Kind, const TargetTransformInfo &TTI,
388 FixedVectorType *VectorTy, Type *ScalarTy,
389 TTI::CastContextHint Ctx, TTI::TargetCostKind CostKind) {
390 unsigned RdxOpcode = RecurrenceDescriptor::getOpcode(Kind);
391 if (Kind == RecurKind::And || Kind == RecurKind::Or) {
392 InstructionCost RdxCost = TTI.getArithmeticReductionCost(
393 Opcode: RdxOpcode, Ty: VectorTy, FMF: std::nullopt, CostKind);
394 InstructionCost BitcastCost =
395 getBoolLogicRdxBitcastCost(Kind, TTI, VectorTy, Ctx, CostKind);
396 return {std::min(a: RdxCost, b: BitcastCost), BitcastCost < RdxCost};
397 }
398 assert(Kind == RecurKind::Add && !ScalarTy->isIntegerTy(1) &&
399 "Expected add reduction of zexted i1 values");
400 // The bitcast+ctpop form is estimated as the cheaper of the extended
401 // reduction cost, which models it for the zexted i1 add reduction, and the
402 // explicitly priced components, including the cast of the ctpop result to
403 // the destination type.
404 auto *IntTy =
405 IntegerType::get(C&: VectorTy->getContext(), NumBits: getNumElements(Ty: VectorTy));
406 InstructionCost ExplicitCost =
407 TTI.getCastInstrCost(Opcode: Instruction::BitCast, Dst: IntTy, Src: VectorTy, CCH: Ctx,
408 CostKind) +
409 TTI.getIntrinsicInstrCost(
410 ICA: IntrinsicCostAttributes(Intrinsic::ctpop, IntTy, {IntTy}), CostKind);
411 if (IntTy != ScalarTy)
412 ExplicitCost += TTI.getCastInstrCost(Opcode: IntTy->getBitWidth() <
413 ScalarTy->getIntegerBitWidth()
414 ? Instruction::ZExt
415 : Instruction::Trunc,
416 Dst: ScalarTy, Src: IntTy, CCH: Ctx, CostKind);
417 InstructionCost CtpopCost = std::min(
418 a: TTI.getExtendedReductionCost(Opcode: RdxOpcode, /*IsUnsigned=*/true, ResTy: ScalarTy,
419 Ty: VectorTy, FMF: std::nullopt, CostKind),
420 b: ExplicitCost);
421 // The plain form is the zext to the wide vector type plus the reduction.
422 auto *ExtTy = VectorType::get(ElementType: ScalarTy, Other: VectorTy);
423 InstructionCost ExtRdxCost =
424 TTI.getCastInstrCost(Opcode: Instruction::ZExt, Dst: ExtTy, Src: VectorTy, CCH: Ctx, CostKind) +
425 TTI.getArithmeticReductionCost(Opcode: RdxOpcode, Ty: ExtTy, FMF: std::nullopt, CostKind);
426 return {std::min(a: ExtRdxCost, b: CtpopCost), CtpopCost <= ExtRdxCost};
427}
428
429InstructionCost getBitPackCost(const TargetTransformInfo &TTI,
430 FixedVectorType *SrcTy, Type *ResultTy,
431 const BitPackInfo &Info, unsigned ZExtSrcWidth,
432 TTI::CastContextHint CCH,
433 TTI::TargetCostKind CostKind,
434 const TargetLibraryInfo *TLI,
435 const Instruction *CtxI, unsigned &ShiftWidth) {
436 unsigned BitWidth = SrcTy->getScalarSizeInBits();
437 unsigned NumElts = SrcTy->getNumElements();
438 uint64_t MaxAmt = *max_element(Range: Info.LShrAmts);
439 // The shift amounts form a constant vector.
440 TTI::OperandValueInfo ShiftAmtInfo = {
441 .Kind: all_equal(Range: Info.LShrAmts) ? TTI::OK_UniformConstantValue
442 : TTI::OK_NonUniformConstantValue,
443 .Properties: all_of(Range: Info.LShrAmts,
444 P: [](uint64_t A) { return A == 0 || isPowerOf2_64(Value: A); })
445 ? TTI::OP_PowerOf2
446 : TTI::OP_None};
447 // After the shift the field content of each lane sits in the low bits of
448 // the lane, so the packing is a single byte shuffle of the shifted lanes.
449 // Pick the cheapest shift width: the narrowest type still holding the field
450 // content is not always the cheapest (e.g. missing narrow variable shifts).
451 Type *Int8Ty = Type::getInt8Ty(C&: SrcTy->getContext());
452 assert(BitWidth % 8 == 0 &&
453 "The byte-multiple field width divides the result bit width.");
454 unsigned OutBytes = ResultTy->getScalarSizeInBits() / 8;
455 auto *PackTy = FixedVectorType::get(ElementType: Int8Ty, NumElts: OutBytes);
456 unsigned MinShiftWidth = 8;
457 while (MinShiftWidth < MaxAmt + Info.FieldWidth)
458 MinShiftWidth *= 2;
459 bool IsReversed = equal(LRange: Info.LaneOfField, RRange: reverse(C: seq<unsigned>(Size: NumElts)));
460 bool IsTrunc = IsReversed || equal(LRange: Info.LaneOfField, RRange: seq<unsigned>(Size: NumElts));
461 auto *FieldTy = FixedVectorType::get(
462 ElementType: IntegerType::get(C&: SrcTy->getContext(), NumBits: Info.FieldWidth), NumElts);
463 InstructionCost NewCost = InstructionCost::getInvalid();
464 ShiftWidth = 0;
465 for (unsigned W2 = MinShiftWidth; W2 <= BitWidth; W2 *= 2) {
466 auto *ShiftTy = FixedVectorType::get(
467 ElementType: IntegerType::get(C&: SrcTy->getContext(), NumBits: W2), NumElts);
468 unsigned BytesPerLane = W2 / 8;
469 unsigned InBytes = NumElts * BytesPerLane;
470 SmallVector<int> Mask =
471 getBitPackMask(Info, NumBytes: OutBytes, NumElts, BytesPerLane);
472 InstructionCost C = TTI.getCastInstrCost(Opcode: Instruction::BitCast, Dst: ResultTy,
473 Src: PackTy, CCH, CostKind);
474 if (IsTrunc) {
475 // Fields in lane order, possibly reversed, are a truncation of the
476 // shifted lanes. A reversal of byte fields is a bswap.
477 if (Info.FieldWidth < W2)
478 C += TTI.getCastInstrCost(Opcode: Instruction::Trunc, Dst: FieldTy, Src: ShiftTy,
479 CCH: TTI::CastContextHint::None, CostKind);
480 if (IsReversed && Info.FieldWidth == 8) {
481 IntrinsicCostAttributes CostAttrs(Intrinsic::bswap, ResultTy,
482 {ResultTy});
483 C += TTI.getIntrinsicInstrCost(ICA: CostAttrs, CostKind);
484 } else if (IsReversed) {
485 C += TTI.getShuffleCost(Kind: TargetTransformInfo::SK_Reverse, DstTy: FieldTy,
486 SrcTy: FieldTy, CostKind);
487 }
488 } else {
489 // A narrowing shuffle is a shuffle at the source width followed by an
490 // extract of the low elements.
491 auto *SrcByteTy = FixedVectorType::get(ElementType: Int8Ty, NumElts: InBytes);
492 SmallVector<int> WideMask(Mask);
493 WideMask.resize(N: std::max(a: InBytes, b: OutBytes), NV: PoisonMaskElem);
494 C += TTI.getShuffleCost(
495 Kind: is_contained(Range: Info.LaneOfField, Element: BitPackInfo::NoLane)
496 ? TargetTransformInfo::SK_PermuteTwoSrc
497 : TargetTransformInfo::SK_PermuteSingleSrc,
498 DstTy: FixedVectorType::get(ElementType: Int8Ty, NumElts: WideMask.size()), SrcTy: SrcByteTy, CostKind,
499 Mask: WideMask, /*Index=*/0, /*SubTp=*/nullptr, /*Args=*/{}, CtxI);
500 if (InBytes > OutBytes)
501 C += TTI.getShuffleCost(Kind: TargetTransformInfo::SK_ExtractSubvector,
502 DstTy: PackTy, SrcTy: SrcByteTy, CostKind, /*Mask=*/{},
503 /*Index=*/0, SubTp: PackTy, /*Args=*/{}, CtxI);
504 }
505 if (W2 != BitWidth && W2 != ZExtSrcWidth)
506 C += TTI.getCastInstrCost(Opcode: Instruction::Trunc, Dst: ShiftTy, Src: SrcTy, CCH,
507 CostKind);
508 if (Info.needsShift())
509 C += TTI.getArithmeticInstrCost(Opcode: Instruction::LShr, Ty: ShiftTy, CostKind,
510 /*Opd1Info=*/{}, Opd2Info: ShiftAmtInfo,
511 /*Args=*/{}, CtxI, TLibInfo: TLI);
512 if (C.isValid() && (!NewCost.isValid() || C < NewCost)) {
513 NewCost = C;
514 ShiftWidth = W2;
515 }
516 }
517 return NewCost;
518}
519
520InstructionCost getBoolBitmaskCost(const TargetTransformInfo &TTI,
521 bool NeedMask, Type *NarrowScalarTy,
522 Type *WideTy, unsigned VF,
523 ArrayRef<int> PermMask, const Value *Root,
524 const TTI::TargetCostKind CostKind) {
525 auto *NarrowVecTy = cast<VectorType>(Val: getWidenedType(ScalarTy: NarrowScalarTy, VF));
526 Type *CmpTy = CmpInst::makeCmpResultType(opnd_type: NarrowVecTy);
527 auto *MaskTy = IntegerType::get(C&: WideTy->getContext(), NumBits: VF);
528 // The result cast inherits the uses of the reduction root.
529 TTI::CastContextHint CCH = getBoolReduxResultCCH(Root);
530 const auto *CtxI = cast<Instruction>(Val: Root);
531 InstructionCost Cost = 0;
532 if (NeedMask)
533 Cost += TTI.getArithmeticInstrCost(
534 Opcode: Instruction::And, Ty: NarrowVecTy, CostKind,
535 Opd1Info: {.Kind: TTI::OK_AnyValue, .Properties: TTI::OP_None},
536 Opd2Info: {.Kind: TTI::OK_NonUniformConstantValue, .Properties: TTI::OP_None}, Args: {}, CtxI);
537 if (!ShuffleVectorInst::isIdentityMask(Mask: PermMask, NumSrcElts: VF))
538 Cost += getShuffleCost(TTI, Kind: TTI::SK_PermuteSingleSrc, Tp: NarrowVecTy, CostKind,
539 Mask: PermMask);
540 if (!NarrowScalarTy->isIntegerTy(BitWidth: 1))
541 Cost += TTI.getCmpSelInstrCost(
542 Opcode: Instruction::ICmp, ValTy: NarrowVecTy, CondTy: CmpTy, VecPred: CmpInst::ICMP_NE, CostKind,
543 Op1Info: {.Kind: TTI::OK_AnyValue, .Properties: TTI::OP_None},
544 Op2Info: {.Kind: TTI::OK_UniformConstantValue, .Properties: TTI::OP_None});
545 // Only the final cast inherits the uses of the reduction root.
546 Cost += TTI.getCastInstrCost(
547 Opcode: Instruction::BitCast, Dst: MaskTy, Src: CmpTy,
548 CCH: MaskTy == WideTy ? CCH : TTI::CastContextHint::None, CostKind);
549 if (MaskTy != WideTy)
550 Cost +=
551 TTI.getCastInstrCost(Opcode: Instruction::ZExt, Dst: WideTy, Src: MaskTy, CCH, CostKind);
552 return Cost;
553}
554
555InstructionCost getNarrowedLeafOpsCost(
556 const TargetTransformInfo &TTI,
557 const SmallDenseMap<Value *, NarrowedLeafInfo> &NarrowedLeafShifts,
558 VectorType *NarrowVecTy, VectorType *WideVecTy, const Instruction *CtxI,
559 const TTI::TargetCostKind CostKind) {
560 InstructionCost Cost = 0;
561 if (any_of(Range: NarrowedLeafShifts,
562 P: [](const auto &P) { return P.second.Shift != 0; }))
563 Cost += TTI.getArithmeticInstrCost(
564 Opcode: Instruction::Shl, Ty: WideVecTy, CostKind, Opd1Info: {.Kind: TTI::OK_AnyValue, .Properties: TTI::OP_None},
565 Opd2Info: {.Kind: TTI::OK_NonUniformConstantValue, .Properties: TTI::OP_None}, Args: {}, CtxI);
566 if (any_of(Range: NarrowedLeafShifts,
567 P: [](const auto &P) { return !P.second.Mask.isAllOnes(); }))
568 Cost += TTI.getArithmeticInstrCost(
569 Opcode: Instruction::And, Ty: NarrowVecTy, CostKind,
570 Opd1Info: {.Kind: TTI::OK_AnyValue, .Properties: TTI::OP_None},
571 Opd2Info: {.Kind: TTI::OK_NonUniformConstantValue, .Properties: TTI::OP_None}, Args: {}, CtxI);
572 return Cost;
573}
574} // namespace llvm::slpvectorizer
575