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

[dsanders]

Summary

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

[dsanders]

llvm/utils/TableGen/GICombinerEmitter.cpp

146

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:

A->B->C->D->E

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

A->{B,C,D,E}

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

A->{B,C}
B->{D,E}

If it becomes a bottleneck then I can improve this

[volkan]

LGTM with a couple of nits.

llvm/utils/TableGen/GICombinerEmitter.cpp

160

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

189

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

[dsanders]

llvm/utils/TableGen/GICombinerEmitter.cpp

189

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

[dsanders]

Landed in rG520e3d66e7257c77f1226185504bbe1cb90afcfa (and re-committed in rG7ea2e5195a82bd9370d0b4362512b67c8b2cde80