Comment by WalterBright
6 months ago
That makes me curious as to how Rust does the DFA. What I do is construct the data flow equations as bit vectors, which are then solved iteratively until a solution is converged on.
Doing this on the whole program eats a lot of memory.
I'm not an expert on this part of the compiler, but what I can tell you is that Rust uses multiple forms of IR, and the IR that the borrow checker operates on (https://rustc-dev-guide.rust-lang.org/mir/index.html) already encodes control flow. So doing that construction, at least, is just a normal part of the compiler, and isn't part of the borrow checker itself.
However, in my understanding, it takes that IR, does build a borrow graph, computes liveliness, and then does inference. There's been a number of details in how this has changed over the years, but it's vaguely datalog shaped.
Because there are cycles in the flow graph, I do not see how liveness can be computed in general without iteration and convergence on a solution.