LLVM  8.0.0svn
InstructionSelector.h
Go to the documentation of this file.
1 //===- llvm/CodeGen/GlobalISel/InstructionSelector.h ------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
17 #define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
18 
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/Optional.h"
21 #include "llvm/ADT/SmallVector.h"
24 #include <bitset>
25 #include <cstddef>
26 #include <cstdint>
27 #include <functional>
28 #include <initializer_list>
29 #include <vector>
30 
31 namespace llvm {
32 
33 class APInt;
34 class APFloat;
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  /// 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
150  /// Check a generic C++ instruction predicate
151  /// - InsnID - Instruction ID
152  /// - PredicateID - The ID of the predicate function to call
154 
155  /// Check the type for the specified operand
156  /// - InsnID - Instruction ID
157  /// - OpIdx - Operand index
158  /// - Expected type
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.
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)
170 
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
177 
178  /// Check the operand is a specific integer
179  /// - InsnID - Instruction ID
180  /// - OpIdx - Operand index
181  /// - Expected integer
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
194 
195  /// Check the specified operand is an MBB
196  /// - InsnID - Instruction ID
197  /// - OpIdx - Operand index
199 
200  /// Check if the specified operand is safe to fold into the current
201  /// instruction.
202  /// - InsnID - Instruction ID
204 
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
211 
212  /// Fail the current try-block, or completely fail to match if there is no
213  /// current try-block.
215 
216  //=== Renderers ===
217 
218  /// Mutate an instruction
219  /// - NewInsnID - Instruction ID to define
220  /// - OldInsnID - Instruction ID to mutate
221  /// - NewOpcode - The new opcode to use
223 
224  /// Build a new instruction
225  /// - InsnID - Instruction ID to define
226  /// - Opcode - The new opcode to use
228 
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
234 
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
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
248 
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
261 
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
267 
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
276 
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.
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
287 
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.
293 
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.
299 
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
305 
306  /// Constrain an instructions operands according to the instruction
307  /// description.
308  /// - InsnID - Instruction ID to modify
310 
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
315  /// merge.
317 
318  /// Erase from parent.
319  /// - InsnID - Instruction ID to erase
321 
322  /// Create a new temporary register that's not constrained.
323  /// - TempRegID - The temporary register ID to initialize.
324  /// - Expected type
326 
327  /// A successful emission
329 
330  /// Increment the rule coverage counter.
331  /// - RuleID - The ID of the rule that was covered.
333 
334  /// Keeping track of the number of the GI opcodes. Must be the last entry.
336 };
337 
338 enum {
339  /// Indicates the end of the variable-length MergeInsnID list in a
340  /// GIR_MergeMemOperands opcode.
342 };
343 
344 /// Provides the logic to select generic machine instructions.
346 public:
347  virtual ~InstructionSelector() = default;
348 
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.
352  ///
353  /// \returns whether selection succeeded.
354  /// \pre I.getParent() && I.getParent()->getParent()
355  /// \post
356  /// if returns true:
357  /// for I in all mutated/inserted instructions:
358  /// !isPreISelGenericOpcode(I.getOpcode())
359  virtual bool select(MachineInstr &I, CodeGenCoverage &CoverageInfo) const = 0;
360 
361 protected:
362  using ComplexRendererFns =
366 
367  struct MatcherState {
368  std::vector<ComplexRendererFns::value_type> Renderers;
371 
372  MatcherState(unsigned MaxRenderers);
373  };
374 
375 public:
376  template <class PredicateBitset, class ComplexMatcherMemFn,
377  class CustomRendererFn>
378  struct ISelInfoTy {
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) {
387 
388  for (size_t I = 0; I < NumTypeObjects; ++I)
389  TypeIDMap[TypeObjects[I]] = I;
390  }
391  const LLT *TypeObjects;
392  const PredicateBitset *FeatureBitsets;
393  const ComplexMatcherMemFn *ComplexPredicates;
394  const CustomRendererFn *CustomRenderers;
395 
397  };
398 
399 protected:
401 
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,
409  &ISelInfo,
410  const int64_t *MatchTable, const TargetInstrInfo &TII,
412  const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures,
413  CodeGenCoverage &CoverageInfo) const;
414 
415  virtual const int64_t *getMatchTable() const {
416  llvm_unreachable("Should have been overridden by tablegen if used");
417  }
418 
419  virtual bool testImmPredicate_I64(unsigned, int64_t) const {
421  "Subclasses must override this with a tablegen-erated function");
422  }
423  virtual bool testImmPredicate_APInt(unsigned, const APInt &) const {
425  "Subclasses must override this with a tablegen-erated function");
426  }
427  virtual bool testImmPredicate_APFloat(unsigned, const APFloat &) const {
429  "Subclasses must override this with a tablegen-erated function");
430  }
431  virtual bool testMIPredicate_MI(unsigned, const MachineInstr &) const {
433  "Subclasses must override this with a tablegen-erated function");
434  }
435 
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;
445 
446  bool isOperandImmEqual(const MachineOperand &MO, int64_t Value,
447  const MachineRegisterInfo &MRI) const;
448 
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;
454 
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
457  /// preceed IntoMI.
458  bool isObviouslySafeToFold(MachineInstr &MI, MachineInstr &IntoMI) const;
459 };
460 
461 } // end namespace llvm
462 
463 #endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
Add a temporary register to the specified instruction.
Add an implicit register use to the specified instruction.
Check the feature bits.
Check the operand is a specific intrinsic ID.
Check an immediate predicate on the specified instruction via an APInt.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Copy an operand to the specified instruction.
std::vector< ComplexRendererFns::value_type > Renderers
unsigned const TargetRegisterInfo * TRI
PredicateBitsetImpl(std::initializer_list< unsigned > Init)
Switch over the LLT on the specified instruction operand.
const ComplexMatcherMemFn * ComplexPredicates
Constrain an instruction operand to a register class.
Holds all the information related to register banks.
Check if the specified operand is safe to fold into the current instruction.
Increment the rule coverage counter.
Definition: BitVector.h:938
virtual const int64_t * getMatchTable() const
const HexagonInstrInfo * TII
Keeping track of the number of the GI opcodes. Must be the last entry.
Render sub-operands of complex operands to the specified instruction.
DenseMap< unsigned, unsigned > TempRegisters
SmallDenseMap< LLT, unsigned, 64 > TypeIDMap
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...
Add an immediate to the specified instruction.
Check the operand is a specific literal integer (i.e.
Copy an operand to the specified instruction or add a zero register if the operand is a zero immediat...
TargetInstrInfo - Interface to description of machine instruction set.
A successful emission.
Container class for CodeGen predicate results.
Create a new temporary register that&#39;s not constrained.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Merge all memory operands into instruction.
unsigned const MachineRegisterInfo * MRI
virtual bool testMIPredicate_MI(unsigned, const MachineInstr &) const
Check the specified operands are identical.
Copy an operand to the specified instruction.
Constrain an instructions operands according to the instruction description.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Check the opcode on the specified instruction.
Check the type for the specified operand.
Check the instruction has the right number of operands.
MachineOperand class - Representation of each machine instruction operand.
Render operands to the specified instruction using a custom function.
Record the specified instruction.
Check a generic C++ instruction predicate.
Add an register to the specified instruction.
Fail the current try-block, or completely fail to match if there is no current try-block.
Class for arbitrary precision integers.
Definition: APInt.h:70
Check a floating point immediate predicate on the specified instruction.
RegisterBankInfo(RegisterBank **RegBanks, unsigned NumRegBanks)
Create a RegisterBankInfo that can accommodate up to NumRegBanks RegisterBank instances.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Check the operand matches a complex predicate.
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
Check the size of the memory access for the given machine memory operand.
Check an immediate predicate on the specified instruction.
virtual bool testImmPredicate_I64(unsigned, int64_t) const
Indicates the end of the variable-length MergeInsnID list in a GIR_MergeMemOperands opcode...
Render complex operands to the specified instruction.
#define I(x, y, z)
Definition: MD5.cpp:58
Build a new instruction.
Check the operand is a specific integer.
Mutate an instruction.
Render a G_FCONSTANT operator as a sign-extended immediate.
LLVM Value Representation.
Definition: Value.h:73
Render a G_CONSTANT operator as a sign-extended immediate.
Check the type of a pointer to any address space.
Begin a try-block to attempt a match and jump to OnFail if it is unsuccessful.
Check the register bank for the specified operand.
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 specified operand is an MBB.
Add an implicit register def to the specified instruction.
Check a memory operation has the specified atomic ordering.