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