include/llvm/CodeGen/GlobalISel/InstructionSelector.h

   1 //===- llvm/CodeGen/GlobalISel/InstructionSelector.h ------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 /// \file This file declares the API for the instruction selector.
  10 /// This class is responsible for selecting machine instructions.
  11 /// It's implemented by the target. It's used by the InstructionSelect pass.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
  16 #define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
  17
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/Optional.h"
  20 #include "llvm/ADT/SmallVector.h"
  21 #include "llvm/Support/CodeGenCoverage.h"
  22 #include "llvm/Support/LowLevelTypeImpl.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 GISelKnownBits;
  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.
  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
 143   /// Check the address space of the memory access for the given machine memory
 144   /// operand.
 145   /// - InsnID - Instruction ID
 146   /// - MMOIdx - MMO index
 147   /// - NumAddrSpace - Number of valid address spaces
 148   /// - AddrSpaceN - An allowed space of the memory access
 149   /// - AddrSpaceN+1 ...
 150   GIM_CheckMemoryAddressSpace,
 151
 152   /// Check the minimum alignment of the memory access for the given machine
 153   /// memory operand.
 154   /// - InsnID - Instruction ID
 155   /// - MMOIdx - MMO index
 156   /// - MinAlign - Minimum acceptable alignment
 157   GIM_CheckMemoryAlignment,
 158
 159   /// Check the size of the memory access for the given machine memory operand
 160   /// against the size of an operand.
 161   /// - InsnID - Instruction ID
 162   /// - MMOIdx - MMO index
 163   /// - OpIdx - The operand index to compare the MMO against
 164   GIM_CheckMemorySizeEqualToLLT,
 165   GIM_CheckMemorySizeLessThanLLT,
 166   GIM_CheckMemorySizeGreaterThanLLT,
 167   /// Check a generic C++ instruction predicate
 168   /// - InsnID - Instruction ID
 169   /// - PredicateID - The ID of the predicate function to call
 170   GIM_CheckCxxInsnPredicate,
 171
 172   /// Check the type for the specified operand
 173   /// - InsnID - Instruction ID
 174   /// - OpIdx - Operand index
 175   /// - Expected type
 176   GIM_CheckType,
 177   /// Check the type of a pointer to any address space.
 178   /// - InsnID - Instruction ID
 179   /// - OpIdx - Operand index
 180   /// - SizeInBits - The size of the pointer value in bits.
 181   GIM_CheckPointerToAny,
 182   /// Check the register bank for the specified operand
 183   /// - InsnID - Instruction ID
 184   /// - OpIdx - Operand index
 185   /// - Expected register bank (specified as a register class)
 186   GIM_CheckRegBankForClass,
 187
 188   /// Check the operand matches a complex predicate
 189   /// - InsnID - Instruction ID
 190   /// - OpIdx - Operand index
 191   /// - RendererID - The renderer to hold the result
 192   /// - Complex predicate ID
 193   GIM_CheckComplexPattern,
 194
 195   /// Check the operand is a specific integer
 196   /// - InsnID - Instruction ID
 197   /// - OpIdx - Operand index
 198   /// - Expected integer
 199   GIM_CheckConstantInt,
 200   /// Check the operand is a specific literal integer (i.e. MO.isImm() or
 201   /// MO.isCImm() is true).
 202   /// - InsnID - Instruction ID
 203   /// - OpIdx - Operand index
 204   /// - Expected integer
 205   GIM_CheckLiteralInt,
 206   /// Check the operand is a specific intrinsic ID
 207   /// - InsnID - Instruction ID
 208   /// - OpIdx - Operand index
 209   /// - Expected Intrinsic ID
 210   GIM_CheckIntrinsicID,
 211
 212   /// Check the operand is a specific predicate
 213   /// - InsnID - Instruction ID
 214   /// - OpIdx - Operand index
 215   /// - Expected predicate
 216   GIM_CheckCmpPredicate,
 217
 218   /// Check the specified operand is an MBB
 219   /// - InsnID - Instruction ID
 220   /// - OpIdx - Operand index
 221   GIM_CheckIsMBB,
 222
 223   /// Check the specified operand is an Imm
 224   /// - InsnID - Instruction ID
 225   /// - OpIdx - Operand index
 226   GIM_CheckIsImm,
 227
 228   /// Check if the specified operand is safe to fold into the current
 229   /// instruction.
 230   /// - InsnID - Instruction ID
 231   GIM_CheckIsSafeToFold,
 232
 233   /// Check the specified operands are identical.
 234   /// - InsnID - Instruction ID
 235   /// - OpIdx - Operand index
 236   /// - OtherInsnID - Other instruction ID
 237   /// - OtherOpIdx - Other operand index
 238   GIM_CheckIsSameOperand,
 239
 240   /// Fail the current try-block, or completely fail to match if there is no
 241   /// current try-block.
 242   GIM_Reject,
 243
 244   //=== Renderers ===
 245
 246   /// Mutate an instruction
 247   /// - NewInsnID - Instruction ID to define
 248   /// - OldInsnID - Instruction ID to mutate
 249   /// - NewOpcode - The new opcode to use
 250   GIR_MutateOpcode,
 251
 252   /// Build a new instruction
 253   /// - InsnID - Instruction ID to define
 254   /// - Opcode - The new opcode to use
 255   GIR_BuildMI,
 256
 257   /// Copy an operand to the specified instruction
 258   /// - NewInsnID - Instruction ID to modify
 259   /// - OldInsnID - Instruction ID to copy from
 260   /// - OpIdx - The operand to copy
 261   GIR_Copy,
 262
 263   /// Copy an operand to the specified instruction or add a zero register if the
 264   /// operand is a zero immediate.
 265   /// - NewInsnID - Instruction ID to modify
 266   /// - OldInsnID - Instruction ID to copy from
 267   /// - OpIdx - The operand to copy
 268   /// - ZeroReg - The zero register to use
 269   GIR_CopyOrAddZeroReg,
 270   /// Copy an operand to the specified instruction
 271   /// - NewInsnID - Instruction ID to modify
 272   /// - OldInsnID - Instruction ID to copy from
 273   /// - OpIdx - The operand to copy
 274   /// - SubRegIdx - The subregister to copy
 275   GIR_CopySubReg,
 276
 277   /// Add an implicit register def to the specified instruction
 278   /// - InsnID - Instruction ID to modify
 279   /// - RegNum - The register to add
 280   GIR_AddImplicitDef,
 281   /// Add an implicit register use to the specified instruction
 282   /// - InsnID - Instruction ID to modify
 283   /// - RegNum - The register to add
 284   GIR_AddImplicitUse,
 285   /// Add an register to the specified instruction
 286   /// - InsnID - Instruction ID to modify
 287   /// - RegNum - The register to add
 288   GIR_AddRegister,
 289
 290   /// Add a temporary register to the specified instruction
 291   /// - InsnID - Instruction ID to modify
 292   /// - TempRegID - The temporary register ID to add
 293   /// - TempRegFlags - The register flags to set
 294   GIR_AddTempRegister,
 295
 296   /// Add an immediate to the specified instruction
 297   /// - InsnID - Instruction ID to modify
 298   /// - Imm - The immediate to add
 299   GIR_AddImm,
 300   /// Render complex operands to the specified instruction
 301   /// - InsnID - Instruction ID to modify
 302   /// - RendererID - The renderer to call
 303   GIR_ComplexRenderer,
 304
 305   /// Render sub-operands of complex operands to the specified instruction
 306   /// - InsnID - Instruction ID to modify
 307   /// - RendererID - The renderer to call
 308   /// - RenderOpID - The suboperand to render.
 309   GIR_ComplexSubOperandRenderer,
 310   /// Render operands to the specified instruction using a custom function
 311   /// - InsnID - Instruction ID to modify
 312   /// - OldInsnID - Instruction ID to get the matched operand from
 313   /// - RendererFnID - Custom renderer function to call
 314   GIR_CustomRenderer,
 315
 316   /// Render a G_CONSTANT operator as a sign-extended immediate.
 317   /// - NewInsnID - Instruction ID to modify
 318   /// - OldInsnID - Instruction ID to copy from
 319   /// The operand index is implicitly 1.
 320   GIR_CopyConstantAsSImm,
 321
 322   /// Render a G_FCONSTANT operator as a sign-extended immediate.
 323   /// - NewInsnID - Instruction ID to modify
 324   /// - OldInsnID - Instruction ID to copy from
 325   /// The operand index is implicitly 1.
 326   GIR_CopyFConstantAsFPImm,
 327
 328   /// Constrain an instruction operand to a register class.
 329   /// - InsnID - Instruction ID to modify
 330   /// - OpIdx - Operand index
 331   /// - RCEnum - Register class enumeration value
 332   GIR_ConstrainOperandRC,
 333
 334   /// Constrain an instructions operands according to the instruction
 335   /// description.
 336   /// - InsnID - Instruction ID to modify
 337   GIR_ConstrainSelectedInstOperands,
 338
 339   /// Merge all memory operands into instruction.
 340   /// - InsnID - Instruction ID to modify
 341   /// - MergeInsnID... - One or more Instruction ID to merge into the result.
 342   /// - GIU_MergeMemOperands_EndOfList - Terminates the list of instructions to
 343   ///                                    merge.
 344   GIR_MergeMemOperands,
 345
 346   /// Erase from parent.
 347   /// - InsnID - Instruction ID to erase
 348   GIR_EraseFromParent,
 349
 350   /// Create a new temporary register that's not constrained.
 351   /// - TempRegID - The temporary register ID to initialize.
 352   /// - Expected type
 353   GIR_MakeTempReg,
 354
 355   /// A successful emission
 356   GIR_Done,
 357
 358   /// Increment the rule coverage counter.
 359   /// - RuleID - The ID of the rule that was covered.
 360   GIR_Coverage,
 361
 362   /// Keeping track of the number of the GI opcodes. Must be the last entry.
 363   GIU_NumOpcodes,
 364 };
 365
 366 enum {
 367   /// Indicates the end of the variable-length MergeInsnID list in a
 368   /// GIR_MergeMemOperands opcode.
 369   GIU_MergeMemOperands_EndOfList = -1,
 370 };
 371
 372 /// Provides the logic to select generic machine instructions.
 373 class InstructionSelector {
 374 public:
 375   virtual ~InstructionSelector() = default;
 376
 377   /// Select the (possibly generic) instruction \p I to only use target-specific
 378   /// opcodes. It is OK to insert multiple instructions, but they cannot be
 379   /// generic pre-isel instructions.
 380   ///
 381   /// \returns whether selection succeeded.
 382   /// \pre  I.getParent() && I.getParent()->getParent()
 383   /// \post
 384   ///   if returns true:
 385   ///     for I in all mutated/inserted instructions:
 386   ///       !isPreISelGenericOpcode(I.getOpcode())
 387   virtual bool select(MachineInstr &I) = 0;
 388
 389   CodeGenCoverage *CoverageInfo = nullptr;
 390   GISelKnownBits *KnownBits = nullptr;
 391   MachineFunction *MF = nullptr;
 392
 393   /// Setup per-MF selector state.
 394   virtual void setupMF(MachineFunction &mf,
 395                        GISelKnownBits &KB,
 396                        CodeGenCoverage &covinfo) {
 397     CoverageInfo = &covinfo;
 398     KnownBits = &KB;
 399     MF = &mf;
 400   }
 401
 402 protected:
 403   using ComplexRendererFns =
 404       Optional<SmallVector<std::function<void(MachineInstrBuilder &)>, 4>>;
 405   using RecordedMIVector = SmallVector<MachineInstr *, 4>;
 406   using NewMIVector = SmallVector<MachineInstrBuilder, 4>;
 407
 408   struct MatcherState {
 409     std::vector<ComplexRendererFns::value_type> Renderers;
 410     RecordedMIVector MIs;
 411     DenseMap<unsigned, unsigned> TempRegisters;
 412
 413     MatcherState(unsigned MaxRenderers);
 414   };
 415
 416 public:
 417   template <class PredicateBitset, class ComplexMatcherMemFn,
 418             class CustomRendererFn>
 419   struct ISelInfoTy {
 420     ISelInfoTy(const LLT *TypeObjects, size_t NumTypeObjects,
 421                const PredicateBitset *FeatureBitsets,
 422                const ComplexMatcherMemFn *ComplexPredicates,
 423                const CustomRendererFn *CustomRenderers)
 424         : TypeObjects(TypeObjects),
 425           FeatureBitsets(FeatureBitsets),
 426           ComplexPredicates(ComplexPredicates),
 427           CustomRenderers(CustomRenderers) {
 428
 429       for (size_t I = 0; I < NumTypeObjects; ++I)
 430         TypeIDMap[TypeObjects[I]] = I;
 431     }
 432     const LLT *TypeObjects;
 433     const PredicateBitset *FeatureBitsets;
 434     const ComplexMatcherMemFn *ComplexPredicates;
 435     const CustomRendererFn *CustomRenderers;
 436
 437     SmallDenseMap<LLT, unsigned, 64> TypeIDMap;
 438   };
 439
 440 protected:
 441   InstructionSelector();
 442
 443   /// Execute a given matcher table and return true if the match was successful
 444   /// and false otherwise.
 445   template <class TgtInstructionSelector, class PredicateBitset,
 446             class ComplexMatcherMemFn, class CustomRendererFn>
 447   bool executeMatchTable(
 448       TgtInstructionSelector &ISel, NewMIVector &OutMIs, MatcherState &State,
 449       const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, CustomRendererFn>
 450           &ISelInfo,
 451       const int64_t *MatchTable, const TargetInstrInfo &TII,
 452       MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
 453       const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures,
 454       CodeGenCoverage &CoverageInfo) const;
 455
 456   virtual const int64_t *getMatchTable() const {
 457     llvm_unreachable("Should have been overridden by tablegen if used");
 458   }
 459
 460   virtual bool testImmPredicate_I64(unsigned, int64_t) const {
 461     llvm_unreachable(
 462         "Subclasses must override this with a tablegen-erated function");
 463   }
 464   virtual bool testImmPredicate_APInt(unsigned, const APInt &) const {
 465     llvm_unreachable(
 466         "Subclasses must override this with a tablegen-erated function");
 467   }
 468   virtual bool testImmPredicate_APFloat(unsigned, const APFloat &) const {
 469     llvm_unreachable(
 470         "Subclasses must override this with a tablegen-erated function");
 471   }
 472   virtual bool testMIPredicate_MI(unsigned, const MachineInstr &) const {
 473     llvm_unreachable(
 474         "Subclasses must override this with a tablegen-erated function");
 475   }
 476
 477   /// Constrain a register operand of an instruction \p I to a specified
 478   /// register class. This could involve inserting COPYs before (for uses) or
 479   /// after (for defs) and may replace the operand of \p I.
 480   /// \returns whether operand regclass constraining succeeded.
 481   bool constrainOperandRegToRegClass(MachineInstr &I, unsigned OpIdx,
 482                                      const TargetRegisterClass &RC,
 483                                      const TargetInstrInfo &TII,
 484                                      const TargetRegisterInfo &TRI,
 485                                      const RegisterBankInfo &RBI) const;
 486
 487   bool isOperandImmEqual(const MachineOperand &MO, int64_t Value,
 488                          const MachineRegisterInfo &MRI) const;
 489
 490   /// Return true if the specified operand is a G_GEP with a G_CONSTANT on the
 491   /// right-hand side. GlobalISel's separation of pointer and integer types
 492   /// means that we don't need to worry about G_OR with equivalent semantics.
 493   bool isBaseWithConstantOffset(const MachineOperand &Root,
 494                                 const MachineRegisterInfo &MRI) const;
 495
 496   /// Return true if MI can obviously be folded into IntoMI.
 497   /// MI and IntoMI do not need to be in the same basic blocks, but MI must
 498   /// preceed IntoMI.
 499   bool isObviouslySafeToFold(MachineInstr &MI, MachineInstr &IntoMI) const;
 500 };
 501
 502 } // end namespace llvm
 503
 504 #endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H