dataflow: use CFGIndex directly as bitvector index

7d244d9
Opened by Felix S Klock II at 2014-07-18 20:01:46

One of the artifacts left over from the old dataflow analysis code was that it had a NodeId to bitvector index mapping that it maintained, since the NodeIds in question were often sparse and also could fall into a range far from starting from zero.

When @pnkfelix converted the code to use the control-flow-graph abstraction, he switched things so that the CFGIndex instead mapped to the relevant bitvector index, and then a different table mapped NodeId to CFGIndex.

The first aforementioned table is index_to_bitset, here: https://github.com/rust-lang/rust/pull/14873/files#diff-158b34791d327b238be103c2d1867e71R48

That's fine, except that the assumptions that motivated using a bitvector index distinct from NodeId (sparse, and starts from from zero) may not hold for CFGIndex.

More specifically, CFGIndex definitely starts from zero. And they are probably very very dense.

It would be good to:

  1. (Informally) confirm that CFGIndex is dense (i.e. gather some quick stats), and then
  2. If the above hypothesis holds up, then get rid of the separate bitvector indices, and just use the CFGIndex directly as the index into the bitvector for dataflow.

  1. (As noted in a comment on #15371, doing this should allow us to get rid of the somewhat ugly frozen/non-frozen distinction in the cfg API.)

    Felix S Klock II at 2014-07-15 10:32:03

  2. A potential advantage of doing this that I just realized: since the CFGIndex is emitted directly in the --pretty flowgraph graphviz output, making the CFGIndex correspond to the bitvector index would allow a determined RUST_LOG reader to decode the bitvectors in the output by looking at the corresponding graphviz output.

    Felix S Klock II at 2014-07-16 15:29:19

  3. it is definitely dense (and maximally so). I had convinced myself earlier that there could be gaps, but that seems to have been incorrect: according to my instrumentation, the index_to_bitset map is always a permutation on the indexes 0..n where n is the max CFGIndex. So yeah, we should just go ahead and do this.

    Felix S Klock II at 2014-07-16 21:33:02

  4. (and a random thought I had while reflecting on this: if we actually allocated extra NodeIds with each expr type that introduces dummy nodes (at least, I believe there is a statically determinable upper bound on the number of dummy cfg nodes per expr node), then the relation between Expr Node ID and CFGIndex would be a simple offset calculation determined from the NodeId of the block itself. That would save us the time of building up the map that is currently used to represent that relation explicitly.)

    update: the above idea isn't ridiculous, but it also isn't an obvious win: You still have the problem that the NodeId's are sparse, i.e. that there may be large gaps between different NodeId's associated with the same control flow graph.

    Felix S Klock II at 2014-07-16 21:35:28