Hacker News Reader

Comment by pcwalton | Hacker News Reader

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

View on HN

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.

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.

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.

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

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.

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.

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.

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.

At least reserve the word, in case you change your mind in the future? I guess it's too late now...

Burn the boats and never look back, I guess.

Since when does rust care about breaking changes to the language.

Seven weeks ago today.

For version 1? Can we break on 2.0?

It's a bit more subtle than that, see https://github.com/rust-lang/rfcs/blob/master/text/1122-lang...

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

Reply on news.ycombinator.com