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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 912 - (view) (download)

1 : george 912 (*
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. (Actually we don't)
14 :     *
15 :     * -- Allen
16 :     *)
17 :    
18 :     functor StaticSingleAssignmentForm
19 :     (Dom : DOMINATOR_TREE) : STATIC_SINGLE_ASSIGNMENT_FORM =
20 :     struct
21 :     structure Dom = Dom
22 :     structure G = Graph
23 :     structure A = Array
24 :    
25 :     type var = int
26 :     type phi = var * var * var list
27 :     type renamer = {defs : var list, uses: var list} ->
28 :     {defs : var list, uses: var list}
29 :     type copy = {dst : var list, src : var list} -> unit
30 :    
31 :     structure DJ = DJGraph(Dom)
32 :    
33 :     fun app f =
34 :     let fun g [] = ()
35 :     | g (x::xs) = (f x; g xs)
36 :     in g end
37 :    
38 :     (*
39 :     * Place join nodes at the iterated dominance frontier of def_sites(v)
40 :     * that is live.
41 :     *)
42 :     fun place_joins (Dom as G.GRAPH dom)
43 :     { max_var=V, defs, is_live } =
44 :     let val N = #capacity dom ()
45 :     val G.GRAPH cfg = Dom.cfg Dom
46 :     val def_sites = A.array(V,[]) (* indexed by var *)
47 :     val phis = A.array(N,[]) (* indexed by block id *)
48 :    
49 :     (* compute the def sites of all variables *)
50 :     val _ = #forall_nodes cfg
51 :     (fn (n,block) =>
52 :     app (fn v => A.update(def_sites,v,n::A.sub(def_sites,v)))
53 :     (defs(n,block))
54 :     )
55 :     (* compute phi placements for a variable *)
56 :     val IDFs = DJ.IDFs Dom
57 :     fun place_phi(v,[]) = ()
58 :     | place_phi(v,def_sites) =
59 :     let fun place_all [] = ()
60 :     | place_all(Y::Ys) =
61 :     (if is_live(v,Y) then
62 :     A.update(phis,Y,(v,v,[])::A.sub(phis,Y))
63 :     else ();
64 :     place_all Ys)
65 :     in place_all (IDFs def_sites)
66 :     end
67 :    
68 :     val _ = A.appi place_phi (def_sites,0,NONE)
69 :     in phis
70 :     end
71 :    
72 :     (*
73 :     * Rename variables and compute the ssa form
74 :     *)
75 :     fun compute_ssa (Dom as G.GRAPH dom)
76 :     { max_var=V, defs, is_live, rename_stmt, insert_phi, rename_var } =
77 :     let val N = #capacity dom ()
78 :     val G.GRAPH cfg = Dom.cfg Dom
79 :     val [ENTRY] = #entries dom ()
80 :     val phis = place_joins Dom {max_var=V,defs=defs,is_live=is_live}
81 :     val stacks = A.array(V,[]) (* indexed by var *)
82 :     val in_edges = A.array(N,[])
83 :    
84 :     (* Lookup the current renaming of v *)
85 :     fun lookup v =
86 :     case A.sub(stacks,v) of
87 :     v'::_ => v'
88 :     | _ => v
89 :    
90 :     (* Retract one entry of v *)
91 :     fun pop v = case A.sub(stacks,v) of _::l => A.update(stacks,v,l)
92 :    
93 :     fun search X =
94 :     let val X' = #node_info cfg X
95 :     val old_defs = ref []
96 :    
97 :     fun rename_use v =
98 :     if v < 0 then v
99 :     else
100 :     let val vs = A.sub(stacks,v)
101 :     val v' = case vs of v'::_ => v' | _ => v
102 :     in v'
103 :     end
104 :    
105 :     fun rename_uses [] = []
106 :     | rename_uses (v::vs) = rename_use v::rename_uses vs
107 :    
108 :     (* rename a definition of v *)
109 :     fun rename_def v =
110 :     let val v' = rename_var v
111 :     val vs = A.sub(stacks,v)
112 :     in A.update(stacks,v,v'::vs);
113 :     old_defs := v :: !old_defs;
114 :     v'
115 :     end
116 :    
117 :     fun rename_defs [] = []
118 :     | rename_defs (v::vs) = rename_def v::rename_defs vs
119 :    
120 :     fun copy_def(v,v') =
121 :     (A.update(stacks,v,v'::A.sub(stacks,v));
122 :     old_defs := v :: !old_defs)
123 :    
124 :     (* parallel copy *)
125 :     fun copy {dst,src} =
126 :     ListPair.app copy_def (dst,rename_uses src)
127 :    
128 :     (* rename statement of the form defs := uses in block X
129 :     * We must rename the uses first!!!
130 :     *)
131 :     fun rename {defs,uses} =
132 :     let val uses' = rename_uses uses
133 :     val defs' = rename_defs defs
134 :     in {defs=defs',uses=uses'}
135 :     end
136 :    
137 :     (* rename the definition of phi functions *)
138 :     fun rename_phi_def X =
139 :     let val X_phis = A.sub(phis,X)
140 :     fun rn [] = []
141 :     | rn((v',v,uses)::rest) = (v',rename_def v,uses)::rn rest
142 :     val X_phis = rn X_phis
143 :     in A.update(phis,X,X_phis)
144 :     end
145 :    
146 :     (* rename the uses of phi functions *)
147 :     fun rename_phi_use X =
148 :     let val out_edges = #out_edges cfg X
149 :     fun rename_phi_of_Y (e as (X,Y,_)) =
150 :     let val Y_phis = A.sub(phis,Y)
151 :     fun insert_uses [] = []
152 :     | insert_uses((v',v,uses)::rest) =
153 :     (v',v,rename_use v'::uses)::insert_uses rest
154 :     in A.update(in_edges,Y,e::A.sub(in_edges,Y));
155 :     A.update(phis,Y,insert_uses Y_phis)
156 :     end
157 :     in app rename_phi_of_Y out_edges
158 :     end
159 :    
160 :     in
161 :     rename_phi_def X;
162 :     rename_stmt {rename=rename,copy=copy} (X,X');
163 :     rename_phi_use X;
164 :     app search (#succ dom X);
165 :     app pop (!old_defs)
166 :     end
167 :    
168 :     (* place phis *)
169 :     fun place_phi (B as (b,_)) =
170 :     insert_phi{block=B,in_edges=A.sub(in_edges,b),phis=A.sub(phis,b)}
171 :    
172 :     in
173 :     search ENTRY;
174 :     #forall_nodes cfg place_phi
175 :     end
176 :    
177 :     end
178 :    

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