MIR Patterns in TableGen

User’s Guide

This section is intended for developers who want to use MIR patterns in their TableGen files.

NOTE: This feature is still in active development. This document may become outdated over time. If you see something that’s incorrect, please update it.

Use Cases

MIR patterns are supported in the following places:

  • GlobalISel GICombineRule

  • GlobalISel GICombinePatFrag

Syntax

MIR patterns use the DAG datatype in TableGen.

(inst operand0, operand1, ...)

inst must be a def which inherits from Instruction (e.g. G_FADD), Intrinsic or GICombinePatFrag.

Operands essentially fall into one of two categories:

  • immediates

    • untyped, unnamed: 0

    • untyped, named: 0:$y

    • typed, unnamed: (i32 0)

    • typed, named: (i32 0):$y

  • machine operands

    • untyped: $x

    • typed: i32:$x

Semantics:

  • A typed operand always adds an operand type check to the matcher.

  • There is a trivial type inference system to propagate types.

    • e.g. You only need to use i32:$x once in any pattern of a GICombinePatFrag alternative or GICombineRule, then all other patterns in that rule/alternative can simply use $x (i32:$x is redundant).

  • A named operand’s behavior depends on whether the name has been seen before.

    • For match patterns, reusing an operand name checks that the operands are identical (see example 2 below).

    • For apply patterns, reusing an operand name simply copies that operand into the new instruction (see example 2 below).

Operands are ordered just like they would be in a MachineInstr: the defs (outs) come first, then the uses (ins).

Patterns are generally grouped into another DAG datatype with a dummy operator such as match, apply or pattern.

Finally, any DAG datatype in TableGen can be named. This also holds for patterns. e.g. the following is valid: (G_FOO $root, (i32 0):$cst):$mypat. This may also be helpful to debug issues. Patterns are always named, and if they don’t have a name, an “anonymous” one is given to them. If you’re trying to debug an error related to a MIR pattern, but the error mentions an anonymous pattern, you can try naming your patterns to see exactly where the issue is.

Listing 1 Pattern Example 1
// Match
//    %imp = G_IMPLICIT_DEF
//    %root = G_MUL %x, %imp
(match (G_IMPLICIT_DEF $imp),
       (G_MUL $root, $x, $imp))
Listing 2 Pattern Example 2
// using $x twice here checks that the operand 1 and 2 of the G_AND are
// identical.
(match (G_AND $root, $x, $x))
// using $x again here copies operand 1 from G_AND into the new inst.
(apply (COPY $root, $x))

Types

ValueType

Subclasses of ValueType are valid types, e.g. i32.

GITypeOf

GITypeOf<"$x"> is a GISpecialType that allows for the creation of a register or immediate with the same type as another (register) operand.

Operand:

  • An operand name as a string, prefixed by $.

Semantics:

  • Can only appear in an ‘apply’ pattern.

  • The operand name used must appear in the ‘match’ pattern of the same GICombineRule.

Listing 3 Example: Immediate
def mul_by_neg_one: GICombineRule <
  (defs root:$root),
  (match (G_MUL $dst, $x, -1)),
  (apply (G_SUB $dst, (GITypeOf<"$x"> 0), $x))
>;
Listing 4 Example: Temp Reg
def Test0 : GICombineRule<
  (defs root:$dst),
  (match (G_FMUL $dst, $src, -1)),
  (apply (G_FSUB $dst, $src, $tmp),
         (G_FNEG GITypeOf<"$dst">:$tmp, $src))>;

Builtin Operations

MIR Patterns also offer builtin operations, also called “builtin instructions”. They offer some powerful features that would otherwise require use of C++ code.

GIReplaceReg

Listing 5 Usage
(apply (GIReplaceReg $old, $new))

Operands:

  • $old (out) register defined by a matched instruction

  • $new (in) register

Semantics:

  • Can only appear in an ‘apply’ pattern.

  • If both old/new are operands of matched instructions, canReplaceReg is checked before applying the rule.

GIEraseRoot

