#
# This is a generic module for computing the control dependence graph
# from a graph with an entry and an exit.
# The graph is treated as a control flow graph.
# The edge predicate is used to determine whether an edge should be
# treated as a branch edge.
#
# -- Allen Leung
### "Mostly, when you see programmers, they aren't doing anything.
### One of the attractive things about programmers is that you
### cannot tell whether or not they are working simply by looking
### at them.
###
### Very often they're sitting there seemingly drinking coffee and
### gossiping, or just staring into space. What the programmer is
### trying to do is get a handle on all the individual and unrelated
### ideas that are scampering around in his head."
###
### -- Charles M Strauss
generic package ControlDependenceGraph
(package dom: Dominator_Tree
package meg: Make_Empty_Graph
) : CONTROL_DEPENDENCE_GRAPH
{
# Export to client packages:
#
package dom = Dom
package g = graph
package meg = meg
type cdg (N, E, G) = graph::graph (N, E, G)
fun control_dependence_graph' f_node f_edge f_graph is_conditional
(PDom as g::GRAPH pdom) =
let my g::GRAPH mcg = Dom::mcg PDom
N = mcg.capacity ()
cdg_info = f_graph mcg.graph_info
my CDG as g::GRAPH cdg = gi::graph("CDG", cdg_info, N)
ipdom = Dom::idom PDom
add_edge = \\ e => cdg.add_edge (f_edge e)
out_edges = mcg.out_edges
# Create the control dependence nodes
mcg.forall_nodes (\\ n => cdg.add_node (f_node n))
# Create the control dependence edges
mcg.forall_nodes
(\\ node as (X, bb) =>
let ipdom_X = ipdom X
fun loop (X, Z, L) =
if ipdom_X == -1 or ipdom_X != Z then
# Z is immediately control dependent on X
(add_edge (X, Z, L);
case ipdom Z of
-1 => ()
| Z => loop (X, Z, L))
else ()
in
apply (\\ (X, Z, L) =>
# Z is a successor of X on label L
if is_conditional L then loop (X, Z, L)
else ()
) (out_edges X)
end)
in
CDG
end
fun control_dependence_graph is_conditional =
control_dependence_graph'
(\\ n => n)
(\\ e => e)
(\\ g => g) is_conditional
}