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 116 /// Check the opcode on the specified instruction, checking 2 acceptable 117 /// alternatives. 118 /// - InsnID - Instruction ID 119 /// - Expected opcode 120 /// - Alternative expected opcode 121 GIM_CheckOpcodeIsEither, 122 123 /// Check the instruction has the right number of operands 124 /// - InsnID - Instruction ID 125 /// - Expected number of operands 126 GIM_CheckNumOperands, 127 /// Check an immediate predicate on the specified instruction 128 /// - InsnID - Instruction ID 129 /// - The predicate to test 130 GIM_CheckI64ImmPredicate, 131 /// Check an immediate predicate on the specified instruction via an APInt. 132 /// - InsnID - Instruction ID 133 /// - The predicate to test 134 GIM_CheckAPIntImmPredicate, 135 /// Check a floating point immediate predicate on the specified instruction. 136 /// - InsnID - Instruction ID 137 /// - The predicate to test 138 GIM_CheckAPFloatImmPredicate, 139 /// Check a memory operation has the specified atomic ordering. 140 /// - InsnID - Instruction ID 141 /// - Ordering - The AtomicOrdering value 142 GIM_CheckAtomicOrdering, 143 GIM_CheckAtomicOrderingOrStrongerThan, 144 GIM_CheckAtomicOrderingWeakerThan, 145 /// Check the size of the memory access for the given machine memory operand. 146 /// - InsnID - Instruction ID 147 /// - MMOIdx - MMO index 148 /// - Size - The size in bytes of the memory access 149 GIM_CheckMemorySizeEqualTo, 150 151 /// Check the address space of the memory access for the given machine memory 152 /// operand. 153 /// - InsnID - Instruction ID 154 /// - MMOIdx - MMO index 155 /// - NumAddrSpace - Number of valid address spaces 156 /// - AddrSpaceN - An allowed space of the memory access 157 /// - AddrSpaceN+1 ... 158 GIM_CheckMemoryAddressSpace, 159 160 /// Check the minimum alignment of the memory access for the given machine 161 /// memory operand. 162 /// - InsnID - Instruction ID 163 /// - MMOIdx - MMO index 164 /// - MinAlign - Minimum acceptable alignment 165 GIM_CheckMemoryAlignment, 166 167 /// Check the size of the memory access for the given machine memory operand 168 /// against the size of an operand. 169 /// - InsnID - Instruction ID 170 /// - MMOIdx - MMO index 171 /// - OpIdx - The operand index to compare the MMO against 172 GIM_CheckMemorySizeEqualToLLT, 173 GIM_CheckMemorySizeLessThanLLT, 174 GIM_CheckMemorySizeGreaterThanLLT, 175 176 /// Check if this is a vector that can be treated as a vector splat 177 /// constant. This is valid for both G_BUILD_VECTOR as well as 178 /// G_BUILD_VECTOR_TRUNC. For AllOnes refers to individual bits, so a -1 179 /// element. 180 /// - InsnID - Instruction ID 181 GIM_CheckIsBuildVectorAllOnes, 182 GIM_CheckIsBuildVectorAllZeros, 183 184 /// Check a generic C++ instruction predicate 185 /// - InsnID - Instruction ID 186 /// - PredicateID - The ID of the predicate function to call 187 GIM_CheckCxxInsnPredicate, 188 189 /// Check the type for the specified operand 190 /// - InsnID - Instruction ID 191 /// - OpIdx - Operand index 192 /// - Expected type 193 GIM_CheckType, 194 /// Check the type of a pointer to any address space. 195 /// - InsnID - Instruction ID 196 /// - OpIdx - Operand index 197 /// - SizeInBits - The size of the pointer value in bits. 198 GIM_CheckPointerToAny, 199 /// Check the register bank for the specified operand 200 /// - InsnID - Instruction ID 201 /// - OpIdx - Operand index 202 /// - Expected register bank (specified as a register class) 203 GIM_CheckRegBankForClass, 204 205 /// Check the operand matches a complex predicate 206 /// - InsnID - Instruction ID 207 /// - OpIdx - Operand index 208 /// - RendererID - The renderer to hold the result 209 /// - Complex predicate ID 210 GIM_CheckComplexPattern, 211 212 /// Check the operand is a specific integer 213 /// - InsnID - Instruction ID 214 /// - OpIdx - Operand index 215 /// - Expected integer 216 GIM_CheckConstantInt, 217 /// Check the operand is a specific literal integer (i.e. MO.isImm() or 218 /// MO.isCImm() is true). 219 /// - InsnID - Instruction ID 220 /// - OpIdx - Operand index 221 /// - Expected integer 222 GIM_CheckLiteralInt, 223 /// Check the operand is a specific intrinsic ID 224 /// - InsnID - Instruction ID 225 /// - OpIdx - Operand index 226 /// - Expected Intrinsic ID 227 GIM_CheckIntrinsicID, 228 229 /// Check the operand is a specific predicate 230 /// - InsnID - Instruction ID 231 /// - OpIdx - Operand index 232 /// - Expected predicate 233 GIM_CheckCmpPredicate, 234 235 /// Check the specified operand is an MBB 236 /// - InsnID - Instruction ID 237 /// - OpIdx - Operand index 238 GIM_CheckIsMBB, 239 240 /// Check the specified operand is an Imm 241 /// - InsnID - Instruction ID 242 /// - OpIdx - Operand index 243 GIM_CheckIsImm, 244 245 /// Check if the specified operand is safe to fold into the current 246 /// instruction. 247 /// - InsnID - Instruction ID 248 GIM_CheckIsSafeToFold, 249 250 /// Check the specified operands are identical. 251 /// - InsnID - Instruction ID 252 /// - OpIdx - Operand index 253 /// - OtherInsnID - Other instruction ID 254 /// - OtherOpIdx - Other operand index 255 GIM_CheckIsSameOperand, 256 257 /// Predicates with 'let PredicateCodeUsesOperands = 1' need to examine some 258 /// named operands that will be recorded in RecordedOperands. Names of these 259 /// operands are referenced in predicate argument list. Emitter determines 260 /// StoreIdx(corresponds to the order in which names appear in argument list). 261 /// - InsnID - Instruction ID 262 /// - OpIdx - Operand index 263 /// - StoreIdx - Store location in RecordedOperands. 264 GIM_RecordNamedOperand, 265 266 /// Fail the current try-block, or completely fail to match if there is no 267 /// current try-block. 268 GIM_Reject, 269 270 //=== Renderers === 271 272 /// Mutate an instruction 273 /// - NewInsnID - Instruction ID to define 274 /// - OldInsnID - Instruction ID to mutate 275 /// - NewOpcode - The new opcode to use 276 GIR_MutateOpcode, 277 278 /// Build a new instruction 279 /// - InsnID - Instruction ID to define 280 /// - Opcode - The new opcode to use 281 GIR_BuildMI, 282 283 /// Copy an operand to the specified instruction 284 /// - NewInsnID - Instruction ID to modify 285 /// - OldInsnID - Instruction ID to copy from 286 /// - OpIdx - The operand to copy 287 GIR_Copy, 288 289 /// Copy an operand to the specified instruction or add a zero register if the 290 /// operand is a zero immediate. 291 /// - NewInsnID - Instruction ID to modify 292 /// - OldInsnID - Instruction ID to copy from 293 /// - OpIdx - The operand to copy 294 /// - ZeroReg - The zero register to use 295 GIR_CopyOrAddZeroReg, 296 /// Copy an operand to the specified instruction 297 /// - NewInsnID - Instruction ID to modify 298 /// - OldInsnID - Instruction ID to copy from 299 /// - OpIdx - The operand to copy 300 /// - SubRegIdx - The subregister to copy 301 GIR_CopySubReg, 302 303 /// Add an implicit register def to the specified instruction 304 /// - InsnID - Instruction ID to modify 305 /// - RegNum - The register to add 306 GIR_AddImplicitDef, 307 /// Add an implicit register use to the specified instruction 308 /// - InsnID - Instruction ID to modify 309 /// - RegNum - The register to add 310 GIR_AddImplicitUse, 311 /// Add an register to the specified instruction 312 /// - InsnID - Instruction ID to modify 313 /// - RegNum - The register to add 314 GIR_AddRegister, 315 316 /// Add a temporary register to the specified instruction 317 /// - InsnID - Instruction ID to modify 318 /// - TempRegID - The temporary register ID to add 319 /// - TempRegFlags - The register flags to set 320 GIR_AddTempRegister, 321 322 /// Add a temporary register to the specified instruction 323 /// - InsnID - Instruction ID to modify 324 /// - TempRegID - The temporary register ID to add 325 /// - TempRegFlags - The register flags to set 326 /// - SubRegIndex - The subregister index to set 327 GIR_AddTempSubRegister, 328 329 /// Add an immediate to the specified instruction 330 /// - InsnID - Instruction ID to modify 331 /// - Imm - The immediate to add 332 GIR_AddImm, 333 /// Render complex operands to the specified instruction 334 /// - InsnID - Instruction ID to modify 335 /// - RendererID - The renderer to call 336 GIR_ComplexRenderer, 337 338 /// Render sub-operands of complex operands to the specified instruction 339 /// - InsnID - Instruction ID to modify 340 /// - RendererID - The renderer to call 341 /// - RenderOpID - The suboperand to render. 342 GIR_ComplexSubOperandRenderer, 343 /// Render operands to the specified instruction using a custom function 344 /// - InsnID - Instruction ID to modify 345 /// - OldInsnID - Instruction ID to get the matched operand from 346 /// - RendererFnID - Custom renderer function to call 347 GIR_CustomRenderer, 348 349 /// Render operands to the specified instruction using a custom function, 350 /// reading from a specific operand. 351 /// - InsnID - Instruction ID to modify 352 /// - OldInsnID - Instruction ID to get the matched operand from 353 /// - OpIdx - Operand index in OldInsnID the render function should read from.. 354 /// - RendererFnID - Custom renderer function to call 355 GIR_CustomOperandRenderer, 356 357 /// Render a G_CONSTANT operator as a sign-extended immediate. 358 /// - NewInsnID - Instruction ID to modify 359 /// - OldInsnID - Instruction ID to copy from 360 /// The operand index is implicitly 1. 361 GIR_CopyConstantAsSImm, 362 363 /// Render a G_FCONSTANT operator as a sign-extended immediate. 364 /// - NewInsnID - Instruction ID to modify 365 /// - OldInsnID - Instruction ID to copy from 366 /// The operand index is implicitly 1. 367 GIR_CopyFConstantAsFPImm, 368 369 /// Constrain an instruction operand to a register class. 370 /// - InsnID - Instruction ID to modify 371 /// - OpIdx - Operand index 372 /// - RCEnum - Register class enumeration value 373 GIR_ConstrainOperandRC, 374 375 /// Constrain an instructions operands according to the instruction 376 /// description. 377 /// - InsnID - Instruction ID to modify 378 GIR_ConstrainSelectedInstOperands, 379 380 /// Merge all memory operands into instruction. 381 /// - InsnID - Instruction ID to modify 382 /// - MergeInsnID... - One or more Instruction ID to merge into the result. 383 /// - GIU_MergeMemOperands_EndOfList - Terminates the list of instructions to 384 /// merge. 385 GIR_MergeMemOperands, 386 387 /// Erase from parent. 388 /// - InsnID - Instruction ID to erase 389 GIR_EraseFromParent, 390 391 /// Create a new temporary register that's not constrained. 392 /// - TempRegID - The temporary register ID to initialize. 393 /// - Expected type 394 GIR_MakeTempReg, 395 396 /// A successful emission 397 GIR_Done, 398 399 /// Increment the rule coverage counter. 400 /// - RuleID - The ID of the rule that was covered. 401 GIR_Coverage, 402 403 /// Keeping track of the number of the GI opcodes. Must be the last entry. 404 GIU_NumOpcodes, 405 }; 406 407 enum { 408 /// Indicates the end of the variable-length MergeInsnID list in a 409 /// GIR_MergeMemOperands opcode. 410 GIU_MergeMemOperands_EndOfList = -1, 411 }; 412 413 /// Provides the logic to select generic machine instructions. 414 class InstructionSelector { 415 public: 416 virtual ~InstructionSelector() = default; 417 418 /// Select the (possibly generic) instruction \p I to only use target-specific 419 /// opcodes. It is OK to insert multiple instructions, but they cannot be 420 /// generic pre-isel instructions. 421 /// 422 /// \returns whether selection succeeded. 423 /// \pre I.getParent() && I.getParent()->getParent() 424 /// \post 425 /// if returns true: 426 /// for I in all mutated/inserted instructions: 427 /// !isPreISelGenericOpcode(I.getOpcode()) 428 virtual bool select(MachineInstr &I) = 0; 429 430 CodeGenCoverage *CoverageInfo = nullptr; 431 GISelKnownBits *KnownBits = nullptr; 432 MachineFunction *MF = nullptr; 433 434 virtual void setupGeneratedPerFunctionState(MachineFunction &MF) { 435 llvm_unreachable("TableGen should have emitted implementation"); 436 } 437 438 /// Setup per-MF selector state. 439 virtual void setupMF(MachineFunction &mf, 440 GISelKnownBits &KB, 441 CodeGenCoverage &covinfo) { 442 CoverageInfo = &covinfo; 443 KnownBits = &KB; 444 MF = &mf; 445 setupGeneratedPerFunctionState(mf); 446 } 447 448 protected: 449 using ComplexRendererFns = 450 Optional<SmallVector<std::function<void(MachineInstrBuilder &)>, 4>>; 451 using RecordedMIVector = SmallVector<MachineInstr *, 4>; 452 using NewMIVector = SmallVector<MachineInstrBuilder, 4>; 453 454 struct MatcherState { 455 std::vector<ComplexRendererFns::value_type> Renderers; 456 RecordedMIVector MIs; 457 DenseMap<unsigned, unsigned> TempRegisters; 458 /// Named operands that predicate with 'let PredicateCodeUsesOperands = 1' 459 /// referenced in its argument list. Operands are inserted at index set by 460 /// emitter, it corresponds to the order in which names appear in argument 461 /// list. Currently such predicates don't have more then 3 arguments. 462 std::array<const MachineOperand *, 3> RecordedOperands; 463 464 MatcherState(unsigned MaxRenderers); 465 }; 466 467 public: 468 template <class PredicateBitset, class ComplexMatcherMemFn, 469 class CustomRendererFn> 470 struct ISelInfoTy { 471 ISelInfoTy(const LLT *TypeObjects, size_t NumTypeObjects, 472 const PredicateBitset *FeatureBitsets, 473 const ComplexMatcherMemFn *ComplexPredicates, 474 const CustomRendererFn *CustomRenderers) 475 : TypeObjects(TypeObjects), 476 FeatureBitsets(FeatureBitsets), 477 ComplexPredicates(ComplexPredicates), 478 CustomRenderers(CustomRenderers) { 479 480 for (size_t I = 0; I < NumTypeObjects; ++I) 481 TypeIDMap[TypeObjects[I]] = I; 482 } 483 const LLT *TypeObjects; 484 const PredicateBitset *FeatureBitsets; 485 const ComplexMatcherMemFn *ComplexPredicates; 486 const CustomRendererFn *CustomRenderers; 487 488 SmallDenseMap<LLT, unsigned, 64> TypeIDMap; 489 }; 490 491 protected: 492 InstructionSelector(); 493 494 /// Execute a given matcher table and return true if the match was successful 495 /// and false otherwise. 496 template <class TgtInstructionSelector, class PredicateBitset, 497 class ComplexMatcherMemFn, class CustomRendererFn> 498 bool executeMatchTable( 499 TgtInstructionSelector &ISel, NewMIVector &OutMIs, MatcherState &State, 500 const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, CustomRendererFn> 501 &ISelInfo, 502 const int64_t *MatchTable, const TargetInstrInfo &TII, 503 MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI, 504 const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures, 505 CodeGenCoverage &CoverageInfo) const; 506 507 virtual const int64_t *getMatchTable() const { 508 llvm_unreachable("Should have been overridden by tablegen if used"); 509 } 510 511 virtual bool testImmPredicate_I64(unsigned, int64_t) const { 512 llvm_unreachable( 513 "Subclasses must override this with a tablegen-erated function"); 514 } 515 virtual bool testImmPredicate_APInt(unsigned, const APInt &) const { 516 llvm_unreachable( 517 "Subclasses must override this with a tablegen-erated function"); 518 } 519 virtual bool testImmPredicate_APFloat(unsigned, const APFloat &) const { 520 llvm_unreachable( 521 "Subclasses must override this with a tablegen-erated function"); 522 } 523 virtual bool testMIPredicate_MI( 524 unsigned, const MachineInstr &, 525 const std::array<const MachineOperand *, 3> &Operands) const { 526 llvm_unreachable( 527 "Subclasses must override this with a tablegen-erated function"); 528 } 529 530 bool isOperandImmEqual(const MachineOperand &MO, int64_t Value, 531 const MachineRegisterInfo &MRI) const; 532 533 /// Return true if the specified operand is a G_PTR_ADD with a G_CONSTANT on the 534 /// right-hand side. GlobalISel's separation of pointer and integer types 535 /// means that we don't need to worry about G_OR with equivalent semantics. 536 bool isBaseWithConstantOffset(const MachineOperand &Root, 537 const MachineRegisterInfo &MRI) const; 538 539 /// Return true if MI can obviously be folded into IntoMI. 540 /// MI and IntoMI do not need to be in the same basic blocks, but MI must 541 /// preceed IntoMI. 542 bool isObviouslySafeToFold(MachineInstr &MI, MachineInstr &IntoMI) const; 543 }; 544 545 } // end namespace llvm 546 547 #endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H 548