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