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) 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.

Pattern Example 1¶

// Match
//    %imp = G_IMPLICIT_DEF
//    %root = G_MUL %x, %imp
(match (G_IMPLICIT_DEF $imp),
       (G_MUL $root, $x, $imp))

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.

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))
>;

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 ¶

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 ¶

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.

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.

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.

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.

Matching intrinsics is not yet possible.
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.

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))
>;

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 additional code after rewriting a pattern.

The following expansions are available for MIR patterns:

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

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).

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.

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)>;

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))>;

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))>;

Documentation

Getting Involved

Additional Links

This Page

MIR Patterns in TableGen¶

User’s Guide ¶

Use Cases ¶

Syntax ¶

Types ¶

ValueType ¶

GITypeOf ¶

Builtin Operations ¶

GIReplaceReg ¶

GIEraseRoot ¶

Instruction Flags ¶

Limitations ¶

GICombineRule ¶

Common Pattern #1: Replace a Register with Another ¶

Common Pattern #2: Erasing a Def-less Root ¶

Common Pattern #3: Emitting a Constant Value ¶

GICombinePatFrag ¶