Module Fang_flow

Flow graphs.

This is an implementation of the paper [1] by Ramsey and Dias.

References

[1] N. Ramsey and J. Dias, “An applicative control-flow graph based on Huet's zipper,” Electronic Notes in Theoretical Computer Science, vol. 148, no. 2, pp. 105–126, 2006.

module Node : sig ... end

Nodes in flow graphs.

type node = Node.t
type block

A "basic-block".

A block is a "straight-line" sequence of connected nodes in the flow graph. Control flow begins at the first node and ends at the last node, with no branches.

Since each flow graph corresponds to a single frame (i.e., flow analysis is not interprocedural), nodes in a block can include calls to subroutines.

Flow graphs are automatically organized into blocks when they're constructed via cursors and fragments.

Blocks always begin with a label definition and end with either a branch to a different label or the end of the frame.

module Block : sig ... end
type graph

A flow graph for a particular frame.

The nodes in a flow graph correspond to assembly instructions and labels. A directed edge exists from node x to node y if control flow can reach y directly from x.

module Graph : sig ... end

Constructing, manipulating, and querying flow graphs.

Generic graph analysis

These are tools for performing generic incremental backwards analysis on flow-graphs based on the definition of a generic "fact" which is of interest for each node and rules for computing it.

Liveness is a specialization of these tools specifically for the case of computing which registers are "live" at every node.

Analysis is generic because it lead to a deeper understanding of the applicable concepts for the author and because it was fun.

module type FACT = sig ... end
module type RULE = sig ... end

Describes how to compute facts for each kind of node in a graph incrementally.

module type ANALYSIS = sig ... end

Generic backward analysis on flow graphs.

module Analysis : functor (F : FACT) -> functor (R : RULE with type fact = F.t) -> ANALYSIS with type fact = F.t

Analyze flow graphs for generic combinations of facts and rules.

Liveness analysis

module Liveness : functor (R : sig ... end) -> ANALYSIS with type fact = Box.Set.t

Compute liveness information for all registers in a flow-graph.