Listing 6 Usage
(apply (GIEraseRoot))

Semantics:

  • Can only appear as the only pattern of an ‘apply’ pattern list.

  • The root cannot have any output operands.

  • The root must be a CodeGenInstruction

Instruction Flags

MIR Patterns support both matching & writing MIFlags.

Listing 7 Example
def Test : GICombineRule<
  (defs root:$dst),
  (match (G_FOO $dst, $src, (MIFlags FmNoNans, FmNoInfs))),
  (apply (G_BAR $dst, $src, (MIFlags FmReassoc)))>;

In apply patterns, we also support referring to a matched instruction to “take” its MIFlags.

Listing 8 Example
; We match NoNans/NoInfs, but $zext may have more flags.
; Copy them all into the output instruction, and set Reassoc on the output inst.
def TestCpyFlags : GICombineRule<
  (defs root:$dst),
  (match (G_FOO $dst, $src, (MIFlags FmNoNans, FmNoInfs)):$zext),
  (apply (G_BAR $dst, $src, (MIFlags $zext, FmReassoc)))>;

The not operator can be used to check that a flag is NOT present on a matched instruction, and to remove a flag from a generated instruction.

Listing 9 Example
; We match NoInfs but we don't want NoNans/Reassoc to be set. $zext may have more flags.
; Copy them all into the output instruction but remove NoInfs on the output inst.
def TestNot : GICombineRule<
  (defs root:$dst),
  (match (G_FOO $dst, $src, (MIFlags FmNoInfs, (not FmNoNans, FmReassoc))):$zext),
  (apply (G_BAR $dst, $src, (MIFlags $zext, (not FmNoInfs))))>;

Limitations

This a non-exhaustive list of known issues with MIR patterns at this time.

  • Using GICombinePatFrag within another GICombinePatFrag is not supported.

  • GICombinePatFrag can only have a single root.

  • Instructions with multiple defs cannot be the root of a GICombinePatFrag.

  • Using GICombinePatFrag in the apply pattern of a GICombineRule is not supported.

  • We cannot rewrite a matched instruction other than the root.

  • Matching/creating a (CImm) immediate >64 bits is not supported (see comment in GIM_CheckConstantInt)

  • There is currently no way to constrain two register/immediate types to match. e.g. if a pattern needs to work on both i32 and i64, you either need to leave it untyped and check the type in C++, or duplicate the pattern.

GICombineRule

MIR patterns can appear in the match or apply patterns of a GICombineRule.

The root of the rule can either be a def of an instruction, or a named pattern. The latter is helpful when the instruction you want to match has no defs. The former is generally preferred because it’s less verbose.

Listing 10 Combine Rule root is a def
// Fold x op 1 -> x
def right_identity_one: GICombineRule<
  (defs root:$dst),
  (match (G_MUL $dst, $x, 1)),
  // Note: Patterns always need to create something, we can't just replace $dst with $x, so we need a COPY.
  (apply (COPY $dst, $x))
>;
Listing 11 Combine Rule root is a named pattern
def Foo : GICombineRule<
  (defs root:$root),
  (match (G_ZEXT $tmp, (i32 0)),
         (G_STORE $tmp, $ptr):$root),
  (apply (G_STORE (i32 0), $ptr):$root)>;

Combine Rules also allow mixing C++ code with MIR patterns, so that you may perform additional checks when matching, or run a C++ action after matching.

Note that C++ code in apply pattern is mutually exclusive with other patterns. However, you can freely mix C++ code with other types of patterns in match patterns. C++ code in match patterns is always run last, after all other patterns matched.

Listing 12 Apply Pattern Examples with C++ code
// Valid
def Foo : GICombineRule<
  (defs root:$root),
  (match (G_ZEXT $tmp, (i32 0)),
         (G_STORE $tmp, $ptr):$root,
         "return myFinalCheck()"),
  (apply "runMyAction(${root})")>;

