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