[memprof] Move YAML support to MemProfYAML.h (NFC) (#119515)
[llvm-project.git] / llvm / docs / GlobalISel / MIRPatterns.rst
blob42ceb1883f7de302bc6303e037a66baf78fc5748
2 .. _tblgen-mirpats:
4 ========================
5 MIR Patterns in TableGen
6 ========================
8 .. contents::
9    :local:
12 User's Guide
13 ============
15 This section is intended for developers who want to use MIR patterns in their
16 TableGen files.
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.
22 Use Cases
23 ---------
25 MIR patterns are supported in the following places:
27 * GlobalISel ``GICombineRule``
28 * GlobalISel ``GICombinePatFrag``
30 Syntax
31 ------
33 MIR patterns use the DAG datatype in TableGen.
35 .. code-block:: text
37   (inst operand0, operand1, ...)
39 ``inst`` must be a def which inherits from ``Instruction`` (e.g. ``G_FADD``),
40 ``Intrinsic`` or ``GICombinePatFrag``.
42 Operands essentially fall into one of two categories:
44 * immediates
46   * untyped, unnamed: ``0``
47   * untyped, named: ``0:$y``
48   * typed, unnamed: ``(i32 0)``
49   * typed, named: ``(i32 0):$y``
51 * machine operands
53   * untyped: ``$x``
54   * typed: ``i32:$x``
56 Semantics:
58 * A typed operand always adds an operand type check to the matcher.
59 * There is a trivial type inference system to propagate types.
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).
66 * A named operand's behavior depends on whether the name has been seen before.
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).
73 Operands are ordered just like they would be in a MachineInstr: the defs (outs)
74 come first, then the uses (ins).
76 Patterns are generally grouped into another DAG datatype with a dummy operator
77 such as ``match``, ``apply`` or ``pattern``.
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.
86 .. code-block:: text
87   :caption: Pattern Example 1
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))
95 .. code-block:: text
96   :caption: Pattern Example 2
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))
104 Types
105 -----
107 ValueType
108 ~~~~~~~~~
110 Subclasses of ``ValueType`` are valid types, e.g. ``i32``.
112 GITypeOf
113 ~~~~~~~~
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.
118 Type Parameters:
120 * An operand name as a string, prefixed by ``$``.
122 Semantics:
124 * Can only appear in an 'apply' pattern.
125 * The operand name used must appear in the 'match' pattern of the
126   same ``GICombineRule``.
128 .. code-block:: text
129   :caption: Example: Immediate
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   >;
137 .. code-block:: text
138   :caption: Example: Temp Reg
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))>;
146 GIVariadic
147 ~~~~~~~~~~
149 ``GIVariadic<>`` is a ``GISpecialType`` that allows for matching 1 or
150 more operands remaining on an instruction.
152 Type Parameters:
154 * The minimum number of additional operands to match. Must be greater than zero.
156   * Default is 1.
158 * The maximum number of additional operands to match. Must be strictly greater
159   than the minimum.
161   * 0 can be used to indicate there is no upper limit.
162   * Default is 0.
164 Semantics:
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 all
171   the matched operands being copied from the original instruction.
172 * The min/max operands will result in the matcher checking that the number of operands
173   falls within that range.
174 * ``GIVariadic<>`` operands can be used in C++ code within a rule, which will
175   result in the operand name being expanded to a value of type ``ArrayRef<MachineOperand>``.
177 .. code-block:: text
179   // bool checkBuildVectorToUnmerge(ArrayRef<MachineOperand>);
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   >;
188 .. code-block:: text
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   >;
199 Builtin Operations
200 ------------------
202 MIR Patterns also offer builtin operations, also called "builtin instructions".
203 They offer some powerful features that would otherwise require use of C++ code.
205 GIReplaceReg
206 ~~~~~~~~~~~~
208 .. code-block:: text
209   :caption: Usage
211   (apply (GIReplaceReg $old, $new))
213 Operands:
215 * ``$old`` (out) register defined by a matched instruction
216 * ``$new`` (in)  register
218 Semantics:
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.
225 GIEraseRoot
226 ~~~~~~~~~~~
228 .. code-block:: text
229   :caption: Usage
231   (apply (GIEraseRoot))
233 Semantics:
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 CodeGenInstruction
239 Instruction Flags
240 -----------------
242 MIR Patterns support both matching & writing ``MIFlags``.
244 .. code-block:: text
245   :caption: Example
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)))>;
252 In ``apply`` patterns, we also support referring to a matched instruction to
253 "take" its MIFlags.
255 .. code-block:: text
256   :caption: Example
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)))>;
265 The ``not`` operator can be used to check that a flag is NOT present
266 on a matched instruction, and to remove a flag from a generated instruction.
268 .. code-block:: text
269   :caption: Example
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))))>;
278 Limitations
279 -----------
281 This a non-exhaustive list of known issues with MIR patterns at this time.
283 * Using ``GICombinePatFrag`` within another ``GICombinePatFrag`` is not
284   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 supported
291   (see comment in ``GIM_CheckConstantInt``)
292 * There is currently no way to constrain two register/immediate types to
293   match. e.g. if a pattern needs to work on both i32 and i64, you either
294   need to leave it untyped and check the type in C++, or duplicate the
295   pattern.
296 * ``GISpecialType`` operands are not allowed within a ``GICombinePatFrag``.
297 * ``GIVariadic<>`` matched operands must each have a unique name.
299 GICombineRule
300 -------------
302 MIR patterns can appear in the ``match`` or ``apply`` patterns of a
303 ``GICombineRule``.
305 The ``root`` of the rule can either be a def of an instruction, or a
306 named pattern. The latter is helpful when the instruction you want
307 to match has no defs. The former is generally preferred because
308 it's less verbose.
310 .. code-block:: text
311   :caption: Combine Rule root is a def
313   // Fold x op 1 -> x
314   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   >;
321 .. code-block:: text
322   :caption: Combine Rule root is a named pattern
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)>;
331 Combine Rules also allow mixing C++ code with MIR patterns, so that you
332 may perform additional checks when matching, or run a C++ action after
333 matching.
335 Note that C++ code in ``apply`` pattern is mutually exclusive with
336 other patterns. However, you can freely mix C++ code with other
337 types of patterns in ``match`` patterns.
338 C++ code in ``match`` patterns is always run last, after all other
339 patterns matched.
341 .. code-block:: text
342   :caption: Apply Pattern Examples with C++ code
344   // Valid
345   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})")>;
352   // error: 'apply' patterns cannot mix C++ code with other types of patterns
353   def Bar : GICombineRule<
354     (defs root:$dst),
355     (match (G_ZEXT $dst, $src):$mi),
356     (apply (G_MUL $dst, $src, $src),
357            "runMyAction(${root})")>;
359 The following expansions are available for MIR patterns:
361 * operand names (``MachineOperand &``)
362 * pattern names (``MachineInstr *`` for ``match``,
363   ``MachineInstrBuilder &`` for apply)
365 .. code-block:: text
366   :caption: Example C++ Expansions
368   def Foo : GICombineRule<
369     (defs root:$root),
370     (match (G_ZEXT $root, $src):$mi),
371     (apply "foobar(${root}.getReg(), ${src}.getReg(), ${mi}->hasImplicitDef())")>;
373 Common Pattern #1: Replace a Register with Another
374 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
376 The 'apply' pattern must always redefine all operands defined by the match root.
377 Sometimes, we do not need to create instructions, simply replace a def with
378 another matched register. The ``GIReplaceReg`` builtin can do just that.
380 .. code-block:: text
382   def Foo : GICombineRule<
383     (defs root:$dst),
384     (match (G_FNEG $tmp, $src), (G_FNEG $dst, $tmp)),
385     (apply (GIReplaceReg $dst, $src))>;
387 This also works if the replacement register is a temporary register from the
388 ``apply`` pattern.
390 .. code-block:: text
392   def ReplaceTemp : GICombineRule<
393     (defs root:$a),
394     (match    (G_BUILD_VECTOR $tmp, $x, $y),
395               (G_UNMERGE_VALUES $a, $b, $tmp)),
396     (apply  (G_UNMERGE_VALUES $a, i32:$new, $y),
397             (GIReplaceReg $b, $new))>
399 Common Pattern #2: Erasing a Def-less Root
400 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
402 If we simply want to erase a def-less match root, we can use the
403 ``GIEraseRoot`` builtin.
405 .. code-block:: text
407   def Foo : GICombineRule<
408     (defs root:$mi),
409     (match (G_STORE $a, $b):$mi),
410     (apply (GIEraseRoot))>;
412 Common Pattern #3: Emitting a Constant Value
413 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
415 When an immediate operand appears in an 'apply' pattern, the behavior
416 depends on whether it's typed or not.
418 * If the immediate is typed, ``MachineIRBuilder::buildConstant`` is used
419   to create a ``G_CONSTANT``. A ``G_BUILD_VECTOR`` will be used for vectors.
420 * If the immediate is untyped, a simple immediate is added
421   (``MachineInstrBuilder::addImm``).
423 There is of course a special case for ``G_CONSTANT``. Immediates for
424 ``G_CONSTANT`` must always be typed, and a CImm is added
425 (``MachineInstrBuilder::addCImm``).
427 .. code-block:: text
428   :caption: Constant Emission Examples:
430   // Example output:
431   //    %0 = G_CONSTANT i32 0
432   //    %dst = COPY %0
433   def Foo : GICombineRule<
434     (defs root:$dst),
435     (match (G_FOO $dst, $src)),
436     (apply (COPY $dst, (i32 0)))>;
438   // Example output:
439   //    %dst = COPY 0
440   // Note that this would be ill-formed because COPY
441   // expects a register operand!
442   def Bar : GICombineRule<
443     (defs root:$dst),
444     (match (G_FOO $dst, $src)),
445     (apply (COPY $dst, (i32 0)))>;
447   // Example output:
448   //    %dst = G_CONSTANT i32 0
449   def Bux : GICombineRule<
450     (defs root:$dst),
451     (match (G_FOO $dst, $src)),
452     (apply (G_CONSTANT $dst, (i32 0)))>;
454 GICombinePatFrag
455 ----------------
457 ``GICombinePatFrag`` is an equivalent of ``PatFrags`` for MIR patterns.
458 They have two main usecases:
460 * Reduce repetition by creating a ``GICombinePatFrag`` for common
461   patterns (see example 1).
462 * Implicitly duplicate a CombineRule for multiple variants of a
463   pattern (see example 2).
465 A ``GICombinePatFrag`` is composed of three elements:
467 * zero or more ``in`` (def) parameter
468 * zero or more ``out`` parameter
469 * A list of MIR patterns that can match.
471   * When a ``GICombinePatFrag`` is used within a pattern, the pattern is
472     cloned once for each alternative that can match.
474 Parameters can have the following types:
476 * ``gi_mo``, which is the implicit default (no type = ``gi_mo``).
478   * Refers to any operand of an instruction (register, BB ref, imm, etc.).
479   * Can be used in both ``in`` and ``out`` parameters.
480   * Users of the PatFrag can only use an operand name for this
481     parameter (e.g. ``(my_pat_frag $foo)``).
483 * ``root``
485   * This is identical to ``gi_mo``.
486   * Can only be used in ``out`` parameters to declare the root of the
487     pattern.
488   * Non-empty ``out`` parameter lists must always have exactly one ``root``.
490 * ``gi_imm``
492   * Refers to an (potentially typed) immediate.
493   * Can only be used in ``in`` parameters.
494   * Users of the PatFrag can only use an immediate for this parameter
495     (e.g. ``(my_pat_frag 0)`` or ``(my_pat_frag (i32 0))``)
497 ``out`` operands can only be empty if the ``GICombinePatFrag`` only contains
498 C++ code. If the fragment contains instruction patterns, it has to have at
499 least one ``out`` operand of type ``root``.
501 ``in`` operands are less restricted, but there is one important concept to
502 remember: you can pass "unbound" operand names, but only if the
503 ``GICombinePatFrag`` binds it. See example 3 below.
505 ``GICombinePatFrag`` are used just like any other instructions.
506 Note that the ``out`` operands are defs, so they come first in the list
507 of operands.
509 .. code-block:: text
510   :caption: Example 1: Reduce Repetition
512   def zext_cst : GICombinePatFrag<(outs root:$dst, $cst), (ins gi_imm:$val),
513     [(pattern (G_CONSTANT $cst, $val),
514               (G_ZEXT $dst, $cst))]
515   >;
517   def foo_to_impdef : GICombineRule<
518    (defs root:$dst),
519    (match (zext_cst $y, $cst, (i32 0))
520           (G_FOO $dst, $y)),
521    (apply (G_IMPLICIT_DEF $dst))>;
523   def store_ext_zero : GICombineRule<
524    (defs root:$root),
525    (match (zext_cst $y, $cst, (i32 0))
526           (G_STORE $y, $ptr):$root),
527    (apply (G_STORE $cst, $ptr):$root)>;
529 .. code-block:: text
530   :caption: Example 2: Generate Multiple Rules at Once
532   // Fold (freeze (freeze x)) -> (freeze x).
533   // Fold (fabs (fabs x)) -> (fabs x).
534   // Fold (fcanonicalize (fcanonicalize x)) -> (fcanonicalize x).
535   def idempotent_prop_frags : GICombinePatFrag<(outs root:$dst, $src), (ins),
536     [
537       (pattern (G_FREEZE $dst, $src), (G_FREEZE $src, $x)),
538       (pattern (G_FABS $dst, $src), (G_FABS $src, $x)),
539       (pattern (G_FCANONICALIZE $dst, $src), (G_FCANONICALIZE $src, $x))
540     ]
541   >;
543   def idempotent_prop : GICombineRule<
544     (defs root:$dst),
545     (match (idempotent_prop_frags $dst, $src)),
546     (apply (COPY $dst, $src))>;
550 .. code-block:: text
551   :caption: Example 3: Unbound Operand Names
553   // This fragment binds $x to an operand in all of its
554   // alternative patterns.
555   def always_binds : GICombinePatFrag<
556     (outs root:$dst), (ins $x),
557     [
558       (pattern (G_FREEZE $dst, $x)),
559       (pattern (G_FABS $dst, $x)),
560     ]
561   >;
563   // This fragment does not bind $x to an operand in any
564   // of its alternative patterns.
565   def does_not_bind : GICombinePatFrag<
566     (outs root:$dst), (ins $x),
567     [
568       (pattern (G_FREEZE $dst, $x)), // binds $x
569       (pattern (G_FOO $dst (i32 0))), // does not bind $x
570       (pattern "return myCheck(${x}.getReg())"), // does not bind $x
571     ]
572   >;
574   // Here we pass $x, which is unbound, to always_binds.
575   // This works because if $x is unbound, always_binds will bind it for us.
576   def test0 : GICombineRule<
577     (defs root:$dst),
578     (match (always_binds $dst, $x)),
579     (apply (COPY $dst, $x))>;
581   // Here we pass $x, which is unbound, to does_not_bind.
582   // This cannot work because $x may not have been initialized in 'apply'.
583   // error: operand 'x' (for parameter 'src' of 'does_not_bind') cannot be unbound
584   def test1 : GICombineRule<
585     (defs root:$dst),
586     (match (does_not_bind $dst, $x)),
587     (apply (COPY $dst, $x))>;
589   // Here we pass $x, which is bound, to does_not_bind.
590   // This is fine because $x will always be bound when emitting does_not_bind
591   def test2 : GICombineRule<
592     (defs root:$dst),
593     (match (does_not_bind $tmp, $x)
594            (G_MUL $dst, $x, $tmp)),
595     (apply (COPY $dst, $x))>;
600 Gallery
601 =======
603 We should use precise patterns that state our intentions. Please avoid
604 using wip_match_opcode in patterns. It can lead to imprecise patterns.
606 .. code-block:: text
607   :caption: Example fold zext(trunc:nuw)
609   // Imprecise: matches any G_ZEXT
610   def zext : GICombineRule<
611     (defs root:$root),
612     (match (wip_match_opcode G_ZEXT):$root,
613     [{ return Helper.matchZextOfTrunc(*${root}, ${matchinfo}); }]),
614     (apply [{ Helper.applyBuildFn(*${root}, ${matchinfo}); }])>;
617   // Imprecise: matches G_ZEXT of G_TRUNC
618   def zext_of_trunc : GICombineRule<
619     (defs root:$root),
620     (match (G_TRUNC $src, $x),
621            (G_ZEXT $root, $src),
622     [{ return Helper.matchZextOfTrunc(${root}, ${matchinfo}); }]),
623     (apply [{ Helper.applyBuildFnMO(${root}, ${matchinfo}); }])>;
626   // Precise: matches G_ZEXT of G_TRUNC with nuw flag
627   def zext_of_trunc_nuw : GICombineRule<
628     (defs root:$root),
629     (match (G_TRUNC $src, $x, (MIFlags NoUWrap)),
630            (G_ZEXT $root, $src),
631     [{ return Helper.matchZextOfTrunc(${root}, ${matchinfo}); }]),
632     (apply [{ Helper.applyBuildFnMO(${root}, ${matchinfo}); }])>;
635   // Precise: lists all combine combinations
636   class ext_of_ext_opcodes<Instruction ext1Opcode, Instruction ext2Opcode> : GICombineRule <
637     (defs root:$root, build_fn_matchinfo:$matchinfo),
638     (match (ext2Opcode $second, $src):$Second,
639            (ext1Opcode $root, $second):$First,
640            [{ return Helper.matchExtOfExt(*${First}, *${Second}, ${matchinfo}); }]),
641     (apply [{ Helper.applyBuildFn(*${First}, ${matchinfo}); }])>;
643   def zext_of_zext : ext_of_ext_opcodes<G_ZEXT, G_ZEXT>;
644   def zext_of_anyext : ext_of_ext_opcodes<G_ZEXT, G_ANYEXT>;
645   def sext_of_sext : ext_of_ext_opcodes<G_SEXT, G_SEXT>;
646   def sext_of_anyext : ext_of_ext_opcodes<G_SEXT, G_ANYEXT>;
647   def anyext_of_anyext : ext_of_ext_opcodes<G_ANYEXT, G_ANYEXT>;
648   def anyext_of_zext : ext_of_ext_opcodes<G_ANYEXT, G_ZEXT>;
649   def anyext_of_sext : ext_of_ext_opcodes<G_ANYEXT, G_SEXT>;