llvm/docs/GlobalISel/MIRPatterns.rst

   1
   2 .. _tblgen-mirpats:
   3
   4 ========================
   5 MIR Patterns in TableGen
   6 ========================
   7
   8 .. contents::
   9    :local:
  10
  11
  12 User's Guide
  13 ============
  14
  15 This section is intended for developers who want to use MIR patterns in their
  16 TableGen files.
  17
  18 ``NOTE``:
  19 This feature is still in active development. This document may become outdated
  20 over time. If you see something that's incorrect, please update it.
  21
  22 Use Cases
  23 ---------
  24
  25 MIR patterns are supported in the following places:
  26
  27 * GlobalISel ``GICombineRule``
  28 * GlobalISel ``GICombinePatFrag``
  29
  30 Syntax
  31 ------
  32
  33 MIR patterns use the DAG datatype in TableGen.
  34
  35 .. code-block:: text
  36
  37   (inst operand0, operand1, ...)
  38
  39 ``inst`` must be a def which inherits from ``Instruction`` (e.g. ``G_FADD``)
  40 or ``GICombinePatFrag``.
  41
  42 Operands essentially fall into one of two categories:
  43
  44 * immediates
  45
  46   * untyped, unnamed: ``0``
  47   * untyped, named: ``0:$y``
  48   * typed, unnamed: ``(i32 0)``
  49   * typed, named: ``(i32 0):$y``
  50
  51 * machine operands
  52
  53   * untyped: ``$x``
  54   * typed: ``i32:$x``
  55
  56 Semantics:
  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 a
  62     ``GICombinePatFrag`` alternative or ``GICombineRule``, then all
  63     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 operands
  69     are identical (see example 2 below).
  70   * For apply patterns, reusing an operand name simply copies that operand into
  71     the new instruction (see example 2 below).
  72
  73 Operands are ordered just like they would be in a MachineInstr: the defs (outs)
  74 come first, then the uses (ins).
  75
  76 Patterns are generally grouped into another DAG datatype with a dummy operator
  77 such as ``match``, ``apply`` or ``pattern``.
  78
  79 Finally, any DAG datatype in TableGen can be named. This also holds for
  80 patterns. e.g. the following is valid: ``(G_FOO $root, (i32 0):$cst):$mypat``.
  81 This may also be helpful to debug issues. Patterns are *always* named, and if
  82 they don't have a name, an "anonymous" one is given to them. If you're trying
  83 to debug an error related to a MIR pattern, but the error mentions an anonymous
  84 pattern, you can try naming your patterns to see exactly where the issue is.
  85
  86 .. code-block:: text
  87   :caption: Pattern Example 1
  88
  89   // Match
  90   //    %imp = G_IMPLICIT_DEF
  91   //    %root = G_MUL %x, %imp
  92   (match (G_IMPLICIT_DEF $imp),
  93          (G_MUL $root, $x, $imp))
  94
  95 .. code-block:: text
  96   :caption: Pattern Example 2
  97
  98   // using $x twice here checks that the operand 1 and 2 of the G_AND are
  99   // 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
 104 Types
 105 -----
 106
 107 ValueType
 108 ~~~~~~~~~
 109
 110 Subclasses of ``ValueType`` are valid types, e.g. ``i32``.
 111
 112 GITypeOf
 113 ~~~~~~~~
 114
 115 ``GITypeOf<"$x">`` is a ``GISpecialType`` that allows for the creation of a
 116 register or immediate with the same type as another (register) operand.
 117
 118 Operand:
 119
 120 * An operand name as a string, prefixed by ``$``.
 121
 122 Semantics:
 123
 124 * Can only appear in an 'apply' pattern.
 125 * The operand name used must appear in the 'match' pattern of the
 126   same ``GICombineRule``.
 127
 128 .. code-block:: text
 129   :caption: Example: Immediate
 130
 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:: text
 138   :caption: Example: Temp Reg
 139
 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
 146 Builtin Operations
 147 ------------------
 148
 149 MIR Patterns also offer builtin operations, also called "builtin instructions".
 150 They offer some powerful features that would otherwise require use of C++ code.
 151
 152 GIReplaceReg
 153 ~~~~~~~~~~~~
 154
 155 .. code-block:: text
 156   :caption: Usage
 157
 158   (apply (GIReplaceReg $old, $new))
 159
 160 Operands:
 161
 162 * ``$old`` (out) register defined by a matched instruction
 163 * ``$new`` (in)  register
 164
 165 Semantics:
 166
 167 * Can only appear in an 'apply' pattern.
 168 * If both old/new are operands of matched instructions,
 169   ``canReplaceReg`` is checked before applying the rule.
 170
 171
 172 GIEraseRoot
 173 ~~~~~~~~~~~
 174
 175 .. code-block:: text
 176   :caption: Usage
 177
 178   (apply (GIEraseRoot))
 179
 180 Semantics:
 181
 182 * Can only appear as the only pattern of an 'apply' pattern list.
 183 * The root cannot have any output operands.
 184 * The root must be a CodeGenInstruction
 185
 186 Instruction Flags
 187 -----------------
 188
 189 MIR Patterns support both matching & writing ``MIFlags``.
 190
 191 .. code-block:: text
 192   :caption: Example
 193
 194   def Test : GICombineRule<
 195     (defs root:$dst),
 196     (match (G_FOO $dst, $src, (MIFlags FmNoNans, FmNoInfs))),
 197     (apply (G_BAR $dst, $src, (MIFlags FmReassoc)))>;
 198
 199 In ``apply`` patterns, we also support referring to a matched instruction to
 200 "take" its MIFlags.
 201
 202 .. code-block:: text
 203   :caption: Example
 204
 205   ; We match NoNans/NoInfs, but $zext may have more flags.
 206   ; Copy them all into the output instruction, and set Reassoc on the output inst.
 207   def TestCpyFlags : GICombineRule<
 208     (defs root:$dst),
 209     (match (G_FOO $dst, $src, (MIFlags FmNoNans, FmNoInfs)):$zext),
 210     (apply (G_BAR $dst, $src, (MIFlags $zext, FmReassoc)))>;
 211
 212 The ``not`` operator can be used to check that a flag is NOT present
 213 on a matched instruction, and to remove a flag from a generated instruction.
 214
 215 .. code-block:: text
 216   :caption: Example
 217
 218   ; We match NoInfs but we don't want NoNans/Reassoc to be set. $zext may have more flags.
 219   ; Copy them all into the output instruction but remove NoInfs on the output inst.
 220   def TestNot : GICombineRule<
 221     (defs root:$dst),
 222     (match (G_FOO $dst, $src, (MIFlags FmNoInfs, (not FmNoNans, FmReassoc))):$zext),
 223     (apply (G_BAR $dst, $src, (MIFlags $zext, (not FmNoInfs))))>;
 224
 225 Limitations
 226 -----------
 227
 228 This a non-exhaustive list of known issues with MIR patterns at this time.
 229
 230 * Matching intrinsics is not yet possible.
 231 * Using ``GICombinePatFrag`` within another ``GICombinePatFrag`` is not
 232   supported.
 233 * ``GICombinePatFrag`` can only have a single root.
 234 * Instructions with multiple defs cannot be the root of a ``GICombinePatFrag``.
 235 * Using ``GICombinePatFrag`` in the ``apply`` pattern of a ``GICombineRule``
 236   is not supported.
 237 * We cannot rewrite a matched instruction other than the root.
 238 * Matching/creating a (CImm) immediate >64 bits is not supported
 239   (see comment in ``GIM_CheckConstantInt``)
 240 * There is currently no way to constrain two register/immediate types to
 241   match. e.g. if a pattern needs to work on both i32 and i64, you either
 242   need to leave it untyped and check the type in C++, or duplicate the
 243   pattern.
 244
 245 GICombineRule
 246 -------------
 247
 248 MIR patterns can appear in the ``match`` or ``apply`` patterns of a
 249 ``GICombineRule``.
 250
 251 The ``root`` of the rule can either be a def of an instruction, or a
 252 named pattern. The latter is helpful when the instruction you want
 253 to match has no defs. The former is generally preferred because
 254 it's less verbose.
 255
 256 .. code-block:: text
 257   :caption: Combine Rule root is a def
 258
 259   // Fold x op 1 -> x
 260   def right_identity_one: GICombineRule<
 261     (defs root:$dst),
 262     (match (G_MUL $dst, $x, 1)),
 263     // Note: Patterns always need to create something, we can't just replace $dst with $x, so we need a COPY.
 264     (apply (COPY $dst, $x))
 265   >;
 266
 267 .. code-block:: text
 268   :caption: Combine Rule root is a named pattern
 269
 270   def Foo : GICombineRule<
 271     (defs root:$root),
 272     (match (G_ZEXT $tmp, (i32 0)),
 273            (G_STORE $tmp, $ptr):$root),
 274     (apply (G_STORE (i32 0), $ptr):$root)>;
 275
 276
 277 Combine Rules also allow mixing C++ code with MIR patterns, so that you
 278 may perform additional checks when matching, or run additional code after
 279 rewriting a pattern.
 280
 281 The following expansions are available for MIR patterns:
 282
 283 * operand names (``MachineOperand &``)
 284 * pattern names (``MachineInstr *`` for ``match``,
 285   ``MachineInstrBuilder &`` for apply)
 286
 287 .. code-block:: text
 288   :caption: Example C++ Expansions
 289
 290   def Foo : GICombineRule<
 291     (defs root:$root),
 292     (match (G_ZEXT $root, $src):$mi),
 293     (apply "foobar(${root}.getReg(), ${src}.getReg(), ${mi}->hasImplicitDef())")>;
 294
 295 Common Pattern #1: Replace a Register with Another
 296 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 297
 298 The 'apply' pattern must always redefine all operands defined by the match root.
 299 Sometimes, we do not need to create instructions, simply replace a def with
 300 another matched register. The ``GIReplaceReg`` builtin can do just that.
 301
 302 .. code-block:: text
 303
 304   def Foo : GICombineRule<
 305     (defs root:$dst),
 306     (match (G_FNEG $tmp, $src), (G_FNEG $dst, $tmp)),
 307     (apply (GIReplaceReg $dst, $src))>;
 308
 309 This also works if the replacement register is a temporary register from the
 310 ``apply`` pattern.
 311
 312 .. code-block:: text
 313
 314   def ReplaceTemp : GICombineRule<
 315     (defs root:$a),
 316     (match    (G_BUILD_VECTOR $tmp, $x, $y),
 317               (G_UNMERGE_VALUES $a, $b, $tmp)),
 318     (apply  (G_UNMERGE_VALUES $a, i32:$new, $y),
 319             (GIReplaceReg $b, $new))>
 320
 321 Common Pattern #2: Erasing a Def-less Root
 322 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 323
 324 If we simply want to erase a def-less match root, we can use the
 325 ``GIEraseRoot`` builtin.
 326
 327 .. code-block:: text
 328
 329   def Foo : GICombineRule<
 330     (defs root:$mi),
 331     (match (G_STORE $a, $b):$mi),
 332     (apply (GIEraseRoot))>;
 333
 334 Common Pattern #3: Emitting a Constant Value
 335 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 336
 337 When an immediate operand appears in an 'apply' pattern, the behavior
 338 depends on whether it's typed or not.
 339
 340 * If the immediate is typed, ``MachineIRBuilder::buildConstant`` is used
 341   to create a ``G_CONSTANT``. A ``G_BUILD_VECTOR`` will be used for vectors.
 342 * If the immediate is untyped, a simple immediate is added
 343   (``MachineInstrBuilder::addImm``).
 344
 345 There is of course a special case for ``G_CONSTANT``. Immediates for
 346 ``G_CONSTANT`` must always be typed, and a CImm is added
 347 (``MachineInstrBuilder::addCImm``).
 348
 349 .. code-block:: text
 350   :caption: Constant Emission Examples:
 351
 352   // Example output:
 353   //    %0 = G_CONSTANT i32 0
 354   //    %dst = COPY %0
 355   def Foo : GICombineRule<
 356     (defs root:$dst),
 357     (match (G_FOO $dst, $src)),
 358     (apply (COPY $dst, (i32 0)))>;
 359
 360   // Example output:
 361   //    %dst = COPY 0
 362   // Note that this would be ill-formed because COPY
 363   // expects a register operand!
 364   def Bar : GICombineRule<
 365     (defs root:$dst),
 366     (match (G_FOO $dst, $src)),
 367     (apply (COPY $dst, (i32 0)))>;
 368
 369   // Example output:
 370   //    %dst = G_CONSTANT i32 0
 371   def Bux : GICombineRule<
 372     (defs root:$dst),
 373     (match (G_FOO $dst, $src)),
 374     (apply (G_CONSTANT $dst, (i32 0)))>;
 375
 376 GICombinePatFrag
 377 ----------------
 378
 379 ``GICombinePatFrag`` is an equivalent of ``PatFrags`` for MIR patterns.
 380 They have two main usecases:
 381
 382 * Reduce repetition by creating a ``GICombinePatFrag`` for common
 383   patterns (see example 1).
 384 * Implicitly duplicate a CombineRule for multiple variants of a
 385   pattern (see example 2).
 386
 387 A ``GICombinePatFrag`` is composed of three elements:
 388
 389 * zero or more ``in`` (def) parameter
 390 * zero or more ``out`` parameter
 391 * A list of MIR patterns that can match.
 392
 393   * When a ``GICombinePatFrag`` is used within a pattern, the pattern is
 394     cloned once for each alternative that can match.
 395
 396 Parameters can have the following types:
 397
 398 * ``gi_mo``, which is the implicit default (no type = ``gi_mo``).
 399
 400   * Refers to any operand of an instruction (register, BB ref, imm, etc.).
 401   * Can be used in both ``in`` and ``out`` parameters.
 402   * Users of the PatFrag can only use an operand name for this
 403     parameter (e.g. ``(my_pat_frag $foo)``).
 404
 405 * ``root``
 406
 407   * This is identical to ``gi_mo``.
 408   * Can only be used in ``out`` parameters to declare the root of the
 409     pattern.
 410   * Non-empty ``out`` parameter lists must always have exactly one ``root``.
 411
 412 * ``gi_imm``
 413
 414   * Refers to an (potentially typed) immediate.
 415   * Can only be used in ``in`` parameters.
 416   * Users of the PatFrag can only use an immediate for this parameter
 417     (e.g. ``(my_pat_frag 0)`` or ``(my_pat_frag (i32 0))``)
 418
 419 ``out`` operands can only be empty if the ``GICombinePatFrag`` only contains
 420 C++ code. If the fragment contains instruction patterns, it has to have at
 421 least one ``out`` operand of type ``root``.
 422
 423 ``in`` operands are less restricted, but there is one important concept to
 424 remember: you can pass "unbound" operand names, but only if the
 425 ``GICombinePatFrag`` binds it. See example 3 below.
 426
 427 ``GICombinePatFrag`` are used just like any other instructions.
 428 Note that the ``out`` operands are defs, so they come first in the list
 429 of operands.
 430
 431 .. code-block:: text
 432   :caption: Example 1: Reduce Repetition
 433
 434   def zext_cst : GICombinePatFrag<(outs root:$dst, $cst), (ins gi_imm:$val),
 435     [(pattern (G_CONSTANT $cst, $val),
 436               (G_ZEXT $dst, $cst))]
 437   >;
 438
 439   def foo_to_impdef : GICombineRule<
 440    (defs root:$dst),
 441    (match (zext_cst $y, $cst, (i32 0))
 442           (G_FOO $dst, $y)),
 443    (apply (G_IMPLICIT_DEF $dst))>;
 444
 445   def store_ext_zero : GICombineRule<
 446    (defs root:$root),
 447    (match (zext_cst $y, $cst, (i32 0))
 448           (G_STORE $y, $ptr):$root),
 449    (apply (G_STORE $cst, $ptr):$root)>;
 450
 451 .. code-block:: text
 452   :caption: Example 2: Generate Multiple Rules at Once
 453
 454   // Fold (freeze (freeze x)) -> (freeze x).
 455   // Fold (fabs (fabs x)) -> (fabs x).
 456   // Fold (fcanonicalize (fcanonicalize x)) -> (fcanonicalize x).
 457   def idempotent_prop_frags : GICombinePatFrag<(outs root:$dst, $src), (ins),
 458     [
 459       (pattern (G_FREEZE $dst, $src), (G_FREEZE $src, $x)),
 460       (pattern (G_FABS $dst, $src), (G_FABS $src, $x)),
 461       (pattern (G_FCANONICALIZE $dst, $src), (G_FCANONICALIZE $src, $x))
 462     ]
 463   >;
 464
 465   def idempotent_prop : GICombineRule<
 466     (defs root:$dst),
 467     (match (idempotent_prop_frags $dst, $src)),
 468     (apply (COPY $dst, $src))>;
 469
 470
 471
 472 .. code-block:: text
 473   :caption: Example 3: Unbound Operand Names
 474
 475   // This fragment binds $x to an operand in all of its
 476   // alternative patterns.
 477   def always_binds : GICombinePatFrag<
 478     (outs root:$dst), (ins $x),
 479     [
 480       (pattern (G_FREEZE $dst, $x)),
 481       (pattern (G_FABS $dst, $x)),
 482     ]
 483   >;
 484
 485   // This fragment does not bind $x to an operand in any
 486   // of its alternative patterns.
 487   def does_not_bind : GICombinePatFrag<
 488     (outs root:$dst), (ins $x),
 489     [
 490       (pattern (G_FREEZE $dst, $x)), // binds $x
 491       (pattern (G_FOO $dst (i32 0))), // does not bind $x
 492       (pattern "return myCheck(${x}.getReg())"), // does not bind $x
 493     ]
 494   >;
 495
 496   // Here we pass $x, which is unbound, to always_binds.
 497   // This works because if $x is unbound, always_binds will bind it for us.
 498   def test0 : GICombineRule<
 499     (defs root:$dst),
 500     (match (always_binds $dst, $x)),
 501     (apply (COPY $dst, $x))>;
 502
 503   // Here we pass $x, which is unbound, to does_not_bind.
 504   // This cannot work because $x may not have been initialized in 'apply'.
 505   // error: operand 'x' (for parameter 'src' of 'does_not_bind') cannot be unbound
 506   def test1 : GICombineRule<
 507     (defs root:$dst),
 508     (match (does_not_bind $dst, $x)),
 509     (apply (COPY $dst, $x))>;
 510
 511   // Here we pass $x, which is bound, to does_not_bind.
 512   // This is fine because $x will always be bound when emitting does_not_bind
 513   def test2 : GICombineRule<
 514     (defs root:$dst),
 515     (match (does_not_bind $tmp, $x)
 516            (G_MUL $dst, $x, $tmp)),
 517     (apply (COPY $dst, $x))>;