Cleanup includes for LLVMTableGenGlobalISel

Based on the output of include-what-you-use. No big deal here, it's a utils
library and it doesn't seem to be used a lot across the codebase.

$ clang++ -

Cleanup includes for LLVMTableGenGlobalISel

Based on the output of include-what-you-use. No big deal here, it's a utils
library and it doesn't seem to be used a lot across the codebase.

$ clang++ -E -Iinclude -I../llvm/include ../llvm/utils/TableGen/GlobalISel/*.cpp -std=c++14 -fno-rtti -fno-exceptions | wc -l
before: 573143
after: 568908

Related Discourse thread: https://llvm.discourse.group/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D118375

show more ...

[gicombiner] Add GIMatchTree and use it for the code generation

Summary:
GIMatchTree's job is to build a decision tree by zipping all the
GIMatchDag's together.

Each DAG is added to the tree builde

[gicombiner] Add GIMatchTree and use it for the code generation

Summary:
GIMatchTree's job is to build a decision tree by zipping all the
GIMatchDag's together.

Each DAG is added to the tree builder as a leaf and partitioners are used
to subdivide each node until there are no more partitioners to apply. At
this point, the code generator is responsible for testing any untested
predicates and following any unvisited traversals (there shouldn't be any
of the latter as the getVRegDef partitioner handles them all).

Note that the leaves don't always fit into partitions cleanly and the
partitions may overlap as a result. This is resolved by cloning the leaf
into every partition it belongs to. One example of this is a rule that can
match one of N opcodes. The leaf for this rule would end up in N partitions
when processed by the opcode partitioner. A similar example is the
getVRegDef partitioner where having rules (add $a, $b), and (add ($a, $b), $c)
will result in the former being in the partition for successfully
following the vreg-def and failing to do so as it doesn't care which
happens.

Depends on D69151

Fixed the issues with the windows bots which were caused by stdout/stderr
interleaving.

Reviewers: bogner, volkan

Reviewed By: volkan

Subscribers: lkail, mgorny, llvm-commits

Tags: #llvm

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

show more ...

Revert "[gicombiner] Add GIMatchTree and use it for the code generation"

All the windows bots are failing match-tree.td and there's no obvious cause that
I can see. It's not just the %p formatting p

Revert "[gicombiner] Add GIMatchTree and use it for the code generation"

All the windows bots are failing match-tree.td and there's no obvious cause that
I can see. It's not just the %p formatting problem. My best guess is that
there's an ordering issue too but I'll need further information to figure that
out. Revert while I'm investigating.

This reverts commit 64f1bb5cd2c6d69af7c74ec68840029603560238 and 77d4b5f5feff663e70b347516cc4c77fa5cd2a20

show more ...

[gicombiner] Add GIMatchTree and use it for the code generation

Summary:
GIMatchTree's job is to build a decision tree by zipping all the
GIMatchDag's together.

Each DAG is added to the tree builde

[gicombiner] Add GIMatchTree and use it for the code generation

Summary:
GIMatchTree's job is to build a decision tree by zipping all the
GIMatchDag's together.

Each DAG is added to the tree builder as a leaf and partitioners are used
to subdivide each node until there are no more partitioners to apply. At
this point, the code generator is responsible for testing any untested
predicates and following any unvisited traversals (there shouldn't be any
of the latter as the getVRegDef partitioner handles them all).

Note that the leaves don't always fit into partitions cleanly and the
partitions may overlap as a result. This is resolved by cloning the leaf
into every partition it belongs to. One example of this is a rule that can
match one of N opcodes. The leaf for this rule would end up in N partitions
when processed by the opcode partitioner. A similar example is the
getVRegDef partitioner where having rules (add $a, $b), and (add ($a, $b), $c)
will result in the former being in the partition for successfully
following the vreg-def and failing to do so as it doesn't care which
happens.

Depends on D69151

Reviewers: bogner, volkan

Reviewed By: volkan

Subscribers: lkail, mgorny, llvm-commits

Tags: #llvm

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

show more ...

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

This reverts commit e62e760f29567fe0841af870c65a4f8ef685d217.

The issue @uweigand ra

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

This reverts commit e62e760f29567fe0841af870c65a4f8ef685d217.

The issue @uweigand raised should have been fixed by iterating over the
vector that owns the operand list data instead of the FoldingSet.

The MSVC issue raised by @thakis should have been fixed by relaxing the
regexes a little. I don't have a Windows machine available to test that so
I tested it by using `perl -p -e 's/0x([0-9a-f]+)/\U\1\E/g' to convert the
output of %p to the windows style.

I've guessed at the issue @phosek raised as there wasn't enough information
to investigate it. What I think is happening on that bot is the -debug
option isn't available because the second stage build is a release build.
I'm not sure why other release-mode bots didn't report it though.

show more ...

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

Summary:
The MatchDag structure is a representation of the checks that need to be
performed and the dependencies th

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

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.

Reviewers: volkan, bogner

Reviewed By: volkan

Subscribers: arsenm, mgorny, mgrang, llvm-commits

Tags: #llvm

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

show more ...