686 lines · plain
1 2.. _tblgen-mirpats:3 4========================5MIR Patterns in TableGen6========================7 8.. contents::9 :local:10 11 12User's Guide13============14 15This section is intended for developers who want to use MIR patterns in their16TableGen files.17 18``NOTE``:19This feature is still in active development. This document may become outdated20over time. If you see something that's incorrect, please update it.21 22Use Cases23---------24 25MIR patterns are supported in the following places:26 27* GlobalISel ``GICombineRule``28* GlobalISel ``GICombinePatFrag``29 30Syntax31------32 33MIR patterns use the DAG datatype in TableGen.34 35.. code-block:: text36 37 (inst operand0, operand1, ...)38 39``inst`` must be a def which inherits from ``Instruction`` (e.g. ``G_FADD``),40``Intrinsic`` or ``GICombinePatFrag``.41 42Operands essentially fall into one of two categories:43 44* immediates45 46 * untyped, unnamed: ``0``47 * untyped, named: ``0:$y``48 * typed, unnamed: ``(i32 0)``49 * typed, named: ``(i32 0):$y``50 51* machine operands52 53 * untyped: ``$x``54 * typed: ``i32:$x``55 56Semantics:57 58* A typed operand always adds an operand type check to the matcher.59* There is a trivial type inference system to propagate types.60 61 * e.g. You only need to use ``i32:$x`` once in any pattern of a62 ``GICombinePatFrag`` alternative or ``GICombineRule``, then all63 other patterns in that rule/alternative can simply use ``$x``64 (``i32:$x`` is redundant).65 66* A named operand's behavior depends on whether the name has been seen before.67 68 * For match patterns, reusing an operand name checks that the operands69 are identical (see example 2 below).70 * For apply patterns, reusing an operand name simply copies that operand into71 the new instruction (see example 2 below).72 73Operands are ordered just like they would be in a MachineInstr: the defs (outs)74come first, then the uses (ins).75 76Patterns are generally grouped into another DAG datatype with a dummy operator77such as ``match``, ``apply``, ``combine`` or ``pattern``.78 79Finally, any DAG datatype in TableGen can be named. This also holds for80patterns. e.g. the following is valid: ``(G_FOO $root, (i32 0):$cst):$mypat``.81This may also be helpful to debug issues. Patterns are *always* named, and if82they don't have a name, an "anonymous" one is given to them. If you're trying83to debug an error related to a MIR pattern, but the error mentions an anonymous84pattern, you can try naming your patterns to see exactly where the issue is.85 86.. code-block:: text87 :caption: Pattern Example 188 89 // Match90 // %imp = G_IMPLICIT_DEF91 // %root = G_MUL %x, %imp92 (match (G_IMPLICIT_DEF $imp),93 (G_MUL $root, $x, $imp))94 95.. code-block:: text96 :caption: Pattern Example 297 98 // using $x twice here checks that the operand 1 and 2 of the G_AND are99 // identical.100 (match (G_AND $root, $x, $x))101 // using $x again here copies operand 1 from G_AND into the new inst.102 (apply (COPY $root, $x))103 104Types105-----106 107ValueType108~~~~~~~~~109 110Subclasses of ``ValueType`` are valid types, e.g. ``i32``.111 112GITypeOf113~~~~~~~~114 115``GITypeOf<"$x">`` is a ``GISpecialType`` that allows for the creation of a116register or immediate with the same type as another (register) operand.117 118Type Parameters:119 120* An operand name as a string, prefixed by ``$``.121 122Semantics:123 124* Can only appear in an 'apply' pattern.125* The operand name used must appear in the 'match' pattern of the126 same ``GICombineRule``.127 128.. code-block:: text129 :caption: Example: Immediate130 131 def mul_by_neg_one: GICombineRule <132 (defs root:$root),133 (match (G_MUL $dst, $x, -1)),134 (apply (G_SUB $dst, (GITypeOf<"$x"> 0), $x))135 >;136 137.. code-block:: text138 :caption: Example: Temp Reg139 140 def Test0 : GICombineRule<141 (defs root:$dst),142 (match (G_FMUL $dst, $src, -1)),143 (apply (G_FSUB $dst, $src, $tmp),144 (G_FNEG GITypeOf<"$dst">:$tmp, $src))>;145 146GIVariadic147~~~~~~~~~~148 149``GIVariadic<>`` is a ``GISpecialType`` that allows for matching 1 or150more operands remaining on an instruction.151 152Type Parameters:153 154* The minimum number of additional operands to match. Must be greater than zero.155 156 * Default is 1.157 158* The maximum number of additional operands to match. Must be strictly greater159 than the minimum.160 161 * 0 can be used to indicate there is no upper limit.162 * Default is 0.163 164Semantics:165 166* ``GIVariadic<>`` operands can only appear on variadic instructions.167* ``GIVariadic<>`` operands cannot be defs.168* ``GIVariadic<>`` operands can only appear as the last operand in a 'match' pattern.169* Each instance within a 'match' pattern must be uniquely named.170* Re-using a ``GIVariadic<>`` operand in an 'apply' pattern will result in all171 the matched operands being copied from the original instruction.172* The min/max operands will result in the matcher checking that the number of operands173 falls within that range.174* ``GIVariadic<>`` operands can be used in C++ code within a rule, which will175 result in the operand name being expanded to a value of type ``ArrayRef<MachineOperand>``.176 177.. code-block:: text178 179 // bool checkBuildVectorToUnmerge(ArrayRef<MachineOperand>);180 181 def build_vector_to_unmerge: GICombineRule <182 (defs root:$root),183 (match (G_BUILD_VECTOR $root, GIVariadic<>:$args),184 [{ return checkBuildVectorToUnmerge(${args}); }]),185 (apply (G_UNMERGE_VALUES $root, $args))186 >;187 188.. code-block:: text189 190 // Will additionally check the number of operands is >= 3 and <= 5.191 // ($root is one operand, then 2 to 4 variadic operands).192 def build_vector_to_unmerge: GICombineRule <193 (defs root:$root),194 (match (G_BUILD_VECTOR $root, GIVariadic<2, 4>:$two_to_four),195 [{ return checkBuildVectorToUnmerge(${two_to_four}); }]),196 (apply (G_UNMERGE_VALUES $root, $two_to_four))197 >;198 199Builtin Operations200------------------201 202MIR Patterns also offer builtin operations, also called "builtin instructions".203They offer some powerful features that would otherwise require use of C++ code.204 205GIReplaceReg206~~~~~~~~~~~~207 208.. code-block:: text209 :caption: Usage210 211 (apply (GIReplaceReg $old, $new))212 213Operands:214 215* ``$old`` (out) register defined by a matched instruction216* ``$new`` (in) register217 218Semantics:219 220* Can only appear in an 'apply' pattern.221* If both old/new are operands of matched instructions,222 ``canReplaceReg`` is checked before applying the rule.223 224 225GIEraseRoot226~~~~~~~~~~~227 228.. code-block:: text229 :caption: Usage230 231 (apply (GIEraseRoot))232 233Semantics:234 235* Can only appear as the only pattern of an 'apply' pattern list.236* The root cannot have any output operands.237* The root must be a CodeGenInstruction238 239Instruction Flags240-----------------241 242MIR Patterns support both matching & writing ``MIFlags``.243 244.. code-block:: text245 :caption: Example246 247 def Test : GICombineRule<248 (defs root:$dst),249 (match (G_FOO $dst, $src, (MIFlags FmNoNans, FmNoInfs))),250 (apply (G_BAR $dst, $src, (MIFlags FmReassoc)))>;251 252In ``apply`` patterns, we also support referring to a matched instruction to253"take" its MIFlags.254 255.. code-block:: text256 :caption: Example257 258 ; We match NoNans/NoInfs, but $zext may have more flags.259 ; Copy them all into the output instruction, and set Reassoc on the output inst.260 def TestCpyFlags : GICombineRule<261 (defs root:$dst),262 (match (G_FOO $dst, $src, (MIFlags FmNoNans, FmNoInfs)):$zext),263 (apply (G_BAR $dst, $src, (MIFlags $zext, FmReassoc)))>;264 265The ``not`` operator can be used to check that a flag is NOT present266on a matched instruction, and to remove a flag from a generated instruction.267 268.. code-block:: text269 :caption: Example270 271 ; We match NoInfs but we don't want NoNans/Reassoc to be set. $zext may have more flags.272 ; Copy them all into the output instruction but remove NoInfs on the output inst.273 def TestNot : GICombineRule<274 (defs root:$dst),275 (match (G_FOO $dst, $src, (MIFlags FmNoInfs, (not FmNoNans, FmReassoc))):$zext),276 (apply (G_BAR $dst, $src, (MIFlags $zext, (not FmNoInfs))))>;277 278Limitations279-----------280 281This a non-exhaustive list of known issues with MIR patterns at this time.282 283* Using ``GICombinePatFrag`` within another ``GICombinePatFrag`` is not284 supported.285* ``GICombinePatFrag`` can only have a single root.286* Instructions with multiple defs cannot be the root of a ``GICombinePatFrag``.287* Using ``GICombinePatFrag`` in the ``apply`` pattern of a ``GICombineRule``288 is not supported.289* We cannot rewrite a matched instruction other than the root.290* Matching/creating a (CImm) immediate >64 bits is not supported291 (see comment in ``GIM_CheckConstantInt``)292* There is currently no way to constrain two register/immediate types to293 match. e.g. if a pattern needs to work on both i32 and i64, you either294 need to leave it untyped and check the type in C++, or duplicate the295 pattern.296* ``GISpecialType`` operands are not allowed within a ``GICombinePatFrag``.297* ``GIVariadic<>`` matched operands must each have a unique name.298 299GICombineRule300-------------301 302MIR patterns can appear in the ``match`` or ``apply`` patterns of a303``GICombineRule``.304 305The ``root`` of the rule can either be a def of an instruction, or a306named pattern. The latter is helpful when the instruction you want307to match has no defs. The former is generally preferred because308it's less verbose.309 310.. code-block:: text311 :caption: Combine Rule root is a def312 313 // Fold x op 1 -> x314 def right_identity_one: GICombineRule<315 (defs root:$dst),316 (match (G_MUL $dst, $x, 1)),317 // Note: Patterns always need to create something, we can't just replace $dst with $x, so we need a COPY.318 (apply (COPY $dst, $x))319 >;320 321.. code-block:: text322 :caption: Combine Rule root is a named pattern323 324 def Foo : GICombineRule<325 (defs root:$root),326 (match (G_ZEXT $tmp, (i32 0)),327 (G_STORE $tmp, $ptr):$root),328 (apply (G_STORE (i32 0), $ptr):$root)>;329 330 331Combine Rules also allow mixing C++ code with MIR patterns, so that you332may perform additional checks when matching, or run a C++ action after333matching.334 335Note that C++ code in ``apply`` pattern is mutually exclusive with336other patterns. However, you can freely mix C++ code with other337types of patterns in ``match`` patterns.338C++ code in ``match`` patterns is always run last, after all other339patterns matched.340 341.. code-block:: text342 :caption: Apply Pattern Examples with C++ code343 344 // Valid345 def Foo : GICombineRule<346 (defs root:$root),347 (match (G_ZEXT $tmp, (i32 0)),348 (G_STORE $tmp, $ptr):$root,349 "return myFinalCheck()"),350 (apply "runMyAction(${root})")>;351 352 // error: 'apply' patterns cannot mix C++ code with other types of patterns353 def Bar : GICombineRule<354 (defs root:$dst),355 (match (G_ZEXT $dst, $src):$mi),356 (apply (G_MUL $dst, $src, $src),357 "runMyAction(${root})")>;358 359The following expansions are available for MIR patterns:360 361* operand names (``MachineOperand &``)362* pattern names (``MachineInstr *`` for ``match``,363 ``MachineInstrBuilder &`` for apply)364 365.. code-block:: text366 :caption: Example C++ Expansions367 368 def Foo : GICombineRule<369 (defs root:$root),370 (match (G_ZEXT $root, $src):$mi),371 (apply "foobar(${root}.getReg(), ${src}.getReg(), ${mi}->hasImplicitDef())")>;372 373``combine`` Operator374~~~~~~~~~~~~~~~~~~~~375 376``GICombineRule`` also supports a single ``combine`` pattern, which is a shorter way to377declare patterns that just match one or more instructions, then defer all remaining matching378and rewriting logic to C++ code.379 380.. code-block:: text381 :caption: Example usage of the combine operator.382 383 // match + apply384 def FooLong : GICombineRule<385 (defs root:$root),386 (match (G_ZEXT $root, $src):$mi, "return matchFoo(${mi});"),387 (apply "applyFoo(${mi});")>;388 389 // combine390 def FooShort : GICombineRule<391 (defs root:$root),392 (combine (G_ZEXT $root, $src):$mi, "return combineFoo(${mi});")>;393 394This has a couple of advantages:395 396* We only need one C++ function, not two.397* We no longer need to use ``GIDefMatchData`` to pass information between the match/apply functions.398 399As described above, this is syntactic sugar for the match+apply form. In a ``combine`` pattern:400 401* Everything except C++ code is considered the ``match`` part.402* The C++ code is the ``apply`` part. C++ code is emitted in order of appearance.403 404.. note::405 406 The C++ code **must** return true if it changed any instruction. Returning false when changing407 instructions is undefined behavior.408 409Common Pattern #1: Replace a Register with Another410~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~411 412The 'apply' pattern must always redefine all operands defined by the match root.413Sometimes, we do not need to create instructions, simply replace a def with414another matched register. The ``GIReplaceReg`` builtin can do just that.415 416.. code-block:: text417 418 def Foo : GICombineRule<419 (defs root:$dst),420 (match (G_FNEG $tmp, $src), (G_FNEG $dst, $tmp)),421 (apply (GIReplaceReg $dst, $src))>;422 423This also works if the replacement register is a temporary register from the424``apply`` pattern.425 426.. code-block:: text427 428 def ReplaceTemp : GICombineRule<429 (defs root:$a),430 (match (G_BUILD_VECTOR $tmp, $x, $y),431 (G_UNMERGE_VALUES $a, $b, $tmp)),432 (apply (G_UNMERGE_VALUES $a, i32:$new, $y),433 (GIReplaceReg $b, $new))>434 435Common Pattern #2: Erasing a Def-less Root436~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~437 438If we simply want to erase a def-less match root, we can use the439``GIEraseRoot`` builtin.440 441.. code-block:: text442 443 def Foo : GICombineRule<444 (defs root:$mi),445 (match (G_STORE $a, $b):$mi),446 (apply (GIEraseRoot))>;447 448Common Pattern #3: Emitting a Constant Value449~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~450 451When an immediate operand appears in an 'apply' pattern, the behavior452depends on whether it's typed or not.453 454* If the immediate is typed, ``MachineIRBuilder::buildConstant`` is used455 to create a ``G_CONSTANT``. A ``G_BUILD_VECTOR`` will be used for vectors.456* If the immediate is untyped, a simple immediate is added457 (``MachineInstrBuilder::addImm``).458 459There is of course a special case for ``G_CONSTANT``. Immediates for460``G_CONSTANT`` must always be typed, and a CImm is added461(``MachineInstrBuilder::addCImm``).462 463.. code-block:: text464 :caption: Constant Emission Examples:465 466 // Example output:467 // %0 = G_CONSTANT i32 0468 // %dst = COPY %0469 def Foo : GICombineRule<470 (defs root:$dst),471 (match (G_FOO $dst, $src)),472 (apply (COPY $dst, (i32 0)))>;473 474 // Example output:475 // %dst = COPY 0476 // Note that this would be ill-formed because COPY477 // expects a register operand!478 def Bar : GICombineRule<479 (defs root:$dst),480 (match (G_FOO $dst, $src)),481 (apply (COPY $dst, (i32 0)))>;482 483 // Example output:484 // %dst = G_CONSTANT i32 0485 def Bux : GICombineRule<486 (defs root:$dst),487 (match (G_FOO $dst, $src)),488 (apply (G_CONSTANT $dst, (i32 0)))>;489 490GICombinePatFrag491----------------492 493``GICombinePatFrag`` is an equivalent of ``PatFrags`` for MIR patterns.494They have two main usecases:495 496* Reduce repetition by creating a ``GICombinePatFrag`` for common497 patterns (see example 1).498* Implicitly duplicate a CombineRule for multiple variants of a499 pattern (see example 2).500 501A ``GICombinePatFrag`` is composed of three elements:502 503* zero or more ``in`` (def) parameter504* zero or more ``out`` parameter505* A list of MIR patterns that can match.506 507 * When a ``GICombinePatFrag`` is used within a pattern, the pattern is508 cloned once for each alternative that can match.509 510Parameters can have the following types:511 512* ``gi_mo``, which is the implicit default (no type = ``gi_mo``).513 514 * Refers to any operand of an instruction (register, BB ref, imm, etc.).515 * Can be used in both ``in`` and ``out`` parameters.516 * Users of the PatFrag can only use an operand name for this517 parameter (e.g. ``(my_pat_frag $foo)``).518 519* ``root``520 521 * This is identical to ``gi_mo``.522 * Can only be used in ``out`` parameters to declare the root of the523 pattern.524 * Non-empty ``out`` parameter lists must always have exactly one ``root``.525 526* ``gi_imm``527 528 * Refers to an (potentially typed) immediate.529 * Can only be used in ``in`` parameters.530 * Users of the PatFrag can only use an immediate for this parameter531 (e.g. ``(my_pat_frag 0)`` or ``(my_pat_frag (i32 0))``)532 533``out`` operands can only be empty if the ``GICombinePatFrag`` only contains534C++ code. If the fragment contains instruction patterns, it has to have at535least one ``out`` operand of type ``root``.536 537``in`` operands are less restricted, but there is one important concept to538remember: you can pass "unbound" operand names, but only if the539``GICombinePatFrag`` binds it. See example 3 below.540 541``GICombinePatFrag`` are used just like any other instructions.542Note that the ``out`` operands are defs, so they come first in the list543of operands.544 545.. code-block:: text546 :caption: Example 1: Reduce Repetition547 548 def zext_cst : GICombinePatFrag<(outs root:$dst, $cst), (ins gi_imm:$val),549 [(pattern (G_CONSTANT $cst, $val),550 (G_ZEXT $dst, $cst))]551 >;552 553 def foo_to_impdef : GICombineRule<554 (defs root:$dst),555 (match (zext_cst $y, $cst, (i32 0))556 (G_FOO $dst, $y)),557 (apply (G_IMPLICIT_DEF $dst))>;558 559 def store_ext_zero : GICombineRule<560 (defs root:$root),561 (match (zext_cst $y, $cst, (i32 0))562 (G_STORE $y, $ptr):$root),563 (apply (G_STORE $cst, $ptr):$root)>;564 565.. code-block:: text566 :caption: Example 2: Generate Multiple Rules at Once567 568 // Fold (freeze (freeze x)) -> (freeze x).569 // Fold (fabs (fabs x)) -> (fabs x).570 // Fold (fcanonicalize (fcanonicalize x)) -> (fcanonicalize x).571 def idempotent_prop_frags : GICombinePatFrag<(outs root:$dst, $src), (ins),572 [573 (pattern (G_FREEZE $dst, $src), (G_FREEZE $src, $x)),574 (pattern (G_FABS $dst, $src), (G_FABS $src, $x)),575 (pattern (G_FCANONICALIZE $dst, $src), (G_FCANONICALIZE $src, $x))576 ]577 >;578 579 def idempotent_prop : GICombineRule<580 (defs root:$dst),581 (match (idempotent_prop_frags $dst, $src)),582 (apply (COPY $dst, $src))>;583 584 585 586.. code-block:: text587 :caption: Example 3: Unbound Operand Names588 589 // This fragment binds $x to an operand in all of its590 // alternative patterns.591 def always_binds : GICombinePatFrag<592 (outs root:$dst), (ins $x),593 [594 (pattern (G_FREEZE $dst, $x)),595 (pattern (G_FABS $dst, $x)),596 ]597 >;598 599 // This fragment does not bind $x to an operand in any600 // of its alternative patterns.601 def does_not_bind : GICombinePatFrag<602 (outs root:$dst), (ins $x),603 [604 (pattern (G_FREEZE $dst, $x)), // binds $x605 (pattern (G_FOO $dst (i32 0))), // does not bind $x606 (pattern "return myCheck(${x}.getReg())"), // does not bind $x607 ]608 >;609 610 // Here we pass $x, which is unbound, to always_binds.611 // This works because if $x is unbound, always_binds will bind it for us.612 def test0 : GICombineRule<613 (defs root:$dst),614 (match (always_binds $dst, $x)),615 (apply (COPY $dst, $x))>;616 617 // Here we pass $x, which is unbound, to does_not_bind.618 // This cannot work because $x may not have been initialized in 'apply'.619 // error: operand 'x' (for parameter 'src' of 'does_not_bind') cannot be unbound620 def test1 : GICombineRule<621 (defs root:$dst),622 (match (does_not_bind $dst, $x)),623 (apply (COPY $dst, $x))>;624 625 // Here we pass $x, which is bound, to does_not_bind.626 // This is fine because $x will always be bound when emitting does_not_bind627 def test2 : GICombineRule<628 (defs root:$dst),629 (match (does_not_bind $tmp, $x)630 (G_MUL $dst, $x, $tmp)),631 (apply (COPY $dst, $x))>;632 633 634 635 636Gallery637=======638 639We should use precise patterns that state our intentions. Please avoid640using wip_match_opcode in patterns. It can lead to imprecise patterns.641 642.. code-block:: text643 :caption: Example fold zext(trunc:nuw)644 645 // Imprecise: matches any G_ZEXT646 def zext : GICombineRule<647 (defs root:$root),648 (match (wip_match_opcode G_ZEXT):$root,649 [{ return Helper.matchZextOfTrunc(*${root}, ${matchinfo}); }]),650 (apply [{ Helper.applyBuildFn(*${root}, ${matchinfo}); }])>;651 652 653 // Imprecise: matches G_ZEXT of G_TRUNC654 def zext_of_trunc : GICombineRule<655 (defs root:$root),656 (match (G_TRUNC $src, $x),657 (G_ZEXT $root, $src),658 [{ return Helper.matchZextOfTrunc(${root}, ${matchinfo}); }]),659 (apply [{ Helper.applyBuildFnMO(${root}, ${matchinfo}); }])>;660 661 662 // Precise: matches G_ZEXT of G_TRUNC with nuw flag663 def zext_of_trunc_nuw : GICombineRule<664 (defs root:$root),665 (match (G_TRUNC $src, $x, (MIFlags NoUWrap)),666 (G_ZEXT $root, $src),667 [{ return Helper.matchZextOfTrunc(${root}, ${matchinfo}); }]),668 (apply [{ Helper.applyBuildFnMO(${root}, ${matchinfo}); }])>;669 670 671 // Precise: lists all combine combinations672 class ext_of_ext_opcodes<Instruction ext1Opcode, Instruction ext2Opcode> : GICombineRule <673 (defs root:$root, build_fn_matchinfo:$matchinfo),674 (match (ext2Opcode $second, $src):$Second,675 (ext1Opcode $root, $second):$First,676 [{ return Helper.matchExtOfExt(*${First}, *${Second}, ${matchinfo}); }]),677 (apply [{ Helper.applyBuildFn(*${First}, ${matchinfo}); }])>;678 679 def zext_of_zext : ext_of_ext_opcodes<G_ZEXT, G_ZEXT>;680 def zext_of_anyext : ext_of_ext_opcodes<G_ZEXT, G_ANYEXT>;681 def sext_of_sext : ext_of_ext_opcodes<G_SEXT, G_SEXT>;682 def sext_of_anyext : ext_of_ext_opcodes<G_SEXT, G_ANYEXT>;683 def anyext_of_anyext : ext_of_ext_opcodes<G_ANYEXT, G_ANYEXT>;684 def anyext_of_zext : ext_of_ext_opcodes<G_ANYEXT, G_ZEXT>;685 def anyext_of_sext : ext_of_ext_opcodes<G_ANYEXT, G_SEXT>;686