1 //===- llvm/CodeGen/GlobalISel/GIMatchTableExecutor.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 GIMatchTableExecutor API, the opcodes supported 10 /// by the match table, and some associated data structures used by the 11 /// executor's implementation (see `GIMatchTableExecutorImpl.h`). 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_CODEGEN_GLOBALISEL_GIMATCHTABLEEXECUTOR_H 16 #define LLVM_CODEGEN_GLOBALISEL_GIMATCHTABLEEXECUTOR_H 17 18 #include "llvm/ADT/Bitset.h" 19 #include "llvm/ADT/DenseMap.h" 20 #include "llvm/ADT/SmallVector.h" 21 #include "llvm/CodeGen/GlobalISel/Utils.h" 22 #include "llvm/CodeGen/MachineFunction.h" 23 #include "llvm/CodeGenTypes/LowLevelType.h" 24 #include "llvm/IR/Function.h" 25 #include <bitset> 26 #include <cstddef> 27 #include <cstdint> 28 #include <functional> 29 #include <initializer_list> 30 #include <optional> 31 #include <vector> 32 33 namespace llvm { 34 35 class BlockFrequencyInfo; 36 class CodeGenCoverage; 37 class MachineBasicBlock; 38 class ProfileSummaryInfo; 39 class APInt; 40 class APFloat; 41 class GISelKnownBits; 42 class MachineInstr; 43 class MachineIRBuilder; 44 class MachineInstrBuilder; 45 class MachineFunction; 46 class MachineOperand; 47 class MachineRegisterInfo; 48 class RegisterBankInfo; 49 class TargetInstrInfo; 50 class TargetRegisterInfo; 51 52 enum { 53 GICXXPred_Invalid = 0, 54 GICXXCustomAction_Invalid = 0, 55 }; 56 57 /// The MatchTable is encoded as an array of bytes. 58 /// Thus, opcodes are expected to be <255. 59 /// 60 /// Operands can be variable-sized, their size is always after their name 61 /// in the docs, e.g. "Foo(4)" means that "Foo" takes 4 entries in the table, 62 /// so 4 bytes. "Foo()" 63 /// 64 /// As a general rule of thumb: 65 /// - Instruction & Operand IDs are ULEB128 66 /// - LLT IDs are 1 byte 67 /// - Predicates and target opcodes, register and register class IDs are 2 68 /// bytes. 69 /// - Indexes into the table are 4 bytes. 70 /// - Inline constants are 8 bytes 71 /// 72 /// Design notes: 73 /// - Inst/Op IDs have to be LEB128 because some targets generate 74 /// extremely long patterns which need more than 255 temporaries. 75 /// We could just use 2 bytes everytime, but then some targets like 76 /// X86/AMDGPU that have no need for it will pay the price all the time. 77 enum { 78 /// Begin a try-block to attempt a match and jump to OnFail if it is 79 /// unsuccessful. 80 /// - OnFail(4) - The MatchTable entry at which to resume if the match fails. 81 /// 82 /// FIXME: This ought to take an argument indicating the number of try-blocks 83 /// to exit on failure. It's usually one but the last match attempt of 84 /// a block will need more. The (implemented) alternative is to tack a 85 /// GIM_Reject on the end of each try-block which is simpler but 86 /// requires an extra opcode and iteration in the interpreter on each 87 /// failed match. 88 GIM_Try, 89 90 /// Switch over the opcode on the specified instruction 91 /// - InsnID(ULEB128) - Instruction ID 92 /// - LowerBound(2) - numerically minimum opcode supported 93 /// - UpperBound(2) - numerically maximum + 1 opcode supported 94 /// - Default(4) - failure jump target 95 /// - JumpTable(4)... - (UpperBound - LowerBound) (at least 2) jump targets 96 GIM_SwitchOpcode, 97 98 /// Switch over the LLT on the specified instruction operand 99 /// - InsnID(ULEB128) - Instruction ID 100 /// - OpIdx(ULEB128) - Operand index 101 /// - LowerBound(2) - numerically minimum Type ID supported 102 /// - UpperBound(2) - numerically maximum + 1 Type ID supported 103 /// - Default(4) - failure jump target 104 /// - JumpTable(4)... - (UpperBound - LowerBound) (at least 2) jump targets 105 GIM_SwitchType, 106 107 /// Record the specified instruction. 108 /// The IgnoreCopies variant ignores COPY instructions. 109 /// - NewInsnID(ULEB128) - Instruction ID to define 110 /// - InsnID(ULEB128) - Instruction ID 111 /// - OpIdx(ULEB128) - Operand index 112 GIM_RecordInsn, 113 GIM_RecordInsnIgnoreCopies, 114 115 /// Check the feature bits 116 /// Feature(2) - Expected features 117 GIM_CheckFeatures, 118 119 /// Check the opcode on the specified instruction 120 /// - InsnID(ULEB128) - Instruction ID 121 /// - Opc(2) - Expected opcode 122 GIM_CheckOpcode, 123 124 /// Check the opcode on the specified instruction, checking 2 acceptable 125 /// alternatives. 126 /// - InsnID(ULEB128) - Instruction ID 127 /// - Opc(2) - Expected opcode 128 /// - Opc(2) - Alternative expected opcode 129 GIM_CheckOpcodeIsEither, 130 131 /// Check the instruction has the right number of operands 132 /// - InsnID(ULEB128) - Instruction ID 133 /// - Ops(ULEB128) - Expected number of operands 134 GIM_CheckNumOperands, 135 136 /// Check an immediate predicate on the specified instruction 137 /// - InsnID(ULEB128) - Instruction ID 138 /// - Pred(2) - The predicate to test 139 GIM_CheckI64ImmPredicate, 140 /// Check an immediate predicate on the specified instruction via an APInt. 141 /// - InsnID(ULEB128) - Instruction ID 142 /// - Pred(2) - The predicate to test 143 GIM_CheckAPIntImmPredicate, 144 /// Check a floating point immediate predicate on the specified instruction. 145 /// - InsnID(ULEB128) - Instruction ID 146 /// - Pred(2) - The predicate to test 147 GIM_CheckAPFloatImmPredicate, 148 /// Check an immediate predicate on the specified instruction 149 /// - InsnID(ULEB128) - Instruction ID 150 /// - OpIdx(ULEB128) - Operand index 151 /// - Pred(2) - The predicate to test 152 GIM_CheckImmOperandPredicate, 153 154 /// Check a memory operation has the specified atomic ordering. 155 /// - InsnID(ULEB128) - Instruction ID 156 /// - Ordering(ULEB128) - The AtomicOrdering value 157 GIM_CheckAtomicOrdering, 158 GIM_CheckAtomicOrderingOrStrongerThan, 159 GIM_CheckAtomicOrderingWeakerThan, 160 161 /// Check the size of the memory access for the given machine memory operand. 162 /// - InsnID(ULEB128) - Instruction ID 163 /// - MMOIdx(ULEB128) - MMO index 164 /// - Size(4) - The size in bytes of the memory access 165 GIM_CheckMemorySizeEqualTo, 166 167 /// Check the address space of the memory access for the given machine memory 168 /// operand. 169 /// - InsnID(ULEB128) - Instruction ID 170 /// - MMOIdx(ULEB128) - MMO index 171 /// - NumAddrSpace(1) - Number of valid address spaces 172 /// - AddrSpaceN(ULEB128) - An allowed space of the memory access 173 /// - AddrSpaceN+1 ... 174 GIM_CheckMemoryAddressSpace, 175 176 /// Check the minimum alignment of the memory access for the given machine 177 /// memory operand. 178 /// - InsnID(ULEB128) - Instruction ID 179 /// - MMOIdx(ULEB128) - MMO index 180 /// - MinAlign(1) - Minimum acceptable alignment 181 GIM_CheckMemoryAlignment, 182 183 /// Check the size of the memory access for the given machine memory operand 184 /// against the size of an operand. 185 /// - InsnID(ULEB128) - Instruction ID 186 /// - MMOIdx(ULEB128) - MMO index 187 /// - OpIdx(ULEB128) - The operand index to compare the MMO against 188 GIM_CheckMemorySizeEqualToLLT, 189 GIM_CheckMemorySizeLessThanLLT, 190 GIM_CheckMemorySizeGreaterThanLLT, 191 192 /// Check if this is a vector that can be treated as a vector splat 193 /// constant. This is valid for both G_BUILD_VECTOR as well as 194 /// G_BUILD_VECTOR_TRUNC. For AllOnes refers to individual bits, so a -1 195 /// element. 196 /// - InsnID(ULEB128) - Instruction ID 197 GIM_CheckIsBuildVectorAllOnes, 198 GIM_CheckIsBuildVectorAllZeros, 199 200 /// Check a trivial predicate which takes no arguments. 201 /// This can be used by executors to implement custom flags that don't fit in 202 /// target features. 203 /// - Pred(2) - Predicate ID to check. 204 GIM_CheckSimplePredicate, 205 206 /// Check a generic C++ instruction predicate 207 /// - InsnID(ULEB128) - Instruction ID 208 /// - PredicateID(2) - The ID of the predicate function to call 209 GIM_CheckCxxInsnPredicate, 210 211 /// Check if there's no use of the first result. 212 /// - InsnID(ULEB128) - Instruction ID 213 GIM_CheckHasNoUse, 214 215 /// Check if there's one use of the first result. 216 /// - InsnID(ULEB128) - Instruction ID 217 GIM_CheckHasOneUse, 218 219 /// Check the type for the specified operand 220 /// - InsnID(ULEB128) - Instruction ID 221 /// - OpIdx(ULEB128) - Operand index 222 /// - Ty(1) - Expected type 223 GIM_CheckType, 224 /// GIM_CheckType but InsnID is omitted and defaults to zero. 225 GIM_RootCheckType, 226 227 /// Check the type of a pointer to any address space. 228 /// - InsnID(ULEB128) - Instruction ID 229 /// - OpIdx(ULEB128) - Operand index 230 /// - SizeInBits(ULEB128) - The size of the pointer value in bits. 231 GIM_CheckPointerToAny, 232 233 /// Check the register bank for the specified operand 234 /// - InsnID(ULEB128) - Instruction ID 235 /// - OpIdx(ULEB128) - Operand index 236 /// - RC(2) - Expected register bank (specified as a register class) 237 GIM_CheckRegBankForClass, 238 /// GIM_CheckRegBankForClass but InsnID is omitted and defaults to zero. 239 GIM_RootCheckRegBankForClass, 240 241 /// Check the operand matches a complex predicate 242 /// - InsnID(ULEB128) - Instruction ID 243 /// - OpIdx(ULEB128) - Operand index 244 /// - RendererID(2) - The renderer to hold the result 245 /// - Pred(2) - Complex predicate ID 246 GIM_CheckComplexPattern, 247 248 /// Check the operand is a specific integer 249 /// - InsnID(ULEB128) - Instruction ID 250 /// - OpIdx(ULEB128) - Operand index 251 /// - Val(8) Expected integer 252 GIM_CheckConstantInt, 253 254 /// Check the operand is a specific 8-bit signed integer 255 /// - InsnID(ULEB128) - Instruction ID 256 /// - OpIdx(ULEB128) - Operand index 257 /// - Val(1) Expected integer 258 GIM_CheckConstantInt8, 259 260 /// Check the operand is a specific literal integer (i.e. MO.isImm() or 261 /// MO.isCImm() is true). 262 /// - InsnID(ULEB128) - Instruction ID 263 /// - OpIdx(ULEB128) - Operand index 264 /// - Val(8) - Expected integer 265 GIM_CheckLiteralInt, 266 267 /// Check the operand is a specific intrinsic ID 268 /// - InsnID(ULEB128) - Instruction ID 269 /// - OpIdx(ULEB128) - Operand index 270 /// - IID(2) - Expected Intrinsic ID 271 GIM_CheckIntrinsicID, 272 273 /// Check the operand is a specific predicate 274 /// - InsnID(ULEB128) - Instruction ID 275 /// - OpIdx(ULEB128) - Operand index 276 /// - Pred(2) - Expected predicate 277 GIM_CheckCmpPredicate, 278 279 /// Check the specified operand is an MBB 280 /// - InsnID(ULEB128) - Instruction ID 281 /// - OpIdx(ULEB128) - Operand index 282 GIM_CheckIsMBB, 283 284 /// Check the specified operand is an Imm 285 /// - InsnID(ULEB128) - Instruction ID 286 /// - OpIdx(ULEB128) - Operand index 287 GIM_CheckIsImm, 288 289 /// Checks if the matched instructions numbered [1, 1+N) can 290 /// be folded into the root (inst 0). 291 /// - Num(1) 292 GIM_CheckIsSafeToFold, 293 294 /// Check the specified operands are identical. 295 /// The IgnoreCopies variant looks through COPY instructions before 296 /// comparing the operands. 297 /// - InsnID(ULEB128) - Instruction ID 298 /// - OpIdx(ULEB128) - Operand index 299 /// - OtherInsnID(ULEB128) - Other instruction ID 300 /// - OtherOpIdx(ULEB128) - Other operand index 301 GIM_CheckIsSameOperand, 302 GIM_CheckIsSameOperandIgnoreCopies, 303 304 /// Check we can replace all uses of a register with another. 305 /// - OldInsnID(ULEB128) 306 /// - OldOpIdx(ULEB128) 307 /// - NewInsnID(ULEB128) 308 /// - NewOpIdx(ULEB128) 309 GIM_CheckCanReplaceReg, 310 311 /// Check that a matched instruction has, or doesn't have a MIFlag. 312 /// 313 /// - InsnID(ULEB128) - Instruction to check. 314 /// - Flags(4) - (can be one or more flags OR'd together) 315 GIM_MIFlags, 316 GIM_MIFlagsNot, 317 318 /// Predicates with 'let PredicateCodeUsesOperands = 1' need to examine some 319 /// named operands that will be recorded in RecordedOperands. Names of these 320 /// operands are referenced in predicate argument list. Emitter determines 321 /// StoreIdx(corresponds to the order in which names appear in argument list). 322 /// - InsnID(ULEB128) - Instruction ID 323 /// - OpIdx(ULEB128) - Operand index 324 /// - StoreIdx(ULEB128) - Store location in RecordedOperands. 325 GIM_RecordNamedOperand, 326 327 /// Records an operand's register type into the set of temporary types. 328 /// - InsnID(ULEB128) - Instruction ID 329 /// - OpIdx(ULEB128) - Operand index 330 /// - TempTypeIdx(1) - Temp Type Index, always negative. 331 GIM_RecordRegType, 332 333 /// Fail the current try-block, or completely fail to match if there is no 334 /// current try-block. 335 GIM_Reject, 336 337 //=== Renderers === 338 339 /// Mutate an instruction 340 /// - NewInsnID(ULEB128) - Instruction ID to define 341 /// - OldInsnID(ULEB128) - Instruction ID to mutate 342 /// - NewOpcode(2) - The new opcode to use 343 GIR_MutateOpcode, 344 345 /// Build a new instruction 346 /// - InsnID(ULEB128) - Instruction ID to define 347 /// - Opcode(2) - The new opcode to use 348 GIR_BuildMI, 349 /// GIR_BuildMI but InsnID is omitted and defaults to zero. 350 GIR_BuildRootMI, 351 352 /// Builds a constant and stores its result in a TempReg. 353 /// - TempRegID(ULEB128) - Temp Register to define. 354 /// - Imm(8) - The immediate to add 355 GIR_BuildConstant, 356 357 /// Copy an operand to the specified instruction 358 /// - NewInsnID(ULEB128) - Instruction ID to modify 359 /// - OldInsnID(ULEB128) - Instruction ID to copy from 360 /// - OpIdx(ULEB128) - The operand to copy 361 GIR_Copy, 362 /// GIR_Copy but with both New/OldInsnIDs omitted and defaulting to zero. 363 GIR_RootToRootCopy, 364 365 /// Copy an operand to the specified instruction or add a zero register if the 366 /// operand is a zero immediate. 367 /// - NewInsnID(ULEB128) - Instruction ID to modify 368 /// - OldInsnID(ULEB128) - Instruction ID to copy from 369 /// - OpIdx(ULEB128) - The operand to copy 370 /// - ZeroReg(2) - The zero register to use 371 GIR_CopyOrAddZeroReg, 372 /// Copy an operand to the specified instruction 373 /// - NewInsnID(ULEB128) - Instruction ID to modify 374 /// - OldInsnID(ULEB128) - Instruction ID to copy from 375 /// - OpIdx(ULEB128) - The operand to copy 376 /// - SubRegIdx(2) - The subregister to copy 377 GIR_CopySubReg, 378 379 /// Add an implicit register def to the specified instruction 380 /// - InsnID(ULEB128) - Instruction ID to modify 381 /// - RegNum(2) - The register to add 382 /// - Flags(2) - Register Flags 383 GIR_AddImplicitDef, 384 /// Add an implicit register use to the specified instruction 385 /// - InsnID(ULEB128) - Instruction ID to modify 386 /// - RegNum(2) - The register to add 387 GIR_AddImplicitUse, 388 /// Add an register to the specified instruction 389 /// - InsnID(ULEB128) - Instruction ID to modify 390 /// - RegNum(2) - The register to add 391 /// - Flags(2) - Register Flags 392 GIR_AddRegister, 393 394 /// Adds an intrinsic ID to the specified instruction. 395 /// - InsnID(ULEB128) - Instruction ID to modify 396 /// - IID(2) - Intrinsic ID 397 GIR_AddIntrinsicID, 398 399 /// Marks the implicit def of a register as dead. 400 /// - InsnID(ULEB128) - Instruction ID to modify 401 /// - OpIdx(ULEB128) - The implicit def operand index 402 /// 403 /// OpIdx starts at 0 for the first implicit def. 404 GIR_SetImplicitDefDead, 405 406 /// Set or unset a MIFlag on an instruction. 407 /// 408 /// - InsnID(ULEB128) - Instruction to modify. 409 /// - Flags(4) - (can be one or more flags OR'd together) 410 GIR_SetMIFlags, 411 GIR_UnsetMIFlags, 412 413 /// Copy the MIFlags of a matched instruction into an 414 /// output instruction. The flags are OR'd together. 415 /// 416 /// - InsnID(ULEB128) - Instruction to modify. 417 /// - OldInsnID(ULEB128) - Matched instruction to copy flags from. 418 GIR_CopyMIFlags, 419 420 /// Add a temporary register to the specified instruction 421 /// - InsnID(ULEB128) - Instruction ID to modify 422 /// - TempRegID(ULEB128) - The temporary register ID to add 423 /// - TempRegFlags(2) - The register flags to set 424 GIR_AddTempRegister, 425 426 /// Add a temporary register to the specified instruction without 427 /// setting any flags. 428 /// - InsnID(ULEB128) - Instruction ID to modify 429 /// - TempRegID(ULEB128) - The temporary register ID to add 430 GIR_AddSimpleTempRegister, 431 432 /// Add a temporary register to the specified instruction 433 /// - InsnID(ULEB128) - Instruction ID to modify 434 /// - TempRegID(ULEB128) - The temporary register ID to add 435 /// - TempRegFlags(2) - The register flags to set 436 /// - SubRegIndex(2) - The subregister index to set 437 GIR_AddTempSubRegister, 438 439 /// Add an immediate to the specified instruction 440 /// - InsnID(ULEB128) - Instruction ID to modify 441 /// - Imm(8) - The immediate to add 442 GIR_AddImm, 443 444 /// Add signed 8 bit immediate to the specified instruction 445 /// - InsnID(ULEB128) - Instruction ID to modify 446 /// - Imm(1) - The immediate to add 447 GIR_AddImm8, 448 449 /// Add an CImm to the specified instruction 450 /// - InsnID(ULEB128) - Instruction ID to modify 451 /// - Ty(1) - Type of the constant immediate. 452 /// - Imm(8) - The immediate to add 453 GIR_AddCImm, 454 455 /// Render complex operands to the specified instruction 456 /// - InsnID(ULEB128) - Instruction ID to modify 457 /// - RendererID(2) - The renderer to call 458 GIR_ComplexRenderer, 459 /// Render sub-operands of complex operands to the specified instruction 460 /// - InsnID(ULEB128) - Instruction ID to modify 461 /// - RendererID(2) - The renderer to call 462 /// - RenderOpID(ULEB128) - The suboperand to render. 463 GIR_ComplexSubOperandRenderer, 464 /// Render subregisters of suboperands of complex operands to the 465 /// specified instruction 466 /// - InsnID(ULEB128) - Instruction ID to modify 467 /// - RendererID(2) - The renderer to call 468 /// - RenderOpID(ULEB128) - The suboperand to render 469 /// - SubRegIdx(2) - The subregister to extract 470 GIR_ComplexSubOperandSubRegRenderer, 471 472 /// Render operands to the specified instruction using a custom function 473 /// - InsnID(ULEB128) - Instruction ID to modify 474 /// - OldInsnID(ULEB128) - Instruction ID to get the matched operand from 475 /// - RendererFnID(2) - Custom renderer function to call 476 GIR_CustomRenderer, 477 478 /// Calls a C++ function that concludes the current match. 479 /// The C++ function is free to return false and reject the match, or 480 /// return true and mutate the instruction(s) (or do nothing, even). 481 /// - FnID(2) - The function to call. 482 GIR_DoneWithCustomAction, 483 484 /// Render operands to the specified instruction using a custom function, 485 /// reading from a specific operand. 486 /// - InsnID(ULEB128) - Instruction ID to modify 487 /// - OldInsnID(ULEB128) - Instruction ID to get the matched operand from 488 /// - OpIdx(ULEB128) - Operand index in OldInsnID the render function should 489 /// read 490 /// from.. 491 /// - RendererFnID(2) - Custom renderer function to call 492 GIR_CustomOperandRenderer, 493 494 /// Render a G_CONSTANT operator as a sign-extended immediate. 495 /// - NewInsnID(ULEB128) - Instruction ID to modify 496 /// - OldInsnID(ULEB128) - Instruction ID to copy from 497 /// The operand index is implicitly 1. 498 GIR_CopyConstantAsSImm, 499 500 /// Render a G_FCONSTANT operator as a sign-extended immediate. 501 /// - NewInsnID(ULEB128) - Instruction ID to modify 502 /// - OldInsnID(ULEB128) - Instruction ID to copy from 503 /// The operand index is implicitly 1. 504 GIR_CopyFConstantAsFPImm, 505 506 /// Constrain an instruction operand to a register class. 507 /// - InsnID(ULEB128) - Instruction ID to modify 508 /// - OpIdx(ULEB128) - Operand index 509 /// - RCEnum(2) - Register class enumeration value 510 GIR_ConstrainOperandRC, 511 512 /// Constrain an instructions operands according to the instruction 513 /// description. 514 /// - InsnID(ULEB128) - Instruction ID to modify 515 GIR_ConstrainSelectedInstOperands, 516 /// GIR_ConstrainSelectedInstOperands but InsnID is omitted and defaults to 517 /// zero. 518 GIR_RootConstrainSelectedInstOperands, 519 520 /// Merge all memory operands into instruction. 521 /// - InsnID(ULEB128) - Instruction ID to modify 522 /// - NumInsnID(1) - Number of instruction IDs following this argument 523 /// - MergeInsnID(ULEB128)... - One or more Instruction ID to merge into the 524 /// result. 525 GIR_MergeMemOperands, 526 527 /// Erase from parent. 528 /// - InsnID(ULEB128) - Instruction ID to erase 529 GIR_EraseFromParent, 530 531 /// Combines both a GIR_EraseFromParent 0 + GIR_Done 532 GIR_EraseRootFromParent_Done, 533 534 /// Create a new temporary register that's not constrained. 535 /// - TempRegID(ULEB128) - The temporary register ID to initialize. 536 /// - Ty(1) - Expected type 537 GIR_MakeTempReg, 538 539 /// Replaces all references to a register from an instruction 540 /// with another register from another instruction. 541 /// - OldInsnID(ULEB128) 542 /// - OldOpIdx(ULEB128) 543 /// - NewInsnID(ULEB128) 544 /// - NewOpIdx(ULEB128) 545 GIR_ReplaceReg, 546 547 /// Replaces all references to a register with a temporary register. 548 /// - OldInsnID(ULEB128) 549 /// - OldOpIdx(ULEB128) 550 /// - TempRegIdx(ULEB128) 551 GIR_ReplaceRegWithTempReg, 552 553 /// A successful emission 554 GIR_Done, 555 556 /// Increment the rule coverage counter. 557 /// - RuleID(4) - The ID of the rule that was covered. 558 GIR_Coverage, 559 560 /// Keeping track of the number of the GI opcodes. Must be the last entry. 561 GIU_NumOpcodes, 562 }; 563 564 /// Provides the logic to execute GlobalISel match tables, which are used by the 565 /// instruction selector and instruction combiners as their engine to match and 566 /// apply MIR patterns. 567 class GIMatchTableExecutor { 568 public: 569 virtual ~GIMatchTableExecutor() = default; 570 571 CodeGenCoverage *CoverageInfo = nullptr; 572 GISelKnownBits *KB = nullptr; 573 MachineFunction *MF = nullptr; 574 ProfileSummaryInfo *PSI = nullptr; 575 BlockFrequencyInfo *BFI = nullptr; 576 // For some predicates, we need to track the current MBB. 577 MachineBasicBlock *CurMBB = nullptr; 578 579 virtual void setupGeneratedPerFunctionState(MachineFunction &MF) = 0; 580 581 /// Setup per-MF executor state. 582 virtual void setupMF(MachineFunction &mf, GISelKnownBits *kb, 583 CodeGenCoverage *covinfo = nullptr, 584 ProfileSummaryInfo *psi = nullptr, 585 BlockFrequencyInfo *bfi = nullptr) { 586 CoverageInfo = covinfo; 587 KB = kb; 588 MF = &mf; 589 PSI = psi; 590 BFI = bfi; 591 CurMBB = nullptr; 592 setupGeneratedPerFunctionState(mf); 593 } 594 595 protected: 596 using ComplexRendererFns = 597 std::optional<SmallVector<std::function<void(MachineInstrBuilder &)>, 4>>; 598 using RecordedMIVector = SmallVector<MachineInstr *, 4>; 599 using NewMIVector = SmallVector<MachineInstrBuilder, 4>; 600 601 struct MatcherState { 602 std::vector<ComplexRendererFns::value_type> Renderers; 603 RecordedMIVector MIs; 604 DenseMap<unsigned, unsigned> TempRegisters; 605 /// Named operands that predicate with 'let PredicateCodeUsesOperands = 1' 606 /// referenced in its argument list. Operands are inserted at index set by 607 /// emitter, it corresponds to the order in which names appear in argument 608 /// list. Currently such predicates don't have more then 3 arguments. 609 std::array<const MachineOperand *, 3> RecordedOperands; 610 611 /// Types extracted from an instruction's operand. 612 /// Whenever a type index is negative, we look here instead. 613 SmallVector<LLT, 4> RecordedTypes; 614 615 MatcherState(unsigned MaxRenderers); 616 }; 617 shouldOptForSize(const MachineFunction * MF)618 bool shouldOptForSize(const MachineFunction *MF) const { 619 const auto &F = MF->getFunction(); 620 return F.hasOptSize() || F.hasMinSize() || 621 (PSI && BFI && CurMBB && llvm::shouldOptForSize(*CurMBB, PSI, BFI)); 622 } 623 624 public: 625 template <class PredicateBitset, class ComplexMatcherMemFn, 626 class CustomRendererFn> 627 struct ExecInfoTy { ExecInfoTyExecInfoTy628 ExecInfoTy(const LLT *TypeObjects, size_t NumTypeObjects, 629 const PredicateBitset *FeatureBitsets, 630 const ComplexMatcherMemFn *ComplexPredicates, 631 const CustomRendererFn *CustomRenderers) 632 : TypeObjects(TypeObjects), FeatureBitsets(FeatureBitsets), 633 ComplexPredicates(ComplexPredicates), 634 CustomRenderers(CustomRenderers) { 635 636 for (size_t I = 0; I < NumTypeObjects; ++I) 637 TypeIDMap[TypeObjects[I]] = I; 638 } 639 const LLT *TypeObjects; 640 const PredicateBitset *FeatureBitsets; 641 const ComplexMatcherMemFn *ComplexPredicates; 642 const CustomRendererFn *CustomRenderers; 643 644 SmallDenseMap<LLT, unsigned, 64> TypeIDMap; 645 }; 646 647 protected: 648 GIMatchTableExecutor(); 649 650 /// Execute a given matcher table and return true if the match was successful 651 /// and false otherwise. 652 template <class TgtExecutor, class PredicateBitset, class ComplexMatcherMemFn, 653 class CustomRendererFn> 654 bool executeMatchTable(TgtExecutor &Exec, MatcherState &State, 655 const ExecInfoTy<PredicateBitset, ComplexMatcherMemFn, 656 CustomRendererFn> &ExecInfo, 657 MachineIRBuilder &Builder, const uint8_t *MatchTable, 658 const TargetInstrInfo &TII, MachineRegisterInfo &MRI, 659 const TargetRegisterInfo &TRI, 660 const RegisterBankInfo &RBI, 661 const PredicateBitset &AvailableFeatures, 662 CodeGenCoverage *CoverageInfo) const; 663 getMatchTable()664 virtual const uint8_t *getMatchTable() const { 665 llvm_unreachable("Should have been overridden by tablegen if used"); 666 } 667 testImmPredicate_I64(unsigned,int64_t)668 virtual bool testImmPredicate_I64(unsigned, int64_t) const { 669 llvm_unreachable( 670 "Subclasses must override this with a tablegen-erated function"); 671 } testImmPredicate_APInt(unsigned,const APInt &)672 virtual bool testImmPredicate_APInt(unsigned, const APInt &) const { 673 llvm_unreachable( 674 "Subclasses must override this with a tablegen-erated function"); 675 } testImmPredicate_APFloat(unsigned,const APFloat &)676 virtual bool testImmPredicate_APFloat(unsigned, const APFloat &) const { 677 llvm_unreachable( 678 "Subclasses must override this with a tablegen-erated function"); 679 } testMIPredicate_MI(unsigned,const MachineInstr &,const MatcherState & State)680 virtual bool testMIPredicate_MI(unsigned, const MachineInstr &, 681 const MatcherState &State) const { 682 llvm_unreachable( 683 "Subclasses must override this with a tablegen-erated function"); 684 } 685 testSimplePredicate(unsigned)686 virtual bool testSimplePredicate(unsigned) const { 687 llvm_unreachable("Subclass does not implement testSimplePredicate!"); 688 } 689 runCustomAction(unsigned,const MatcherState & State,NewMIVector & OutMIs)690 virtual bool runCustomAction(unsigned, const MatcherState &State, 691 NewMIVector &OutMIs) const { 692 llvm_unreachable("Subclass does not implement runCustomAction!"); 693 } 694 695 bool isOperandImmEqual(const MachineOperand &MO, int64_t Value, 696 const MachineRegisterInfo &MRI, 697 bool Splat = false) const; 698 699 /// Return true if the specified operand is a G_PTR_ADD with a G_CONSTANT on 700 /// the right-hand side. GlobalISel's separation of pointer and integer types 701 /// means that we don't need to worry about G_OR with equivalent semantics. 702 bool isBaseWithConstantOffset(const MachineOperand &Root, 703 const MachineRegisterInfo &MRI) const; 704 705 /// Return true if MI can obviously be folded into IntoMI. 706 /// MI and IntoMI do not need to be in the same basic blocks, but MI must 707 /// preceed IntoMI. 708 bool isObviouslySafeToFold(MachineInstr &MI, MachineInstr &IntoMI) const; 709 readBytesAs(const uint8_t * MatchTable)710 template <typename Ty> static Ty readBytesAs(const uint8_t *MatchTable) { 711 Ty Ret; 712 memcpy(&Ret, MatchTable, sizeof(Ret)); 713 return Ret; 714 } 715 716 public: 717 // Faster ULEB128 decoder tailored for the Match Table Executor. 718 // 719 // - Arguments are fixed to avoid mid-function checks. 720 // - Unchecked execution, assumes no error. 721 // - Fast common case handling (1 byte values). 722 LLVM_ATTRIBUTE_ALWAYS_INLINE static uint64_t fastDecodeULEB128(const uint8_t * LLVM_ATTRIBUTE_RESTRICT MatchTable,uint64_t & CurrentIdx)723 fastDecodeULEB128(const uint8_t *LLVM_ATTRIBUTE_RESTRICT MatchTable, 724 uint64_t &CurrentIdx) { 725 uint64_t Value = MatchTable[CurrentIdx++]; 726 if (LLVM_UNLIKELY(Value >= 128)) { 727 Value &= 0x7f; 728 unsigned Shift = 7; 729 do { 730 uint64_t Slice = MatchTable[CurrentIdx] & 0x7f; 731 Value += Slice << Shift; 732 Shift += 7; 733 } while (MatchTable[CurrentIdx++] >= 128); 734 } 735 return Value; 736 } 737 }; 738 739 } // end namespace llvm 740 741 #endif // LLVM_CODEGEN_GLOBALISEL_GIMATCHTABLEEXECUTOR_H 742