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#include "SLPMemoryUtils.h"
11
12#include "llvm/ADT/APInt.h"
13#include "llvm/ADT/STLExtras.h"
14#include "llvm/ADT/Sequence.h"
15#include "llvm/ADT/SmallPtrSet.h"
16#include "llvm/Analysis/AssumptionCache.h"
17#include "llvm/Analysis/LoopInfo.h"
18#include "llvm/Analysis/ScalarEvolution.h"
19#include "llvm/Analysis/ValueTracking.h"
20#include "llvm/Analysis/VectorUtils.h"
21#include "llvm/IR/Constants.h"
22#include "llvm/IR/DataLayout.h"
23#include "llvm/IR/DebugInfo.h"
24#include "llvm/IR/DebugLoc.h"
25#include "llvm/IR/DerivedTypes.h"
26#include "llvm/IR/IRBuilder.h"
27#include "llvm/IR/Instructions.h"
28#include "llvm/IR/IntrinsicInst.h"
29#include "llvm/IR/PatternMatch.h"
30#include "llvm/Support/Casting.h"
31#include "llvm/Support/ErrorHandling.h"
32#include "llvm/Support/MathExtras.h"
33#include "llvm/Support/raw_ostream.h"
34#include "llvm/Transforms/Utils/LoopUtils.h"
35
36#include <algorithm>
37#include <numeric>
38#include <optional>
39#include <string>
40#include <type_traits>
41
42using namespace llvm;
43using namespace llvm::PatternMatch;
44
45namespace llvm::slpvectorizer {
46
47bool isConstant(Value *V) {
48 return isa<Constant>(Val: V) && !isa<ConstantExpr, GlobalValue>(Val: V);
49}
50
51bool isBinOpIdentityConstant(const Value *V, unsigned Opcode) {
52 const auto *CI = dyn_cast<ConstantInt>(Val: V);
53 return CI && ConstantExpr::getBinOpIdentity(Opcode, Ty: CI->getType()) == CI;
54}
55
56bool isUndefTolerantBinOp(const Value *V) {
57 const BinaryOperator *BO;
58 return match(V, P: m_BinOp(I&: BO)) && BO->getType()->isIntOrIntVectorTy() &&
59 !BO->isShift() && !BO->isIntDivRem();
60}
61
62const LoadInst *getLoadOfUndefTolerantBinOp(const Value *V) {
63 if (!isUndefTolerantBinOp(V))
64 return nullptr;
65 for (const Value *Op : cast<BinaryOperator>(Val: V)->operands())
66 if (const auto *LI = dyn_cast<LoadInst>(Val: Op))
67 return LI;
68 return nullptr;
69}
70
71unsigned getReassocCombineOpcode(unsigned Opcode) {
72 switch (Opcode) {
73 case Instruction::Sub:
74 return Instruction::Add;
75 case Instruction::FSub:
76 return Instruction::FAdd;
77 default:
78 return Opcode;
79 }
80}
81
82bool isReassocChainLink(const Instruction *I) {
83 if (I->getOpcode() == Instruction::Sub)
84 return true;
85 if (I->getOpcode() == Instruction::FSub)
86 return I->hasAllowReassoc();
87 return I->isAssociative();
88}
89
90bool isVectorLikeInstWithConstOps(Value *V) {
91 auto *I = dyn_cast<Instruction>(Val: V);
92 // Non-instructions are vector-like only if they are undef.
93 if (!I)
94 return isa<UndefValue>(Val: V);
95 switch (I->getOpcode()) {
96 case Instruction::ExtractValue:
97 case Instruction::InsertValue:
98 return true;
99 case Instruction::ExtractElement:
100 return isa<FixedVectorType>(Val: I->getOperand(i: 0)->getType()) &&
101 isConstant(V: I->getOperand(i: 1));
102 case Instruction::InsertElement:
103 return isa<FixedVectorType>(Val: I->getOperand(i: 0)->getType()) &&
104 isConstant(V: I->getOperand(i: 2));
105 default:
106 return false;
107 }
108}
109
110unsigned getNumElements(Type *Ty) {
111 assert(!isa<ScalableVectorType>(Ty) &&
112 "ScalableVectorType is not supported.");
113 if (isVectorizedTy(Ty))
114 return getVectorizedTypeVF(Ty).getFixedValue();
115 return 1;
116}
117
118unsigned getPartNumElems(unsigned Size, unsigned NumParts) {
119 return std::min<unsigned>(a: Size, b: bit_ceil(Value: divideCeil(Numerator: Size, Denominator: NumParts)));
120}
121
122unsigned getNumElems(unsigned Size, unsigned PartNumElems, unsigned Part) {
123 return std::min<unsigned>(a: PartNumElems, b: Size - Part * PartNumElems);
124}
125
126#if !defined(NDEBUG)
127std::string shortBundleName(ArrayRef<Value *> VL, int Idx) {
128 std::string Result;
129 raw_string_ostream OS(Result);
130 if (Idx >= 0)
131 OS << "Idx: " << Idx << ", ";
132 OS << "n=" << VL.size() << " [" << *VL.front() << ", ..]";
133 return Result;
134}
135#endif
136
137bool allSameBlock(ArrayRef<Value *> VL) {
138 auto *It = find_if(Range&: VL, P: IsaPred<Instruction>);
139 if (It == VL.end())
140 return false;
141 Instruction *I0 = cast<Instruction>(Val: *It);
142 if (all_of(Range&: VL, P: isVectorLikeInstWithConstOps))
143 return true;
144
145 BasicBlock *BB = I0->getParent();
146 for (Value *V : make_filter_range(Range: iterator_range(It, VL.end()), Pred: [](Value *V) {
147 return !isa<PoisonValue>(Val: V);
148 })) {
149 auto *II = dyn_cast<Instruction>(Val: V);
150 if (!II)
151 return false;
152
153 if (BB != II->getParent())
154 return false;
155 }
156 return true;
157}
158
159bool allConstant(ArrayRef<Value *> VL) {
160 // Constant expressions and globals can't be vectorized like normal integer/FP
161 // constants.
162 return all_of(Range&: VL, P: isConstant);
163}
164
165bool isSplat(ArrayRef<Value *> VL) {
166 Value *FirstNonUndef = nullptr;
167 for (Value *V :
168 make_filter_range(Range&: VL, Pred: [](Value *V) { return !isa<UndefValue>(Val: V); })) {
169 if (!FirstNonUndef) {
170 FirstNonUndef = V;
171 continue;
172 }
173 if (V != FirstNonUndef)
174 return false;
175 }
176 return FirstNonUndef != nullptr;
177}
178
179Intrinsic::ID isEquivalentIntrinsicID(Intrinsic::ID LHS, Intrinsic::ID RHS) {
180 if (LHS == RHS)
181 return RHS;
182 if ((LHS == Intrinsic::fma || LHS == Intrinsic::fmuladd) &&
183 (RHS == Intrinsic::fma || RHS == Intrinsic::fmuladd))
184 return Intrinsic::fma;
185 return Intrinsic::not_intrinsic;
186}
187
188bool isCommutative(const Instruction *I, const Value *ValWithUses,
189 bool IsCopyable) {
190 // The trunc X to i1 lanes of a compare have the single operand X.
191 if (auto *Cmp = dyn_cast<CmpInst>(Val: I))
192 return isa<CmpInst>(Val: ValWithUses) && Cmp->isCommutative();
193 if (auto *BO = dyn_cast<BinaryOperator>(Val: I))
194 return BO->isCommutative() ||
195 (BO->getOpcode() == Instruction::Sub && ValWithUses->hasUseList() &&
196 !ValWithUses->hasNUsesOrMore(N: UsesLimit) &&
197 all_of(
198 Range: ValWithUses->uses(),
199 P: [&](const Use &U) {
200 // Commutative, if icmp eq/ne sub, 0
201 CmpPredicate Pred;
202 if (match(V: U.getUser(),
203 P: m_ICmp(Pred, L: m_Specific(V: U.get()), R: m_Zero())) &&
204 (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE))
205 return true;
206 // Commutative, if abs(sub nsw, true) or abs(sub, false).
207 ConstantInt *Flag;
208 auto *I = dyn_cast<BinaryOperator>(Val: U.get());
209 return match(V: U.getUser(),
210 P: m_Intrinsic<Intrinsic::abs>(
211 Ops: m_Specific(V: U.get()), Ops: m_ConstantInt(CI&: Flag))) &&
212 ((!IsCopyable && I && !I->hasNoSignedWrap()) ||
213 Flag->isOne());
214 })) ||
215 (BO->getOpcode() == Instruction::FSub && ValWithUses->hasUseList() &&
216 !ValWithUses->hasNUsesOrMore(N: UsesLimit) &&
217 all_of(Range: ValWithUses->uses(), P: [](const Use &U) {
218 return match(V: U.getUser(),
219 P: m_Intrinsic<Intrinsic::fabs>(Ops: m_Specific(V: U.get())));
220 }));
221 return I->isCommutative();
222}
223
224bool isCommutative(const Instruction *I) { return isCommutative(I, ValWithUses: I); }
225
226bool isCommutableOperand(const Instruction *I, Value *ValWithUses, unsigned Op,
227 bool IsCopyable) {
228 assert(isCommutative(I, ValWithUses, IsCopyable) &&
229 "The instruction is not commutative.");
230 if (isa<CmpInst>(Val: I))
231 return true;
232 if (auto *BO = dyn_cast<BinaryOperator>(Val: I)) {
233 switch (BO->getOpcode()) {
234 case Instruction::Sub:
235 case Instruction::FSub:
236 return true;
237 default:
238 break;
239 }
240 }
241 return I->isCommutableOperand(Op);
242}
243
244unsigned getNumberOfPotentiallyCommutativeOps(Instruction *I) {
245 if (isa<IntrinsicInst>(Val: I) && isCommutative(I)) {
246 // IntrinsicInst::isCommutative returns true if swapping the first "two"
247 // arguments to the intrinsic produces the same result.
248 constexpr unsigned IntrinsicNumOperands = 2;
249 return IntrinsicNumOperands;
250 }
251 return I->getNumOperands();
252}
253
254std::optional<unsigned> getElementIndex(const Value *Inst, unsigned Offset) {
255 if (auto Index = getInsertExtractIndex<InsertElementInst>(Inst, Offset))
256 return Index;
257 if (auto Index = getInsertExtractIndex<ExtractElementInst>(Inst, Offset))
258 return Index;
259
260 unsigned Index = Offset;
261
262 const auto *IV = dyn_cast<InsertValueInst>(Val: Inst);
263 if (!IV)
264 return std::nullopt;
265
266 Type *CurrentType = IV->getType();
267 for (unsigned I : IV->indices()) {
268 if (const auto *ST = dyn_cast<StructType>(Val: CurrentType)) {
269 Index *= ST->getNumElements();
270 CurrentType = ST->getElementType(N: I);
271 } else if (const auto *AT = dyn_cast<ArrayType>(Val: CurrentType)) {
272 Index *= AT->getNumElements();
273 CurrentType = AT->getElementType();
274 } else {
275 return std::nullopt;
276 }
277 Index += I;
278 }
279 return Index;
280}
281
282bool allSameOpcode(ArrayRef<Value *> VL) {
283 auto *It = find_if(Range&: VL, P: IsaPred<Instruction>);
284 if (It == VL.end())
285 return true;
286 Instruction *MainOp = cast<Instruction>(Val: *It);
287 unsigned Opcode = MainOp->getOpcode();
288 bool IsCmpOp = isa<CmpInst>(Val: MainOp);
289 CmpInst::Predicate BasePred = IsCmpOp ? cast<CmpInst>(Val: MainOp)->getPredicate()
290 : CmpInst::BAD_ICMP_PREDICATE;
291 return all_of(Range: make_range(x: It, y: VL.end()), P: [&](Value *V) {
292 if (auto *CI = dyn_cast<CmpInst>(Val: V))
293 return BasePred == CI->getPredicate();
294 if (auto *I = dyn_cast<Instruction>(Val: V))
295 return I->getOpcode() == Opcode;
296 return isa<PoisonValue>(Val: V);
297 });
298}
299
300std::optional<unsigned> getExtractIndex(const Instruction *E) {
301 unsigned Opcode = E->getOpcode();
302 assert((Opcode == Instruction::ExtractElement ||
303 Opcode == Instruction::ExtractValue) &&
304 "Expected extractelement or extractvalue instruction.");
305 if (Opcode == Instruction::ExtractElement) {
306 auto *CI = dyn_cast<ConstantInt>(Val: E->getOperand(i: 1));
307 if (!CI)
308 return std::nullopt;
309 // Check if the index is out of bound. We can get the source vector from
310 // operand 0.
311 unsigned Idx = CI->getZExtValue();
312 auto *EE = cast<ExtractElementInst>(Val: E);
313 const unsigned VF = getNumElements(Ty: EE->getVectorOperandType());
314 if (Idx >= VF)
315 return std::nullopt;
316 return Idx;
317 }
318 auto *EI = cast<ExtractValueInst>(Val: E);
319 if (EI->getNumIndices() != 1)
320 return std::nullopt;
321 return *EI->idx_begin();
322}
323
324void inversePermutation(ArrayRef<unsigned> Indices,
325 SmallVectorImpl<int> &Mask) {
326 Mask.clear();
327 const unsigned E = Indices.size();
328 Mask.resize(N: E, NV: PoisonMaskElem);
329 for (unsigned I = 0; I < E; ++I)
330 Mask[Indices[I]] = I;
331}
332
333void reorderScalars(SmallVectorImpl<Value *> &Scalars, ArrayRef<int> Mask) {
334 assert(!Mask.empty() && "Expected non-empty mask.");
335 SmallVector<Value *> Prev(Scalars.size(),
336 PoisonValue::get(T: Scalars.front()->getType()));
337 Prev.swap(RHS&: Scalars);
338 for (unsigned I = 0, E = Prev.size(); I < E; ++I)
339 if (Mask[I] != PoisonMaskElem)
340 Scalars[Mask[I]] = Prev[I];
341}
342
343void reorderReuses(SmallVectorImpl<int> &Reuses, ArrayRef<int> Mask) {
344 assert(!Mask.empty() && Reuses.size() == Mask.size() &&
345 "Expected non-empty mask.");
346 SmallVector<int> Prev(Reuses.begin(), Reuses.end());
347 Prev.swap(RHS&: Reuses);
348 for (unsigned I = 0, E = Prev.size(); I < E; ++I)
349 if (Mask[I] != PoisonMaskElem)
350 Reuses[Mask[I]] = Prev[I];
351}
352
353void reorderOrder(SmallVectorImpl<unsigned> &Order, ArrayRef<int> Mask,
354 bool BottomOrder) {
355 assert(!Mask.empty() && "Expected non-empty mask.");
356 unsigned Sz = Mask.size();
357 if (BottomOrder) {
358 SmallVector<unsigned> PrevOrder;
359 if (Order.empty()) {
360 PrevOrder.resize(N: Sz);
361 std::iota(first: PrevOrder.begin(), last: PrevOrder.end(), value: 0);
362 } else {
363 PrevOrder.swap(RHS&: Order);
364 }
365 Order.assign(NumElts: Sz, Elt: Sz);
366 for (unsigned I = 0; I < Sz; ++I)
367 if (Mask[I] != PoisonMaskElem)
368 Order[I] = PrevOrder[Mask[I]];
369 if (all_of(Range: enumerate(First&: Order), P: [&](const auto &Data) {
370 return Data.value() == Sz || Data.index() == Data.value();
371 })) {
372 Order.clear();
373 return;
374 }
375 fixupOrderingIndices(Order);
376 return;
377 }
378 SmallVector<int> MaskOrder;
379 if (Order.empty()) {
380 MaskOrder.resize(N: Sz);
381 std::iota(first: MaskOrder.begin(), last: MaskOrder.end(), value: 0);
382 } else {
383 inversePermutation(Indices: Order, Mask&: MaskOrder);
384 }
385 reorderReuses(Reuses&: MaskOrder, Mask);
386 if (ShuffleVectorInst::isIdentityMask(Mask: MaskOrder, NumSrcElts: Sz)) {
387 Order.clear();
388 return;
389 }
390 Order.assign(NumElts: Sz, Elt: Sz);
391 for (unsigned I = 0; I < Sz; ++I)
392 if (MaskOrder[I] != PoisonMaskElem)
393 Order[MaskOrder[I]] = I;
394 fixupOrderingIndices(Order);
395}
396
397bool isReverseOrder(ArrayRef<unsigned> Order) {
398 assert(!Order.empty() &&
399 "Order is empty. Please check it before using isReverseOrder.");
400 unsigned Sz = Order.size();
401 return all_of(Range: enumerate(First&: Order), P: [&](const auto &Pair) {
402 return Pair.value() == Sz || Sz - Pair.index() - 1 == Pair.value();
403 });
404}
405
406bool isRepeatedNonIdentityClusteredMask(ArrayRef<int> Mask, unsigned Sz) {
407 ArrayRef<int> FirstCluster = Mask.slice(N: 0, M: Sz);
408 if (ShuffleVectorInst::isIdentityMask(Mask: FirstCluster, NumSrcElts: Sz))
409 return false;
410 for (unsigned I = Sz, E = Mask.size(); I < E; I += Sz) {
411 ArrayRef<int> Cluster = Mask.slice(N: I, M: Sz);
412 if (Cluster != FirstCluster)
413 return false;
414 }
415 return true;
416}
417
418void combineOrders(MutableArrayRef<unsigned> Order,
419 ArrayRef<unsigned> SecondaryOrder) {
420 assert((SecondaryOrder.empty() || Order.size() == SecondaryOrder.size()) &&
421 "Expected same size of orders");
422 size_t Sz = Order.size();
423 SmallBitVector UsedIndices(Sz);
424 for (unsigned Idx : seq<unsigned>(Begin: 0, End: Sz)) {
425 if (Order[Idx] != Sz)
426 UsedIndices.set(Order[Idx]);
427 }
428 if (SecondaryOrder.empty()) {
429 for (unsigned Idx : seq<unsigned>(Begin: 0, End: Sz))
430 if (Order[Idx] == Sz && !UsedIndices.test(Idx))
431 Order[Idx] = Idx;
432 } else {
433 for (unsigned Idx : seq<unsigned>(Begin: 0, End: Sz))
434 if (SecondaryOrder[Idx] != Sz && Order[Idx] == Sz &&
435 !UsedIndices.test(Idx: SecondaryOrder[Idx]))
436 Order[Idx] = SecondaryOrder[Idx];
437 }
438}
439
440bool allSameType(ArrayRef<Value *> VL) {
441 assert(!VL.empty() && "Expected non-empty list of values.");
442 Type *Ty = VL.consume_front()->getType();
443 return all_of(Range&: VL, P: [&](Value *V) { return V->getType() == Ty; });
444}
445
446template <typename T>
447std::optional<unsigned> getInsertExtractIndex(const Value *Inst,
448 unsigned Offset) {
449 static_assert(std::is_same_v<T, InsertElementInst> ||
450 std::is_same_v<T, ExtractElementInst>,
451 "unsupported T");
452 const auto *IE = dyn_cast<T>(Inst);
453 if (!IE)
454 return std::nullopt;
455 // InsertElement: result is the vector, index is op 2.
456 // ExtractElement: result is scalar, vector is op 0, index is op 1.
457 constexpr bool IsInsert = std::is_same_v<T, InsertElementInst>;
458 Type *VecTy = IsInsert ? IE->getType() : IE->getOperand(0)->getType();
459 const auto *VT = dyn_cast<FixedVectorType>(Val: VecTy);
460 if (!VT)
461 return std::nullopt;
462 const auto *CI = dyn_cast<ConstantInt>(IE->getOperand(IsInsert ? 2 : 1));
463 if (!CI)
464 return std::nullopt;
465 if (CI->getValue().uge(VT->getNumElements()))
466 return std::nullopt;
467 unsigned Index = Offset;
468 Index *= VT->getNumElements();
469 Index += CI->getZExtValue();
470 return Index;
471}
472
473// Only these two specializations are used; instantiate them here so the
474// definition can stay out of the header.
475template std::optional<unsigned>
476getInsertExtractIndex<InsertElementInst>(const Value *, unsigned);
477template std::optional<unsigned>
478getInsertExtractIndex<ExtractElementInst>(const Value *, unsigned);
479
480bool areAllOperandsNonInsts(Value *V) {
481 auto *I = dyn_cast<Instruction>(Val: V);
482 if (!I)
483 return true;
484 return !mayHaveNonDefUseDependency(I: *I) &&
485 all_of(Range: make_isa_range<Instruction>(Range: I->operands()),
486 P: [I](Instruction *IO) {
487 return isa<PHINode>(Val: IO) || IO->getParent() != I->getParent();
488 });
489}
490
491bool isUsedOutsideBlock(Value *V) {
492 auto *I = dyn_cast<Instruction>(Val: V);
493 if (!I)
494 return true;
495 // Limits the number of uses to save compile time.
496 return !I->mayReadOrWriteMemory() && !I->hasNUsesOrMore(N: UsesLimit) &&
497 all_of(Range: I->users(), P: [I](User *U) {
498 auto *IU = dyn_cast<Instruction>(Val: U);
499 if (!IU)
500 return true;
501 return IU->getParent() != I->getParent() || isa<PHINode>(Val: IU);
502 });
503}
504
505bool doesNotNeedToBeScheduled(Value *V) {
506 return areAllOperandsNonInsts(V) && isUsedOutsideBlock(V);
507}
508
509bool doesNotNeedToSchedule(ArrayRef<Value *> VL) {
510 return !VL.empty() &&
511 (all_of(Range&: VL, P: isUsedOutsideBlock) || all_of(Range&: VL, P: areAllOperandsNonInsts));
512}
513
514void transformScalarShuffleIndiciesToVector(unsigned VecTyNumElements,
515 SmallVectorImpl<int> &Mask) {
516 // The ShuffleBuilder implementation use shufflevector to splat an "element".
517 // But the element have different meaning for SLP (scalar) and REVEC
518 // (vector). We need to expand Mask into masks which shufflevector can use
519 // directly.
520 SmallVector<int> NewMask(Mask.size() * VecTyNumElements);
521 for (unsigned I : seq<unsigned>(Size: Mask.size()))
522 for (auto [J, MaskV] : enumerate(First: MutableArrayRef(NewMask).slice(
523 N: I * VecTyNumElements, M: VecTyNumElements)))
524 MaskV = Mask[I] == PoisonMaskElem ? PoisonMaskElem
525 : Mask[I] * VecTyNumElements + J;
526 Mask.swap(RHS&: NewMask);
527}
528
529unsigned getShufflevectorNumGroups(ArrayRef<Value *> VL) {
530 if (VL.empty())
531 return 0;
532 if (!all_of(Range&: VL, P: IsaPred<ShuffleVectorInst>))
533 return 0;
534 auto *SV = cast<ShuffleVectorInst>(Val: VL.front());
535 unsigned SVNumElements =
536 cast<FixedVectorType>(Val: SV->getOperand(i_nocapture: 0)->getType())->getNumElements();
537 unsigned ShuffleMaskSize = SV->getShuffleMask().size();
538 if (SVNumElements % ShuffleMaskSize != 0)
539 return 0;
540 unsigned GroupSize = SVNumElements / ShuffleMaskSize;
541 if (GroupSize == 0 || (VL.size() % GroupSize) != 0)
542 return 0;
543 unsigned NumGroup = 0;
544 for (size_t I = 0, E = VL.size(); I != E; I += GroupSize) {
545 auto *SV = cast<ShuffleVectorInst>(Val: VL[I]);
546 Value *Src = SV->getOperand(i_nocapture: 0);
547 ArrayRef<Value *> Group = VL.slice(N: I, M: GroupSize);
548 SmallBitVector ExpectedIndex(GroupSize);
549 if (!all_of(Range&: Group, P: [&](Value *V) {
550 auto *SV = cast<ShuffleVectorInst>(Val: V);
551 // From the same source.
552 if (SV->getOperand(i_nocapture: 0) != Src)
553 return false;
554 int Index;
555 if (!SV->isExtractSubvectorMask(Index))
556 return false;
557 ExpectedIndex.set(Index / ShuffleMaskSize);
558 return true;
559 }))
560 return 0;
561 if (!ExpectedIndex.all())
562 return 0;
563 ++NumGroup;
564 }
565 assert(NumGroup == (VL.size() / GroupSize) && "Unexpected number of groups");
566 return NumGroup;
567}
568
569SmallVector<int> calculateShufflevectorMask(ArrayRef<Value *> VL) {
570 assert(getShufflevectorNumGroups(VL) && "Not supported shufflevector usage.");
571 auto *SV = cast<ShuffleVectorInst>(Val: VL.front());
572 unsigned SVNumElements =
573 cast<FixedVectorType>(Val: SV->getOperand(i_nocapture: 0)->getType())->getNumElements();
574 SmallVector<int> Mask;
575 unsigned AccumulateLength = 0;
576 for (Value *V : VL) {
577 auto *SV = cast<ShuffleVectorInst>(Val: V);
578 for (int M : SV->getShuffleMask())
579 Mask.push_back(Elt: M == PoisonMaskElem ? PoisonMaskElem
580 : AccumulateLength + M);
581 AccumulateLength += SVNumElements;
582 }
583 return Mask;
584}
585
586/// Checks if the vector of instructions can be represented as a shuffle, like:
587/// %x0 = extractelement <4 x i8> %x, i32 0
588/// %x3 = extractelement <4 x i8> %x, i32 3
589/// %y1 = extractelement <4 x i8> %y, i32 1
590/// %y2 = extractelement <4 x i8> %y, i32 2
591/// %x0x0 = mul i8 %x0, %x0
592/// %x3x3 = mul i8 %x3, %x3
593/// %y1y1 = mul i8 %y1, %y1
594/// %y2y2 = mul i8 %y2, %y2
595/// %ins1 = insertelement <4 x i8> poison, i8 %x0x0, i32 0
596/// %ins2 = insertelement <4 x i8> %ins1, i8 %x3x3, i32 1
597/// %ins3 = insertelement <4 x i8> %ins2, i8 %y1y1, i32 2
598/// %ins4 = insertelement <4 x i8> %ins3, i8 %y2y2, i32 3
599/// ret <4 x i8> %ins4
600/// can be transformed into:
601/// %1 = shufflevector <4 x i8> %x, <4 x i8> %y, <4 x i32> <i32 0, i32 3, i32 5,
602/// i32 6>
603/// %2 = mul <4 x i8> %1, %1
604/// ret <4 x i8> %2
605/// Mask will return the Shuffle Mask equivalent to the extracted elements.
606/// TODO: Can we split off and reuse the shuffle mask detection from
607/// ShuffleVectorInst/getShuffleCost?
608std::optional<TargetTransformInfo::ShuffleKind>
609isFixedVectorShuffle(ArrayRef<Value *> VL, SmallVectorImpl<int> &Mask,
610 AssumptionCache *AC, SLPAnalysisCache &Cache) {
611 const auto *It = find_if(Range&: VL, P: IsaPred<ExtractElementInst>);
612 if (It == VL.end())
613 return std::nullopt;
614 unsigned Size = 0;
615 Value *Vec1 = nullptr;
616 Value *Vec2 = nullptr;
617 // The poison analysis is expensive, it is required only for the undef
618 // vectors.
619 std::optional<bool> HasNonUndefVec;
620 auto IsNonUndefVecPresent = [&]() {
621 if (!HasNonUndefVec)
622 HasNonUndefVec = any_of(Range: make_isa_range<ExtractElementInst>(Range&: VL),
623 P: [&](ExtractElementInst *EE) {
624 Value *Vec = EE->getVectorOperand();
625 if (isa<UndefValue>(Val: Vec))
626 return false;
627 return Cache.isGuaranteedNotToBePoison(V: Vec, AC);
628 });
629 return *HasNonUndefVec;
630 };
631 enum ShuffleMode { Unknown, Select, Permute };
632 ShuffleMode CommonShuffleMode = Unknown;
633 Mask.assign(NumElts: VL.size(), Elt: PoisonMaskElem);
634 for (unsigned I = 0, E = VL.size(); I < E; ++I) {
635 // Undef, or a copyable lane modeled on an extract main op, can be
636 // represented as an undef element in a vector.
637 if (isa<UndefValue>(Val: VL[I]))
638 continue;
639 auto *EI = dyn_cast<ExtractElementInst>(Val: VL[I]);
640 if (!EI)
641 continue;
642 if (isa<ScalableVectorType>(Val: EI->getVectorOperandType()))
643 return std::nullopt;
644 auto *Vec = EI->getVectorOperand();
645 // We can extractelement from undef or poison vector.
646 if (isUndefVector</*isPoisonOnly=*/true>(V: Vec).all())
647 continue;
648 // All vector operands must have the same number of vector elements.
649 if (isa<UndefValue>(Val: Vec)) {
650 Mask[I] = I;
651 } else {
652 if (isa<UndefValue>(Val: EI->getIndexOperand()))
653 continue;
654 auto *Idx = dyn_cast<ConstantInt>(Val: EI->getIndexOperand());
655 if (!Idx)
656 return std::nullopt;
657 // Undefined behavior if Idx is negative or out of bounds.
658 if (Idx->getValue().uge(RHS: getNumElements(Ty: Vec->getType())))
659 continue;
660 unsigned IntIdx = Idx->getValue().getZExtValue();
661 Mask[I] = IntIdx;
662 }
663 // The width is defined only by the lanes that are present in the mask.
664 Size = std::max(a: Size, b: getNumElements(Ty: Vec->getType()));
665 if (isUndefVector(V: Vec).all() && IsNonUndefVecPresent())
666 continue;
667 // For correct shuffling we have to have at most 2 different vector operands
668 // in all extractelement instructions.
669 if (!Vec1 || Vec1 == Vec) {
670 Vec1 = Vec;
671 } else if (!Vec2 || Vec2 == Vec) {
672 Vec2 = Vec;
673 } else {
674 return std::nullopt;
675 }
676 }
677 if (Vec2 && Size != std::max(a: getNumElements(Ty: Vec1->getType()),
678 b: getNumElements(Ty: Vec2->getType())))
679 return std::nullopt;
680 for (auto [I, Idx] : enumerate(First&: Mask)) {
681 if (Idx == PoisonMaskElem)
682 continue;
683 auto *Vec = cast<ExtractElementInst>(Val: VL[I])->getVectorOperand();
684 if (Vec == Vec2)
685 Idx += Size;
686 else if (Vec != Vec1)
687 continue;
688 if (CommonShuffleMode == Permute)
689 continue;
690 // If the extract index is not the same as the operation number, it is a
691 // permutation.
692 if (Idx % Size != I) {
693 CommonShuffleMode = Permute;
694 continue;
695 }
696 CommonShuffleMode = Select;
697 }
698 // If we're not crossing lanes in different vectors, consider it as blending.
699 if (CommonShuffleMode == Select && Vec2)
700 return TargetTransformInfo::SK_Select;
701 // If Vec2 was never used, we have a permutation of a single vector, otherwise
702 // we have permutation of 2 vectors.
703 return Vec2 ? TargetTransformInfo::SK_PermuteTwoSrc
704 : TargetTransformInfo::SK_PermuteSingleSrc;
705}
706
707Value *createInsertVector(
708 IRBuilderBase &Builder, Value *Vec, Value *V, unsigned Index,
709 function_ref<Value *(Value *, Value *, ArrayRef<int>)> Generator) {
710 if (isa<PoisonValue>(Val: Vec) && isa<PoisonValue>(Val: V))
711 return Vec;
712 const unsigned SubVecVF = getNumElements(Ty: V->getType());
713 // Create shuffle, insertvector requires that index is multiple of
714 // the subvector length.
715 const unsigned VecVF = getNumElements(Ty: Vec->getType());
716 SmallVector<int> Mask(VecVF, PoisonMaskElem);
717 if (isa<PoisonValue>(Val: Vec)) {
718 auto *Begin = std::next(x: Mask.begin(), n: Index);
719 std::iota(first: Begin, last: std::next(x: Begin, n: SubVecVF), value: 0);
720 Vec = Builder.CreateShuffleVector(V, Mask);
721 return Vec;
722 }
723 std::iota(first: Mask.begin(), last: Mask.end(), value: 0);
724 std::iota(first: std::next(x: Mask.begin(), n: Index),
725 last: std::next(x: Mask.begin(), n: Index + SubVecVF), value: VecVF);
726 if (Generator)
727 return Generator(Vec, V, Mask);
728 // 1. Resize V to the size of Vec.
729 SmallVector<int> ResizeMask(VecVF, PoisonMaskElem);
730 std::iota(first: ResizeMask.begin(), last: std::next(x: ResizeMask.begin(), n: SubVecVF), value: 0);
731 V = Builder.CreateShuffleVector(V, Mask: ResizeMask);
732 // 2. Insert V into Vec.
733 return Builder.CreateShuffleVector(V1: Vec, V2: V, Mask);
734}
735
736Value *createExtractVector(IRBuilderBase &Builder, Value *Vec,
737 unsigned SubVecVF, unsigned Index) {
738 SmallVector<int> Mask(SubVecVF, PoisonMaskElem);
739 std::iota(first: Mask.begin(), last: Mask.end(), value: Index);
740 return Builder.CreateShuffleVector(V: Vec, Mask);
741}
742
743SmallBitVector buildUseMask(int VF, ArrayRef<int> Mask, UseMask MaskArg) {
744 SmallBitVector UseMask(VF, true);
745 for (auto [Idx, Value] : enumerate(First&: Mask)) {
746 if (Value == PoisonMaskElem) {
747 if (MaskArg == UseMask::UndefsAsMask)
748 UseMask.reset(Idx);
749 continue;
750 }
751 if (MaskArg == UseMask::FirstArg && Value < VF)
752 UseMask.reset(Idx: Value);
753 else if (MaskArg == UseMask::SecondArg && Value >= VF)
754 UseMask.reset(Idx: Value - VF);
755 }
756 return UseMask;
757}
758
759template <bool IsPoisonOnly>
760SmallBitVector isUndefVector(const Value *V, const SmallBitVector &UseMask) {
761 SmallBitVector Res(UseMask.empty() ? 1 : UseMask.size(), true);
762 using T = std::conditional_t<IsPoisonOnly, PoisonValue, UndefValue>;
763 if (isa<T>(V))
764 return Res;
765 auto *VecTy = dyn_cast<FixedVectorType>(Val: V->getType());
766 if (!VecTy)
767 return Res.reset();
768 auto *C = dyn_cast<Constant>(Val: V);
769 if (!C) {
770 if (!UseMask.empty()) {
771 const Value *Base = V;
772 while (auto *II = dyn_cast<InsertElementInst>(Val: Base)) {
773 Base = II->getOperand(i_nocapture: 0);
774 if (isa<T>(II->getOperand(i_nocapture: 1)))
775 continue;
776 std::optional<unsigned> Idx = getElementIndex(Inst: II);
777 if (!Idx) {
778 Res.reset();
779 return Res;
780 }
781 if (*Idx < UseMask.size() && !UseMask.test(Idx: *Idx))
782 Res.reset(Idx: *Idx);
783 }
784 // TODO: Add analysis for shuffles here too.
785 if (V == Base) {
786 Res.reset();
787 } else {
788 SmallBitVector SubMask(UseMask.size(), false);
789 Res &= isUndefVector<IsPoisonOnly>(Base, SubMask);
790 }
791 } else {
792 Res.reset();
793 }
794 return Res;
795 }
796 for (unsigned I = 0, E = VecTy->getNumElements(); I != E; ++I) {
797 if (Constant *Elem = C->getAggregateElement(Elt: I))
798 if (!isa<T>(Elem) &&
799 (UseMask.empty() || (I < UseMask.size() && !UseMask.test(Idx: I))))
800 Res.reset(Idx: I);
801 }
802 return Res;
803}
804
805template SmallBitVector isUndefVector<false>(const Value *,
806 const SmallBitVector &);
807template SmallBitVector isUndefVector<true>(const Value *,
808 const SmallBitVector &);
809
810bool doesInTreeUserNeedToExtract(Value *Scalar, Instruction *UserInst,
811 TargetLibraryInfo *TLI,
812 const TargetTransformInfo *TTI) {
813 if (!UserInst)
814 return false;
815 unsigned Opcode = UserInst->getOpcode();
816 switch (Opcode) {
817 case Instruction::Load: {
818 LoadInst *LI = cast<LoadInst>(Val: UserInst);
819 return (LI->getPointerOperand() == Scalar);
820 }
821 case Instruction::Store: {
822 StoreInst *SI = cast<StoreInst>(Val: UserInst);
823 return (SI->getPointerOperand() == Scalar);
824 }
825 case Instruction::Call: {
826 CallInst *CI = cast<CallInst>(Val: UserInst);
827 Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI);
828 return any_of(Range: enumerate(First: CI->args()), P: [&](auto &&Arg) {
829 return isVectorIntrinsicWithScalarOpAtArg(ID, Arg.index(), TTI) &&
830 Arg.value().get() == Scalar;
831 });
832 }
833 default:
834 return false;
835 }
836}
837
838MemoryLocation getLocation(Instruction *I) {
839 if (StoreInst *SI = dyn_cast<StoreInst>(Val: I))
840 return MemoryLocation::get(SI);
841 if (LoadInst *LI = dyn_cast<LoadInst>(Val: I))
842 return MemoryLocation::get(LI);
843 return MemoryLocation();
844}
845
846bool isSimple(Instruction *I) {
847 if (LoadInst *LI = dyn_cast<LoadInst>(Val: I))
848 return LI->isSimple();
849 if (StoreInst *SI = dyn_cast<StoreInst>(Val: I))
850 return SI->isSimple();
851 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Val: I))
852 return !MI->isVolatile();
853 return true;
854}
855
856bool isSelectedBaseLoad(Type *ScalarTy, ArrayRef<Value *> PointerOps,
857 const DataLayout &DL, Value *&TrueBase,
858 Value *&FalseBase,
859 SmallVectorImpl<Value *> &Conditions) {
860 TrueBase = nullptr;
861 FalseBase = nullptr;
862 uint64_t ScalarSize = DL.getTypeStoreSize(Ty: ScalarTy);
863 Conditions.assign(NumElts: PointerOps.size(), Elt: nullptr);
864 for (auto [Idx, P] : enumerate(First&: PointerOps)) {
865 Value *Base = P;
866 uint64_t Offset = 0;
867 if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: P)) {
868 APInt OffsetAP(DL.getIndexTypeSizeInBits(Ty: GEP->getType()), 0);
869 if (!GEP->accumulateConstantOffset(DL, Offset&: OffsetAP) || OffsetAP.isNegative())
870 return false;
871 Offset = OffsetAP.getZExtValue();
872 Base = GEP->getPointerOperand();
873 }
874 auto *Sel = dyn_cast<SelectInst>(Val: Base);
875 if (!Sel)
876 return false;
877 Value *T = Sel->getTrueValue();
878 Value *F = Sel->getFalseValue();
879 if (!TrueBase) {
880 if (T == F)
881 return false;
882 TrueBase = T;
883 FalseBase = F;
884 } else if (TrueBase != T || FalseBase != F) {
885 return false;
886 }
887 // Lane Idx must be at exactly Base + Idx * sizeof(ScalarTy); codegen reads
888 // contiguously from TrueBase/FalseBase starting at lane 0.
889 if (Offset != static_cast<uint64_t>(Idx) * ScalarSize)
890 return false;
891 Conditions[Idx] = Sel->getCondition();
892 }
893 return TrueBase != nullptr;
894}
895
896Align computeBlendedLoadBaseAlignment(ArrayRef<Value *> VL,
897 const DataLayout &DL) {
898 assert(all_of(VL, IsaPred<LoadInst>) &&
899 "Expected only load lanes in a blended load.");
900 const uint64_t ScalarSize = DL.getTypeStoreSize(Ty: VL.front()->getType());
901 Align BaseAlignment = cast<LoadInst>(Val: VL.front())->getAlign();
902 for (auto [Idx, V] : enumerate(First&: VL))
903 BaseAlignment =
904 std::min(a: BaseAlignment, b: commonAlignment(A: cast<LoadInst>(Val: V)->getAlign(),
905 Offset: Idx * ScalarSize));
906 return BaseAlignment;
907}
908
909Type *getCommonGEPIndexType(ArrayRef<Value *> VL, Instruction *VL0,
910 function_ref<bool(Value *)> IsGEPLane,
911 const DataLayout &DL) {
912 constexpr unsigned IndexIdx = 1;
913 Type *VL0Ty = VL0->getOperand(i: IndexIdx)->getType();
914 Type *PtrIdxTy =
915 DL.getIndexType(PtrTy: VL0->getOperand(i: 0)->getType()->getScalarType());
916 bool AllSameTy = true;
917 bool HasNonConstIdx = false;
918 bool ConstsFitVL0Ty = true;
919 for (Value *V : make_filter_range(Range&: VL, Pred: IsGEPLane)) {
920 Value *Op = cast<GetElementPtrInst>(Val: V)->getOperand(i_nocapture: IndexIdx);
921 if (Op->getType() != VL0Ty)
922 AllSameTy = false;
923 auto *CI = dyn_cast<ConstantInt>(Val: Op);
924 if (!CI) {
925 // Non-constant indices are not cast, they must have the main op type.
926 if (Op->getType() != VL0Ty)
927 return nullptr;
928 HasNonConstIdx = true;
929 continue;
930 }
931 if (!CI->getValue().isSignedIntN(N: VL0Ty->getIntegerBitWidth()))
932 ConstsFitVL0Ty = false;
933 }
934 if (AllSameTy)
935 return VL0Ty;
936 if (!HasNonConstIdx || VL0Ty == PtrIdxTy)
937 return PtrIdxTy;
938 return ConstsFitVL0Ty ? VL0Ty : nullptr;
939}
940
941bool isCopyableGEPAddressVector(ArrayRef<Value *> PointerOps) {
942 SmallPtrSet<Value *, 16> UniquePtrs(llvm::from_range, PointerOps);
943 if (UniquePtrs.size() != PointerOps.size())
944 return false;
945 auto IsConstantOffsetPtr = [](Value *P) {
946 auto *GEP = dyn_cast<GetElementPtrInst>(Val: P);
947 return !GEP ||
948 (GEP->getNumOperands() == 2 && isConstant(V: GEP->getOperand(i_nocapture: 1)));
949 };
950 auto *RefIt = find_if_not(Range&: PointerOps, P: IsConstantOffsetPtr);
951 if (RefIt == PointerOps.end())
952 return false;
953 auto *RefGEP = dyn_cast<GetElementPtrInst>(Val: *RefIt);
954 if (!RefGEP || RefGEP->getNumOperands() != 2)
955 return false;
956 Value *Base = RefGEP->getPointerOperand();
957 Type *PtrTy = RefGEP->getType();
958 Type *SrcElemTy = RefGEP->getSourceElementType();
959 // The stride and the (optional) cast opcode of the runtime indices.
960 Value *Stride = nullptr;
961 unsigned CastOpcode = 0;
962 for (Value *P : PointerOps) {
963 if (P->getType() != PtrTy)
964 return false;
965 if (P == Base)
966 continue;
967 auto *GEP = dyn_cast<GetElementPtrInst>(Val: P);
968 if (!GEP || GEP->getNumOperands() != 2 ||
969 GEP->getPointerOperand() != Base ||
970 GEP->getSourceElementType() != SrcElemTy)
971 return false;
972 Value *Idx = GEP->getOperand(i_nocapture: 1);
973 if (isConstant(V: Idx))
974 continue;
975 unsigned LaneCastOpcode = 0;
976 if (auto *Cast = dyn_cast<CastInst>(Val: Idx)) {
977 LaneCastOpcode = Cast->getOpcode();
978 Idx = Cast->getOperand(i_nocapture: 0);
979 }
980 Value *LaneStride = Idx;
981 if (auto *BO = dyn_cast<BinaryOperator>(Val: Idx)) {
982 if (isa<Constant>(Val: BO->getOperand(i_nocapture: 1)))
983 LaneStride = BO->getOperand(i_nocapture: 0);
984 else if (isa<Constant>(Val: BO->getOperand(i_nocapture: 0)))
985 LaneStride = BO->getOperand(i_nocapture: 1);
986 }
987 if (!Stride) {
988 Stride = LaneStride;
989 CastOpcode = LaneCastOpcode;
990 continue;
991 }
992 if (LaneStride != Stride || LaneCastOpcode != CastOpcode)
993 return false;
994 }
995 return Stride != nullptr;
996}
997
998void addMask(SmallVectorImpl<int> &Mask, ArrayRef<int> SubMask,
999 bool ExtendingManyInputs) {
1000 if (SubMask.empty())
1001 return;
1002 assert(
1003 (!ExtendingManyInputs || SubMask.size() > Mask.size() ||
1004 // Check if input scalars were extended to match the size of other node.
1005 (SubMask.size() == Mask.size() && Mask.back() == PoisonMaskElem)) &&
1006 "SubMask with many inputs support must be larger than the mask.");
1007 if (Mask.empty()) {
1008 Mask.append(in_start: SubMask.begin(), in_end: SubMask.end());
1009 return;
1010 }
1011 SmallVector<int> NewMask(SubMask.size(), PoisonMaskElem);
1012 int TermValue = std::min(a: Mask.size(), b: SubMask.size());
1013 for (int I = 0, E = SubMask.size(); I < E; ++I) {
1014 if (SubMask[I] == PoisonMaskElem ||
1015 (!ExtendingManyInputs &&
1016 (SubMask[I] >= TermValue || Mask[SubMask[I]] >= TermValue)))
1017 continue;
1018 NewMask[I] = Mask[SubMask[I]];
1019 }
1020 Mask.swap(RHS&: NewMask);
1021}
1022
1023void fixupOrderingIndices(MutableArrayRef<unsigned> Order) {
1024 const size_t Sz = Order.size();
1025 SmallBitVector UnusedIndices(Sz, /*t=*/true);
1026 SmallBitVector MaskedIndices(Sz);
1027 for (unsigned I = 0; I < Sz; ++I) {
1028 if (Order[I] < Sz)
1029 UnusedIndices.reset(Idx: Order[I]);
1030 else
1031 MaskedIndices.set(I);
1032 }
1033 if (MaskedIndices.none())
1034 return;
1035 assert(UnusedIndices.count() == MaskedIndices.count() &&
1036 "Non-synced masked/available indices.");
1037 int Idx = UnusedIndices.find_first();
1038 int MIdx = MaskedIndices.find_first();
1039 while (MIdx >= 0) {
1040 assert(Idx >= 0 && "Indices must be synced.");
1041 Order[MIdx] = Idx;
1042 Idx = UnusedIndices.find_next(Prev: Idx);
1043 MIdx = MaskedIndices.find_next(Prev: MIdx);
1044 }
1045}
1046
1047SmallBitVector getAltInstrMask(ArrayRef<Value *> VL, Type *ScalarTy,
1048 unsigned Opcode0, unsigned Opcode1) {
1049 unsigned ScalarTyNumElements = getNumElements(Ty: ScalarTy);
1050 SmallBitVector OpcodeMask(VL.size() * ScalarTyNumElements, false);
1051 for (unsigned Lane : seq<unsigned>(Size: VL.size())) {
1052 if (isa<PoisonValue>(Val: VL[Lane]))
1053 continue;
1054 if (cast<Instruction>(Val: VL[Lane])->getOpcode() == Opcode1)
1055 OpcodeMask.set(I: Lane * ScalarTyNumElements,
1056 E: Lane * ScalarTyNumElements + ScalarTyNumElements);
1057 }
1058 return OpcodeMask;
1059}
1060
1061SmallVector<Constant *> replicateMask(ArrayRef<Constant *> Val, unsigned VF) {
1062 assert(none_of(Val, [](Constant *C) { return C->getType()->isVectorTy(); }) &&
1063 "Expected scalar constants.");
1064 SmallVector<Constant *> NewVal(Val.size() * VF);
1065 for (auto [I, V] : enumerate(First&: Val))
1066 std::fill_n(first: NewVal.begin() + I * VF, n: VF, value: V);
1067 return NewVal;
1068}
1069
1070Intrinsic::ID getMaskedDivRemIntrinsic(unsigned Opcode) {
1071 switch (Opcode) {
1072 case Instruction::UDiv:
1073 return Intrinsic::masked_udiv;
1074 case Instruction::SDiv:
1075 return Intrinsic::masked_sdiv;
1076 case Instruction::URem:
1077 return Intrinsic::masked_urem;
1078 case Instruction::SRem:
1079 return Intrinsic::masked_srem;
1080 default:
1081 llvm_unreachable("Unexpected opcode");
1082 }
1083}
1084
1085/// Returns true if \p I is a part of a single-use chain, computing an address,
1086/// which does not pay off the vectorization: all the lanes are extracted for
1087/// the scalar addresses, the extracts delay the memory accesses.
1088static bool isNonProfitableIndex(const Instruction *I) {
1089 constexpr unsigned MaxIndexChainLength = 3;
1090 const User *U = I->user_back();
1091 for ([[maybe_unused]] unsigned _ : seq<unsigned>(Size: MaxIndexChainLength)) {
1092 if (isa<GetElementPtrInst>(Val: U))
1093 return true;
1094 if (!isa<Instruction>(Val: U) || !U->hasOneUse())
1095 return false;
1096 U = U->user_back();
1097 }
1098 return false;
1099}
1100
1101bool isOnceUsedSeed(const Instruction *I) {
1102 if (!I->hasOneUse() || isNonProfitableIndex(I))
1103 return false;
1104 // The operation with the identity or the absorbing constant is folded away
1105 // before the codegen, the vector node only repacks the lanes.
1106 if (const auto *BO = dyn_cast<BinaryOperator>(Val: I)) {
1107 unsigned Opcode = BO->getOpcode();
1108 Type *Ty = BO->getType();
1109 for (unsigned Idx : seq<unsigned>(Size: 2)) {
1110 const auto *C = dyn_cast<Constant>(Val: BO->getOperand(i_nocapture: Idx));
1111 if (C && (C == ConstantExpr::getBinOpIdentity(
1112 Opcode, Ty, /*AllowRHSConstant=*/Idx == 1) ||
1113 C == ConstantExpr::getBinOpAbsorber(
1114 Opcode, Ty, /*AllowLHSConstant=*/Idx == 0)))
1115 return false;
1116 }
1117 }
1118 const User *U = I->user_back();
1119 if (isa<ExtractElementInst, ExtractValueInst>(Val: I))
1120 return isa<InsertElementInst, InsertValueInst>(Val: U);
1121 if (isa<CastInst>(Val: I))
1122 return !isa<FPToSIInst, FPToUIInst>(Val: I) &&
1123 (!isa<CastInst>(Val: U) || U->hasOneUse());
1124 return isa<BinaryOperator, UnaryOperator, SelectInst, FreezeInst, CallInst>(
1125 Val: I);
1126}
1127
1128Instruction *lookThroughCastRoundTrip(Value *V, bool MustBeElidable) {
1129 auto *Wide = dyn_cast<FPExtInst>(Val: V);
1130 if (!Wide || !Wide->hasOneUse())
1131 return nullptr;
1132 auto *Narrow = dyn_cast<FPTruncInst>(Val: Wide->getOperand(i_nocapture: 0));
1133 if (!Narrow || !Narrow->hasOneUse())
1134 return nullptr;
1135 Value *Src = Narrow->getOperand(i_nocapture: 0);
1136 if (!isa<Instruction>(Val: Src) || Src->getType() != Wide->getType())
1137 return nullptr;
1138 if (MustBeElidable && !(Wide->hasAllowContract() && Wide->hasNoNaNs() &&
1139 Wide->hasNoInfs() && Narrow->hasAllowContract()))
1140 return nullptr;
1141 return Narrow;
1142}
1143
1144namespace {
1145
1146/// Shifts and the mask accumulated from the narrow ops on the current path:
1147/// the shifts above and at the narrow level, the bitwidth of the narrow ops
1148/// (0 if none) and the mask from the absorbed narrow ands.
1149struct NarrowedChainState {
1150 unsigned Shift = 0;
1151 unsigned NarrowShift = 0;
1152 unsigned NarrowBW = 0;
1153 APInt NarrowMask = APInt(1, 0);
1154
1155 /// The mask for the absorbed narrow ops in the leaf type, applied before
1156 /// widening and shifting; all-ones if nothing was absorbed.
1157 APInt getMask(unsigned LeafBW) const {
1158 if (NarrowBW == 0)
1159 return APInt::getAllOnes(numBits: LeafBW);
1160 return (NarrowMask & (APInt::getAllOnes(numBits: NarrowBW) << NarrowShift))
1161 .lshr(shiftAmt: NarrowShift)
1162 .trunc(width: LeafBW);
1163 }
1164};
1165
1166} // namespace
1167
1168static void
1169collectNarrowedLeavesImpl(Value *V, unsigned RdxOpcode, unsigned WideBW,
1170 NarrowedChainState S, unsigned Depth,
1171 unsigned MaxDepth,
1172 SmallVectorImpl<NarrowedLeafInfo> &Leaves,
1173 SmallVectorImpl<Instruction *> &ChainInsts) {
1174 if (Depth < MaxDepth) {
1175 if (auto *Z = dyn_cast<ZExtInst>(Val: V);
1176 Z && Z->getSrcTy()->isIntegerTy() && !Z->getSrcTy()->isIntegerTy(BitWidth: 1)) {
1177 ChainInsts.push_back(Elt: Z);
1178 return collectNarrowedLeavesImpl(V: Z->getOperand(i_nocapture: 0), RdxOpcode, WideBW, S,
1179 Depth: Depth + 1, MaxDepth, Leaves, ChainInsts);
1180 }
1181 if (auto *BO = dyn_cast<BinaryOperator>(Val: V)) {
1182 if (BO->getOpcode() == RdxOpcode) {
1183 ChainInsts.push_back(Elt: BO);
1184 collectNarrowedLeavesImpl(V: BO->getOperand(i_nocapture: 0), RdxOpcode, WideBW, S,
1185 Depth: Depth + 1, MaxDepth, Leaves, ChainInsts);
1186 collectNarrowedLeavesImpl(V: BO->getOperand(i_nocapture: 1), RdxOpcode, WideBW, S,
1187 Depth: Depth + 1, MaxDepth, Leaves, ChainInsts);
1188 return;
1189 }
1190 const APInt *Amt;
1191 unsigned BW = V->getType()->getScalarSizeInBits();
1192 auto *Z = dyn_cast<ZExtInst>(Val: BO->getOperand(i_nocapture: 0));
1193 if (BO->getOpcode() == Instruction::Shl && Z && S.NarrowBW == 0 &&
1194 match(V: BO->getOperand(i_nocapture: 1), P: m_APInt(Res&: Amt)) && Amt->ult(RHS: BW) &&
1195 Z->getSrcTy()->isIntegerTy() && !Z->getSrcTy()->isIntegerTy(BitWidth: 1) &&
1196 (BW == WideBW ||
1197 Z->getSrcTy()->getIntegerBitWidth() + Amt->getZExtValue() <= BW) &&
1198 S.Shift + Amt->getZExtValue() < WideBW) {
1199 ChainInsts.push_back(Elt: BO);
1200 ChainInsts.push_back(Elt: Z);
1201 S.Shift += Amt->getZExtValue();
1202 return collectNarrowedLeavesImpl(V: Z->getOperand(i_nocapture: 0), RdxOpcode, WideBW, S,
1203 Depth: Depth + 1, MaxDepth, Leaves,
1204 ChainInsts);
1205 }
1206 // Narrow shls fold into the shift and narrow ands into the mask; the
1207 // mask clears the bits the shls shift out. Only same-width ops compose
1208 // on one path, and the combined shift must stay a valid shift amount in
1209 // both types.
1210 if (BW < WideBW && (S.NarrowBW == 0 || BW == S.NarrowBW)) {
1211 if (BO->getOpcode() == Instruction::Shl &&
1212 match(V: BO->getOperand(i_nocapture: 1), P: m_APInt(Res&: Amt)) && Amt->ult(RHS: BW) &&
1213 S.NarrowShift + Amt->getZExtValue() < BW &&
1214 S.Shift + S.NarrowShift + Amt->getZExtValue() < WideBW) {
1215 ChainInsts.push_back(Elt: BO);
1216 if (BO->hasNoUnsignedWrap() && S.NarrowBW == 0) {
1217 S.Shift += Amt->getZExtValue();
1218 // Lossless shls shift out only known-zero bits; record them as
1219 // the mask so matching lanes can form a splat.
1220 S.NarrowBW = BW;
1221 S.NarrowMask = APInt::getLowBitsSet(numBits: BW, loBitsSet: BW - Amt->getZExtValue());
1222 } else {
1223 if (S.NarrowBW == 0) {
1224 S.NarrowBW = BW;
1225 S.NarrowMask = APInt::getAllOnes(numBits: BW);
1226 }
1227 S.NarrowShift += Amt->getZExtValue();
1228 }
1229 return collectNarrowedLeavesImpl(V: BO->getOperand(i_nocapture: 0), RdxOpcode, WideBW,
1230 S, Depth: Depth + 1, MaxDepth, Leaves,
1231 ChainInsts);
1232 }
1233 Value *X;
1234 if (match(V: BO, P: m_c_And(L: m_Value(V&: X), R: m_APInt(Res&: Amt)))) {
1235 ChainInsts.push_back(Elt: BO);
1236 if (S.NarrowBW == 0) {
1237 S.NarrowBW = BW;
1238 S.NarrowMask = APInt::getAllOnes(numBits: BW);
1239 }
1240 S.NarrowMask &= *Amt << S.NarrowShift;
1241 return collectNarrowedLeavesImpl(V: X, RdxOpcode, WideBW, S, Depth: Depth + 1,
1242 MaxDepth, Leaves, ChainInsts);
1243 }
1244 }
1245 }
1246 }
1247 Leaves.emplace_back(Args&: V, Args: S.Shift + S.NarrowShift,
1248 Args: S.getMask(LeafBW: V->getType()->getScalarSizeInBits()));
1249}
1250
1251void collectNarrowedLeaves(Value *V, unsigned RdxOpcode, unsigned WideBW,
1252 unsigned MaxDepth,
1253 SmallVectorImpl<NarrowedLeafInfo> &Leaves,
1254 SmallVectorImpl<Instruction *> &ChainInsts) {
1255 collectNarrowedLeavesImpl(V, RdxOpcode, WideBW, S: NarrowedChainState(),
1256 /*Depth=*/0, MaxDepth, Leaves, ChainInsts);
1257}
1258
1259TargetTransformInfo::TargetCostKind getSLPCostKind(const Function *F) {
1260 assert(F && "Expected function.");
1261 return F->hasOptSize() ? TTI::TCK_CodeSize : TTI::TCK_RecipThroughput;
1262}
1263
1264/// Checks if \p V is a zero-extended sub-field of a wider integer scalar.
1265/// Returns the source scalar, the field width and the field offset.
1266static std::optional<std::tuple<Value *, unsigned, unsigned>>
1267matchExtractedField(Value *V) {
1268 if (!V->getType()->isIntegerTy())
1269 return std::nullopt;
1270 // Field offset for the field-aligned shift amount, if the shifted value of
1271 // the given bit width keeps at least one full field.
1272 auto GetFieldOffset = [](const APInt *Amt, unsigned BitWidth,
1273 unsigned FieldWidth) -> std::optional<unsigned> {
1274 uint64_t ShAmt = Amt->getLimitedValue(Limit: BitWidth);
1275 if (ShAmt % FieldWidth != 0 || ShAmt + FieldWidth > BitWidth)
1276 return std::nullopt;
1277 return ShAmt / FieldWidth;
1278 };
1279 // Checks if the low bits of Val are a sub-field of the given width of a
1280 // wider integer scalar. Val is a scalar integer, since V is one, and so is
1281 // the matched source.
1282 auto MatchLowField =
1283 [&](Value *Val,
1284 unsigned FieldWidth) -> std::optional<std::pair<Value *, unsigned>> {
1285 Value *Src;
1286 const APInt *Amt;
1287 // Only the low bits of Val are observed, so lshr and ashr are equivalent.
1288 if (match(V: Val, P: m_Trunc(Op: m_Shr(L: m_Value(V&: Src), R: m_APInt(Res&: Amt)))) ||
1289 match(V: Val, P: m_Shr(L: m_Value(V&: Src), R: m_APInt(Res&: Amt)))) {
1290 if (std::optional<unsigned> Offset = GetFieldOffset(
1291 Amt, Src->getType()->getIntegerBitWidth(), FieldWidth)) {
1292 // The truncation of the shifted value keeps the field, look through it.
1293 match(V: Src, P: m_Trunc(Op: m_Value(V&: Src)));
1294 return std::make_pair(x&: Src, y&: *Offset);
1295 }
1296 return std::nullopt;
1297 }
1298 if (match(V: Val, P: m_Trunc(Op: m_Value(V&: Src))) &&
1299 Src->getType()->getIntegerBitWidth() >= FieldWidth)
1300 return std::make_pair(x&: Src, y: 0u);
1301 // Val itself is the source of its low field.
1302 if (Val->getType()->getIntegerBitWidth() > FieldWidth)
1303 return std::make_pair(x&: Val, y: 0u);
1304 return std::nullopt;
1305 };
1306 Value *Val;
1307 const APInt *Mask;
1308 // and Val, (1 << FieldWidth) - 1 or zext i<FieldWidth> Val - the low bits of
1309 // Val.
1310 unsigned FieldWidth = 0;
1311 if (match(V, P: m_c_And(L: m_Value(V&: Val), R: m_APInt(Res&: Mask))) && Mask->isMask())
1312 FieldWidth = Mask->popcount();
1313 else if (match(V, P: m_ZExt(Op: m_Value(V&: Val))))
1314 FieldWidth = Val->getType()->getIntegerBitWidth();
1315 if (FieldWidth != 0) {
1316 if (std::optional<std::pair<Value *, unsigned>> Field =
1317 MatchLowField(Val, FieldWidth))
1318 return std::make_tuple(args&: Field->first, args&: FieldWidth, args&: Field->second);
1319 return std::nullopt;
1320 }
1321 unsigned LaneWidth = V->getType()->getIntegerBitWidth();
1322 Value *Src;
1323 const APInt *Amt;
1324 if (match(V, P: m_Trunc(Op: m_LShr(L: m_Value(V&: Src), R: m_APInt(Res&: Amt))))) {
1325 unsigned SrcWidth = Src->getType()->getIntegerBitWidth();
1326 uint64_t ShAmt = Amt->getLimitedValue(Limit: SrcWidth);
1327 // The field itself, if the lane width is the field width.
1328 if (std::optional<unsigned> Offset =
1329 GetFieldOffset(Amt, SrcWidth, LaneWidth))
1330 return std::make_tuple(args&: Src, args&: LaneWidth, args&: *Offset);
1331 // The zero-extended top field of the source.
1332 unsigned FieldWidth = SrcWidth - ShAmt;
1333 if (FieldWidth > 0 && FieldWidth < LaneWidth && ShAmt % FieldWidth == 0)
1334 return std::make_tuple(args&: Src, args&: FieldWidth, args: ShAmt / FieldWidth);
1335 return std::nullopt;
1336 }
1337 if (match(V, P: m_LShr(L: m_Value(V&: Src), R: m_APInt(Res&: Amt)))) {
1338 // The zero-extended top field of the source, if the result keeps exactly
1339 // one field. Look through a truncation of the shifted value.
1340 unsigned ShfWidth = Src->getType()->getIntegerBitWidth();
1341 uint64_t ShAmt = Amt->getLimitedValue(Limit: ShfWidth);
1342 unsigned FieldWidth = ShfWidth - ShAmt;
1343 if (FieldWidth > 0 && ShAmt % FieldWidth == 0) {
1344 match(V: Src, P: m_Trunc(Op: m_Value(V&: Src)));
1345 return std::make_tuple(args&: Src, args&: FieldWidth, args: ShAmt / FieldWidth);
1346 }
1347 return std::nullopt;
1348 }
1349 if (match(V, P: m_Trunc(Op: m_Value(V&: Src))))
1350 return std::make_tuple(args&: Src, args&: LaneWidth, args: 0u);
1351 return std::nullopt;
1352}
1353
1354std::optional<std::tuple<Value *, unsigned, SmallVector<int>>>
1355matchGatheredExtractedFields(ArrayRef<Value *> VL, const DataLayout &DL) {
1356 // Splats are emitted as broadcasts, sub-fields of a constant are folded.
1357 // The bitcast to the field vector maps lane 0 to the least significant
1358 // field on little-endian targets only.
1359 if (VL.size() < 2 || !VL.front()->getType()->isIntegerTy() || isSplat(VL) ||
1360 DL.isBigEndian())
1361 return std::nullopt;
1362 Value *Src = nullptr;
1363 unsigned FieldWidth = 0;
1364 SmallVector<int> Mask(VL.size(), PoisonMaskElem);
1365 for (auto [Idx, V] : make_filter_range(Range: enumerate(First&: VL), Pred: [](const auto &P) {
1366 return !isa<UndefValue>(P.value());
1367 })) {
1368 if (V->getType() != VL.front()->getType())
1369 return std::nullopt;
1370 std::optional<std::tuple<Value *, unsigned, unsigned>> Field =
1371 matchExtractedField(V);
1372 if (!Field || (Src && (Src != std::get<0>(t&: *Field) ||
1373 FieldWidth != std::get<1>(t&: *Field))))
1374 return std::nullopt;
1375 Src = std::get<0>(t&: *Field);
1376 FieldWidth = std::get<1>(t&: *Field);
1377 Mask[Idx] = std::get<2>(t&: *Field);
1378 }
1379 // The field width is a whole number of bytes and divides the source
1380 // exactly, same as for the packing layout, so the source bitcasts to the
1381 // field vector.
1382 if (!Src || isa<Constant>(Val: Src) || FieldWidth % 8 != 0 ||
1383 Src->getType()->getIntegerBitWidth() % FieldWidth != 0)
1384 return std::nullopt;
1385 // The same field in every lane is a splat, emitted as a broadcast.
1386 if (all_of(Range&: Mask, P: [First = *find_if(Range&: Mask, P: not_equal_to(Arg: PoisonMaskElem))](
1387 int MaskElt) {
1388 return MaskElt == PoisonMaskElem || MaskElt == First;
1389 }))
1390 return std::nullopt;
1391 return std::make_tuple(args&: Src, args&: FieldWidth, args: std::move(Mask));
1392}
1393
1394/// Deeper than the standard analysis recursion depth to keep the numeric
1395/// bound precise through arithmetic carry chains.
1396constexpr unsigned MaxBitPackAnalysisDepth = MaxAnalysisRecursionDepth + 2;
1397
1398APInt getScalarMaxValue(const Value *V, unsigned Depth) {
1399 unsigned BitWidth = V->getType()->getScalarSizeInBits();
1400 const APInt Unknown = APInt::getAllOnes(numBits: BitWidth);
1401 if (Depth > MaxBitPackAnalysisDepth || !V->getType()->isIntegerTy())
1402 return Unknown;
1403 const APInt *C, *Amt;
1404 if (match(V, P: m_APInt(Res&: C)))
1405 return *C;
1406 Value *L, *R;
1407 if (match(V, P: m_Add(L: m_Value(V&: L), R: m_Value(V&: R))) ||
1408 match(V, P: m_Or(L: m_Value(V&: L), R: m_Value(V&: R))) ||
1409 match(V, P: m_Xor(L: m_Value(V&: L), R: m_Value(V&: R))))
1410 return getScalarMaxValue(V: L, Depth: Depth + 1)
1411 .uadd_sat(RHS: getScalarMaxValue(V: R, Depth: Depth + 1));
1412 if (match(V, P: m_NUWSub(L: m_Value(V&: L), R: m_Value(V&: R))))
1413 return getScalarMaxValue(V: L, Depth: Depth + 1);
1414 if (match(V, P: m_Mul(L: m_Value(V&: L), R: m_Value(V&: R))))
1415 return getScalarMaxValue(V: L, Depth: Depth + 1)
1416 .umul_sat(RHS: getScalarMaxValue(V: R, Depth: Depth + 1));
1417 if (match(V, P: m_And(L: m_Value(V&: L), R: m_Value(V&: R))))
1418 return APIntOps::umin(A: getScalarMaxValue(V: L, Depth: Depth + 1),
1419 B: getScalarMaxValue(V: R, Depth: Depth + 1));
1420 if (match(V, P: m_LShr(L: m_Value(V&: L), R: m_APInt(Res&: Amt))) && Amt->ult(RHS: BitWidth))
1421 return getScalarMaxValue(V: L, Depth: Depth + 1).lshr(ShiftAmt: *Amt);
1422 if (match(V, P: m_Shl(L: m_Value(V&: L), R: m_APInt(Res&: Amt))) && Amt->ult(RHS: BitWidth)) {
1423 APInt LMax = getScalarMaxValue(V: L, Depth: Depth + 1);
1424 return LMax.getActiveBits() + Amt->getZExtValue() <= BitWidth
1425 ? LMax.shl(ShiftAmt: *Amt)
1426 : Unknown;
1427 }
1428 if (match(V, P: m_ZExt(Op: m_Value(V&: L))))
1429 return getScalarMaxValue(V: L, Depth: Depth + 1).zext(width: BitWidth);
1430 if (match(V, P: m_Trunc(Op: m_Value(V&: L)))) {
1431 APInt Max = getScalarMaxValue(V: L, Depth: Depth + 1);
1432 return Max.getActiveBits() <= BitWidth ? Max.trunc(width: BitWidth) : Unknown;
1433 }
1434 if (match(V, P: m_SExt(Op: m_Value(V&: L)))) {
1435 APInt Max = getScalarMaxValue(V: L, Depth: Depth + 1);
1436 return Max.isNonNegative() ? Max.zext(width: BitWidth) : Unknown;
1437 }
1438 Value *F;
1439 if (match(V, P: m_Select(C: m_Value(), L: m_Value(V&: L), R: m_Value(V&: F))))
1440 return APIntOps::umax(A: getScalarMaxValue(V: L, Depth: Depth + 1),
1441 B: getScalarMaxValue(V: F, Depth: Depth + 1));
1442 return Unknown;
1443}
1444
1445std::optional<BitPackInfo> computeBitPackInfo(unsigned BitWidth,
1446 ArrayRef<APInt> PossibleBits,
1447 ArrayRef<uint64_t> ShlAmts,
1448 ArrayRef<APInt> Masks) {
1449 unsigned NumElts = PossibleBits.size();
1450 BitPackInfo Info;
1451 Info.LShrAmts.assign(NumElts, Elt: 0);
1452 for (unsigned Idx : seq(Size: NumElts)) {
1453 APInt Possible = PossibleBits[Idx].shl(shiftAmt: ShlAmts[Idx]) & Masks[Idx];
1454 if (Possible.isZero())
1455 continue;
1456 unsigned Lo, W;
1457 if (!Possible.isShiftedMask(MaskIdx&: Lo, MaskLen&: W))
1458 return std::nullopt;
1459 if (Info.FieldWidth == 0) {
1460 if (W % 8 != 0 || BitWidth % W != 0)
1461 return std::nullopt;
1462 Info.FieldWidth = W;
1463 Info.LaneOfField.assign(NumElts: BitWidth / W, Elt: BitPackInfo::NoLane);
1464 }
1465 if (W != Info.FieldWidth || Lo % W != 0)
1466 return std::nullopt;
1467 unsigned Field = Lo / W;
1468 if (Info.LaneOfField[Field] != BitPackInfo::NoLane)
1469 return std::nullopt;
1470 Info.LaneOfField[Field] = Idx;
1471 Info.LShrAmts[Idx] = Lo - ShlAmts[Idx];
1472 }
1473 if (Info.FieldWidth == 0)
1474 return std::nullopt;
1475 return Info;
1476}
1477
1478SmallVector<int> getBitPackMask(const BitPackInfo &Info, unsigned NumBytes,
1479 unsigned NumElts, unsigned BytesPerLane) {
1480 unsigned BytesPerField = Info.FieldWidth / 8;
1481 SmallVector<int> Mask;
1482 for (unsigned J : seq(Size: NumBytes)) {
1483 unsigned Lane = Info.LaneOfField[J / BytesPerField];
1484 Mask.push_back(Elt: Lane == BitPackInfo::NoLane
1485 ? (int)(NumElts * BytesPerLane)
1486 : (int)(Lane * BytesPerLane + J % BytesPerField));
1487 }
1488 return Mask;
1489}
1490
1491Value *buildBitPack(IRBuilderBase &Builder, Value *X, const BitPackInfo &Info,
1492 Type *ResultTy, unsigned ShiftWidth, unsigned &NumInsts) {
1493 NumInsts = 0;
1494 auto *VecTy = cast<FixedVectorType>(Val: X->getType());
1495 unsigned BitWidth = VecTy->getScalarSizeInBits();
1496 assert(BitWidth % 8 == 0 &&
1497 "The byte-multiple field width divides the result bit width.");
1498 unsigned NumElts = VecTy->getNumElements();
1499 Value *Y = X;
1500 if (ShiftWidth != BitWidth) {
1501 // Compacting a zext back to its source is free, use it directly.
1502 if (auto *Z = dyn_cast<ZExtInst>(Val: X);
1503 Z && Z->getSrcTy()->getScalarSizeInBits() == ShiftWidth)
1504 Y = Z->getOperand(i_nocapture: 0);
1505 else {
1506 Y = Builder.CreateTrunc(
1507 V: Y, DestTy: FixedVectorType::get(ElementType: IntegerType::get(C&: X->getContext(), NumBits: ShiftWidth),
1508 NumElts));
1509 ++NumInsts;
1510 }
1511 }
1512 if (Info.needsShift()) {
1513 SmallVector<Constant *> Amts;
1514 for (uint64_t A : Info.LShrAmts)
1515 Amts.push_back(
1516 Elt: ConstantInt::get(Ty: IntegerType::get(C&: X->getContext(), NumBits: ShiftWidth), V: A));
1517 Y = Builder.CreateLShr(LHS: Y, RHS: ConstantVector::get(V: Amts));
1518 ++NumInsts;
1519 }
1520 unsigned InBytes = NumElts * (ShiftWidth / 8);
1521 auto *ByteTy = FixedVectorType::get(ElementType: Builder.getInt8Ty(), NumElts: InBytes);
1522 SmallVector<int> Mask = getBitPackMask(
1523 Info, NumBytes: ResultTy->getScalarSizeInBits() / 8, NumElts, BytesPerLane: ShiftWidth / 8);
1524 // Fields in lane order, possibly reversed, are a truncation of the shifted
1525 // lanes. A reversal of byte fields is a bswap.
1526 bool IsReversed = equal(LRange: Info.LaneOfField, RRange: reverse(C: seq<unsigned>(Size: NumElts)));
1527 if (IsReversed || equal(LRange: Info.LaneOfField, RRange: seq<unsigned>(Size: NumElts))) {
1528 Value *Fields = Builder.CreateTrunc(
1529 V: Y, DestTy: Y->getType()->getWithNewBitWidth(NewBitWidth: Info.FieldWidth));
1530 NumInsts += 1 + (Info.FieldWidth != ShiftWidth) + IsReversed;
1531 if (IsReversed && Info.FieldWidth == 8)
1532 return Builder.CreateUnaryIntrinsic(
1533 ID: Intrinsic::bswap, Op: Builder.CreateBitCast(V: Fields, DestTy: ResultTy));
1534 if (IsReversed)
1535 Fields = Builder.CreateVectorReverse(V: Fields);
1536 return Builder.CreateBitCast(V: Fields, DestTy: ResultTy);
1537 }
1538 Value *Packed = Builder.CreateShuffleVector(
1539 V1: Builder.CreateBitCast(V: Y, DestTy: ByteTy),
1540 V2: is_contained(Range: Info.LaneOfField, Element: BitPackInfo::NoLane)
1541 ? Constant::getNullValue(Ty: ByteTy)
1542 : PoisonValue::get(T: ByteTy),
1543 Mask);
1544 NumInsts += 3;
1545 return Builder.CreateBitCast(V: Packed, DestTy: ResultTy);
1546}
1547
1548void redirectDbgValues(Instruction &From, Value &To) {
1549 SmallVector<DbgVariableRecord *, 2> DVRs;
1550 findDbgValues(V: &From, DbgVariableRecords&: DVRs);
1551 auto *ExI = dyn_cast<Instruction>(Val: &To);
1552 for (DbgVariableRecord *DVR : DVRs) {
1553 if (!DVR->isDbgValue())
1554 continue;
1555 Instruction *MarkedI = DVR->getInstruction();
1556 if (ExI && MarkedI->getParent() != ExI->getParent())
1557 continue;
1558 if (!ExI || ExI->comesBefore(Other: MarkedI)) {
1559 DVR->replaceVariableLocationOp(OldValue: &From, NewValue: &To);
1560 continue;
1561 }
1562 DebugVariableAggregate Var(DVR);
1563 auto HasSameVar = [&](auto Records) {
1564 return any_of(filterDbgVars(Records),
1565 [&](const DbgVariableRecord &Other) {
1566 return DebugVariableAggregate(&Other) == Var;
1567 });
1568 };
1569 if (HasSameVar(make_range(x: std::next(x: DVR->getIterator()),
1570 y: MarkedI->getDbgRecordRange().end())) ||
1571 any_of(Range: make_range(x: std::next(x: MarkedI->getIterator()),
1572 y: std::next(x: ExI->getIterator())),
1573 P: [&](const Instruction &I) {
1574 return HasSameVar(I.getDbgRecordRange());
1575 }))
1576 continue;
1577 DbgVariableRecord *NewDVR = DVR->clone();
1578 NewDVR->replaceVariableLocationOp(OldValue: &From, NewValue: &To);
1579 ExI->getParent()->insertDbgRecordAfter(DR: NewDVR, I: ExI);
1580 }
1581}
1582
1583bool isFirstInsertElement(const InsertElementInst *IE1,
1584 const InsertElementInst *IE2) {
1585 if (IE1 == IE2)
1586 return false;
1587 const auto *I1 = IE1;
1588 const auto *I2 = IE2;
1589 const InsertElementInst *PrevI1;
1590 const InsertElementInst *PrevI2;
1591 unsigned Idx1 = *getElementIndex(Inst: IE1);
1592 unsigned Idx2 = *getElementIndex(Inst: IE2);
1593 do {
1594 if (I2 == IE1)
1595 return true;
1596 if (I1 == IE2)
1597 return false;
1598 PrevI1 = I1;
1599 PrevI2 = I2;
1600 if (I1 && (I1 == IE1 || I1->hasOneUse()) &&
1601 getElementIndex(Inst: I1).value_or(u&: Idx2) != Idx2)
1602 I1 = dyn_cast<InsertElementInst>(Val: I1->getOperand(i_nocapture: 0));
1603 if (I2 && ((I2 == IE2 || I2->hasOneUse())) &&
1604 getElementIndex(Inst: I2).value_or(u&: Idx1) != Idx1)
1605 I2 = dyn_cast<InsertElementInst>(Val: I2->getOperand(i_nocapture: 0));
1606 } while ((I1 && PrevI1 != I1) || (I2 && PrevI2 != I2));
1607 llvm_unreachable("Two different buildvectors not expected.");
1608}
1609
1610DebugLoc getDebugLocFromPHI(const PHINode &PN) {
1611 if (DebugLoc DL = PN.getDebugLoc())
1612 return DL;
1613 return DebugLoc::getUnknown();
1614}
1615
1616std::optional<unsigned> getAggregateSize(Instruction *InsertInst) {
1617 if (auto *IE = dyn_cast<InsertElementInst>(Val: InsertInst))
1618 return cast<FixedVectorType>(Val: IE->getType())->getNumElements();
1619
1620 unsigned AggregateSize = 1;
1621 auto *IV = cast<InsertValueInst>(Val: InsertInst);
1622 Type *CurrentType = IV->getType();
1623 do {
1624 if (auto *ST = dyn_cast<StructType>(Val: CurrentType)) {
1625 for (auto *Elt : ST->elements())
1626 if (Elt != ST->getElementType(N: 0)) // check homogeneity
1627 return std::nullopt;
1628 AggregateSize *= ST->getNumElements();
1629 CurrentType = ST->getElementType(N: 0);
1630 } else if (auto *AT = dyn_cast<ArrayType>(Val: CurrentType)) {
1631 AggregateSize *= AT->getNumElements();
1632 CurrentType = AT->getElementType();
1633 } else if (auto *VT = dyn_cast<FixedVectorType>(Val: CurrentType)) {
1634 AggregateSize *= VT->getNumElements();
1635 return AggregateSize;
1636 } else if (CurrentType->isSingleValueType()) {
1637 return AggregateSize;
1638 } else {
1639 return std::nullopt;
1640 }
1641 } while (true);
1642}
1643
1644const Loop *findInnermostNonInvariantLoop(const Loop *L, ArrayRef<Value *> VL) {
1645 assert(L && "Expected valid loop");
1646 auto IsLoopInvariant = [&](const Loop *L, ArrayRef<Value *> VL) {
1647 return all_of(Range: make_isa_range<Instruction>(Range&: VL),
1648 P: [L](Instruction *I) { return L->isLoopInvariant(V: I); });
1649 };
1650 while (L && IsLoopInvariant(L, VL))
1651 L = L->getParentLoop();
1652 return L;
1653}
1654
1655unsigned getLoopTripCount(const Loop *L, ScalarEvolution &SE,
1656 unsigned LoopAwareTripCount) {
1657 if (LoopAwareTripCount == 0)
1658 return 1;
1659 unsigned Scale = SE.getSmallConstantTripCount(L);
1660 if (Scale == 0)
1661 Scale = getLoopEstimatedTripCount(L: const_cast<Loop *>(L)).value_or(u: 0);
1662 if (Scale != 0) {
1663 // Multiple exiting blocks - choose the minimum between trip count (scale)
1664 // and LoopAwareTripCount, since the multiple exit loops can be terminated
1665 // early.
1666 if (!L->getExitingBlock())
1667 return std::min<unsigned>(a: LoopAwareTripCount, b: Scale);
1668 return Scale;
1669 }
1670 return LoopAwareTripCount;
1671}
1672
1673} // namespace llvm::slpvectorizer
1674