This is an archive of the discontinued LLVM Phabricator instance.

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

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

Details

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

Diff Detail

Event Timeline

dsanders created this revision.Oct 17 2019, 6:33 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 17 2019, 6:33 PM
Herald added a subscriber: mgorny. · View Herald Transcript
lkail added a subscriber: lkail.Oct 18 2019, 5:35 AM
volkan accepted this revision.Dec 18 2019, 2:58 PM

LGTM.

llvm/include/llvm/Target/GlobalISel/Combine.td
106–108

Missing wip_match_opcode for COPY?

This revision is now accepted and ready to land.Dec 18 2019, 2:58 PM
dsanders marked an inline comment as done.Jan 3 2020, 4:22 PM
dsanders added inline comments.
llvm/include/llvm/Target/GlobalISel/Combine.td
106–108

It's not needed here as COPY is the only thing it matches. wip_match_opcode is a temporary way of matching one of a set of opcodes until the feature that supports a choice of patterns becomes available.

This revision was automatically updated to reflect the committed changes.
dsanders reopened this revision.Jan 3 2020, 7:20 PM
This revision is now accepted and ready to land.Jan 3 2020, 7:20 PM
This revision was automatically updated to reflect the committed changes.
thakis added a subscriber: thakis.Jan 7 2020, 11:29 AM

This broke tests on Windows: http://45.33.8.238/win/5239/step_11.txt

Probably the "%p doesn't include 0x on Windows" thing again.

This broke tests on Windows: http://45.33.8.238/win/5239/step_11.txt

Probably the "%p doesn't include 0x on Windows" thing again.

It looks like I undid the fixup I did the last time I committed this. It should be fixed in 19110fd982b (I cherry-picked 77d4b5f5fef to re-apply the fix)

thakis added a comment.Jan 7 2020, 1:01 PM

Thanks, the bot is happy again. (Looks like the commit landed just now though.)