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 size of the memory access for the given machine memory operand
152  /// against the size of an operand.
153  /// - InsnID - Instruction ID
154  /// - MMOIdx - MMO index
155  /// - OpIdx - The operand index to compare the MMO against
159  /// Check a generic C++ instruction predicate
160  /// - InsnID - Instruction ID
161  /// - PredicateID - The ID of the predicate function to call
163 
164  /// Check the type for the specified operand
165  /// - InsnID - Instruction ID
166  /// - OpIdx - Operand index
167  /// - Expected type
169  /// Check the type of a pointer to any address space.
170  /// - InsnID - Instruction ID
171  /// - OpIdx - Operand index
172  /// - SizeInBits - The size of the pointer value in bits.
174  /// Check the register bank for the specified operand
175  /// - InsnID - Instruction ID
176  /// - OpIdx - Operand index
177  /// - Expected register bank (specified as a register class)
179 
180  /// Check the operand matches a complex predicate
181  /// - InsnID - Instruction ID
182  /// - OpIdx - Operand index
183  /// - RendererID - The renderer to hold the result
184  /// - Complex predicate ID
186 
187  /// Check the operand is a specific integer
188  /// - InsnID - Instruction ID
189  /// - OpIdx - Operand index
190  /// - Expected integer
192  /// Check the operand is a specific literal integer (i.e. MO.isImm() or
193  /// MO.isCImm() is true).
194  /// - InsnID - Instruction ID
195  /// - OpIdx - Operand index
196  /// - Expected integer
198  /// Check the operand is a specific intrinsic ID
199  /// - InsnID - Instruction ID
200  /// - OpIdx - Operand index
201  /// - Expected Intrinsic ID
203 
204  /// Check the specified operand is an MBB
205  /// - InsnID - Instruction ID
206  /// - OpIdx - Operand index
208 
209  /// Check if the specified operand is safe to fold into the current
210  /// instruction.
211  /// - InsnID - Instruction ID
213 
214  /// Check the specified operands are identical.
215  /// - InsnID - Instruction ID
216  /// - OpIdx - Operand index
217  /// - OtherInsnID - Other instruction ID
218  /// - OtherOpIdx - Other operand index
220 
221  /// Fail the current try-block, or completely fail to match if there is no
222  /// current try-block.
224 
225  //=== Renderers ===
226 
227  /// Mutate an instruction
228  /// - NewInsnID - Instruction ID to define
229  /// - OldInsnID - Instruction ID to mutate
230  /// - NewOpcode - The new opcode to use
232 
233  /// Build a new instruction
234  /// - InsnID - Instruction ID to define
235  /// - Opcode - The new opcode to use
237 
238  /// Copy an operand to the specified instruction
239  /// - NewInsnID - Instruction ID to modify
240  /// - OldInsnID - Instruction ID to copy from
241  /// - OpIdx - The operand to copy
243 
244  /// Copy an operand to the specified instruction or add a zero register if the
245  /// operand is a zero immediate.
246  /// - NewInsnID - Instruction ID to modify
247  /// - OldInsnID - Instruction ID to copy from
248  /// - OpIdx - The operand to copy
249  /// - ZeroReg - The zero register to use
251  /// Copy an operand to the specified instruction
252  /// - NewInsnID - Instruction ID to modify
253  /// - OldInsnID - Instruction ID to copy from
254  /// - OpIdx - The operand to copy
255  /// - SubRegIdx - The subregister to copy
257 
258  /// Add an implicit register def to the specified instruction
259  /// - InsnID - Instruction ID to modify
260  /// - RegNum - The register to add
262  /// Add an implicit register use to the specified instruction
263  /// - InsnID - Instruction ID to modify
264  /// - RegNum - The register to add
266  /// Add an register to the specified instruction
267  /// - InsnID - Instruction ID to modify
268  /// - RegNum - The register to add
270 
271  /// Add a temporary register to the specified instruction
272  /// - InsnID - Instruction ID to modify
273  /// - TempRegID - The temporary register ID to add
274  /// - TempRegFlags - The register flags to set
276 
277  /// Add an immediate to the specified instruction
278  /// - InsnID - Instruction ID to modify
279  /// - Imm - The immediate to add
281  /// Render complex operands to the specified instruction
282  /// - InsnID - Instruction ID to modify
283  /// - RendererID - The renderer to call
285 
286  /// Render sub-operands of complex operands to the specified instruction
287  /// - InsnID - Instruction ID to modify
288  /// - RendererID - The renderer to call
289  /// - RenderOpID - The suboperand to render.
291  /// Render operands to the specified instruction using a custom function
292  /// - InsnID - Instruction ID to modify
293  /// - OldInsnID - Instruction ID to get the matched operand from
294  /// - RendererFnID - Custom renderer function to call
296 
297  /// Render a G_CONSTANT operator as a sign-extended immediate.
298  /// - NewInsnID - Instruction ID to modify
299  /// - OldInsnID - Instruction ID to copy from
300  /// The operand index is implicitly 1.
302 
303  /// Render a G_FCONSTANT operator as a sign-extended immediate.
304  /// - NewInsnID - Instruction ID to modify
305  /// - OldInsnID - Instruction ID to copy from
306  /// The operand index is implicitly 1.
308 
309  /// Constrain an instruction operand to a register class.
310  /// - InsnID - Instruction ID to modify
311  /// - OpIdx - Operand index
312  /// - RCEnum - Register class enumeration value
314 
315  /// Constrain an instructions operands according to the instruction
316  /// description.
317  /// - InsnID - Instruction ID to modify
319 
320  /// Merge all memory operands into instruction.
321  /// - InsnID - Instruction ID to modify
322  /// - MergeInsnID... - One or more Instruction ID to merge into the result.
323  /// - GIU_MergeMemOperands_EndOfList - Terminates the list of instructions to
324  /// merge.
326 
327  /// Erase from parent.
328  /// - InsnID - Instruction ID to erase
330 
331  /// Create a new temporary register that's not constrained.
332  /// - TempRegID - The temporary register ID to initialize.
333  /// - Expected type
335 
336  /// A successful emission
338 
339  /// Increment the rule coverage counter.
340  /// - RuleID - The ID of the rule that was covered.
342 
343  /// Keeping track of the number of the GI opcodes. Must be the last entry.
345 };
346 
347 enum {
348  /// Indicates the end of the variable-length MergeInsnID list in a
349  /// GIR_MergeMemOperands opcode.
351 };
352 
353 /// Provides the logic to select generic machine instructions.
355 public:
356  virtual ~InstructionSelector() = default;
357 
358  /// Select the (possibly generic) instruction \p I to only use target-specific
359  /// opcodes. It is OK to insert multiple instructions, but they cannot be
360  /// generic pre-isel instructions.
361  ///
362  /// \returns whether selection succeeded.
363  /// \pre I.getParent() && I.getParent()->getParent()
364  /// \post
365  /// if returns true:
366  /// for I in all mutated/inserted instructions:
367  /// !isPreISelGenericOpcode(I.getOpcode())
368  virtual bool select(MachineInstr &I, CodeGenCoverage &CoverageInfo) const = 0;
369 
370 protected:
371  using ComplexRendererFns =
375 
376  struct MatcherState {
377  std::vector<ComplexRendererFns::value_type> Renderers;
380 
381  MatcherState(unsigned MaxRenderers);
382  };
383 
384 public:
385  template <class PredicateBitset, class ComplexMatcherMemFn,
386  class CustomRendererFn>
387  struct ISelInfoTy {
388  ISelInfoTy(const LLT *TypeObjects, size_t NumTypeObjects,
389  const PredicateBitset *FeatureBitsets,
390  const ComplexMatcherMemFn *ComplexPredicates,
391  const CustomRendererFn *CustomRenderers)
392  : TypeObjects(TypeObjects),
393  FeatureBitsets(FeatureBitsets),
394  ComplexPredicates(ComplexPredicates),
395  CustomRenderers(CustomRenderers) {
396 
397  for (size_t I = 0; I < NumTypeObjects; ++I)
398  TypeIDMap[TypeObjects[I]] = I;
399  }
400  const LLT *TypeObjects;
401  const PredicateBitset *FeatureBitsets;
402  const ComplexMatcherMemFn *ComplexPredicates;
403  const CustomRendererFn *CustomRenderers;
404 
406  };
407 
408 protected:
410 
411  /// Execute a given matcher table and return true if the match was successful
412  /// and false otherwise.
413  template <class TgtInstructionSelector, class PredicateBitset,
414  class ComplexMatcherMemFn, class CustomRendererFn>
415  bool executeMatchTable(
416  TgtInstructionSelector &ISel, NewMIVector &OutMIs, MatcherState &State,
418  &ISelInfo,
419  const int64_t *MatchTable, const TargetInstrInfo &TII,
421  const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures,
422  CodeGenCoverage &CoverageInfo) const;
423 
424  virtual const int64_t *getMatchTable() const {
425  llvm_unreachable("Should have been overridden by tablegen if used");
426  }
427 
428  virtual bool testImmPredicate_I64(unsigned, int64_t) const {
430  "Subclasses must override this with a tablegen-erated function");
431  }
432  virtual bool testImmPredicate_APInt(unsigned, const APInt &) const {
434  "Subclasses must override this with a tablegen-erated function");
435  }
436  virtual bool testImmPredicate_APFloat(unsigned, const APFloat &) const {
438  "Subclasses must override this with a tablegen-erated function");
439  }
440  virtual bool testMIPredicate_MI(unsigned, const MachineInstr &) const {
442  "Subclasses must override this with a tablegen-erated function");
443  }
444 
445  /// Constrain a register operand of an instruction \p I to a specified
446  /// register class. This could involve inserting COPYs before (for uses) or
447  /// after (for defs) and may replace the operand of \p I.
448  /// \returns whether operand regclass constraining succeeded.
449  bool constrainOperandRegToRegClass(MachineInstr &I, unsigned OpIdx,
450  const TargetRegisterClass &RC,
451  const TargetInstrInfo &TII,
452  const TargetRegisterInfo &TRI,
453  const RegisterBankInfo &RBI) const;
454 
455  bool isOperandImmEqual(const MachineOperand &MO, int64_t Value,
456  const MachineRegisterInfo &MRI) const;
457 
458  /// Return true if the specified operand is a G_GEP with a G_CONSTANT on the
459  /// right-hand side. GlobalISel's separation of pointer and integer types
460  /// means that we don't need to worry about G_OR with equivalent semantics.
461  bool isBaseWithConstantOffset(const MachineOperand &Root,
462  const MachineRegisterInfo &MRI) const;
463 
464  /// Return true if MI can obviously be folded into IntoMI.
465  /// MI and IntoMI do not need to be in the same basic blocks, but MI must
466  /// preceed IntoMI.
467  bool isObviouslySafeToFold(MachineInstr &MI, MachineInstr &IntoMI) const;
468 };
469 
470 } // end namespace llvm
471 
472 #endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
Copy an operand to the specified instruction.
Check the specified operand is an MBB.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
std::vector< ComplexRendererFns::value_type > Renderers
Build a new instruction.
Check the register bank for the specified operand.
unsigned const TargetRegisterInfo * TRI
PredicateBitsetImpl(std::initializer_list< unsigned > Init)
Begin a try-block to attempt a match and jump to OnFail if it is unsuccessful.
Create a new temporary register that&#39;s not constrained.
const ComplexMatcherMemFn * ComplexPredicates
Switch over the opcode on the specified instruction.
Check the size of the memory access for the given machine memory operand against the size of an opera...
Holds all the information related to register banks.
Definition: BitVector.h:937
virtual const int64_t * getMatchTable() const
Check the instruction has the right number of operands.
const HexagonInstrInfo * TII
Check the specified operands are identical.
Merge all memory operands into instruction.
Check the operand matches a complex predicate.
DenseMap< unsigned, unsigned > TempRegisters
SmallDenseMap< LLT, unsigned, 64 > TypeIDMap
Check the feature bits.
Mutate an instruction.
Record the specified instruction.
Render a G_FCONSTANT operator as a sign-extended immediate.
Add an implicit register use to the specified instruction.
Fail the current try-block, or completely fail to match if there is no current try-block.
TargetInstrInfo - Interface to description of machine instruction set.
Add a temporary register to the specified instruction.
Container class for CodeGen predicate results.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
virtual bool testMIPredicate_MI(unsigned, const MachineInstr &) const
Render complex operands to the specified instruction.
Check an immediate predicate on the specified instruction via an APInt.
Check the opcode on the specified instruction.
Render operands to the specified instruction using a custom function.
Check a memory operation has the specified atomic ordering.
Check the address space of the memory access for the given machine memory operand.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Constrain an instructions operands according to the instruction description.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Check the type of a pointer to any address space.
Check a generic C++ instruction predicate.
Check the size of the memory access for the given machine memory operand.
Check if the specified operand is safe to fold into the current instruction.
Add an register to the specified instruction.
Check the operand is a specific literal integer (i.e.
Copy an operand to the specified instruction.
MachineOperand class - Representation of each machine instruction operand.
Switch over the LLT on the specified instruction operand.
Increment the rule coverage counter.
Class for arbitrary precision integers.
Definition: APInt.h:69
Add an immediate to the specified instruction.
RegisterBankInfo(RegisterBank **RegBanks, unsigned NumRegBanks)
Create a RegisterBankInfo that can accommodate up to NumRegBanks RegisterBank instances.
Render a G_CONSTANT operator as a sign-extended immediate.
Copy an operand to the specified instruction or add a zero register if the operand is a zero immediat...
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:64
virtual bool testImmPredicate_I64(unsigned, int64_t) const
Render sub-operands of complex operands to the specified instruction.
#define I(x, y, z)
Definition: MD5.cpp:58
Check the operand is a specific intrinsic ID.
Add an implicit register def to the specified instruction.
Keeping track of the number of the GI opcodes. Must be the last entry.
Check the type for the specified operand.
Check the operand is a specific integer.
LLVM Value Representation.
Definition: Value.h:72
Check a floating point immediate predicate on 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)
Indicates the end of the variable-length MergeInsnID list in a GIR_MergeMemOperands opcode...
Check an immediate predicate on the specified instruction.
Constrain an instruction operand to a register class.
A successful emission.