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/ArrayRef.h"
20#include "llvm/ADT/SmallBitVector.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/Analysis/MemoryLocation.h"
23
24#include <optional>
25#include <string>
26
27namespace llvm {
28class Constant;
29class Instruction;
30class TargetLibraryInfo;
31class TargetTransformInfo;
32class Type;
33class Value;
34} // namespace llvm
35
36namespace llvm::slpvectorizer {
37
38/// Limit of the number of uses for potentially transformed instructions/values,
39/// used in checks to avoid compile-time explode.
40inline constexpr int UsesLimit = 64;
41
42/// \returns True if the value is a constant (but not globals/constant
43/// expressions).
44bool isConstant(Value *V);
45
46/// Checks if \p V is one of vector-like instructions, i.e. undef,
47/// insertelement/extractelement with constant indices for fixed vector type
48/// or extractvalue instruction.
49bool isVectorLikeInstWithConstOps(Value *V);
50
51/// \returns the number of elements for Ty.
52unsigned getNumElements(Type *Ty);
53
54/// Returns power-of-2 number of elements in a single register (part), given
55/// the total number of elements \p Size and number of registers (parts) \p
56/// NumParts.
57unsigned getPartNumElems(unsigned Size, unsigned NumParts);
58
59/// Returns correct remaining number of elements, considering total amount
60/// \p Size, (power-of-2 number) of elements in a single register
61/// \p PartNumElems and current register (part) \p Part.
62unsigned getNumElems(unsigned Size, unsigned PartNumElems, unsigned Part);
63
64#if !defined(NDEBUG)
65/// Print a short descriptor of the instruction bundle suitable for debug
66/// output.
67std::string shortBundleName(ArrayRef<Value *> VL, int Idx = -1);
68#endif
69
70/// \returns True if all of the instructions in \p VL are in the same block.
71bool allSameBlock(ArrayRef<Value *> VL);
72
73/// \returns True if all of the values in \p VL are constants (but not
74/// globals/constant expressions).
75bool allConstant(ArrayRef<Value *> VL);
76
77/// \returns True if all of the values in \p VL are identical or some of them
78/// are UndefValue.
79bool isSplat(ArrayRef<Value *> VL);
80
81/// \returns True if \p I is commutative, handles CmpInst and BinaryOperator.
82/// For BinaryOperator, it also checks if \p ValWithUses is used in specific
83/// patterns that make it effectively commutative (like equality comparisons
84/// with zero).
85/// In most cases, users should not call this function directly (since \p I and
86/// \p ValWithUses are the same). However, when analyzing interchangeable
87/// instructions, we need to use the converted opcode along with the original
88/// uses.
89/// \param I The instruction to check for commutativity
90/// \param ValWithUses The value whose uses are analyzed for special
91/// patterns
92bool isCommutative(const Instruction *I, const Value *ValWithUses,
93 bool IsCopyable = false);
94
95/// This is a helper function to check whether \p I is commutative.
96/// This is a convenience wrapper that calls the two-parameter version of
97/// isCommutative with the same instruction for both parameters. This is
98/// the common case where the instruction being checked for commutativity
99/// is the same as the instruction whose uses are analyzed for special
100/// patterns (see the two-parameter version above for details).
101/// \param I The instruction to check for commutativity
102/// \returns true if the instruction is commutative, false otherwise
103bool isCommutative(const Instruction *I);
104
105/// Checks if the operand is commutative. In commutative operations, not all
106/// operands might commutable, e.g. for fmuladd only 2 first operands are
107/// commutable.
108bool isCommutableOperand(const Instruction *I, Value *ValWithUses, unsigned Op,
109 bool IsCopyable = false);
110
111/// \returns number of operands of \p I, considering commutativity. Returns 2
112/// for commutative intrinsics.
113/// \param I The instruction to check for commutativity
114unsigned getNumberOfPotentiallyCommutativeOps(Instruction *I);
115
116/// \returns inserting or extracting index of InsertElement, ExtractElement
117/// or InsertValue instruction, using \p Offset as base offset for index.
118/// \returns std::nullopt if the index is not an immediate.
119std::optional<unsigned> getElementIndex(const Value *Inst, unsigned Offset = 0);
120
121/// \returns True if all of the values in \p VL use the same opcode.
122/// For comparison instructions, also checks if predicates match.
123/// PoisonValues are considered matching. Interchangeable instructions are
124/// not considered.
125bool allSameOpcode(ArrayRef<Value *> VL);
126
127/// \returns Optional element Idx for Extract{Value,Element} instructions.
128std::optional<unsigned> getExtractIndex(const Instruction *E);
129
130/// Compute the inverse permutation \p Mask of \p Indices.
131void inversePermutation(ArrayRef<unsigned> Indices, SmallVectorImpl<int> &Mask);
132
133/// Reorders the list of scalars in accordance with the given \p Mask.
134void reorderScalars(SmallVectorImpl<Value *> &Scalars, ArrayRef<int> Mask);
135
136/// \returns True iff every value in \p VL has the same Type as the first.
137bool allSameType(ArrayRef<Value *> VL);
138
139/// Checks if the provided value does not require scheduling. It does not
140/// require scheduling if this is not an instruction or it is an instruction
141/// that does not read/write memory and all operands are either not
142/// instructions or phi nodes or instructions from different blocks.
143bool areAllOperandsNonInsts(Value *V);
144
145/// Checks if the provided value does not require scheduling. It does not
146/// require scheduling if this is not an instruction or it is an instruction
147/// that does not read/write memory and all users are phi nodes or
148/// instructions from different blocks.
149bool isUsedOutsideBlock(Value *V);
150
151/// Checks if the specified value does not require scheduling. It does not
152/// require scheduling if all operands and all users do not need to be
153/// scheduled in the current basic block.
154bool doesNotNeedToBeScheduled(Value *V);
155
156/// Checks if the specified array of instructions does not require scheduling.
157/// It is so if all either instructions have operands that do not require
158/// scheduling or their users do not require scheduling since they are phis or
159/// in other basic blocks.
160bool doesNotNeedToSchedule(ArrayRef<Value *> VL);
161
162/// \returns inserting or extracting index of InsertElement / ExtractElement
163/// instruction, using \p Offset as base offset for index. Only instantiated
164/// for InsertElementInst and ExtractElementInst (see SLPUtils.cpp).
165template <typename T>
166std::optional<unsigned> getInsertExtractIndex(const Value *Inst,
167 unsigned Offset);
168
169void transformScalarShuffleIndiciesToVector(unsigned VecTyNumElements,
170 SmallVectorImpl<int> &Mask);
171
172/// \returns the number of groups of shufflevector
173/// A group has the following features
174/// 1. All of value in a group are shufflevector.
175/// 2. The mask of all shufflevector is isExtractSubvectorMask.
176/// 3. The mask of all shufflevector uses all of the elements of the source.
177/// e.g., it is 1 group (%0)
178/// %1 = shufflevector <16 x i8> %0, <16 x i8> poison,
179/// <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
180/// %2 = shufflevector <16 x i8> %0, <16 x i8> poison,
181/// <8 x i32> <i32 8, i32 9, i32 10, i32 11, i32 12, i32 13, i32 14, i32 15>
182/// it is 2 groups (%3 and %4)
183/// %5 = shufflevector <8 x i16> %3, <8 x i16> poison,
184/// <4 x i32> <i32 0, i32 1, i32 2, i32 3>
185/// %6 = shufflevector <8 x i16> %3, <8 x i16> poison,
186/// <4 x i32> <i32 4, i32 5, i32 6, i32 7>
187/// %7 = shufflevector <8 x i16> %4, <8 x i16> poison,
188/// <4 x i32> <i32 0, i32 1, i32 2, i32 3>
189/// %8 = shufflevector <8 x i16> %4, <8 x i16> poison,
190/// <4 x i32> <i32 4, i32 5, i32 6, i32 7>
191/// it is 0 group
192/// %12 = shufflevector <8 x i16> %10, <8 x i16> poison,
193/// <4 x i32> <i32 0, i32 1, i32 2, i32 3>
194/// %13 = shufflevector <8 x i16> %11, <8 x i16> poison,
195/// <4 x i32> <i32 0, i32 1, i32 2, i32 3>
196unsigned getShufflevectorNumGroups(ArrayRef<Value *> VL);
197
198/// \returns a shufflevector mask which is used to vectorize shufflevectors
199/// e.g.,
200/// %5 = shufflevector <8 x i16> %3, <8 x i16> poison,
201/// <4 x i32> <i32 0, i32 1, i32 2, i32 3>
202/// %6 = shufflevector <8 x i16> %3, <8 x i16> poison,
203/// <4 x i32> <i32 4, i32 5, i32 6, i32 7>
204/// %7 = shufflevector <8 x i16> %4, <8 x i16> poison,
205/// <4 x i32> <i32 0, i32 1, i32 2, i32 3>
206/// %8 = shufflevector <8 x i16> %4, <8 x i16> poison,
207/// <4 x i32> <i32 4, i32 5, i32 6, i32 7>
208/// the result is
209/// <0, 1, 2, 3, 12, 13, 14, 15, 16, 17, 18, 19, 28, 29, 30, 31>
210SmallVector<int> calculateShufflevectorMask(ArrayRef<Value *> VL);
211
212/// Specifies the way the mask should be analyzed for undefs/poisonous elements
213/// in the shuffle mask.
214enum class UseMask {
215 FirstArg, ///< The mask is expected to be for permutation of 1-2 vectors,
216 ///< check for the mask elements for the first argument (mask
217 ///< indices are in range [0:VF)).
218 SecondArg, ///< The mask is expected to be for permutation of 2 vectors, check
219 ///< for the mask elements for the second argument (mask indices
220 ///< are in range [VF:2*VF))
221 UndefsAsMask ///< Consider undef mask elements (-1) as placeholders for
222 ///< future shuffle elements and mark them as ones as being used
223 ///< in future. Non-undef elements are considered as unused since
224 ///< they're already marked as used in the mask.
225};
226
227/// Prepares a use bitset for the given mask either for the first argument or
228/// for the second.
229SmallBitVector buildUseMask(int VF, ArrayRef<int> Mask, UseMask MaskArg);
230
231/// Checks if the given value is actually an undefined constant vector.
232/// Also, if the \p UseMask is not empty, tries to check if the non-masked
233/// elements actually mask the insertelement buildvector, if any.
234template <bool IsPoisonOnly = false>
235SmallBitVector isUndefVector(const Value *V,
236 const SmallBitVector &UseMask = {});
237
238/// \returns True if in-tree use also needs extract. This refers to
239/// possible scalar operand in vectorized instruction.
240bool doesInTreeUserNeedToExtract(Value *Scalar, Instruction *UserInst,
241 TargetLibraryInfo *TLI,
242 const TargetTransformInfo *TTI);
243
244/// \returns the AA location that is being access by the instruction.
245MemoryLocation getLocation(Instruction *I);
246
247/// \returns True if the instruction is not a volatile or atomic load/store.
248bool isSimple(Instruction *I);
249
250/// Shuffles \p Mask in accordance with the given \p SubMask.
251/// \param ExtendingManyInputs Supports reshuffling of the mask with not only
252/// one but two input vectors.
253void addMask(SmallVectorImpl<int> &Mask, ArrayRef<int> SubMask,
254 bool ExtendingManyInputs = false);
255
256/// Order may have elements assigned special value (size) which is out of
257/// bounds. Such indices only appear on places which correspond to undef values
258/// (see canReuseExtract for details) and used in order to avoid undef values
259/// have effect on operands ordering.
260/// The first loop below simply finds all unused indices and then the next loop
261/// nest assigns these indices for undef values positions.
262/// As an example below Order has two undef positions and they have assigned
263/// values 3 and 7 respectively:
264/// before: 6 9 5 4 9 2 1 0
265/// after: 6 3 5 4 7 2 1 0
266void fixupOrderingIndices(MutableArrayRef<unsigned> Order);
267
268/// \returns a bitset for selecting opcodes. false for Opcode0 and true for
269/// Opcode1.
270SmallBitVector getAltInstrMask(ArrayRef<Value *> VL, Type *ScalarTy,
271 unsigned Opcode0, unsigned Opcode1);
272
273/// Replicates the given \p Val \p VF times.
274SmallVector<Constant *> replicateMask(ArrayRef<Constant *> Val, unsigned VF);
275
276} // namespace llvm::slpvectorizer
277
278#endif // LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPUTILS_H
279