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