Module `Fang_flow.Graph`

Constructing, manipulating, and querying flow graphs.

type t = graph

val empty : label -> t: empty l is an empty graph for the frame with the label l.

val pp : box Fmt.t -> t Fmt.t

type cursor: A point at which graph fragments may be inserted into a graph.

val entry : t -> cursor: entry g is a cursor pointing to first non-entry node of g.

val exit : t -> cursor: exit g is a cursor pointing to the last non-exit node of g.

val blur : cursor -> t: blur c is the graph to which c is pointing.

Fragments

type fragment = cursor -> cursor

A collection of one or more nodes forming part of a graph.

Given a cursor c into a graph and a fragment f, f c is a cursor into a new graph which includes all the nodes of the original graph and also the nodes of f.

The new nodes are inserted immediately after the node to which the cursor was originally pointing. The position of the cursor doesn't change.

Larger fragments are made by combining smaller ones.

Example

Consider the fragments f1, f2, f3, and a cursor c. We'd like to insert all three fragments into the graph immediately following the node to which c is pointing.

We first insert f3

let c' = f3 c

then f2

let c'' = f2 c'

and finally f1

let c''' = f1 c''

The "order" of the new graph is c -> f1 -> f2 -> f3.

We could have written this as

f1 (f2 (f3 c))

Or, using the @@ operator, as

f1 @@ f2 @@ f3 c

Here, @@ looks like "append" (if you squint).

Thus, the combination of all three fragments into a single fragment f is

let f c = f1 @@ f2 @@ f3 c

val asm : asm -> fragment: asm s is a fragment consisting of a single node which is the (non-branching) assembly instruction s.

val label : label -> (label -> asm) -> fragment

label l m is a fragment consisting of a single node which is the definition of the label l. m l is an assembly instruction for branching to l, which is necessary for forming blocks in the graph.

Important: the behaviour is unspecified when a fragment or graph defines the same label multiple times.

val branch : (label -> asm) -> label -> fragment: branch m l is a fragment consisting of a single node which represents an unconditional branch to the label l. m l is an assembly instruction for branching to l.

val cbranch : (label -> asm) -> label -> (label -> asm) -> label -> fragment

cbranch m pos m_inv neg is a fragment consisting of a single node which represents a branch of execution conditional on some internal state (typically, the result of comparing two values).

m pos is an assembly instruction which conditionally branches to pos based on the value of the state.

If the condition does not hold then execution continues at neg.

m_inv neg is an assembly instruction which checks the "inverted" condition of m pos and which conditionally branches to neg. This is required information for moving the location of the conditional branch in the flow graph.

Finalizing the graph

val trace : t -> t

trace g is the graph g with only the blocks in g which are reachable.

When building graphs with cursors and fragments, every intermediate graph consists of well-formed blocks. As a consequence, sometimes the materialized blocks are extraneous.

Tracing the graph removes any unnecessary blocks.

Important: prior to tracing the graph, all branches must refer to defined labels. If they don't, the behaviour is unspecified.

val finalize : branch:(label -> asm) -> t -> node iter

finalize ~branch g iterates over the nodes of g after "clean-ups" have been performed on the blocks comprising g. These include eliminating unused labels and unnecessary jumps, and "taming conditional branches".

branch l is an assembly instruction for jumping to label l and is necessary for finalizing the graph.

Important: prior to finalizing the graph, all branches must refer to defined labels. If they don't, the behaviour is unspecified.

Querying the graph

val blocks : t -> block iter
val nodes : t -> node iter
val find_block_with_label : label -> t -> block: Important: the behaviour is unspecified when the label is not defined in the graph.

Transforming the graph

val filter_map : (asm -> asm option) -> t -> t
val flat_map : (asm -> asm list) -> t -> t