• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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"
22 #include "llvm/Support/CodeGenCoverage.h"
23 #include "llvm/Support/LowLevelTypeImpl.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 
PredicateBitsetImpl(const std::bitset<MaxPredicates> & B)62   PredicateBitsetImpl(const std::bitset<MaxPredicates> &B)
63       : std::bitset<MaxPredicates>(B) {}
64 
PredicateBitsetImpl(std::initializer_list<unsigned> Init)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.
82   GIM_Try,
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
90   GIM_SwitchOpcode,
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
99   GIM_SwitchType,
100 
101   /// Record the specified instruction
102   /// - NewInsnID - Instruction ID to define
103   /// - InsnID - Instruction ID
104   /// - OpIdx - Operand index
105   GIM_RecordInsn,
106 
107   /// Check the feature bits
108   /// - Expected features
109   GIM_CheckFeatures,
110 
111   /// Check the opcode on the specified instruction
112   /// - InsnID - Instruction ID
113   /// - Expected opcode
114   GIM_CheckOpcode,
115   /// Check the instruction has the right number of operands
116   /// - InsnID - Instruction ID
117   /// - Expected number of operands
118   GIM_CheckNumOperands,
119   /// Check an immediate predicate on the specified instruction
120   /// - InsnID - Instruction ID
121   /// - The predicate to test
122   GIM_CheckI64ImmPredicate,
123   /// Check an immediate predicate on the specified instruction via an APInt.
124   /// - InsnID - Instruction ID
125   /// - The predicate to test
126   GIM_CheckAPIntImmPredicate,
127   /// Check a floating point immediate predicate on the specified instruction.
128   /// - InsnID - Instruction ID
129   /// - The predicate to test
130   GIM_CheckAPFloatImmPredicate,
131   /// Check a memory operation has the specified atomic ordering.
132   /// - InsnID - Instruction ID
133   /// - Ordering - The AtomicOrdering value
134   GIM_CheckAtomicOrdering,
135   GIM_CheckAtomicOrderingOrStrongerThan,
136   GIM_CheckAtomicOrderingWeakerThan,
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
141   GIM_CheckMemorySizeEqualTo,
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
147   GIM_CheckMemorySizeEqualToLLT,
148   GIM_CheckMemorySizeLessThanLLT,
149   GIM_CheckMemorySizeGreaterThanLLT,
150   /// Check a generic C++ instruction predicate
151   /// - InsnID - Instruction ID
152   /// - PredicateID - The ID of the predicate function to call
153   GIM_CheckCxxInsnPredicate,
154 
155   /// Check the type for the specified operand
156   /// - InsnID - Instruction ID
157   /// - OpIdx - Operand index
158   /// - Expected type
159   GIM_CheckType,
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.
164   GIM_CheckPointerToAny,
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)
169   GIM_CheckRegBankForClass,
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
176   GIM_CheckComplexPattern,
177 
178   /// Check the operand is a specific integer
179   /// - InsnID - Instruction ID
180   /// - OpIdx - Operand index
181   /// - Expected integer
182   GIM_CheckConstantInt,
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
188   GIM_CheckLiteralInt,
189   /// Check the operand is a specific intrinsic ID
190   /// - InsnID - Instruction ID
191   /// - OpIdx - Operand index
192   /// - Expected Intrinsic ID
193   GIM_CheckIntrinsicID,
194 
195   /// Check the specified operand is an MBB
196   /// - InsnID - Instruction ID
197   /// - OpIdx - Operand index
198   GIM_CheckIsMBB,
199 
200   /// Check if the specified operand is safe to fold into the current
201   /// instruction.
202   /// - InsnID - Instruction ID
203   GIM_CheckIsSafeToFold,
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
210   GIM_CheckIsSameOperand,
211 
212   /// Fail the current try-block, or completely fail to match if there is no
213   /// current try-block.
214   GIM_Reject,
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
222   GIR_MutateOpcode,
223 
224   /// Build a new instruction
225   /// - InsnID - Instruction ID to define
226   /// - Opcode - The new opcode to use
227   GIR_BuildMI,
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
233   GIR_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
241   GIR_CopyOrAddZeroReg,
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
247   GIR_CopySubReg,
248 
249   /// Add an implicit register def to the specified instruction
250   /// - InsnID - Instruction ID to modify
251   /// - RegNum - The register to add
252   GIR_AddImplicitDef,
253   /// Add an implicit register use to the specified instruction
254   /// - InsnID - Instruction ID to modify
255   /// - RegNum - The register to add
256   GIR_AddImplicitUse,
257   /// Add an register to the specified instruction
258   /// - InsnID - Instruction ID to modify
259   /// - RegNum - The register to add
260   GIR_AddRegister,
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
266   GIR_AddTempRegister,
267 
268   /// Add an immediate to the specified instruction
269   /// - InsnID - Instruction ID to modify
270   /// - Imm - The immediate to add
271   GIR_AddImm,
272   /// Render complex operands to the specified instruction
273   /// - InsnID - Instruction ID to modify
274   /// - RendererID - The renderer to call
275   GIR_ComplexRenderer,
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.
281   GIR_ComplexSubOperandRenderer,
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
286   GIR_CustomRenderer,
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.
292   GIR_CopyConstantAsSImm,
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.
298   GIR_CopyFConstantAsFPImm,
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
304   GIR_ConstrainOperandRC,
305 
306   /// Constrain an instructions operands according to the instruction
307   /// description.
308   /// - InsnID - Instruction ID to modify
309   GIR_ConstrainSelectedInstOperands,
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.
316   GIR_MergeMemOperands,
317 
318   /// Erase from parent.
319   /// - InsnID - Instruction ID to erase
320   GIR_EraseFromParent,
321 
322   /// Create a new temporary register that's not constrained.
323   /// - TempRegID - The temporary register ID to initialize.
324   /// - Expected type
325   GIR_MakeTempReg,
326 
327   /// A successful emission
328   GIR_Done,
329 
330   /// Increment the rule coverage counter.
331   /// - RuleID - The ID of the rule that was covered.
332   GIR_Coverage,
333 
334   /// Keeping track of the number of the GI opcodes. Must be the last entry.
335   GIU_NumOpcodes,
336 };
337 
338 enum {
339   /// Indicates the end of the variable-length MergeInsnID list in a
340   /// GIR_MergeMemOperands opcode.
341   GIU_MergeMemOperands_EndOfList = -1,
342 };
343 
344 /// Provides the logic to select generic machine instructions.
345 class InstructionSelector {
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 =
363       Optional<SmallVector<std::function<void(MachineInstrBuilder &)>, 4>>;
364   using RecordedMIVector = SmallVector<MachineInstr *, 4>;
365   using NewMIVector = SmallVector<MachineInstrBuilder, 4>;
366 
367   struct MatcherState {
368     std::vector<ComplexRendererFns::value_type> Renderers;
369     RecordedMIVector MIs;
370     DenseMap<unsigned, unsigned> TempRegisters;
371 
372     MatcherState(unsigned MaxRenderers);
373   };
374 
375 public:
376   template <class PredicateBitset, class ComplexMatcherMemFn,
377             class CustomRendererFn>
378   struct ISelInfoTy {
ISelInfoTyISelInfoTy379     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 
396     SmallDenseMap<LLT, unsigned, 64> TypeIDMap;
397   };
398 
399 protected:
400   InstructionSelector();
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,
408       const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, CustomRendererFn>
409           &ISelInfo,
410       const int64_t *MatchTable, const TargetInstrInfo &TII,
411       MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
412       const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures,
413       CodeGenCoverage &CoverageInfo) const;
414 
getMatchTable()415   virtual const int64_t *getMatchTable() const {
416     llvm_unreachable("Should have been overridden by tablegen if used");
417   }
418 
testImmPredicate_I64(unsigned,int64_t)419   virtual bool testImmPredicate_I64(unsigned, int64_t) const {
420     llvm_unreachable(
421         "Subclasses must override this with a tablegen-erated function");
422   }
testImmPredicate_APInt(unsigned,const APInt &)423   virtual bool testImmPredicate_APInt(unsigned, const APInt &) const {
424     llvm_unreachable(
425         "Subclasses must override this with a tablegen-erated function");
426   }
testImmPredicate_APFloat(unsigned,const APFloat &)427   virtual bool testImmPredicate_APFloat(unsigned, const APFloat &) const {
428     llvm_unreachable(
429         "Subclasses must override this with a tablegen-erated function");
430   }
testMIPredicate_MI(unsigned,const MachineInstr &)431   virtual bool testMIPredicate_MI(unsigned, const MachineInstr &) const {
432     llvm_unreachable(
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
464