Module reloop 

Recovering Rust’s own control flow from the graph.

The graph is a correct lowering of any goto, and as a flat loop { match state { … } } it is also an opaque one: every edge is a store and a jump back to a dispatch, and the loops the C program had are gone — which is what made SQLite’s sqlite3VdbeExec run five times the instructions GCC’s does. This module puts them back. It reads the finished graph and rebuilds a structured program out of three shapes, which codegen emits as ordinary Rust:

• Simple — one basic block. Its terminator becomes an if or a match, and the blocks that only it can reach are emitted inside the arms, so a two-way branch is if c { … } else { … } and a switch is a match with the case bodies in it.
• Loop — a set of blocks with an entry that something inside jumps back to. It becomes 'l: loop { … }: a back edge is continue 'l and an exit is break 'l. The label is the C label the head carries, where there is one.
• Sequence — the run of shapes at one level, in an order in which every remaining jump goes forward. A forward jump is break of a labelled block that ends where its target begins, which is the same trick regions plays on the statement tree, and the reason nothing here needs a variable to say where control went.

The algorithm is Emscripten’s relooper — Alon Zakai, Emscripten: An LLVM-to-JavaScript Compiler, OOPSLA 2011, §3.2 — as it is also implemented in c2rust-transpile’s cfg::relooper. It was written from the description of the algorithm rather than from either implementation.

The recursion

process(entries, blocks) builds the shapes for blocks, which control can only get into at one of entries:

1. One entry that nothing in blocks jumps back to → a Simple for it, then process of what its terminator reaches.
2. Several entries → try a Multiple: give each entry the blocks that only it can reach, lay those groups out one after another, and process the rest after them. An entry another entry can reach owns nothing and waits for the rest.
3. Otherwise → a Loop. Its body is the entries plus every block that can get back to one of them; what is left follows it. The back edges are then taken out of the graph, which is what lets the body be relooped as if its entries were entered from outside only.

Irreducible regions

A goto into the middle of a loop, Duff’s device and two loops that jump into each other’s bodies all produce a cycle with two heads, which no arrangement of Rust’s blocks and loops can express. Step 3 is where they land: the Loop keeps both heads, and once its back edges are cut, step 2 splits the body into one group per head. That dispatch — and only that one — reads a state variable, which every jump to a head writes first. It is one u32 per irreducible region rather than one per function, and the blocks outside the region never touch it.

What the shapes preserve

Everything, because the graph already holds it. A cleanup call and a variable length array’s release are statements at the end of the block the edge leaves from — cfg puts them there — so no shape has to know about them. switch fallthrough is an edge from one case block to the next, and comes out as the case body falling out of its match arm into the code after the match. A return is a block terminator wherever it stands.

Giving up

Two things keep the state machine alive. A switch whose cases fall through one into the next gives each of them a labelled block, and past two hundred of those rustc’s own parser runs out of stack, where the machine’s flat match does not. And the shapes are checked before they are handed over: if every block is not in the tree exactly once, or if some jump has nothing to break to, plan answers None and the state machine runs instead of something subtly wrong.

GNU’s computed goto is not one of them: cfg has already made it a switch over the labels whose address is taken, so an interpreter’s dispatch loop is a Loop around a Simple whose match holds the handlers — the shape the same interpreter written with a switch has.

Structs

Arm

One entry of a branch, and the shapes that run it.

Exit

Where control arrives when it runs off the end of a shape, or when it breaks or continues a labelled one.

Plan

A whole function body, recovered.

Enums

Shape

A piece of recovered control flow.

Functions

plan

Recovers the structured form of a graph, or answers None.

Type Aliases

Seq

A run of shapes, one after another.