As said many times in this thread already, the borrow checker is virtually never a significant amount of time spent while compiling.
replyAlso, the article goes into great depth as to what is happening there, and the borrow checker never comes up.
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.
replyDoing 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.
replyHowever, 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.
reply