LLVM  6.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"
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 LLT;
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  /// Record the specified instruction
85  /// - NewInsnID - Instruction ID to define
86  /// - InsnID - Instruction ID
87  /// - OpIdx - Operand index
89 
90  /// Check the feature bits
91  /// - Expected features
93 
94  /// Check the opcode on the specified instruction
95  /// - InsnID - Instruction ID
96  /// - Expected opcode
98  /// Check the instruction has the right number of operands
99  /// - InsnID - Instruction ID
100  /// - Expected number of operands
102  /// Check an immediate predicate on the specified instruction
103  /// - InsnID - Instruction ID
104  /// - The predicate to test
106  /// Check an immediate predicate on the specified instruction via an APInt.
107  /// - InsnID - Instruction ID
108  /// - The predicate to test
110  /// Check a floating point immediate predicate on the specified instruction.
111  /// - InsnID - Instruction ID
112  /// - The predicate to test
114  /// Check a memory operation is non-atomic.
115  /// - InsnID - Instruction ID
117 
118  /// Check the type for the specified operand
119  /// - InsnID - Instruction ID
120  /// - OpIdx - Operand index
121  /// - Expected type
123  /// Check the type of a pointer to any address space.
124  /// - InsnID - Instruction ID
125  /// - OpIdx - Operand index
126  /// - SizeInBits - The size of the pointer value in bits.
128  /// Check the register bank for the specified operand
129  /// - InsnID - Instruction ID
130  /// - OpIdx - Operand index
131  /// - Expected register bank (specified as a register class)
133  /// Check the operand matches a complex predicate
134  /// - InsnID - Instruction ID
135  /// - OpIdx - Operand index
136  /// - RendererID - The renderer to hold the result
137  /// - Complex predicate ID
139  /// Check the operand is a specific integer
140  /// - InsnID - Instruction ID
141  /// - OpIdx - Operand index
142  /// - Expected integer
144  /// Check the operand is a specific literal integer (i.e. MO.isImm() or
145  /// MO.isCImm() is true).
146  /// - InsnID - Instruction ID
147  /// - OpIdx - Operand index
148  /// - Expected integer
150  /// Check the operand is a specific intrinsic ID
151  /// - InsnID - Instruction ID
152  /// - OpIdx - Operand index
153  /// - Expected Intrinsic ID
155  /// Check the specified operand is an MBB
156  /// - InsnID - Instruction ID
157  /// - OpIdx - Operand index
159 
160  /// Check if the specified operand is safe to fold into the current
161  /// instruction.
162  /// - InsnID - Instruction ID
164 
165  /// Check the specified operands are identical.
166  /// - InsnID - Instruction ID
167  /// - OpIdx - Operand index
168  /// - OtherInsnID - Other instruction ID
169  /// - OtherOpIdx - Other operand index
171 
172  /// Fail the current try-block, or completely fail to match if there is no
173  /// current try-block.
175 
176  //=== Renderers ===
177 
178  /// Mutate an instruction
179  /// - NewInsnID - Instruction ID to define
180  /// - OldInsnID - Instruction ID to mutate
181  /// - NewOpcode - The new opcode to use
183  /// Build a new instruction
184  /// - InsnID - Instruction ID to define
185  /// - Opcode - The new opcode to use
187 
188  /// Copy an operand to the specified instruction
189  /// - NewInsnID - Instruction ID to modify
190  /// - OldInsnID - Instruction ID to copy from
191  /// - OpIdx - The operand to copy
193  /// Copy an operand to the specified instruction or add a zero register if the
194  /// operand is a zero immediate.
195  /// - NewInsnID - Instruction ID to modify
196  /// - OldInsnID - Instruction ID to copy from
197  /// - OpIdx - The operand to copy
198  /// - ZeroReg - The zero register to use
200  /// Copy an operand to the specified instruction
201  /// - NewInsnID - Instruction ID to modify
202  /// - OldInsnID - Instruction ID to copy from
203  /// - OpIdx - The operand to copy
204  /// - SubRegIdx - The subregister to copy
206  /// Add an implicit register def to the specified instruction
207  /// - InsnID - Instruction ID to modify
208  /// - RegNum - The register to add
210  /// Add an implicit register use to the specified instruction
211  /// - InsnID - Instruction ID to modify
212  /// - RegNum - The register to add
214  /// Add an register to the specified instruction
215  /// - InsnID - Instruction ID to modify
216  /// - RegNum - The register to add
218  /// Add a a temporary register to the specified instruction
219  /// - InsnID - Instruction ID to modify
220  /// - TempRegID - The temporary register ID to add
222  /// Add an immediate to the specified instruction
223  /// - InsnID - Instruction ID to modify
224  /// - Imm - The immediate to add
226  /// Render complex operands to the specified instruction
227  /// - InsnID - Instruction ID to modify
228  /// - RendererID - The renderer to call
230  /// Render sub-operands of complex operands to the specified instruction
231  /// - InsnID - Instruction ID to modify
232  /// - RendererID - The renderer to call
233  /// - RenderOpID - The suboperand to render.
235 
236  /// Render a G_CONSTANT operator as a sign-extended immediate.
237  /// - NewInsnID - Instruction ID to modify
238  /// - OldInsnID - Instruction ID to copy from
239  /// The operand index is implicitly 1.
241 
242  /// Constrain an instruction operand to a register class.
243  /// - InsnID - Instruction ID to modify
244  /// - OpIdx - Operand index
245  /// - RCEnum - Register class enumeration value
247  /// Constrain an instructions operands according to the instruction
248  /// description.
249  /// - InsnID - Instruction ID to modify
251  /// Merge all memory operands into instruction.
252  /// - InsnID - Instruction ID to modify
253  /// - MergeInsnID... - One or more Instruction ID to merge into the result.
254  /// - GIU_MergeMemOperands_EndOfList - Terminates the list of instructions to
255  /// merge.
257  /// Erase from parent.
258  /// - InsnID - Instruction ID to erase
260  /// Create a new temporary register that's not constrained.
261  /// - TempRegID - The temporary register ID to initialize.
262  /// - Expected type
264 
265  /// A successful emission
267 
268  /// Increment the rule coverage counter.
269  /// - RuleID - The ID of the rule that was covered.
271 };
272 
273 enum {
274  /// Indicates the end of the variable-length MergeInsnID list in a
275  /// GIR_MergeMemOperands opcode.
277 };
278 
279 /// Provides the logic to select generic machine instructions.
281 public:
282  using I64ImmediatePredicateFn = bool (*)(int64_t);
283  using APIntImmediatePredicateFn = bool (*)(const APInt &);
285 
286  virtual ~InstructionSelector() = default;
287 
288  /// Select the (possibly generic) instruction \p I to only use target-specific
289  /// opcodes. It is OK to insert multiple instructions, but they cannot be
290  /// generic pre-isel instructions.
291  ///
292  /// \returns whether selection succeeded.
293  /// \pre I.getParent() && I.getParent()->getParent()
294  /// \post
295  /// if returns true:
296  /// for I in all mutated/inserted instructions:
297  /// !isPreISelGenericOpcode(I.getOpcode())
298  virtual bool select(MachineInstr &I, CodeGenCoverage &CoverageInfo) const = 0;
299 
300 protected:
301  using ComplexRendererFns =
305 
306  struct MatcherState {
307  std::vector<ComplexRendererFns::value_type> Renderers;
310 
311  MatcherState(unsigned MaxRenderers);
312  };
313 
314 public:
315  template <class PredicateBitset, class ComplexMatcherMemFn>
316  struct MatcherInfoTy {
317  const LLT *TypeObjects;
318  const PredicateBitset *FeatureBitsets;
322  const ComplexMatcherMemFn *ComplexPredicates;
323  };
324 
325 protected:
327 
328  /// Execute a given matcher table and return true if the match was successful
329  /// and false otherwise.
330  template <class TgtInstructionSelector, class PredicateBitset,
331  class ComplexMatcherMemFn>
332  bool executeMatchTable(
333  TgtInstructionSelector &ISel, NewMIVector &OutMIs, MatcherState &State,
335  const int64_t *MatchTable, const TargetInstrInfo &TII,
337  const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures,
338  CodeGenCoverage &CoverageInfo) const;
339 
340  /// Constrain a register operand of an instruction \p I to a specified
341  /// register class. This could involve inserting COPYs before (for uses) or
342  /// after (for defs) and may replace the operand of \p I.
343  /// \returns whether operand regclass constraining succeeded.
344  bool constrainOperandRegToRegClass(MachineInstr &I, unsigned OpIdx,
345  const TargetRegisterClass &RC,
346  const TargetInstrInfo &TII,
347  const TargetRegisterInfo &TRI,
348  const RegisterBankInfo &RBI) const;
349 
350  /// Mutate the newly-selected instruction \p I to constrain its (possibly
351  /// generic) virtual register operands to the instruction's register class.
352  /// This could involve inserting COPYs before (for uses) or after (for defs).
353  /// This requires the number of operands to match the instruction description.
354  /// \returns whether operand regclass constraining succeeded.
355  ///
356  // FIXME: Not all instructions have the same number of operands. We should
357  // probably expose a constrain helper per operand and let the target selector
358  // constrain individual registers, like fast-isel.
359  bool constrainSelectedInstRegOperands(MachineInstr &I,
360  const TargetInstrInfo &TII,
361  const TargetRegisterInfo &TRI,
362  const RegisterBankInfo &RBI) const;
363 
364  bool isOperandImmEqual(const MachineOperand &MO, int64_t Value,
365  const MachineRegisterInfo &MRI) const;
366 
367  /// Return true if the specified operand is a G_GEP with a G_CONSTANT on the
368  /// right-hand side. GlobalISel's separation of pointer and integer types
369  /// means that we don't need to worry about G_OR with equivalent semantics.
370  bool isBaseWithConstantOffset(const MachineOperand &Root,
371  const MachineRegisterInfo &MRI) const;
372 
373  /// Return true if MI can obviously be folded into IntoMI.
374  /// MI and IntoMI do not need to be in the same basic blocks, but MI must
375  /// preceed IntoMI.
376  bool isObviouslySafeToFold(MachineInstr &MI, MachineInstr &IntoMI) const;
377 };
378 
379 } // end namespace llvm
380 
381 #endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
Check the type of a pointer to any address space.
Fail the current try-block, or completely fail to match if there is no current try-block.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Check if the specified operand is safe to fold into the current instruction.
std::vector< ComplexRendererFns::value_type > Renderers
Check the specified operands are identical.
Check the instruction has the right number of operands.
PredicateBitsetImpl(std::initializer_list< unsigned > Init)
Check the register bank for the specified operand.
Copy an operand to the specified instruction.
Constrain an instructions operands according to the instruction description.
Copy an operand to the specified instruction.
Indicates the end of the variable-length MergeInsnID list in a GIR_MergeMemOperands opcode...
Render complex operands to the specified instruction.
Render sub-operands of complex operands to the specified instruction.
Holds all the information related to register banks.
Definition: BitVector.h:920
const ComplexMatcherMemFn * ComplexPredicates
const HexagonInstrInfo * TII
Add an register to the specified instruction.
Record the specified instruction.
const APFloatImmediatePredicateFn * APFloatImmPredicateFns
DenseMap< unsigned, unsigned > TempRegisters
Check the operand is a specific integer.
Add an implicit register def to the specified instruction.
Render a G_CONSTANT operator as a sign-extended immediate.
Merge all memory operands into instruction.
Check the opcode on the specified instruction.
Copy an operand to the specified instruction or add a zero register if the operand is a zero immediat...
const I64ImmediatePredicateFn * I64ImmPredicateFns
Check the feature bits.
Mutate an instruction.
TargetInstrInfo - Interface to description of machine instruction set.
Add a a temporary register to the specified instruction.
Container class for CodeGen predicate results.
Check the operand is a specific literal integer (i.e.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
Check the specified operand is an MBB.
bool(*)(const APFloat &) APFloatImmediatePredicateFn
Check an immediate predicate on the specified instruction.
bool(*)(const APInt &) APIntImmediatePredicateFn
Constrain an instruction operand to a register class.
Increment the rule coverage counter.
Add an immediate to the specified instruction.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Check a memory operation is non-atomic.
Add an implicit register use to the specified instruction.
Build a new instruction.
A successful emission.
Check an immediate predicate on the specified instruction via an APInt.
MachineOperand class - Representation of each machine instruction operand.
Check the type for the specified operand.
Check a floating point immediate predicate on the specified instruction.
Begin a try-block to attempt a match and jump to OnFail if it is unsuccessful.
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.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
const APIntImmediatePredicateFn * APIntImmPredicateFns
Check the operand is a specific intrinsic ID.
Provides the logic to select generic machine instructions.
Representation of each machine instruction.
Definition: MachineInstr.h:59
Check the operand matches a complex predicate.
bool(*)(int64_t) I64ImmediatePredicateFn
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM Value Representation.
Definition: Value.h:73
Create a new temporary register that&#39;s not constrained.
IRTranslator LLVM IR MI
PredicateBitsetImpl(const std::bitset< MaxPredicates > &B)