Module ullbc_to_llbc

ULLBC to LLBC

We reconstruct the control-flow in the Unstructured LLBC.

The reconstruction algorithm is not written to be efficient (its complexity is probably very bad), but it was not written to be: this is still an early stage and we want the algorithm to generate the best reconstruction as possible. We still need to test the algorithm on more interesting examples, and will consider making it more efficient once it is a bit mature and well tested. Also note that we more importantly focus on making the algorithm sound: the reconstructed program must always be equivalent to the original MIR program, and the fact that the reconstruction preserves this property must be obvious.

Finally, we conjecture the execution time shouldn’t be too much a problem: we don’t expect the translation mechanism to be applied on super huge functions (which will be difficult to formally analyze), and the MIR graphs are actually not that big because statements are grouped into code blocks (a block is made of a list of statements, followed by a terminator - branchings and jumps can only be performed by terminators -, meaning that MIR graphs don’t have that many nodes and edges).

Structs

BlockInfo 🔒

Small utility

BlockWithRank 🔒

BlocksInfo 🔒

Information used to compute the switch exits. We compute this information for every block in the graph. Note that we make sure to use immutable sets because we rely a lot on cloning.

CfgInfo 🔒

This structure contains various information about a function’s CFG.

ExitInfo 🔒

The exits of a graph

FilteredLoopParents 🔒

LoopExitCandidateInfo 🔒

Transform

Enums

GotoKind 🔒

Functions

block_is_error 🔒

The terminator of the block is a panic, etc.

block_is_switch 🔒

build_cfg_info 🔒

Build the CFGs (the “regular” CFG and the CFG without backward edges) and compute some information like the loop entries and the switch blocks.

build_cfg_partial_info_edges 🔒

can_reach_outer_exit 🔒

Auxiliary helper

compute_loop_exit_candidates 🔒

Compute the loop exit candidates.

compute_loop_exits 🔒

See compute_loop_switch_exits for explanations about what “exits” are.

compute_loop_switch_exits 🔒

Compute the exits for the loops and the switches (switch on integer and if … then … else …). We need to do this because control-flow in MIR is destructured: we have gotos everywhere.

compute_switch_exits 🔒

See compute_loop_switch_exits for explanations about what “exits” are.

compute_switch_exits_explore 🔒

Compute BlocksInfo for every block in the graph. This information is then used to compute the switch exits.

filter_loop_parents 🔒

get_goto_kind 🔒

is_terminal 🔒

Return true if whatever the path we take, evaluating the statement necessarily leads to:

is_terminal_explore 🔒

is_terminal_explore_block 🔒

list_reachable 🔒

List the nodes reachable from a starting point. We list the nodes and the depth (in the AST) at which they were found.

loop_entry_is_reachable_from_inner 🔒

Check if a loop entry is reachable from a node, in a graph where we remove the backward edges going directly to the loop entry.

make_ord_block_id 🔒

Create an OrdBlockId from a block id and a rank given by a map giving a sort (topological in our use cases) over the graph.

opt_block_unwrap_or_nop 🔒

register_children_as_loop_exit_candidates 🔒

Register a node and its children as exit candidates for a list of parent loops.

translate_block 🔒

Remark: some values are boxed (here, the returned statement) so that they are allocated on the heap. This reduces stack usage (we had problems with stack overflows in the past). A more efficient solution would be to use loops to make this code constant space, but that would require a serious rewriting.

translate_body 🔒

translate_body_aux 🔒

translate_child_block 🔒

parent_span: we need some span data for the new statement. We use the one for the parent terminator.

translate_statement 🔒

translate_terminator 🔒

Type Aliases

Cfg 🔒

Control-Flow Graph

FlowBlockId 🔒

For the rank we use:

OrdBlockId 🔒