1//===- SLPCompatibilityAnalysis.h - SLP same-opcode 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 the same-opcode
10// compatibility primitives that decide whether a group of values can be
11// treated as sharing the same (or an interchangeable/alternate) opcode. These
12// do not depend on BoUpSLP or any other SLP-private type.
13//
14//===----------------------------------------------------------------------===//
15
16#ifndef LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPCOMPATIBILITYANALYSIS_H
17#define LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPCOMPATIBILITYANALYSIS_H
18
19#include "llvm/ADT/ArrayRef.h"
20#include "llvm/ADT/BitmaskEnum.h"
21#include "llvm/ADT/STLExtras.h"
22#include "llvm/ADT/SmallBitVector.h"
23#include "llvm/ADT/SmallVector.h"
24#include "llvm/Analysis/IVDescriptors.h"
25#include "llvm/IR/Instruction.h"
26#include "llvm/IR/Instructions.h"
27
28#include <cstdint>
29#include <utility>
30
31namespace llvm {
32class APInt;
33class Constant;
34class ConstantInt;
35class TargetLibraryInfo;
36class Value;
37} // namespace llvm
38
39namespace llvm::slpvectorizer {
40
41/// \returns true if \p Opcode is allowed as part of the main/alternate
42/// instruction for SLP vectorization.
43///
44/// Example of unsupported opcode is SDIV that can potentially cause UB if the
45/// "shuffled out" lane would result in division by zero.
46bool isValidForAlternation(unsigned Opcode);
47
48/// Helper class that determines VL can use the same opcode.
49/// Alternate instruction is supported. In addition, it supports interchangeable
50/// instruction. An interchangeable instruction is an instruction that can be
51/// converted to another instruction with same semantics. For example, x << 1 is
52/// equal to x * 2. x * 1 is equal to x | 0.
53class BinOpSameOpcodeHelper {
54 using MaskType = std::uint_fast32_t;
55 /// Sort SupportedOp because it is used by binary_search.
56 constexpr static unsigned SupportedOp[] = {
57 Instruction::Add, Instruction::FAdd, Instruction::Sub, Instruction::FSub,
58 Instruction::Mul, Instruction::Shl, Instruction::AShr, Instruction::And,
59 Instruction::Or, Instruction::Xor};
60 static_assert(llvm::is_sorted_constexpr(Range: SupportedOp) &&
61 "SupportedOp is not sorted.");
62 enum : MaskType {
63 ShlBIT = 1,
64 AShrBIT = 1 << 1,
65 MulBIT = 1 << 2,
66 AddBIT = 1 << 3,
67 SubBIT = 1 << 4,
68 AndBIT = 1 << 5,
69 OrBIT = 1 << 6,
70 XorBIT = 1 << 7,
71 FAddBIT = 1 << 8,
72 FSubBIT = 1 << 9,
73 MainOpBIT = 1 << 10,
74 LLVM_MARK_AS_BITMASK_ENUM(MainOpBIT)
75 };
76 /// Return a non-nullptr if either operand of I is a ConstantInt (for the
77 /// integer opcodes) or a ConstantFP (for FAdd/FSub).
78 /// The second return value represents the operand position. We check the
79 /// right-hand side first (1). If the right hand side is not a constant and
80 /// the instruction is neither Sub, FSub, Shl, nor AShr, we then check the
81 /// left hand side (0).
82 static std::pair<Constant *, unsigned>
83 isBinOpWithConstant(const Instruction *I);
84 struct InterchangeableInfo {
85 const Instruction *I = nullptr;
86 /// The bit it sets represents whether MainOp can be converted to.
87 MaskType Mask = MainOpBIT | XorBIT | OrBIT | AndBIT | SubBIT | AddBIT |
88 MulBIT | AShrBIT | ShlBIT | FSubBIT | FAddBIT;
89 /// We cannot create an interchangeable instruction that does not exist in
90 /// VL. For example, VL [x + 0, y * 1] can be converted to [x << 0, y << 0],
91 /// but << does not exist in VL. In the end, we convert VL to [x * 1, y *
92 /// 1]. SeenBefore is used to know what operations have been seen before.
93 MaskType SeenBefore = 0;
94 InterchangeableInfo(const Instruction *I) : I(I) {}
95 /// Return false allows BinOpSameOpcodeHelper to find an alternate
96 /// instruction. Directly setting the mask will destroy the mask state,
97 /// preventing us from determining which instruction it should convert to.
98 bool trySet(MaskType OpcodeInMaskForm, MaskType InterchangeableMask);
99 bool equal(unsigned Opcode) {
100 return Opcode == I->getOpcode() && trySet(OpcodeInMaskForm: MainOpBIT, InterchangeableMask: MainOpBIT);
101 }
102 unsigned getOpcode() const;
103 bool hasDefinedOpcode() const { return (Mask & SeenBefore) > 0; }
104 /// Return true if the instruction can be converted to \p Opcode.
105 bool hasCandidateOpcode(unsigned Opcode) const;
106 SmallVector<Value *> getOperand(const Instruction *To) const;
107 };
108 InterchangeableInfo MainOp;
109 InterchangeableInfo AltOp;
110 bool isValidForAlternation(const Instruction *I) const;
111 bool initializeAltOp(const Instruction *I);
112
113public:
114 BinOpSameOpcodeHelper(const Instruction *MainOp,
115 const Instruction *AltOp = nullptr)
116 : MainOp(MainOp), AltOp(AltOp) {}
117 bool add(const Instruction *I);
118 unsigned getMainOpcode() const { return MainOp.getOpcode(); }
119 bool hasDefinedMainOpcode() const { return MainOp.hasDefinedOpcode(); }
120 /// Checks if the list of potential opcodes includes \p Opcode.
121 bool hasCandidateOpcode(unsigned Opcode) const {
122 return MainOp.hasCandidateOpcode(Opcode);
123 }
124 bool hasAltOp() const { return AltOp.I; }
125 unsigned getAltOpcode() const {
126 return hasAltOp() ? AltOp.getOpcode() : getMainOpcode();
127 }
128 bool hasDefinedAltOpcode() const {
129 return !hasAltOp() || AltOp.hasDefinedOpcode();
130 }
131 SmallVector<Value *> getOperand(const Instruction *I) const {
132 return MainOp.getOperand(To: I);
133 }
134};
135
136/// Helper class that determines whether a list of integer comparisons can
137/// share a single predicate. InstCombine canonicalizes single-element and
138/// single-complement range comparisons to eq/ne at the type boundaries
139/// (e.g. x <u 1 becomes x == 0); such lanes are interchangeable with the
140/// rest of the list by adjusting the compared constant.
141class CmpSamePredicateHelper {
142 using MaskType = std::uint16_t;
143 /// Bit i represents predicate ICMP_EQ + i.
144 static constexpr unsigned NumPreds = CmpInst::ICMP_SLE - CmpInst::ICMP_EQ + 1;
145 static constexpr MaskType AllPreds = (1 << NumPreds) - 1;
146 /// Intersection of the per-lane convertible predicate sets.
147 MaskType Mask = AllPreds;
148 /// Predicates present in the list natively. The shared predicate must be
149 /// one of them: the main op must be an actual instruction with this
150 /// predicate.
151 MaskType SeenBefore = 0;
152
153 static constexpr MaskType getBit(CmpInst::Predicate P) {
154 return static_cast<MaskType>(1) << (P - CmpInst::ICMP_EQ);
155 }
156 /// Returns the mask of the predicates that can express the comparison
157 /// (Pred, X, C) with an adjusted constant C, including Pred itself.
158 static MaskType getFormsMask(CmpInst::Predicate Pred, const APInt &C);
159 /// Returns the constant of the (Pred, X, C') form equivalent to the
160 /// boundary family (IsComplement, K). Pred must be in the family mask.
161 static APInt getFamilyConstant(bool IsComplement, const APInt &K,
162 CmpInst::Predicate Pred);
163
164public:
165 /// Intersects the convertible predicate set of \p CI with the running
166 /// set. Returns false when the intersection becomes empty.
167 bool add(const ICmpInst *CI);
168 /// Returns the shared predicate, preferring the predicate of
169 /// \p Preferred when the whole list can use it, or BAD_ICMP_PREDICATE
170 /// when the list cannot share a natively present predicate.
171 CmpInst::Predicate getPredicate(const ICmpInst *Preferred) const;
172 /// Returns the predicate the whole list can share, or BAD_ICMP_PREDICATE
173 /// when it cannot share a natively present predicate.
174 static CmpInst::Predicate getSharedPredicate(ArrayRef<Value *> VL,
175 const ICmpInst *Preferred);
176 /// Checks if the comparison \p CI can be expressed with the predicate
177 /// \p Pred by adjusting its constant operand.
178 static bool canConvertTo(const CmpInst *CI, CmpInst::Predicate Pred);
179 /// Returns the adjusted constant operand expressing \p CI with the
180 /// predicate \p Pred, or nullptr if not convertible or if \p CI already
181 /// uses \p Pred.
182 static ConstantInt *getAdjustedConstant(const CmpInst *CI,
183 CmpInst::Predicate Pred);
184};
185
186/// Main data required for vectorization of instructions.
187class InstructionsState {
188 /// MainOp and AltOp are primarily determined by getSameOpcode. Currently,
189 /// only BinaryOperator, CastInst, and CmpInst support alternate instructions
190 /// (i.e., AltOp is not equal to MainOp; this can be checked using
191 /// isAltShuffle).
192 /// A rare exception is TrySplitNode, where the InstructionsState is derived
193 /// from getMainAltOpsNoStateVL.
194 /// For those InstructionsState that use alternate instructions, the resulting
195 /// vectorized output ultimately comes from a shufflevector. For example,
196 /// given a vector list (VL):
197 /// VL[0] = add i32 a, e
198 /// VL[1] = sub i32 b, f
199 /// VL[2] = add i32 c, g
200 /// VL[3] = sub i32 d, h
201 /// The vectorized result would be:
202 /// intermediated_0 = add <4 x i32> <a, b, c, d>, <e, f, g, h>
203 /// intermediated_1 = sub <4 x i32> <a, b, c, d>, <e, f, g, h>
204 /// result = shufflevector <4 x i32> intermediated_0,
205 /// <4 x i32> intermediated_1,
206 /// <4 x i32> <i32 0, i32 5, i32 2, i32 7>
207 /// Since shufflevector is used in the final result, when calculating the cost
208 /// (getEntryCost), we must account for the usage of shufflevector in
209 /// GetVectorCost.
210 Instruction *MainOp = nullptr;
211 Instruction *AltOp = nullptr;
212 /// Whether the instruction state represents copyable instructions.
213 bool HasCopyables = false;
214 /// Index of the operand modeling the copyable values: the addend for
215 /// fmuladd (retried with a multiplicand), the first operand otherwise.
216 unsigned CopyableOpIdx = 0;
217 /// Whether copyable single-use fmuls/fadds are modeled as
218 /// fmuladd(a, b, -0.0)/fmuladd(1.0, a, b), absorbing the binop instead of
219 /// computing and gathering its result.
220 bool AbsorbCopyableFMulOrFAdd = false;
221
222public:
223 Instruction *getMainOp() const {
224 assert(valid() && "InstructionsState is invalid.");
225 return MainOp;
226 }
227
228 Instruction *getAltOp() const {
229 assert(valid() && "InstructionsState is invalid.");
230 return AltOp;
231 }
232
233 /// The main/alternate opcodes for the list of instructions.
234 unsigned getOpcode() const { return getMainOp()->getOpcode(); }
235
236 unsigned getAltOpcode() const { return getAltOp()->getOpcode(); }
237
238 /// Some of the instructions in the list have alternate opcodes.
239 bool isAltShuffle() const { return getMainOp() != getAltOp(); }
240
241 /// Checks if \p I is the same operation as \p Op, distinguishing calls by
242 /// intrinsic ID (all calls share the Call opcode, so e.g. umax != smax).
243 static bool isSameOperation(const Instruction *I, const Instruction *Op);
244
245 /// Checks if the instruction matches either the main or alternate opcode.
246 /// \returns
247 /// - MainOp if \param I matches MainOp's opcode directly or can be converted
248 /// to it
249 /// - AltOp if \param I matches AltOp's opcode directly or can be converted to
250 /// it
251 /// - nullptr if \param I cannot be matched or converted to either opcode
252 Instruction *getMatchingMainOpOrAltOp(Instruction *I) const;
253
254 /// Checks if main/alt instructions are shift operations.
255 bool isShiftOp() const {
256 return getMainOp()->isShift() && getAltOp()->isShift();
257 }
258
259 /// Checks if main/alt instructions are bitwise logic operations.
260 bool isBitwiseLogicOp() const {
261 return getMainOp()->isBitwiseLogicOp() && getAltOp()->isBitwiseLogicOp();
262 }
263
264 /// Checks if main/alt instructions are mul/div/rem/fmul/fdiv/frem operations.
265 bool isMulDivLikeOp() const;
266
267 /// Checks if main/alt instructions are add/sub/fadd/fsub operations.
268 bool isAddSubLikeOp() const;
269
270 /// Checks if main/alt instructions are cmp operations.
271 bool isCmpOp() const {
272 return (getOpcode() == Instruction::ICmp ||
273 getOpcode() == Instruction::FCmp) &&
274 getAltOpcode() == getOpcode();
275 }
276
277 /// Checks if the current state is valid, i.e. has non-null MainOp
278 bool valid() const { return MainOp && AltOp; }
279
280 explicit operator bool() const { return valid(); }
281
282 InstructionsState() = delete;
283 InstructionsState(Instruction *MainOp, Instruction *AltOp,
284 bool HasCopyables = false)
285 : MainOp(MainOp), AltOp(AltOp), HasCopyables(HasCopyables),
286 CopyableOpIdx(MainOp && RecurrenceDescriptor::isFMulAddIntrinsic(I: MainOp)
287 ? 2
288 : 0) {}
289 static InstructionsState invalid() { return {nullptr, nullptr}; }
290
291 /// Checks if the value is a copyable element.
292 bool isCopyableElement(Value *V) const;
293
294 /// Checks if the value \p V is a transformed instruction, compatible either
295 /// with main or alternate ops.
296 bool isExpandedBinOp(Value *V) const;
297
298 /// Checks if the operand at index \p Idx of instruction \p I is an expanded
299 /// operand.
300 bool isExpandedOperand(Instruction *I, unsigned Idx) const;
301
302 /// Checks if the value is non-schedulable.
303 bool isNonSchedulable(Value *V) const;
304
305 /// Checks if the state represents copyable instructions.
306 bool areInstructionsWithCopyableElements() const {
307 assert(valid() && "InstructionsState is invalid.");
308 return HasCopyables;
309 }
310
311 /// Returns the index of the operand the copyable value is modeled in.
312 unsigned getCopyableOpIdx() const {
313 assert(valid() && "InstructionsState is invalid.");
314 return CopyableOpIdx;
315 }
316
317 /// Sets the index of the operand the copyable value is modeled in.
318 void setCopyableOpIdx(unsigned Idx) {
319 assert((Idx == 0 || Idx == 2) && "Unexpected copyable operand index.");
320 CopyableOpIdx = Idx;
321 }
322
323 /// Checks if copyable fmuls/fadds are absorbed as fmuladd(a, b, -0.0) or
324 /// fmuladd(1.0, a, b).
325 bool hasAbsorbedCopyableFMulOrFAdd() const {
326 assert(valid() && "InstructionsState is invalid.");
327 return AbsorbCopyableFMulOrFAdd;
328 }
329
330 /// Sets the absorbed-fmul/fadd modeling for copyable fmuls/fadds.
331 void setAbsorbCopyableFMulOrFAdd(bool Absorb) {
332 AbsorbCopyableFMulOrFAdd = Absorb;
333 }
334};
335
336/// Checks if \p V is a single-use fmul/fadd with operands outside \p VL.
337bool isAbsorbableFMulOrFAdd(ArrayRef<Value *> VL, Value *V);
338
339/// Checks if \p V is a copyable single-use fmul/fadd, absorbable as
340/// fmuladd(a, b, -0.0) or fmuladd(1.0, a, b).
341bool isAbsorbableCopyableFMulOrFAdd(const InstructionsState &S, Value *V);
342
343/// Checks if every copyable in \p VL is an absorbable fmul/fadd: the binops
344/// die instead of being computed and gathered. Operand order is normalized
345/// when the operands are built.
346bool hasOnlyAbsorbableCopyableFMulOrFAdds(ArrayRef<Value *> VL);
347
348/// \returns analysis of the Instructions in \p VL described in
349/// InstructionsState, the Opcode that we suppose the whole list
350/// could be vectorized even if its structure is diverse.
351InstructionsState getSameOpcode(ArrayRef<Value *> VL,
352 const TargetLibraryInfo &TLI);
353
354/// \returns the main or alternate operation from \p S matching \p I, together
355/// with the operands of \p I adjusted to the selected operation.
356std::pair<Instruction *, SmallVector<Value *>>
357convertTo(Instruction *I, const InstructionsState &S);
358
359/// Checks if the specified instruction \p I is an alternate operation for
360/// the given \p MainOp and \p AltOp instructions.
361bool isAlternateInstruction(Instruction *I, Instruction *MainOp,
362 Instruction *AltOp, const TargetLibraryInfo &TLI);
363
364/// Peel the per-lane associative chains of an alternate node into operand
365/// columns. Lanes peel in lockstep and only chain links with the lane's own
366/// opcode, so every combine level keeps the root's main/alt opcode pattern
367/// and a subtract lane never becomes an add of a negated leaf. Only the
368/// leading (running) column peels: peeling a subtracted subtract would flip
369/// signs. \p SubLanes records the subtract lanes for the realignment sign
370/// query. Returns the flattened columns, empty when no level peels.
371SmallVector<SmallVector<Value *>> scanAltAssociativeOperands(
372 const InstructionsState &S, const TargetLibraryInfo &TLI,
373 ArrayRef<Value *> VL, ArrayRef<Value *> Op0, ArrayRef<Value *> Op1,
374 SmallVectorImpl<Value *> &ReassocScalars, SmallBitVector &SubLanes);
375} // namespace llvm::slpvectorizer
376
377#endif // LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPCOMPATIBILITYANALYSIS_H
378