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 MachineInstr;
35 class MachineInstrBuilder;
36 class MachineFunction;
37 class MachineOperand;
38 class MachineRegisterInfo;
39 class RegisterBankInfo;
40 class TargetInstrInfo;
41 class TargetRegisterClass;
42 class TargetRegisterInfo;
43 
44 /// Container class for CodeGen predicate results.
45 /// This is convenient because std::bitset does not have a constructor
46 /// with an initializer list of set bits.
47 ///
48 /// Each InstructionSelector subclass should define a PredicateBitset class
49 /// with:
50 /// const unsigned MAX_SUBTARGET_PREDICATES = 192;
51 /// using PredicateBitset = PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;
52 /// and updating the constant to suit the target. Tablegen provides a suitable
53 /// definition for the predicates in use in <Target>GenGlobalISel.inc when
54 /// GET_GLOBALISEL_PREDICATE_BITSET is defined.
55 template <std::size_t MaxPredicates>
56 class PredicateBitsetImpl : public std::bitset<MaxPredicates> {
57 public:
58  // Cannot inherit constructors because it's not supported by VC++..
59  PredicateBitsetImpl() = default;
60 
61  PredicateBitsetImpl(const std::bitset<MaxPredicates> &B)
62  : std::bitset<MaxPredicates>(B) {}
63 
64  PredicateBitsetImpl(std::initializer_list<unsigned> Init) {
65  for (auto I : Init)
66  std::bitset<MaxPredicates>::set(I);
67  }
68 };
69 
70 enum {
71  /// Begin a try-block to attempt a match and jump to OnFail if it is
72  /// unsuccessful.
73  /// - OnFail - The MatchTable entry at which to resume if the match fails.
74  ///
75  /// FIXME: This ought to take an argument indicating the number of try-blocks
76  /// to exit on failure. It's usually one but the last match attempt of
77  /// a block will need more. The (implemented) alternative is to tack a
78  /// GIM_Reject on the end of each try-block which is simpler but
79  /// requires an extra opcode and iteration in the interpreter on each
80  /// failed match.
82 
83  /// Switch over the opcode on the specified instruction
84  /// - InsnID - Instruction ID
85  /// - LowerBound - numerically minimum opcode supported
86  /// - UpperBound - numerically maximum + 1 opcode supported
87  /// - Default - failure jump target
88  /// - JumpTable... - (UpperBound - LowerBound) (at least 2) jump targets
90 
91  /// Switch over the LLT on the specified instruction operand
92  /// - InsnID - Instruction ID
93  /// - OpIdx - Operand index
94  /// - LowerBound - numerically minimum Type ID supported
95  /// - UpperBound - numerically maximum + 1 Type ID supported
96  /// - Default - failure jump target
97  /// - JumpTable... - (UpperBound - LowerBound) (at least 2) jump targets
99 
100  /// Record the specified instruction
101  /// - NewInsnID - Instruction ID to define
102  /// - InsnID - Instruction ID
103  /// - OpIdx - Operand index
105 
106  /// Check the feature bits
107  /// - Expected features
109 
110  /// Check the opcode on the specified instruction
111  /// - InsnID - Instruction ID
112  /// - Expected opcode
114  /// Check the instruction has the right number of operands
115  /// - InsnID - Instruction ID
116  /// - Expected number of operands
118  /// Check an immediate predicate on the specified instruction
119  /// - InsnID - Instruction ID
120  /// - The predicate to test
122  /// Check an immediate predicate on the specified instruction via an APInt.
123  /// - InsnID - Instruction ID
124  /// - The predicate to test
126  /// Check a floating point immediate predicate on the specified instruction.
127  /// - InsnID - Instruction ID
128  /// - The predicate to test
130  /// Check a memory operation has the specified atomic ordering.
131  /// - InsnID - Instruction ID
132  /// - Ordering - The AtomicOrdering value
136  /// Check the size of the memory access for the given machine memory operand.
137  /// - InsnID - Instruction ID
138  /// - MMOIdx - MMO index
139  /// - Size - The size in bytes of the memory access
141 
142  /// Check the address space of the memory access for the given machine memory
143  /// operand.
144  /// - InsnID - Instruction ID
145  /// - MMOIdx - MMO index
146  /// - NumAddrSpace - Number of valid address spaces
147  /// - AddrSpaceN - An allowed space of the memory access
148  /// - AddrSpaceN+1 ...
150 
151  /// Check the minimum alignment of the memory access for the given machine
152  /// memory operand.
153  /// - InsnID - Instruction ID
154  /// - MMOIdx - MMO index
155  /// - MinAlign - Minimum acceptable alignment
157 
158  /// Check the size of the memory access for the given machine memory operand
159  /// against the size of an operand.
160  /// - InsnID - Instruction ID
161  /// - MMOIdx - MMO index
162  /// - OpIdx - The operand index to compare the MMO against
166  /// Check a generic C++ instruction predicate
167  /// - InsnID - Instruction ID
168  /// - PredicateID - The ID of the predicate function to call
170 
171  /// Check the type for the specified operand
172  /// - InsnID - Instruction ID
173  /// - OpIdx - Operand index
174  /// - Expected type
176  /// Check the type of a pointer to any address space.
177  /// - InsnID - Instruction ID
178  /// - OpIdx - Operand index
179  /// - SizeInBits - The size of the pointer value in bits.
181  /// Check the register bank for the specified operand
182  /// - InsnID - Instruction ID
183  /// - OpIdx - Operand index
184  /// - Expected register bank (specified as a register class)
186 
187  /// Check the operand matches a complex predicate
188  /// - InsnID - Instruction ID
189  /// - OpIdx - Operand index
190  /// - RendererID - The renderer to hold the result
191  /// - Complex predicate ID
193 
194  /// Check the operand is a specific integer
195  /// - InsnID - Instruction ID
196  /// - OpIdx - Operand index
197  /// - Expected integer
199  /// Check the operand is a specific literal integer (i.e. MO.isImm() or
200  /// MO.isCImm() is true).
201  /// - InsnID - Instruction ID
202  /// - OpIdx - Operand index
203  /// - Expected integer
205  /// Check the operand is a specific intrinsic ID
206  /// - InsnID - Instruction ID
207  /// - OpIdx - Operand index
208  /// - Expected Intrinsic ID
210 
211  /// Check the specified operand is an MBB
212  /// - InsnID - Instruction ID
213  /// - OpIdx - Operand index
215 
216  /// Check if the specified operand is safe to fold into the current
217  /// instruction.
218  /// - InsnID - Instruction ID
220 
221  /// Check the specified operands are identical.
222  /// - InsnID - Instruction ID
223  /// - OpIdx - Operand index
224  /// - OtherInsnID - Other instruction ID
225  /// - OtherOpIdx - Other operand index
227 
228  /// Fail the current try-block, or completely fail to match if there is no
229  /// current try-block.
231 
232  //=== Renderers ===
233 
234  /// Mutate an instruction
235  /// - NewInsnID - Instruction ID to define
236  /// - OldInsnID - Instruction ID to mutate
237  /// - NewOpcode - The new opcode to use
239 
240  /// Build a new instruction
241  /// - InsnID - Instruction ID to define
242  /// - Opcode - The new opcode to use
244 
245  /// Copy an operand to the specified instruction
246  /// - NewInsnID - Instruction ID to modify
247  /// - OldInsnID - Instruction ID to copy from
248  /// - OpIdx - The operand to copy
250 
251  /// Copy an operand to the specified instruction or add a zero register if the
252  /// operand is a zero immediate.
253  /// - NewInsnID - Instruction ID to modify
254  /// - OldInsnID - Instruction ID to copy from
255  /// - OpIdx - The operand to copy
256  /// - ZeroReg - The zero register to use
258  /// Copy an operand to the specified instruction
259  /// - NewInsnID - Instruction ID to modify
260  /// - OldInsnID - Instruction ID to copy from
261  /// - OpIdx - The operand to copy
262  /// - SubRegIdx - The subregister to copy
264 
265  /// Add an implicit register def to the specified instruction
266  /// - InsnID - Instruction ID to modify
267  /// - RegNum - The register to add
269  /// Add an implicit register use to the specified instruction
270  /// - InsnID - Instruction ID to modify
271  /// - RegNum - The register to add
273  /// Add an register to the specified instruction
274  /// - InsnID - Instruction ID to modify
275  /// - RegNum - The register to add
277 
278  /// Add a temporary register to the specified instruction
279  /// - InsnID - Instruction ID to modify
280  /// - TempRegID - The temporary register ID to add
281  /// - TempRegFlags - The register flags to set
283 
284  /// Add an immediate to the specified instruction
285  /// - InsnID - Instruction ID to modify
286  /// - Imm - The immediate to add
288  /// Render complex operands to the specified instruction
289  /// - InsnID - Instruction ID to modify
290  /// - RendererID - The renderer to call
292 
293  /// Render sub-operands of complex operands to the specified instruction
294  /// - InsnID - Instruction ID to modify
295  /// - RendererID - The renderer to call
296  /// - RenderOpID - The suboperand to render.
298  /// Render operands to the specified instruction using a custom function
299  /// - InsnID - Instruction ID to modify
300  /// - OldInsnID - Instruction ID to get the matched operand from
301  /// - RendererFnID - Custom renderer function to call
303 
304  /// Render a G_CONSTANT operator as a sign-extended immediate.
305  /// - NewInsnID - Instruction ID to modify
306  /// - OldInsnID - Instruction ID to copy from
307  /// The operand index is implicitly 1.
309 
310  /// Render a G_FCONSTANT operator as a sign-extended immediate.
311  /// - NewInsnID - Instruction ID to modify
312  /// - OldInsnID - Instruction ID to copy from
313  /// The operand index is implicitly 1.
315 
316  /// Constrain an instruction operand to a register class.
317  /// - InsnID - Instruction ID to modify
318  /// - OpIdx - Operand index
319  /// - RCEnum - Register class enumeration value
321 
322  /// Constrain an instructions operands according to the instruction
323  /// description.
324  /// - InsnID - Instruction ID to modify
326 
327  /// Merge all memory operands into instruction.
328  /// - InsnID - Instruction ID to modify
329  /// - MergeInsnID... - One or more Instruction ID to merge into the result.
330  /// - GIU_MergeMemOperands_EndOfList - Terminates the list of instructions to
331  /// merge.
333 
334  /// Erase from parent.
335  /// - InsnID - Instruction ID to erase
337 
338  /// Create a new temporary register that's not constrained.
339  /// - TempRegID - The temporary register ID to initialize.
340  /// - Expected type
342 
343  /// A successful emission
345 
346  /// Increment the rule coverage counter.
347  /// - RuleID - The ID of the rule that was covered.
349 
350  /// Keeping track of the number of the GI opcodes. Must be the last entry.
352 };
353 
354 enum {
355  /// Indicates the end of the variable-length MergeInsnID list in a
356  /// GIR_MergeMemOperands opcode.
358 };
359 
360 /// Provides the logic to select generic machine instructions.
362 public:
363  virtual ~InstructionSelector() = default;
364 
365  /// Select the (possibly generic) instruction \p I to only use target-specific
366  /// opcodes. It is OK to insert multiple instructions, but they cannot be
367  /// generic pre-isel instructions.
368  ///
369  /// \returns whether selection succeeded.
370  /// \pre I.getParent() && I.getParent()->getParent()
371  /// \post
372  /// if returns true:
373  /// for I in all mutated/inserted instructions:
374  /// !isPreISelGenericOpcode(I.getOpcode())
375  virtual bool select(MachineInstr &I) = 0;
376 
377  CodeGenCoverage *CoverageInfo = nullptr;
378  MachineFunction *MF = nullptr;
379 
380  /// Setup per-MF selector state.
381  virtual void setupMF(MachineFunction &mf, CodeGenCoverage &covinfo) {
382  CoverageInfo = &covinfo;
383  MF = &mf;
384  }
385 
386 protected:
387  using ComplexRendererFns =
391 
392  struct MatcherState {
393  std::vector<ComplexRendererFns::value_type> Renderers;
396 
397  MatcherState(unsigned MaxRenderers);
398  };
399 
400 public:
401  template <class PredicateBitset, class ComplexMatcherMemFn,
402  class CustomRendererFn>
403  struct ISelInfoTy {
404  ISelInfoTy(const LLT *TypeObjects, size_t NumTypeObjects,
405  const PredicateBitset *FeatureBitsets,
406  const ComplexMatcherMemFn *ComplexPredicates,
407  const CustomRendererFn *CustomRenderers)
408  : TypeObjects(TypeObjects),
409  FeatureBitsets(FeatureBitsets),
410  ComplexPredicates(ComplexPredicates),
411  CustomRenderers(CustomRenderers) {
412 
413  for (size_t I = 0; I < NumTypeObjects; ++I)
414  TypeIDMap[TypeObjects[I]] = I;
415  }
416  const LLT *TypeObjects;
417  const PredicateBitset *FeatureBitsets;
418  const ComplexMatcherMemFn *ComplexPredicates;
419  const CustomRendererFn *CustomRenderers;
420 
422  };
423 
424 protected:
426 
427  /// Execute a given matcher table and return true if the match was successful
428  /// and false otherwise.
429  template <class TgtInstructionSelector, class PredicateBitset,
430  class ComplexMatcherMemFn, class CustomRendererFn>
431  bool executeMatchTable(
432  TgtInstructionSelector &ISel, NewMIVector &OutMIs, MatcherState &State,
434  &ISelInfo,
435  const int64_t *MatchTable, const TargetInstrInfo &TII,
437  const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures,
438  CodeGenCoverage &CoverageInfo) const;
439 
440  virtual const int64_t *getMatchTable() const {
441  llvm_unreachable("Should have been overridden by tablegen if used");
442  }
443 
444  virtual bool testImmPredicate_I64(unsigned, int64_t) const {
446  "Subclasses must override this with a tablegen-erated function");
447  }
448  virtual bool testImmPredicate_APInt(unsigned, const APInt &) const {
450  "Subclasses must override this with a tablegen-erated function");
451  }
452  virtual bool testImmPredicate_APFloat(unsigned, const APFloat &) const {
454  "Subclasses must override this with a tablegen-erated function");
455  }
456  virtual bool testMIPredicate_MI(unsigned, const MachineInstr &) const {
458  "Subclasses must override this with a tablegen-erated function");
459  }
460 
461  /// Constrain a register operand of an instruction \p I to a specified
462  /// register class. This could involve inserting COPYs before (for uses) or
463  /// after (for defs) and may replace the operand of \p I.
464  /// \returns whether operand regclass constraining succeeded.
465  bool constrainOperandRegToRegClass(MachineInstr &I, unsigned OpIdx,
466  const TargetRegisterClass &RC,
467  const TargetInstrInfo &TII,
468  const TargetRegisterInfo &TRI,
469  const RegisterBankInfo &RBI) const;
470 
471  bool isOperandImmEqual(const MachineOperand &MO, int64_t Value,
472  const MachineRegisterInfo &MRI) const;
473 
474  /// Return true if the specified operand is a G_GEP with a G_CONSTANT on the
475  /// right-hand side. GlobalISel's separation of pointer and integer types
476  /// means that we don't need to worry about G_OR with equivalent semantics.
477  bool isBaseWithConstantOffset(const MachineOperand &Root,
478  const MachineRegisterInfo &MRI) const;
479 
480  /// Return true if MI can obviously be folded into IntoMI.
481  /// MI and IntoMI do not need to be in the same basic blocks, but MI must
482  /// preceed IntoMI.
483  bool isObviouslySafeToFold(MachineInstr &MI, MachineInstr &IntoMI) const;
484 };
485 
486 } // end namespace llvm
487 
488 #endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
Constrain an instruction operand to a register class.
Check an immediate predicate on the specified instruction via an APInt.
Record the specified instruction.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
std::vector< ComplexRendererFns::value_type > Renderers
Add an implicit register use to the specified instruction.
Check the operand is a specific literal integer (i.e.
Increment the rule coverage counter.
unsigned const TargetRegisterInfo * TRI
PredicateBitsetImpl(std::initializer_list< unsigned > Init)
Check the operand is a specific intrinsic ID.
Check the opcode on the specified instruction.
const ComplexMatcherMemFn * ComplexPredicates
A successful emission.
Check an immediate predicate on the specified instruction.
Holds all the information related to register banks.
Check the specified operand is an MBB.
Definition: BitVector.h:937
virtual const int64_t * getMatchTable() const
Check the type for the specified operand.
const HexagonInstrInfo * TII
Render sub-operands of complex operands to the specified instruction.
Check a generic C++ instruction predicate.
Switch over the LLT on the specified instruction operand.
DenseMap< unsigned, unsigned > TempRegisters
SmallDenseMap< LLT, unsigned, 64 > TypeIDMap
Check the feature bits.
Check the size of the memory access for the given machine memory operand against the size of an opera...
Copy an operand to the specified instruction.
Build a new instruction.
Create a new temporary register that&#39;s not constrained.
Check the address space of the memory access for the given machine memory operand.
Check a floating point immediate predicate on the specified instruction.
virtual void setupMF(MachineFunction &mf, CodeGenCoverage &covinfo)
Setup per-MF selector state.
Add an register to the specified instruction.
Check the instruction has the right number of operands.
TargetInstrInfo - Interface to description of machine instruction set.
Container class for CodeGen predicate results.
Merge all memory operands into instruction.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
virtual bool testMIPredicate_MI(unsigned, const MachineInstr &) const
Render a G_CONSTANT operator as a sign-extended immediate.
Indicates the end of the variable-length MergeInsnID list in a GIR_MergeMemOperands opcode...
Copy an operand to the specified instruction.
Check the minimum alignment of the memory access for the given machine memory operand.
Check the size of the memory access for the given machine memory operand.
Render operands to the specified instruction using a custom function.
Check the register bank for the specified operand.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Render a G_FCONSTANT operator as a sign-extended immediate.
Check the specified operands are identical.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Add a temporary register to the specified instruction.
Check the type of a pointer to any address space.
MachineOperand class - Representation of each machine instruction operand.
Keeping track of the number of the GI opcodes. Must be the last entry.
Copy an operand to the specified instruction or add a zero register if the operand is a zero immediat...
Add an immediate to the specified instruction.
Class for arbitrary precision integers.
Definition: APInt.h:69
RegisterBankInfo(RegisterBank **RegBanks, unsigned NumRegBanks)
Create a RegisterBankInfo that can accommodate up to NumRegBanks RegisterBank instances.
Add an implicit register def to the specified instruction.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Mutate an instruction.
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:64
virtual bool testImmPredicate_I64(unsigned, int64_t) const
Switch over the opcode on the specified instruction.
Check the operand is a specific integer.
#define I(x, y, z)
Definition: MD5.cpp:58
Constrain an instructions operands according to the instruction description.
Begin a try-block to attempt a match and jump to OnFail if it is unsuccessful.
LLVM Value Representation.
Definition: Value.h:73
Check if the specified operand is safe to fold into the current instruction.
Render complex operands to the specified instruction.
virtual bool testImmPredicate_APInt(unsigned, const APInt &) const
virtual bool testImmPredicate_APFloat(unsigned, const APFloat &) const
IRTranslator LLVM IR MI
PredicateBitsetImpl(const std::bitset< MaxPredicates > &B)
Fail the current try-block, or completely fail to match if there is no current try-block.
Check the operand matches a complex predicate.
Check a memory operation has the specified atomic ordering.