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