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