// error: 'apply' patterns cannot mix C++ code with other types of patterns
def Bar : GICombineRule<
  (defs root:$dst),
  (match (G_ZEXT $dst, $src):$mi),
  (apply (G_MUL $dst, $src, $src),
         "runMyAction(${root})")>;

The following expansions are available for MIR patterns:

  • operand names (MachineOperand &)

  • pattern names (MachineInstr * for match, MachineInstrBuilder & for apply)

Listing 13 Example C++ Expansions
def Foo : GICombineRule<
  (defs root:$root),
  (match (G_ZEXT $root, $src):$mi),
  (apply "foobar(${root}.getReg(), ${src}.getReg(), ${mi}->hasImplicitDef())")>;

Common Pattern #1: Replace a Register with Another

The ‘apply’ pattern must always redefine all operands defined by the match root. Sometimes, we do not need to create instructions, simply replace a def with another matched register. The GIReplaceReg builtin can do just that.

def Foo : GICombineRule<
  (defs root:$dst),
  (match (G_FNEG $tmp, $src), (G_FNEG $dst, $tmp)),
  (apply (GIReplaceReg $dst, $src))>;

This also works if the replacement register is a temporary register from the apply pattern.

def ReplaceTemp : GICombineRule<
  (defs root:$a),
  (match    (G_BUILD_VECTOR $tmp, $x, $y),
            (G_UNMERGE_VALUES $a, $b, $tmp)),
  (apply  (G_UNMERGE_VALUES $a, i32:$new, $y),
          (GIReplaceReg $b, $new))>

Common Pattern #2: Erasing a Def-less Root

If we simply want to erase a def-less match root, we can use the GIEraseRoot builtin.

def Foo : GICombineRule<
  (defs root:$mi),
  (match (G_STORE $a, $b):$mi),
  (apply (GIEraseRoot))>;

Common Pattern #3: Emitting a Constant Value

When an immediate operand appears in an ‘apply’ pattern, the behavior depends on whether it’s typed or not.

  • If the immediate is typed, MachineIRBuilder::buildConstant is used to create a G_CONSTANT. A G_BUILD_VECTOR will be used for vectors.

  • If the immediate is untyped, a simple immediate is added (MachineInstrBuilder::addImm).

There is of course a special case for G_CONSTANT. Immediates for G_CONSTANT must always be typed, and a CImm is added (MachineInstrBuilder::addCImm).

Listing 14 Constant Emission Examples:
// Example output:
//    %0 = G_CONSTANT i32 0
//    %dst = COPY %0
def Foo : GICombineRule<
  (defs root:$dst),
  (match (G_FOO $dst, $src)),
  (apply (COPY $dst, (i32 0)))>;

// Example output:
//    %dst = COPY 0
// Note that this would be ill-formed because COPY
// expects a register operand!
def Bar : GICombineRule<
  (defs root:$dst),
  (match (G_FOO $dst, $src)),
  (apply (COPY $dst, (i32 0)))>;

// Example output:
//    %dst = G_CONSTANT i32 0
def Bux : GICombineRule<
  (defs root:$dst),
  (match (G_FOO $dst, $src)),
  (apply (G_CONSTANT $dst, (i32 0)))>;

GICombinePatFrag

GICombinePatFrag is an equivalent of PatFrags for MIR patterns. They have two main usecases:

  • Reduce repetition by creating a GICombinePatFrag for common patterns (see example 1).

  • Implicitly duplicate a CombineRule for multiple variants of a pattern (see example 2).

A GICombinePatFrag is composed of three elements:

  • zero or more in (def) parameter

  • zero or more out parameter

  • A list of MIR patterns that can match.

    • When a GICombinePatFrag is used within a pattern, the pattern is cloned once for each alternative that can match.

Parameters can have the following types:

  • gi_mo, which is the implicit default (no type = gi_mo).

    • Refers to any operand of an instruction (register, BB ref, imm, etc.).

    • Can be used in both in and out parameters.

    • Users of the PatFrag can only use an operand name for this parameter (e.g. (my_pat_frag $foo)).

  • root

    • This is identical to gi_mo.

    • Can only be used in out parameters to declare the root of the pattern.

    • Non-empty out parameter lists must always have exactly one root.

  • gi_imm

    • Refers to an (potentially typed) immediate.

    • Can only be used in in parameters.

    • Users of the PatFrag can only use an immediate for this parameter (e.g. (my_pat_frag 0) or (my_pat_frag (i32 0)))

