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 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 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 a temporary register to the specified instruction 297 /// - InsnID - Instruction ID to modify 298 /// - TempRegID - The temporary register ID to add 299 /// - TempRegFlags - The register flags to set 300 /// - SubRegIndex - The subregister index to set 301 GIR_AddTempSubRegister, 302 303 /// Add an immediate to the specified instruction 304 /// - InsnID - Instruction ID to modify 305 /// - Imm - The immediate to add 306 GIR_AddImm, 307 /// Render complex operands to the specified instruction 308 /// - InsnID - Instruction ID to modify 309 /// - RendererID - The renderer to call 310 GIR_ComplexRenderer, 311 312 /// Render sub-operands of complex operands to the specified instruction 313 /// - InsnID - Instruction ID to modify 314 /// - RendererID - The renderer to call 315 /// - RenderOpID - The suboperand to render. 316 GIR_ComplexSubOperandRenderer, 317 /// Render operands to the specified instruction using a custom function 318 /// - InsnID - Instruction ID to modify 319 /// - OldInsnID - Instruction ID to get the matched operand from 320 /// - RendererFnID - Custom renderer function to call 321 GIR_CustomRenderer, 322 323 /// Render operands to the specified instruction using a custom function, 324 /// reading from a specific operand. 325 /// - InsnID - Instruction ID to modify 326 /// - OldInsnID - Instruction ID to get the matched operand from 327 /// - OpIdx - Operand index in OldInsnID the render function should read from.. 328 /// - RendererFnID - Custom renderer function to call 329 GIR_CustomOperandRenderer, 330 331 /// Render a G_CONSTANT operator as a sign-extended immediate. 332 /// - NewInsnID - Instruction ID to modify 333 /// - OldInsnID - Instruction ID to copy from 334 /// The operand index is implicitly 1. 335 GIR_CopyConstantAsSImm, 336 337 /// Render a G_FCONSTANT operator as a sign-extended immediate. 338 /// - NewInsnID - Instruction ID to modify 339 /// - OldInsnID - Instruction ID to copy from 340 /// The operand index is implicitly 1. 341 GIR_CopyFConstantAsFPImm, 342 343 /// Constrain an instruction operand to a register class. 344 /// - InsnID - Instruction ID to modify 345 /// - OpIdx - Operand index 346 /// - RCEnum - Register class enumeration value 347 GIR_ConstrainOperandRC, 348 349 /// Constrain an instructions operands according to the instruction 350 /// description. 351 /// - InsnID - Instruction ID to modify 352 GIR_ConstrainSelectedInstOperands, 353 354 /// Merge all memory operands into instruction. 355 /// - InsnID - Instruction ID to modify 356 /// - MergeInsnID... - One or more Instruction ID to merge into the result. 357 /// - GIU_MergeMemOperands_EndOfList - Terminates the list of instructions to 358 /// merge. 359 GIR_MergeMemOperands, 360 361 /// Erase from parent. 362 /// - InsnID - Instruction ID to erase 363 GIR_EraseFromParent, 364 365 /// Create a new temporary register that's not constrained. 366 /// - TempRegID - The temporary register ID to initialize. 367 /// - Expected type 368 GIR_MakeTempReg, 369 370 /// A successful emission 371 GIR_Done, 372 373 /// Increment the rule coverage counter. 374 /// - RuleID - The ID of the rule that was covered. 375 GIR_Coverage, 376 377 /// Keeping track of the number of the GI opcodes. Must be the last entry. 378 GIU_NumOpcodes, 379 }; 380 381 enum { 382 /// Indicates the end of the variable-length MergeInsnID list in a 383 /// GIR_MergeMemOperands opcode. 384 GIU_MergeMemOperands_EndOfList = -1, 385 }; 386 387 /// Provides the logic to select generic machine instructions. 388 class InstructionSelector { 389 public: 390 virtual ~InstructionSelector() = default; 391 392 /// Select the (possibly generic) instruction \p I to only use target-specific 393 /// opcodes. It is OK to insert multiple instructions, but they cannot be 394 /// generic pre-isel instructions. 395 /// 396 /// \returns whether selection succeeded. 397 /// \pre I.getParent() && I.getParent()->getParent() 398 /// \post 399 /// if returns true: 400 /// for I in all mutated/inserted instructions: 401 /// !isPreISelGenericOpcode(I.getOpcode()) 402 virtual bool select(MachineInstr &I) = 0; 403 404 CodeGenCoverage *CoverageInfo = nullptr; 405 GISelKnownBits *KnownBits = nullptr; 406 MachineFunction *MF = nullptr; 407 setupGeneratedPerFunctionState(MachineFunction & MF)408 virtual void setupGeneratedPerFunctionState(MachineFunction &MF) { 409 llvm_unreachable("TableGen should have emitted implementation"); 410 } 411 412 /// Setup per-MF selector state. setupMF(MachineFunction & mf,GISelKnownBits & KB,CodeGenCoverage & covinfo)413 virtual void setupMF(MachineFunction &mf, 414 GISelKnownBits &KB, 415 CodeGenCoverage &covinfo) { 416 CoverageInfo = &covinfo; 417 KnownBits = &KB; 418 MF = &mf; 419 setupGeneratedPerFunctionState(mf); 420 } 421 422 protected: 423 using ComplexRendererFns = 424 Optional<SmallVector<std::function<void(MachineInstrBuilder &)>, 4>>; 425 using RecordedMIVector = SmallVector<MachineInstr *, 4>; 426 using NewMIVector = SmallVector<MachineInstrBuilder, 4>; 427 428 struct MatcherState { 429 std::vector<ComplexRendererFns::value_type> Renderers; 430 RecordedMIVector MIs; 431 DenseMap<unsigned, unsigned> TempRegisters; 432 433 MatcherState(unsigned MaxRenderers); 434 }; 435 436 public: 437 template <class PredicateBitset, class ComplexMatcherMemFn, 438 class CustomRendererFn> 439 struct ISelInfoTy { ISelInfoTyISelInfoTy440 ISelInfoTy(const LLT *TypeObjects, size_t NumTypeObjects, 441 const PredicateBitset *FeatureBitsets, 442 const ComplexMatcherMemFn *ComplexPredicates, 443 const CustomRendererFn *CustomRenderers) 444 : TypeObjects(TypeObjects), 445 FeatureBitsets(FeatureBitsets), 446 ComplexPredicates(ComplexPredicates), 447 CustomRenderers(CustomRenderers) { 448 449 for (size_t I = 0; I < NumTypeObjects; ++I) 450 TypeIDMap[TypeObjects[I]] = I; 451 } 452 const LLT *TypeObjects; 453 const PredicateBitset *FeatureBitsets; 454 const ComplexMatcherMemFn *ComplexPredicates; 455 const CustomRendererFn *CustomRenderers; 456 457 SmallDenseMap<LLT, unsigned, 64> TypeIDMap; 458 }; 459 460 protected: 461 InstructionSelector(); 462 463 /// Execute a given matcher table and return true if the match was successful 464 /// and false otherwise. 465 template <class TgtInstructionSelector, class PredicateBitset, 466 class ComplexMatcherMemFn, class CustomRendererFn> 467 bool executeMatchTable( 468 TgtInstructionSelector &ISel, NewMIVector &OutMIs, MatcherState &State, 469 const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, CustomRendererFn> 470 &ISelInfo, 471 const int64_t *MatchTable, const TargetInstrInfo &TII, 472 MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI, 473 const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures, 474 CodeGenCoverage &CoverageInfo) const; 475 getMatchTable()476 virtual const int64_t *getMatchTable() const { 477 llvm_unreachable("Should have been overridden by tablegen if used"); 478 } 479 testImmPredicate_I64(unsigned,int64_t)480 virtual bool testImmPredicate_I64(unsigned, int64_t) const { 481 llvm_unreachable( 482 "Subclasses must override this with a tablegen-erated function"); 483 } testImmPredicate_APInt(unsigned,const APInt &)484 virtual bool testImmPredicate_APInt(unsigned, const APInt &) const { 485 llvm_unreachable( 486 "Subclasses must override this with a tablegen-erated function"); 487 } testImmPredicate_APFloat(unsigned,const APFloat &)488 virtual bool testImmPredicate_APFloat(unsigned, const APFloat &) const { 489 llvm_unreachable( 490 "Subclasses must override this with a tablegen-erated function"); 491 } testMIPredicate_MI(unsigned,const MachineInstr &)492 virtual bool testMIPredicate_MI(unsigned, const MachineInstr &) const { 493 llvm_unreachable( 494 "Subclasses must override this with a tablegen-erated function"); 495 } 496 497 /// Constrain a register operand of an instruction \p I to a specified 498 /// register class. This could involve inserting COPYs before (for uses) or 499 /// after (for defs) and may replace the operand of \p I. 500 /// \returns whether operand regclass constraining succeeded. 501 bool constrainOperandRegToRegClass(MachineInstr &I, unsigned OpIdx, 502 const TargetRegisterClass &RC, 503 const TargetInstrInfo &TII, 504 const TargetRegisterInfo &TRI, 505 const RegisterBankInfo &RBI) const; 506 507 bool isOperandImmEqual(const MachineOperand &MO, int64_t Value, 508 const MachineRegisterInfo &MRI) const; 509 510 /// Return true if the specified operand is a G_PTR_ADD with a G_CONSTANT on the 511 /// right-hand side. GlobalISel's separation of pointer and integer types 512 /// means that we don't need to worry about G_OR with equivalent semantics. 513 bool isBaseWithConstantOffset(const MachineOperand &Root, 514 const MachineRegisterInfo &MRI) const; 515 516 /// Return true if MI can obviously be folded into IntoMI. 517 /// MI and IntoMI do not need to be in the same basic blocks, but MI must 518 /// preceed IntoMI. 519 bool isObviouslySafeToFold(MachineInstr &MI, MachineInstr &IntoMI) const; 520 }; 521 522 } // end namespace llvm 523 524 #endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H 525