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 nodey
if control flow can reachy
directly fromx
.
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.