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