experiment with bespoke graph representation

Copying some comments from NLL dropbox paper document for now:

Current analysis is slow primarily because it is computing the full transitive closure of the subset and requires relations at each program point. These are represented as tuples. This is O(N^2) storage and very inefficient.

The reason we do this is because of the way that we want to kill constraints when we find that regions are dead. The trick is that we want to preserve their transitive effects. So for example:

• If you have subset(Ra, Rb) and subset(Rb, Rc) at some program point P:
  • then we can also conclude (by transitivity) that subset(Ra, Rc)
• If Rb is dead at the successor point Q (but Ra and Rc are still live):
  • we still want subset(Ra, Rc) to be known at Q.

We currently handle this by generating everything and filtering. But you could imagine instead not using differential-dataflow and instead representing graphs as a set of edges (perhaps built using some persistent vectors, a la the graph impl in rustc). When we remove the edges for a given node, we would "reconnect" the incoming/outgoing edges. We can do this with varying degrees of efficiency.

The reason I mentioned using a persistent graph is that most nodes just clone the set of edges from the point before, and a persistent implementation would make that cheap. But there are lots of knobs to consider turning here.

(Ok, this issue is a bit vague, but I'm trying to capture and brainstorm here.)

Start with the existing representation of the subset and requires relations and the transitive-closure computation described in the issue. Compare the current differential-dataflow approach with the proposed persistent graph alternatives. Done would require a defined representation and evidence that it improves storage or analysis performance without losing transitive effects when regions are removed.