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/SmallVector.h"
20#include "llvm/ADT/Optional.h"
21#include <bitset>
22#include <cstddef>
23#include <cstdint>
24#include <functional>
25#include <initializer_list>
26#include <vector>
27
28namespace llvm {
29
30class APInt;
31class APFloat;
32class LLT;
33class MachineInstr;
34class MachineInstrBuilder;
35class MachineOperand;
36class MachineRegisterInfo;
37class RegisterBankInfo;
38class TargetInstrInfo;
39class TargetRegisterClass;
40class TargetRegisterInfo;
41
42/// Container class for CodeGen predicate results.
43/// This is convenient because std::bitset does not have a constructor
44/// with an initializer list of set bits.
45///
46/// Each InstructionSelector subclass should define a PredicateBitset class
47/// with:
48///   const unsigned MAX_SUBTARGET_PREDICATES = 192;
49///   using PredicateBitset = PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;
50/// and updating the constant to suit the target. Tablegen provides a suitable
51/// definition for the predicates in use in <Target>GenGlobalISel.inc when
52/// GET_GLOBALISEL_PREDICATE_BITSET is defined.
53template <std::size_t MaxPredicates>
54class PredicateBitsetImpl : public std::bitset<MaxPredicates> {
55public:
56  // Cannot inherit constructors because it's not supported by VC++..
57  PredicateBitsetImpl() = default;
58
59  PredicateBitsetImpl(const std::bitset<MaxPredicates> &B)
60      : std::bitset<MaxPredicates>(B) {}
61
62  PredicateBitsetImpl(std::initializer_list<unsigned> Init) {
63    for (auto I : Init)
64      std::bitset<MaxPredicates>::set(I);
65  }
66};
67
68enum {
69  /// Begin a try-block to attempt a match and jump to OnFail if it is
70  /// unsuccessful.
71  /// - OnFail - The MatchTable entry at which to resume if the match fails.
72  ///
73  /// FIXME: This ought to take an argument indicating the number of try-blocks
74  ///        to exit on failure. It's usually one but the last match attempt of
75  ///        a block will need more. The (implemented) alternative is to tack a
76  ///        GIM_Reject on the end of each try-block which is simpler but
77  ///        requires an extra opcode and iteration in the interpreter on each
78  ///        failed match.
79  GIM_Try,
80
81  /// Record the specified instruction
82  /// - NewInsnID - Instruction ID to define
83  /// - InsnID - Instruction ID
84  /// - OpIdx - Operand index
85  GIM_RecordInsn,
86
87  /// Check the feature bits
88  /// - Expected features
89  GIM_CheckFeatures,
90
91  /// Check the opcode on the specified instruction
92  /// - InsnID - Instruction ID
93  /// - Expected opcode
94  GIM_CheckOpcode,
95  /// Check the instruction has the right number of operands
96  /// - InsnID - Instruction ID
97  /// - Expected number of operands
98  GIM_CheckNumOperands,
99  /// Check an immediate predicate on the specified instruction
100  /// - InsnID - Instruction ID
101  /// - The predicate to test
102  GIM_CheckI64ImmPredicate,
103  /// Check an immediate predicate on the specified instruction via an APInt.
104  /// - InsnID - Instruction ID
105  /// - The predicate to test
106  GIM_CheckAPIntImmPredicate,
107  /// Check a floating point immediate predicate on the specified instruction.
108  /// - InsnID - Instruction ID
109  /// - The predicate to test
110  GIM_CheckAPFloatImmPredicate,
111  /// Check a memory operation is non-atomic.
112  /// - InsnID - Instruction ID
113  GIM_CheckNonAtomic,
114
115  /// Check the type for the specified operand
116  /// - InsnID - Instruction ID
117  /// - OpIdx - Operand index
118  /// - Expected type
119  GIM_CheckType,
120  /// Check the type of a pointer to any address space.
121  /// - InsnID - Instruction ID
122  /// - OpIdx - Operand index
123  /// - SizeInBits - The size of the pointer value in bits.
124  GIM_CheckPointerToAny,
125  /// Check the register bank for the specified operand
126  /// - InsnID - Instruction ID
127  /// - OpIdx - Operand index
128  /// - Expected register bank (specified as a register class)
129  GIM_CheckRegBankForClass,
130  /// Check the operand matches a complex predicate
131  /// - InsnID - Instruction ID
132  /// - OpIdx - Operand index
133  /// - RendererID - The renderer to hold the result
134  /// - Complex predicate ID
135  GIM_CheckComplexPattern,
136  /// Check the operand is a specific integer
137  /// - InsnID - Instruction ID
138  /// - OpIdx - Operand index
139  /// - Expected integer
140  GIM_CheckConstantInt,
141  /// Check the operand is a specific literal integer (i.e. MO.isImm() or
142  /// MO.isCImm() is true).
143  /// - InsnID - Instruction ID
144  /// - OpIdx - Operand index
145  /// - Expected integer
146  GIM_CheckLiteralInt,
147  /// Check the operand is a specific intrinsic ID
148  /// - InsnID - Instruction ID
149  /// - OpIdx - Operand index
150  /// - Expected Intrinsic ID
151  GIM_CheckIntrinsicID,
152  /// Check the specified operand is an MBB
153  /// - InsnID - Instruction ID
154  /// - OpIdx - Operand index
155  GIM_CheckIsMBB,
156
157  /// Check if the specified operand is safe to fold into the current
158  /// instruction.
159  /// - InsnID - Instruction ID
160  GIM_CheckIsSafeToFold,
161
162  /// Check the specified operands are identical.
163  /// - InsnID - Instruction ID
164  /// - OpIdx - Operand index
165  /// - OtherInsnID - Other instruction ID
166  /// - OtherOpIdx - Other operand index
167  GIM_CheckIsSameOperand,
168
169  /// Fail the current try-block, or completely fail to match if there is no
170  /// current try-block.
171  GIM_Reject,
172
173  //=== Renderers ===
174
175  /// Mutate an instruction
176  /// - NewInsnID - Instruction ID to define
177  /// - OldInsnID - Instruction ID to mutate
178  /// - NewOpcode - The new opcode to use
179  GIR_MutateOpcode,
180  /// Build a new instruction
181  /// - InsnID - Instruction ID to define
182  /// - Opcode - The new opcode to use
183  GIR_BuildMI,
184
185  /// Copy an operand to the specified instruction
186  /// - NewInsnID - Instruction ID to modify
187  /// - OldInsnID - Instruction ID to copy from
188  /// - OpIdx - The operand to copy
189  GIR_Copy,
190  /// Copy an operand to the specified instruction
191  /// - NewInsnID - Instruction ID to modify
192  /// - OldInsnID - Instruction ID to copy from
193  /// - OpIdx - The operand to copy
194  /// - SubRegIdx - The subregister to copy
195  GIR_CopySubReg,
196  /// Add an implicit register def to the specified instruction
197  /// - InsnID - Instruction ID to modify
198  /// - RegNum - The register to add
199  GIR_AddImplicitDef,
200  /// Add an implicit register use to the specified instruction
201  /// - InsnID - Instruction ID to modify
202  /// - RegNum - The register to add
203  GIR_AddImplicitUse,
204  /// Add an register to the specified instruction
205  /// - InsnID - Instruction ID to modify
206  /// - RegNum - The register to add
207  GIR_AddRegister,
208  /// Add an immediate to the specified instruction
209  /// - InsnID - Instruction ID to modify
210  /// - Imm - The immediate to add
211  GIR_AddImm,
212  /// Render complex operands to the specified instruction
213  /// - InsnID - Instruction ID to modify
214  /// - RendererID - The renderer to call
215  GIR_ComplexRenderer,
216  /// Render sub-operands of complex operands to the specified instruction
217  /// - InsnID - Instruction ID to modify
218  /// - RendererID - The renderer to call
219  /// - RenderOpID - The suboperand to render.
220  GIR_ComplexSubOperandRenderer,
221
222  /// Render a G_CONSTANT operator as a sign-extended immediate.
223  /// - NewInsnID - Instruction ID to modify
224  /// - OldInsnID - Instruction ID to copy from
225  /// The operand index is implicitly 1.
226  GIR_CopyConstantAsSImm,
227
228  /// Constrain an instruction operand to a register class.
229  /// - InsnID - Instruction ID to modify
230  /// - OpIdx - Operand index
231  /// - RCEnum - Register class enumeration value
232  GIR_ConstrainOperandRC,
233  /// Constrain an instructions operands according to the instruction
234  /// description.
235  /// - InsnID - Instruction ID to modify
236  GIR_ConstrainSelectedInstOperands,
237  /// Merge all memory operands into instruction.
238  /// - InsnID - Instruction ID to modify
239  /// - MergeInsnID... - One or more Instruction ID to merge into the result.
240  /// - GIU_MergeMemOperands_EndOfList - Terminates the list of instructions to
241  ///                                    merge.
242  GIR_MergeMemOperands,
243  /// Erase from parent.
244  /// - InsnID - Instruction ID to erase
245  GIR_EraseFromParent,
246
247  /// A successful emission
248  GIR_Done,
249};
250
251enum {
252  /// Indicates the end of the variable-length MergeInsnID list in a
253  /// GIR_MergeMemOperands opcode.
254  GIU_MergeMemOperands_EndOfList = -1,
255};
256
257/// Provides the logic to select generic machine instructions.
258class InstructionSelector {
259public:
260  using I64ImmediatePredicateFn = bool (*)(int64_t);
261  using APIntImmediatePredicateFn = bool (*)(const APInt &);
262  using APFloatImmediatePredicateFn = bool (*)(const APFloat &);
263
264  virtual ~InstructionSelector() = default;
265
266  /// Select the (possibly generic) instruction \p I to only use target-specific
267  /// opcodes. It is OK to insert multiple instructions, but they cannot be
268  /// generic pre-isel instructions.
269  ///
270  /// \returns whether selection succeeded.
271  /// \pre  I.getParent() && I.getParent()->getParent()
272  /// \post
273  ///   if returns true:
274  ///     for I in all mutated/inserted instructions:
275  ///       !isPreISelGenericOpcode(I.getOpcode())
276  virtual bool select(MachineInstr &I) const = 0;
277
278protected:
279  using ComplexRendererFn =
280      Optional<SmallVector<std::function<void(MachineInstrBuilder &)>, 4>>;
281  using RecordedMIVector = SmallVector<MachineInstr *, 4>;
282  using NewMIVector = SmallVector<MachineInstrBuilder, 4>;
283
284  struct MatcherState {
285    std::vector<ComplexRendererFn::value_type> Renderers;
286    RecordedMIVector MIs;
287
288    MatcherState(unsigned MaxRenderers);
289  };
290
291public:
292  template <class PredicateBitset, class ComplexMatcherMemFn>
293  struct MatcherInfoTy {
294    const LLT *TypeObjects;
295    const PredicateBitset *FeatureBitsets;
296    const I64ImmediatePredicateFn *I64ImmPredicateFns;
297    const APIntImmediatePredicateFn *APIntImmPredicateFns;
298    const APFloatImmediatePredicateFn *APFloatImmPredicateFns;
299    const ComplexMatcherMemFn *ComplexPredicates;
300  };
301
302protected:
303  InstructionSelector();
304
305  /// Execute a given matcher table and return true if the match was successful
306  /// and false otherwise.
307  template <class TgtInstructionSelector, class PredicateBitset,
308            class ComplexMatcherMemFn>
309  bool executeMatchTable(
310      TgtInstructionSelector &ISel, NewMIVector &OutMIs, MatcherState &State,
311      const MatcherInfoTy<PredicateBitset, ComplexMatcherMemFn> &MatcherInfo,
312      const int64_t *MatchTable, const TargetInstrInfo &TII,
313      MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
314      const RegisterBankInfo &RBI,
315      const PredicateBitset &AvailableFeatures) const;
316
317  /// Constrain a register operand of an instruction \p I to a specified
318  /// register class. This could involve inserting COPYs before (for uses) or
319  /// after (for defs) and may replace the operand of \p I.
320  /// \returns whether operand regclass constraining succeeded.
321  bool constrainOperandRegToRegClass(MachineInstr &I, unsigned OpIdx,
322                                     const TargetRegisterClass &RC,
323                                     const TargetInstrInfo &TII,
324                                     const TargetRegisterInfo &TRI,
325                                     const RegisterBankInfo &RBI) const;
326
327  /// Mutate the newly-selected instruction \p I to constrain its (possibly
328  /// generic) virtual register operands to the instruction's register class.
329  /// This could involve inserting COPYs before (for uses) or after (for defs).
330  /// This requires the number of operands to match the instruction description.
331  /// \returns whether operand regclass constraining succeeded.
332  ///
333  // FIXME: Not all instructions have the same number of operands. We should
334  // probably expose a constrain helper per operand and let the target selector
335  // constrain individual registers, like fast-isel.
336  bool constrainSelectedInstRegOperands(MachineInstr &I,
337                                        const TargetInstrInfo &TII,
338                                        const TargetRegisterInfo &TRI,
339                                        const RegisterBankInfo &RBI) const;
340
341  bool isOperandImmEqual(const MachineOperand &MO, int64_t Value,
342                         const MachineRegisterInfo &MRI) const;
343
344  /// Return true if the specified operand is a G_GEP with a G_CONSTANT on the
345  /// right-hand side. GlobalISel's separation of pointer and integer types
346  /// means that we don't need to worry about G_OR with equivalent semantics.
347  bool isBaseWithConstantOffset(const MachineOperand &Root,
348                                const MachineRegisterInfo &MRI) const;
349
350  bool isObviouslySafeToFold(MachineInstr &MI) const;
351};
352
353} // end namespace llvm
354
355#endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
356