4 ms·
Yeah. Even basic things like building SSA can be done more simply on "structured" CFGs. The benefits are enough that data structure and algorithm designs in th
by gsg 11y ago
Yeah. Even basic things like building SSA can be done more simply on "structured" CFGs.
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.
- cwzwarich 11y agoRust'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.