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/SmallPtrSet.h"
17#include "llvm/ADT/SmallVector.h"
18#include "llvm/Analysis/IVDescriptors.h"
19#include "llvm/Analysis/VectorUtils.h"
20#include "llvm/IR/BasicBlock.h"
21#include "llvm/IR/DataLayout.h"
22#include "llvm/IR/DerivedTypes.h"
23#include "llvm/IR/Instructions.h"
24#include "llvm/IR/Intrinsics.h"
25#include "llvm/IR/Operator.h"
26#include "llvm/IR/PatternMatch.h"
27#include "llvm/IR/Type.h"
28#include "llvm/IR/Value.h"
29#include "llvm/IR/VectorTypeUtils.h"
30#include "llvm/Support/Casting.h"
31#include "llvm/Support/MathExtras.h"
32
33#include <cassert>
34#include <utility>
35
36using namespace llvm;
37using namespace llvm::PatternMatch;
38
39namespace llvm::slpvectorizer {
40
41InstructionCost getShuffleCost(const TargetTransformInfo &TTI,
42 TTI::ShuffleKind Kind, VectorType *Tp,
43 const TTI::TargetCostKind CostKind,
44 ArrayRef<int> Mask, int Index, VectorType *SubTp,
45 ArrayRef<const Value *> Args,
46 TTI::VectorInstrContext VIC) {
47 VectorType *DstTy = Tp;
48 if (!Mask.empty())
49 DstTy = FixedVectorType::get(ElementType: Tp->getScalarType(), NumElts: Mask.size());
50
51 if (Kind != TTI::SK_PermuteTwoSrc)
52 return TTI.getShuffleCost(Kind, DstTy, SrcTy: Tp, CostKind, Mask, Index, SubTp,
53 Args, /*CtxI=*/nullptr, VIC);
54 int NumSrcElts = Tp->getElementCount().getKnownMinValue();
55 int NumSubElts;
56 if (Mask.size() > 2 && ShuffleVectorInst::isInsertSubvectorMask(
57 Mask, NumSrcElts, NumSubElts, Index)) {
58 if (Index + NumSubElts > NumSrcElts &&
59 Index + NumSrcElts <= static_cast<int>(Mask.size()))
60 return TTI.getShuffleCost(Kind: TTI::SK_InsertSubvector, DstTy, SrcTy: Tp, CostKind,
61 Mask, Index, SubTp: Tp);
62 }
63 return TTI.getShuffleCost(Kind, DstTy, SrcTy: Tp, CostKind, Mask, Index, SubTp, Args,
64 /*CtxI=*/nullptr, VIC);
65}
66
67std::pair<InstructionCost, InstructionCost>
68getGEPCosts(const TargetTransformInfo &TTI, ArrayRef<Value *> Ptrs,
69 Value *BasePtr, unsigned Opcode, const TTI::TargetCostKind CostKind,
70 Type *ScalarTy, VectorType *VecTy) {
71 InstructionCost ScalarCost = 0;
72 InstructionCost VecCost = 0;
73 // Here we differentiate two cases: (1) when Ptrs represent a regular
74 // vectorization tree node (as they are pointer arguments of scattered
75 // loads) or (2) when Ptrs are the arguments of loads or stores being
76 // vectorized as plane wide unit-stride load/store since all the
77 // loads/stores are known to be from/to adjacent locations.
78 if (Opcode == Instruction::Load || Opcode == Instruction::Store) {
79 // Case 2: estimate costs for pointer related costs when vectorizing to
80 // a wide load/store.
81 // Scalar cost is estimated as a set of pointers with known relationship
82 // between them.
83 // For vector code we will use BasePtr as argument for the wide load/store
84 // but we also need to account all the instructions which are going to
85 // stay in vectorized code due to uses outside of these scalar
86 // loads/stores.
87 ScalarCost = TTI.getPointersChainCost(
88 Ptrs, Base: BasePtr, Info: TTI::PointersChainInfo::getUnitStride(), AccessTy: ScalarTy,
89 CostKind);
90
91 SmallVector<const Value *> PtrsRetainedInVecCode;
92 for (Value *V : Ptrs) {
93 if (V == BasePtr) {
94 PtrsRetainedInVecCode.push_back(Elt: V);
95 continue;
96 }
97 auto *Ptr = dyn_cast<GetElementPtrInst>(Val: V);
98 // For simplicity assume Ptr to stay in vectorized code if it's not a
99 // GEP instruction. We don't care since it's cost considered free.
100 // TODO: We should check for any uses outside of vectorizable tree
101 // rather than just single use.
102 if (!Ptr || !Ptr->hasOneUse())
103 PtrsRetainedInVecCode.push_back(Elt: V);
104 }
105
106 if (PtrsRetainedInVecCode.size() == Ptrs.size()) {
107 // If all pointers stay in vectorized code then we don't have
108 // any savings on that.
109 return std::make_pair(x: TTI::TCC_Free, y: TTI::TCC_Free);
110 }
111 VecCost = TTI.getPointersChainCost(Ptrs: PtrsRetainedInVecCode, Base: BasePtr,
112 Info: TTI::PointersChainInfo::getKnownStride(),
113 AccessTy: VecTy, CostKind);
114 } else {
115 // Case 1: Ptrs are the arguments of loads that we are going to transform
116 // into masked gather load intrinsic.
117 // All the scalar GEPs will be removed as a result of vectorization.
118 // For any external uses of some lanes extract element instructions will
119 // be generated (which cost is estimated separately).
120 TTI::PointersChainInfo PtrsInfo =
121 all_of(Range&: Ptrs,
122 P: [](const Value *V) {
123 auto *Ptr = dyn_cast<GetElementPtrInst>(Val: V);
124 return Ptr && !Ptr->hasAllConstantIndices();
125 })
126 ? TTI::PointersChainInfo::getUnknownStride()
127 : TTI::PointersChainInfo::getKnownStride();
128
129 const bool IsSameBase =
130 !all_of(Range&: Ptrs, P: IsaPred<GetElementPtrInst>) ||
131 all_equal(Range: map_range(C&: Ptrs, F: [](Value *V) {
132 return cast<GetElementPtrInst>(Val: V)->getPointerOperand();
133 }));
134 // The GEPs of the masked gather loads are accessed with the loaded type
135 // and form a chain only if the lanes share the base.
136 Type *AccessTy = ScalarTy;
137 if (all_of(Range&: Ptrs, P: [](const Value *V) {
138 auto *Ptr = dyn_cast<GetElementPtrInst>(Val: V);
139 return Ptr && Ptr->hasOneUse() && isa<LoadInst>(Val: Ptr->user_back());
140 })) {
141 PtrsInfo.IsSameBaseAddress = IsSameBase;
142 AccessTy = Ptrs.front()->user_back()->getType();
143 }
144 ScalarCost =
145 TTI.getPointersChainCost(Ptrs, Base: BasePtr, Info: PtrsInfo, AccessTy, CostKind);
146 auto *BaseGEP = dyn_cast<GEPOperator>(Val: BasePtr);
147 if (!BaseGEP) {
148 auto *It = find_if(Range&: Ptrs, P: IsaPred<GEPOperator>);
149 if (It != Ptrs.end())
150 BaseGEP = cast<GEPOperator>(Val: *It);
151 }
152 if (!IsSameBase) {
153 // The different bases are not folded into the addressing of the vector
154 // access, the scaled indices are added to them.
155 const DataLayout &DL = cast<Instruction>(Val: Ptrs.front())->getDataLayout();
156 Type *IdxTy = DL.getIndexType(PtrTy: VecTy);
157 VecCost = TTI.getArithmeticInstrCost(Opcode: Instruction::Add, Ty: IdxTy, CostKind);
158 uint64_t Stride = DL.getTypeAllocSize(Ty: BaseGEP->getSourceElementType())
159 .getKnownMinValue();
160 if (Stride != 1 && !all_of(Range&: Ptrs, P: [](Value *V) {
161 return isa<Constant>(Val: cast<GetElementPtrInst>(Val: V)->getOperand(i_nocapture: 1));
162 }))
163 VecCost += TTI.getArithmeticInstrCost(
164 Opcode: isPowerOf2_64(Value: Stride) ? Instruction::Shl : Instruction::Mul, Ty: IdxTy,
165 CostKind, Opd1Info: {}, Opd2Info: {.Kind: TTI::OK_UniformConstantValue, .Properties: TTI::OP_None});
166 } else if (BaseGEP) {
167 SmallVector<const Value *> Indices(BaseGEP->indices());
168 VecCost = TTI.getGEPCost(PointeeType: BaseGEP->getSourceElementType(),
169 Ptr: BaseGEP->getPointerOperand(), Operands: Indices, CostKind,
170 AccessType: VecTy);
171 }
172 }
173
174 return std::make_pair(x&: ScalarCost, y&: VecCost);
175}
176
177InstructionCost getBlendedLoadCost(const TargetTransformInfo &TTI, Type *VecTy,
178 Align Alignment, unsigned AddressSpace,
179 const TTI::TargetCostKind CostKind) {
180 Type *CmpTy = CmpInst::makeCmpResultType(opnd_type: VecTy);
181 return 2 * TTI.getMemIntrinsicInstrCost(
182 MICA: MemIntrinsicCostAttributes(Intrinsic::masked_load, VecTy,
183 Alignment, AddressSpace),
184 CostKind) +
185 TTI.getArithmeticInstrCost(Opcode: Instruction::Xor, Ty: CmpTy, CostKind) +
186 TTI.getCmpSelInstrCost(Opcode: Instruction::Select, ValTy: VecTy, CondTy: CmpTy,
187 VecPred: CmpInst::BAD_ICMP_PREDICATE, CostKind);
188}
189
190InstructionCost getWidenedStridedCastCost(const TargetTransformInfo &TTI,
191 Type *SrcTy, Type *DstTy,
192 const DataLayout &DL,
193 TTI::CastContextHint CCH,
194 TTI::TargetCostKind CostKind) {
195 bool ToPtr = cast<VectorType>(Val: DstTy)->getElementType()->isPointerTy();
196 if (ToPtr == cast<VectorType>(Val: SrcTy)->getElementType()->isPointerTy())
197 return TTI.getCastInstrCost(Opcode: Instruction::BitCast, Dst: DstTy, Src: SrcTy, CCH,
198 CostKind);
199 // The ptr/int conversion keeps the vector shape, the bitcast transforms the
200 // resulting integer vector.
201 if (ToPtr) {
202 Type *IntVecTy = DL.getIntPtrType(DstTy);
203 return TTI.getCastInstrCost(Opcode: Instruction::IntToPtr, Dst: DstTy, Src: IntVecTy, CCH,
204 CostKind) +
205 TTI.getCastInstrCost(Opcode: Instruction::BitCast, Dst: IntVecTy, Src: SrcTy, CCH,
206 CostKind);
207 }
208 Type *IntVecTy = DL.getIntPtrType(SrcTy);
209 return TTI.getCastInstrCost(Opcode: Instruction::PtrToInt, Dst: IntVecTy, Src: SrcTy, CCH,
210 CostKind) +
211 TTI.getCastInstrCost(Opcode: Instruction::BitCast, Dst: DstTy, Src: IntVecTy, CCH,
212 CostKind);
213}
214
215InstructionCost getMaskedDivRemCost(const TargetTransformInfo &TTI, bool ReVec,
216 unsigned Opcode, Type *ScalarTy,
217 unsigned NumElts,
218 const TTI::TargetCostKind CostKind,
219 FixedVectorType **PaddedTy) {
220 FixedVectorType *PaddedVecTy =
221 getMaskedDivRemType(TTI, Opcode, ScalarTy, NumElts, ReVec);
222 if (!PaddedVecTy)
223 return InstructionCost::getInvalid();
224 // One mask bit per element of the padded vector, not per padded lane.
225 auto *MaskTy =
226 FixedVectorType::get(ElementType: IntegerType::getInt1Ty(C&: ScalarTy->getContext()),
227 NumElts: PaddedVecTy->getNumElements());
228 InstructionCost DirectCost = TTI.getArithmeticInstrCost(
229 Opcode, Ty: getWidenedType(ScalarTy, VF: NumElts), CostKind);
230 IntrinsicCostAttributes ICA(getMaskedDivRemIntrinsic(Opcode), PaddedVecTy,
231 {PaddedVecTy, PaddedVecTy, MaskTy});
232 InstructionCost MaskedCost = TTI.getIntrinsicInstrCost(ICA, CostKind);
233 if (!MaskedCost.isValid() || MaskedCost >= DirectCost)
234 return InstructionCost::getInvalid();
235 if (PaddedTy)
236 *PaddedTy = PaddedVecTy;
237 return MaskedCost;
238}
239
240InstructionCost
241getScalarizationOverhead(const TargetTransformInfo &TTI, bool ReVec,
242 Type *ScalarTy, VectorType *Ty,
243 const APInt &DemandedElts, bool Insert, bool Extract,
244 const TTI::TargetCostKind CostKind, bool ForPoisonSrc,
245 ArrayRef<Value *> VL, TTI::VectorInstrContext VIC) {
246 assert(!isa<ScalableVectorType>(Ty) &&
247 "ScalableVectorType is not supported.");
248 assert(getNumElements(ScalarTy) * DemandedElts.getBitWidth() ==
249 getNumElements(Ty) &&
250 "Incorrect usage.");
251 if (auto *VecTy = dyn_cast<FixedVectorType>(Val: ScalarTy)) {
252 assert(ReVec && "Only supported by REVEC.");
253 // If ScalarTy is FixedVectorType, we should use CreateInsertVector instead
254 // of CreateInsertElement.
255 unsigned ScalarTyNumElements = VecTy->getNumElements();
256 InstructionCost Cost = 0;
257 for (unsigned I : seq(Size: DemandedElts.getBitWidth())) {
258 if (!DemandedElts[I])
259 continue;
260 if (Insert)
261 Cost += getShuffleCost(TTI, Kind: TTI::SK_InsertSubvector, Tp: Ty, CostKind, Mask: {},
262 Index: I * ScalarTyNumElements, SubTp: VecTy);
263 if (Extract)
264 Cost += getShuffleCost(TTI, Kind: TTI::SK_ExtractSubvector, Tp: Ty, CostKind, Mask: {},
265 Index: I * ScalarTyNumElements, SubTp: VecTy);
266 }
267 return Cost;
268 }
269 return TTI.getScalarizationOverhead(Ty, DemandedElts, Insert, Extract,
270 CostKind, ForPoisonSrc, VL, VIC);
271}
272
273InstructionCost getVectorInstrCost(
274 const TargetTransformInfo &TTI, bool ReVec, Type *ScalarTy, unsigned Opcode,
275 Type *Val, const TTI::TargetCostKind CostKind, unsigned Index,
276 Value *Scalar, ArrayRef<std::tuple<Value *, User *, int>> ScalarUserAndIdx,
277 TTI::VectorInstrContext VIC) {
278 if (Opcode == Instruction::ExtractElement) {
279 if (auto *VecTy = dyn_cast<FixedVectorType>(Val: ScalarTy)) {
280 assert(ReVec && "Only supported by REVEC.");
281 assert(isa<VectorType>(Val) && "Val must be a vector type.");
282 return getShuffleCost(TTI, Kind: TTI::SK_ExtractSubvector,
283 Tp: cast<VectorType>(Val), CostKind, Mask: {},
284 Index: Index * VecTy->getNumElements(), SubTp: VecTy);
285 }
286 }
287 return TTI.getVectorInstrCost(Opcode, Val, CostKind, Index, Scalar,
288 ScalarUserAndIdx, VIC);
289}
290
291InstructionCost getExtractWithExtendCost(const TargetTransformInfo &TTI,
292 bool ReVec, unsigned Opcode, Type *Dst,
293 VectorType *VecTy, unsigned Index,
294 const TTI::TargetCostKind CostKind) {
295 if (isVectorizedTy(Ty: Dst)) {
296 assert(ReVec && "Only supported by REVEC.");
297 auto *SubTp = cast<FixedVectorType>(
298 Val: getWidenedType(ScalarTy: toScalarizedTy(Ty: VecTy), VF: getNumElements(Ty: Dst)));
299 return getShuffleCost(TTI, Kind: TTI::SK_ExtractSubvector, Tp: VecTy, CostKind, Mask: {},
300 Index: Index * getNumElements(Ty: Dst), SubTp) +
301 TTI.getCastInstrCost(Opcode, Dst, Src: SubTp, CCH: TTI::CastContextHint::None,
302 CostKind);
303 }
304 return TTI.getExtractWithExtendCost(Opcode, Dst, VecTy, Index, CostKind);
305}
306
307/// Returns the cast context hint for the trunc of the booleanized reduction
308/// result, which inherits the uses of the reduction root \p Root.
309static TTI::CastContextHint getBoolReduxResultCCH(const Value *Root) {
310 if (!Root->hasOneUse())
311 return TTI::CastContextHint::None;
312 const Value *U = *Root->user_begin();
313 if (isa<StoreInst>(Val: U))
314 return TTI::CastContextHint::Normal;
315 if (match(V: U, P: m_Intrinsic<Intrinsic::masked_store>()))
316 return TTI::CastContextHint::Masked;
317 if (match(V: U, P: m_Intrinsic<Intrinsic::masked_scatter>()))
318 return TTI::CastContextHint::GatherScatter;
319 return TTI::CastContextHint::None;
320}
321
322InstructionCost getBoolReduxWideRdxCost(const TargetTransformInfo &TTI,
323 RecurKind RdxKind,
324 FixedVectorType *VecTy,
325 const Value *Root, FastMathFlags FMF,
326 const TTI::TargetCostKind CostKind) {
327 Type *I1Ty = Type::getInt1Ty(C&: VecTy->getContext());
328 return TTI.getArithmeticReductionCost(
329 Opcode: RecurrenceDescriptor::getOpcode(Kind: RdxKind), Ty: VecTy, FMF, CostKind) +
330 TTI.getCastInstrCost(Opcode: Instruction::Trunc, Dst: I1Ty, Src: VecTy->getScalarType(),
331 CCH: getBoolReduxResultCCH(Root), CostKind);
332}
333
334InstructionCost getBoolReduxBitcastCmpCost(const TargetTransformInfo &TTI,
335 RecurKind RdxKind,
336 FixedVectorType *VecTy,
337 const Value *Root,
338 ArrayRef<Instruction *> ChainInsts,
339 const TTI::TargetCostKind CostKind) {
340 // The new instructions are costed in the context of the replaced cast chain
341 // instructions.
342 auto TruncIt =
343 find_if(Range&: ChainInsts, P: [](Instruction *I) { return isa<TruncInst>(Val: I); });
344 const Instruction *TruncI = TruncIt == ChainInsts.end() ? nullptr : *TruncIt;
345 auto CmpIt =
346 find_if(Range&: ChainInsts, P: [](Instruction *I) { return isa<ICmpInst>(Val: I); });
347 const Instruction *CmpI = CmpIt == ChainInsts.end() ? nullptr : *CmpIt;
348 unsigned VF = VecTy->getNumElements();
349 auto *I1VecTy =
350 FixedVectorType::get(ElementType: Type::getInt1Ty(C&: VecTy->getContext()), NumElts: VF);
351 Type *IntTy = IntegerType::get(C&: VecTy->getContext(), NumBits: VF);
352 Constant *CmpRHS = RdxKind == RecurKind::And
353 ? Constant::getAllOnesValue(Ty: IntTy)
354 : Constant::getNullValue(Ty: IntTy);
355 return TTI.getCastInstrCost(Opcode: Instruction::Trunc, Dst: I1VecTy, Src: VecTy,
356 CCH: TTI.getCastContextHint(I: TruncI), CostKind,
357 I: TruncI) +
358 TTI.getCastInstrCost(Opcode: Instruction::BitCast, Dst: IntTy, Src: I1VecTy,
359 CCH: TTI.getCastContextHint(I: TruncI), CostKind) +
360 TTI.getCmpSelInstrCost(
361 Opcode: Instruction::ICmp, ValTy: IntTy, CondTy: CmpInst::makeCmpResultType(opnd_type: IntTy),
362 VecPred: RdxKind == RecurKind::And ? CmpInst::ICMP_EQ : CmpInst::ICMP_NE,
363 CostKind, Op1Info: TTI.getOperandInfo(V: Root), Op2Info: TTI.getOperandInfo(V: CmpRHS),
364 I: CmpI);
365}
366
367static InstructionCost
368getBoolLogicRdxBitcastCost(RecurKind Kind, const TargetTransformInfo &TTI,
369 FixedVectorType *VectorTy, TTI::CastContextHint Ctx,
370 TTI::TargetCostKind CostKind) {
371 assert((Kind == RecurKind::And || Kind == RecurKind::Or) &&
372 VectorTy->getElementType()->isIntegerTy(1) &&
373 "Expected and/or reduction of i1");
374 auto *IntTy =
375 IntegerType::get(C&: VectorTy->getContext(), NumBits: getNumElements(Ty: VectorTy));
376 CmpInst::Predicate Pred =
377 Kind == RecurKind::And ? CmpInst::ICMP_EQ : CmpInst::ICMP_NE;
378 // The compare is against the all-ones (and) or zero (or) constant.
379 return TTI.getCastInstrCost(Opcode: Instruction::BitCast, Dst: IntTy, Src: VectorTy, CCH: Ctx,
380 CostKind) +
381 TTI.getCmpSelInstrCost(Opcode: Instruction::ICmp, ValTy: IntTy,
382 CondTy: CmpInst::makeCmpResultType(opnd_type: IntTy), VecPred: Pred,
383 CostKind, /*Op1Info=*/{},
384 Op2Info: {.Kind: TTI::OK_UniformConstantValue, .Properties: TTI::OP_None});
385}
386
387std::pair<InstructionCost, bool>
388getI1ReductionCost(RecurKind Kind, const TargetTransformInfo &TTI,
389 FixedVectorType *VectorTy, Type *ScalarTy,
390 TTI::CastContextHint Ctx, TTI::TargetCostKind CostKind) {
391 unsigned RdxOpcode = RecurrenceDescriptor::getOpcode(Kind);
392 if (Kind == RecurKind::And || Kind == RecurKind::Or) {
393 InstructionCost RdxCost = TTI.getArithmeticReductionCost(
394 Opcode: RdxOpcode, Ty: VectorTy, FMF: std::nullopt, CostKind);
395 InstructionCost BitcastCost =
396 getBoolLogicRdxBitcastCost(Kind, TTI, VectorTy, Ctx, CostKind);
397 return {std::min(a: RdxCost, b: BitcastCost), BitcastCost < RdxCost};
398 }
399 assert(Kind == RecurKind::Add && !ScalarTy->isIntegerTy(1) &&
400 "Expected add reduction of zexted i1 values");
401 // The bitcast+ctpop form is estimated as the cheaper of the extended
402 // reduction cost, which models it for the zexted i1 add reduction, and the
403 // explicitly priced components, including the cast of the ctpop result to
404 // the destination type.
405 auto *IntTy =
406 IntegerType::get(C&: VectorTy->getContext(), NumBits: getNumElements(Ty: VectorTy));
407 InstructionCost ExplicitCost =
408 TTI.getCastInstrCost(Opcode: Instruction::BitCast, Dst: IntTy, Src: VectorTy, CCH: Ctx,
409 CostKind) +
410 TTI.getIntrinsicInstrCost(
411 ICA: IntrinsicCostAttributes(Intrinsic::ctpop, IntTy, {IntTy}), CostKind);
412 if (IntTy != ScalarTy)
413 ExplicitCost += TTI.getCastInstrCost(Opcode: IntTy->getBitWidth() <
414 ScalarTy->getIntegerBitWidth()
415 ? Instruction::ZExt
416 : Instruction::Trunc,
417 Dst: ScalarTy, Src: IntTy, CCH: Ctx, CostKind);
418 InstructionCost CtpopCost = std::min(
419 a: TTI.getExtendedReductionCost(Opcode: RdxOpcode, /*IsUnsigned=*/true, ResTy: ScalarTy,
420 Ty: VectorTy, FMF: std::nullopt, CostKind),
421 b: ExplicitCost);
422 // The plain form is the zext to the wide vector type plus the reduction.
423 auto *ExtTy = VectorType::get(ElementType: ScalarTy, Other: VectorTy);
424 InstructionCost ExtRdxCost =
425 TTI.getCastInstrCost(Opcode: Instruction::ZExt, Dst: ExtTy, Src: VectorTy, CCH: Ctx, CostKind) +
426 TTI.getArithmeticReductionCost(Opcode: RdxOpcode, Ty: ExtTy, FMF: std::nullopt, CostKind);
427 return {std::min(a: ExtRdxCost, b: CtpopCost), CtpopCost <= ExtRdxCost};
428}
429
430InstructionCost getBitPackCost(const TargetTransformInfo &TTI,
431 FixedVectorType *SrcTy, Type *ResultTy,
432 const BitPackInfo &Info, unsigned ZExtSrcWidth,
433 TTI::CastContextHint CCH,
434 TTI::TargetCostKind CostKind,
435 const TargetLibraryInfo *TLI,
436 const Instruction *CtxI, unsigned &ShiftWidth) {
437 unsigned BitWidth = SrcTy->getScalarSizeInBits();
438 unsigned NumElts = SrcTy->getNumElements();
439 uint64_t MaxAmt = *max_element(Range: Info.LShrAmts);
440 // The shift amounts form a constant vector.
441 TTI::OperandValueInfo ShiftAmtInfo = {
442 .Kind: all_equal(Range: Info.LShrAmts) ? TTI::OK_UniformConstantValue
443 : TTI::OK_NonUniformConstantValue,
444 .Properties: all_of(Range: Info.LShrAmts,
445 P: [](uint64_t A) { return A == 0 || isPowerOf2_64(Value: A); })
446 ? TTI::OP_PowerOf2
447 : TTI::OP_None};
448 // After the shift the field content of each lane sits in the low bits of
449 // the lane, so the packing is a single byte shuffle of the shifted lanes.
450 // Pick the cheapest shift width: the narrowest type still holding the field
451 // content is not always the cheapest (e.g. missing narrow variable shifts).
452 Type *Int8Ty = Type::getInt8Ty(C&: SrcTy->getContext());
453 assert(BitWidth % 8 == 0 &&
454 "The byte-multiple field width divides the result bit width.");
455 unsigned OutBytes = ResultTy->getScalarSizeInBits() / 8;
456 auto *PackTy = FixedVectorType::get(ElementType: Int8Ty, NumElts: OutBytes);
457 unsigned MinShiftWidth = 8;
458 while (MinShiftWidth < MaxAmt + Info.FieldWidth)
459 MinShiftWidth *= 2;
460 bool IsReversed = equal(LRange: Info.LaneOfField, RRange: reverse(C: seq<unsigned>(Size: NumElts)));
461 bool IsTrunc = IsReversed || equal(LRange: Info.LaneOfField, RRange: seq<unsigned>(Size: NumElts));
462 auto *FieldTy = FixedVectorType::get(
463 ElementType: IntegerType::get(C&: SrcTy->getContext(), NumBits: Info.FieldWidth), NumElts);
464 InstructionCost NewCost = InstructionCost::getInvalid();
465 ShiftWidth = 0;
466 for (unsigned W2 = MinShiftWidth; W2 <= BitWidth; W2 *= 2) {
467 auto *ShiftTy = FixedVectorType::get(
468 ElementType: IntegerType::get(C&: SrcTy->getContext(), NumBits: W2), NumElts);
469 unsigned BytesPerLane = W2 / 8;
470 unsigned InBytes = NumElts * BytesPerLane;
471 SmallVector<int> Mask =
472 getBitPackMask(Info, NumBytes: OutBytes, NumElts, BytesPerLane);
473 InstructionCost C = TTI.getCastInstrCost(Opcode: Instruction::BitCast, Dst: ResultTy,
474 Src: PackTy, CCH, CostKind);
475 if (IsTrunc) {
476 // Fields in lane order, possibly reversed, are a truncation of the
477 // shifted lanes. A reversal of byte fields is a bswap.
478 if (Info.FieldWidth < W2)
479 C += TTI.getCastInstrCost(Opcode: Instruction::Trunc, Dst: FieldTy, Src: ShiftTy,
480 CCH: TTI::CastContextHint::None, CostKind);
481 if (IsReversed && Info.FieldWidth == 8) {
482 IntrinsicCostAttributes CostAttrs(Intrinsic::bswap, ResultTy,
483 {ResultTy});
484 C += TTI.getIntrinsicInstrCost(ICA: CostAttrs, CostKind);
485 } else if (IsReversed) {
486 C += TTI.getShuffleCost(Kind: TargetTransformInfo::SK_Reverse, DstTy: FieldTy,
487 SrcTy: FieldTy, CostKind);
488 }
489 } else {
490 // A narrowing shuffle is a shuffle at the source width followed by an
491 // extract of the low elements.
492 auto *SrcByteTy = FixedVectorType::get(ElementType: Int8Ty, NumElts: InBytes);
493 SmallVector<int> WideMask(Mask);
494 WideMask.resize(N: std::max(a: InBytes, b: OutBytes), NV: PoisonMaskElem);
495 C += TTI.getShuffleCost(
496 Kind: is_contained(Range: Info.LaneOfField, Element: BitPackInfo::NoLane)
497 ? TargetTransformInfo::SK_PermuteTwoSrc
498 : TargetTransformInfo::SK_PermuteSingleSrc,
499 DstTy: FixedVectorType::get(ElementType: Int8Ty, NumElts: WideMask.size()), SrcTy: SrcByteTy, CostKind,
500 Mask: WideMask, /*Index=*/0, /*SubTp=*/nullptr, /*Args=*/{}, CtxI);
501 if (InBytes > OutBytes)
502 C += TTI.getShuffleCost(Kind: TargetTransformInfo::SK_ExtractSubvector,
503 DstTy: PackTy, SrcTy: SrcByteTy, CostKind, /*Mask=*/{},
504 /*Index=*/0, SubTp: PackTy, /*Args=*/{}, CtxI);
505 }
506 if (W2 != BitWidth && W2 != ZExtSrcWidth)
507 C += TTI.getCastInstrCost(Opcode: Instruction::Trunc, Dst: ShiftTy, Src: SrcTy, CCH,
508 CostKind);
509 if (Info.needsShift())
510 C += TTI.getArithmeticInstrCost(Opcode: Instruction::LShr, Ty: ShiftTy, CostKind,
511 /*Opd1Info=*/{}, Opd2Info: ShiftAmtInfo,
512 /*Args=*/{}, CtxI, TLibInfo: TLI);
513 if (C.isValid() && (!NewCost.isValid() || C < NewCost)) {
514 NewCost = C;
515 ShiftWidth = W2;
516 }
517 }
518 return NewCost;
519}
520
521InstructionCost getBoolBitmaskCost(const TargetTransformInfo &TTI,
522 bool NeedMask, Type *NarrowScalarTy,
523 Type *WideTy, unsigned VF,
524 ArrayRef<int> PermMask, const Value *Root,
525 const TTI::TargetCostKind CostKind) {
526 auto *NarrowVecTy = cast<VectorType>(Val: getWidenedType(ScalarTy: NarrowScalarTy, VF));
527 Type *CmpTy = CmpInst::makeCmpResultType(opnd_type: NarrowVecTy);
528 auto *MaskTy = IntegerType::get(C&: WideTy->getContext(), NumBits: VF);
529 // The result cast inherits the uses of the reduction root.
530 TTI::CastContextHint CCH = getBoolReduxResultCCH(Root);
531 const auto *CtxI = cast<Instruction>(Val: Root);
532 InstructionCost Cost = 0;
533 if (NeedMask)
534 Cost += TTI.getArithmeticInstrCost(
535 Opcode: Instruction::And, Ty: NarrowVecTy, CostKind,
536 Opd1Info: {.Kind: TTI::OK_AnyValue, .Properties: TTI::OP_None},
537 Opd2Info: {.Kind: TTI::OK_NonUniformConstantValue, .Properties: TTI::OP_None}, Args: {}, CtxI);
538 if (!ShuffleVectorInst::isIdentityMask(Mask: PermMask, NumSrcElts: VF))
539 Cost += getShuffleCost(TTI, Kind: TTI::SK_PermuteSingleSrc, Tp: NarrowVecTy, CostKind,
540 Mask: PermMask);
541 if (!NarrowScalarTy->isIntegerTy(BitWidth: 1))
542 Cost += TTI.getCmpSelInstrCost(
543 Opcode: Instruction::ICmp, ValTy: NarrowVecTy, CondTy: CmpTy, VecPred: CmpInst::ICMP_NE, CostKind,
544 Op1Info: {.Kind: TTI::OK_AnyValue, .Properties: TTI::OP_None},
545 Op2Info: {.Kind: TTI::OK_UniformConstantValue, .Properties: TTI::OP_None});
546 // Only the final cast inherits the uses of the reduction root.
547 Cost += TTI.getCastInstrCost(
548 Opcode: Instruction::BitCast, Dst: MaskTy, Src: CmpTy,
549 CCH: MaskTy == WideTy ? CCH : TTI::CastContextHint::None, CostKind);
550 if (MaskTy != WideTy)
551 Cost +=
552 TTI.getCastInstrCost(Opcode: Instruction::ZExt, Dst: WideTy, Src: MaskTy, CCH, CostKind);
553 return Cost;
554}
555
556InstructionCost getNarrowedLeafOpsCost(
557 const TargetTransformInfo &TTI,
558 const SmallDenseMap<Value *, NarrowedLeafInfo> &NarrowedLeafShifts,
559 VectorType *NarrowVecTy, VectorType *WideVecTy, const Instruction *CtxI,
560 const TTI::TargetCostKind CostKind) {
561 InstructionCost Cost = 0;
562 if (any_of(Range: NarrowedLeafShifts,
563 P: [](const auto &P) { return P.second.Shift != 0; }))
564 Cost += TTI.getArithmeticInstrCost(
565 Opcode: Instruction::Shl, Ty: WideVecTy, CostKind, Opd1Info: {.Kind: TTI::OK_AnyValue, .Properties: TTI::OP_None},
566 Opd2Info: {.Kind: TTI::OK_NonUniformConstantValue, .Properties: TTI::OP_None}, Args: {}, CtxI);
567 if (any_of(Range: NarrowedLeafShifts,
568 P: [](const auto &P) { return !P.second.Mask.isAllOnes(); }))
569 Cost += TTI.getArithmeticInstrCost(
570 Opcode: Instruction::And, Ty: NarrowVecTy, CostKind,
571 Opd1Info: {.Kind: TTI::OK_AnyValue, .Properties: TTI::OP_None},
572 Opd2Info: {.Kind: TTI::OK_NonUniformConstantValue, .Properties: TTI::OP_None}, Args: {}, CtxI);
573 return Cost;
574}
575
576SmallVector<Type *> buildIntrinsicArgTypes(const CallInst *CI,
577 const Intrinsic::ID ID,
578 const unsigned VF, unsigned MinBW,
579 const TargetTransformInfo &TTI) {
580 SmallVector<Type *> ArgTys;
581 for (auto [Idx, Arg] : enumerate(First: CI->args())) {
582 if (ID != Intrinsic::not_intrinsic) {
583 if (isVectorIntrinsicWithScalarOpAtArg(ID, ScalarOpdIdx: Idx, TTI: &TTI)) {
584 ArgTys.push_back(Elt: Arg->getType());
585 continue;
586 }
587 if (MinBW > 0) {
588 ArgTys.push_back(
589 Elt: getWidenedType(ScalarTy: IntegerType::get(C&: CI->getContext(), NumBits: MinBW), VF));
590 continue;
591 }
592 }
593 ArgTys.push_back(Elt: getWidenedType(ScalarTy: Arg->getType(), VF));
594 }
595 return ArgTys;
596}
597
598std::pair<InstructionCost, InstructionCost>
599getVectorCallCosts(CallInst *CI, Type *VecTy, const TargetTransformInfo &TTI,
600 const TargetLibraryInfo &TLI, ArrayRef<Type *> ArgTys,
601 const TTI::TargetCostKind CostKind) {
602 auto Shape = VFShape::get(FTy: CI->getFunctionType(),
603 EC: ElementCount::getFixed(MinVal: getNumElements(Ty: VecTy)),
604 HasGlobalPred: false /*HasGlobalPred*/);
605 Function *VecFunc = VFDatabase(*CI).getVectorizedFunction(Shape);
606 auto LibCost = InstructionCost::getInvalid();
607 if (!CI->isNoBuiltin() && VecFunc) {
608 // Calculate the cost of the vector library call.
609 // If the corresponding vector call is cheaper, return its cost.
610 LibCost = TTI.getCallInstrCost(F: nullptr, RetTy: VecTy, Tys: ArgTys, CostKind);
611 }
612 Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI: &TLI);
613
614 // Calculate the cost of the vector intrinsic call.
615 FastMathFlags FMF;
616 if (auto *FPCI = dyn_cast<FPMathOperator>(Val: CI))
617 FMF = FPCI->getFastMathFlags();
618 const InstructionCost ScalarLimit = 10000;
619 IntrinsicCostAttributes CostAttrs(ID, VecTy, ArgTys, FMF,
620 dyn_cast<IntrinsicInst>(Val: CI),
621 LibCost.isValid() ? LibCost : ScalarLimit);
622 auto IntrinsicCost = TTI.getIntrinsicInstrCost(ICA: CostAttrs, CostKind);
623 if (LibCost.isValid()) {
624 if (IntrinsicCost > LibCost)
625 IntrinsicCost = InstructionCost::getInvalid();
626 } else if (IntrinsicCost > ScalarLimit) {
627 // A type-based query always scalarizes struct-returning intrinsics (e.g.
628 // llvm.sincos), which do not have a VFDatabase name mapping. Retry with an
629 // argument-aware query (as the loop vectorizer does) so such lowerings are
630 // taken into account.
631 SmallVector<const Value *> Args(CI->args());
632 IntrinsicCostAttributes ArgAwareAttrs(
633 ID, VecTy, Args, ArgTys, FMF, dyn_cast<IntrinsicInst>(Val: CI), ScalarLimit);
634 IntrinsicCost = TTI.getIntrinsicInstrCost(ICA: ArgAwareAttrs, CostKind);
635 if (IntrinsicCost > ScalarLimit)
636 IntrinsicCost = InstructionCost::getInvalid();
637 }
638 if (ID == Intrinsic::sincos &&
639 shouldSplitVectorSinCos(TLI,
640 ScalarTy: CI->getArgOperand(i: 0)->getType()->getScalarType(),
641 EC: Shape.VF, M: CI->getModule()))
642 IntrinsicCost =
643 2 * TTI.getCallInstrCost(F: nullptr, RetTy: ArgTys.front(), Tys: ArgTys, CostKind);
644
645 return {IntrinsicCost, LibCost};
646}
647
648/// \returns the reciprocal-throughput cost of \p I widened to \p VF lanes (an
649/// arithmetic op or a vectorizable call).
650static InstructionCost getVectorOpCost(Instruction *I, unsigned VF,
651 const TargetTransformInfo &TTI,
652 const TargetLibraryInfo &TLI,
653 const TTI::TargetCostKind CostKind) {
654 assert((isa<BinaryOperator, CallInst>(I)) &&
655 "getVectorOpCost expects an arithmetic op or a vectorizable call.");
656 Type *VecTy = getWidenedType(ScalarTy: I->getType(), VF);
657 if (auto *CI = dyn_cast<CallInst>(Val: I)) {
658 Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI: &TLI);
659 SmallVector<Type *> ArgTys = buildIntrinsicArgTypes(CI, ID, VF, MinBW: 0, TTI);
660 auto [IntrCost, LibCost] =
661 getVectorCallCosts(CI, VecTy, TTI, TLI, ArgTys, CostKind);
662 return std::min(a: IntrCost, b: LibCost);
663 }
664 SmallVector<const Value *, 2> Args{I->getOperand(i: 0), I->getOperand(i: 1)};
665 return TTI.getArithmeticInstrCost(
666 Opcode: I->getOpcode(), Ty: VecTy, CostKind, Opd1Info: TTI::getOperandInfo(V: I->getOperand(i: 0)),
667 Opd2Info: TTI::getOperandInfo(V: I->getOperand(i: 1)), Args, CtxI: I);
668}
669
670/// Packs a type's kind and scalar width into one key, so an opcode/intrinsic
671/// id reused across scalar widths (e.g. fdiv float vs. fdiv double) is cached
672/// per width instead of sharing one verdict.
673static unsigned getPoorThroughputTypeKey(Type *Ty) {
674 return (static_cast<unsigned>(Ty->getTypeID()) << 16) |
675 Ty->getScalarSizeInBits();
676}
677
678bool isPoorThroughputOp(bool ReVec, Instruction *I,
679 const TargetTransformInfo &TTI,
680 const TargetLibraryInfo &TLI,
681 PoorThroughputOpCache &Cache,
682 const TTI::TargetCostKind CostKind,
683 unsigned MaxVecRegSize) {
684 if (!isa<BinaryOperator, CallInst>(Val: I))
685 return false;
686 Type *Ty = I->getType();
687 if ((Ty->isVectorTy() && !ReVec) || Ty->isAggregateType() ||
688 !isValidElementType(Ty, ReVec))
689 return false;
690 auto Analyze = [&]() {
691 InstructionCost ScalarCost = TTI.getInstructionCost(U: I, CostKind);
692 if (ScalarCost < TTI::TCC_Expensive)
693 return false;
694 constexpr unsigned MinVF = 2;
695 if (getVectorOpCost(I, VF: MinVF, TTI, TLI, CostKind) < ScalarCost * MinVF)
696 return true;
697 // Some ops (e.g. div by constant) scalarize at VF=2 but have a cheap
698 // vector form at the full register width.
699 unsigned TyBits = Ty->getPrimitiveSizeInBits().getFixedValue();
700 unsigned MaxVF = TyBits ? llvm::bit_floor(Value: MaxVecRegSize / TyBits) : 0;
701 return MaxVF > MinVF &&
702 getVectorOpCost(I, VF: MaxVF, TTI, TLI, CostKind) < ScalarCost * MaxVF;
703 };
704 auto CheckCached = [&](bool IsCheap, llvm::function_ref<void()> MarkCheap) {
705 if (IsCheap)
706 return false;
707 if (Analyze())
708 return true;
709 MarkCheap();
710 return false;
711 };
712 if (auto *CI = dyn_cast<CallInst>(Val: I)) {
713 if (any_of(Range: CI->args(), P: [&](const Value *Arg) {
714 return !isValidElementType(Ty: Arg->getType(), ReVec);
715 }))
716 return false;
717 // A call, used only as a select operand, may get the values rejected by the
718 // select condition, which the vector library call handles on its slow path.
719 if (!CI->use_empty() && !CI->hasNUsesOrMore(N: UsesLimit) &&
720 all_of(Range: CI->users(), P: [&](User *U) {
721 return match(
722 V: U, P: m_Select(C: m_Unless(P: m_Specific(V: CI)), L: m_Value(), R: m_Value()));
723 }))
724 return false;
725 if (Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI: &TLI)) {
726 auto Key = std::make_pair(x&: ID, y: getPoorThroughputTypeKey(Ty));
727 return CheckCached(Cache.CheapIntrinsics.contains(V: Key),
728 [&] { Cache.CheapIntrinsics.insert(V: Key); });
729 }
730 // A call without the vector variants is never vectorized.
731 if (VFDatabase::getMappings(CI: *CI).empty())
732 return false;
733 const Function *Callee = CI->getCalledFunction();
734 if (!Callee)
735 return Analyze();
736 return CheckCached(Cache.CheapCallees.contains(V: Callee),
737 [&] { Cache.CheapCallees.insert(V: Callee); });
738 }
739 auto Key = std::make_pair(x: I->getOpcode(), y: getPoorThroughputTypeKey(Ty));
740 return CheckCached(Cache.CheapOpcodes.contains(V: Key),
741 [&] { Cache.CheapOpcodes.insert(V: Key); });
742}
743
744bool isFusableFMulOperand(Value *Op, Instruction *I,
745 const TargetTransformInfo &TTI) {
746 Instruction *FMul;
747 if (!match(V: Op, P: m_Instruction(I&: FMul, P: m_OneUse(SubPattern: m_AllowContract(
748 SubPattern: m_FMul(L: m_Value(), R: m_Value()))))))
749 return false;
750 if (FMul->getParent() == I->getParent())
751 return true;
752 SmallVector<Use *> OpsToSink;
753 return TTI.isProfitableToSinkOperands(I, Ops&: OpsToSink) &&
754 any_of(Range&: OpsToSink, P: [&](const Use *U) { return U->get() == FMul; });
755}
756
757bool hasHighRegisterPressure(unsigned ScheduleBudget, const BasicBlock &BB,
758 Type *Ty, const TargetTransformInfo &TTI) {
759 if (hasNItemsOrMore(C: BB, N: ScheduleBudget))
760 return false;
761 const unsigned NumRegs = TTI.getNumberOfRegisters(
762 ClassID: TTI.getRegisterClassForType(/*Vector=*/false, Ty));
763 auto IsLiveCandidate = [&](const Value *V) {
764 return isa<Instruction, Argument>(Val: V) && V->getType()->getScalarType() == Ty;
765 };
766 SmallPtrSet<const Value *, 32> Live;
767 for (const Instruction &I : reverse(C: BB)) {
768 // The operands of the PHIs are live in the predecessors.
769 if (isa<PHINode>(Val: I))
770 break;
771 Live.erase(Ptr: &I);
772 Live.insert_range(R: make_filter_range(Range: I.operand_values(), Pred: IsLiveCandidate));
773 if (Live.size() > NumRegs)
774 return true;
775 }
776 return false;
777}
778
779SmallBitVector selectBSwapGathers(
780 ArrayRef<SmallVector<Value *>> GatheredScalars, const DataLayout &DL,
781 const TargetTransformInfo &TTI, bool ReVec,
782 TargetTransformInfo::TargetCostKind CostKind,
783 function_ref<std::optional<
784 std::tuple<const void *, FixedVectorType *, unsigned>>(Value *)>
785 GetVectorizedSource) {
786 struct SourceVector {
787 FixedVectorType *VecTy = nullptr;
788 APInt DemandedElts;
789 InstructionCost Cost = 0;
790 SmallVector<unsigned> Gathers;
791 };
792 SmallDenseMap<const void *, SourceVector> SourceVectors;
793 SmallBitVector BSwapGathers(GatheredScalars.size());
794 for (auto [Idx, VL] : enumerate(First&: GatheredScalars)) {
795 std::optional<std::tuple<Value *, unsigned, SmallVector<int>>> Fields =
796 matchGatheredExtractedFields(VL, DL);
797 if (!Fields)
798 continue;
799 auto &[Src, FieldWidth, Mask] = *Fields;
800 Type *SrcTy = Src->getType();
801 unsigned NumFields = SrcTy->getIntegerBitWidth() / FieldWidth;
802 if (FieldWidth != 8 || NumFields % 2 != 0 ||
803 !ShuffleVectorInst::isReverseMask(Mask, NumSrcElts: NumFields))
804 continue;
805 Type *ByteTy = Type::getInt8Ty(C&: SrcTy->getContext());
806 auto *FieldVecTy = cast<VectorType>(Val: getWidenedType(ScalarTy: ByteTy, VF: NumFields));
807 IntrinsicCostAttributes CostAttrs(Intrinsic::bswap, SrcTy, {SrcTy});
808 InstructionCost BSwapCost = TTI.getIntrinsicInstrCost(ICA: CostAttrs, CostKind);
809 InstructionCost PermuteCost = getShuffleCost(TTI, Kind: TTI::SK_PermuteSingleSrc,
810 Tp: FieldVecTy, CostKind, Mask);
811 std::optional<std::tuple<const void *, FixedVectorType *, unsigned>>
812 Source = GetVectorizedSource(Src);
813 if (!Source)
814 if (std::optional<unsigned> Lane = getElementIndex(Inst: Src)) {
815 auto *EE = cast<ExtractElementInst>(Val: Src);
816 Source = std::make_tuple(
817 args: EE->getVectorOperand(),
818 args: cast<FixedVectorType>(Val: EE->getVectorOperandType()), args&: *Lane);
819 }
820 if (!Source) {
821 if (BSwapCost <= PermuteCost)
822 BSwapGathers.set(Idx);
823 continue;
824 }
825 auto &[Vec, VecTy, Lane] = *Source;
826 // The bytes of the scalar are either extracted from the vector as a
827 // subvector and permuted, or permuted from the whole vector directly.
828 auto *VecBytesTy = cast<VectorType>(
829 Val: getWidenedType(ScalarTy: ByteTy, VF: NumFields * VecTy->getNumElements()));
830 for (int &I : Mask)
831 if (I != PoisonMaskElem)
832 I += Lane * NumFields;
833 PermuteCost =
834 std::min(a: PermuteCost + getShuffleCost(TTI, Kind: TTI::SK_ExtractSubvector,
835 Tp: VecBytesTy, CostKind, Mask: {},
836 Index: Lane * NumFields, SubTp: FieldVecTy),
837 b: getShuffleCost(TTI, Kind: TTI::SK_PermuteSingleSrc, Tp: VecBytesTy,
838 CostKind, Mask));
839 auto [It, Inserted] = SourceVectors.try_emplace(Key: Vec);
840 SourceVector &Info = It->second;
841 if (Inserted) {
842 Info.VecTy = VecTy;
843 Info.DemandedElts = APInt::getZero(numBits: VecTy->getNumElements());
844 }
845 Info.DemandedElts.setBit(Lane);
846 Info.Cost += BSwapCost - PermuteCost;
847 Info.Gathers.push_back(Elt: Idx);
848 }
849 for (const SourceVector &Info : make_second_range(c&: SourceVectors)) {
850 InstructionCost ExtractCost = getScalarizationOverhead(
851 TTI, ReVec, ScalarTy: Info.VecTy->getElementType(), Ty: Info.VecTy, DemandedElts: Info.DemandedElts,
852 /*Insert=*/false, /*Extract=*/true, CostKind);
853 if (Info.Cost + ExtractCost <= 0)
854 for (unsigned Idx : Info.Gathers)
855 BSwapGathers.set(Idx);
856 }
857 return BSwapGathers;
858}
859} // namespace llvm::slpvectorizer
860