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-moved/cdg.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 412 - (view) (download)

1 : monnier 411 (*
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 : monnier 245 functor ControlDependenceGraphFn
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 :     (Dom as G.GRAPH dom, PDom as G.GRAPH pdom) =
26 :     let val G.GRAPH cfg = Dom.cfg Dom
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 methods = Dom.methods Dom
31 :     val ipdom = #ipdom methods
32 :     val add_edge = fn e => #add_edge cdg (f_edge e)
33 :     val out_edges = #out_edges cfg
34 :    
35 :     (* create the control dependence nodes *)
36 :     val _ = #forall_nodes cfg (fn n => #add_node cdg (f_node n))
37 :    
38 :     (* create the control dependence edges *)
39 :     val _ = #forall_nodes cfg
40 :     (fn node as (X,bb) =>
41 :     let val ipdom_X = ipdom X
42 :     fun loop (X,Z,L) =
43 :     if ipdom_X = ~1 orelse ipdom_X <> Z then
44 :     (* Z is immediately control dependent on X *)
45 :     (add_edge (X,Z,L);
46 :     case ipdom Z of
47 :     ~1 => ()
48 :     | Z => loop (X,Z,L))
49 :     else ()
50 :     in
51 :     app (fn (X,Z,L) =>
52 :     (* Z is a successor of X on label L *)
53 :     if is_conditional L then loop(X,Z,L)
54 :     else ()
55 :     ) (out_edges X)
56 :     end)
57 :     in
58 :     CDG
59 :     end
60 :    
61 :     fun control_dependence_graph is_conditional =
62 :     control_dependence_graph'
63 :     (fn n => n)
64 :     (fn e => e)
65 :     (fn g => g) is_conditional
66 :    
67 :     end

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