https://github.com/rust-lang/rfcs/pull/396
It does have the effect of picking a single dominating entry point for a loop with multiple entry points, but if you want a single-entry region that's necessarily true. Multiple-entry regions are probably possible, but they could be counterintuitive and produce even stranger error messages than the current region system.
The borrow checker is based on dataflow analyses that should work on arbitrary CFGs, assuming an appropriately generalized notion of region.
"Just recently, however, Hoare has shown that there is, in fact, a rather simple way to give an axiomatic definition of go to statements; indeed, he wishes quite frankly that it hadn't been quite so simple....
"Informally, α(L) represents the desired state of affairs at label L; this definition says essentially that a program is correct if α(L) holds at L and before all "go to L" statements, and that control never "falls through" a go to statement to the following text. Stating the assertions α(L) is analogous to formulating loop invariants. Thus, it is not difficult to deal formally with tortuous program structure if it turns out to be necessary; all we need to know is the "meaning" of each label."
The benefits are enough that data structure and algorithm designs in the JVM compiler world often take advantage of assuming reducible control flow even though Java bytecode can express irreducible CFGs. Instead, such programs are left to the interpreter.
Most problems on reducible graphs are not easier than for general graphs, because you can always compute a loop forest (for generalized loops, not natural loops with a single entry point) and just consider a derived acyclic graph.
> you can always compute a loop forest
It's easier to not have to.
https://pp.info.uni-karlsruhe.de/uploads/publikationen/braun...
In the case of irreducible control-flow it may produce redundant cyclic phis, but those can be eliminated with a pretty simple post-pass.
True, but only in node-splitting approaches. If you use a label threading variable (as emscripten's relooper does), there is a guaranteed reasonable limit on code size increase (at the cost of performance).
(I don't recall whether the borrow checker actually depends on the control flow being reducible, but some of the possible future improvements we've talked about with "non-lexical lifetimes" definitely do. There are also nasty interactions between RAII and irreducible control flow…)