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/branches/SMLNJ/src/MLRISC/ir-moved/ssa.sml
ViewVC logotype

Annotation of /sml/branches/SMLNJ/src/MLRISC/ir-moved/ssa.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 245 - (view) (download)

1 : monnier 245 (*
2 :     * SSA placement module. This is the algorithm from Cytron et al.'s
3 :     * TOPLAS paper. This module is kept generic so that we can also use it
4 :     * to compute sparse evaluation graphs, factored redef/use chains (of Wolfe)
5 :     * etc.
6 :     *
7 :     * This implementation uses Sreedhar et al.'s DJ-graph to compute
8 :     * the iterated dominance frontier, which should be slightly faster
9 :     * than the default implementation.
10 :     *
11 :     * For the stack of renamed variables, we use the scheme proposed
12 :     * by Briggs, Cooper, Harvey and Simpson in Software Practice & Experience
13 :     * 1988.
14 :     *)
15 :    
16 :     functor StaticSingleAssignmentFormFn
17 :     (Dom : DOMINATOR_TREE) : STATIC_SINGLE_ASSIGNMENT_FORM =
18 :     struct
19 :     structure Dom = Dom
20 :     structure G = Graph
21 :     structure A = Array
22 :    
23 :     type var = int
24 :     type phi = var * var * var list
25 :     type renamer = {defs : var list, uses: var list} ->
26 :     {defs : var list, uses: var list}
27 :     type copy = {dst : var list, src : var list} -> unit
28 :    
29 :     structure DJ = DJGraphFn(Dom)
30 :    
31 :     (*
32 :     * Place join nodes at the iterated dominance frontier of def_sites(v)
33 :     * that is live.
34 :     *)
35 :     fun place_joins (Dom as G.GRAPH dom)
36 :     { max_var=V, defs, is_live } =
37 :     let val N = #capacity dom ()
38 :     val G.GRAPH cfg = Dom.cfg Dom
39 :     val def_sites = A.array(V,[]) (* indexed by var *)
40 :     val phis = A.array(N,[]) (* indexed by block id *)
41 :    
42 :     (* compute the def sites of all variables *)
43 :     val _ = #forall_nodes cfg
44 :     (fn (n,block) =>
45 :     app (fn v => A.update(def_sites,v,n::A.sub(def_sites,v)))
46 :     (defs(n,block))
47 :     )
48 :     (* compute phi placements for a variable *)
49 :     val {IDFs,...} = DJ.dj_graph Dom
50 :     fun place_phi(v,[]) = ()
51 :     | place_phi(v,def_sites) =
52 :     let fun place_all [] = ()
53 :     | place_all(Y::Ys) =
54 :     (if is_live(v,Y) then
55 :     A.update(phis,Y,(v,v,[])::A.sub(phis,Y))
56 :     else ();
57 :     place_all Ys)
58 :     in place_all (IDFs def_sites)
59 :     end
60 :    
61 :     val _ = A.appi place_phi (def_sites,0,NONE)
62 :     in phis
63 :     end
64 :    
65 :     (*
66 :     * Rename variables and compute the ssa form
67 :     *)
68 :     fun compute_ssa (Dom as G.GRAPH dom)
69 :     { max_var=V, defs, is_live, rename_stmt, insert_phi, rename_var } =
70 :     let val N = #capacity dom ()
71 :     val G.GRAPH cfg = Dom.cfg Dom
72 :     val [ENTRY] = #entries dom ()
73 :     val phis = place_joins Dom {max_var=V,defs=defs,is_live=is_live}
74 :     val stacks = A.array(V,[]) (* indexed by var *)
75 :     val in_edges = A.array(N,[])
76 :    
77 :     (* Lookup the current renaming of v *)
78 :     fun lookup v =
79 :     case A.sub(stacks,v) of
80 :     v'::_ => v'
81 :     | _ => v
82 :    
83 :     (* Retract one entry of v *)
84 :     fun pop v = case A.sub(stacks,v) of _::l => A.update(stacks,v,l)
85 :    
86 :     fun search X =
87 :     let val X' = #node_info cfg X
88 :     val old_defs = ref []
89 :    
90 :     fun rename_use v =
91 :     if v < 0 then v
92 :     else
93 :     let val vs = A.sub(stacks,v)
94 :     val v' = case vs of v'::_ => v' | _ => v
95 :     in v'
96 :     end
97 :    
98 :     (* rename a definition of v *)
99 :     fun rename_def v =
100 :     let val v' = rename_var v
101 :     val vs = A.sub(stacks,v)
102 :     in A.update(stacks,v,v'::vs);
103 :     old_defs := v :: !old_defs;
104 :     v'
105 :     end
106 :    
107 :     fun copy_def(v,v') =
108 :     (A.update(stacks,v,v'::A.sub(stacks,v));
109 :     old_defs := v :: !old_defs)
110 :    
111 :     (* parallel copy *)
112 :     fun copy {dst,src} =
113 :     ListPair.app copy_def (dst,map rename_use src)
114 :    
115 :     (* rename statement of the form defs := uses in block X
116 :     * We must rename the uses first!!!
117 :     *)
118 :     fun rename {defs,uses} =
119 :     let val uses' = map rename_use uses
120 :     val defs' = map rename_def defs
121 :     in {defs=defs',uses=uses'}
122 :     end
123 :    
124 :     (* rename the definition of phi functions *)
125 :     fun rename_phi_def X =
126 :     let val X_phis = A.sub(phis,X)
127 :     val X_phis = map(fn (v',v,uses) =>
128 :     (v',rename_def v,uses)) X_phis
129 :     in A.update(phis,X,X_phis)
130 :     end
131 :    
132 :     (* rename the uses of phi functions *)
133 :     fun rename_phi_use X =
134 :     let val out_edges = #out_edges cfg X
135 :     fun rename_phi_of_Y (e as (X,Y,_)) =
136 :     let val Y_phis = A.sub(phis,Y)
137 :     fun insert_use (v',v,uses) =
138 :     (v',v,rename_use v'::uses)
139 :     in A.update(in_edges,Y,e::A.sub(in_edges,Y));
140 :     A.update(phis,Y,map insert_use Y_phis)
141 :     end
142 :     in app rename_phi_of_Y out_edges
143 :     end
144 :    
145 :     in
146 :     rename_phi_def X;
147 :     rename_stmt {rename=rename,copy=copy} (X,X');
148 :     rename_phi_use X;
149 :     app search (#succ dom X);
150 :     app pop (!old_defs)
151 :     end
152 :    
153 :     (* place phis *)
154 :     fun place_phi (B as (b,_)) =
155 :     insert_phi{block=B,in_edges=A.sub(in_edges,b),phis=A.sub(phis,b)}
156 :    
157 :     in
158 :     search ENTRY;
159 :     #forall_nodes cfg place_phi
160 :     end
161 :    
162 :     end
163 :    
164 :     (*
165 :     * $Log$
166 :     *)

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