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