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. InstCombine also
141/// canonicalizes icmp ne (and X, 1), 0 to trunc X to i1, such lanes are
142/// treated as the original comparison or as icmp eq (and X, 1), 1.
143class CmpSamePredicateHelper {
144 using MaskType = std::uint16_t;
145 /// Bit i represents predicate ICMP_EQ + i.
146 static constexpr unsigned NumPreds = CmpInst::ICMP_SLE - CmpInst::ICMP_EQ + 1;
147 static constexpr MaskType AllPreds = (1 << NumPreds) - 1;
148 /// Intersection of the per-lane convertible predicate sets.
149 MaskType Mask = AllPreds;
150 /// Predicates present in the list natively. The shared predicate must be
151 /// one of them: the main op must be an actual instruction with this
152 /// predicate.
153 MaskType SeenBefore = 0;
154
155 static constexpr MaskType getBit(CmpInst::Predicate P) {
156 return static_cast<MaskType>(1) << (P - CmpInst::ICMP_EQ);
157 }
158 /// Returns the mask of the predicates that can express the comparison
159 /// (Pred, X, C) with an adjusted constant C, including Pred itself.
160 static MaskType getFormsMask(CmpInst::Predicate Pred, const APInt &C);
161 /// Returns the constant of the (Pred, X, C') form equivalent to the
162 /// boundary family (IsComplement, K). Pred must be in the family mask.
163 static APInt getFamilyConstant(bool IsComplement, const APInt &K,
164 CmpInst::Predicate Pred);
165 /// Returns the mask of the predicates that can express the comparison
166 /// lane \p I, or 0 if \p I is not a comparison lane.
167 static MaskType getLaneMask(const Instruction *I);
168
169public:
170 /// Intersects the convertible predicate set of the comparison lane \p I
171 /// (an icmp or a trunc to i1) with the running set. Returns false when the
172 /// intersection becomes empty.
173 bool add(const Instruction *I);
174 /// Returns the shared predicate, preferring the predicate of
175 /// \p Preferred when the whole list can use it, or BAD_ICMP_PREDICATE
176 /// when the list cannot share a natively present predicate.
177 CmpInst::Predicate getPredicate(const ICmpInst *Preferred) const;
178 /// Returns the predicate the whole list can share, or BAD_ICMP_PREDICATE
179 /// when it cannot share a natively present predicate.
180 static CmpInst::Predicate getSharedPredicate(ArrayRef<Value *> VL,
181 const ICmpInst *Preferred);
182 /// Checks if the comparison lane \p I is the bit test of the single use
183 /// and A, B != 0 or and A, B == 0, or trunc X to i1, which is
184 /// and X, 1 != 0.
185 static bool isBitTest(const Instruction *I);
186 /// Checks if the comparison lane \p I can be expressed with the predicate
187 /// \p Pred by adjusting its constant operand.
188 static bool canConvertTo(const Instruction *I, CmpInst::Predicate Pred);
189 /// Returns the adjusted constant operand expressing the comparison lane
190 /// \p I with the predicate \p Pred, or nullptr if not convertible or if
191 /// \p I is a compare already using \p Pred.
192 static Constant *getAdjustedConstant(const Instruction *I,
193 CmpInst::Predicate Pred);
194};
195
196/// Main data required for vectorization of instructions.
197class InstructionsState {
198 /// MainOp and AltOp are primarily determined by getSameOpcode. Currently,
199 /// only BinaryOperator, CastInst, and CmpInst support alternate instructions
200 /// (i.e., AltOp is not equal to MainOp; this can be checked using
201 /// isAltShuffle).
202 /// A rare exception is TrySplitNode, where the InstructionsState is derived
203 /// from getMainAltOpsNoStateVL.
204 /// For those InstructionsState that use alternate instructions, the resulting
205 /// vectorized output ultimately comes from a shufflevector. For example,
206 /// given a vector list (VL):
207 /// VL[0] = add i32 a, e
208 /// VL[1] = sub i32 b, f
209 /// VL[2] = add i32 c, g
210 /// VL[3] = sub i32 d, h
211 /// The vectorized result would be:
212 /// intermediated_0 = add <4 x i32> <a, b, c, d>, <e, f, g, h>
213 /// intermediated_1 = sub <4 x i32> <a, b, c, d>, <e, f, g, h>
214 /// result = shufflevector <4 x i32> intermediated_0,
215 /// <4 x i32> intermediated_1,
216 /// <4 x i32> <i32 0, i32 5, i32 2, i32 7>
217 /// Since shufflevector is used in the final result, when calculating the cost
218 /// (getEntryCost), we must account for the usage of shufflevector in
219 /// GetVectorCost.
220 Instruction *MainOp = nullptr;
221 Instruction *AltOp = nullptr;
222 /// Whether the instruction state represents copyable instructions.
223 bool HasCopyables = false;
224 /// Index of the operand modeling the copyable values: the addend for
225 /// fmuladd (retried with a multiplicand), the first operand otherwise.
226 unsigned CopyableOpIdx = 0;
227 /// Whether copyable single-use fmuls/fadds are modeled as
228 /// fmuladd(a, b, -0.0)/fmuladd(1.0, a, b), absorbing the binop instead of
229 /// computing and gathering its result.
230 bool AbsorbCopyableFMulOrFAdd = false;
231
232public:
233 Instruction *getMainOp() const {
234 assert(valid() && "InstructionsState is invalid.");
235 return MainOp;
236 }
237
238 Instruction *getAltOp() const {
239 assert(valid() && "InstructionsState is invalid.");
240 return AltOp;
241 }
242
243 /// The main/alternate opcodes for the list of instructions.
244 unsigned getOpcode() const { return getMainOp()->getOpcode(); }
245
246 unsigned getAltOpcode() const { return getAltOp()->getOpcode(); }
247
248 /// Some of the instructions in the list have alternate opcodes.
249 bool isAltShuffle() const { return getMainOp() != getAltOp(); }
250
251 /// Checks if \p I is the same operation as \p Op, distinguishing calls by
252 /// intrinsic ID (all calls share the Call opcode, so e.g. umax != smax).
253 static bool isSameOperation(const Instruction *I, const Instruction *Op);
254
255 /// Checks if the instruction matches either the main or alternate opcode.
256 /// \returns
257 /// - MainOp if \param I matches MainOp's opcode directly or can be converted
258 /// to it
259 /// - AltOp if \param I matches AltOp's opcode directly or can be converted to
260 /// it
261 /// - nullptr if \param I cannot be matched or converted to either opcode
262 Instruction *getMatchingMainOpOrAltOp(Instruction *I) const;
263
264 /// Checks if main/alt instructions are shift operations.
265 bool isShiftOp() const {
266 return getMainOp()->isShift() && getAltOp()->isShift();
267 }
268
269 /// Checks if main/alt instructions are bitwise logic operations.
270 bool isBitwiseLogicOp() const {
271 return getMainOp()->isBitwiseLogicOp() && getAltOp()->isBitwiseLogicOp();
272 }
273
274 /// Checks if main/alt instructions are mul/div/rem/fmul/fdiv/frem operations.
275 bool isMulDivLikeOp() const;
276
277 /// Checks if main/alt instructions are add/sub/fadd/fsub operations.
278 bool isAddSubLikeOp() const;
279
280 /// Checks for an add/sub-like operation or an fneg, which models a
281 /// flattened fadd reduction chain link: the link is dropped and its
282 /// operand joins a sign-flipped combine, which may form an fma as well.
283 bool isAddSubOrFNegLikeOp() const;
284
285 /// Checks if main/alt instructions are cmp operations.
286 bool isCmpOp() const {
287 return (getOpcode() == Instruction::ICmp ||
288 getOpcode() == Instruction::FCmp) &&
289 getAltOpcode() == getOpcode();
290 }
291
292 /// Checks if the current state is valid, i.e. has non-null MainOp
293 bool valid() const { return MainOp && AltOp; }
294
295 explicit operator bool() const { return valid(); }
296
297 InstructionsState() = delete;
298 InstructionsState(Instruction *MainOp, Instruction *AltOp,
299 bool HasCopyables = false)
300 : MainOp(MainOp), AltOp(AltOp), HasCopyables(HasCopyables),
301 CopyableOpIdx(MainOp && RecurrenceDescriptor::isFMulAddIntrinsic(I: MainOp)
302 ? 2
303 : 0) {}
304 static InstructionsState invalid() { return {nullptr, nullptr}; }
305
306 /// Checks if the value is a copyable element.
307 bool isCopyableElement(Value *V) const;
308
309 /// Checks if the value \p V is a transformed instruction, compatible either
310 /// with main or alternate ops.
311 bool isExpandedBinOp(Value *V) const;
312
313 /// Checks if the operand at index \p Idx of instruction \p I is an expanded
314 /// operand.
315 bool isExpandedOperand(Instruction *I, unsigned Idx) const;
316
317 /// Checks if the value is non-schedulable.
318 bool isNonSchedulable(Value *V) const;
319
320 /// Checks if the state represents copyable instructions.
321 bool areInstructionsWithCopyableElements() const {
322 assert(valid() && "InstructionsState is invalid.");
323 return HasCopyables;
324 }
325
326 /// Returns the index of the operand the copyable value is modeled in.
327 unsigned getCopyableOpIdx() const {
328 assert(valid() && "InstructionsState is invalid.");
329 return CopyableOpIdx;
330 }
331
332 /// Sets the index of the operand the copyable value is modeled in.
333 void setCopyableOpIdx(unsigned Idx) {
334 assert((Idx == 0 || Idx == 2) && "Unexpected copyable operand index.");
335 CopyableOpIdx = Idx;
336 }
337
338 /// Checks if copyable fmuls/fadds are absorbed as fmuladd(a, b, -0.0) or
339 /// fmuladd(1.0, a, b).
340 bool hasAbsorbedCopyableFMulOrFAdd() const {
341 assert(valid() && "InstructionsState is invalid.");
342 return AbsorbCopyableFMulOrFAdd;
343 }
344
345 /// Sets the absorbed-fmul/fadd modeling for copyable fmuls/fadds.
346 void setAbsorbCopyableFMulOrFAdd(bool Absorb) {
347 AbsorbCopyableFMulOrFAdd = Absorb;
348 }
349};
350
351/// Checks if \p V is a single-use fmul/fadd with operands outside \p VL.
352bool isAbsorbableFMulOrFAdd(ArrayRef<Value *> VL, Value *V);
353
354/// Checks if \p V is a copyable single-use fmul/fadd, absorbable as
355/// fmuladd(a, b, -0.0) or fmuladd(1.0, a, b).
356bool isAbsorbableCopyableFMulOrFAdd(const InstructionsState &S, Value *V);
357
358/// Checks if every copyable in \p VL is an absorbable fmul/fadd: the binops
359/// die instead of being computed and gathered. Operand order is normalized
360/// when the operands are built.
361bool hasOnlyAbsorbableCopyableFMulOrFAdds(ArrayRef<Value *> VL);
362
363/// \returns analysis of the Instructions in \p VL described in
364/// InstructionsState, the Opcode that we suppose the whole list
365/// could be vectorized even if its structure is diverse.
366InstructionsState getSameOpcode(ArrayRef<Value *> VL,
367 const TargetLibraryInfo &TLI);
368
369/// \returns the main or alternate operation from \p S matching \p I, together
370/// with the operands of \p I adjusted to the selected operation.
371std::pair<Instruction *, SmallVector<Value *>>
372convertTo(Instruction *I, const InstructionsState &S);
373
374/// Checks if the specified instruction \p I is an alternate operation for
375/// the given \p MainOp and \p AltOp instructions.
376bool isAlternateInstruction(Instruction *I, Instruction *MainOp,
377 Instruction *AltOp, const TargetLibraryInfo &TLI);
378
379/// Peel the per-lane associative chains of an alternate node into operand
380/// columns. Lanes peel in lockstep and only chain links with the lane's own
381/// opcode, so every combine level keeps the root's main/alt opcode pattern
382/// and a subtract lane never becomes an add of a negated leaf. Only the
383/// leading (running) column peels: peeling a subtracted subtract would flip
384/// signs. \p SubLanes records the subtract lanes for the realignment sign
385/// query. Returns the flattened columns, empty when no level peels.
386SmallVector<SmallVector<Value *>> scanAltAssociativeOperands(
387 const InstructionsState &S, const TargetLibraryInfo &TLI,
388 ArrayRef<Value *> VL, ArrayRef<Value *> Op0, ArrayRef<Value *> Op1,
389 SmallVectorImpl<Value *> &ReassocScalars, SmallBitVector &SubLanes);
390} // namespace llvm::slpvectorizer
391
392#endif // LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPCOMPATIBILITYANALYSIS_H
393