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