1 //===- llvm/CodeGen/GlobalISel/InstructionSelector.h ------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 /// \file This file declares the API for the instruction selector.
11 /// This class is responsible for selecting machine instructions.
12 /// It's implemented by the target. It's used by the InstructionSelect pass.
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
17 #define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/Optional.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/Support/CodeGenCoverage.h"
23 #include "llvm/Support/LowLevelTypeImpl.h"
28 #include <initializer_list>
36 class MachineInstrBuilder;
37 class MachineFunction;
39 class MachineRegisterInfo;
40 class RegisterBankInfo;
41 class TargetInstrInfo;
42 class TargetRegisterClass;
43 class TargetRegisterInfo;
45 /// Container class for CodeGen predicate results.
46 /// This is convenient because std::bitset does not have a constructor
47 /// with an initializer list of set bits.
49 /// Each InstructionSelector subclass should define a PredicateBitset class
51 /// const unsigned MAX_SUBTARGET_PREDICATES = 192;
52 /// using PredicateBitset = PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;
53 /// and updating the constant to suit the target. Tablegen provides a suitable
54 /// definition for the predicates in use in <Target>GenGlobalISel.inc when
55 /// GET_GLOBALISEL_PREDICATE_BITSET is defined.
56 template <std::size_t MaxPredicates>
57 class PredicateBitsetImpl : public std::bitset<MaxPredicates> {
59 // Cannot inherit constructors because it's not supported by VC++..
60 PredicateBitsetImpl() = default;
62 PredicateBitsetImpl(const std::bitset<MaxPredicates> &B)
63 : std::bitset<MaxPredicates>(B) {}
65 PredicateBitsetImpl(std::initializer_list<unsigned> Init) {
67 std::bitset<MaxPredicates>::set(I);
72 /// Begin a try-block to attempt a match and jump to OnFail if it is
74 /// - OnFail - The MatchTable entry at which to resume if the match fails.
76 /// FIXME: This ought to take an argument indicating the number of try-blocks
77 /// to exit on failure. It's usually one but the last match attempt of
78 /// a block will need more. The (implemented) alternative is to tack a
79 /// GIM_Reject on the end of each try-block which is simpler but
80 /// requires an extra opcode and iteration in the interpreter on each
84 /// Switch over the opcode on the specified instruction
85 /// - InsnID - Instruction ID
86 /// - LowerBound - numerically minimum opcode supported
87 /// - UpperBound - numerically maximum + 1 opcode supported
88 /// - Default - failure jump target
89 /// - JumpTable... - (UpperBound - LowerBound) (at least 2) jump targets
92 /// Switch over the LLT on the specified instruction operand
93 /// - InsnID - Instruction ID
94 /// - OpIdx - Operand index
95 /// - LowerBound - numerically minimum Type ID supported
96 /// - UpperBound - numerically maximum + 1 Type ID supported
97 /// - Default - failure jump target
98 /// - JumpTable... - (UpperBound - LowerBound) (at least 2) jump targets
101 /// Record the specified instruction
102 /// - NewInsnID - Instruction ID to define
103 /// - InsnID - Instruction ID
104 /// - OpIdx - Operand index
107 /// Check the feature bits
108 /// - Expected features
111 /// Check the opcode on the specified instruction
112 /// - InsnID - Instruction ID
113 /// - Expected opcode
115 /// Check the instruction has the right number of operands
116 /// - InsnID - Instruction ID
117 /// - Expected number of operands
118 GIM_CheckNumOperands,
119 /// Check an immediate predicate on the specified instruction
120 /// - InsnID - Instruction ID
121 /// - The predicate to test
122 GIM_CheckI64ImmPredicate,
123 /// Check an immediate predicate on the specified instruction via an APInt.
124 /// - InsnID - Instruction ID
125 /// - The predicate to test
126 GIM_CheckAPIntImmPredicate,
127 /// Check a floating point immediate predicate on the specified instruction.
128 /// - InsnID - Instruction ID
129 /// - The predicate to test
130 GIM_CheckAPFloatImmPredicate,
131 /// Check a memory operation has the specified atomic ordering.
132 /// - InsnID - Instruction ID
133 /// - Ordering - The AtomicOrdering value
134 GIM_CheckAtomicOrdering,
135 GIM_CheckAtomicOrderingOrStrongerThan,
136 GIM_CheckAtomicOrderingWeakerThan,
137 /// Check the size of the memory access for the given machine memory operand.
138 /// - InsnID - Instruction ID
139 /// - MMOIdx - MMO index
140 /// - Size - The size in bytes of the memory access
141 GIM_CheckMemorySizeEqualTo,
142 /// Check the size of the memory access for the given machine memory operand
143 /// against the size of an operand.
144 /// - InsnID - Instruction ID
145 /// - MMOIdx - MMO index
146 /// - OpIdx - The operand index to compare the MMO against
147 GIM_CheckMemorySizeEqualToLLT,
148 GIM_CheckMemorySizeLessThanLLT,
149 GIM_CheckMemorySizeGreaterThanLLT,
150 /// Check a generic C++ instruction predicate
151 /// - InsnID - Instruction ID
152 /// - PredicateID - The ID of the predicate function to call
153 GIM_CheckCxxInsnPredicate,
155 /// Check the type for the specified operand
156 /// - InsnID - Instruction ID
157 /// - OpIdx - Operand index
160 /// Check the type of a pointer to any address space.
161 /// - InsnID - Instruction ID
162 /// - OpIdx - Operand index
163 /// - SizeInBits - The size of the pointer value in bits.
164 GIM_CheckPointerToAny,
165 /// Check the register bank for the specified operand
166 /// - InsnID - Instruction ID
167 /// - OpIdx - Operand index
168 /// - Expected register bank (specified as a register class)
169 GIM_CheckRegBankForClass,
171 /// Check the operand matches a complex predicate
172 /// - InsnID - Instruction ID
173 /// - OpIdx - Operand index
174 /// - RendererID - The renderer to hold the result
175 /// - Complex predicate ID
176 GIM_CheckComplexPattern,
178 /// Check the operand is a specific integer
179 /// - InsnID - Instruction ID
180 /// - OpIdx - Operand index
181 /// - Expected integer
182 GIM_CheckConstantInt,
183 /// Check the operand is a specific literal integer (i.e. MO.isImm() or
184 /// MO.isCImm() is true).
185 /// - InsnID - Instruction ID
186 /// - OpIdx - Operand index
187 /// - Expected integer
189 /// Check the operand is a specific intrinsic ID
190 /// - InsnID - Instruction ID
191 /// - OpIdx - Operand index
192 /// - Expected Intrinsic ID
193 GIM_CheckIntrinsicID,
195 /// Check the specified operand is an MBB
196 /// - InsnID - Instruction ID
197 /// - OpIdx - Operand index
200 /// Check if the specified operand is safe to fold into the current
202 /// - InsnID - Instruction ID
203 GIM_CheckIsSafeToFold,
205 /// Check the specified operands are identical.
206 /// - InsnID - Instruction ID
207 /// - OpIdx - Operand index
208 /// - OtherInsnID - Other instruction ID
209 /// - OtherOpIdx - Other operand index
210 GIM_CheckIsSameOperand,
212 /// Fail the current try-block, or completely fail to match if there is no
213 /// current try-block.
218 /// Mutate an instruction
219 /// - NewInsnID - Instruction ID to define
220 /// - OldInsnID - Instruction ID to mutate
221 /// - NewOpcode - The new opcode to use
224 /// Build a new instruction
225 /// - InsnID - Instruction ID to define
226 /// - Opcode - The new opcode to use
229 /// Copy an operand to the specified instruction
230 /// - NewInsnID - Instruction ID to modify
231 /// - OldInsnID - Instruction ID to copy from
232 /// - OpIdx - The operand to copy
235 /// Copy an operand to the specified instruction or add a zero register if the
236 /// operand is a zero immediate.
237 /// - NewInsnID - Instruction ID to modify
238 /// - OldInsnID - Instruction ID to copy from
239 /// - OpIdx - The operand to copy
240 /// - ZeroReg - The zero register to use
241 GIR_CopyOrAddZeroReg,
242 /// Copy an operand to the specified instruction
243 /// - NewInsnID - Instruction ID to modify
244 /// - OldInsnID - Instruction ID to copy from
245 /// - OpIdx - The operand to copy
246 /// - SubRegIdx - The subregister to copy
249 /// Add an implicit register def to the specified instruction
250 /// - InsnID - Instruction ID to modify
251 /// - RegNum - The register to add
253 /// Add an implicit register use to the specified instruction
254 /// - InsnID - Instruction ID to modify
255 /// - RegNum - The register to add
257 /// Add an register to the specified instruction
258 /// - InsnID - Instruction ID to modify
259 /// - RegNum - The register to add
262 /// Add a temporary register to the specified instruction
263 /// - InsnID - Instruction ID to modify
264 /// - TempRegID - The temporary register ID to add
265 /// - TempRegFlags - The register flags to set
268 /// Add an immediate to the specified instruction
269 /// - InsnID - Instruction ID to modify
270 /// - Imm - The immediate to add
272 /// Render complex operands to the specified instruction
273 /// - InsnID - Instruction ID to modify
274 /// - RendererID - The renderer to call
277 /// Render sub-operands of complex operands to the specified instruction
278 /// - InsnID - Instruction ID to modify
279 /// - RendererID - The renderer to call
280 /// - RenderOpID - The suboperand to render.
281 GIR_ComplexSubOperandRenderer,
282 /// Render operands to the specified instruction using a custom function
283 /// - InsnID - Instruction ID to modify
284 /// - OldInsnID - Instruction ID to get the matched operand from
285 /// - RendererFnID - Custom renderer function to call
288 /// Render a G_CONSTANT operator as a sign-extended immediate.
289 /// - NewInsnID - Instruction ID to modify
290 /// - OldInsnID - Instruction ID to copy from
291 /// The operand index is implicitly 1.
292 GIR_CopyConstantAsSImm,
294 /// Render a G_FCONSTANT operator as a sign-extended immediate.
295 /// - NewInsnID - Instruction ID to modify
296 /// - OldInsnID - Instruction ID to copy from
297 /// The operand index is implicitly 1.
298 GIR_CopyFConstantAsFPImm,
300 /// Constrain an instruction operand to a register class.
301 /// - InsnID - Instruction ID to modify
302 /// - OpIdx - Operand index
303 /// - RCEnum - Register class enumeration value
304 GIR_ConstrainOperandRC,
306 /// Constrain an instructions operands according to the instruction
308 /// - InsnID - Instruction ID to modify
309 GIR_ConstrainSelectedInstOperands,
311 /// Merge all memory operands into instruction.
312 /// - InsnID - Instruction ID to modify
313 /// - MergeInsnID... - One or more Instruction ID to merge into the result.
314 /// - GIU_MergeMemOperands_EndOfList - Terminates the list of instructions to
316 GIR_MergeMemOperands,
318 /// Erase from parent.
319 /// - InsnID - Instruction ID to erase
322 /// Create a new temporary register that's not constrained.
323 /// - TempRegID - The temporary register ID to initialize.
327 /// A successful emission
330 /// Increment the rule coverage counter.
331 /// - RuleID - The ID of the rule that was covered.
334 /// Keeping track of the number of the GI opcodes. Must be the last entry.
339 /// Indicates the end of the variable-length MergeInsnID list in a
340 /// GIR_MergeMemOperands opcode.
341 GIU_MergeMemOperands_EndOfList = -1,
344 /// Provides the logic to select generic machine instructions.
345 class InstructionSelector {
347 virtual ~InstructionSelector() = default;
349 /// Select the (possibly generic) instruction \p I to only use target-specific
350 /// opcodes. It is OK to insert multiple instructions, but they cannot be
351 /// generic pre-isel instructions.
353 /// \returns whether selection succeeded.
354 /// \pre I.getParent() && I.getParent()->getParent()
357 /// for I in all mutated/inserted instructions:
358 /// !isPreISelGenericOpcode(I.getOpcode())
359 virtual bool select(MachineInstr &I, CodeGenCoverage &CoverageInfo) const = 0;
362 using ComplexRendererFns =
363 Optional<SmallVector<std::function<void(MachineInstrBuilder &)>, 4>>;
364 using RecordedMIVector = SmallVector<MachineInstr *, 4>;
365 using NewMIVector = SmallVector<MachineInstrBuilder, 4>;
367 struct MatcherState {
368 std::vector<ComplexRendererFns::value_type> Renderers;
369 RecordedMIVector MIs;
370 DenseMap<unsigned, unsigned> TempRegisters;
372 MatcherState(unsigned MaxRenderers);
376 template <class PredicateBitset, class ComplexMatcherMemFn,
377 class CustomRendererFn>
379 ISelInfoTy(const LLT *TypeObjects, size_t NumTypeObjects,
380 const PredicateBitset *FeatureBitsets,
381 const ComplexMatcherMemFn *ComplexPredicates,
382 const CustomRendererFn *CustomRenderers)
383 : TypeObjects(TypeObjects),
384 FeatureBitsets(FeatureBitsets),
385 ComplexPredicates(ComplexPredicates),
386 CustomRenderers(CustomRenderers) {
388 for (size_t I = 0; I < NumTypeObjects; ++I)
389 TypeIDMap[TypeObjects[I]] = I;
391 const LLT *TypeObjects;
392 const PredicateBitset *FeatureBitsets;
393 const ComplexMatcherMemFn *ComplexPredicates;
394 const CustomRendererFn *CustomRenderers;
396 SmallDenseMap<LLT, unsigned, 64> TypeIDMap;
400 InstructionSelector();
402 /// Execute a given matcher table and return true if the match was successful
403 /// and false otherwise.
404 template <class TgtInstructionSelector, class PredicateBitset,
405 class ComplexMatcherMemFn, class CustomRendererFn>
406 bool executeMatchTable(
407 TgtInstructionSelector &ISel, NewMIVector &OutMIs, MatcherState &State,
408 const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, CustomRendererFn>
410 const int64_t *MatchTable, const TargetInstrInfo &TII,
411 MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
412 const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures,
413 CodeGenCoverage &CoverageInfo) const;
415 virtual const int64_t *getMatchTable() const {
416 llvm_unreachable("Should have been overridden by tablegen if used");
419 virtual bool testImmPredicate_I64(unsigned, int64_t) const {
421 "Subclasses must override this with a tablegen-erated function");
423 virtual bool testImmPredicate_APInt(unsigned, const APInt &) const {
425 "Subclasses must override this with a tablegen-erated function");
427 virtual bool testImmPredicate_APFloat(unsigned, const APFloat &) const {
429 "Subclasses must override this with a tablegen-erated function");
431 virtual bool testMIPredicate_MI(unsigned, const MachineInstr &) const {
433 "Subclasses must override this with a tablegen-erated function");
436 /// Constrain a register operand of an instruction \p I to a specified
437 /// register class. This could involve inserting COPYs before (for uses) or
438 /// after (for defs) and may replace the operand of \p I.
439 /// \returns whether operand regclass constraining succeeded.
440 bool constrainOperandRegToRegClass(MachineInstr &I, unsigned OpIdx,
441 const TargetRegisterClass &RC,
442 const TargetInstrInfo &TII,
443 const TargetRegisterInfo &TRI,
444 const RegisterBankInfo &RBI) const;
446 bool isOperandImmEqual(const MachineOperand &MO, int64_t Value,
447 const MachineRegisterInfo &MRI) const;
449 /// Return true if the specified operand is a G_GEP with a G_CONSTANT on the
450 /// right-hand side. GlobalISel's separation of pointer and integer types
451 /// means that we don't need to worry about G_OR with equivalent semantics.
452 bool isBaseWithConstantOffset(const MachineOperand &Root,
453 const MachineRegisterInfo &MRI) const;
455 /// Return true if MI can obviously be folded into IntoMI.
456 /// MI and IntoMI do not need to be in the same basic blocks, but MI must
458 bool isObviouslySafeToFold(MachineInstr &MI, MachineInstr &IntoMI) const;
461 } // end namespace llvm
463 #endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H