1//===- SLPUtils.h - SLP Vectorizer free utility helpers --------*- C++ -*-===//
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// Internal header used by SLPVectorizer.cpp. It declares free helper
10// functions that do not depend on BoUpSLP, InstructionsState, or any other
11// SLP-private type. Splitting them out keeps SLPVectorizer.cpp focused on
12// the build / legality / cost / codegen pipeline.
13//
14//===----------------------------------------------------------------------===//
15
16#ifndef LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPUTILS_H
17#define LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPUTILS_H
18
19#include "llvm/ADT/APInt.h"
20#include "llvm/ADT/ArrayRef.h"
21#include "llvm/ADT/STLExtras.h"
22#include "llvm/ADT/STLFunctionalExtras.h"
23#include "llvm/ADT/SmallBitVector.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/Analysis/MemoryLocation.h"
26#include "llvm/Analysis/TargetTransformInfo.h"
27#include "llvm/IR/Intrinsics.h"
28
29#include <cstdint>
30#include <limits>
31#include <optional>
32#include <string>
33#include <tuple>
34
35namespace llvm {
36class AssumptionCache;
37class Constant;
38class DataLayout;
39class DebugLoc;
40class InsertElementInst;
41class Instruction;
42class IRBuilderBase;
43class LoadInst;
44class Loop;
45class PHINode;
46class ScalarEvolution;
47class SelectInst;
48class TargetLibraryInfo;
49class Type;
50class Value;
51} // namespace llvm
52
53namespace llvm::slpvectorizer {
54
55class SLPAnalysisCache;
56
57/// Limit of the number of uses for potentially transformed instructions/values,
58/// used in checks to avoid compile-time explode.
59inline constexpr int UsesLimit = 64;
60
61/// \returns True if the value is a constant (but not globals/constant
62/// expressions).
63bool isConstant(Value *V);
64
65/// \returns the identity constant of type \p Ty for the operands of the
66/// binary \p Opcode chain (e.g. 0 for add, 1 for mul, all-ones for and, -0.0
67/// for fadd, 1.0 for fmul). If \p Negated, the identity of an operand
68/// subtracted from the chain, which is +0.0 for fadd.
69Constant *getReassocIdentity(unsigned Opcode, Type *Ty, bool Negated);
70
71/// \returns True if \p V is the identity constant for the operands of the
72/// binary \p Opcode chain, subtracted from the chain if \p Negated.
73bool isBinOpIdentityConstant(const Value *V, unsigned Opcode,
74 bool Negated = false);
75
76/// \returns True if \p V is an integer binary operator, which gives an undef
77/// result for the undef operands: neither a shift nor a division.
78bool isUndefTolerantBinOp(const Value *V);
79
80/// \returns the load operand of the undef tolerant binary operator \p V, if
81/// any.
82const LoadInst *getLoadOfUndefTolerantBinOp(const Value *V);
83
84/// \returns the opcode of the combines emitted for a reassociated node:
85/// subtract chains regroup their positive and negative operand columns with
86/// plain adds.
87unsigned getReassocCombineOpcode(unsigned Opcode);
88
89/// \returns True if \p I can be a link of a flattenable binary chain:
90/// subtracts flatten as adds of a negated leaf, float subtracts need reassoc
91/// to allow the regrouping.
92bool isReassocChainLink(const Instruction *I);
93
94/// Checks if \p V is one of vector-like instructions, i.e. undef,
95/// insertelement/extractelement with constant indices for fixed vector type
96/// or extractvalue instruction.
97bool isVectorLikeInstWithConstOps(Value *V);
98
99/// \returns the number of elements for Ty.
100unsigned getNumElements(Type *Ty);
101
102/// Returns power-of-2 number of elements in a single register (part), given
103/// the total number of elements \p Size and number of registers (parts) \p
104/// NumParts.
105unsigned getPartNumElems(unsigned Size, unsigned NumParts);
106
107/// Returns correct remaining number of elements, considering total amount
108/// \p Size, (power-of-2 number) of elements in a single register
109/// \p PartNumElems and current register (part) \p Part.
110unsigned getNumElems(unsigned Size, unsigned PartNumElems, unsigned Part);
111
112#if !defined(NDEBUG)
113/// Print a short descriptor of the instruction bundle suitable for debug
114/// output.
115std::string shortBundleName(ArrayRef<Value *> VL, int Idx = -1);
116#endif
117
118/// \returns True if all of the instructions in \p VL are in the same block.
119bool allSameBlock(ArrayRef<Value *> VL);
120
121/// \returns True if all of the values in \p VL are constants (but not
122/// globals/constant expressions).
123bool allConstant(ArrayRef<Value *> VL);
124
125/// \returns True if all of the values in \p VL are identical or some of them
126/// are UndefValue.
127bool isSplat(ArrayRef<Value *> VL);
128
129/// Checks if \p LHS and \p RHS are the same intrinsic, or one is llvm.fma
130/// and the other is llvm.fmuladd, since both lower to the same fused
131/// vector operation.
132/// \returns the intrinsic ID to use for the pair (\p RHS if the IDs match,
133/// otherwise Intrinsic::fma), or Intrinsic::not_intrinsic if they are not
134/// equivalent.
135Intrinsic::ID isEquivalentIntrinsicID(Intrinsic::ID LHS, Intrinsic::ID RHS);
136
137/// \returns True if \p I is commutative, handles CmpInst and BinaryOperator.
138/// For BinaryOperator, it also checks if \p ValWithUses is used in specific
139/// patterns that make it effectively commutative (like equality comparisons
140/// with zero).
141/// In most cases, users should not call this function directly (since \p I and
142/// \p ValWithUses are the same). However, when analyzing interchangeable
143/// instructions, we need to use the converted opcode along with the original
144/// uses.
145/// \param I The instruction to check for commutativity
146/// \param ValWithUses The value whose uses are analyzed for special
147/// patterns
148bool isCommutative(const Instruction *I, const Value *ValWithUses,
149 bool IsCopyable = false);
150
151/// This is a helper function to check whether \p I is commutative.
152/// This is a convenience wrapper that calls the two-parameter version of
153/// isCommutative with the same instruction for both parameters. This is
154/// the common case where the instruction being checked for commutativity
155/// is the same as the instruction whose uses are analyzed for special
156/// patterns (see the two-parameter version above for details).
157/// \param I The instruction to check for commutativity
158/// \returns true if the instruction is commutative, false otherwise
159bool isCommutative(const Instruction *I);
160
161/// Checks if the operand is commutative. In commutative operations, not all
162/// operands might commutable, e.g. for fmuladd only 2 first operands are
163/// commutable.
164bool isCommutableOperand(const Instruction *I, Value *ValWithUses, unsigned Op,
165 bool IsCopyable = false);
166
167/// \returns number of operands of \p I, considering commutativity. Returns 2
168/// for commutative intrinsics.
169/// \param I The instruction to check for commutativity
170unsigned getNumberOfPotentiallyCommutativeOps(Instruction *I);
171
172/// \returns inserting or extracting index of InsertElement, ExtractElement
173/// or InsertValue instruction, using \p Offset as base offset for index.
174/// \returns std::nullopt if the index is not an immediate.
175std::optional<unsigned> getElementIndex(const Value *Inst, unsigned Offset = 0);
176
177/// \returns True if all of the values in \p VL use the same opcode.
178/// For comparison instructions, also checks if predicates match.
179/// PoisonValues are considered matching. Interchangeable instructions are
180/// not considered.
181bool allSameOpcode(ArrayRef<Value *> VL);
182
183/// \returns Optional element Idx for Extract{Value,Element} instructions.
184std::optional<unsigned> getExtractIndex(const Instruction *E);
185
186/// Compute the inverse permutation \p Mask of \p Indices.
187void inversePermutation(ArrayRef<unsigned> Indices, SmallVectorImpl<int> &Mask);
188
189/// Reorders the list of scalars in accordance with the given \p Mask.
190void reorderScalars(SmallVectorImpl<Value *> &Scalars, ArrayRef<int> Mask);
191
192/// Reorders the given \p Reuses mask according to the given \p Mask. \p Reuses
193/// contains original mask for the scalars reused in the node. Procedure
194/// transform this mask in accordance with the given \p Mask.
195void reorderReuses(SmallVectorImpl<int> &Reuses, ArrayRef<int> Mask);
196
197/// Reorders the given \p Order according to the given \p Mask. \p Order - is
198/// the original order of the scalars. Procedure transforms the provided order
199/// in accordance with the given \p Mask. If the resulting \p Order is just an
200/// identity order, \p Order is cleared.
201void reorderOrder(SmallVectorImpl<unsigned> &Order, ArrayRef<int> Mask,
202 bool BottomOrder = false);
203
204/// Check if \p Order represents reverse order.
205bool isReverseOrder(ArrayRef<unsigned> Order);
206
207/// Checks if the given mask is a "clustered" mask with the same clusters of
208/// size \p Sz, which are not identity submasks.
209bool isRepeatedNonIdentityClusteredMask(ArrayRef<int> Mask, unsigned Sz);
210
211/// Fills unset elements of \p Order (marked with the sentinel value equal to
212/// the order size) with the corresponding elements of \p SecondaryOrder,
213/// skipping already used indices, or with the identity order if
214/// \p SecondaryOrder is empty.
215void combineOrders(MutableArrayRef<unsigned> Order,
216 ArrayRef<unsigned> SecondaryOrder);
217
218/// \returns True iff every value in \p VL has the same Type as the first.
219bool allSameType(ArrayRef<Value *> VL);
220
221/// Checks if the provided value does not require scheduling. It does not
222/// require scheduling if this is not an instruction or it is an instruction
223/// that does not read/write memory and all operands are either not
224/// instructions or phi nodes or instructions from different blocks.
225bool areAllOperandsNonInsts(Value *V);
226
227/// Checks if the provided value does not require scheduling. It does not
228/// require scheduling if this is not an instruction or it is an instruction
229/// that does not read/write memory and all users are phi nodes or
230/// instructions from different blocks.
231bool isUsedOutsideBlock(Value *V);
232
233/// Checks if the specified value does not require scheduling. It does not
234/// require scheduling if all operands and all users do not need to be
235/// scheduled in the current basic block.
236bool doesNotNeedToBeScheduled(Value *V);
237
238/// Checks if the specified array of instructions does not require scheduling.
239/// It is so if all either instructions have operands that do not require
240/// scheduling or their users do not require scheduling since they are phis or
241/// in other basic blocks.
242bool doesNotNeedToSchedule(ArrayRef<Value *> VL);
243
244/// \returns inserting or extracting index of InsertElement / ExtractElement
245/// instruction, using \p Offset as base offset for index. Only instantiated
246/// for InsertElementInst and ExtractElementInst (see SLPUtils.cpp).
247template <typename T>
248std::optional<unsigned> getInsertExtractIndex(const Value *Inst,
249 unsigned Offset);
250
251void transformScalarShuffleIndiciesToVector(unsigned VecTyNumElements,
252 SmallVectorImpl<int> &Mask);
253
254/// \returns the number of groups of shufflevector
255/// A group has the following features
256/// 1. All of value in a group are shufflevector.
257/// 2. The mask of all shufflevector is isExtractSubvectorMask.
258/// 3. The mask of all shufflevector uses all of the elements of the source.
259/// e.g., it is 1 group (%0)
260/// %1 = shufflevector <16 x i8> %0, <16 x i8> poison,
261/// <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
262/// %2 = shufflevector <16 x i8> %0, <16 x i8> poison,
263/// <8 x i32> <i32 8, i32 9, i32 10, i32 11, i32 12, i32 13, i32 14, i32 15>
264/// it is 2 groups (%3 and %4)
265/// %5 = shufflevector <8 x i16> %3, <8 x i16> poison,
266/// <4 x i32> <i32 0, i32 1, i32 2, i32 3>
267/// %6 = shufflevector <8 x i16> %3, <8 x i16> poison,
268/// <4 x i32> <i32 4, i32 5, i32 6, i32 7>
269/// %7 = shufflevector <8 x i16> %4, <8 x i16> poison,
270/// <4 x i32> <i32 0, i32 1, i32 2, i32 3>
271/// %8 = shufflevector <8 x i16> %4, <8 x i16> poison,
272/// <4 x i32> <i32 4, i32 5, i32 6, i32 7>
273/// it is 0 group
274/// %12 = shufflevector <8 x i16> %10, <8 x i16> poison,
275/// <4 x i32> <i32 0, i32 1, i32 2, i32 3>
276/// %13 = shufflevector <8 x i16> %11, <8 x i16> poison,
277/// <4 x i32> <i32 0, i32 1, i32 2, i32 3>
278unsigned getShufflevectorNumGroups(ArrayRef<Value *> VL);
279
280/// \returns a shufflevector mask which is used to vectorize shufflevectors
281/// e.g.,
282/// %5 = shufflevector <8 x i16> %3, <8 x i16> poison,
283/// <4 x i32> <i32 0, i32 1, i32 2, i32 3>
284/// %6 = shufflevector <8 x i16> %3, <8 x i16> poison,
285/// <4 x i32> <i32 4, i32 5, i32 6, i32 7>
286/// %7 = shufflevector <8 x i16> %4, <8 x i16> poison,
287/// <4 x i32> <i32 0, i32 1, i32 2, i32 3>
288/// %8 = shufflevector <8 x i16> %4, <8 x i16> poison,
289/// <4 x i32> <i32 4, i32 5, i32 6, i32 7>
290/// the result is
291/// <0, 1, 2, 3, 12, 13, 14, 15, 16, 17, 18, 19, 28, 29, 30, 31>
292SmallVector<int> calculateShufflevectorMask(ArrayRef<Value *> VL);
293
294/// Checks if the values in \p VL can be represented as a shuffle of at most
295/// two vector operands (extractelement lanes). On success, \p Mask is the
296/// equivalent shuffle mask.
297std::optional<TargetTransformInfo::ShuffleKind>
298isFixedVectorShuffle(ArrayRef<Value *> VL, SmallVectorImpl<int> &Mask,
299 AssumptionCache *AC, SLPAnalysisCache &Cache);
300
301/// Creates subvector insert. Generates shuffle using \p Generator or
302/// using default shuffle.
303Value *createInsertVector(
304 IRBuilderBase &Builder, Value *Vec, Value *V, unsigned Index,
305 function_ref<Value *(Value *, Value *, ArrayRef<int>)> Generator = {});
306
307/// Generates subvector extract.
308Value *createExtractVector(IRBuilderBase &Builder, Value *Vec,
309 unsigned SubVecVF, unsigned Index);
310
311/// Specifies the way the mask should be analyzed for undefs/poisonous elements
312/// in the shuffle mask.
313enum class UseMask {
314 FirstArg, ///< The mask is expected to be for permutation of 1-2 vectors,
315 ///< check for the mask elements for the first argument (mask
316 ///< indices are in range [0:VF)).
317 SecondArg, ///< The mask is expected to be for permutation of 2 vectors, check
318 ///< for the mask elements for the second argument (mask indices
319 ///< are in range [VF:2*VF))
320 UndefsAsMask ///< Consider undef mask elements (-1) as placeholders for
321 ///< future shuffle elements and mark them as ones as being used
322 ///< in future. Non-undef elements are considered as unused since
323 ///< they're already marked as used in the mask.
324};
325
326/// Prepares a use bitset for the given mask either for the first argument or
327/// for the second.
328SmallBitVector buildUseMask(int VF, ArrayRef<int> Mask, UseMask MaskArg);
329
330/// Checks if the given value is actually an undefined constant vector.
331/// Also, if the \p UseMask is not empty, tries to check if the non-masked
332/// elements actually mask the insertelement buildvector, if any.
333template <bool IsPoisonOnly = false>
334SmallBitVector isUndefVector(const Value *V,
335 const SmallBitVector &UseMask = {});
336
337/// \returns True if in-tree use also needs extract. This refers to
338/// possible scalar operand in vectorized instruction.
339bool doesInTreeUserNeedToExtract(Value *Scalar, Instruction *UserInst,
340 TargetLibraryInfo *TLI,
341 const TargetTransformInfo *TTI);
342
343/// \returns the AA location that is being access by the instruction.
344MemoryLocation getLocation(Instruction *I);
345
346/// \returns True if the instruction is not a volatile or atomic load/store.
347bool isSimple(Instruction *I);
348
349/// Checks if the loads with scalar type \p ScalarTy and pointer operands
350/// \p PointerOps are each (optionally via a constant-offset GEP) a
351/// `select Cond, A, B` picking between the same two base pointers A/B on
352/// every lane - the shape a fully unrolled `x = cond ? A[i] : B[i]` takes. On
353/// success \p TrueBase / \p FalseBase are the candidate bases and
354/// \p Conditions holds each lane's `select` condition, used to build the
355/// blend mask. Lane \p Idx must be at `Base + Idx * sizeof(ScalarTy)`; only
356/// dense, natural lane order starting at the base is recognized (reordered or
357/// partial groups fall back to Gather/Scatter).
358bool isSelectedBaseLoad(Type *ScalarTy, ArrayRef<Value *> PointerOps,
359 const DataLayout &DL, Value *&TrueBase,
360 Value *&FalseBase,
361 SmallVectorImpl<Value *> &Conditions);
362
363/// Returns the alignment of the shared base pointer of a blended load for
364/// the loads \p VL.
365Align computeBlendedLoadBaseAlignment(ArrayRef<Value *> VL,
366 const DataLayout &DL);
367
368/// Returns the select instruction picking between the candidate base pointers
369/// of the blended loads \p VL.
370SelectInst *getBlendedLoadSelect(ArrayRef<Value *> VL);
371
372/// Returns the common type for the indices of the single-index GEP lanes of
373/// a GEP node with the main op \p VL0, or nullptr if no such type exists.
374/// \p IsGEPLane tells which lanes of \p VL are matching GEPs, whose index is
375/// used as is; all other lanes (copyable, poison, non-GEP pointers) are
376/// modeled as gep V, 0 and just take a zero index of the common type.
377/// The common type is the index type of \p VL0 if all matching lanes share
378/// it. Otherwise the constant indices are cast: to the pointer index type if
379/// there are no non-constant indices (or the index type of \p VL0 already is
380/// the pointer index type), or to the index type of \p VL0 if all the
381/// non-constant indices have that type and all the constants are
382/// representable in it (GEP indices are sign-extended to the pointer index
383/// width, so the value must fit as a signed number). A non-constant index of
384/// a different type cannot be cast without a new instruction, so no common
385/// type exists.
386Type *getCommonGEPIndexType(ArrayRef<Value *> VL, Instruction *VL0,
387 function_ref<bool(Value *)> IsGEPLane,
388 const DataLayout &DL);
389
390/// Checks if the pointers \p PointerOps of the gathered loads, which are not
391/// compatible in the usual sense (some of them are constant-offset pointers,
392/// some have runtime indices), still form a cheap address vector as a
393/// copyable GEP node: a splat of the common base and a vector of indices.
394/// The constant-offset lanes are the base itself or single-index GEPs of the
395/// base with a constant index (modeled as gep V, 0 or as matching lanes with
396/// constant indices), the other lanes are single-index GEPs of the base of
397/// the same shape, whose indices are affine in a single runtime value (the
398/// stride): optionally cast (all with the same cast opcode) values, each of
399/// which is the stride itself or a binary operation of the stride and a
400/// constant, like b[i * S] or b[S + i]. Duplicate lanes are not accepted:
401/// the node would be a shuffled non-full vector, gathering the loads is
402/// cheaper then.
403bool isCopyableGEPAddressVector(ArrayRef<Value *> PointerOps);
404
405/// Shuffles \p Mask in accordance with the given \p SubMask.
406/// \param ExtendingManyInputs Supports reshuffling of the mask with not only
407/// one but two input vectors.
408void addMask(SmallVectorImpl<int> &Mask, ArrayRef<int> SubMask,
409 bool ExtendingManyInputs = false);
410
411/// Order may have elements assigned special value (size) which is out of
412/// bounds. Such indices only appear on places which correspond to undef values
413/// (see canReuseExtract for details) and used in order to avoid undef values
414/// have effect on operands ordering.
415/// The first loop below simply finds all unused indices and then the next loop
416/// nest assigns these indices for undef values positions.
417/// As an example below Order has two undef positions and they have assigned
418/// values 3 and 7 respectively:
419/// before: 6 9 5 4 9 2 1 0
420/// after: 6 3 5 4 7 2 1 0
421void fixupOrderingIndices(MutableArrayRef<unsigned> Order);
422
423/// \returns a bitset for selecting opcodes. false for Opcode0 and true for
424/// Opcode1.
425SmallBitVector getAltInstrMask(ArrayRef<Value *> VL, Type *ScalarTy,
426 unsigned Opcode0, unsigned Opcode1);
427
428/// Replicates the given \p Val \p VF times.
429SmallVector<Constant *> replicateMask(ArrayRef<Constant *> Val, unsigned VF);
430
431/// \returns the masked division/remainder intrinsic corresponding to \p
432/// Opcode. Disabled lanes of these intrinsics are poison rather than UB,
433/// unlike the plain opcode.
434Intrinsic::ID getMaskedDivRemIntrinsic(unsigned Opcode);
435
436/// Returns true if \p I forms a vectorizable bundle on its own and its single
437/// user does not tear the vector apart. Loads and addresses are excluded: the
438/// tree is built without the users, so it does not pay off the extracts. A
439/// cast, feeding a multi-used cast, is excluded for the same reason, such a
440/// user stays scalar. The fp-to-int conversions move the result to the other
441/// register domain, so the extracts are paid on top of the repacking. The
442/// values, feeding the inserts, are vectorized together with them by the
443/// dedicated attempt.
444bool isOnceUsedSeed(const Instruction *I);
445
446/// If \p V is a single-use fpext of a single-use fptrunc forming a round-trip
447/// back to the type of \p V, returns the fptrunc; the round-trip source is its
448/// operand, always an instruction of the same type as \p V. If
449/// \p MustBeElidable, matches only when the intermediate rounding may be
450/// removed: both casts must allow contraction and the widening cast cannot
451/// produce nan/inf.
452Instruction *lookThroughCastRoundTrip(Value *V, bool MustBeElidable);
453
454/// Narrow reduction leaf: the value, the shift applied after widening and
455/// the mask applied in the narrow type before widening, clearing the bits
456/// the absorbed narrow shls shift out and applying the absorbed narrow
457/// and-masks. Lossless narrow shls contribute their known-zero bits to the
458/// mask so matching lanes can form a splat. All-ones mask means nothing
459/// was absorbed and no 'and' is needed.
460struct NarrowedLeafInfo {
461 NarrowedLeafInfo(Value *V, unsigned Shift, APInt Mask)
462 : V(V), Shift(Shift), Mask(std::move(Mask)) {}
463
464 Value *V = nullptr;
465 unsigned Shift = 0;
466 APInt Mask;
467 /// Set to false, if the or chain is not disjoint
468 bool Disjoint = true;
469};
470
471/// Recursively collects the narrow leaves of the widened reduction value
472/// \p V. zext is looked through directly, same-kind binops per operand,
473/// shl of a zext - only if no bits are shifted out in the current type,
474/// shls in narrower types fold into the shift and ands with a constant into
475/// the mask applied in the narrow type. Also collects the looked-through
476/// instructions into \p ChainInsts.
477void collectNarrowedLeaves(Value *V, unsigned RdxOpcode, unsigned WideBW,
478 unsigned MaxDepth,
479 SmallVectorImpl<NarrowedLeafInfo> &Leaves,
480 SmallVectorImpl<Instruction *> &ChainInsts);
481
482TargetTransformInfo::TargetCostKind getSLPCostKind(const Function *F);
483
484/// Returns a saturating unsigned upper bound of the scalar V. The numeric
485/// bound keeps precision on arithmetic carries, where bit-wise analysis
486/// loses it.
487APInt getScalarMaxValue(const Value *V, unsigned Depth = 0);
488
489/// Checks if the values in \p VL are zero-extended sub-fields of the same
490/// wider integer scalar. Returns the source scalar, the field width and the
491/// field permutation mask. The extraction dual of the lane-packing layout.
492/// The field-to-lane mapping of the bitcast to the field vector is defined
493/// for little-endian targets only.
494std::optional<std::tuple<Value *, unsigned, SmallVector<int>>>
495matchGatheredExtractedFields(ArrayRef<Value *> VL, const DataLayout &DL);
496
497/// Description of a bitfield packing of vector lanes into a scalar value:
498/// every lane contributes a disjoint contiguous byte field of the result.
499struct BitPackInfo {
500 static constexpr unsigned NoLane = std::numeric_limits<unsigned>::max();
501 unsigned FieldWidth = 0;
502 /// Lane covering each field, NoLane if the field is always zero.
503 SmallVector<unsigned, 8> LaneOfField;
504 /// Per-lane right-shift amounts bringing the field content to the low bits.
505 SmallVector<uint64_t, 8> LShrAmts;
506
507 /// True if any lane needs a right shift to align its field content.
508 bool needsShift() const {
509 return any_of(Range: LShrAmts, P: [](uint64_t A) { return A != 0; });
510 }
511};
512
513/// Computes the bitfield packing layout from the per-lane possibly set bits
514/// of the source values, the per-lane left-shift amounts and the per-lane
515/// masks (all-ones for unmasked lanes).
516std::optional<BitPackInfo> computeBitPackInfo(unsigned BitWidth,
517 ArrayRef<APInt> PossibleBits,
518 ArrayRef<uint64_t> ShlAmts,
519 ArrayRef<APInt> Masks);
520
521/// Returns the byte shuffle mask packing the per-lane fields of the shifted
522/// lanes (BytesPerLane bytes each) into the packed scalar of NumBytes bytes.
523SmallVector<int> getBitPackMask(const BitPackInfo &Info, unsigned NumBytes,
524 unsigned NumElts, unsigned BytesPerLane);
525
526/// Builds the bitfield packing of X into \p ResultTy per the layout and the
527/// shift width. \p NumInsts returns the number of emitted instructions.
528Value *buildBitPack(IRBuilderBase &Builder, Value *X, const BitPackInfo &Info,
529 Type *ResultTy, unsigned ShiftWidth, unsigned &NumInsts);
530
531/// The debug values of the erased \p From are kept on its replacement \p To.
532/// A record placed before \p To is cloned right after it, while the original
533/// one is killed together with the scalar, so the variable is undefined up to
534/// \p To. The clone is skipped if it would pass a record of the same variable,
535/// otherwise the variable would show a stale value.
536void redirectDbgValues(Instruction &From, Value &To);
537/// \returns true if \p IE1 is inserted before \p IE2 in their build-vector
538/// chain. Both must have constant insert indices and belong to one chain.
539bool isFirstInsertElement(const InsertElementInst *IE1,
540 const InsertElementInst *IE2);
541
542/// \returns the debug location of \p PN, or an unknown location if it has
543/// none.
544DebugLoc getDebugLocFromPHI(const PHINode &PN);
545
546/// \returns the number of elements of the homogeneous aggregate built by
547/// \p InsertInst (insertelement or insertvalue), or std::nullopt if it is not
548/// a homogeneous aggregate.
549std::optional<unsigned> getAggregateSize(Instruction *InsertInst);
550
551/// \returns the innermost loop starting from \p L for which at least one value
552/// in \p VL is not loop-invariant.
553const Loop *findInnermostNonInvariantLoop(const Loop *L, ArrayRef<Value *> VL);
554
555/// \returns an estimated trip count for \p L, bounded by the loop-aware budget
556/// \p LoopAwareTripCount. Returns 1 when the budget is 0.
557unsigned getLoopTripCount(const Loop *L, ScalarEvolution &SE,
558 unsigned LoopAwareTripCount);
559
560/// Check if two insertelement instructions are from the same buildvector.
561bool areTwoInsertFromSameBuildVector(
562 InsertElementInst *VU, InsertElementInst *V,
563 function_ref<Value *(InsertElementInst *)> GetBaseOperand);
564
565} // namespace llvm::slpvectorizer
566
567#endif // LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPUTILS_H
568