Page MenuHomePhabricator

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

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

Details

Summary

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.

Diff Detail

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?

llvm/utils/TableGen/GICombinerEmitter.cpp
453–456

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

Merge LLVM_DEBUG's

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

LGTM with a few nits.

llvm/utils/TableGen/GICombinerEmitter.cpp
334

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

458

Nit: curly braces can be removed.

llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.cpp
12

Nit: empty lines

21

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

llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h
14

Nit: empty line

This revision is now accepted and ready to land.Nov 15 2019, 10:23 AM
dsanders marked an inline comment as done.Nov 15 2019, 10:47 AM
dsanders added inline comments.
llvm/utils/TableGen/GICombinerEmitter.cpp
334

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.

dsanders marked 7 inline comments as done.Dec 17 2019, 7:00 AM
dsanders added inline comments.
llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.cpp
12

These empty lines were intended to separate the groups of includes from (http://llvm.org/docs/CodingStandards.html#include-style). However, it turns out clang-format is smart enough for that anyway. Removed them

llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h
14

Likewise for this one

This revision was automatically updated to reflect the committed changes.
dsanders marked 2 inline comments as done.

The new test case causes build bot failures (hidden by another failure that was already present):
http://lab.llvm.org:8011/builders/clang-s390x-linux/builds/28934/steps/ninja%20check%201/logs/FAIL%3A%20LLVM%3A%3Aparse-match-pattern.td

/home/uweigand/sandbox/buildbot/clang-s390x-linux/llvm/llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td:212:16: error: CHECK-NEXT: expected string not found in input
// CHECK-NEXT: 0:$<def>, 1:mi0, 2:mi1
               ^
<stdin>:129:16: note: scanning from here
 0:$<def>, 1:mi0, 2:mi1
               ^
<stdin>:130:2: note: possible intended match here
 0:$<def>, 1:mi
 ^

The test also fails on Windows: http://45.33.8.238/win/4272/step_11.txt

Looks like %p doesn't prefix pointers with 0x there.

phosek added a subscriber: phosek.Dec 17 2019, 4:56 PM

We're seeing a different failure on our 2-stage bots (in second stage):

/b/s/w/ir/k/llvm-project/llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td:30:17: error: CHECK-LABEL: expected string not found in input
// CHECK-LABEL: Parsed rule defs/match for 'trivial'
                ^
<stdin>:1:1: note: scanning from here
llvm-tblgen: for the -d option: may not occur within a group!
^
<stdin>:3:11: note: possible intended match here
llvm-tblgen: Did you mean '-d'?
          ^

The new test case causes build bot failures (hidden by another failure that was already present):
http://lab.llvm.org:8011/builders/clang-s390x-linux/builds/28934/steps/ninja%20check%201/logs/FAIL%3A%20LLVM%3A%3Aparse-match-pattern.td

/home/uweigand/sandbox/buildbot/clang-s390x-linux/llvm/llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td:212:16: error: CHECK-NEXT: expected string not found in input
// CHECK-NEXT: 0:$<def>, 1:mi0, 2:mi1
               ^
<stdin>:129:16: note: scanning from here
 0:$<def>, 1:mi0, 2:mi1
               ^
<stdin>:130:2: note: possible intended match here
 0:$<def>, 1:mi
 ^

I think I can hazard a reasonable guess what this one is going to be. It's probably printed in a slightly different order. I'll look into it

The test also fails on Windows: http://45.33.8.238/win/4272/step_11.txt

Looks like %p doesn't prefix pointers with 0x there.

Windows always has to be different :-). Ok, I can fix this by relaxing the regexes a bit

We're seeing a different failure on our 2-stage bots (in second stage):

/b/s/w/ir/k/llvm-project/llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td:30:17: error: CHECK-LABEL: expected string not found in input
// CHECK-LABEL: Parsed rule defs/match for 'trivial'
                ^
<stdin>:1:1: note: scanning from here
llvm-tblgen: for the -d option: may not occur within a group!
^
<stdin>:3:11: note: possible intended match here
llvm-tblgen: Did you mean '-d'?
          ^

Could you give me more information on this? Which bots is it? For now, I'm going to hazard a guess that the test just needs a 'REQUIRES: asserts'. Though it's a bit surprising that I don't have an email from one of the release-build bots if that were the problem

I've pushed 7ea2e5195a8 which should address these three issues