News for hackers. Stuff that matters.
Re:Things Rust shipped without by pcwalton on Friday July 03, 2015 @02:55PM (#9827305)
It often simplifies a lot of the compiler implementation if you only have reducible control flow. LLVM is fine with irreducible control flow, because it has to handle C, but rustc uses a CFG for the borrow checker, which is flow-sensitive. You can convert irreducible control flow to reducible control flow, but it can explode the size of the graph in pathological cases.

(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…)

Re:Things Rust shipped without by cwzwarich on Friday July 03, 2015 @03:48PM (#9827582)
Non-lexical lifetimes don't depend on reducibility. The RFC I wrote works fine for irreducible CFGs:

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.

Re:Things Rust shipped without by EugeneOZ on Saturday July 04, 2015 @01:11AM (#9829309)
I think the point of parent comment is "it's ok to don't have goto in Rust, but it's not the reason to be proud of just not having goto". Goto is important enough operator and doesn't deserve blind hate.
Re:Things Rust shipped without by tracker1 on Saturday July 04, 2015 @01:30AM (#9829347)
Agreed... I honestly tend to break code into a lot of discrete functions, and combine for workflows, but sometimes you just need to easily jump back a few places, and where goto is available it's not always a bad option. Just one that should be used sparingly... once in a complex workflow is fine.. more than twenty times in a few thousand line method, not so much.
Re:Things Rust shipped without by mcguire on Saturday July 04, 2015 @12:24PM (#9830611)
Don Knuth, "Structured Programming with go to Statements":

"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."

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.

Re:Things Rust shipped without by haberman on Friday July 03, 2015 @04:27PM (#9827753)
At least reserve the word, in case you change your mind in the future? I guess it's too late now...
Re:Things Rust shipped without by Maken on Friday July 03, 2015 @04:56PM (#9827912)
Burn the boats and never look back, I guess.
Re:Things Rust shipped without by GFK_of_xmaspast on Friday July 03, 2015 @05:44PM (#9828114)
Since when does rust care about breaking changes to the language.
Re:Things Rust shipped without by steveklabnik on Friday July 03, 2015 @05:45PM (#9828117)
Seven weeks ago today.
Re:Things Rust shipped without by mcguire on Saturday July 04, 2015 @12:25PM (#9830616)
For version 1? Can we break on 2.0?
Re:Things Rust shipped without by steveklabnik on Saturday July 04, 2015 @12:27PM (#9830620)
Re:Things Rust shipped without by azakai on Friday July 03, 2015 @04:06PM (#9827658)
> You can convert irreducible control flow to reducible control flow, but it can explode the size of the graph in pathological cases.

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).