[gicombiner] Add the MatchDag structure and parse instruction DAG's from the…

Authored by dsanders on Dec 17 2019, 6:29 AM.


[gicombiner] Add the MatchDag structure and parse instruction DAG's from the input

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)

traversal edges:

__anon0_1[src1] --[t]--> __anon0_0[dst]

predicate nodes:

<<$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
viewed visually.

Later on, these MatchDag's will be used to generate code and to build an
efficient decision tree.

Reviewers: volkan, bogner

Reviewed By: volkan

Subscribers: arsenm, mgorny, mgrang, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D69077