contrib/llvm-project/llvm/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 MachineInstr;
  35 class MachineInstrBuilder;
  36 class MachineFunction;
  37 class MachineOperand;
  38 class MachineRegisterInfo;
  39 class RegisterBankInfo;
  40 class TargetInstrInfo;
  41 class TargetRegisterClass;
  42 class TargetRegisterInfo;
  43
  44 /// Container class for CodeGen predicate results.
  45 /// This is convenient because std::bitset does not have a constructor
  46 /// with an initializer list of set bits.
  47 ///
  48 /// Each InstructionSelector subclass should define a PredicateBitset class
  49 /// with:
  50 ///   const unsigned MAX_SUBTARGET_PREDICATES = 192;
  51 ///   using PredicateBitset = PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;
  52 /// and updating the constant to suit the target. Tablegen provides a suitable
  53 /// definition for the predicates in use in <Target>GenGlobalISel.inc when
  54 /// GET_GLOBALISEL_PREDICATE_BITSET is defined.
  55 template <std::size_t MaxPredicates>
  56 class PredicateBitsetImpl : public std::bitset<MaxPredicates> {
  57 public:
  58   // Cannot inherit constructors because it's not supported by VC++..
  59   PredicateBitsetImpl() = default;
  60
  61   PredicateBitsetImpl(const std::bitset<MaxPredicates> &B)
  62       : std::bitset<MaxPredicates>(B) {}
  63
  64   PredicateBitsetImpl(std::initializer_list<unsigned> Init) {
  65     for (auto I : Init)
  66       std::bitset<MaxPredicates>::set(I);
  67   }
  68 };
  69
  70 enum {
  71   /// Begin a try-block to attempt a match and jump to OnFail if it is
  72   /// unsuccessful.
  73   /// - OnFail - The MatchTable entry at which to resume if the match fails.
  74   ///
  75   /// FIXME: This ought to take an argument indicating the number of try-blocks
  76   ///        to exit on failure. It's usually one but the last match attempt of
  77   ///        a block will need more. The (implemented) alternative is to tack a
  78   ///        GIM_Reject on the end of each try-block which is simpler but
  79   ///        requires an extra opcode and iteration in the interpreter on each
  80   ///        failed match.
  81   GIM_Try,
  82
  83   /// Switch over the opcode on the specified instruction
  84   /// - InsnID - Instruction ID
  85   /// - LowerBound - numerically minimum opcode supported
  86   /// - UpperBound - numerically maximum + 1 opcode supported
  87   /// - Default - failure jump target
  88   /// - JumpTable... - (UpperBound - LowerBound) (at least 2) jump targets
  89   GIM_SwitchOpcode,
  90
  91   /// Switch over the LLT on the specified instruction operand
  92   /// - InsnID - Instruction ID
  93   /// - OpIdx - Operand index
  94   /// - LowerBound - numerically minimum Type ID supported
  95   /// - UpperBound - numerically maximum + 1 Type ID supported
  96   /// - Default - failure jump target
  97   /// - JumpTable... - (UpperBound - LowerBound) (at least 2) jump targets
  98   GIM_SwitchType,
  99
 100   /// Record the specified instruction
 101   /// - NewInsnID - Instruction ID to define
 102   /// - InsnID - Instruction ID
 103   /// - OpIdx - Operand index
 104   GIM_RecordInsn,
 105
 106   /// Check the feature bits
 107   /// - Expected features
 108   GIM_CheckFeatures,
 109
 110   /// Check the opcode on the specified instruction
 111   /// - InsnID - Instruction ID
 112   /// - Expected opcode
 113   GIM_CheckOpcode,
 114   /// Check the instruction has the right number of operands
 115   /// - InsnID - Instruction ID
 116   /// - Expected number of operands
 117   GIM_CheckNumOperands,
 118   /// Check an immediate predicate on the specified instruction
 119   /// - InsnID - Instruction ID
 120   /// - The predicate to test
 121   GIM_CheckI64ImmPredicate,
 122   /// Check an immediate predicate on the specified instruction via an APInt.
 123   /// - InsnID - Instruction ID
 124   /// - The predicate to test
 125   GIM_CheckAPIntImmPredicate,
 126   /// Check a floating point immediate predicate on the specified instruction.
 127   /// - InsnID - Instruction ID
 128   /// - The predicate to test
 129   GIM_CheckAPFloatImmPredicate,
 130   /// Check a memory operation has the specified atomic ordering.
 131   /// - InsnID - Instruction ID
 132   /// - Ordering - The AtomicOrdering value
 133   GIM_CheckAtomicOrdering,
 134   GIM_CheckAtomicOrderingOrStrongerThan,
 135   GIM_CheckAtomicOrderingWeakerThan,
 136   /// Check the size of the memory access for the given machine memory operand.
 137   /// - InsnID - Instruction ID
 138   /// - MMOIdx - MMO index
 139   /// - Size - The size in bytes of the memory access
 140   GIM_CheckMemorySizeEqualTo,
 141
 142   /// Check the address space of the memory access for the given machine memory
 143   /// operand.
 144   /// - InsnID - Instruction ID
 145   /// - MMOIdx - MMO index
 146   /// - NumAddrSpace - Number of valid address spaces
 147   /// - AddrSpaceN - An allowed space of the memory access
 148   /// - AddrSpaceN+1 ...
 149   GIM_CheckMemoryAddressSpace,
 150
 151   /// Check the size of the memory access for the given machine memory operand
 152   /// against the size of an operand.
 153   /// - InsnID - Instruction ID
 154   /// - MMOIdx - MMO index
 155   /// - OpIdx - The operand index to compare the MMO against
 156   GIM_CheckMemorySizeEqualToLLT,
 157   GIM_CheckMemorySizeLessThanLLT,
 158   GIM_CheckMemorySizeGreaterThanLLT,
 159   /// Check a generic C++ instruction predicate
 160   /// - InsnID - Instruction ID
 161   /// - PredicateID - The ID of the predicate function to call
 162   GIM_CheckCxxInsnPredicate,
 163
 164   /// Check the type for the specified operand
 165   /// - InsnID - Instruction ID
 166   /// - OpIdx - Operand index
 167   /// - Expected type
 168   GIM_CheckType,
 169   /// Check the type of a pointer to any address space.
 170   /// - InsnID - Instruction ID
 171   /// - OpIdx - Operand index
 172   /// - SizeInBits - The size of the pointer value in bits.
 173   GIM_CheckPointerToAny,
 174   /// Check the register bank for the specified operand
 175   /// - InsnID - Instruction ID
 176   /// - OpIdx - Operand index
 177   /// - Expected register bank (specified as a register class)
 178   GIM_CheckRegBankForClass,
 179
 180   /// Check the operand matches a complex predicate
 181   /// - InsnID - Instruction ID
 182   /// - OpIdx - Operand index
 183   /// - RendererID - The renderer to hold the result
 184   /// - Complex predicate ID
 185   GIM_CheckComplexPattern,
 186
 187   /// Check the operand is a specific integer
 188   /// - InsnID - Instruction ID
 189   /// - OpIdx - Operand index
 190   /// - Expected integer
 191   GIM_CheckConstantInt,
 192   /// Check the operand is a specific literal integer (i.e. MO.isImm() or
 193   /// MO.isCImm() is true).
 194   /// - InsnID - Instruction ID
 195   /// - OpIdx - Operand index
 196   /// - Expected integer
 197   GIM_CheckLiteralInt,
 198   /// Check the operand is a specific intrinsic ID
 199   /// - InsnID - Instruction ID
 200   /// - OpIdx - Operand index
 201   /// - Expected Intrinsic ID
 202   GIM_CheckIntrinsicID,
 203
 204   /// Check the specified operand is an MBB
 205   /// - InsnID - Instruction ID
 206   /// - OpIdx - Operand index
 207   GIM_CheckIsMBB,
 208
 209   /// Check if the specified operand is safe to fold into the current
 210   /// instruction.
 211   /// - InsnID - Instruction ID
 212   GIM_CheckIsSafeToFold,
 213
 214   /// Check the specified operands are identical.
 215   /// - InsnID - Instruction ID
 216   /// - OpIdx - Operand index
 217   /// - OtherInsnID - Other instruction ID
 218   /// - OtherOpIdx - Other operand index
 219   GIM_CheckIsSameOperand,
 220
 221   /// Fail the current try-block, or completely fail to match if there is no
 222   /// current try-block.
 223   GIM_Reject,
 224
 225   //=== Renderers ===
 226
 227   /// Mutate an instruction
 228   /// - NewInsnID - Instruction ID to define
 229   /// - OldInsnID - Instruction ID to mutate
 230   /// - NewOpcode - The new opcode to use
 231   GIR_MutateOpcode,
 232
 233   /// Build a new instruction
 234   /// - InsnID - Instruction ID to define
 235   /// - Opcode - The new opcode to use
 236   GIR_BuildMI,
 237
 238   /// Copy an operand to the specified instruction
 239   /// - NewInsnID - Instruction ID to modify
 240   /// - OldInsnID - Instruction ID to copy from
 241   /// - OpIdx - The operand to copy
 242   GIR_Copy,
 243
 244   /// Copy an operand to the specified instruction or add a zero register if the
 245   /// operand is a zero immediate.
 246   /// - NewInsnID - Instruction ID to modify
 247   /// - OldInsnID - Instruction ID to copy from
 248   /// - OpIdx - The operand to copy
 249   /// - ZeroReg - The zero register to use
 250   GIR_CopyOrAddZeroReg,
 251   /// Copy an operand to the specified instruction
 252   /// - NewInsnID - Instruction ID to modify
 253   /// - OldInsnID - Instruction ID to copy from
 254   /// - OpIdx - The operand to copy
 255   /// - SubRegIdx - The subregister to copy
 256   GIR_CopySubReg,
 257
 258   /// Add an implicit register def to the specified instruction
 259   /// - InsnID - Instruction ID to modify
 260   /// - RegNum - The register to add
 261   GIR_AddImplicitDef,
 262   /// Add an implicit register use to the specified instruction
 263   /// - InsnID - Instruction ID to modify
 264   /// - RegNum - The register to add
 265   GIR_AddImplicitUse,
 266   /// Add an register to the specified instruction
 267   /// - InsnID - Instruction ID to modify
 268   /// - RegNum - The register to add
 269   GIR_AddRegister,
 270
 271   /// Add a temporary register to the specified instruction
 272   /// - InsnID - Instruction ID to modify
 273   /// - TempRegID - The temporary register ID to add
 274   /// - TempRegFlags - The register flags to set
 275   GIR_AddTempRegister,
 276
 277   /// Add an immediate to the specified instruction
 278   /// - InsnID - Instruction ID to modify
 279   /// - Imm - The immediate to add
 280   GIR_AddImm,
 281   /// Render complex operands to the specified instruction
 282   /// - InsnID - Instruction ID to modify
 283   /// - RendererID - The renderer to call
 284   GIR_ComplexRenderer,
 285
 286   /// Render sub-operands of complex operands to the specified instruction
 287   /// - InsnID - Instruction ID to modify
 288   /// - RendererID - The renderer to call
 289   /// - RenderOpID - The suboperand to render.
 290   GIR_ComplexSubOperandRenderer,
 291   /// Render operands to the specified instruction using a custom function
 292   /// - InsnID - Instruction ID to modify
 293   /// - OldInsnID - Instruction ID to get the matched operand from
 294   /// - RendererFnID - Custom renderer function to call
 295   GIR_CustomRenderer,
 296
 297   /// Render a G_CONSTANT operator as a sign-extended immediate.
 298   /// - NewInsnID - Instruction ID to modify
 299   /// - OldInsnID - Instruction ID to copy from
 300   /// The operand index is implicitly 1.
 301   GIR_CopyConstantAsSImm,
 302
 303   /// Render a G_FCONSTANT operator as a sign-extended immediate.
 304   /// - NewInsnID - Instruction ID to modify
 305   /// - OldInsnID - Instruction ID to copy from
 306   /// The operand index is implicitly 1.
 307   GIR_CopyFConstantAsFPImm,
 308
 309   /// Constrain an instruction operand to a register class.
 310   /// - InsnID - Instruction ID to modify
 311   /// - OpIdx - Operand index
 312   /// - RCEnum - Register class enumeration value
 313   GIR_ConstrainOperandRC,
 314
 315   /// Constrain an instructions operands according to the instruction
 316   /// description.
 317   /// - InsnID - Instruction ID to modify
 318   GIR_ConstrainSelectedInstOperands,
 319
 320   /// Merge all memory operands into instruction.
 321   /// - InsnID - Instruction ID to modify
 322   /// - MergeInsnID... - One or more Instruction ID to merge into the result.
 323   /// - GIU_MergeMemOperands_EndOfList - Terminates the list of instructions to
 324   ///                                    merge.
 325   GIR_MergeMemOperands,
 326
 327   /// Erase from parent.
 328   /// - InsnID - Instruction ID to erase
 329   GIR_EraseFromParent,
 330
 331   /// Create a new temporary register that's not constrained.
 332   /// - TempRegID - The temporary register ID to initialize.
 333   /// - Expected type
 334   GIR_MakeTempReg,
 335
 336   /// A successful emission
 337   GIR_Done,
 338
 339   /// Increment the rule coverage counter.
 340   /// - RuleID - The ID of the rule that was covered.
 341   GIR_Coverage,
 342
 343   /// Keeping track of the number of the GI opcodes. Must be the last entry.
 344   GIU_NumOpcodes,
 345 };
 346
 347 enum {
 348   /// Indicates the end of the variable-length MergeInsnID list in a
 349   /// GIR_MergeMemOperands opcode.
 350   GIU_MergeMemOperands_EndOfList = -1,
 351 };
 352
 353 /// Provides the logic to select generic machine instructions.
 354 class InstructionSelector {
 355 public:
 356   virtual ~InstructionSelector() = default;
 357
 358   /// Select the (possibly generic) instruction \p I to only use target-specific
 359   /// opcodes. It is OK to insert multiple instructions, but they cannot be
 360   /// generic pre-isel instructions.
 361   ///
 362   /// \returns whether selection succeeded.
 363   /// \pre  I.getParent() && I.getParent()->getParent()
 364   /// \post
 365   ///   if returns true:
 366   ///     for I in all mutated/inserted instructions:
 367   ///       !isPreISelGenericOpcode(I.getOpcode())
 368   virtual bool select(MachineInstr &I, CodeGenCoverage &CoverageInfo) const = 0;
 369
 370 protected:
 371   using ComplexRendererFns =
 372       Optional<SmallVector<std::function<void(MachineInstrBuilder &)>, 4>>;
 373   using RecordedMIVector = SmallVector<MachineInstr *, 4>;
 374   using NewMIVector = SmallVector<MachineInstrBuilder, 4>;
 375
 376   struct MatcherState {
 377     std::vector<ComplexRendererFns::value_type> Renderers;
 378     RecordedMIVector MIs;
 379     DenseMap<unsigned, unsigned> TempRegisters;
 380
 381     MatcherState(unsigned MaxRenderers);
 382   };
 383
 384 public:
 385   template <class PredicateBitset, class ComplexMatcherMemFn,
 386             class CustomRendererFn>
 387   struct ISelInfoTy {
 388     ISelInfoTy(const LLT *TypeObjects, size_t NumTypeObjects,
 389                const PredicateBitset *FeatureBitsets,
 390                const ComplexMatcherMemFn *ComplexPredicates,
 391                const CustomRendererFn *CustomRenderers)
 392         : TypeObjects(TypeObjects),
 393           FeatureBitsets(FeatureBitsets),
 394           ComplexPredicates(ComplexPredicates),
 395           CustomRenderers(CustomRenderers) {
 396
 397       for (size_t I = 0; I < NumTypeObjects; ++I)
 398         TypeIDMap[TypeObjects[I]] = I;
 399     }
 400     const LLT *TypeObjects;
 401     const PredicateBitset *FeatureBitsets;
 402     const ComplexMatcherMemFn *ComplexPredicates;
 403     const CustomRendererFn *CustomRenderers;
 404
 405     SmallDenseMap<LLT, unsigned, 64> TypeIDMap;
 406   };
 407
 408 protected:
 409   InstructionSelector();
 410
 411   /// Execute a given matcher table and return true if the match was successful
 412   /// and false otherwise.
 413   template <class TgtInstructionSelector, class PredicateBitset,
 414             class ComplexMatcherMemFn, class CustomRendererFn>
 415   bool executeMatchTable(
 416       TgtInstructionSelector &ISel, NewMIVector &OutMIs, MatcherState &State,
 417       const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, CustomRendererFn>
 418           &ISelInfo,
 419       const int64_t *MatchTable, const TargetInstrInfo &TII,
 420       MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI,
 421       const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures,
 422       CodeGenCoverage &CoverageInfo) const;
 423
 424   virtual const int64_t *getMatchTable() const {
 425     llvm_unreachable("Should have been overridden by tablegen if used");
 426   }
 427
 428   virtual bool testImmPredicate_I64(unsigned, int64_t) const {
 429     llvm_unreachable(
 430         "Subclasses must override this with a tablegen-erated function");
 431   }
 432   virtual bool testImmPredicate_APInt(unsigned, const APInt &) const {
 433     llvm_unreachable(
 434         "Subclasses must override this with a tablegen-erated function");
 435   }
 436   virtual bool testImmPredicate_APFloat(unsigned, const APFloat &) const {
 437     llvm_unreachable(
 438         "Subclasses must override this with a tablegen-erated function");
 439   }
 440   virtual bool testMIPredicate_MI(unsigned, const MachineInstr &) const {
 441     llvm_unreachable(
 442         "Subclasses must override this with a tablegen-erated function");
 443   }
 444
 445   /// Constrain a register operand of an instruction \p I to a specified
 446   /// register class. This could involve inserting COPYs before (for uses) or
 447   /// after (for defs) and may replace the operand of \p I.
 448   /// \returns whether operand regclass constraining succeeded.
 449   bool constrainOperandRegToRegClass(MachineInstr &I, unsigned OpIdx,
 450                                      const TargetRegisterClass &RC,
 451                                      const TargetInstrInfo &TII,
 452                                      const TargetRegisterInfo &TRI,
 453                                      const RegisterBankInfo &RBI) const;
 454
 455   bool isOperandImmEqual(const MachineOperand &MO, int64_t Value,
 456                          const MachineRegisterInfo &MRI) const;
 457
 458   /// Return true if the specified operand is a G_GEP with a G_CONSTANT on the
 459   /// right-hand side. GlobalISel's separation of pointer and integer types
 460   /// means that we don't need to worry about G_OR with equivalent semantics.
 461   bool isBaseWithConstantOffset(const MachineOperand &Root,
 462                                 const MachineRegisterInfo &MRI) const;
 463
 464   /// Return true if MI can obviously be folded into IntoMI.
 465   /// MI and IntoMI do not need to be in the same basic blocks, but MI must
 466   /// preceed IntoMI.
 467   bool isObviouslySafeToFold(MachineInstr &MI, MachineInstr &IntoMI) const;
 468 };
 469
 470 } // end namespace llvm
 471
 472 #endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H