out operands can only be empty if the GICombinePatFrag only contains C++ code. If the fragment contains instruction patterns, it has to have at least one out operand of type root.

in operands are less restricted, but there is one important concept to remember: you can pass “unbound” operand names, but only if the GICombinePatFrag binds it. See example 3 below.

GICombinePatFrag are used just like any other instructions. Note that the out operands are defs, so they come first in the list of operands.

Listing 15 Example 1: Reduce Repetition
def zext_cst : GICombinePatFrag<(outs root:$dst, $cst), (ins gi_imm:$val),
  [(pattern (G_CONSTANT $cst, $val),
            (G_ZEXT $dst, $cst))]
>;

def foo_to_impdef : GICombineRule<
 (defs root:$dst),
 (match (zext_cst $y, $cst, (i32 0))
        (G_FOO $dst, $y)),
 (apply (G_IMPLICIT_DEF $dst))>;

def store_ext_zero : GICombineRule<
 (defs root:$root),
 (match (zext_cst $y, $cst, (i32 0))
        (G_STORE $y, $ptr):$root),
 (apply (G_STORE $cst, $ptr):$root)>;
Listing 16 Example 2: Generate Multiple Rules at Once
// Fold (freeze (freeze x)) -> (freeze x).
// Fold (fabs (fabs x)) -> (fabs x).
// Fold (fcanonicalize (fcanonicalize x)) -> (fcanonicalize x).
def idempotent_prop_frags : GICombinePatFrag<(outs root:$dst, $src), (ins),
  [
    (pattern (G_FREEZE $dst, $src), (G_FREEZE $src, $x)),
    (pattern (G_FABS $dst, $src), (G_FABS $src, $x)),
    (pattern (G_FCANONICALIZE $dst, $src), (G_FCANONICALIZE $src, $x))
  ]
>;

def idempotent_prop : GICombineRule<
  (defs root:$dst),
  (match (idempotent_prop_frags $dst, $src)),
  (apply (COPY $dst, $src))>;
Listing 17 Example 3: Unbound Operand Names
// This fragment binds $x to an operand in all of its
// alternative patterns.
def always_binds : GICombinePatFrag<
  (outs root:$dst), (ins $x),
  [
    (pattern (G_FREEZE $dst, $x)),
    (pattern (G_FABS $dst, $x)),
  ]
>;

// This fragment does not bind $x to an operand in any
// of its alternative patterns.
def does_not_bind : GICombinePatFrag<
  (outs root:$dst), (ins $x),
  [
    (pattern (G_FREEZE $dst, $x)), // binds $x
    (pattern (G_FOO $dst (i32 0))), // does not bind $x
    (pattern "return myCheck(${x}.getReg())"), // does not bind $x
  ]
>;

// Here we pass $x, which is unbound, to always_binds.
// This works because if $x is unbound, always_binds will bind it for us.
def test0 : GICombineRule<
  (defs root:$dst),
  (match (always_binds $dst, $x)),
  (apply (COPY $dst, $x))>;

// Here we pass $x, which is unbound, to does_not_bind.
// This cannot work because $x may not have been initialized in 'apply'.
// error: operand 'x' (for parameter 'src' of 'does_not_bind') cannot be unbound
def test1 : GICombineRule<
  (defs root:$dst),
  (match (does_not_bind $dst, $x)),
  (apply (COPY $dst, $x))>;

// Here we pass $x, which is bound, to does_not_bind.
// This is fine because $x will always be bound when emitting does_not_bind
def test2 : GICombineRule<
  (defs root:$dst),
  (match (does_not_bind $tmp, $x)
         (G_MUL $dst, $x, $tmp)),
  (apply (COPY $dst, $x))>;