The MatchDag structure is a representation of the checks that need to be
performed and the dependencies that limit when they can happen.
There are two kinds of node in the MatchDag:
- Instrs - Represent a MachineInstr
- Predicates - Represent a check that needs to be performed (i.e. opcode, is register, same machine operand, etc.)
and two kinds of edges:
- (Traversal) Edges - Represent a register that can be traversed to find one instr from another
- Predicate Dependency Edges - Indicate that a predicate requires a piece of information to be tested.
For example, the matcher:
(match (MOV $t, $s),
(MOV $d, $t))
with MOV declared as an instruction of the form:
%dst = MOV %src1
becomes the following MatchDag with the following instruction nodes:
__anon0_0 // $t=getOperand(0), $s=getOperand(1) __anon0_1 // $d=getOperand(0), $t=getOperand(1)
__anon0_1[src1] --[t]--> __anon0_0[dst]
<<$mi.getOpcode() == MOV>>:$__anonpred0_2 <<$mi.getOpcode() == MOV>>:$__anonpred0_3
and predicate dependencies:
__anon0_0 ==> __anonpred0_2[mi] __anon0_0 ==> __anonpred0_3[mi]
The result of this parse is currently unused but can be tested
using -gicombiner-stop-after-parse as done in parse-match-pattern.td. The
dump for testing includes a graphviz format dump to allow the rule to be
Later on, these MatchDag's will be used to generate code and to build an
efficient decision tree.