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/STLExtras.h"
12#include "llvm/ADT/Sequence.h"
13#include "llvm/Analysis/ValueTracking.h"
14#include "llvm/Analysis/VectorUtils.h"
15#include "llvm/IR/Constants.h"
16#include "llvm/IR/DerivedTypes.h"
17#include "llvm/IR/Instructions.h"
18#include "llvm/IR/IntrinsicInst.h"
19#include "llvm/IR/PatternMatch.h"
20#include "llvm/Support/Casting.h"
21#include "llvm/Support/MathExtras.h"
22#include "llvm/Support/raw_ostream.h"
23
24#include <algorithm>
25#include <string>
26#include <type_traits>
27
28using namespace llvm;
29using namespace llvm::PatternMatch;
30
31namespace llvm::slpvectorizer {
32
33bool isConstant(Value *V) {
34 return isa<Constant>(Val: V) && !isa<ConstantExpr, GlobalValue>(Val: V);
35}
36
37bool isVectorLikeInstWithConstOps(Value *V) {
38 auto *I = dyn_cast<Instruction>(Val: V);
39 // Non-instructions are vector-like only if they are undef.
40 if (!I)
41 return isa<UndefValue>(Val: V);
42 switch (I->getOpcode()) {
43 case Instruction::ExtractValue:
44 case Instruction::InsertValue:
45 return true;
46 case Instruction::ExtractElement:
47 return isa<FixedVectorType>(Val: I->getOperand(i: 0)->getType()) &&
48 isConstant(V: I->getOperand(i: 1));
49 case Instruction::InsertElement:
50 return isa<FixedVectorType>(Val: I->getOperand(i: 0)->getType()) &&
51 isConstant(V: I->getOperand(i: 2));
52 default:
53 return false;
54 }
55}
56
57unsigned getNumElements(Type *Ty) {
58 assert(!isa<ScalableVectorType>(Ty) &&
59 "ScalableVectorType is not supported.");
60 if (isVectorizedTy(Ty))
61 return getVectorizedTypeVF(Ty).getFixedValue();
62 return 1;
63}
64
65unsigned getPartNumElems(unsigned Size, unsigned NumParts) {
66 return std::min<unsigned>(a: Size, b: bit_ceil(Value: divideCeil(Numerator: Size, Denominator: NumParts)));
67}
68
69unsigned getNumElems(unsigned Size, unsigned PartNumElems, unsigned Part) {
70 return std::min<unsigned>(a: PartNumElems, b: Size - Part * PartNumElems);
71}
72
73#if !defined(NDEBUG)
74std::string shortBundleName(ArrayRef<Value *> VL, int Idx) {
75 std::string Result;
76 raw_string_ostream OS(Result);
77 if (Idx >= 0)
78 OS << "Idx: " << Idx << ", ";
79 OS << "n=" << VL.size() << " [" << *VL.front() << ", ..]";
80 return Result;
81}
82#endif
83
84bool allSameBlock(ArrayRef<Value *> VL) {
85 auto *It = find_if(Range&: VL, P: IsaPred<Instruction>);
86 if (It == VL.end())
87 return false;
88 Instruction *I0 = cast<Instruction>(Val: *It);
89 if (all_of(Range&: VL, P: isVectorLikeInstWithConstOps))
90 return true;
91
92 BasicBlock *BB = I0->getParent();
93 for (Value *V : iterator_range(It, VL.end())) {
94 if (isa<PoisonValue>(Val: V))
95 continue;
96 auto *II = dyn_cast<Instruction>(Val: V);
97 if (!II)
98 return false;
99
100 if (BB != II->getParent())
101 return false;
102 }
103 return true;
104}
105
106bool allConstant(ArrayRef<Value *> VL) {
107 // Constant expressions and globals can't be vectorized like normal integer/FP
108 // constants.
109 return all_of(Range&: VL, P: isConstant);
110}
111
112bool isSplat(ArrayRef<Value *> VL) {
113 Value *FirstNonUndef = nullptr;
114 for (Value *V : VL) {
115 if (isa<UndefValue>(Val: V))
116 continue;
117 if (!FirstNonUndef) {
118 FirstNonUndef = V;
119 continue;
120 }
121 if (V != FirstNonUndef)
122 return false;
123 }
124 return FirstNonUndef != nullptr;
125}
126
127bool isCommutative(const Instruction *I, const Value *ValWithUses,
128 bool IsCopyable) {
129 if (auto *Cmp = dyn_cast<CmpInst>(Val: I))
130 return Cmp->isCommutative();
131 if (auto *BO = dyn_cast<BinaryOperator>(Val: I))
132 return BO->isCommutative() ||
133 (BO->getOpcode() == Instruction::Sub && ValWithUses->hasUseList() &&
134 !ValWithUses->hasNUsesOrMore(N: UsesLimit) &&
135 all_of(
136 Range: ValWithUses->uses(),
137 P: [&](const Use &U) {
138 // Commutative, if icmp eq/ne sub, 0
139 CmpPredicate Pred;
140 if (match(V: U.getUser(),
141 P: m_ICmp(Pred, L: m_Specific(V: U.get()), R: m_Zero())) &&
142 (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE))
143 return true;
144 // Commutative, if abs(sub nsw, true) or abs(sub, false).
145 ConstantInt *Flag;
146 auto *I = dyn_cast<BinaryOperator>(Val: U.get());
147 return match(V: U.getUser(),
148 P: m_Intrinsic<Intrinsic::abs>(
149 Ops: m_Specific(V: U.get()), Ops: m_ConstantInt(CI&: Flag))) &&
150 ((!IsCopyable && I && !I->hasNoSignedWrap()) ||
151 Flag->isOne());
152 })) ||
153 (BO->getOpcode() == Instruction::FSub && ValWithUses->hasUseList() &&
154 !ValWithUses->hasNUsesOrMore(N: UsesLimit) &&
155 all_of(Range: ValWithUses->uses(), P: [](const Use &U) {
156 return match(V: U.getUser(),
157 P: m_Intrinsic<Intrinsic::fabs>(Ops: m_Specific(V: U.get())));
158 }));
159 return I->isCommutative();
160}
161
162bool isCommutative(const Instruction *I) { return isCommutative(I, ValWithUses: I); }
163
164bool isCommutableOperand(const Instruction *I, Value *ValWithUses, unsigned Op,
165 bool IsCopyable) {
166 assert(isCommutative(I, ValWithUses, IsCopyable) &&
167 "The instruction is not commutative.");
168 if (isa<CmpInst>(Val: I))
169 return true;
170 if (auto *BO = dyn_cast<BinaryOperator>(Val: I)) {
171 switch (BO->getOpcode()) {
172 case Instruction::Sub:
173 case Instruction::FSub:
174 return true;
175 default:
176 break;
177 }
178 }
179 return I->isCommutableOperand(Op);
180}
181
182unsigned getNumberOfPotentiallyCommutativeOps(Instruction *I) {
183 if (isa<IntrinsicInst>(Val: I) && isCommutative(I)) {
184 // IntrinsicInst::isCommutative returns true if swapping the first "two"
185 // arguments to the intrinsic produces the same result.
186 constexpr unsigned IntrinsicNumOperands = 2;
187 return IntrinsicNumOperands;
188 }
189 return I->getNumOperands();
190}
191
192std::optional<unsigned> getElementIndex(const Value *Inst, unsigned Offset) {
193 if (auto Index = getInsertExtractIndex<InsertElementInst>(Inst, Offset))
194 return Index;
195 if (auto Index = getInsertExtractIndex<ExtractElementInst>(Inst, Offset))
196 return Index;
197
198 unsigned Index = Offset;
199
200 const auto *IV = dyn_cast<InsertValueInst>(Val: Inst);
201 if (!IV)
202 return std::nullopt;
203
204 Type *CurrentType = IV->getType();
205 for (unsigned I : IV->indices()) {
206 if (const auto *ST = dyn_cast<StructType>(Val: CurrentType)) {
207 Index *= ST->getNumElements();
208 CurrentType = ST->getElementType(N: I);
209 } else if (const auto *AT = dyn_cast<ArrayType>(Val: CurrentType)) {
210 Index *= AT->getNumElements();
211 CurrentType = AT->getElementType();
212 } else {
213 return std::nullopt;
214 }
215 Index += I;
216 }
217 return Index;
218}
219
220bool allSameOpcode(ArrayRef<Value *> VL) {
221 auto *It = find_if(Range&: VL, P: IsaPred<Instruction>);
222 if (It == VL.end())
223 return true;
224 Instruction *MainOp = cast<Instruction>(Val: *It);
225 unsigned Opcode = MainOp->getOpcode();
226 bool IsCmpOp = isa<CmpInst>(Val: MainOp);
227 CmpInst::Predicate BasePred = IsCmpOp ? cast<CmpInst>(Val: MainOp)->getPredicate()
228 : CmpInst::BAD_ICMP_PREDICATE;
229 return all_of(Range: make_range(x: It, y: VL.end()), P: [&](Value *V) {
230 if (auto *CI = dyn_cast<CmpInst>(Val: V))
231 return BasePred == CI->getPredicate();
232 if (auto *I = dyn_cast<Instruction>(Val: V))
233 return I->getOpcode() == Opcode;
234 return isa<PoisonValue>(Val: V);
235 });
236}
237
238std::optional<unsigned> getExtractIndex(const Instruction *E) {
239 unsigned Opcode = E->getOpcode();
240 assert((Opcode == Instruction::ExtractElement ||
241 Opcode == Instruction::ExtractValue) &&
242 "Expected extractelement or extractvalue instruction.");
243 if (Opcode == Instruction::ExtractElement) {
244 auto *CI = dyn_cast<ConstantInt>(Val: E->getOperand(i: 1));
245 if (!CI)
246 return std::nullopt;
247 // Check if the index is out of bound. We can get the source vector from
248 // operand 0.
249 unsigned Idx = CI->getZExtValue();
250 auto *EE = cast<ExtractElementInst>(Val: E);
251 const unsigned VF = getNumElements(Ty: EE->getVectorOperandType());
252 if (Idx >= VF)
253 return std::nullopt;
254 return Idx;
255 }
256 auto *EI = cast<ExtractValueInst>(Val: E);
257 if (EI->getNumIndices() != 1)
258 return std::nullopt;
259 return *EI->idx_begin();
260}
261
262void inversePermutation(ArrayRef<unsigned> Indices,
263 SmallVectorImpl<int> &Mask) {
264 Mask.clear();
265 const unsigned E = Indices.size();
266 Mask.resize(N: E, NV: PoisonMaskElem);
267 for (unsigned I = 0; I < E; ++I)
268 Mask[Indices[I]] = I;
269}
270
271void reorderScalars(SmallVectorImpl<Value *> &Scalars, ArrayRef<int> Mask) {
272 assert(!Mask.empty() && "Expected non-empty mask.");
273 SmallVector<Value *> Prev(Scalars.size(),
274 PoisonValue::get(T: Scalars.front()->getType()));
275 Prev.swap(RHS&: Scalars);
276 for (unsigned I = 0, E = Prev.size(); I < E; ++I)
277 if (Mask[I] != PoisonMaskElem)
278 Scalars[Mask[I]] = Prev[I];
279}
280
281bool allSameType(ArrayRef<Value *> VL) {
282 assert(!VL.empty() && "Expected non-empty list of values.");
283 Type *Ty = VL.consume_front()->getType();
284 return all_of(Range&: VL, P: [&](Value *V) { return V->getType() == Ty; });
285}
286
287template <typename T>
288std::optional<unsigned> getInsertExtractIndex(const Value *Inst,
289 unsigned Offset) {
290 static_assert(std::is_same_v<T, InsertElementInst> ||
291 std::is_same_v<T, ExtractElementInst>,
292 "unsupported T");
293 const auto *IE = dyn_cast<T>(Inst);
294 if (!IE)
295 return std::nullopt;
296 // InsertElement: result is the vector, index is op 2.
297 // ExtractElement: result is scalar, vector is op 0, index is op 1.
298 constexpr bool IsInsert = std::is_same_v<T, InsertElementInst>;
299 Type *VecTy = IsInsert ? IE->getType() : IE->getOperand(0)->getType();
300 const auto *VT = dyn_cast<FixedVectorType>(Val: VecTy);
301 if (!VT)
302 return std::nullopt;
303 const auto *CI = dyn_cast<ConstantInt>(IE->getOperand(IsInsert ? 2 : 1));
304 if (!CI)
305 return std::nullopt;
306 if (CI->getValue().uge(VT->getNumElements()))
307 return std::nullopt;
308 unsigned Index = Offset;
309 Index *= VT->getNumElements();
310 Index += CI->getZExtValue();
311 return Index;
312}
313
314// Only these two specializations are used; instantiate them here so the
315// definition can stay out of the header.
316template std::optional<unsigned>
317getInsertExtractIndex<InsertElementInst>(const Value *, unsigned);
318template std::optional<unsigned>
319getInsertExtractIndex<ExtractElementInst>(const Value *, unsigned);
320
321bool areAllOperandsNonInsts(Value *V) {
322 auto *I = dyn_cast<Instruction>(Val: V);
323 if (!I)
324 return true;
325 return !mayHaveNonDefUseDependency(I: *I) &&
326 all_of(Range: I->operands(), P: [I](Value *V) {
327 auto *IO = dyn_cast<Instruction>(Val: V);
328 if (!IO)
329 return true;
330 return isa<PHINode>(Val: IO) || IO->getParent() != I->getParent();
331 });
332}
333
334bool isUsedOutsideBlock(Value *V) {
335 auto *I = dyn_cast<Instruction>(Val: V);
336 if (!I)
337 return true;
338 // Limits the number of uses to save compile time.
339 return !I->mayReadOrWriteMemory() && !I->hasNUsesOrMore(N: UsesLimit) &&
340 all_of(Range: I->users(), P: [I](User *U) {
341 auto *IU = dyn_cast<Instruction>(Val: U);
342 if (!IU)
343 return true;
344 return IU->getParent() != I->getParent() || isa<PHINode>(Val: IU);
345 });
346}
347
348bool doesNotNeedToBeScheduled(Value *V) {
349 return areAllOperandsNonInsts(V) && isUsedOutsideBlock(V);
350}
351
352bool doesNotNeedToSchedule(ArrayRef<Value *> VL) {
353 return !VL.empty() &&
354 (all_of(Range&: VL, P: isUsedOutsideBlock) || all_of(Range&: VL, P: areAllOperandsNonInsts));
355}
356
357void transformScalarShuffleIndiciesToVector(unsigned VecTyNumElements,
358 SmallVectorImpl<int> &Mask) {
359 // The ShuffleBuilder implementation use shufflevector to splat an "element".
360 // But the element have different meaning for SLP (scalar) and REVEC
361 // (vector). We need to expand Mask into masks which shufflevector can use
362 // directly.
363 SmallVector<int> NewMask(Mask.size() * VecTyNumElements);
364 for (unsigned I : seq<unsigned>(Size: Mask.size()))
365 for (auto [J, MaskV] : enumerate(First: MutableArrayRef(NewMask).slice(
366 N: I * VecTyNumElements, M: VecTyNumElements)))
367 MaskV = Mask[I] == PoisonMaskElem ? PoisonMaskElem
368 : Mask[I] * VecTyNumElements + J;
369 Mask.swap(RHS&: NewMask);
370}
371
372unsigned getShufflevectorNumGroups(ArrayRef<Value *> VL) {
373 if (VL.empty())
374 return 0;
375 if (!all_of(Range&: VL, P: IsaPred<ShuffleVectorInst>))
376 return 0;
377 auto *SV = cast<ShuffleVectorInst>(Val: VL.front());
378 unsigned SVNumElements =
379 cast<FixedVectorType>(Val: SV->getOperand(i_nocapture: 0)->getType())->getNumElements();
380 unsigned ShuffleMaskSize = SV->getShuffleMask().size();
381 if (SVNumElements % ShuffleMaskSize != 0)
382 return 0;
383 unsigned GroupSize = SVNumElements / ShuffleMaskSize;
384 if (GroupSize == 0 || (VL.size() % GroupSize) != 0)
385 return 0;
386 unsigned NumGroup = 0;
387 for (size_t I = 0, E = VL.size(); I != E; I += GroupSize) {
388 auto *SV = cast<ShuffleVectorInst>(Val: VL[I]);
389 Value *Src = SV->getOperand(i_nocapture: 0);
390 ArrayRef<Value *> Group = VL.slice(N: I, M: GroupSize);
391 SmallBitVector ExpectedIndex(GroupSize);
392 if (!all_of(Range&: Group, P: [&](Value *V) {
393 auto *SV = cast<ShuffleVectorInst>(Val: V);
394 // From the same source.
395 if (SV->getOperand(i_nocapture: 0) != Src)
396 return false;
397 int Index;
398 if (!SV->isExtractSubvectorMask(Index))
399 return false;
400 ExpectedIndex.set(Index / ShuffleMaskSize);
401 return true;
402 }))
403 return 0;
404 if (!ExpectedIndex.all())
405 return 0;
406 ++NumGroup;
407 }
408 assert(NumGroup == (VL.size() / GroupSize) && "Unexpected number of groups");
409 return NumGroup;
410}
411
412SmallVector<int> calculateShufflevectorMask(ArrayRef<Value *> VL) {
413 assert(getShufflevectorNumGroups(VL) && "Not supported shufflevector usage.");
414 auto *SV = cast<ShuffleVectorInst>(Val: VL.front());
415 unsigned SVNumElements =
416 cast<FixedVectorType>(Val: SV->getOperand(i_nocapture: 0)->getType())->getNumElements();
417 SmallVector<int> Mask;
418 unsigned AccumulateLength = 0;
419 for (Value *V : VL) {
420 auto *SV = cast<ShuffleVectorInst>(Val: V);
421 for (int M : SV->getShuffleMask())
422 Mask.push_back(Elt: M == PoisonMaskElem ? PoisonMaskElem
423 : AccumulateLength + M);
424 AccumulateLength += SVNumElements;
425 }
426 return Mask;
427}
428
429SmallBitVector buildUseMask(int VF, ArrayRef<int> Mask, UseMask MaskArg) {
430 SmallBitVector UseMask(VF, true);
431 for (auto [Idx, Value] : enumerate(First&: Mask)) {
432 if (Value == PoisonMaskElem) {
433 if (MaskArg == UseMask::UndefsAsMask)
434 UseMask.reset(Idx);
435 continue;
436 }
437 if (MaskArg == UseMask::FirstArg && Value < VF)
438 UseMask.reset(Idx: Value);
439 else if (MaskArg == UseMask::SecondArg && Value >= VF)
440 UseMask.reset(Idx: Value - VF);
441 }
442 return UseMask;
443}
444
445template <bool IsPoisonOnly>
446SmallBitVector isUndefVector(const Value *V, const SmallBitVector &UseMask) {
447 SmallBitVector Res(UseMask.empty() ? 1 : UseMask.size(), true);
448 using T = std::conditional_t<IsPoisonOnly, PoisonValue, UndefValue>;
449 if (isa<T>(V))
450 return Res;
451 auto *VecTy = dyn_cast<FixedVectorType>(Val: V->getType());
452 if (!VecTy)
453 return Res.reset();
454 auto *C = dyn_cast<Constant>(Val: V);
455 if (!C) {
456 if (!UseMask.empty()) {
457 const Value *Base = V;
458 while (auto *II = dyn_cast<InsertElementInst>(Val: Base)) {
459 Base = II->getOperand(i_nocapture: 0);
460 if (isa<T>(II->getOperand(i_nocapture: 1)))
461 continue;
462 std::optional<unsigned> Idx = getElementIndex(Inst: II);
463 if (!Idx) {
464 Res.reset();
465 return Res;
466 }
467 if (*Idx < UseMask.size() && !UseMask.test(Idx: *Idx))
468 Res.reset(Idx: *Idx);
469 }
470 // TODO: Add analysis for shuffles here too.
471 if (V == Base) {
472 Res.reset();
473 } else {
474 SmallBitVector SubMask(UseMask.size(), false);
475 Res &= isUndefVector<IsPoisonOnly>(Base, SubMask);
476 }
477 } else {
478 Res.reset();
479 }
480 return Res;
481 }
482 for (unsigned I = 0, E = VecTy->getNumElements(); I != E; ++I) {
483 if (Constant *Elem = C->getAggregateElement(Elt: I))
484 if (!isa<T>(Elem) &&
485 (UseMask.empty() || (I < UseMask.size() && !UseMask.test(Idx: I))))
486 Res.reset(Idx: I);
487 }
488 return Res;
489}
490
491template SmallBitVector isUndefVector<false>(const Value *,
492 const SmallBitVector &);
493template SmallBitVector isUndefVector<true>(const Value *,
494 const SmallBitVector &);
495
496bool doesInTreeUserNeedToExtract(Value *Scalar, Instruction *UserInst,
497 TargetLibraryInfo *TLI,
498 const TargetTransformInfo *TTI) {
499 if (!UserInst)
500 return false;
501 unsigned Opcode = UserInst->getOpcode();
502 switch (Opcode) {
503 case Instruction::Load: {
504 LoadInst *LI = cast<LoadInst>(Val: UserInst);
505 return (LI->getPointerOperand() == Scalar);
506 }
507 case Instruction::Store: {
508 StoreInst *SI = cast<StoreInst>(Val: UserInst);
509 return (SI->getPointerOperand() == Scalar);
510 }
511 case Instruction::Call: {
512 CallInst *CI = cast<CallInst>(Val: UserInst);
513 Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI);
514 return any_of(Range: enumerate(First: CI->args()), P: [&](auto &&Arg) {
515 return isVectorIntrinsicWithScalarOpAtArg(ID, Arg.index(), TTI) &&
516 Arg.value().get() == Scalar;
517 });
518 }
519 default:
520 return false;
521 }
522}
523
524MemoryLocation getLocation(Instruction *I) {
525 if (StoreInst *SI = dyn_cast<StoreInst>(Val: I))
526 return MemoryLocation::get(SI);
527 if (LoadInst *LI = dyn_cast<LoadInst>(Val: I))
528 return MemoryLocation::get(LI);
529 return MemoryLocation();
530}
531
532bool isSimple(Instruction *I) {
533 if (LoadInst *LI = dyn_cast<LoadInst>(Val: I))
534 return LI->isSimple();
535 if (StoreInst *SI = dyn_cast<StoreInst>(Val: I))
536 return SI->isSimple();
537 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Val: I))
538 return !MI->isVolatile();
539 return true;
540}
541
542void addMask(SmallVectorImpl<int> &Mask, ArrayRef<int> SubMask,
543 bool ExtendingManyInputs) {
544 if (SubMask.empty())
545 return;
546 assert(
547 (!ExtendingManyInputs || SubMask.size() > Mask.size() ||
548 // Check if input scalars were extended to match the size of other node.
549 (SubMask.size() == Mask.size() && Mask.back() == PoisonMaskElem)) &&
550 "SubMask with many inputs support must be larger than the mask.");
551 if (Mask.empty()) {
552 Mask.append(in_start: SubMask.begin(), in_end: SubMask.end());
553 return;
554 }
555 SmallVector<int> NewMask(SubMask.size(), PoisonMaskElem);
556 int TermValue = std::min(a: Mask.size(), b: SubMask.size());
557 for (int I = 0, E = SubMask.size(); I < E; ++I) {
558 if (SubMask[I] == PoisonMaskElem ||
559 (!ExtendingManyInputs &&
560 (SubMask[I] >= TermValue || Mask[SubMask[I]] >= TermValue)))
561 continue;
562 NewMask[I] = Mask[SubMask[I]];
563 }
564 Mask.swap(RHS&: NewMask);
565}
566
567void fixupOrderingIndices(MutableArrayRef<unsigned> Order) {
568 const size_t Sz = Order.size();
569 SmallBitVector UnusedIndices(Sz, /*t=*/true);
570 SmallBitVector MaskedIndices(Sz);
571 for (unsigned I = 0; I < Sz; ++I) {
572 if (Order[I] < Sz)
573 UnusedIndices.reset(Idx: Order[I]);
574 else
575 MaskedIndices.set(I);
576 }
577 if (MaskedIndices.none())
578 return;
579 assert(UnusedIndices.count() == MaskedIndices.count() &&
580 "Non-synced masked/available indices.");
581 int Idx = UnusedIndices.find_first();
582 int MIdx = MaskedIndices.find_first();
583 while (MIdx >= 0) {
584 assert(Idx >= 0 && "Indices must be synced.");
585 Order[MIdx] = Idx;
586 Idx = UnusedIndices.find_next(Prev: Idx);
587 MIdx = MaskedIndices.find_next(Prev: MIdx);
588 }
589}
590
591SmallBitVector getAltInstrMask(ArrayRef<Value *> VL, Type *ScalarTy,
592 unsigned Opcode0, unsigned Opcode1) {
593 unsigned ScalarTyNumElements = getNumElements(Ty: ScalarTy);
594 SmallBitVector OpcodeMask(VL.size() * ScalarTyNumElements, false);
595 for (unsigned Lane : seq<unsigned>(Size: VL.size())) {
596 if (isa<PoisonValue>(Val: VL[Lane]))
597 continue;
598 if (cast<Instruction>(Val: VL[Lane])->getOpcode() == Opcode1)
599 OpcodeMask.set(I: Lane * ScalarTyNumElements,
600 E: Lane * ScalarTyNumElements + ScalarTyNumElements);
601 }
602 return OpcodeMask;
603}
604
605SmallVector<Constant *> replicateMask(ArrayRef<Constant *> Val, unsigned VF) {
606 assert(none_of(Val, [](Constant *C) { return C->getType()->isVectorTy(); }) &&
607 "Expected scalar constants.");
608 SmallVector<Constant *> NewVal(Val.size() * VF);
609 for (auto [I, V] : enumerate(First&: Val))
610 std::fill_n(first: NewVal.begin() + I * VF, n: VF, value: V);
611 return NewVal;
612}
613
614} // namespace llvm::slpvectorizer
615