News for hackers. Stuff that matters.
Re:Things Rust shipped without by gsg on Friday July 03, 2015 @03:24PM (#9827483)
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.

Re:Things Rust shipped without by cwzwarich on Friday July 03, 2015 @03:54PM (#9827605)
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.

Re:Things Rust shipped without by gsg on Saturday July 04, 2015 @12:31AM (#9829212)
The 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.

Re:Things Rust shipped without by cwzwarich on Saturday July 04, 2015 @02:59AM (#9829497)
Technically 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/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.