1 of 87

Interpreted Pattern Match Execution

Jeff Niu

2 of 87

Agenda

Background and motivation
Turning patterns into bytecode
Dialect for patterns
Optimizing patterns
Dialect for a state machine
Quick look at the interpreter
Performance metrics
Current status and what’s next

3 of 87

Background

4 of 87

Match and Rewrite

Underlies many MLIR code transformations
Not runtime extensible
Has room for match optimization
Binary size bloat

5 of 87

Runtime Extensibility

mlir-opt -opt-patterns=MyOptPatterns.pat

-legalize-patterns=MyLegalizePatterns.pat

6 of 87

Duplicate Work

def MyPatternA : Pattern<

(OpA $arg, $attr),

(OpB $arg),

[(CheckD $arg)]>;

def MyPatternB : Pattern<

(OpA $arg, $attr),

(OpC $arg, $attr),

[(CheckE $arg)]>;

7 of 87

Duplicate Work

def MyPatternA : Pattern<

(OpA $arg, $attr),

(OpB $arg),

[(CheckD $arg)]>;

def MyPatternB : Pattern<

(OpA $arg, $attr),

(OpC $arg, $attr),

[(CheckE $arg)]>;

op0.getAttr(“myAttr”)

8 of 87

Pattern Pipeline

Python

JSON

Swift

...

TableGen

PDL

Predicate List

FSM

Bytecode

MLIR emitter

Merge

Lowering MLIR

-O0

9 of 87

Pattern Descriptor Language

10 of 87

Building MLIR with MLIR

def FusedMAdd : Pattern<(AddOp $x, (MulOp $y, $z)), (MAddOp $x, $y, $z)>;

def : Pattern<(MAddOp $x, $y, $z), (MAddIOp $x, $y, $z), [(isInt $x)]>;

def : Pattern<(MAddOp $x, $y, $z), (MAddFOp $x, $y, $z), [(isFlt $x)]>;

11 of 87

Building MLIR with MLIR

def FusedMAdd : Pattern<(AddOp $x, (MulOp $y, $z)), (MAddOp $x, $y, $z)>;

def : Pattern<(MAddOp $x, $y, $z), (MAddIOp $x, $y, $z), [(isInt $x)]>;

def : Pattern<(MAddOp $x, $y, $z), (MAddFOp $x, $y, $z), [(isFlt $x)]>;

