1//===- SLPUtils.cpp - SLP Vectorizer free utility helpers -----------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "SLPUtils.h"
10
11#include "llvm/ADT/APInt.h"
12#include "llvm/ADT/STLExtras.h"
13#include "llvm/ADT/Sequence.h"
14#include "llvm/Analysis/ValueTracking.h"
15#include "llvm/Analysis/VectorUtils.h"
16#include "llvm/IR/Constants.h"
17#include "llvm/IR/DataLayout.h"
18#include "llvm/IR/DerivedTypes.h"
19#include "llvm/IR/Instructions.h"
20#include "llvm/IR/IntrinsicInst.h"
21#include "llvm/IR/PatternMatch.h"
22#include "llvm/Support/Casting.h"
23#include "llvm/Support/MathExtras.h"
24#include "llvm/Support/raw_ostream.h"
25
26#include <algorithm>
27#include <string>
28#include <type_traits>
29
30using namespace llvm;
31using namespace llvm::PatternMatch;
32
33namespace llvm::slpvectorizer {
34
35bool isConstant(Value *V) {
36 return isa<Constant>(Val: V) && !isa<ConstantExpr, GlobalValue>(Val: V);
37}
38
39bool isBinOpIdentityConstant(const Value *V, unsigned Opcode) {
40 const auto *CI = dyn_cast<ConstantInt>(Val: V);
41 return CI && ConstantExpr::getBinOpIdentity(Opcode, Ty: CI->getType()) == CI;
42}
43
44unsigned getReassocCombineOpcode(unsigned Opcode) {
45 switch (Opcode) {
46 case Instruction::Sub:
47 return Instruction::Add;
48 case Instruction::FSub:
49 return Instruction::FAdd;
50 default:
51 return Opcode;
52 }
53}
54
55bool isReassocChainLink(const Instruction *I) {
56 if (I->getOpcode() == Instruction::Sub)
57 return true;
58 if (I->getOpcode() == Instruction::FSub)
59 return I->hasAllowReassoc();
60 return I->isAssociative();
61}
62
63bool isVectorLikeInstWithConstOps(Value *V) {
64 auto *I = dyn_cast<Instruction>(Val: V);
65 // Non-instructions are vector-like only if they are undef.
66 if (!I)
67 return isa<UndefValue>(Val: V);
68 switch (I->getOpcode()) {
69 case Instruction::ExtractValue:
70 case Instruction::InsertValue:
71 return true;
72 case Instruction::ExtractElement:
73 return isa<FixedVectorType>(Val: I->getOperand(i: 0)->getType()) &&
74 isConstant(V: I->getOperand(i: 1));
75 case Instruction::InsertElement:
76 return isa<FixedVectorType>(Val: I->getOperand(i: 0)->getType()) &&
77 isConstant(V: I->getOperand(i: 2));
78 default:
79 return false;
80 }
81}
82
83unsigned getNumElements(Type *Ty) {
84 assert(!isa<ScalableVectorType>(Ty) &&
85 "ScalableVectorType is not supported.");
86 if (isVectorizedTy(Ty))
87 return getVectorizedTypeVF(Ty).getFixedValue();
88 return 1;
89}
90
91unsigned getPartNumElems(unsigned Size, unsigned NumParts) {
92 return std::min<unsigned>(a: Size, b: bit_ceil(Value: divideCeil(Numerator: Size, Denominator: NumParts)));
93}
94
95unsigned getNumElems(unsigned Size, unsigned PartNumElems, unsigned Part) {
96 return std::min<unsigned>(a: PartNumElems, b: Size - Part * PartNumElems);
97}
98
99#if !defined(NDEBUG)
100std::string shortBundleName(ArrayRef<Value *> VL, int Idx) {
101 std::string Result;
102 raw_string_ostream OS(Result);
103 if (Idx >= 0)
104 OS << "Idx: " << Idx << ", ";
105 OS << "n=" << VL.size() << " [" << *VL.front() << ", ..]";
106 return Result;
107}
108#endif
109
110bool allSameBlock(ArrayRef<Value *> VL) {
111 auto *It = find_if(Range&: VL, P: IsaPred<Instruction>);
112 if (It == VL.end())
113 return false;
114 Instruction *I0 = cast<Instruction>(Val: *It);
115 if (all_of(Range&: VL, P: isVectorLikeInstWithConstOps))
116 return true;
117
118 BasicBlock *BB = I0->getParent();
119 for (Value *V : iterator_range(It, VL.end())) {
120 if (isa<PoisonValue>(Val: V))
121 continue;
122 auto *II = dyn_cast<Instruction>(Val: V);
123 if (!II)
124 return false;
125
126 if (BB != II->getParent())
127 return false;
128 }
129 return true;
130}
131
132bool allConstant(ArrayRef<Value *> VL) {
133 // Constant expressions and globals can't be vectorized like normal integer/FP
134 // constants.
135 return all_of(Range&: VL, P: isConstant);
136}
137
138bool isSplat(ArrayRef<Value *> VL) {
139 Value *FirstNonUndef = nullptr;
140 for (Value *V : VL) {
141 if (isa<UndefValue>(Val: V))
142 continue;
143 if (!FirstNonUndef) {
144 FirstNonUndef = V;
145 continue;
146 }
147 if (V != FirstNonUndef)
148 return false;
149 }
150 return FirstNonUndef != nullptr;
151}
152
153Intrinsic::ID isEquivalentIntrinsicID(Intrinsic::ID LHS, Intrinsic::ID RHS) {
154 if (LHS == RHS)
155 return RHS;
156 if ((LHS == Intrinsic::fma || LHS == Intrinsic::fmuladd) &&
157 (RHS == Intrinsic::fma || RHS == Intrinsic::fmuladd))
158 return Intrinsic::fma;
159 return Intrinsic::not_intrinsic;
160}
161
162bool isCommutative(const Instruction *I, const Value *ValWithUses,
163 bool IsCopyable) {
164 if (auto *Cmp = dyn_cast<CmpInst>(Val: I))
165 return Cmp->isCommutative();
166 if (auto *BO = dyn_cast<BinaryOperator>(Val: I))
167 return BO->isCommutative() ||
168 (BO->getOpcode() == Instruction::Sub && ValWithUses->hasUseList() &&
169 !ValWithUses->hasNUsesOrMore(N: UsesLimit) &&
170 all_of(
171 Range: ValWithUses->uses(),
172 P: [&](const Use &U) {
173 // Commutative, if icmp eq/ne sub, 0
174 CmpPredicate Pred;
175 if (match(V: U.getUser(),
176 P: m_ICmp(Pred, L: m_Specific(V: U.get()), R: m_Zero())) &&
177 (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE))
178 return true;
179 // Commutative, if abs(sub nsw, true) or abs(sub, false).
180 ConstantInt *Flag;
181 auto *I = dyn_cast<BinaryOperator>(Val: U.get());
182 return match(V: U.getUser(),
183 P: m_Intrinsic<Intrinsic::abs>(
184 Ops: m_Specific(V: U.get()), Ops: m_ConstantInt(CI&: Flag))) &&
185 ((!IsCopyable && I && !I->hasNoSignedWrap()) ||
186 Flag->isOne());
187 })) ||
188 (BO->getOpcode() == Instruction::FSub && ValWithUses->hasUseList() &&
189 !ValWithUses->hasNUsesOrMore(N: UsesLimit) &&
190 all_of(Range: ValWithUses->uses(), P: [](const Use &U) {
191 return match(V: U.getUser(),
192 P: m_Intrinsic<Intrinsic::fabs>(Ops: m_Specific(V: U.get())));
193 }));
194 return I->isCommutative();
195}
196
197bool isCommutative(const Instruction *I) { return isCommutative(I, ValWithUses: I); }
198
199bool isCommutableOperand(const Instruction *I, Value *ValWithUses, unsigned Op,
200 bool IsCopyable) {
201 assert(isCommutative(I, ValWithUses, IsCopyable) &&
202 "The instruction is not commutative.");
203 if (isa<CmpInst>(Val: I))
204 return true;
205 if (auto *BO = dyn_cast<BinaryOperator>(Val: I)) {
206 switch (BO->getOpcode()) {
207 case Instruction::Sub:
208 case Instruction::FSub:
209 return true;
210 default:
211 break;
212 }
213 }
214 return I->isCommutableOperand(Op);
215}
216
217unsigned getNumberOfPotentiallyCommutativeOps(Instruction *I) {
218 if (isa<IntrinsicInst>(Val: I) && isCommutative(I)) {
219 // IntrinsicInst::isCommutative returns true if swapping the first "two"
220 // arguments to the intrinsic produces the same result.
221 constexpr unsigned IntrinsicNumOperands = 2;
222 return IntrinsicNumOperands;
223 }
224 return I->getNumOperands();
225}
226
227std::optional<unsigned> getElementIndex(const Value *Inst, unsigned Offset) {
228 if (auto Index = getInsertExtractIndex<InsertElementInst>(Inst, Offset))
229 return Index;
230 if (auto Index = getInsertExtractIndex<ExtractElementInst>(Inst, Offset))
231 return Index;
232
233 unsigned Index = Offset;
234
235 const auto *IV = dyn_cast<InsertValueInst>(Val: Inst);
236 if (!IV)
237 return std::nullopt;
238
239 Type *CurrentType = IV->getType();
240 for (unsigned I : IV->indices()) {
241 if (const auto *ST = dyn_cast<StructType>(Val: CurrentType)) {
242 Index *= ST->getNumElements();
243 CurrentType = ST->getElementType(N: I);
244 } else if (const auto *AT = dyn_cast<ArrayType>(Val: CurrentType)) {
245 Index *= AT->getNumElements();
246 CurrentType = AT->getElementType();
247 } else {
248 return std::nullopt;
249 }
250 Index += I;
251 }
252 return Index;
253}
254
255bool allSameOpcode(ArrayRef<Value *> VL) {
256 auto *It = find_if(Range&: VL, P: IsaPred<Instruction>);
257 if (It == VL.end())
258 return true;
259 Instruction *MainOp = cast<Instruction>(Val: *It);
260 unsigned Opcode = MainOp->getOpcode();
261 bool IsCmpOp = isa<CmpInst>(Val: MainOp);
262 CmpInst::Predicate BasePred = IsCmpOp ? cast<CmpInst>(Val: MainOp)->getPredicate()
263 : CmpInst::BAD_ICMP_PREDICATE;
264 return all_of(Range: make_range(x: It, y: VL.end()), P: [&](Value *V) {
265 if (auto *CI = dyn_cast<CmpInst>(Val: V))
266 return BasePred == CI->getPredicate();
267 if (auto *I = dyn_cast<Instruction>(Val: V))
268 return I->getOpcode() == Opcode;
269 return isa<PoisonValue>(Val: V);
270 });
271}
272
273std::optional<unsigned> getExtractIndex(const Instruction *E) {
274 unsigned Opcode = E->getOpcode();
275 assert((Opcode == Instruction::ExtractElement ||
276 Opcode == Instruction::ExtractValue) &&
277 "Expected extractelement or extractvalue instruction.");
278 if (Opcode == Instruction::ExtractElement) {
279 auto *CI = dyn_cast<ConstantInt>(Val: E->getOperand(i: 1));
280 if (!CI)
281 return std::nullopt;
282 // Check if the index is out of bound. We can get the source vector from
283 // operand 0.
284 unsigned Idx = CI->getZExtValue();
285 auto *EE = cast<ExtractElementInst>(Val: E);
286 const unsigned VF = getNumElements(Ty: EE->getVectorOperandType());
287 if (Idx >= VF)
288 return std::nullopt;
289 return Idx;
290 }
291 auto *EI = cast<ExtractValueInst>(Val: E);
292 if (EI->getNumIndices() != 1)
293 return std::nullopt;
294 return *EI->idx_begin();
295}
296
297void inversePermutation(ArrayRef<unsigned> Indices,
298 SmallVectorImpl<int> &Mask) {
299 Mask.clear();
300 const unsigned E = Indices.size();
301 Mask.resize(N: E, NV: PoisonMaskElem);
302 for (unsigned I = 0; I < E; ++I)
303 Mask[Indices[I]] = I;
304}
305
306void reorderScalars(SmallVectorImpl<Value *> &Scalars, ArrayRef<int> Mask) {
307 assert(!Mask.empty() && "Expected non-empty mask.");
308 SmallVector<Value *> Prev(Scalars.size(),
309 PoisonValue::get(T: Scalars.front()->getType()));
310 Prev.swap(RHS&: Scalars);
311 for (unsigned I = 0, E = Prev.size(); I < E; ++I)
312 if (Mask[I] != PoisonMaskElem)
313 Scalars[Mask[I]] = Prev[I];
314}
315
316bool allSameType(ArrayRef<Value *> VL) {
317 assert(!VL.empty() && "Expected non-empty list of values.");
318 Type *Ty = VL.consume_front()->getType();
319 return all_of(Range&: VL, P: [&](Value *V) { return V->getType() == Ty; });
320}
321
322template <typename T>
323std::optional<unsigned> getInsertExtractIndex(const Value *Inst,
324 unsigned Offset) {
325 static_assert(std::is_same_v<T, InsertElementInst> ||
326 std::is_same_v<T, ExtractElementInst>,
327 "unsupported T");
328 const auto *IE = dyn_cast<T>(Inst);
329 if (!IE)
330 return std::nullopt;
331 // InsertElement: result is the vector, index is op 2.
332 // ExtractElement: result is scalar, vector is op 0, index is op 1.
333 constexpr bool IsInsert = std::is_same_v<T, InsertElementInst>;
334 Type *VecTy = IsInsert ? IE->getType() : IE->getOperand(0)->getType();
335 const auto *VT = dyn_cast<FixedVectorType>(Val: VecTy);
336 if (!VT)
337 return std::nullopt;
338 const auto *CI = dyn_cast<ConstantInt>(IE->getOperand(IsInsert ? 2 : 1));
339 if (!CI)
340 return std::nullopt;
341 if (CI->getValue().uge(VT->getNumElements()))
342 return std::nullopt;
343 unsigned Index = Offset;
344 Index *= VT->getNumElements();
345 Index += CI->getZExtValue();
346 return Index;
347}
348
349// Only these two specializations are used; instantiate them here so the
350// definition can stay out of the header.
351template std::optional<unsigned>
352getInsertExtractIndex<InsertElementInst>(const Value *, unsigned);
353template std::optional<unsigned>
354getInsertExtractIndex<ExtractElementInst>(const Value *, unsigned);
355
356bool areAllOperandsNonInsts(Value *V) {
357 auto *I = dyn_cast<Instruction>(Val: V);
358 if (!I)
359 return true;
360 return !mayHaveNonDefUseDependency(I: *I) &&
361 all_of(Range: I->operands(), P: [I](Value *V) {
362 auto *IO = dyn_cast<Instruction>(Val: V);
363 if (!IO)
364 return true;
365 return isa<PHINode>(Val: IO) || IO->getParent() != I->getParent();
366 });
367}
368
369bool isUsedOutsideBlock(Value *V) {
370 auto *I = dyn_cast<Instruction>(Val: V);
371 if (!I)
372 return true;
373 // Limits the number of uses to save compile time.
374 return !I->mayReadOrWriteMemory() && !I->hasNUsesOrMore(N: UsesLimit) &&
375 all_of(Range: I->users(), P: [I](User *U) {
376 auto *IU = dyn_cast<Instruction>(Val: U);
377 if (!IU)
378 return true;
379 return IU->getParent() != I->getParent() || isa<PHINode>(Val: IU);
380 });
381}
382
383bool doesNotNeedToBeScheduled(Value *V) {
384 return areAllOperandsNonInsts(V) && isUsedOutsideBlock(V);
385}
386
387bool doesNotNeedToSchedule(ArrayRef<Value *> VL) {
388 return !VL.empty() &&
389 (all_of(Range&: VL, P: isUsedOutsideBlock) || all_of(Range&: VL, P: areAllOperandsNonInsts));
390}
391
392void transformScalarShuffleIndiciesToVector(unsigned VecTyNumElements,
393 SmallVectorImpl<int> &Mask) {
394 // The ShuffleBuilder implementation use shufflevector to splat an "element".
395 // But the element have different meaning for SLP (scalar) and REVEC
396 // (vector). We need to expand Mask into masks which shufflevector can use
397 // directly.
398 SmallVector<int> NewMask(Mask.size() * VecTyNumElements);
399 for (unsigned I : seq<unsigned>(Size: Mask.size()))
400 for (auto [J, MaskV] : enumerate(First: MutableArrayRef(NewMask).slice(
401 N: I * VecTyNumElements, M: VecTyNumElements)))
402 MaskV = Mask[I] == PoisonMaskElem ? PoisonMaskElem
403 : Mask[I] * VecTyNumElements + J;
404 Mask.swap(RHS&: NewMask);
405}
406
407unsigned getShufflevectorNumGroups(ArrayRef<Value *> VL) {
408 if (VL.empty())
409 return 0;
410 if (!all_of(Range&: VL, P: IsaPred<ShuffleVectorInst>))
411 return 0;
412 auto *SV = cast<ShuffleVectorInst>(Val: VL.front());
413 unsigned SVNumElements =
414 cast<FixedVectorType>(Val: SV->getOperand(i_nocapture: 0)->getType())->getNumElements();
415 unsigned ShuffleMaskSize = SV->getShuffleMask().size();
416 if (SVNumElements % ShuffleMaskSize != 0)
417 return 0;
418 unsigned GroupSize = SVNumElements / ShuffleMaskSize;
419 if (GroupSize == 0 || (VL.size() % GroupSize) != 0)
420 return 0;
421 unsigned NumGroup = 0;
422 for (size_t I = 0, E = VL.size(); I != E; I += GroupSize) {
423 auto *SV = cast<ShuffleVectorInst>(Val: VL[I]);
424 Value *Src = SV->getOperand(i_nocapture: 0);
425 ArrayRef<Value *> Group = VL.slice(N: I, M: GroupSize);
426 SmallBitVector ExpectedIndex(GroupSize);
427 if (!all_of(Range&: Group, P: [&](Value *V) {
428 auto *SV = cast<ShuffleVectorInst>(Val: V);
429 // From the same source.
430 if (SV->getOperand(i_nocapture: 0) != Src)
431 return false;
432 int Index;
433 if (!SV->isExtractSubvectorMask(Index))
434 return false;
435 ExpectedIndex.set(Index / ShuffleMaskSize);
436 return true;
437 }))
438 return 0;
439 if (!ExpectedIndex.all())
440 return 0;
441 ++NumGroup;
442 }
443 assert(NumGroup == (VL.size() / GroupSize) && "Unexpected number of groups");
444 return NumGroup;
445}
446
447SmallVector<int> calculateShufflevectorMask(ArrayRef<Value *> VL) {
448 assert(getShufflevectorNumGroups(VL) && "Not supported shufflevector usage.");
449 auto *SV = cast<ShuffleVectorInst>(Val: VL.front());
450 unsigned SVNumElements =
451 cast<FixedVectorType>(Val: SV->getOperand(i_nocapture: 0)->getType())->getNumElements();
452 SmallVector<int> Mask;
453 unsigned AccumulateLength = 0;
454 for (Value *V : VL) {
455 auto *SV = cast<ShuffleVectorInst>(Val: V);
456 for (int M : SV->getShuffleMask())
457 Mask.push_back(Elt: M == PoisonMaskElem ? PoisonMaskElem
458 : AccumulateLength + M);
459 AccumulateLength += SVNumElements;
460 }
461 return Mask;
462}
463
464SmallBitVector buildUseMask(int VF, ArrayRef<int> Mask, UseMask MaskArg) {
465 SmallBitVector UseMask(VF, true);
466 for (auto [Idx, Value] : enumerate(First&: Mask)) {
467 if (Value == PoisonMaskElem) {
468 if (MaskArg == UseMask::UndefsAsMask)
469 UseMask.reset(Idx);
470 continue;
471 }
472 if (MaskArg == UseMask::FirstArg && Value < VF)
473 UseMask.reset(Idx: Value);
474 else if (MaskArg == UseMask::SecondArg && Value >= VF)
475 UseMask.reset(Idx: Value - VF);
476 }
477 return UseMask;
478}
479
480template <bool IsPoisonOnly>
481SmallBitVector isUndefVector(const Value *V, const SmallBitVector &UseMask) {
482 SmallBitVector Res(UseMask.empty() ? 1 : UseMask.size(), true);
483 using T = std::conditional_t<IsPoisonOnly, PoisonValue, UndefValue>;
484 if (isa<T>(V))
485 return Res;
486 auto *VecTy = dyn_cast<FixedVectorType>(Val: V->getType());
487 if (!VecTy)
488 return Res.reset();
489 auto *C = dyn_cast<Constant>(Val: V);
490 if (!C) {
491 if (!UseMask.empty()) {
492 const Value *Base = V;
493 while (auto *II = dyn_cast<InsertElementInst>(Val: Base)) {
494 Base = II->getOperand(i_nocapture: 0);
495 if (isa<T>(II->getOperand(i_nocapture: 1)))
496 continue;
497 std::optional<unsigned> Idx = getElementIndex(Inst: II);
498 if (!Idx) {
499 Res.reset();
500 return Res;
501 }
502 if (*Idx < UseMask.size() && !UseMask.test(Idx: *Idx))
503 Res.reset(Idx: *Idx);
504 }
505 // TODO: Add analysis for shuffles here too.
506 if (V == Base) {
507 Res.reset();
508 } else {
509 SmallBitVector SubMask(UseMask.size(), false);
510 Res &= isUndefVector<IsPoisonOnly>(Base, SubMask);
511 }
512 } else {
513 Res.reset();
514 }
515 return Res;
516 }
517 for (unsigned I = 0, E = VecTy->getNumElements(); I != E; ++I) {
518 if (Constant *Elem = C->getAggregateElement(Elt: I))
519 if (!isa<T>(Elem) &&
520 (UseMask.empty() || (I < UseMask.size() && !UseMask.test(Idx: I))))
521 Res.reset(Idx: I);
522 }
523 return Res;
524}
525
526template SmallBitVector isUndefVector<false>(const Value *,
527 const SmallBitVector &);
528template SmallBitVector isUndefVector<true>(const Value *,
529 const SmallBitVector &);
530
531bool doesInTreeUserNeedToExtract(Value *Scalar, Instruction *UserInst,
532 TargetLibraryInfo *TLI,
533 const TargetTransformInfo *TTI) {
534 if (!UserInst)
535 return false;
536 unsigned Opcode = UserInst->getOpcode();
537 switch (Opcode) {
538 case Instruction::Load: {
539 LoadInst *LI = cast<LoadInst>(Val: UserInst);
540 return (LI->getPointerOperand() == Scalar);
541 }
542 case Instruction::Store: {
543 StoreInst *SI = cast<StoreInst>(Val: UserInst);
544 return (SI->getPointerOperand() == Scalar);
545 }
546 case Instruction::Call: {
547 CallInst *CI = cast<CallInst>(Val: UserInst);
548 Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI);
549 return any_of(Range: enumerate(First: CI->args()), P: [&](auto &&Arg) {
550 return isVectorIntrinsicWithScalarOpAtArg(ID, Arg.index(), TTI) &&
551 Arg.value().get() == Scalar;
552 });
553 }
554 default:
555 return false;
556 }
557}
558
559MemoryLocation getLocation(Instruction *I) {
560 if (StoreInst *SI = dyn_cast<StoreInst>(Val: I))
561 return MemoryLocation::get(SI);
562 if (LoadInst *LI = dyn_cast<LoadInst>(Val: I))
563 return MemoryLocation::get(LI);
564 return MemoryLocation();
565}
566
567bool isSimple(Instruction *I) {
568 if (LoadInst *LI = dyn_cast<LoadInst>(Val: I))
569 return LI->isSimple();
570 if (StoreInst *SI = dyn_cast<StoreInst>(Val: I))
571 return SI->isSimple();
572 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Val: I))
573 return !MI->isVolatile();
574 return true;
575}
576
577bool isSelectedBaseLoad(Type *ScalarTy, ArrayRef<Value *> PointerOps,
578 const DataLayout &DL, Value *&TrueBase,
579 Value *&FalseBase,
580 SmallVectorImpl<Value *> &Conditions) {
581 TrueBase = nullptr;
582 FalseBase = nullptr;
583 uint64_t ScalarSize = DL.getTypeStoreSize(Ty: ScalarTy);
584 Conditions.assign(NumElts: PointerOps.size(), Elt: nullptr);
585 for (auto [Idx, P] : enumerate(First&: PointerOps)) {
586 Value *Base = P;
587 uint64_t Offset = 0;
588 if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: P)) {
589 APInt OffsetAP(DL.getIndexTypeSizeInBits(Ty: GEP->getType()), 0);
590 if (!GEP->accumulateConstantOffset(DL, Offset&: OffsetAP) || OffsetAP.isNegative())
591 return false;
592 Offset = OffsetAP.getZExtValue();
593 Base = GEP->getPointerOperand();
594 }
595 auto *Sel = dyn_cast<SelectInst>(Val: Base);
596 if (!Sel)
597 return false;
598 Value *T = Sel->getTrueValue();
599 Value *F = Sel->getFalseValue();
600 if (!TrueBase) {
601 if (T == F)
602 return false;
603 TrueBase = T;
604 FalseBase = F;
605 } else if (TrueBase != T || FalseBase != F) {
606 return false;
607 }
608 // Lane Idx must be at exactly Base + Idx * sizeof(ScalarTy); codegen reads
609 // contiguously from TrueBase/FalseBase starting at lane 0.
610 if (Offset != static_cast<uint64_t>(Idx) * ScalarSize)
611 return false;
612 Conditions[Idx] = Sel->getCondition();
613 }
614 return TrueBase != nullptr;
615}
616
617void addMask(SmallVectorImpl<int> &Mask, ArrayRef<int> SubMask,
618 bool ExtendingManyInputs) {
619 if (SubMask.empty())
620 return;
621 assert(
622 (!ExtendingManyInputs || SubMask.size() > Mask.size() ||
623 // Check if input scalars were extended to match the size of other node.
624 (SubMask.size() == Mask.size() && Mask.back() == PoisonMaskElem)) &&
625 "SubMask with many inputs support must be larger than the mask.");
626 if (Mask.empty()) {
627 Mask.append(in_start: SubMask.begin(), in_end: SubMask.end());
628 return;
629 }
630 SmallVector<int> NewMask(SubMask.size(), PoisonMaskElem);
631 int TermValue = std::min(a: Mask.size(), b: SubMask.size());
632 for (int I = 0, E = SubMask.size(); I < E; ++I) {
633 if (SubMask[I] == PoisonMaskElem ||
634 (!ExtendingManyInputs &&
635 (SubMask[I] >= TermValue || Mask[SubMask[I]] >= TermValue)))
636 continue;
637 NewMask[I] = Mask[SubMask[I]];
638 }
639 Mask.swap(RHS&: NewMask);
640}
641
642void fixupOrderingIndices(MutableArrayRef<unsigned> Order) {
643 const size_t Sz = Order.size();
644 SmallBitVector UnusedIndices(Sz, /*t=*/true);
645 SmallBitVector MaskedIndices(Sz);
646 for (unsigned I = 0; I < Sz; ++I) {
647 if (Order[I] < Sz)
648 UnusedIndices.reset(Idx: Order[I]);
649 else
650 MaskedIndices.set(I);
651 }
652 if (MaskedIndices.none())
653 return;
654 assert(UnusedIndices.count() == MaskedIndices.count() &&
655 "Non-synced masked/available indices.");
656 int Idx = UnusedIndices.find_first();
657 int MIdx = MaskedIndices.find_first();
658 while (MIdx >= 0) {
659 assert(Idx >= 0 && "Indices must be synced.");
660 Order[MIdx] = Idx;
661 Idx = UnusedIndices.find_next(Prev: Idx);
662 MIdx = MaskedIndices.find_next(Prev: MIdx);
663 }
664}
665
666SmallBitVector getAltInstrMask(ArrayRef<Value *> VL, Type *ScalarTy,
667 unsigned Opcode0, unsigned Opcode1) {
668 unsigned ScalarTyNumElements = getNumElements(Ty: ScalarTy);
669 SmallBitVector OpcodeMask(VL.size() * ScalarTyNumElements, false);
670 for (unsigned Lane : seq<unsigned>(Size: VL.size())) {
671 if (isa<PoisonValue>(Val: VL[Lane]))
672 continue;
673 if (cast<Instruction>(Val: VL[Lane])->getOpcode() == Opcode1)
674 OpcodeMask.set(I: Lane * ScalarTyNumElements,
675 E: Lane * ScalarTyNumElements + ScalarTyNumElements);
676 }
677 return OpcodeMask;
678}
679
680SmallVector<Constant *> replicateMask(ArrayRef<Constant *> Val, unsigned VF) {
681 assert(none_of(Val, [](Constant *C) { return C->getType()->isVectorTy(); }) &&
682 "Expected scalar constants.");
683 SmallVector<Constant *> NewVal(Val.size() * VF);
684 for (auto [I, V] : enumerate(First&: Val))
685 std::fill_n(first: NewVal.begin() + I * VF, n: VF, value: V);
686 return NewVal;
687}
688
689Intrinsic::ID getMaskedDivRemIntrinsic(unsigned Opcode) {
690 switch (Opcode) {
691 case Instruction::UDiv:
692 return Intrinsic::masked_udiv;
693 case Instruction::SDiv:
694 return Intrinsic::masked_sdiv;
695 case Instruction::URem:
696 return Intrinsic::masked_urem;
697 case Instruction::SRem:
698 return Intrinsic::masked_srem;
699 default:
700 llvm_unreachable("Unexpected opcode");
701 }
702}
703
704/// Returns true if \p I is a part of a single-use chain, computing an address,
705/// which does not pay off the vectorization: a constant table is accessed by a
706/// gather, while the indices, unrelated between the lanes, require a full
707/// buildvector, unlike the ones, shifted by a constant from a common base.
708static bool isNonProfitableIndex(const Instruction *I) {
709 constexpr unsigned MaxIndexChainLength = 3;
710 // A constant shift of a common base is a cheap buildvector, while the loads
711 // are vectorized together with the indices, computed from them.
712 auto IsProfitableOperand = [](const Value *V) {
713 if (isa<Constant>(Val: V))
714 return true;
715 if (const auto *Cast = dyn_cast<CastInst>(Val: V); Cast && Cast->hasOneUse())
716 V = Cast->getOperand(i_nocapture: 0);
717 return isa<LoadInst>(Val: V);
718 };
719 const User *U = I->user_back();
720 for ([[maybe_unused]] unsigned _ : seq<unsigned>(Size: MaxIndexChainLength)) {
721 if (const auto *GEP = dyn_cast<GetElementPtrInst>(Val: U))
722 return isa<Constant>(Val: GEP->getPointerOperand()) ||
723 none_of(Range: I->operand_values(), P: IsProfitableOperand);
724 if (!isa<Instruction>(Val: U) || !U->hasOneUse())
725 return false;
726 U = U->user_back();
727 }
728 return false;
729}
730
731bool isOnceUsedSeed(const Instruction *I) {
732 if (!I->hasOneUse() || isNonProfitableIndex(I))
733 return false;
734 // The operation with the identity or the absorbing constant is folded away
735 // before the codegen, the vector node only repacks the lanes.
736 if (const auto *BO = dyn_cast<BinaryOperator>(Val: I)) {
737 unsigned Opcode = BO->getOpcode();
738 Type *Ty = BO->getType();
739 for (unsigned Idx : seq<unsigned>(Size: 2)) {
740 const auto *C = dyn_cast<Constant>(Val: BO->getOperand(i_nocapture: Idx));
741 if (C && (C == ConstantExpr::getBinOpIdentity(
742 Opcode, Ty, /*AllowRHSConstant=*/Idx == 1) ||
743 C == ConstantExpr::getBinOpAbsorber(
744 Opcode, Ty, /*AllowLHSConstant=*/Idx == 0)))
745 return false;
746 }
747 }
748 const User *U = I->user_back();
749 if (isa<ExtractElementInst, ExtractValueInst>(Val: I))
750 return isa<InsertElementInst, InsertValueInst>(Val: U);
751 if (isa<CastInst>(Val: I))
752 return !isa<FPToSIInst, FPToUIInst>(Val: I) &&
753 (!isa<CastInst>(Val: U) || U->hasOneUse());
754 return isa<BinaryOperator, UnaryOperator, SelectInst, FreezeInst, CallInst>(
755 Val: I);
756}
757
758Instruction *lookThroughCastRoundTrip(Value *V, bool MustBeElidable) {
759 auto *Wide = dyn_cast<FPExtInst>(Val: V);
760 if (!Wide || !Wide->hasOneUse())
761 return nullptr;
762 auto *Narrow = dyn_cast<FPTruncInst>(Val: Wide->getOperand(i_nocapture: 0));
763 if (!Narrow || !Narrow->hasOneUse())
764 return nullptr;
765 Value *Src = Narrow->getOperand(i_nocapture: 0);
766 if (!isa<Instruction>(Val: Src) || Src->getType() != Wide->getType())
767 return nullptr;
768 if (MustBeElidable && !(Wide->hasAllowContract() && Wide->hasNoNaNs() &&
769 Wide->hasNoInfs() && Narrow->hasAllowContract()))
770 return nullptr;
771 return Narrow;
772}
773
774namespace {
775
776/// Shifts and the mask accumulated from the narrow ops on the current path:
777/// the shifts above and at the narrow level, the bitwidth of the narrow ops
778/// (0 if none) and the mask from the absorbed narrow ands.
779struct NarrowedChainState {
780 unsigned Shift = 0;
781 unsigned NarrowShift = 0;
782 unsigned NarrowBW = 0;
783 APInt NarrowMask = APInt(1, 0);
784
785 /// The mask for the absorbed narrow ops in the leaf type, applied before
786 /// widening and shifting; all-ones if nothing was absorbed.
787 APInt getMask(unsigned LeafBW) const {
788 if (NarrowBW == 0)
789 return APInt::getAllOnes(numBits: LeafBW);
790 return (NarrowMask & (APInt::getAllOnes(numBits: NarrowBW) << NarrowShift))
791 .lshr(shiftAmt: NarrowShift)
792 .trunc(width: LeafBW);
793 }
794};
795
796} // namespace
797
798static void
799collectNarrowedLeavesImpl(Value *V, unsigned RdxOpcode, unsigned WideBW,
800 NarrowedChainState S, unsigned Depth,
801 unsigned MaxDepth,
802 SmallVectorImpl<NarrowedLeafInfo> &Leaves,
803 SmallVectorImpl<Instruction *> &ChainInsts) {
804 if (Depth < MaxDepth) {
805 if (auto *Z = dyn_cast<ZExtInst>(Val: V);
806 Z && Z->getSrcTy()->isIntegerTy() && !Z->getSrcTy()->isIntegerTy(BitWidth: 1)) {
807 ChainInsts.push_back(Elt: Z);
808 return collectNarrowedLeavesImpl(V: Z->getOperand(i_nocapture: 0), RdxOpcode, WideBW, S,
809 Depth: Depth + 1, MaxDepth, Leaves, ChainInsts);
810 }
811 if (auto *BO = dyn_cast<BinaryOperator>(Val: V)) {
812 if (BO->getOpcode() == RdxOpcode) {
813 ChainInsts.push_back(Elt: BO);
814 collectNarrowedLeavesImpl(V: BO->getOperand(i_nocapture: 0), RdxOpcode, WideBW, S,
815 Depth: Depth + 1, MaxDepth, Leaves, ChainInsts);
816 collectNarrowedLeavesImpl(V: BO->getOperand(i_nocapture: 1), RdxOpcode, WideBW, S,
817 Depth: Depth + 1, MaxDepth, Leaves, ChainInsts);
818 return;
819 }
820 const APInt *Amt;
821 unsigned BW = V->getType()->getScalarSizeInBits();
822 auto *Z = dyn_cast<ZExtInst>(Val: BO->getOperand(i_nocapture: 0));
823 if (BO->getOpcode() == Instruction::Shl && Z && S.NarrowBW == 0 &&
824 match(V: BO->getOperand(i_nocapture: 1), P: m_APInt(Res&: Amt)) && Amt->ult(RHS: BW) &&
825 Z->getSrcTy()->isIntegerTy() && !Z->getSrcTy()->isIntegerTy(BitWidth: 1) &&
826 (BW == WideBW ||
827 Z->getSrcTy()->getIntegerBitWidth() + Amt->getZExtValue() <= BW) &&
828 S.Shift + Amt->getZExtValue() < WideBW) {
829 ChainInsts.push_back(Elt: BO);
830 ChainInsts.push_back(Elt: Z);
831 S.Shift += Amt->getZExtValue();
832 return collectNarrowedLeavesImpl(V: Z->getOperand(i_nocapture: 0), RdxOpcode, WideBW, S,
833 Depth: Depth + 1, MaxDepth, Leaves,
834 ChainInsts);
835 }
836 // Narrow shls fold into the shift and narrow ands into the mask; the
837 // mask clears the bits the shls shift out. Only same-width ops compose
838 // on one path, and the combined shift must stay a valid shift amount in
839 // both types.
840 if (BW < WideBW && (S.NarrowBW == 0 || BW == S.NarrowBW)) {
841 if (BO->getOpcode() == Instruction::Shl &&
842 match(V: BO->getOperand(i_nocapture: 1), P: m_APInt(Res&: Amt)) && Amt->ult(RHS: BW) &&
843 S.NarrowShift + Amt->getZExtValue() < BW &&
844 S.Shift + S.NarrowShift + Amt->getZExtValue() < WideBW) {
845 ChainInsts.push_back(Elt: BO);
846 if (BO->hasNoUnsignedWrap() && S.NarrowBW == 0) {
847 S.Shift += Amt->getZExtValue();
848 // Lossless shls shift out only known-zero bits; record them as
849 // the mask so matching lanes can form a splat.
850 S.NarrowBW = BW;
851 S.NarrowMask = APInt::getLowBitsSet(numBits: BW, loBitsSet: BW - Amt->getZExtValue());
852 } else {
853 if (S.NarrowBW == 0) {
854 S.NarrowBW = BW;
855 S.NarrowMask = APInt::getAllOnes(numBits: BW);
856 }
857 S.NarrowShift += Amt->getZExtValue();
858 }
859 return collectNarrowedLeavesImpl(V: BO->getOperand(i_nocapture: 0), RdxOpcode, WideBW,
860 S, Depth: Depth + 1, MaxDepth, Leaves,
861 ChainInsts);
862 }
863 Value *X;
864 if (match(V: BO, P: m_c_And(L: m_Value(V&: X), R: m_APInt(Res&: Amt)))) {
865 ChainInsts.push_back(Elt: BO);
866 if (S.NarrowBW == 0) {
867 S.NarrowBW = BW;
868 S.NarrowMask = APInt::getAllOnes(numBits: BW);
869 }
870 S.NarrowMask &= *Amt << S.NarrowShift;
871 return collectNarrowedLeavesImpl(V: X, RdxOpcode, WideBW, S, Depth: Depth + 1,
872 MaxDepth, Leaves, ChainInsts);
873 }
874 }
875 }
876 }
877 Leaves.emplace_back(Args&: V, Args: S.Shift + S.NarrowShift,
878 Args: S.getMask(LeafBW: V->getType()->getScalarSizeInBits()));
879}
880
881void collectNarrowedLeaves(Value *V, unsigned RdxOpcode, unsigned WideBW,
882 unsigned MaxDepth,
883 SmallVectorImpl<NarrowedLeafInfo> &Leaves,
884 SmallVectorImpl<Instruction *> &ChainInsts) {
885 collectNarrowedLeavesImpl(V, RdxOpcode, WideBW, S: NarrowedChainState(),
886 /*Depth=*/0, MaxDepth, Leaves, ChainInsts);
887}
888
889TargetTransformInfo::TargetCostKind getSLPCostKind(const Function *F) {
890 assert(F && "Expected function.");
891 return F->hasOptSize() ? TTI::TCK_CodeSize : TTI::TCK_RecipThroughput;
892}
893
894} // namespace llvm::slpvectorizer
895