4 ms·
Rust's CFGs are reducible with unbounded treewidth, not structured, because Rust has named exits from loops that nest arbitrarily. Most problems on reducible g
by cwzwarich 11y ago
Rust's CFGs are reducible with unbounded treewidth, not structured, because Rust has named exits from loops that nest arbitrarily.
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.
- gsg 11y agoThe structured SSA building algorithm I had in mind has a fairly simple extension that covers break, continue, and early return. It's more complicated, but still way simpler than iterated dominance frontiers. > you can always compute a loop forest It's easier to not have to.
- cwzwarich 11y agoTechnically speaking, break / continue / early return are unstructured by the classical definition. The algorithm you are likely thinking of can easily be extended to handle arbitrary control-flow: https://pp.info.uni-karlsruhe.de/uploads/publikationen/braun13cc.pdf 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.