pdl.pattern @FusedMAdd {

%x, %y, %z = pdl.ins 3

%mul_op, %mul_ret = pdl.node “u.mul”(%y, %z)

%add_op, %add_ret = pdl.node “u.add”(%x, %mul_ret)

pdl.output(%add_op) {

%madd_op, %madd_ret = pdl.node “u.madd”(%x, %y, %z)

pdl.replace -> (%madd_ret)

}

pdl.pattern {

%x, %y, %z = pdl.ins 3

pdl.constraint “isInt”(%x : value)

%madd_op, %madd_ret = pdl.node “u.madd”(%x, %y, %z)

pdl.output(%madd_op) {

%maddi_op, %maddi_ret = pdl.node “u.maddi”(%x, %y, %z)

pdl.replace -> (%maddi_ret)

}

pdl.pattern {

%x, %y, %z = pdl.ins 3

pdl.constraint “isFlt”(%x : value)

%madd_op, %madd_ret = pdl.node “u.madd”(%x, %y, %z)

pdl.output(%madd_op) {

%maddf_op, %maddf_ret = pdl.node “u.maddf”(%x, %y, %z)

pdl.replace -> (%maddf_ret)

}

12 of 87

Building MLIR with MLIR

def FusedMAdd : Pattern<(AddOp $x, (MulOp $y, $z)), (MAddOp $x, $y, $z)>;

def : Pattern<(MAddOp $x, $y, $z), (MAddIOp $x, $y, $z), [(isInt $x)]>;

def : Pattern<(MAddOp $x, $y, $z), (MAddFOp $x, $y, $z), [(isFlt $x)]>;

pdl.pattern @FusedMAdd {

%x, %y, %z = pdl.ins 3

%mul_op, %mul_ret = pdl.node “u.mul”(%y, %z)

%add_op, %add_ret = pdl.node “u.add”(%x, %mul_ret)

pdl.output(%add_op) {

%madd_op, %madd_ret = pdl.node “u.madd”(%x, %y, %z)

pdl.replace -> (%madd_ret)

}

pdl.pattern {

%x, %y, %z = pdl.ins 3

pdl.constraint “isInt”(%x : value)

%madd_op, %madd_ret = pdl.node “u.madd”(%x, %y, %z)

pdl.output(%madd_op) {

%maddi_op, %maddi_ret = pdl.node “u.maddi”(%x, %y, %z)

pdl.replace -> (%maddi_ret)

}

pdl.pattern {

%x, %y, %z = pdl.ins 3

pdl.constraint “isFlt”(%x : value)

%madd_op, %madd_ret = pdl.node “u.madd”(%x, %y, %z)

pdl.output(%madd_op) {

%maddf_op, %maddf_ret = pdl.node “u.maddf”(%x, %y, %z)

pdl.replace -> (%maddf_ret)

}

13 of 87

Building MLIR with MLIR

def FusedMAdd : Pattern<(AddOp $x, (MulOp $y, $z)), (MAddOp $x, $y, $z)>;

from mlir import pdl

from dialects import U

ins = pdl.Ins(3)

mul = pdl.Node(U.Mul, ins[1], ins[2])

add = pdl.Node(U.Add, ins[0], mul[0])

pdl.Replace(add, pdl.Node(U.MAdd, ins[0], ins[1], ins[2]))

// Verify patterns

mlir::verify(myPdlPatterns);

14 of 87

PDL Extensibility

%optional = pdl.attr ?

/* ... */

pdl.output(%root) {

%defAttr = pdl.render attr “useDefault”<42 : i16>(%optional : attr)

/* ... */

}

15 of 87

PDL Extensibility

%optional = pdl.attr ?

/* ... */

pdl.output(%root) {

%defAttr = pdl.render attr “useDefault”<42 : i16>(%optional : attr)

/* ... */

}

GenericValue useDefault(GenericValue arg,

Attribute defVal) {

return arg ? arg : defVal;

}

16 of 87

PDL Extensibility

pdl.constraint “atLeastOneIsOneOf”<1, 2, 4, i16, “abc”, ...>(

%attr0, %attr1, %attr2, ..., %attrN

)

bool atLeastOneIsOneOf(ArrayRef<GenericValue> args,

ArrayAttr params) {

for (auto &arg : args)

if (llvm::find(params, arg.get<Attribute>()) != params.end())

return true;

return false;

}

17 of 87

Pattern Optimization

18 of 87

The Literature

19 of 87

Become as One

20 of 87

Strings are Patterns

[“racecar”,

“racetrack”,

“rancid”]

21 of 87

Strings are Patterns

[“running”,

“raining”,

“craving”]

22 of 87

Strings are Patterns

[“running”,

“raining”,

“craving”]

23 of 87

Strings are Patterns

[“ABC”,

“AAC”,

“CBA”]

24 of 87

Patterns are Strings

25 of 87

Patterns are Strings

26 of 87

Patterns are Strings

27 of 87

Patterns are Strings

{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}

28 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

29 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

30 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

31 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

32 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

33 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

34 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

35 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

36 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

"add"

37 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

"add"

38 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

"add"

[0] → 0

EqualTo<[0] → 1>

39 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

"add"

[0] → 0

EqualTo<[0] → 1>

true

40 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

"add"

[0] → 0

EqualTo<[0] → 1>

true

41 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

"add"

[0] → 0

EqualTo<[0] → 1>

true

42 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

"add"

[0] → 0

EqualTo<[0] → 1>

true

43 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

"add"

[0] → 0

EqualTo<[0] → 1>

true

44 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

"add"

[0] → 0

EqualTo<[0] → 1>

true

45 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

"add"

[0] → 0

EqualTo<[0] → 1>

true

46 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

"add"

[0] → 0

EqualTo<[0] → 1>

true

47 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

"add"

[0] → 0

EqualTo<[0] → 1>

true

48 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

49 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

50 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

51 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

52 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

53 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

54 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

55 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

56 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

57 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

58 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

59 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

60 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

61 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

62 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

63 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

false

64 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

[0,1]

ArgCount

false

65 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

[0,1]

ArgCount

false

2

66 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

[0,1]

ArgCount

false

2

67 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

[0,1]

ArgCount

false

2

[0,1]

OpName

68 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

[0,1]

ArgCount

false

2

[0,1]

OpName

"mul"

69 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

[0,1]

ArgCount

false

2

[0,1]

OpName

"mul"

70 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

[0,1]

ArgCount

false

2

[0,1]

OpName

"mul"

71 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

[0]

ArgCount

2

[0]

OpName

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0] → 0

EqualTo<[0] → 1>

true

[0,1]

ArgCount

false

2

[0,1]

OpName

"mul"

return

else

72 of 87

Pattern Matching FSM

{[0], ArgCount}

{[0], OpName}

{[0] → 0, EqualTo<[0] → 1>}

{[0,1], ArgCount}

{[0,1], OpName}

[0]

ArgCount

[0]

OpName

2

return

else

[0] → 0

EqualTo<[0] → 1>

[0] → 0

EqualTo<[0] → 1>

"mul"

"add"

true

[0,1]

ArgCount

false

[0,1]

OpName

2

"mul"

else

false

else

{[0], ArgCount, 2} {[0], OpName, “add”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “mul”} {[0] → 0, EqualTo<[0] → 1>, true}	{[0], ArgCount, 2} {[0], OpName, “add”} {[0,1], ArgCount, 2} {[0,1], OpName, “mul”}

73 of 87

Interpreter Dialect

74 of 87

CFG → MLIR

func @matcher(%0 : !Operation) {

^bb0:

CheckArgCount(%0) [^ex0, ^bb1] {count = 2}

^bb1:

SwitchOpName(%0) [^ex0, ^bb2, ^bb3]

{names = ["mul", "add"]}

^bb2:

%1 = GetOperand(%0) {index = 0}

%2 = GetOperand(%0) {index = 1}

EqualTo(%1, %2) [^ex0, ^rr3]

^rr0:

RegisterResult() [^ex0] {id = 0}

^bb3:

%3 = GetOperand(%0) {index = 0}

%4 = GetOperand(%0) {index = 1}

EqualTo(%3, %4) [^bb4, ^rr1]

^rr1:

RegisterResult() [^bb4] {id = 1}

^bb4:

%5 = GetDefiningOp(%4)

CheckArgCount(%5) [^ex0, ^bb5] {count = 2}

^bb5:

CheckOpName(%5) [^ex0, ^rr2] {name = "mul"}

^rr2:

RegisterResult() [^ex0] {id = 2}

^ex0:

return

}

75 of 87

Lowering to Byte-Code

func @matcher(%0 : !Operation) {

^bb0:

CheckArgCount(%0) [^ex0, ^bb1] {count = 2}

^bb1:

SwitchOpName(%0) [^ex0, ^bb2, ^bb3]

{names = ["mul", "add"]}

^bb2:

%1 = GetOperand(%0) {index = 0}

%2 = GetOperand(%0) {index = 1}

EqualTo(%1, %2) [^ex0, ^rr0]

^rr0:

RegisterResult() [^ex0] {id = 0}

^bb3:

%3 = GetOperand(%0) {index = 0}

%4 = GetOperand(%0) {index = 1}

EqualTo(%3, %4) [^bb4, ^rr1]

^rr1:

RegisterResult() [^bb4] {id = 1}

^bb4:

%5 = GetDefiningOp(%4)

CheckArgCount(%5) [^ex0, ^bb5] {count = 2}

^bb5:

CheckOpName(%5) [^ex0, ^rr2] {name = "mul"}

^rr2:

RegisterResult() [^ex0] {id = 2}

^ex0:

return

}

FuncOp matcher = …

matcher.walk(convertToByteCode);

[2, 2, 0, 63, 5, 17, 0, 0, 1, 63, 10, 25, 6, 0, 0, 1, 6, 0, 1, 2, 16, 1, 2, 63, 21, 1, 0, 63, 6, 0, 0, 1, 6, 0, 1, 2, 16, 1, 2, 40, 37, 1, 1, 42, 8, 4, 3, 2, 2, 5, 63, 55, 3, 3, 0, 63, 60, 21, 2, 63, 0]

names = [“mul”, “add”]

76 of 87

Static Info

func @matcher(%0 : !Operation) {

^bb0:

CheckArgCount(%0) [^ex0, ^bb1] {count = 2}

^bb1:

SwitchOpName(%0) [^ex0, ^bb2, ^bb3]

{names = ["mul", "add"]}

^bb2:

%1 = GetOperand(%0) {index = 0}

%2 = GetOperand(%0) {index = 1}

EqualTo(%1, %2) [^ex0, ^rr0]

^rr0:

RegisterResult() [^ex0] {id = 0}

^bb3:

%3 = GetOperand(%0) {index = 0}

%4 = GetOperand(%0) {index = 1}

EqualTo(%3, %4) [^bb4, ^rr1]

^rr1:

RegisterResult() [^bb4] {id = 1}

^bb4:

%5 = GetDefiningOp(%4)

CheckArgCount(%5) [^ex0, ^bb5] {count = 2}

^bb5:

CheckOpName(%5) [^ex0, ^rr2] {name = "mul"}

^rr2:

RegisterResult() [^ex0] {id = 2}

^ex0:

return

}

[2, 2, 0, 63, 5, 17, 0, 0, 1, 63, 10, 25, 6, 0, 0, 1, 6, 0, 1, 2, 16, 1, 2, 63, 21, 1, 0, 63, 6, 0, 0, 1, 6, 0, 1, 2, 16, 1, 2, 40, 37, 1, 1, 42, 8, 4, 3, 2, 2, 5, 63, 55, 3, 3, 0, 63, 60, 21, 2, 63, 0]

names = [“mul”, “add”]

77 of 87

Memory Allocation

func @matcher(%0 : !Operation) {

^bb0:

CheckArgCount(%0) [^ex0, ^bb1] {count = 2}

^bb1:

SwitchOpName(%0) [^ex0, ^bb2, ^bb3]

{names = ["mul", "add"]}

^bb2:

%1 = GetOperand(%0) {index = 0}

%2 = GetOperand(%0) {index = 1}

EqualTo(%1, %2) [^ex0, ^rr0]

^rr0:

RegisterResult() [^ex0] {id = 0}

^bb3:

%3 = GetOperand(%0) {index = 0}

%4 = GetOperand(%0) {index = 1}

EqualTo(%3, %4) [^bb4, ^rr1]

^rr1:

RegisterResult() [^bb4] {id = 1}

^bb4:

%5 = GetDefiningOp(%4)

CheckArgCount(%5) [^ex0, ^bb5] {count = 2}

^bb5:

CheckOpName(%5) [^ex0, ^rr2] {name = "mul"}

^rr2:

RegisterResult() [^ex0] {id = 2}

^ex0:

return

}

[2, 2, 0, 63, 5, 17, 0, 0, 1, 63, 10, 25, 6, 0, 0, 1, 6, 0, 1, 2, 16, 1, 2, 63, 21, 1, 0, 63, 6, 0, 0, 1, 6, 0, 1, 2, 16, 1, 2, 40, 37, 1, 1, 42, 8, 4, 3, 2, 2, 5, 63, 55, 3, 3, 0, 63, 60, 21, 2, 63, 0]

names = [“mul”, “add”]

78 of 87

Comparison to LLVM

SelectionDagISel

Contract nodes
Factor nodes
vector<vector<...>>

GlobalISel

Direct improvement over SelectionDagISel
Plus some small optimizations
Uses a single vector<...>

MLIR

More optimal merge/factor of nodes
A few rewrite patterns on FSM
Preallocated vector<...>

Now there is the inevitable comparison to how LLVM does it. After all, I did steal ideas from LLVM.

MLIR adds additional problems so kind of apples vs. oranges

SelectionDagISel just performs two optimizations on its matchers.

The interpreter uses a vector of vectors to manage memory.

“Contact nodes” collapses common series of instructions

We do this using MLIR RewritePatterns on the matcher MLIR

Factor nodes is similar to how we build the FSM, 2 major differences

The approach is greedy, whereas we analyze the patterns to determine the best “factor order”
SelectionDagISel enforces a match order, which creates merge barriers that impact overall performance

GlobalISel is in many regards a direct improvement:

A single vector instead of a stack of vectors
A few additional small optimizations: trying to delay custom constraints
Core matcher optimization is the same as FactorNodes

I think I can conclude that the approach that was implemented is better than what exists in LLVM, in at least one major aspect

79 of 87

Merge Barriers

D

C

B

A

C

B

A

B

A

10

9

3

1

A

B

C

D

1

3

9

10

true

false

80 of 87

Merge Barriers

D

C

B

A

C

B

A

B

A

10

9

3

1

Y

X

5

X

Y

A

B

C

D

1

3

9

10

true

false

5

true

A

B

true

false

81 of 87

Metrics

82 of 87

Estimates*

Bytecode is ~10x smaller than pattern object file
Pattern merge time is ~15x faster than compiling in Clang

83 of 87

Pattern Match Runtime

50

84 of 87

Pattern Match Runtime

Seems to remove number of patterns from runtime complexity
Interpreter adds ~15 ms of overhead

85 of 87

Current Status

Not upstream
No support for ODS variadic arguments as in TableGen
Otherwise feature-complete
Hybrid pattern generator from TableGen

86 of 87

Next Steps

Not upstream
No support for ODS variadic arguments as in TableGen
Otherwise feature-complete
Hybrid pattern generator from TableGen

87 of 87

That’s all folks

Questions?