Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/src/MLRISC/ir-archive/cdg.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/ir-archive/cdg.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 912 - (view) (download)

1 : george 912 (*
2 :     * This is a generic module for computing the control dependence graph
3 :     * from a graph with an entry and an exit.
4 :     * The graph is treated as a control flow graph.
5 :     * The edge predicate is used to determine whether an edge should be
6 :     * treated as a branch edge.
7 :     *
8 :     * -- Allen
9 :     *)
10 :    
11 :     functor ControlDependenceGraph
12 :     (structure Dom : DOMINATOR_TREE
13 :     structure GraphImpl : GRAPH_IMPLEMENTATION
14 :     ) : CONTROL_DEPENDENCE_GRAPH =
15 :    
16 :     struct
17 :    
18 :     structure Dom = Dom
19 :     structure G = Graph
20 :     structure GI = GraphImpl
21 :    
22 :     type ('n,'e,'g) cdg = ('n,'e,'g) Graph.graph
23 :    
24 :     fun control_dependence_graph' f_node f_edge f_graph is_conditional
25 :     (PDom as G.GRAPH pdom) =
26 :     let val G.GRAPH cfg = Dom.cfg PDom
27 :     val N = #capacity cfg ()
28 :     val cdg_info = f_graph (#graph_info cfg)
29 :     val CDG as G.GRAPH cdg = GI.graph("CDG", cdg_info, N)
30 :     val ipdom = Dom.idom PDom
31 :     val add_edge = fn e => #add_edge cdg (f_edge e)
32 :     val out_edges = #out_edges cfg
33 :    
34 :     (* create the control dependence nodes *)
35 :     val _ = #forall_nodes cfg (fn n => #add_node cdg (f_node n))
36 :    
37 :     (* create the control dependence edges *)
38 :     val _ = #forall_nodes cfg
39 :     (fn node as (X,bb) =>
40 :     let val ipdom_X = ipdom X
41 :     fun loop (X,Z,L) =
42 :     if ipdom_X = ~1 orelse ipdom_X <> Z then
43 :     (* Z is immediately control dependent on X *)
44 :     (add_edge (X,Z,L);
45 :     case ipdom Z of
46 :     ~1 => ()
47 :     | Z => loop (X,Z,L))
48 :     else ()
49 :     in
50 :     app (fn (X,Z,L) =>
51 :     (* Z is a successor of X on label L *)
52 :     if is_conditional L then loop(X,Z,L)
53 :     else ()
54 :     ) (out_edges X)
55 :     end)
56 :     in
57 :     CDG
58 :     end
59 :    
60 :     fun control_dependence_graph is_conditional =
61 :     control_dependence_graph'
62 :     (fn n => n)
63 :     (fn e => e)
64 :     (fn g => g) is_conditional
65 :    
66 :     end

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0