Page MenuHomePhabricator

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

Authored by dsanders on Oct 16 2019, 6:33 PM.



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

Event Timeline

dsanders created this revision.Oct 16 2019, 6:33 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 16 2019, 6:33 PM
Herald added subscribers: mgrang, mgorny. · View Herald Transcript
arsenm added a subscriber: arsenm.Oct 25 2019, 1:18 PM

Is there a mechanism here for supporting hasOneUse checks?


merge into one LLVM_DEBUG block?

Is there a mechanism here for supporting hasOneUse checks?

At the moment it's available using the code-block escape hatch:

(match ...
       [{ ...
          if (!MRI.hasOneUse(${root}.getOperand(1).getReg()))
            return false;

There's a patch that I haven't posted yet (just to keep the patches under review to a reasonable number) that adds the arbitrary C++ predicate feature (GIMatchPredicate from the original proposal) and that will be the preferred way to use it unless/until we decide that GIMatchTree (D69152) needs to be aware of it

dsanders updated this revision to Diff 226496.Oct 25 2019, 1:52 PM


dsanders marked an inline comment as done.Oct 25 2019, 1:55 PM
volkan accepted this revision.Fri, Nov 15, 10:23 AM

LGTM with a few nits.


Is there a reason not to add continue here? Do we want to keep processing if it failed to add edges?


Nit: curly braces can be removed.


Nit: empty lines


Nit: this can be replaced with if (auto Annotation = getOpcodeAnnotation())


Nit: empty line

This revision is now accepted and ready to land.Fri, Nov 15, 10:23 AM
dsanders marked an inline comment as done.Fri, Nov 15, 10:47 AM
dsanders added inline comments.

It's so that we print more errors (if there are any) before we give up. This helps the developer fix all their mistakes in fewer attempts.