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