Page MenuHomePhabricator

[gicombiner] Process the MatchDag such that every node is reachable from the roots

Authored by dsanders on Oct 17 2019, 9:55 AM.



When we build the walk across these DAG's we need to be able to reach every node
from the roots. Flip and traversal edges (so that use->def becomes def->uses)
that make nodes unreachable. Note that early on we'll just error out on these
flipped edges as def->uses edges are more complicated to match due to their
one->many nature.

Depends on D69077

Event Timeline

dsanders created this revision.Oct 17 2019, 9:55 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 17 2019, 9:55 AM
Herald added a subscriber: dexonsmith. · View Herald Transcript
dsanders marked an inline comment as done.Oct 17 2019, 10:03 AM
dsanders added inline comments.

During an off-list review it was pointed out that this is quadratic in the worst case. I haven't fixed that yet but I don't think it's likely to be an issue in practice. This is partly due to the DAG's tending to be small (1-5 instr nodes) but is mostly due to the common case for the shape of the DAG.

The quadratic case is a 'straight-line' DAG of the form:


which can occasionally occur but is rarely more than 3 nodes long. The best case is a fan-out like:


which is linear but most DAGs will be roughly nlogn. For example:


If it becomes a bottleneck then I can improve this

volkan accepted this revision.Nov 15 2019, 10:39 AM

LGTM with a couple of nits.


No need to create a new set for each edge, this can be moved outside of the loop.


Looks like there is no other debug output in this functions, is it worth keeping this?

This revision is now accepted and ready to land.Nov 15 2019, 10:39 AM
dsanders marked 2 inline comments as done.Dec 17 2019, 8:34 AM
dsanders added inline comments.

It's useful for seeing where the overall tablegen pass has got to.