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/IR/Instruction.h"
25#include "llvm/IR/Instructions.h"
26
27#include <cstdint>
28#include <utility>
29
30namespace llvm {
31class APInt;
32class Constant;
33class ConstantInt;
34class TargetLibraryInfo;
35class Value;
36} // namespace llvm
37
38namespace llvm::slpvectorizer {
39
40/// \returns true if \p Opcode is allowed as part of the main/alternate
41/// instruction for SLP vectorization.
42///
43/// Example of unsupported opcode is SDIV that can potentially cause UB if the
44/// "shuffled out" lane would result in division by zero.
45bool isValidForAlternation(unsigned Opcode);
46
47/// Helper class that determines VL can use the same opcode.
48/// Alternate instruction is supported. In addition, it supports interchangeable
49/// instruction. An interchangeable instruction is an instruction that can be
50/// converted to another instruction with same semantics. For example, x << 1 is
51/// equal to x * 2. x * 1 is equal to x | 0.
52class BinOpSameOpcodeHelper {
53 using MaskType = std::uint_fast32_t;
54 /// Sort SupportedOp because it is used by binary_search.
55 constexpr static unsigned SupportedOp[] = {
56 Instruction::Add, Instruction::FAdd, Instruction::Sub, Instruction::FSub,
57 Instruction::Mul, Instruction::Shl, Instruction::AShr, Instruction::And,
58 Instruction::Or, Instruction::Xor};
59 static_assert(llvm::is_sorted_constexpr(Range: SupportedOp) &&
60 "SupportedOp is not sorted.");
61 enum : MaskType {
62 ShlBIT = 1,
63 AShrBIT = 1 << 1,
64 MulBIT = 1 << 2,
65 AddBIT = 1 << 3,
66 SubBIT = 1 << 4,
67 AndBIT = 1 << 5,
68 OrBIT = 1 << 6,
69 XorBIT = 1 << 7,
70 FAddBIT = 1 << 8,
71 FSubBIT = 1 << 9,
72 MainOpBIT = 1 << 10,
73 LLVM_MARK_AS_BITMASK_ENUM(MainOpBIT)
74 };
75 /// Return a non-nullptr if either operand of I is a ConstantInt (for the
76 /// integer opcodes) or a ConstantFP (for FAdd/FSub).
77 /// The second return value represents the operand position. We check the
78 /// right-hand side first (1). If the right hand side is not a constant and
79 /// the instruction is neither Sub, FSub, Shl, nor AShr, we then check the
80 /// left hand side (0).
81 static std::pair<Constant *, unsigned>
82 isBinOpWithConstant(const Instruction *I);
83 struct InterchangeableInfo {
84 const Instruction *I = nullptr;
85 /// The bit it sets represents whether MainOp can be converted to.
86 MaskType Mask = MainOpBIT | XorBIT | OrBIT | AndBIT | SubBIT | AddBIT |
87 MulBIT | AShrBIT | ShlBIT | FSubBIT | FAddBIT;
88 /// We cannot create an interchangeable instruction that does not exist in
89 /// VL. For example, VL [x + 0, y * 1] can be converted to [x << 0, y << 0],
90 /// but << does not exist in VL. In the end, we convert VL to [x * 1, y *
91 /// 1]. SeenBefore is used to know what operations have been seen before.
92 MaskType SeenBefore = 0;
93 InterchangeableInfo(const Instruction *I) : I(I) {}
94 /// Return false allows BinOpSameOpcodeHelper to find an alternate
95 /// instruction. Directly setting the mask will destroy the mask state,
96 /// preventing us from determining which instruction it should convert to.
97 bool trySet(MaskType OpcodeInMaskForm, MaskType InterchangeableMask);
98 bool equal(unsigned Opcode) {
99 return Opcode == I->getOpcode() && trySet(OpcodeInMaskForm: MainOpBIT, InterchangeableMask: MainOpBIT);
100 }
101 unsigned getOpcode() const;
102 bool hasDefinedOpcode() const { return (Mask & SeenBefore) > 0; }
103 /// Return true if the instruction can be converted to \p Opcode.
104 bool hasCandidateOpcode(unsigned Opcode) const;
105 SmallVector<Value *> getOperand(const Instruction *To) const;
106 };
107 InterchangeableInfo MainOp;
108 InterchangeableInfo AltOp;
109 bool isValidForAlternation(const Instruction *I) const;
110 bool initializeAltOp(const Instruction *I);
111
112public:
113 BinOpSameOpcodeHelper(const Instruction *MainOp,
114 const Instruction *AltOp = nullptr)
115 : MainOp(MainOp), AltOp(AltOp) {}
116 bool add(const Instruction *I);
117 unsigned getMainOpcode() const { return MainOp.getOpcode(); }
118 bool hasDefinedMainOpcode() const { return MainOp.hasDefinedOpcode(); }
119 /// Checks if the list of potential opcodes includes \p Opcode.
120 bool hasCandidateOpcode(unsigned Opcode) const {
121 return MainOp.hasCandidateOpcode(Opcode);
122 }
123 bool hasAltOp() const { return AltOp.I; }
124 unsigned getAltOpcode() const {
125 return hasAltOp() ? AltOp.getOpcode() : getMainOpcode();
126 }
127 bool hasDefinedAltOpcode() const {
128 return !hasAltOp() || AltOp.hasDefinedOpcode();
129 }
130 SmallVector<Value *> getOperand(const Instruction *I) const {
131 return MainOp.getOperand(To: I);
132 }
133};
134
135/// Helper class that determines whether a list of integer comparisons can
136/// share a single predicate. InstCombine canonicalizes single-element and
137/// single-complement range comparisons to eq/ne at the type boundaries
138/// (e.g. x <u 1 becomes x == 0); such lanes are interchangeable with the
139/// rest of the list by adjusting the compared constant. InstCombine also
140/// canonicalizes icmp ne (and X, 1), 0 to trunc X to i1, such lanes are
141/// treated as the original comparison or as icmp eq (and X, 1), 1. An i1
142/// constant lane is the comparison of constants with any predicate.
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 V, or 0 if \p V is not a comparison lane.
167 static MaskType getLaneMask(const Value *V);
168
169public:
170 /// Intersects the convertible predicate set of the comparison lane \p V
171 /// (an icmp, a trunc to i1 or an i1 constant) with the running set.
172 /// Returns false when the intersection becomes empty.
173 bool add(const Value *V);
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 V can be expressed with the predicate
187 /// \p Pred by adjusting its constant operand.
188 static bool canConvertTo(const Value *V, 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 /// Returns the constant operands expressing the i1 constant lane \p V as
195 /// the comparison \p Cmp.
196 static SmallVector<Value *> getConstantLaneOperands(const Value *V,
197 const ICmpInst *Cmp);
198};
199
200/// Checks if \p I is a call to llvm.fma or llvm.fmuladd.
201bool isFMAOrFMulAdd(const Instruction *I);
202
203/// How the FP identity ops of the copyable lanes produce the lane values:
204/// exactly, inexactly (a NaN may be quieted and a subnormal flushed, so the
205/// vector is valid only for FP math) or with the original values blended in.
206enum class FPCopyables { Exact, Inexact, Blended };
207
208/// Main data required for vectorization of instructions.
209class InstructionsState {
210 /// MainOp and AltOp are primarily determined by getSameOpcode. Currently,
211 /// only BinaryOperator, CastInst, and CmpInst support alternate instructions
212 /// (i.e., AltOp is not equal to MainOp; this can be checked using
213 /// isAltShuffle).
214 /// A rare exception is TrySplitNode, where the InstructionsState is derived
215 /// from getMainAltOpsNoStateVL.
216 /// For those InstructionsState that use alternate instructions, the resulting
217 /// vectorized output ultimately comes from a shufflevector. For example,
218 /// given a vector list (VL):
219 /// VL[0] = add i32 a, e
220 /// VL[1] = sub i32 b, f
221 /// VL[2] = add i32 c, g
222 /// VL[3] = sub i32 d, h
223 /// The vectorized result would be:
224 /// intermediated_0 = add <4 x i32> <a, b, c, d>, <e, f, g, h>
225 /// intermediated_1 = sub <4 x i32> <a, b, c, d>, <e, f, g, h>
226 /// result = shufflevector <4 x i32> intermediated_0,
227 /// <4 x i32> intermediated_1,
228 /// <4 x i32> <i32 0, i32 5, i32 2, i32 7>
229 /// Since shufflevector is used in the final result, when calculating the cost
230 /// (getEntryCost), we must account for the usage of shufflevector in
231 /// GetVectorCost.
232 Instruction *MainOp = nullptr;
233 Instruction *AltOp = nullptr;
234 /// Whether the instruction state represents copyable instructions.
235 bool HasCopyables = false;
236 /// Index of the operand modeling the copyable values: the addend for
237 /// fma/fmuladd (retried with a multiplicand), the first operand otherwise.
238 unsigned CopyableOpIdx = 0;
239 /// Whether copyable single-use fmuls/fadds are modeled as
240 /// fmuladd(a, b, -0.0)/fmuladd(1.0, a, b), absorbing the binop instead of
241 /// computing and gathering its result.
242 bool AbsorbCopyableFMulOrFAdd = false;
243 /// How the FP identity ops produce the values of the copyable lanes.
244 FPCopyables FPCopyablesKind = FPCopyables::Exact;
245
246public:
247 Instruction *getMainOp() const {
248 assert(valid() && "InstructionsState is invalid.");
249 return MainOp;
250 }
251
252 Instruction *getAltOp() const {
253 assert(valid() && "InstructionsState is invalid.");
254 return AltOp;
255 }
256
257 /// The main/alternate opcodes for the list of instructions.
258 unsigned getOpcode() const { return getMainOp()->getOpcode(); }
259
260 unsigned getAltOpcode() const { return getAltOp()->getOpcode(); }
261
262 /// Some of the instructions in the list have alternate opcodes.
263 bool isAltShuffle() const { return getMainOp() != getAltOp(); }
264
265 /// Checks if \p I is the same operation as \p Op, distinguishing calls by
266 /// intrinsic ID (all calls share the Call opcode, so e.g. umax != smax).
267 static bool isSameOperation(const Instruction *I, const Instruction *Op);
268
269 /// Checks if the instruction matches either the main or alternate opcode.
270 /// \returns
271 /// - MainOp if \param I matches MainOp's opcode directly or can be converted
272 /// to it
273 /// - AltOp if \param I matches AltOp's opcode directly or can be converted to
274 /// it
275 /// - nullptr if \param I cannot be matched or converted to either opcode
276 Instruction *getMatchingMainOpOrAltOp(Instruction *I) const;
277
278 /// Checks if main/alt instructions are shift operations.
279 bool isShiftOp() const {
280 return getMainOp()->isShift() && getAltOp()->isShift();
281 }
282
283 /// Checks if main/alt instructions are bitwise logic operations.
284 bool isBitwiseLogicOp() const {
285 return getMainOp()->isBitwiseLogicOp() && getAltOp()->isBitwiseLogicOp();
286 }
287
288 /// Checks if main/alt instructions are mul/div/rem/fmul/fdiv/frem operations.
289 bool isMulDivLikeOp() const;
290
291 /// Checks if main/alt instructions are add/sub/fadd/fsub operations.
292 bool isAddSubLikeOp() const;
293
294 /// Checks for an add/sub-like operation or an fneg, which models a
295 /// flattened fadd reduction chain link: the link is dropped and its
296 /// operand joins a sign-flipped combine, which may form an fma as well.
297 bool isAddSubOrFNegLikeOp() const;
298
299 /// Checks if main/alt instructions are cmp operations.
300 bool isCmpOp() const {
301 return (getOpcode() == Instruction::ICmp ||
302 getOpcode() == Instruction::FCmp) &&
303 getAltOpcode() == getOpcode();
304 }
305
306 /// Checks if the current state is valid, i.e. has non-null MainOp
307 bool valid() const { return MainOp && AltOp; }
308
309 explicit operator bool() const { return valid(); }
310
311 InstructionsState() = delete;
312 InstructionsState(Instruction *MainOp, Instruction *AltOp,
313 bool HasCopyables = false)
314 : MainOp(MainOp), AltOp(AltOp), HasCopyables(HasCopyables),
315 CopyableOpIdx(MainOp && isFMAOrFMulAdd(I: MainOp) ? 2 : 0) {}
316 static InstructionsState invalid() { return {nullptr, nullptr}; }
317
318 /// Checks if the value is a copyable element.
319 bool isCopyableElement(Value *V) const;
320
321 /// Checks if the value \p V is a transformed instruction, compatible either
322 /// with main or alternate ops.
323 bool isExpandedBinOp(Value *V) const;
324
325 /// Checks if the operand at index \p Idx of instruction \p I is an expanded
326 /// operand.
327 bool isExpandedOperand(Instruction *I, unsigned Idx) const;
328
329 /// Checks if the value is non-schedulable.
330 bool isNonSchedulable(Value *V) const;
331
332 /// Checks if the state represents copyable instructions.
333 bool areInstructionsWithCopyableElements() const {
334 assert(valid() && "InstructionsState is invalid.");
335 return HasCopyables;
336 }
337
338 /// Returns the index of the operand the copyable value is modeled in.
339 unsigned getCopyableOpIdx() const {
340 assert(valid() && "InstructionsState is invalid.");
341 return CopyableOpIdx;
342 }
343
344 /// Sets the index of the operand the copyable value is modeled in.
345 void setCopyableOpIdx(unsigned Idx) {
346 assert((Idx == 0 || Idx == 2) && "Unexpected copyable operand index.");
347 CopyableOpIdx = Idx;
348 }
349
350 /// Checks if copyable fmuls/fadds are absorbed as fmuladd(a, b, -0.0) or
351 /// fmuladd(1.0, a, b).
352 bool hasAbsorbedCopyableFMulOrFAdd() const {
353 assert(valid() && "InstructionsState is invalid.");
354 return AbsorbCopyableFMulOrFAdd;
355 }
356
357 /// Sets the absorbed-fmul/fadd modeling for copyable fmuls/fadds.
358 void setAbsorbCopyableFMulOrFAdd(bool Absorb) {
359 AbsorbCopyableFMulOrFAdd = Absorb;
360 }
361
362 /// Returns how the FP identity ops produce the values of the copyable lanes.
363 FPCopyables getFPCopyables() const {
364 assert(valid() && "InstructionsState is invalid.");
365 return FPCopyablesKind;
366 }
367
368 /// Sets how the FP identity ops produce the values of the copyable lanes.
369 void setFPCopyables(FPCopyables Kind) { FPCopyablesKind = Kind; }
370};
371
372/// Checks if \p V is a single-use fmul/fadd with operands outside \p VL.
373bool isAbsorbableFMulOrFAdd(ArrayRef<Value *> VL, Value *V);
374
375/// Checks if \p V is a copyable single-use fmul/fadd, absorbable as
376/// fmuladd(a, b, -0.0) or fmuladd(1.0, a, b).
377bool isAbsorbableCopyableFMulOrFAdd(const InstructionsState &S, Value *V);
378
379/// Checks if every copyable in \p VL is an absorbable fmul/fadd: the binops
380/// die instead of being computed and gathered. Operand order is normalized
381/// when the operands are built.
382bool hasOnlyAbsorbableCopyableFMulOrFAdds(ArrayRef<Value *> VL);
383
384/// \returns analysis of the Instructions in \p VL described in
385/// InstructionsState, the Opcode that we suppose the whole list
386/// could be vectorized even if its structure is diverse.
387InstructionsState getSameOpcode(ArrayRef<Value *> VL,
388 const TargetLibraryInfo &TLI);
389
390/// \returns the main or alternate operation from \p S matching \p I, together
391/// with the operands of \p I adjusted to the selected operation.
392std::pair<Instruction *, SmallVector<Value *>>
393convertTo(Instruction *I, const InstructionsState &S);
394
395/// Checks if the specified instruction \p I is an alternate operation for
396/// the given \p MainOp and \p AltOp instructions.
397bool isAlternateInstruction(Instruction *I, Instruction *MainOp,
398 Instruction *AltOp, const TargetLibraryInfo &TLI);
399
400/// Peel the per-lane associative chains of an alternate node into operand
401/// columns. Lanes peel in lockstep and only chain links with the lane's own
402/// opcode, so every combine level keeps the root's main/alt opcode pattern
403/// and a subtract lane never becomes an add of a negated leaf. Only the
404/// leading (running) column peels: peeling a subtracted subtract would flip
405/// signs. \p SubLanes records the subtract lanes for the realignment sign
406/// query. Returns the flattened columns, empty when no level peels.
407SmallVector<SmallVector<Value *>> scanAltAssociativeOperands(
408 const InstructionsState &S, const TargetLibraryInfo &TLI,
409 ArrayRef<Value *> VL, ArrayRef<Value *> Op0, ArrayRef<Value *> Op1,
410 SmallVectorImpl<Value *> &ReassocScalars, SmallBitVector &SubLanes);
411
412/// Returns main/alternate instructions for the given \p VL. Unlike
413/// getSameOpcode supports non-compatible instructions for better SplitVectorize
414/// node support.
415/// \returns first main/alt instructions, if only poisons and instruction with
416/// only 2 opcodes exists. Returns pair of nullptr otherwise.
417std::pair<Instruction *, Instruction *>
418getMainAltOpsNoStateVL(ArrayRef<Value *> VL);
419
420/// Detects an extractvalue bundle that can be widened by vectorizing the
421/// underlying struct-returning calls.
422///
423/// \p VL is a bundle whose state \p S is Instruction::ExtractValue. The
424/// bundle is acceptable for widening into one struct-of-vectors call only
425/// when:
426/// - every element of \p VL is an ExtractValueInst,
427/// - every ExtractValueInst extracts the same struct field (its
428/// getIndices() matches the main op's indices),
429/// - the aggregate operands form a uniform set of CallInsts (per
430/// getSameOpcode) that is not an alt-shuffle and whose return type is
431/// a literal struct, and
432/// - every user of every such call is itself an ExtractValueInst, so the
433/// external-use extraction code can rebuild scalars via extractvalue +
434/// extractelement without needing an insertvalue chain.
435///
436/// On success returns true and fills \p Indices with the common field
437/// index path and \p Calls with the per-lane aggregate calls (in VL order),
438/// for the caller to feed as the operand of the new tree entry. Otherwise
439/// returns false and leaves the output parameters untouched.
440bool checkEVsForVecCalls(ArrayRef<Value *> VL, const InstructionsState &S,
441 const TargetLibraryInfo &TLI,
442 SmallVectorImpl<unsigned> &Indices,
443 SmallVectorImpl<Value *> &Calls);
444} // namespace llvm::slpvectorizer
445
446#endif // LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPCOMPATIBILITYANALYSIS_H
447