1//===- SLPUtils.cpp - SLP Vectorizer free utility 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 "SLPUtils.h"
10
11#include "llvm/ADT/APInt.h"
12#include "llvm/ADT/STLExtras.h"
13#include "llvm/ADT/Sequence.h"
14#include "llvm/Analysis/AssumptionCache.h"
15#include "llvm/Analysis/ValueTracking.h"
16#include "llvm/Analysis/VectorUtils.h"
17#include "llvm/IR/Constants.h"
18#include "llvm/IR/DataLayout.h"
19#include "llvm/IR/DerivedTypes.h"
20#include "llvm/IR/IRBuilder.h"
21#include "llvm/IR/Instructions.h"
22#include "llvm/IR/IntrinsicInst.h"
23#include "llvm/IR/PatternMatch.h"
24#include "llvm/Support/Casting.h"
25#include "llvm/Support/MathExtras.h"
26#include "llvm/Support/raw_ostream.h"
27
28#include <algorithm>
29#include <numeric>
30#include <string>
31#include <type_traits>
32
33using namespace llvm;
34using namespace llvm::PatternMatch;
35
36namespace llvm::slpvectorizer {
37
38bool isConstant(Value *V) {
39 return isa<Constant>(Val: V) && !isa<ConstantExpr, GlobalValue>(Val: V);
40}
41
42bool isBinOpIdentityConstant(const Value *V, unsigned Opcode) {
43 const auto *CI = dyn_cast<ConstantInt>(Val: V);
44 return CI && ConstantExpr::getBinOpIdentity(Opcode, Ty: CI->getType()) == CI;
45}
46
47unsigned getReassocCombineOpcode(unsigned Opcode) {
48 switch (Opcode) {
49 case Instruction::Sub:
50 return Instruction::Add;
51 case Instruction::FSub:
52 return Instruction::FAdd;
53 default:
54 return Opcode;
55 }
56}
57
58bool isReassocChainLink(const Instruction *I) {
59 if (I->getOpcode() == Instruction::Sub)
60 return true;
61 if (I->getOpcode() == Instruction::FSub)
62 return I->hasAllowReassoc();
63 return I->isAssociative();
64}
65
66bool isVectorLikeInstWithConstOps(Value *V) {
67 auto *I = dyn_cast<Instruction>(Val: V);
68 // Non-instructions are vector-like only if they are undef.
69 if (!I)
70 return isa<UndefValue>(Val: V);
71 switch (I->getOpcode()) {
72 case Instruction::ExtractValue:
73 case Instruction::InsertValue:
74 return true;
75 case Instruction::ExtractElement:
76 return isa<FixedVectorType>(Val: I->getOperand(i: 0)->getType()) &&
77 isConstant(V: I->getOperand(i: 1));
78 case Instruction::InsertElement:
79 return isa<FixedVectorType>(Val: I->getOperand(i: 0)->getType()) &&
80 isConstant(V: I->getOperand(i: 2));
81 default:
82 return false;
83 }
84}
85
86unsigned getNumElements(Type *Ty) {
87 assert(!isa<ScalableVectorType>(Ty) &&
88 "ScalableVectorType is not supported.");
89 if (isVectorizedTy(Ty))
90 return getVectorizedTypeVF(Ty).getFixedValue();
91 return 1;
92}
93
94unsigned getPartNumElems(unsigned Size, unsigned NumParts) {
95 return std::min<unsigned>(a: Size, b: bit_ceil(Value: divideCeil(Numerator: Size, Denominator: NumParts)));
96}
97
98unsigned getNumElems(unsigned Size, unsigned PartNumElems, unsigned Part) {
99 return std::min<unsigned>(a: PartNumElems, b: Size - Part * PartNumElems);
100}
101
102#if !defined(NDEBUG)
103std::string shortBundleName(ArrayRef<Value *> VL, int Idx) {
104 std::string Result;
105 raw_string_ostream OS(Result);
106 if (Idx >= 0)
107 OS << "Idx: " << Idx << ", ";
108 OS << "n=" << VL.size() << " [" << *VL.front() << ", ..]";
109 return Result;
110}
111#endif
112
113bool allSameBlock(ArrayRef<Value *> VL) {
114 auto *It = find_if(Range&: VL, P: IsaPred<Instruction>);
115 if (It == VL.end())
116 return false;
117 Instruction *I0 = cast<Instruction>(Val: *It);
118 if (all_of(Range&: VL, P: isVectorLikeInstWithConstOps))
119 return true;
120
121 BasicBlock *BB = I0->getParent();
122 for (Value *V : iterator_range(It, VL.end())) {
123 if (isa<PoisonValue>(Val: V))
124 continue;
125 auto *II = dyn_cast<Instruction>(Val: V);
126 if (!II)
127 return false;
128
129 if (BB != II->getParent())
130 return false;
131 }
132 return true;
133}
134
135bool allConstant(ArrayRef<Value *> VL) {
136 // Constant expressions and globals can't be vectorized like normal integer/FP
137 // constants.
138 return all_of(Range&: VL, P: isConstant);
139}
140
141bool isSplat(ArrayRef<Value *> VL) {
142 Value *FirstNonUndef = nullptr;
143 for (Value *V : VL) {
144 if (isa<UndefValue>(Val: V))
145 continue;
146 if (!FirstNonUndef) {
147 FirstNonUndef = V;
148 continue;
149 }
150 if (V != FirstNonUndef)
151 return false;
152 }
153 return FirstNonUndef != nullptr;
154}
155
156Intrinsic::ID isEquivalentIntrinsicID(Intrinsic::ID LHS, Intrinsic::ID RHS) {
157 if (LHS == RHS)
158 return RHS;
159 if ((LHS == Intrinsic::fma || LHS == Intrinsic::fmuladd) &&
160 (RHS == Intrinsic::fma || RHS == Intrinsic::fmuladd))
161 return Intrinsic::fma;
162 return Intrinsic::not_intrinsic;
163}
164
165bool isCommutative(const Instruction *I, const Value *ValWithUses,
166 bool IsCopyable) {
167 if (auto *Cmp = dyn_cast<CmpInst>(Val: I))
168 return Cmp->isCommutative();
169 if (auto *BO = dyn_cast<BinaryOperator>(Val: I))
170 return BO->isCommutative() ||
171 (BO->getOpcode() == Instruction::Sub && ValWithUses->hasUseList() &&
172 !ValWithUses->hasNUsesOrMore(N: UsesLimit) &&
173 all_of(
174 Range: ValWithUses->uses(),
175 P: [&](const Use &U) {
176 // Commutative, if icmp eq/ne sub, 0
177 CmpPredicate Pred;
178 if (match(V: U.getUser(),
179 P: m_ICmp(Pred, L: m_Specific(V: U.get()), R: m_Zero())) &&
180 (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE))
181 return true;
182 // Commutative, if abs(sub nsw, true) or abs(sub, false).
183 ConstantInt *Flag;
184 auto *I = dyn_cast<BinaryOperator>(Val: U.get());
185 return match(V: U.getUser(),
186 P: m_Intrinsic<Intrinsic::abs>(
187 Ops: m_Specific(V: U.get()), Ops: m_ConstantInt(CI&: Flag))) &&
188 ((!IsCopyable && I && !I->hasNoSignedWrap()) ||
189 Flag->isOne());
190 })) ||
191 (BO->getOpcode() == Instruction::FSub && ValWithUses->hasUseList() &&
192 !ValWithUses->hasNUsesOrMore(N: UsesLimit) &&
193 all_of(Range: ValWithUses->uses(), P: [](const Use &U) {
194 return match(V: U.getUser(),
195 P: m_Intrinsic<Intrinsic::fabs>(Ops: m_Specific(V: U.get())));
196 }));
197 return I->isCommutative();
198}
199
200bool isCommutative(const Instruction *I) { return isCommutative(I, ValWithUses: I); }
201
202bool isCommutableOperand(const Instruction *I, Value *ValWithUses, unsigned Op,
203 bool IsCopyable) {
204 assert(isCommutative(I, ValWithUses, IsCopyable) &&
205 "The instruction is not commutative.");
206 if (isa<CmpInst>(Val: I))
207 return true;
208 if (auto *BO = dyn_cast<BinaryOperator>(Val: I)) {
209 switch (BO->getOpcode()) {
210 case Instruction::Sub:
211 case Instruction::FSub:
212 return true;
213 default:
214 break;
215 }
216 }
217 return I->isCommutableOperand(Op);
218}
219
220unsigned getNumberOfPotentiallyCommutativeOps(Instruction *I) {
221 if (isa<IntrinsicInst>(Val: I) && isCommutative(I)) {
222 // IntrinsicInst::isCommutative returns true if swapping the first "two"
223 // arguments to the intrinsic produces the same result.
224 constexpr unsigned IntrinsicNumOperands = 2;
225 return IntrinsicNumOperands;
226 }
227 return I->getNumOperands();
228}
229
230std::optional<unsigned> getElementIndex(const Value *Inst, unsigned Offset) {
231 if (auto Index = getInsertExtractIndex<InsertElementInst>(Inst, Offset))
232 return Index;
233 if (auto Index = getInsertExtractIndex<ExtractElementInst>(Inst, Offset))
234 return Index;
235
236 unsigned Index = Offset;
237
238 const auto *IV = dyn_cast<InsertValueInst>(Val: Inst);
239 if (!IV)
240 return std::nullopt;
241
242 Type *CurrentType = IV->getType();
243 for (unsigned I : IV->indices()) {
244 if (const auto *ST = dyn_cast<StructType>(Val: CurrentType)) {
245 Index *= ST->getNumElements();
246 CurrentType = ST->getElementType(N: I);
247 } else if (const auto *AT = dyn_cast<ArrayType>(Val: CurrentType)) {
248 Index *= AT->getNumElements();
249 CurrentType = AT->getElementType();
250 } else {
251 return std::nullopt;
252 }
253 Index += I;
254 }
255 return Index;
256}
257
258bool allSameOpcode(ArrayRef<Value *> VL) {
259 auto *It = find_if(Range&: VL, P: IsaPred<Instruction>);
260 if (It == VL.end())
261 return true;
262 Instruction *MainOp = cast<Instruction>(Val: *It);
263 unsigned Opcode = MainOp->getOpcode();
264 bool IsCmpOp = isa<CmpInst>(Val: MainOp);
265 CmpInst::Predicate BasePred = IsCmpOp ? cast<CmpInst>(Val: MainOp)->getPredicate()
266 : CmpInst::BAD_ICMP_PREDICATE;
267 return all_of(Range: make_range(x: It, y: VL.end()), P: [&](Value *V) {
268 if (auto *CI = dyn_cast<CmpInst>(Val: V))
269 return BasePred == CI->getPredicate();
270 if (auto *I = dyn_cast<Instruction>(Val: V))
271 return I->getOpcode() == Opcode;
272 return isa<PoisonValue>(Val: V);
273 });
274}
275
276std::optional<unsigned> getExtractIndex(const Instruction *E) {
277 unsigned Opcode = E->getOpcode();
278 assert((Opcode == Instruction::ExtractElement ||
279 Opcode == Instruction::ExtractValue) &&
280 "Expected extractelement or extractvalue instruction.");
281 if (Opcode == Instruction::ExtractElement) {
282 auto *CI = dyn_cast<ConstantInt>(Val: E->getOperand(i: 1));
283 if (!CI)
284 return std::nullopt;
285 // Check if the index is out of bound. We can get the source vector from
286 // operand 0.
287 unsigned Idx = CI->getZExtValue();
288 auto *EE = cast<ExtractElementInst>(Val: E);
289 const unsigned VF = getNumElements(Ty: EE->getVectorOperandType());
290 if (Idx >= VF)
291 return std::nullopt;
292 return Idx;
293 }
294 auto *EI = cast<ExtractValueInst>(Val: E);
295 if (EI->getNumIndices() != 1)
296 return std::nullopt;
297 return *EI->idx_begin();
298}
299
300void inversePermutation(ArrayRef<unsigned> Indices,
301 SmallVectorImpl<int> &Mask) {
302 Mask.clear();
303 const unsigned E = Indices.size();
304 Mask.resize(N: E, NV: PoisonMaskElem);
305 for (unsigned I = 0; I < E; ++I)
306 Mask[Indices[I]] = I;
307}
308
309void reorderScalars(SmallVectorImpl<Value *> &Scalars, ArrayRef<int> Mask) {
310 assert(!Mask.empty() && "Expected non-empty mask.");
311 SmallVector<Value *> Prev(Scalars.size(),
312 PoisonValue::get(T: Scalars.front()->getType()));
313 Prev.swap(RHS&: Scalars);
314 for (unsigned I = 0, E = Prev.size(); I < E; ++I)
315 if (Mask[I] != PoisonMaskElem)
316 Scalars[Mask[I]] = Prev[I];
317}
318
319void reorderReuses(SmallVectorImpl<int> &Reuses, ArrayRef<int> Mask) {
320 assert(!Mask.empty() && Reuses.size() == Mask.size() &&
321 "Expected non-empty mask.");
322 SmallVector<int> Prev(Reuses.begin(), Reuses.end());
323 Prev.swap(RHS&: Reuses);
324 for (unsigned I = 0, E = Prev.size(); I < E; ++I)
325 if (Mask[I] != PoisonMaskElem)
326 Reuses[Mask[I]] = Prev[I];
327}
328
329void reorderOrder(SmallVectorImpl<unsigned> &Order, ArrayRef<int> Mask,
330 bool BottomOrder) {
331 assert(!Mask.empty() && "Expected non-empty mask.");
332 unsigned Sz = Mask.size();
333 if (BottomOrder) {
334 SmallVector<unsigned> PrevOrder;
335 if (Order.empty()) {
336 PrevOrder.resize(N: Sz);
337 std::iota(first: PrevOrder.begin(), last: PrevOrder.end(), value: 0);
338 } else {
339 PrevOrder.swap(RHS&: Order);
340 }
341 Order.assign(NumElts: Sz, Elt: Sz);
342 for (unsigned I = 0; I < Sz; ++I)
343 if (Mask[I] != PoisonMaskElem)
344 Order[I] = PrevOrder[Mask[I]];
345 if (all_of(Range: enumerate(First&: Order), P: [&](const auto &Data) {
346 return Data.value() == Sz || Data.index() == Data.value();
347 })) {
348 Order.clear();
349 return;
350 }
351 fixupOrderingIndices(Order);
352 return;
353 }
354 SmallVector<int> MaskOrder;
355 if (Order.empty()) {
356 MaskOrder.resize(N: Sz);
357 std::iota(first: MaskOrder.begin(), last: MaskOrder.end(), value: 0);
358 } else {
359 inversePermutation(Indices: Order, Mask&: MaskOrder);
360 }
361 reorderReuses(Reuses&: MaskOrder, Mask);
362 if (ShuffleVectorInst::isIdentityMask(Mask: MaskOrder, NumSrcElts: Sz)) {
363 Order.clear();
364 return;
365 }
366 Order.assign(NumElts: Sz, Elt: Sz);
367 for (unsigned I = 0; I < Sz; ++I)
368 if (MaskOrder[I] != PoisonMaskElem)
369 Order[MaskOrder[I]] = I;
370 fixupOrderingIndices(Order);
371}
372
373bool isReverseOrder(ArrayRef<unsigned> Order) {
374 assert(!Order.empty() &&
375 "Order is empty. Please check it before using isReverseOrder.");
376 unsigned Sz = Order.size();
377 return all_of(Range: enumerate(First&: Order), P: [&](const auto &Pair) {
378 return Pair.value() == Sz || Sz - Pair.index() - 1 == Pair.value();
379 });
380}
381
382bool isRepeatedNonIdentityClusteredMask(ArrayRef<int> Mask, unsigned Sz) {
383 ArrayRef<int> FirstCluster = Mask.slice(N: 0, M: Sz);
384 if (ShuffleVectorInst::isIdentityMask(Mask: FirstCluster, NumSrcElts: Sz))
385 return false;
386 for (unsigned I = Sz, E = Mask.size(); I < E; I += Sz) {
387 ArrayRef<int> Cluster = Mask.slice(N: I, M: Sz);
388 if (Cluster != FirstCluster)
389 return false;
390 }
391 return true;
392}
393
394void combineOrders(MutableArrayRef<unsigned> Order,
395 ArrayRef<unsigned> SecondaryOrder) {
396 assert((SecondaryOrder.empty() || Order.size() == SecondaryOrder.size()) &&
397 "Expected same size of orders");
398 size_t Sz = Order.size();
399 SmallBitVector UsedIndices(Sz);
400 for (unsigned Idx : seq<unsigned>(Begin: 0, End: Sz)) {
401 if (Order[Idx] != Sz)
402 UsedIndices.set(Order[Idx]);
403 }
404 if (SecondaryOrder.empty()) {
405 for (unsigned Idx : seq<unsigned>(Begin: 0, End: Sz))
406 if (Order[Idx] == Sz && !UsedIndices.test(Idx))
407 Order[Idx] = Idx;
408 } else {
409 for (unsigned Idx : seq<unsigned>(Begin: 0, End: Sz))
410 if (SecondaryOrder[Idx] != Sz && Order[Idx] == Sz &&
411 !UsedIndices.test(Idx: SecondaryOrder[Idx]))
412 Order[Idx] = SecondaryOrder[Idx];
413 }
414}
415
416bool allSameType(ArrayRef<Value *> VL) {
417 assert(!VL.empty() && "Expected non-empty list of values.");
418 Type *Ty = VL.consume_front()->getType();
419 return all_of(Range&: VL, P: [&](Value *V) { return V->getType() == Ty; });
420}
421
422template <typename T>
423std::optional<unsigned> getInsertExtractIndex(const Value *Inst,
424 unsigned Offset) {
425 static_assert(std::is_same_v<T, InsertElementInst> ||
426 std::is_same_v<T, ExtractElementInst>,
427 "unsupported T");
428 const auto *IE = dyn_cast<T>(Inst);
429 if (!IE)
430 return std::nullopt;
431 // InsertElement: result is the vector, index is op 2.
432 // ExtractElement: result is scalar, vector is op 0, index is op 1.
433 constexpr bool IsInsert = std::is_same_v<T, InsertElementInst>;
434 Type *VecTy = IsInsert ? IE->getType() : IE->getOperand(0)->getType();
435 const auto *VT = dyn_cast<FixedVectorType>(Val: VecTy);
436 if (!VT)
437 return std::nullopt;
438 const auto *CI = dyn_cast<ConstantInt>(IE->getOperand(IsInsert ? 2 : 1));
439 if (!CI)
440 return std::nullopt;
441 if (CI->getValue().uge(VT->getNumElements()))
442 return std::nullopt;
443 unsigned Index = Offset;
444 Index *= VT->getNumElements();
445 Index += CI->getZExtValue();
446 return Index;
447}
448
449// Only these two specializations are used; instantiate them here so the
450// definition can stay out of the header.
451template std::optional<unsigned>
452getInsertExtractIndex<InsertElementInst>(const Value *, unsigned);
453template std::optional<unsigned>
454getInsertExtractIndex<ExtractElementInst>(const Value *, unsigned);
455
456bool areAllOperandsNonInsts(Value *V) {
457 auto *I = dyn_cast<Instruction>(Val: V);
458 if (!I)
459 return true;
460 return !mayHaveNonDefUseDependency(I: *I) &&
461 all_of(Range: I->operands(), P: [I](Value *V) {
462 auto *IO = dyn_cast<Instruction>(Val: V);
463 if (!IO)
464 return true;
465 return isa<PHINode>(Val: IO) || IO->getParent() != I->getParent();
466 });
467}
468
469bool isUsedOutsideBlock(Value *V) {
470 auto *I = dyn_cast<Instruction>(Val: V);
471 if (!I)
472 return true;
473 // Limits the number of uses to save compile time.
474 return !I->mayReadOrWriteMemory() && !I->hasNUsesOrMore(N: UsesLimit) &&
475 all_of(Range: I->users(), P: [I](User *U) {
476 auto *IU = dyn_cast<Instruction>(Val: U);
477 if (!IU)
478 return true;
479 return IU->getParent() != I->getParent() || isa<PHINode>(Val: IU);
480 });
481}
482
483bool doesNotNeedToBeScheduled(Value *V) {
484 return areAllOperandsNonInsts(V) && isUsedOutsideBlock(V);
485}
486
487bool doesNotNeedToSchedule(ArrayRef<Value *> VL) {
488 return !VL.empty() &&
489 (all_of(Range&: VL, P: isUsedOutsideBlock) || all_of(Range&: VL, P: areAllOperandsNonInsts));
490}
491
492void transformScalarShuffleIndiciesToVector(unsigned VecTyNumElements,
493 SmallVectorImpl<int> &Mask) {
494 // The ShuffleBuilder implementation use shufflevector to splat an "element".
495 // But the element have different meaning for SLP (scalar) and REVEC
496 // (vector). We need to expand Mask into masks which shufflevector can use
497 // directly.
498 SmallVector<int> NewMask(Mask.size() * VecTyNumElements);
499 for (unsigned I : seq<unsigned>(Size: Mask.size()))
500 for (auto [J, MaskV] : enumerate(First: MutableArrayRef(NewMask).slice(
501 N: I * VecTyNumElements, M: VecTyNumElements)))
502 MaskV = Mask[I] == PoisonMaskElem ? PoisonMaskElem
503 : Mask[I] * VecTyNumElements + J;
504 Mask.swap(RHS&: NewMask);
505}
506
507unsigned getShufflevectorNumGroups(ArrayRef<Value *> VL) {
508 if (VL.empty())
509 return 0;
510 if (!all_of(Range&: VL, P: IsaPred<ShuffleVectorInst>))
511 return 0;
512 auto *SV = cast<ShuffleVectorInst>(Val: VL.front());
513 unsigned SVNumElements =
514 cast<FixedVectorType>(Val: SV->getOperand(i_nocapture: 0)->getType())->getNumElements();
515 unsigned ShuffleMaskSize = SV->getShuffleMask().size();
516 if (SVNumElements % ShuffleMaskSize != 0)
517 return 0;
518 unsigned GroupSize = SVNumElements / ShuffleMaskSize;
519 if (GroupSize == 0 || (VL.size() % GroupSize) != 0)
520 return 0;
521 unsigned NumGroup = 0;
522 for (size_t I = 0, E = VL.size(); I != E; I += GroupSize) {
523 auto *SV = cast<ShuffleVectorInst>(Val: VL[I]);
524 Value *Src = SV->getOperand(i_nocapture: 0);
525 ArrayRef<Value *> Group = VL.slice(N: I, M: GroupSize);
526 SmallBitVector ExpectedIndex(GroupSize);
527 if (!all_of(Range&: Group, P: [&](Value *V) {
528 auto *SV = cast<ShuffleVectorInst>(Val: V);
529 // From the same source.
530 if (SV->getOperand(i_nocapture: 0) != Src)
531 return false;
532 int Index;
533 if (!SV->isExtractSubvectorMask(Index))
534 return false;
535 ExpectedIndex.set(Index / ShuffleMaskSize);
536 return true;
537 }))
538 return 0;
539 if (!ExpectedIndex.all())
540 return 0;
541 ++NumGroup;
542 }
543 assert(NumGroup == (VL.size() / GroupSize) && "Unexpected number of groups");
544 return NumGroup;
545}
546
547SmallVector<int> calculateShufflevectorMask(ArrayRef<Value *> VL) {
548 assert(getShufflevectorNumGroups(VL) && "Not supported shufflevector usage.");
549 auto *SV = cast<ShuffleVectorInst>(Val: VL.front());
550 unsigned SVNumElements =
551 cast<FixedVectorType>(Val: SV->getOperand(i_nocapture: 0)->getType())->getNumElements();
552 SmallVector<int> Mask;
553 unsigned AccumulateLength = 0;
554 for (Value *V : VL) {
555 auto *SV = cast<ShuffleVectorInst>(Val: V);
556 for (int M : SV->getShuffleMask())
557 Mask.push_back(Elt: M == PoisonMaskElem ? PoisonMaskElem
558 : AccumulateLength + M);
559 AccumulateLength += SVNumElements;
560 }
561 return Mask;
562}
563
564/// Checks if the vector of instructions can be represented as a shuffle, like:
565/// %x0 = extractelement <4 x i8> %x, i32 0
566/// %x3 = extractelement <4 x i8> %x, i32 3
567/// %y1 = extractelement <4 x i8> %y, i32 1
568/// %y2 = extractelement <4 x i8> %y, i32 2
569/// %x0x0 = mul i8 %x0, %x0
570/// %x3x3 = mul i8 %x3, %x3
571/// %y1y1 = mul i8 %y1, %y1
572/// %y2y2 = mul i8 %y2, %y2
573/// %ins1 = insertelement <4 x i8> poison, i8 %x0x0, i32 0
574/// %ins2 = insertelement <4 x i8> %ins1, i8 %x3x3, i32 1
575/// %ins3 = insertelement <4 x i8> %ins2, i8 %y1y1, i32 2
576/// %ins4 = insertelement <4 x i8> %ins3, i8 %y2y2, i32 3
577/// ret <4 x i8> %ins4
578/// can be transformed into:
579/// %1 = shufflevector <4 x i8> %x, <4 x i8> %y, <4 x i32> <i32 0, i32 3, i32 5,
580/// i32 6>
581/// %2 = mul <4 x i8> %1, %1
582/// ret <4 x i8> %2
583/// Mask will return the Shuffle Mask equivalent to the extracted elements.
584/// TODO: Can we split off and reuse the shuffle mask detection from
585/// ShuffleVectorInst/getShuffleCost?
586std::optional<TargetTransformInfo::ShuffleKind>
587isFixedVectorShuffle(ArrayRef<Value *> VL, SmallVectorImpl<int> &Mask,
588 AssumptionCache *AC) {
589 const auto *It = find_if(Range&: VL, P: IsaPred<ExtractElementInst>);
590 if (It == VL.end())
591 return std::nullopt;
592 unsigned Size = accumulate(Range&: VL, Init: 0u, Op: [](unsigned S, Value *V) {
593 auto *EI = dyn_cast<ExtractElementInst>(Val: V);
594 if (!EI)
595 return S;
596 auto *VTy = dyn_cast<FixedVectorType>(Val: EI->getVectorOperandType());
597 if (!VTy)
598 return S;
599 return std::max(a: S, b: VTy->getNumElements());
600 });
601
602 Value *Vec1 = nullptr;
603 Value *Vec2 = nullptr;
604 bool HasNonUndefVec = any_of(Range&: VL, P: [&](Value *V) {
605 auto *EE = dyn_cast<ExtractElementInst>(Val: V);
606 if (!EE)
607 return false;
608 Value *Vec = EE->getVectorOperand();
609 if (isa<UndefValue>(Val: Vec))
610 return false;
611 return isGuaranteedNotToBePoison(V: Vec, AC);
612 });
613 enum ShuffleMode { Unknown, Select, Permute };
614 ShuffleMode CommonShuffleMode = Unknown;
615 Mask.assign(NumElts: VL.size(), Elt: PoisonMaskElem);
616 for (unsigned I = 0, E = VL.size(); I < E; ++I) {
617 // Undef, or a copyable lane modeled on an extract main op, can be
618 // represented as an undef element in a vector.
619 if (isa<UndefValue>(Val: VL[I]))
620 continue;
621 auto *EI = dyn_cast<ExtractElementInst>(Val: VL[I]);
622 if (!EI)
623 continue;
624 if (isa<ScalableVectorType>(Val: EI->getVectorOperandType()))
625 return std::nullopt;
626 auto *Vec = EI->getVectorOperand();
627 // We can extractelement from undef or poison vector.
628 if (isUndefVector</*isPoisonOnly=*/true>(V: Vec).all())
629 continue;
630 // All vector operands must have the same number of vector elements.
631 if (isa<UndefValue>(Val: Vec)) {
632 Mask[I] = I;
633 } else {
634 if (isa<UndefValue>(Val: EI->getIndexOperand()))
635 continue;
636 auto *Idx = dyn_cast<ConstantInt>(Val: EI->getIndexOperand());
637 if (!Idx)
638 return std::nullopt;
639 // Undefined behavior if Idx is negative or >= Size.
640 if (Idx->getValue().uge(RHS: Size))
641 continue;
642 unsigned IntIdx = Idx->getValue().getZExtValue();
643 Mask[I] = IntIdx;
644 }
645 if (isUndefVector(V: Vec).all() && HasNonUndefVec)
646 continue;
647 // For correct shuffling we have to have at most 2 different vector operands
648 // in all extractelement instructions.
649 if (!Vec1 || Vec1 == Vec) {
650 Vec1 = Vec;
651 } else if (!Vec2 || Vec2 == Vec) {
652 Vec2 = Vec;
653 Mask[I] += Size;
654 } else {
655 return std::nullopt;
656 }
657 if (CommonShuffleMode == Permute)
658 continue;
659 // If the extract index is not the same as the operation number, it is a
660 // permutation.
661 if (Mask[I] % Size != I) {
662 CommonShuffleMode = Permute;
663 continue;
664 }
665 CommonShuffleMode = Select;
666 }
667 // If we're not crossing lanes in different vectors, consider it as blending.
668 if (CommonShuffleMode == Select && Vec2)
669 return TargetTransformInfo::SK_Select;
670 // If Vec2 was never used, we have a permutation of a single vector, otherwise
671 // we have permutation of 2 vectors.
672 return Vec2 ? TargetTransformInfo::SK_PermuteTwoSrc
673 : TargetTransformInfo::SK_PermuteSingleSrc;
674}
675
676Value *createInsertVector(
677 IRBuilderBase &Builder, Value *Vec, Value *V, unsigned Index,
678 function_ref<Value *(Value *, Value *, ArrayRef<int>)> Generator) {
679 if (isa<PoisonValue>(Val: Vec) && isa<PoisonValue>(Val: V))
680 return Vec;
681 const unsigned SubVecVF = getNumElements(Ty: V->getType());
682 // Create shuffle, insertvector requires that index is multiple of
683 // the subvector length.
684 const unsigned VecVF = getNumElements(Ty: Vec->getType());
685 SmallVector<int> Mask(VecVF, PoisonMaskElem);
686 if (isa<PoisonValue>(Val: Vec)) {
687 auto *Begin = std::next(x: Mask.begin(), n: Index);
688 std::iota(first: Begin, last: std::next(x: Begin, n: SubVecVF), value: 0);
689 Vec = Builder.CreateShuffleVector(V, Mask);
690 return Vec;
691 }
692 std::iota(first: Mask.begin(), last: Mask.end(), value: 0);
693 std::iota(first: std::next(x: Mask.begin(), n: Index),
694 last: std::next(x: Mask.begin(), n: Index + SubVecVF), value: VecVF);
695 if (Generator)
696 return Generator(Vec, V, Mask);
697 // 1. Resize V to the size of Vec.
698 SmallVector<int> ResizeMask(VecVF, PoisonMaskElem);
699 std::iota(first: ResizeMask.begin(), last: std::next(x: ResizeMask.begin(), n: SubVecVF), value: 0);
700 V = Builder.CreateShuffleVector(V, Mask: ResizeMask);
701 // 2. Insert V into Vec.
702 return Builder.CreateShuffleVector(V1: Vec, V2: V, Mask);
703}
704
705Value *createExtractVector(IRBuilderBase &Builder, Value *Vec,
706 unsigned SubVecVF, unsigned Index) {
707 SmallVector<int> Mask(SubVecVF, PoisonMaskElem);
708 std::iota(first: Mask.begin(), last: Mask.end(), value: Index);
709 return Builder.CreateShuffleVector(V: Vec, Mask);
710}
711
712SmallBitVector buildUseMask(int VF, ArrayRef<int> Mask, UseMask MaskArg) {
713 SmallBitVector UseMask(VF, true);
714 for (auto [Idx, Value] : enumerate(First&: Mask)) {
715 if (Value == PoisonMaskElem) {
716 if (MaskArg == UseMask::UndefsAsMask)
717 UseMask.reset(Idx);
718 continue;
719 }
720 if (MaskArg == UseMask::FirstArg && Value < VF)
721 UseMask.reset(Idx: Value);
722 else if (MaskArg == UseMask::SecondArg && Value >= VF)
723 UseMask.reset(Idx: Value - VF);
724 }
725 return UseMask;
726}
727
728template <bool IsPoisonOnly>
729SmallBitVector isUndefVector(const Value *V, const SmallBitVector &UseMask) {
730 SmallBitVector Res(UseMask.empty() ? 1 : UseMask.size(), true);
731 using T = std::conditional_t<IsPoisonOnly, PoisonValue, UndefValue>;
732 if (isa<T>(V))
733 return Res;
734 auto *VecTy = dyn_cast<FixedVectorType>(Val: V->getType());
735 if (!VecTy)
736 return Res.reset();
737 auto *C = dyn_cast<Constant>(Val: V);
738 if (!C) {
739 if (!UseMask.empty()) {
740 const Value *Base = V;
741 while (auto *II = dyn_cast<InsertElementInst>(Val: Base)) {
742 Base = II->getOperand(i_nocapture: 0);
743 if (isa<T>(II->getOperand(i_nocapture: 1)))
744 continue;
745 std::optional<unsigned> Idx = getElementIndex(Inst: II);
746 if (!Idx) {
747 Res.reset();
748 return Res;
749 }
750 if (*Idx < UseMask.size() && !UseMask.test(Idx: *Idx))
751 Res.reset(Idx: *Idx);
752 }
753 // TODO: Add analysis for shuffles here too.
754 if (V == Base) {
755 Res.reset();
756 } else {
757 SmallBitVector SubMask(UseMask.size(), false);
758 Res &= isUndefVector<IsPoisonOnly>(Base, SubMask);
759 }
760 } else {
761 Res.reset();
762 }
763 return Res;
764 }
765 for (unsigned I = 0, E = VecTy->getNumElements(); I != E; ++I) {
766 if (Constant *Elem = C->getAggregateElement(Elt: I))
767 if (!isa<T>(Elem) &&
768 (UseMask.empty() || (I < UseMask.size() && !UseMask.test(Idx: I))))
769 Res.reset(Idx: I);
770 }
771 return Res;
772}
773
774template SmallBitVector isUndefVector<false>(const Value *,
775 const SmallBitVector &);
776template SmallBitVector isUndefVector<true>(const Value *,
777 const SmallBitVector &);
778
779bool doesInTreeUserNeedToExtract(Value *Scalar, Instruction *UserInst,
780 TargetLibraryInfo *TLI,
781 const TargetTransformInfo *TTI) {
782 if (!UserInst)
783 return false;
784 unsigned Opcode = UserInst->getOpcode();
785 switch (Opcode) {
786 case Instruction::Load: {
787 LoadInst *LI = cast<LoadInst>(Val: UserInst);
788 return (LI->getPointerOperand() == Scalar);
789 }
790 case Instruction::Store: {
791 StoreInst *SI = cast<StoreInst>(Val: UserInst);
792 return (SI->getPointerOperand() == Scalar);
793 }
794 case Instruction::Call: {
795 CallInst *CI = cast<CallInst>(Val: UserInst);
796 Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI);
797 return any_of(Range: enumerate(First: CI->args()), P: [&](auto &&Arg) {
798 return isVectorIntrinsicWithScalarOpAtArg(ID, Arg.index(), TTI) &&
799 Arg.value().get() == Scalar;
800 });
801 }
802 default:
803 return false;
804 }
805}
806
807MemoryLocation getLocation(Instruction *I) {
808 if (StoreInst *SI = dyn_cast<StoreInst>(Val: I))
809 return MemoryLocation::get(SI);
810 if (LoadInst *LI = dyn_cast<LoadInst>(Val: I))
811 return MemoryLocation::get(LI);
812 return MemoryLocation();
813}
814
815bool isSimple(Instruction *I) {
816 if (LoadInst *LI = dyn_cast<LoadInst>(Val: I))
817 return LI->isSimple();
818 if (StoreInst *SI = dyn_cast<StoreInst>(Val: I))
819 return SI->isSimple();
820 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Val: I))
821 return !MI->isVolatile();
822 return true;
823}
824
825bool isSelectedBaseLoad(Type *ScalarTy, ArrayRef<Value *> PointerOps,
826 const DataLayout &DL, Value *&TrueBase,
827 Value *&FalseBase,
828 SmallVectorImpl<Value *> &Conditions) {
829 TrueBase = nullptr;
830 FalseBase = nullptr;
831 uint64_t ScalarSize = DL.getTypeStoreSize(Ty: ScalarTy);
832 Conditions.assign(NumElts: PointerOps.size(), Elt: nullptr);
833 for (auto [Idx, P] : enumerate(First&: PointerOps)) {
834 Value *Base = P;
835 uint64_t Offset = 0;
836 if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: P)) {
837 APInt OffsetAP(DL.getIndexTypeSizeInBits(Ty: GEP->getType()), 0);
838 if (!GEP->accumulateConstantOffset(DL, Offset&: OffsetAP) || OffsetAP.isNegative())
839 return false;
840 Offset = OffsetAP.getZExtValue();
841 Base = GEP->getPointerOperand();
842 }
843 auto *Sel = dyn_cast<SelectInst>(Val: Base);
844 if (!Sel)
845 return false;
846 Value *T = Sel->getTrueValue();
847 Value *F = Sel->getFalseValue();
848 if (!TrueBase) {
849 if (T == F)
850 return false;
851 TrueBase = T;
852 FalseBase = F;
853 } else if (TrueBase != T || FalseBase != F) {
854 return false;
855 }
856 // Lane Idx must be at exactly Base + Idx * sizeof(ScalarTy); codegen reads
857 // contiguously from TrueBase/FalseBase starting at lane 0.
858 if (Offset != static_cast<uint64_t>(Idx) * ScalarSize)
859 return false;
860 Conditions[Idx] = Sel->getCondition();
861 }
862 return TrueBase != nullptr;
863}
864
865void addMask(SmallVectorImpl<int> &Mask, ArrayRef<int> SubMask,
866 bool ExtendingManyInputs) {
867 if (SubMask.empty())
868 return;
869 assert(
870 (!ExtendingManyInputs || SubMask.size() > Mask.size() ||
871 // Check if input scalars were extended to match the size of other node.
872 (SubMask.size() == Mask.size() && Mask.back() == PoisonMaskElem)) &&
873 "SubMask with many inputs support must be larger than the mask.");
874 if (Mask.empty()) {
875 Mask.append(in_start: SubMask.begin(), in_end: SubMask.end());
876 return;
877 }
878 SmallVector<int> NewMask(SubMask.size(), PoisonMaskElem);
879 int TermValue = std::min(a: Mask.size(), b: SubMask.size());
880 for (int I = 0, E = SubMask.size(); I < E; ++I) {
881 if (SubMask[I] == PoisonMaskElem ||
882 (!ExtendingManyInputs &&
883 (SubMask[I] >= TermValue || Mask[SubMask[I]] >= TermValue)))
884 continue;
885 NewMask[I] = Mask[SubMask[I]];
886 }
887 Mask.swap(RHS&: NewMask);
888}
889
890void fixupOrderingIndices(MutableArrayRef<unsigned> Order) {
891 const size_t Sz = Order.size();
892 SmallBitVector UnusedIndices(Sz, /*t=*/true);
893 SmallBitVector MaskedIndices(Sz);
894 for (unsigned I = 0; I < Sz; ++I) {
895 if (Order[I] < Sz)
896 UnusedIndices.reset(Idx: Order[I]);
897 else
898 MaskedIndices.set(I);
899 }
900 if (MaskedIndices.none())
901 return;
902 assert(UnusedIndices.count() == MaskedIndices.count() &&
903 "Non-synced masked/available indices.");
904 int Idx = UnusedIndices.find_first();
905 int MIdx = MaskedIndices.find_first();
906 while (MIdx >= 0) {
907 assert(Idx >= 0 && "Indices must be synced.");
908 Order[MIdx] = Idx;
909 Idx = UnusedIndices.find_next(Prev: Idx);
910 MIdx = MaskedIndices.find_next(Prev: MIdx);
911 }
912}
913
914SmallBitVector getAltInstrMask(ArrayRef<Value *> VL, Type *ScalarTy,
915 unsigned Opcode0, unsigned Opcode1) {
916 unsigned ScalarTyNumElements = getNumElements(Ty: ScalarTy);
917 SmallBitVector OpcodeMask(VL.size() * ScalarTyNumElements, false);
918 for (unsigned Lane : seq<unsigned>(Size: VL.size())) {
919 if (isa<PoisonValue>(Val: VL[Lane]))
920 continue;
921 if (cast<Instruction>(Val: VL[Lane])->getOpcode() == Opcode1)
922 OpcodeMask.set(I: Lane * ScalarTyNumElements,
923 E: Lane * ScalarTyNumElements + ScalarTyNumElements);
924 }
925 return OpcodeMask;
926}
927
928SmallVector<Constant *> replicateMask(ArrayRef<Constant *> Val, unsigned VF) {
929 assert(none_of(Val, [](Constant *C) { return C->getType()->isVectorTy(); }) &&
930 "Expected scalar constants.");
931 SmallVector<Constant *> NewVal(Val.size() * VF);
932 for (auto [I, V] : enumerate(First&: Val))
933 std::fill_n(first: NewVal.begin() + I * VF, n: VF, value: V);
934 return NewVal;
935}
936
937Intrinsic::ID getMaskedDivRemIntrinsic(unsigned Opcode) {
938 switch (Opcode) {
939 case Instruction::UDiv:
940 return Intrinsic::masked_udiv;
941 case Instruction::SDiv:
942 return Intrinsic::masked_sdiv;
943 case Instruction::URem:
944 return Intrinsic::masked_urem;
945 case Instruction::SRem:
946 return Intrinsic::masked_srem;
947 default:
948 llvm_unreachable("Unexpected opcode");
949 }
950}
951
952/// Returns true if \p I is a part of a single-use chain, computing an address,
953/// which does not pay off the vectorization: a constant table is accessed by a
954/// gather, while the indices, unrelated between the lanes, require a full
955/// buildvector, unlike the ones, shifted by a constant from a common base.
956static bool isNonProfitableIndex(const Instruction *I) {
957 constexpr unsigned MaxIndexChainLength = 3;
958 // A constant shift of a common base is a cheap buildvector, while the loads
959 // are vectorized together with the indices, computed from them.
960 auto IsProfitableOperand = [](const Value *V) {
961 if (isa<Constant>(Val: V))
962 return true;
963 if (const auto *Cast = dyn_cast<CastInst>(Val: V); Cast && Cast->hasOneUse())
964 V = Cast->getOperand(i_nocapture: 0);
965 return isa<LoadInst>(Val: V);
966 };
967 const User *U = I->user_back();
968 for ([[maybe_unused]] unsigned _ : seq<unsigned>(Size: MaxIndexChainLength)) {
969 if (const auto *GEP = dyn_cast<GetElementPtrInst>(Val: U))
970 return isa<Constant>(Val: GEP->getPointerOperand()) ||
971 none_of(Range: I->operand_values(), P: IsProfitableOperand);
972 if (!isa<Instruction>(Val: U) || !U->hasOneUse())
973 return false;
974 U = U->user_back();
975 }
976 return false;
977}
978
979bool isOnceUsedSeed(const Instruction *I) {
980 if (!I->hasOneUse() || isNonProfitableIndex(I))
981 return false;
982 // The operation with the identity or the absorbing constant is folded away
983 // before the codegen, the vector node only repacks the lanes.
984 if (const auto *BO = dyn_cast<BinaryOperator>(Val: I)) {
985 unsigned Opcode = BO->getOpcode();
986 Type *Ty = BO->getType();
987 for (unsigned Idx : seq<unsigned>(Size: 2)) {
988 const auto *C = dyn_cast<Constant>(Val: BO->getOperand(i_nocapture: Idx));
989 if (C && (C == ConstantExpr::getBinOpIdentity(
990 Opcode, Ty, /*AllowRHSConstant=*/Idx == 1) ||
991 C == ConstantExpr::getBinOpAbsorber(
992 Opcode, Ty, /*AllowLHSConstant=*/Idx == 0)))
993 return false;
994 }
995 }
996 const User *U = I->user_back();
997 if (isa<ExtractElementInst, ExtractValueInst>(Val: I))
998 return isa<InsertElementInst, InsertValueInst>(Val: U);
999 if (isa<CastInst>(Val: I))
1000 return !isa<FPToSIInst, FPToUIInst>(Val: I) &&
1001 (!isa<CastInst>(Val: U) || U->hasOneUse());
1002 return isa<BinaryOperator, UnaryOperator, SelectInst, FreezeInst, CallInst>(
1003 Val: I);
1004}
1005
1006Instruction *lookThroughCastRoundTrip(Value *V, bool MustBeElidable) {
1007 auto *Wide = dyn_cast<FPExtInst>(Val: V);
1008 if (!Wide || !Wide->hasOneUse())
1009 return nullptr;
1010 auto *Narrow = dyn_cast<FPTruncInst>(Val: Wide->getOperand(i_nocapture: 0));
1011 if (!Narrow || !Narrow->hasOneUse())
1012 return nullptr;
1013 Value *Src = Narrow->getOperand(i_nocapture: 0);
1014 if (!isa<Instruction>(Val: Src) || Src->getType() != Wide->getType())
1015 return nullptr;
1016 if (MustBeElidable && !(Wide->hasAllowContract() && Wide->hasNoNaNs() &&
1017 Wide->hasNoInfs() && Narrow->hasAllowContract()))
1018 return nullptr;
1019 return Narrow;
1020}
1021
1022namespace {
1023
1024/// Shifts and the mask accumulated from the narrow ops on the current path:
1025/// the shifts above and at the narrow level, the bitwidth of the narrow ops
1026/// (0 if none) and the mask from the absorbed narrow ands.
1027struct NarrowedChainState {
1028 unsigned Shift = 0;
1029 unsigned NarrowShift = 0;
1030 unsigned NarrowBW = 0;
1031 APInt NarrowMask = APInt(1, 0);
1032
1033 /// The mask for the absorbed narrow ops in the leaf type, applied before
1034 /// widening and shifting; all-ones if nothing was absorbed.
1035 APInt getMask(unsigned LeafBW) const {
1036 if (NarrowBW == 0)
1037 return APInt::getAllOnes(numBits: LeafBW);
1038 return (NarrowMask & (APInt::getAllOnes(numBits: NarrowBW) << NarrowShift))
1039 .lshr(shiftAmt: NarrowShift)
1040 .trunc(width: LeafBW);
1041 }
1042};
1043
1044} // namespace
1045
1046static void
1047collectNarrowedLeavesImpl(Value *V, unsigned RdxOpcode, unsigned WideBW,
1048 NarrowedChainState S, unsigned Depth,
1049 unsigned MaxDepth,
1050 SmallVectorImpl<NarrowedLeafInfo> &Leaves,
1051 SmallVectorImpl<Instruction *> &ChainInsts) {
1052 if (Depth < MaxDepth) {
1053 if (auto *Z = dyn_cast<ZExtInst>(Val: V);
1054 Z && Z->getSrcTy()->isIntegerTy() && !Z->getSrcTy()->isIntegerTy(BitWidth: 1)) {
1055 ChainInsts.push_back(Elt: Z);
1056 return collectNarrowedLeavesImpl(V: Z->getOperand(i_nocapture: 0), RdxOpcode, WideBW, S,
1057 Depth: Depth + 1, MaxDepth, Leaves, ChainInsts);
1058 }
1059 if (auto *BO = dyn_cast<BinaryOperator>(Val: V)) {
1060 if (BO->getOpcode() == RdxOpcode) {
1061 ChainInsts.push_back(Elt: BO);
1062 collectNarrowedLeavesImpl(V: BO->getOperand(i_nocapture: 0), RdxOpcode, WideBW, S,
1063 Depth: Depth + 1, MaxDepth, Leaves, ChainInsts);
1064 collectNarrowedLeavesImpl(V: BO->getOperand(i_nocapture: 1), RdxOpcode, WideBW, S,
1065 Depth: Depth + 1, MaxDepth, Leaves, ChainInsts);
1066 return;
1067 }
1068 const APInt *Amt;
1069 unsigned BW = V->getType()->getScalarSizeInBits();
1070 auto *Z = dyn_cast<ZExtInst>(Val: BO->getOperand(i_nocapture: 0));
1071 if (BO->getOpcode() == Instruction::Shl && Z && S.NarrowBW == 0 &&
1072 match(V: BO->getOperand(i_nocapture: 1), P: m_APInt(Res&: Amt)) && Amt->ult(RHS: BW) &&
1073 Z->getSrcTy()->isIntegerTy() && !Z->getSrcTy()->isIntegerTy(BitWidth: 1) &&
1074 (BW == WideBW ||
1075 Z->getSrcTy()->getIntegerBitWidth() + Amt->getZExtValue() <= BW) &&
1076 S.Shift + Amt->getZExtValue() < WideBW) {
1077 ChainInsts.push_back(Elt: BO);
1078 ChainInsts.push_back(Elt: Z);
1079 S.Shift += Amt->getZExtValue();
1080 return collectNarrowedLeavesImpl(V: Z->getOperand(i_nocapture: 0), RdxOpcode, WideBW, S,
1081 Depth: Depth + 1, MaxDepth, Leaves,
1082 ChainInsts);
1083 }
1084 // Narrow shls fold into the shift and narrow ands into the mask; the
1085 // mask clears the bits the shls shift out. Only same-width ops compose
1086 // on one path, and the combined shift must stay a valid shift amount in
1087 // both types.
1088 if (BW < WideBW && (S.NarrowBW == 0 || BW == S.NarrowBW)) {
1089 if (BO->getOpcode() == Instruction::Shl &&
1090 match(V: BO->getOperand(i_nocapture: 1), P: m_APInt(Res&: Amt)) && Amt->ult(RHS: BW) &&
1091 S.NarrowShift + Amt->getZExtValue() < BW &&
1092 S.Shift + S.NarrowShift + Amt->getZExtValue() < WideBW) {
1093 ChainInsts.push_back(Elt: BO);
1094 if (BO->hasNoUnsignedWrap() && S.NarrowBW == 0) {
1095 S.Shift += Amt->getZExtValue();
1096 // Lossless shls shift out only known-zero bits; record them as
1097 // the mask so matching lanes can form a splat.
1098 S.NarrowBW = BW;
1099 S.NarrowMask = APInt::getLowBitsSet(numBits: BW, loBitsSet: BW - Amt->getZExtValue());
1100 } else {
1101 if (S.NarrowBW == 0) {
1102 S.NarrowBW = BW;
1103 S.NarrowMask = APInt::getAllOnes(numBits: BW);
1104 }
1105 S.NarrowShift += Amt->getZExtValue();
1106 }
1107 return collectNarrowedLeavesImpl(V: BO->getOperand(i_nocapture: 0), RdxOpcode, WideBW,
1108 S, Depth: Depth + 1, MaxDepth, Leaves,
1109 ChainInsts);
1110 }
1111 Value *X;
1112 if (match(V: BO, P: m_c_And(L: m_Value(V&: X), R: m_APInt(Res&: Amt)))) {
1113 ChainInsts.push_back(Elt: BO);
1114 if (S.NarrowBW == 0) {
1115 S.NarrowBW = BW;
1116 S.NarrowMask = APInt::getAllOnes(numBits: BW);
1117 }
1118 S.NarrowMask &= *Amt << S.NarrowShift;
1119 return collectNarrowedLeavesImpl(V: X, RdxOpcode, WideBW, S, Depth: Depth + 1,
1120 MaxDepth, Leaves, ChainInsts);
1121 }
1122 }
1123 }
1124 }
1125 Leaves.emplace_back(Args&: V, Args: S.Shift + S.NarrowShift,
1126 Args: S.getMask(LeafBW: V->getType()->getScalarSizeInBits()));
1127}
1128
1129void collectNarrowedLeaves(Value *V, unsigned RdxOpcode, unsigned WideBW,
1130 unsigned MaxDepth,
1131 SmallVectorImpl<NarrowedLeafInfo> &Leaves,
1132 SmallVectorImpl<Instruction *> &ChainInsts) {
1133 collectNarrowedLeavesImpl(V, RdxOpcode, WideBW, S: NarrowedChainState(),
1134 /*Depth=*/0, MaxDepth, Leaves, ChainInsts);
1135}
1136
1137TargetTransformInfo::TargetCostKind getSLPCostKind(const Function *F) {
1138 assert(F && "Expected function.");
1139 return F->hasOptSize() ? TTI::TCK_CodeSize : TTI::TCK_RecipThroughput;
1140}
1141
1142/// Deeper than the standard analysis recursion depth to keep the numeric
1143/// bound precise through arithmetic carry chains.
1144constexpr unsigned MaxBitPackAnalysisDepth = MaxAnalysisRecursionDepth + 2;
1145
1146APInt getScalarMaxValue(const Value *V, unsigned Depth) {
1147 unsigned BitWidth = V->getType()->getScalarSizeInBits();
1148 const APInt Unknown = APInt::getAllOnes(numBits: BitWidth);
1149 if (Depth > MaxBitPackAnalysisDepth || !V->getType()->isIntegerTy())
1150 return Unknown;
1151 const APInt *C, *Amt;
1152 if (match(V, P: m_APInt(Res&: C)))
1153 return *C;
1154 Value *L, *R;
1155 if (match(V, P: m_Add(L: m_Value(V&: L), R: m_Value(V&: R))) ||
1156 match(V, P: m_Or(L: m_Value(V&: L), R: m_Value(V&: R))) ||
1157 match(V, P: m_Xor(L: m_Value(V&: L), R: m_Value(V&: R))))
1158 return getScalarMaxValue(V: L, Depth: Depth + 1)
1159 .uadd_sat(RHS: getScalarMaxValue(V: R, Depth: Depth + 1));
1160 if (match(V, P: m_NUWSub(L: m_Value(V&: L), R: m_Value(V&: R))))
1161 return getScalarMaxValue(V: L, Depth: Depth + 1);
1162 if (match(V, P: m_Mul(L: m_Value(V&: L), R: m_Value(V&: R))))
1163 return getScalarMaxValue(V: L, Depth: Depth + 1)
1164 .umul_sat(RHS: getScalarMaxValue(V: R, Depth: Depth + 1));
1165 if (match(V, P: m_And(L: m_Value(V&: L), R: m_Value(V&: R))))
1166 return APIntOps::umin(A: getScalarMaxValue(V: L, Depth: Depth + 1),
1167 B: getScalarMaxValue(V: R, Depth: Depth + 1));
1168 if (match(V, P: m_LShr(L: m_Value(V&: L), R: m_APInt(Res&: Amt))) && Amt->ult(RHS: BitWidth))
1169 return getScalarMaxValue(V: L, Depth: Depth + 1).lshr(ShiftAmt: *Amt);
1170 if (match(V, P: m_Shl(L: m_Value(V&: L), R: m_APInt(Res&: Amt))) && Amt->ult(RHS: BitWidth)) {
1171 APInt LMax = getScalarMaxValue(V: L, Depth: Depth + 1);
1172 return LMax.getActiveBits() + Amt->getZExtValue() <= BitWidth
1173 ? LMax.shl(ShiftAmt: *Amt)
1174 : Unknown;
1175 }
1176 if (match(V, P: m_ZExt(Op: m_Value(V&: L))))
1177 return getScalarMaxValue(V: L, Depth: Depth + 1).zext(width: BitWidth);
1178 if (match(V, P: m_Trunc(Op: m_Value(V&: L)))) {
1179 APInt Max = getScalarMaxValue(V: L, Depth: Depth + 1);
1180 return Max.getActiveBits() <= BitWidth ? Max.trunc(width: BitWidth) : Unknown;
1181 }
1182 if (match(V, P: m_SExt(Op: m_Value(V&: L)))) {
1183 APInt Max = getScalarMaxValue(V: L, Depth: Depth + 1);
1184 return Max.isNonNegative() ? Max.zext(width: BitWidth) : Unknown;
1185 }
1186 Value *F;
1187 if (match(V, P: m_Select(C: m_Value(), L: m_Value(V&: L), R: m_Value(V&: F))))
1188 return APIntOps::umax(A: getScalarMaxValue(V: L, Depth: Depth + 1),
1189 B: getScalarMaxValue(V: F, Depth: Depth + 1));
1190 return Unknown;
1191}
1192
1193std::optional<BitPackInfo> computeBitPackInfo(unsigned BitWidth,
1194 ArrayRef<APInt> PossibleBits,
1195 ArrayRef<uint64_t> ShlAmts,
1196 ArrayRef<APInt> Masks) {
1197 unsigned NumElts = PossibleBits.size();
1198 BitPackInfo Info;
1199 Info.LShrAmts.assign(NumElts, Elt: 0);
1200 for (unsigned Idx : seq(Size: NumElts)) {
1201 APInt Possible = PossibleBits[Idx].shl(shiftAmt: ShlAmts[Idx]) & Masks[Idx];
1202 if (Possible.isZero())
1203 continue;
1204 unsigned Lo, W;
1205 if (!Possible.isShiftedMask(MaskIdx&: Lo, MaskLen&: W))
1206 return std::nullopt;
1207 if (Info.FieldWidth == 0) {
1208 if (W % 8 != 0 || BitWidth % W != 0)
1209 return std::nullopt;
1210 Info.FieldWidth = W;
1211 Info.LaneOfField.assign(NumElts: BitWidth / W, Elt: BitPackInfo::NoLane);
1212 }
1213 if (W != Info.FieldWidth || Lo % W != 0)
1214 return std::nullopt;
1215 unsigned Field = Lo / W;
1216 if (Info.LaneOfField[Field] != BitPackInfo::NoLane)
1217 return std::nullopt;
1218 Info.LaneOfField[Field] = Idx;
1219 Info.LShrAmts[Idx] = Lo - ShlAmts[Idx];
1220 }
1221 if (Info.FieldWidth == 0)
1222 return std::nullopt;
1223 return Info;
1224}
1225
1226SmallVector<int> getBitPackMask(const BitPackInfo &Info, unsigned NumBytes,
1227 unsigned NumElts, unsigned BytesPerLane) {
1228 unsigned BytesPerField = Info.FieldWidth / 8;
1229 SmallVector<int> Mask;
1230 for (unsigned J : seq(Size: NumBytes)) {
1231 unsigned Lane = Info.LaneOfField[J / BytesPerField];
1232 Mask.push_back(Elt: Lane == BitPackInfo::NoLane
1233 ? (int)(NumElts * BytesPerLane)
1234 : (int)(Lane * BytesPerLane + J % BytesPerField));
1235 }
1236 return Mask;
1237}
1238
1239Value *buildBitPack(IRBuilderBase &Builder, Value *X, const BitPackInfo &Info,
1240 unsigned ShiftWidth, unsigned &NumInsts) {
1241 NumInsts = 0;
1242 auto *VecTy = cast<FixedVectorType>(Val: X->getType());
1243 unsigned BitWidth = VecTy->getScalarSizeInBits();
1244 assert(BitWidth % 8 == 0 &&
1245 "The byte-multiple field width divides the result bit width.");
1246 unsigned NumElts = VecTy->getNumElements();
1247 Value *Y = X;
1248 if (ShiftWidth != BitWidth) {
1249 // Compacting a zext back to its source is free, use it directly.
1250 if (auto *Z = dyn_cast<ZExtInst>(Val: X);
1251 Z && Z->getSrcTy()->getScalarSizeInBits() == ShiftWidth)
1252 Y = Z->getOperand(i_nocapture: 0);
1253 else {
1254 Y = Builder.CreateTrunc(
1255 V: Y, DestTy: FixedVectorType::get(ElementType: IntegerType::get(C&: X->getContext(), NumBits: ShiftWidth),
1256 NumElts));
1257 ++NumInsts;
1258 }
1259 }
1260 if (Info.needsShift()) {
1261 SmallVector<Constant *> Amts;
1262 for (uint64_t A : Info.LShrAmts)
1263 Amts.push_back(
1264 Elt: ConstantInt::get(Ty: IntegerType::get(C&: X->getContext(), NumBits: ShiftWidth), V: A));
1265 Y = Builder.CreateLShr(LHS: Y, RHS: ConstantVector::get(V: Amts));
1266 ++NumInsts;
1267 }
1268 unsigned InBytes = NumElts * (ShiftWidth / 8);
1269 auto *ByteTy = FixedVectorType::get(ElementType: Builder.getInt8Ty(), NumElts: InBytes);
1270 SmallVector<int> Mask =
1271 getBitPackMask(Info, NumBytes: BitWidth / 8, NumElts, BytesPerLane: ShiftWidth / 8);
1272 auto *IntTy = IntegerType::get(C&: X->getContext(), NumBits: BitWidth);
1273 // A plain byte reversal of the shifted lanes is a bswap.
1274 if (ShuffleVectorInst::isReverseMask(Mask, NumSrcElts: InBytes)) {
1275 NumInsts += 2;
1276 return Builder.CreateUnaryIntrinsic(ID: Intrinsic::bswap,
1277 Op: Builder.CreateBitCast(V: Y, DestTy: IntTy));
1278 }
1279 // An identity byte order needs no shuffle.
1280 if (ShuffleVectorInst::isIdentityMask(Mask, NumSrcElts: InBytes)) {
1281 ++NumInsts;
1282 return Builder.CreateBitCast(V: Y, DestTy: IntTy);
1283 }
1284 Value *Packed = Builder.CreateShuffleVector(
1285 V1: Builder.CreateBitCast(V: Y, DestTy: ByteTy),
1286 V2: is_contained(Range: Info.LaneOfField, Element: BitPackInfo::NoLane)
1287 ? Constant::getNullValue(Ty: ByteTy)
1288 : PoisonValue::get(T: ByteTy),
1289 Mask);
1290 NumInsts += 3;
1291 return Builder.CreateBitCast(V: Packed, DestTy: IntTy);
1292}
1293
1294} // namespace llvm::slpvectorizer
1295