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
 187 Limitations
 188 -----------
 189
 190 This a non-exhaustive list of known issues with MIR patterns at this time.
 191
 192 * Matching intrinsics is not yet possible.
 193 * Using ``GICombinePatFrag`` within another ``GICombinePatFrag`` is not
 194   supported.
 195 * ``GICombinePatFrag`` can only have a single root.
 196 * Instructions with multiple defs cannot be the root of a ``GICombinePatFrag``.
 197 * Using ``GICombinePatFrag`` in the ``apply`` pattern of a ``GICombineRule``
 198   is not supported.
 199 * We cannot rewrite a matched instruction other than the root.
 200 * Matching/creating a (CImm) immediate >64 bits is not supported
 201   (see comment in ``GIM_CheckConstantInt``)
 202 * There is currently no way to constrain two register/immediate types to
 203   match. e.g. if a pattern needs to work on both i32 and i64, you either
 204   need to leave it untyped and check the type in C++, or duplicate the
 205   pattern.
 206
 207 GICombineRule
 208 -------------
 209
 210 MIR patterns can appear in the ``match`` or ``apply`` patterns of a
 211 ``GICombineRule``.
 212
 213 The ``root`` of the rule can either be a def of an instruction, or a
 214 named pattern. The latter is helpful when the instruction you want
 215 to match has no defs. The former is generally preferred because
 216 it's less verbose.
 217
 218 .. code-block:: text
 219   :caption: Combine Rule root is a def
 220
 221   // Fold x op 1 -> x
 222   def right_identity_one: GICombineRule<
 223     (defs root:$dst),
 224     (match (G_MUL $dst, $x, 1)),
 225     // Note: Patterns always need to create something, we can't just replace $dst with $x, so we need a COPY.
 226     (apply (COPY $dst, $x))
 227   >;
 228
 229 .. code-block:: text
 230   :caption: Combine Rule root is a named pattern
 231
 232   def Foo : GICombineRule<
 233     (defs root:$root),
 234     (match (G_ZEXT $tmp, (i32 0)),
 235            (G_STORE $tmp, $ptr):$root),
 236     (apply (G_STORE (i32 0), $ptr):$root)>;
 237
 238
 239 Combine Rules also allow mixing C++ code with MIR patterns, so that you
 240 may perform additional checks when matching, or run additional code after
 241 rewriting a pattern.
 242
 243 The following expansions are available for MIR patterns:
 244
 245 * operand names (``MachineOperand &``)
 246 * pattern names (``MachineInstr *`` for ``match``,
 247   ``MachineInstrBuilder &`` for apply)
 248
 249 .. code-block:: text
 250   :caption: Example C++ Expansions
 251
 252   def Foo : GICombineRule<
 253     (defs root:$root),
 254     (match (G_ZEXT $root, $src):$mi),
 255     (apply "foobar(${root}.getReg(), ${src}.getReg(), ${mi}->hasImplicitDef())")>;
 256
 257 Common Pattern #1: Replace a Register with Another
 258 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 259
 260 The 'apply' pattern must always redefine all operands defined by the match root.
 261 Sometimes, we do not need to create instructions, simply replace a def with
 262 another matched register. The ``GIReplaceReg`` builtin can do just that.
 263
 264 .. code-block:: text
 265
 266   def Foo : GICombineRule<
 267     (defs root:$dst),
 268     (match (G_FNEG $tmp, $src), (G_FNEG $dst, $tmp)),
 269     (apply (GIReplaceReg $dst, $src))>;
 270
 271 This also works if the replacement register is a temporary register from the
 272 ``apply`` pattern.
 273
 274 .. code-block:: text
 275
 276   def ReplaceTemp : GICombineRule<
 277     (defs root:$a),
 278     (match    (G_BUILD_VECTOR $tmp, $x, $y),
 279               (G_UNMERGE_VALUES $a, $b, $tmp)),
 280     (apply  (G_UNMERGE_VALUES $a, i32:$new, $y),
 281             (GIReplaceReg $b, $new))>
 282
 283 Common Pattern #2: Erasing a Def-less Root
 284 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 285
 286 If we simply want to erase a def-less match root, we can use the
 287 ``GIEraseRoot`` builtin.
 288
 289 .. code-block:: text
 290
 291   def Foo : GICombineRule<
 292     (defs root:$mi),
 293     (match (G_STORE $a, $b):$mi),
 294     (apply (GIEraseRoot))>;
 295
 296 Common Pattern #3: Emitting a Constant Value
 297 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 298
 299 When an immediate operand appears in an 'apply' pattern, the behavior
 300 depends on whether it's typed or not.
 301
 302 * If the immediate is typed, ``MachineIRBuilder::buildConstant`` is used
 303   to create a ``G_CONSTANT``. A ``G_BUILD_VECTOR`` will be used for vectors.
 304 * If the immediate is untyped, a simple immediate is added
 305   (``MachineInstrBuilder::addImm``).
 306
 307 There is of course a special case for ``G_CONSTANT``. Immediates for
 308 ``G_CONSTANT`` must always be typed, and a CImm is added
 309 (``MachineInstrBuilder::addCImm``).
 310
 311 .. code-block:: text
 312   :caption: Constant Emission Examples:
 313
 314   // Example output:
 315   //    %0 = G_CONSTANT i32 0
 316   //    %dst = COPY %0
 317   def Foo : GICombineRule<
 318     (defs root:$dst),
 319     (match (G_FOO $dst, $src)),
 320     (apply (COPY $dst, (i32 0)))>;
 321
 322   // Example output:
 323   //    %dst = COPY 0
 324   // Note that this would be ill-formed because COPY
 325   // expects a register operand!
 326   def Bar : GICombineRule<
 327     (defs root:$dst),
 328     (match (G_FOO $dst, $src)),
 329     (apply (COPY $dst, (i32 0)))>;
 330
 331   // Example output:
 332   //    %dst = G_CONSTANT i32 0
 333   def Bux : GICombineRule<
 334     (defs root:$dst),
 335     (match (G_FOO $dst, $src)),
 336     (apply (G_CONSTANT $dst, (i32 0)))>;
 337
 338 GICombinePatFrag
 339 ----------------
 340
 341 ``GICombinePatFrag`` is an equivalent of ``PatFrags`` for MIR patterns.
 342 They have two main usecases:
 343
 344 * Reduce repetition by creating a ``GICombinePatFrag`` for common
 345   patterns (see example 1).
 346 * Implicitly duplicate a CombineRule for multiple variants of a
 347   pattern (see example 2).
 348
 349 A ``GICombinePatFrag`` is composed of three elements:
 350
 351 * zero or more ``in`` (def) parameter
 352 * zero or more ``out`` parameter
 353 * A list of MIR patterns that can match.
 354
 355   * When a ``GICombinePatFrag`` is used within a pattern, the pattern is
 356     cloned once for each alternative that can match.
 357
 358 Parameters can have the following types:
 359
 360 * ``gi_mo``, which is the implicit default (no type = ``gi_mo``).
 361
 362   * Refers to any operand of an instruction (register, BB ref, imm, etc.).
 363   * Can be used in both ``in`` and ``out`` parameters.
 364   * Users of the PatFrag can only use an operand name for this
 365     parameter (e.g. ``(my_pat_frag $foo)``).
 366
 367 * ``root``
 368
 369   * This is identical to ``gi_mo``.
 370   * Can only be used in ``out`` parameters to declare the root of the
 371     pattern.
 372   * Non-empty ``out`` parameter lists must always have exactly one ``root``.
 373
 374 * ``gi_imm``
 375
 376   * Refers to an (potentially typed) immediate.
 377   * Can only be used in ``in`` parameters.
 378   * Users of the PatFrag can only use an immediate for this parameter
 379     (e.g. ``(my_pat_frag 0)`` or ``(my_pat_frag (i32 0))``)
 380
 381 ``out`` operands can only be empty if the ``GICombinePatFrag`` only contains
 382 C++ code. If the fragment contains instruction patterns, it has to have at
 383 least one ``out`` operand of type ``root``.
 384
 385 ``in`` operands are less restricted, but there is one important concept to
 386 remember: you can pass "unbound" operand names, but only if the
 387 ``GICombinePatFrag`` binds it. See example 3 below.
 388
 389 ``GICombinePatFrag`` are used just like any other instructions.
 390 Note that the ``out`` operands are defs, so they come first in the list
 391 of operands.
 392
 393 .. code-block:: text
 394   :caption: Example 1: Reduce Repetition
 395
 396   def zext_cst : GICombinePatFrag<(outs root:$dst, $cst), (ins gi_imm:$val),
 397     [(pattern (G_CONSTANT $cst, $val),
 398               (G_ZEXT $dst, $cst))]
 399   >;
 400
 401   def foo_to_impdef : GICombineRule<
 402    (defs root:$dst),
 403    (match (zext_cst $y, $cst, (i32 0))
 404           (G_FOO $dst, $y)),
 405    (apply (G_IMPLICIT_DEF $dst))>;
 406
 407   def store_ext_zero : GICombineRule<
 408    (defs root:$root),
 409    (match (zext_cst $y, $cst, (i32 0))
 410           (G_STORE $y, $ptr):$root),
 411    (apply (G_STORE $cst, $ptr):$root)>;
 412
 413 .. code-block:: text
 414   :caption: Example 2: Generate Multiple Rules at Once
 415
 416   // Fold (freeze (freeze x)) -> (freeze x).
 417   // Fold (fabs (fabs x)) -> (fabs x).
 418   // Fold (fcanonicalize (fcanonicalize x)) -> (fcanonicalize x).
 419   def idempotent_prop_frags : GICombinePatFrag<(outs root:$dst, $src), (ins),
 420     [
 421       (pattern (G_FREEZE $dst, $src), (G_FREEZE $src, $x)),
 422       (pattern (G_FABS $dst, $src), (G_FABS $src, $x)),
 423       (pattern (G_FCANONICALIZE $dst, $src), (G_FCANONICALIZE $src, $x))
 424     ]
 425   >;
 426
 427   def idempotent_prop : GICombineRule<
 428     (defs root:$dst),
 429     (match (idempotent_prop_frags $dst, $src)),
 430     (apply (COPY $dst, $src))>;
 431
 432
 433
 434 .. code-block:: text
 435   :caption: Example 3: Unbound Operand Names
 436
 437   // This fragment binds $x to an operand in all of its
 438   // alternative patterns.
 439   def always_binds : GICombinePatFrag<
 440     (outs root:$dst), (ins $x),
 441     [
 442       (pattern (G_FREEZE $dst, $x)),
 443       (pattern (G_FABS $dst, $x)),
 444     ]
 445   >;
 446
 447   // This fragment does not bind $x to an operand in any
 448   // of its alternative patterns.
 449   def does_not_bind : GICombinePatFrag<
 450     (outs root:$dst), (ins $x),
 451     [
 452       (pattern (G_FREEZE $dst, $x)), // binds $x
 453       (pattern (G_FOO $dst (i32 0))), // does not bind $x
 454       (pattern "return myCheck(${x}.getReg())"), // does not bind $x
 455     ]
 456   >;
 457
 458   // Here we pass $x, which is unbound, to always_binds.
 459   // This works because if $x is unbound, always_binds will bind it for us.
 460   def test0 : GICombineRule<
 461     (defs root:$dst),
 462     (match (always_binds $dst, $x)),
 463     (apply (COPY $dst, $x))>;
 464
 465   // Here we pass $x, which is unbound, to does_not_bind.
 466   // This cannot work because $x may not have been initialized in 'apply'.
 467   // error: operand 'x' (for parameter 'src' of 'does_not_bind') cannot be unbound
 468   def test1 : GICombineRule<
 469     (defs root:$dst),
 470     (match (does_not_bind $dst, $x)),
 471     (apply (COPY $dst, $x))>;
 472
 473   // Here we pass $x, which is bound, to does_not_bind.
 474   // This is fine because $x will always be bound when emitting does_not_bind
 475   def test2 : GICombineRule<
 476     (defs root:$dst),
 477     (match (does_not_bind $tmp, $x)
 478            (G_MUL $dst, $x, $tmp)),
 479     (apply (COPY $dst, $x))>;