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