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