LLVM  10.0.0svn
InstructionSelector.h
Go to the documentation of this file.
1 //===- llvm/CodeGen/GlobalISel/InstructionSelector.h ------------*- 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 /// \file This file declares the API for the instruction selector.
10 /// This class is responsible for selecting machine instructions.
11 /// It's implemented by the target. It's used by the InstructionSelect pass.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
16 #define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
17 
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/Optional.h"
20 #include "llvm/ADT/SmallVector.h"
23 #include <bitset>
24 #include <cstddef>
25 #include <cstdint>
26 #include <functional>
27 #include <initializer_list>
28 #include <vector>
29 
30 namespace llvm {
31 
32 class APInt;
33 class APFloat;
34 class GISelKnownBits;
35 class MachineInstr;
36 class MachineInstrBuilder;
37 class MachineFunction;
38 class MachineOperand;
39 class MachineRegisterInfo;
40 class RegisterBankInfo;
41 class TargetInstrInfo;
42 class TargetRegisterClass;
43 class TargetRegisterInfo;
44 
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.
48 ///
49 /// Each InstructionSelector subclass should define a PredicateBitset class
50 /// with:
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> {
58 public:
59  // Cannot inherit constructors because it's not supported by VC++..
60  PredicateBitsetImpl() = default;
61 
62  PredicateBitsetImpl(const std::bitset<MaxPredicates> &B)
63  : std::bitset<MaxPredicates>(B) {}
64 
65  PredicateBitsetImpl(std::initializer_list<unsigned> Init) {
66  for (auto I : Init)
67  std::bitset<MaxPredicates>::set(I);
68  }
69 };
70 
71 enum {
72  /// Begin a try-block to attempt a match and jump to OnFail if it is
73  /// unsuccessful.
74  /// - OnFail - The MatchTable entry at which to resume if the match fails.
75  ///
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
81  /// failed match.
83 
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
91 
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
100 
101  /// Record the specified instruction
102  /// - NewInsnID - Instruction ID to define
103  /// - InsnID - Instruction ID
104  /// - OpIdx - Operand index
106 
107  /// Check the feature bits
108  /// - Expected features
110 
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
119  /// Check an immediate predicate on the specified instruction
120  /// - InsnID - Instruction ID
121  /// - The predicate to test
123  /// Check an immediate predicate on the specified instruction via an APInt.
124  /// - InsnID - Instruction ID
125  /// - The predicate to test
127  /// Check a floating point immediate predicate on the specified instruction.
128  /// - InsnID - Instruction ID
129  /// - The predicate to test
131  /// Check a memory operation has the specified atomic ordering.
132  /// - InsnID - Instruction ID
133  /// - Ordering - The AtomicOrdering value
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
142 
143  /// Check the address space of the memory access for the given machine memory
144  /// operand.
145  /// - InsnID - Instruction ID
146  /// - MMOIdx - MMO index
147  /// - NumAddrSpace - Number of valid address spaces
148  /// - AddrSpaceN - An allowed space of the memory access
149  /// - AddrSpaceN+1 ...
151 
152  /// Check the minimum alignment of the memory access for the given machine
153  /// memory operand.
154  /// - InsnID - Instruction ID
155  /// - MMOIdx - MMO index
156  /// - MinAlign - Minimum acceptable alignment
158 
159  /// Check the size of the memory access for the given machine memory operand
160  /// against the size of an operand.
161  /// - InsnID - Instruction ID
162  /// - MMOIdx - MMO index
163  /// - OpIdx - The operand index to compare the MMO against
167  /// Check a generic C++ instruction predicate
168  /// - InsnID - Instruction ID
169  /// - PredicateID - The ID of the predicate function to call
171 
172  /// Check the type for the specified operand
173  /// - InsnID - Instruction ID
174  /// - OpIdx - Operand index
175  /// - Expected type
177  /// Check the type of a pointer to any address space.
178  /// - InsnID - Instruction ID
179  /// - OpIdx - Operand index
180  /// - SizeInBits - The size of the pointer value in bits.
182  /// Check the register bank for the specified operand
183  /// - InsnID - Instruction ID
184  /// - OpIdx - Operand index
185  /// - Expected register bank (specified as a register class)
187 
188  /// Check the operand matches a complex predicate
189  /// - InsnID - Instruction ID
190  /// - OpIdx - Operand index
191  /// - RendererID - The renderer to hold the result
192  /// - Complex predicate ID
194 
195  /// Check the operand is a specific integer
196  /// - InsnID - Instruction ID
197  /// - OpIdx - Operand index
198  /// - Expected integer
200  /// Check the operand is a specific literal integer (i.e. MO.isImm() or
201  /// MO.isCImm() is true).
202  /// - InsnID - Instruction ID
203  /// - OpIdx - Operand index
204  /// - Expected integer
206  /// Check the operand is a specific intrinsic ID
207  /// - InsnID - Instruction ID
208  /// - OpIdx - Operand index
209  /// - Expected Intrinsic ID
211 
212  /// Check the operand is a specific predicate
213  /// - InsnID - Instruction ID
214  /// - OpIdx - Operand index
215  /// - Expected predicate
217 
218  /// Check the specified operand is an MBB
219  /// - InsnID - Instruction ID
220  /// - OpIdx - Operand index
222 
223  /// Check the specified operand is an Imm
224  /// - InsnID - Instruction ID
225  /// - OpIdx - Operand index
227 
228  /// Check if the specified operand is safe to fold into the current
229  /// instruction.
230  /// - InsnID - Instruction ID
232 
233  /// Check the specified operands are identical.
234  /// - InsnID - Instruction ID
235  /// - OpIdx - Operand index
236  /// - OtherInsnID - Other instruction ID
237  /// - OtherOpIdx - Other operand index
239 
240  /// Fail the current try-block, or completely fail to match if there is no
241  /// current try-block.
243 
244  //=== Renderers ===
245 
246  /// Mutate an instruction
247  /// - NewInsnID - Instruction ID to define
248  /// - OldInsnID - Instruction ID to mutate
249  /// - NewOpcode - The new opcode to use
251 
252  /// Build a new instruction
253  /// - InsnID - Instruction ID to define
254  /// - Opcode - The new opcode to use
256 
257  /// Copy an operand to the specified instruction
258  /// - NewInsnID - Instruction ID to modify
259  /// - OldInsnID - Instruction ID to copy from
260  /// - OpIdx - The operand to copy
262 
263  /// Copy an operand to the specified instruction or add a zero register if the
264  /// operand is a zero immediate.
265  /// - NewInsnID - Instruction ID to modify
266  /// - OldInsnID - Instruction ID to copy from
267  /// - OpIdx - The operand to copy
268  /// - ZeroReg - The zero register to use
270  /// Copy an operand to the specified instruction
271  /// - NewInsnID - Instruction ID to modify
272  /// - OldInsnID - Instruction ID to copy from
273  /// - OpIdx - The operand to copy
274  /// - SubRegIdx - The subregister to copy
276 
277  /// Add an implicit register def to the specified instruction
278  /// - InsnID - Instruction ID to modify
279  /// - RegNum - The register to add
281  /// Add an implicit register use to the specified instruction
282  /// - InsnID - Instruction ID to modify
283  /// - RegNum - The register to add
285  /// Add an register to the specified instruction
286  /// - InsnID - Instruction ID to modify
287  /// - RegNum - The register to add
289 
290  /// Add a temporary register to the specified instruction
291  /// - InsnID - Instruction ID to modify
292  /// - TempRegID - The temporary register ID to add
293  /// - TempRegFlags - The register flags to set
295 
296  /// Add an immediate to the specified instruction
297  /// - InsnID - Instruction ID to modify
298  /// - Imm - The immediate to add
300  /// Render complex operands to the specified instruction
301  /// - InsnID - Instruction ID to modify
302  /// - RendererID - The renderer to call
304 
305  /// Render sub-operands of complex operands to the specified instruction
306  /// - InsnID - Instruction ID to modify
307  /// - RendererID - The renderer to call
308  /// - RenderOpID - The suboperand to render.
310  /// Render operands to the specified instruction using a custom function
311  /// - InsnID - Instruction ID to modify
312  /// - OldInsnID - Instruction ID to get the matched operand from
313  /// - RendererFnID - Custom renderer function to call
315 
316  /// Render a G_CONSTANT operator as a sign-extended immediate.
317  /// - NewInsnID - Instruction ID to modify
318  /// - OldInsnID - Instruction ID to copy from
319  /// The operand index is implicitly 1.
321 
322  /// Render a G_FCONSTANT operator as a sign-extended immediate.
323  /// - NewInsnID - Instruction ID to modify
324  /// - OldInsnID - Instruction ID to copy from
325  /// The operand index is implicitly 1.
327 
328  /// Constrain an instruction operand to a register class.
329  /// - InsnID - Instruction ID to modify
330  /// - OpIdx - Operand index
331  /// - RCEnum - Register class enumeration value
333 
334  /// Constrain an instructions operands according to the instruction
335  /// description.
336  /// - InsnID - Instruction ID to modify
338 
339  /// Merge all memory operands into instruction.
340  /// - InsnID - Instruction ID to modify
341  /// - MergeInsnID... - One or more Instruction ID to merge into the result.
342  /// - GIU_MergeMemOperands_EndOfList - Terminates the list of instructions to
343  /// merge.
345 
346  /// Erase from parent.
347  /// - InsnID - Instruction ID to erase
349 
350  /// Create a new temporary register that's not constrained.
351  /// - TempRegID - The temporary register ID to initialize.
352  /// - Expected type
354 
355  /// A successful emission
357 
358  /// Increment the rule coverage counter.
359  /// - RuleID - The ID of the rule that was covered.
361 
362  /// Keeping track of the number of the GI opcodes. Must be the last entry.
364 };
365 
366 enum {
367  /// Indicates the end of the variable-length MergeInsnID list in a
368  /// GIR_MergeMemOperands opcode.
370 };
371 
372 /// Provides the logic to select generic machine instructions.
374 public:
375  virtual ~InstructionSelector() = default;
376 
377  /// Select the (possibly generic) instruction \p I to only use target-specific
378  /// opcodes. It is OK to insert multiple instructions, but they cannot be
379  /// generic pre-isel instructions.
380  ///
381  /// \returns whether selection succeeded.
382  /// \pre I.getParent() && I.getParent()->getParent()
383  /// \post
384  /// if returns true:
385  /// for I in all mutated/inserted instructions:
386  /// !isPreISelGenericOpcode(I.getOpcode())
387  virtual bool select(MachineInstr &I) = 0;
388 
389  CodeGenCoverage *CoverageInfo = nullptr;
391  MachineFunction *MF = nullptr;
392 
393  /// Setup per-MF selector state.
394  virtual void setupMF(MachineFunction &mf,
395  GISelKnownBits &KB,
396  CodeGenCoverage &covinfo) {
397  CoverageInfo = &covinfo;
398  KnownBits = &KB;
399  MF = &mf;
400  }
401 
402 protected:
403  using ComplexRendererFns =
407 
408  struct MatcherState {
409  std::vector<ComplexRendererFns::value_type> Renderers;
412 
413  MatcherState(unsigned MaxRenderers);
414  };
415 
416 public:
417  template <class PredicateBitset, class ComplexMatcherMemFn,
418  class CustomRendererFn>
419  struct ISelInfoTy {
420  ISelInfoTy(const LLT *TypeObjects, size_t NumTypeObjects,
421  const PredicateBitset *FeatureBitsets,
422  const ComplexMatcherMemFn *ComplexPredicates,
423  const CustomRendererFn *CustomRenderers)
424  : TypeObjects(TypeObjects),
425  FeatureBitsets(FeatureBitsets),
426  ComplexPredicates(ComplexPredicates),
427  CustomRenderers(CustomRenderers) {
428 
429  for (size_t I = 0; I < NumTypeObjects; ++I)
430  TypeIDMap[TypeObjects[I]] = I;
431  }
432  const LLT *TypeObjects;
433  const PredicateBitset *FeatureBitsets;
434  const ComplexMatcherMemFn *ComplexPredicates;
435  const CustomRendererFn *CustomRenderers;
436 
438  };
439 
440 protected:
442 
443  /// Execute a given matcher table and return true if the match was successful
444  /// and false otherwise.
445  template <class TgtInstructionSelector, class PredicateBitset,
446  class ComplexMatcherMemFn, class CustomRendererFn>
447  bool executeMatchTable(
448  TgtInstructionSelector &ISel, NewMIVector &OutMIs, MatcherState &State,
450  &ISelInfo,
451  const int64_t *MatchTable, const TargetInstrInfo &TII,
453  const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures,
454  CodeGenCoverage &CoverageInfo) const;
455 
456  virtual const int64_t *getMatchTable() const {
457  llvm_unreachable("Should have been overridden by tablegen if used");
458  }
459 
460  virtual bool testImmPredicate_I64(unsigned, int64_t) const {
462  "Subclasses must override this with a tablegen-erated function");
463  }
464  virtual bool testImmPredicate_APInt(unsigned, const APInt &) const {
466  "Subclasses must override this with a tablegen-erated function");
467  }
468  virtual bool testImmPredicate_APFloat(unsigned, const APFloat &) const {
470  "Subclasses must override this with a tablegen-erated function");
471  }
472  virtual bool testMIPredicate_MI(unsigned, const MachineInstr &) const {
474  "Subclasses must override this with a tablegen-erated function");
475  }
476 
477  /// Constrain a register operand of an instruction \p I to a specified
478  /// register class. This could involve inserting COPYs before (for uses) or
479  /// after (for defs) and may replace the operand of \p I.
480  /// \returns whether operand regclass constraining succeeded.
481  bool constrainOperandRegToRegClass(MachineInstr &I, unsigned OpIdx,
482  const TargetRegisterClass &RC,
483  const TargetInstrInfo &TII,
484  const TargetRegisterInfo &TRI,
485  const RegisterBankInfo &RBI) const;
486 
487  bool isOperandImmEqual(const MachineOperand &MO, int64_t Value,
488  const MachineRegisterInfo &MRI) const;
489 
490  /// Return true if the specified operand is a G_GEP with a G_CONSTANT on the
491  /// right-hand side. GlobalISel's separation of pointer and integer types
492  /// means that we don't need to worry about G_OR with equivalent semantics.
493  bool isBaseWithConstantOffset(const MachineOperand &Root,
494  const MachineRegisterInfo &MRI) const;
495 
496  /// Return true if MI can obviously be folded into IntoMI.
497  /// MI and IntoMI do not need to be in the same basic blocks, but MI must
498  /// preceed IntoMI.
499  bool isObviouslySafeToFold(MachineInstr &MI, MachineInstr &IntoMI) const;
500 };
501 
502 } // end namespace llvm
503 
504 #endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Constrain an instruction operand to a register class.
virtual void setupMF(MachineFunction &mf, GISelKnownBits &KB, CodeGenCoverage &covinfo)
Setup per-MF selector state.
std::vector< ComplexRendererFns::value_type > Renderers
unsigned const TargetRegisterInfo * TRI
PredicateBitsetImpl(std::initializer_list< unsigned > Init)
Add an implicit register def to the specified instruction.
const ComplexMatcherMemFn * ComplexPredicates
Merge all memory operands into instruction.
Check a memory operation has the specified atomic ordering.
Holds all the information related to register banks.
Definition: BitVector.h:937
virtual const int64_t * getMatchTable() const
const HexagonInstrInfo * TII
Check the specified operands are identical.
Check the specified operand is an MBB.
Check the type of a pointer to any address space.
Render operands to the specified instruction using a custom function.
DenseMap< unsigned, unsigned > TempRegisters
SmallDenseMap< LLT, unsigned, 64 > TypeIDMap
Add an immediate to the specified instruction.
A successful emission.
Mutate an instruction.
Copy an operand to the specified instruction.
Switch over the LLT on the specified instruction operand.
TargetInstrInfo - Interface to description of machine instruction set.
Add an implicit register use to the specified instruction.
Container class for CodeGen predicate results.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Render sub-operands of complex operands to the specified instruction.
unsigned const MachineRegisterInfo * MRI
virtual bool testMIPredicate_MI(unsigned, const MachineInstr &) const
Build a new instruction.
Copy an operand to the specified instruction.
Check the operand is a specific integer.
Check the instruction has the right number of operands.
Check if the specified operand is safe to fold into the current instruction.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Switch over the opcode on the specified instruction.
Check a floating point immediate predicate on the specified instruction.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Indicates the end of the variable-length MergeInsnID list in a GIR_MergeMemOperands opcode...
Check the minimum alignment of the memory access for the given machine memory operand.
Check the opcode on the specified instruction.
Check a generic C++ instruction predicate.
Constrain an instructions operands according to the instruction description.
Render a G_CONSTANT operator as a sign-extended immediate.
Increment the rule coverage counter.
Check the register bank for the specified operand.
Check the type for the specified operand.
MachineOperand class - Representation of each machine instruction operand.
Check the size of the memory access for the given machine memory operand against the size of an opera...
Class for arbitrary precision integers.
Definition: APInt.h:69
Create a new temporary register that&#39;s not constrained.
RegisterBankInfo(RegisterBank **RegBanks, unsigned NumRegBanks)
Create a RegisterBankInfo that can accommodate up to NumRegBanks RegisterBank instances.
Copy an operand to the specified instruction or add a zero register if the operand is a zero immediat...
Check the feature bits.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Provides the logic to select generic machine instructions.
ISelInfoTy(const LLT *TypeObjects, size_t NumTypeObjects, const PredicateBitset *FeatureBitsets, const ComplexMatcherMemFn *ComplexPredicates, const CustomRendererFn *CustomRenderers)
Representation of each machine instruction.
Definition: MachineInstr.h:63
Render complex operands to the specified instruction.
virtual bool testImmPredicate_I64(unsigned, int64_t) const
Check the specified operand is an Imm.
Fail the current try-block, or completely fail to match if there is no current try-block.
Check the operand is a specific literal integer (i.e.
Check the size of the memory access for the given machine memory operand.
#define I(x, y, z)
Definition: MD5.cpp:58
Check an immediate predicate on the specified instruction.
Check the operand is a specific predicate.
Begin a try-block to attempt a match and jump to OnFail if it is unsuccessful.
Add an register to the specified instruction.
Check the operand matches a complex predicate.
Check the address space of the memory access for the given machine memory operand.
LLVM Value Representation.
Definition: Value.h:74
Record the specified instruction.
Render a G_FCONSTANT operator as a sign-extended immediate.
virtual bool testImmPredicate_APInt(unsigned, const APInt &) const
Check the operand is a specific intrinsic ID.
virtual bool testImmPredicate_APFloat(unsigned, const APFloat &) const
IRTranslator LLVM IR MI
PredicateBitsetImpl(const std::bitset< MaxPredicates > &B)
Keeping track of the number of the GI opcodes. Must be the last entry.
Add a temporary register to the specified instruction.
Check an immediate predicate on the specified instruction via an APInt.