The same problem arose discussing https://github.com/rust-lang/rust/issues/32966 with Scott Carr (username unknown). In particular, I wanted to port some graph algorithms code that I wrote to operate on MIR so that we can easily compute dominators, post-dominators, and so forth, but that code needs access to the predecessors for a node.
Anyway, all of this has reminded me that I wanted to discuss whether we are representing the graph in the right way. In the first version of the MIR representation that I wrote, I based it on the
rustc_data_structures::graph code. This means effectively that each basic block could have any number of successors and so forth – the terminator did not contain the basic blocks directly. Therefore, if you had a
Goto terminator, for example, you would expect exactly one successor, and if the terminator was
If, you would expect two successors (true, false), and so forth.
The advantage of this is that it is super easy to write generic graph traversal code – right now we have to use some rather awkward accessors (
successors_mut) for this. The disadvantage is that you have to maintain the correspondence for the terminator and the number of successors etc yourself. On balance, it seems better to use the generic graph than not to me-- I’ve used this system in many compilers in the past and never really had a problem with the terminator / set-of-successors getting out of scope.
So how do people feel about moving MIR back to use
librustc_data_structures::graph again to represent the graph? This would mean replacing the
Vec<BasicBlockData>, basically, with a
I’d also be open to some other graph representation, though (a) I think the one we have is pretty decent and (b) I’d prefer to just upgrade
librustc_data_structures::graph in that case, rather than having something special for MIR.