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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 245 - (view) (download)

1 : monnier 245 (*
2 :     * Computation of the dominator tree representation from the
3 :     * control flow graph. Can also compute the DJgraph.
4 :     * I'm using the old algorithm by Lengauer and Tarjan.
5 :     *
6 :     * Note: to deal with CFG with endless loops,
7 :     * by default we assume instructions are postdominated by STOP.
8 :     *
9 :     * The algorithm for dominance frontier and iterated dominance
10 :     * frontier is due to Sreedhar, Gao and Lee. The algorithm as cited
11 :     * uses the DJgraph. In order not to bother with constructing and
12 :     * maintaining the DJgraph, we'll just use a combination of the dominator tree
13 :     * and the original cfg.
14 :     *)
15 :    
16 :     functor DominatorTreeFn (GraphImpl : GRAPH_IMPLEMENTATION
17 :     ) : DOMINATOR_TREE =
18 :     struct
19 :    
20 :     structure GI = GraphImpl
21 :     structure G = Graph
22 :     structure Rev = ReversedGraphView
23 :     structure A = Array
24 :     structure NodeSet = BitSet
25 :    
26 :     exception Dominator
27 :    
28 :     datatype 'n dom_node =
29 :     DOM of { node : 'n, level : int, preorder : int, postorder : int }
30 :    
31 :     type dominator_methods =
32 :     { dominates : G.node_id * G.node_id -> bool,
33 :     immediately_dominates : G.node_id * G.node_id -> bool,
34 :     strictly_dominates : G.node_id * G.node_id -> bool,
35 :     postdominates : G.node_id * G.node_id -> bool,
36 :     immediately_postdominates : G.node_id * G.node_id -> bool,
37 :     strictly_postdominates : G.node_id * G.node_id -> bool,
38 :     control_equivalent : G.node_id * G.node_id -> bool,
39 :     idom : G.node_id -> G.node_id,
40 :     idoms : G.node_id -> G.node_id list,
41 :     doms : G.node_id -> G.node_id list,
42 :     ipdom : G.node_id -> G.node_id,
43 :     ipdoms : G.node_id -> G.node_id list,
44 :     pdoms : G.node_id -> G.node_id list,
45 :     dom_lca : Graph.node_id * Graph.node_id -> Graph.node_id,
46 :     pdom_lca : Graph.node_id * Graph.node_id -> Graph.node_id,
47 :     dom_level : Graph.node_id -> int,
48 :     pdom_level : Graph.node_id -> int,
49 :     control_equivalent_partitions : unit -> Graph.node_id list list
50 :     }
51 :    
52 :     type ('n,'e,'g) dom_info =
53 :     { cfg : ('n,'e,'g) G.graph, edge_label : string,
54 :     methods : (unit -> dominator_methods) ref,
55 :     max_levels : int ref
56 :     }
57 :     type ('n,'e,'g) dominator_tree =
58 :     ('n dom_node,unit,('n,'e,'g) dom_info) G.graph
59 :     type ('n,'e,'g) postdominator_tree =
60 :     ('n dom_node,unit,('n,'e,'g) dom_info) G.graph
61 :    
62 :     fun graph_info (G.GRAPH dom) : ('n,'e,'g) dom_info = #graph_info dom
63 :    
64 :     fun cfg dom = #cfg(graph_info dom)
65 :     fun max_levels dom = !(#max_levels(graph_info dom))
66 :     fun methods dom = (!(#methods(graph_info dom)))()
67 :    
68 :     (*
69 :     * This is the main Lengauer/Tarjan algorithm
70 :     *)
71 :     fun tarjan_lengauer (name,edge_label) (CFG as (G.GRAPH cfg)) =
72 :     let val N = #order cfg ()
73 :     val M = #capacity cfg ()
74 :     val r = case #entries cfg () of
75 :     [r] => r
76 :     | _ => raise Dominator
77 :     val in_edges = #in_edges cfg
78 :     val succ = #succ cfg
79 :     val dfnum = A.array (M, ~1)
80 :     val vertex = A.array (N, ~1)
81 :     val parent = A.array (M, ~1)
82 :     val bucket = A.array (M, []) : G.node_id list array
83 :     val semi = A.array (M, r)
84 :     val ancestor = A.array (M, ~1)
85 :     val idom = A.array (M, r)
86 :     val samedom = A.array (M, ~1)
87 :     val best = A.array (M, ~1)
88 :     val max_levels = ref 0
89 :     val dom_info = { cfg = CFG, edge_label = edge_label,
90 :     methods = ref(fn _ => raise G.Graph "dom"),
91 :     max_levels = max_levels }
92 :     val Dom as G.GRAPH domtree = GI.graph(name, dom_info, N)
93 :    
94 :     (* step 1
95 :     * Initialize semi dominators and parent map
96 :     *)
97 :     fun dfs(p,n,N) =
98 :     if A.sub(dfnum,n) = ~1 then
99 :     (A.update(dfnum,n,N);
100 :     A.update(vertex,N,n);
101 :     A.update(parent,n,p);
102 :     dfsSucc(n,succ n,N+1)
103 :     )
104 :     else N
105 :     and dfsSucc(p,[],N) = N
106 :     | dfsSucc(p,n::ns,N) = dfsSucc(p,ns,dfs(p,n,N))
107 :    
108 :     and dfsAll(n::ns,N) = dfsAll(ns,dfs(~1,n,N))
109 :     | dfsAll([],N) = ()
110 :     val nonRoots = List.foldr
111 :     (fn ((r',_),l) => if r <> r' then r'::l else l) []
112 :     (#nodes cfg ())
113 :     val _ = dfsAll(nonRoots,dfs(~1,r,0))
114 :    
115 :     (*
116 :     fun pr s = print (s ^ "\n")
117 :     fun dumpArray title a =
118 :     pr(title ^ ": " ^
119 :     String.concat(A.foldr
120 :     (fn (i,s) => Int.toString i::" "::s) [] a))
121 :    
122 :     val _ = pr("root = " ^ Int.toString r)
123 :     val _ = dumpArray "vertex" vertex
124 :     val _ = dumpArray "dfnum" dfnum
125 :     val _ = dumpArray "parent" parent
126 :     val _ = Msg.printMessages(fn _ => CFG.G.printGraph (!Msg.outStream) cfg)
127 :     *)
128 :    
129 :     fun link(p,n) = (A.update(ancestor,n,p); A.update(best,n,n))
130 :    
131 :     fun ancestorWithLowestSemi v =
132 :     let val a = A.sub(ancestor,v)
133 :     in if a <> ~1 andalso A.sub(ancestor,a) <> ~1 then
134 :     let val b = ancestorWithLowestSemi a
135 :     in A.update(ancestor,v,A.sub(ancestor,a));
136 :     if A.sub(dfnum,A.sub(semi,b)) <
137 :     A.sub(dfnum,A.sub(semi,A.sub(best,v))) then
138 :     A.update(best,v,b)
139 :     else ()
140 :     end
141 :     else ();
142 :     let val u = A.sub(best,v)
143 :     in if u = ~1 then v else u
144 :     end
145 :     end
146 :    
147 :     (* steps 2 and 3
148 :     * Compute vertex, bucket and semi maps
149 :     *)
150 :     fun compute 0 = ()
151 :     | compute i =
152 :     let val n = A.sub(vertex,i)
153 :     val p = A.sub(parent,n)
154 :     fun computeSemi ((v,n,_)::rest,s) =
155 :     if v = n then computeSemi(rest,s)
156 :     else
157 :     let val s' = if A.sub(dfnum,v) < A.sub(dfnum,n) then v
158 :     else A.sub(semi,ancestorWithLowestSemi(v))
159 :     val s = if A.sub(dfnum,s') <
160 :     A.sub(dfnum,s) then s'
161 :     else s
162 :     in computeSemi(rest,s)
163 :     end
164 :     | computeSemi ([], s) = s
165 :     in if p <> ~1 then
166 :     let val s = computeSemi(in_edges n, p)
167 :     in A.update(semi,n,s);
168 :     A.update(bucket,s,n::A.sub(bucket,s));
169 :     link(p,n);
170 :     app (fn v =>
171 :     let val y = ancestorWithLowestSemi(v)
172 :     in if A.sub(semi,y) = A.sub(semi,v) then
173 :     A.update(idom,v,p) else A.update(samedom,v,y)
174 :     end) (A.sub(bucket,p));
175 :     A.update(bucket,p,[])
176 :     end else ();
177 :     compute(i-1)
178 :     end
179 :     val _ = compute (N-1)
180 :    
181 :     (*
182 :     val _ = dumpArray "semi" idom
183 :     val _ = dumpArray "idom" idom
184 :     *)
185 :    
186 :     (* step 4 update dominators *)
187 :     fun updateIdoms i =
188 :     if i < N then
189 :     let val n = A.sub(vertex, i)
190 :     in if A.sub(samedom, n) <> ~1
191 :     then A.update(idom, n, A.sub(idom, A.sub(samedom, n)))
192 :     else ();
193 :     updateIdoms (i+1)
194 :     end
195 :     else ()
196 :     val _ = updateIdoms 1
197 :    
198 :     (*
199 :     val _ = dumpArray "idom" idom
200 :     *)
201 :    
202 :     (* Create the nodes of the dominator tree *)
203 :     fun addNode ~1 = ()
204 :     | addNode i = let val v = A.sub(vertex,i)
205 :     in #add_node domtree (v,
206 :     DOM { node = #node_info cfg v,
207 :     level = 0,
208 :     preorder = 0,
209 :     postorder = 0
210 :     });
211 :     addNode (i-1)
212 :     end
213 :    
214 :     val _ = addNode (N-1)
215 :    
216 :     (* Create the edges of the dominator tree *)
217 :     val _ = #forall_nodes domtree
218 :     (fn (v,_) =>
219 :     if v <> r then
220 :     let val w = A.sub(idom,v)
221 :     in #add_edge domtree (w,v,()) end
222 :     else ())
223 :    
224 :     (* Compute the level/preorder/postorder numbers *)
225 :     fun computeNumbering(level,preorder,postorder,n) =
226 :     let val DOM { node, ... } = #node_info domtree n
227 :     val (preorder',postorder',max_level) =
228 :     computeNumbering'(level+1,preorder+1,postorder,
229 :     #succ domtree n)
230 :     in #add_node domtree (n,
231 :     DOM{node=node,level=level,
232 :     preorder=preorder,postorder=postorder'});
233 :     (preorder',postorder'+1,max_level)
234 :     end
235 :    
236 :     and computeNumbering'(level,preorder,postorder,[]) =
237 :     (preorder,postorder,level)
238 :     | computeNumbering'(level,preorder,postorder,n::ns) =
239 :     let val (preorder',postorder',max1) =
240 :     computeNumbering(level,preorder,postorder,n)
241 :     val (preorder',postorder',max2) =
242 :     computeNumbering'(level,preorder',postorder',ns)
243 :     in (preorder',postorder',Int.max(max1,max2))
244 :     end
245 :    
246 :     val (_,_,max) = computeNumbering(0,0,0,r)
247 :     in
248 :     max_levels := max+1;
249 :     #set_entries domtree [r];
250 :     (* Msg.printMessages(fn _ => G.printGraph (!Msg.outStream) domtree); *)
251 :     Dom
252 :     end
253 :    
254 :     (* The algorithm specialized to making dominators and postdominators *)
255 :    
256 :     fun dominator_trees (cfg as (G.GRAPH g)) =
257 :     let val Dom as G.GRAPH D =
258 :     tarjan_lengauer ("Dom","dom") cfg
259 :     val PDom as G.GRAPH P =
260 :     tarjan_lengauer ("PDom","pdom") (Rev.rev_view cfg)
261 :    
262 :     fun immediately_dominates (i,j) =
263 :     case #in_edges D j of
264 :     (k,_,_)::_ => i = k
265 :     | _ => false
266 :    
267 :     fun immediately_postdominates (i,j) =
268 :     case #in_edges D j of
269 :     (k,_,_)::_ => i = k
270 :     | _ => false
271 :    
272 :     (* immediate dominator of n *)
273 :     fun idom n = case #in_edges D n of
274 :     (n,_,_)::_ => n
275 :     | _ => ~1
276 :    
277 :     fun idoms n = #succ D n
278 :    
279 :     fun subtree (succ,[],S) = S
280 :     | subtree (succ,n::ns,S) = subtree(succ,succ n,
281 :     subtree(succ,ns,n::S))
282 :    
283 :     fun dom_level i =
284 :     let val DOM{level,...} = #node_info D i in level end
285 :     fun pdom_level i =
286 :     let val DOM{level,...} = #node_info P i in level end
287 :    
288 :     (* Least common ancestors *)
289 :     fun dom_lca(a,b) =
290 :     let val l_a = dom_level a
291 :     val l_b = dom_level b
292 :     fun idom i = case #in_edges D i of (j,_,_)::_ => j
293 :     fun up_a(a,l_a) = if l_a > l_b then up_a(idom a,l_a-1) else a
294 :     fun up_b(b,l_b) = if l_b > l_a then up_b(idom b,l_b-1) else b
295 :     val a = up_a(a,l_a)
296 :     val b = up_b(b,l_b)
297 :     fun up_both(a,b) = if a = b then a else up_both(idom a,idom b)
298 :     in up_both(a,b)
299 :     end
300 :     fun pdom_lca(a,b) =
301 :     let val l_a = pdom_level a
302 :     val l_b = pdom_level b
303 :     fun ipdom i = case #in_edges P i of (j,_,_)::_ => j
304 :     fun up_a(a,l_a) = if l_a > l_b then up_a(ipdom a,l_a-1) else a
305 :     fun up_b(b,l_b) = if l_b > l_a then up_b(ipdom b,l_b-1) else b
306 :     val a = up_a(a,l_a)
307 :     val b = up_b(b,l_b)
308 :     fun up_both(a,b) = if a = b then a else up_both(ipdom a,ipdom b)
309 :     in up_both(a,b)
310 :     end
311 :    
312 :     fun doms n = subtree(#succ D, [n], [])
313 :    
314 :     (* immediate postdominator of n *)
315 :     fun ipdom n = case #in_edges P n of
316 :     (n,_,_)::_ => n
317 :     | _ => ~1
318 :     fun ipdoms n = #succ P n
319 :     fun pdoms n = subtree(#succ P, [n], [])
320 :    
321 :     (* is x and ancestor of y in D?
322 :     * This is true iff PREORDER(x) <= PREORDER(y) and
323 :     * POSTORDER(x) >= POSTORDER(y)
324 :     *)
325 :     fun dominates (x,y) =
326 :     let val DOM { preorder = a, postorder = b, ... } = #node_info D x
327 :     val DOM { preorder = c, postorder = d, ... } = #node_info D y
328 :     in a <= c andalso b >= d
329 :     end
330 :    
331 :     fun strictly_dominates (x,y) =
332 :     let val DOM { preorder = a, postorder = b, ... } = #node_info D x
333 :     val DOM { preorder = c, postorder = d, ... } = #node_info D y
334 :     in a < c andalso b > d
335 :     end
336 :    
337 :     fun postdominates (x,y) =
338 :     let val DOM { preorder = a, postorder = b, ... } = #node_info P x
339 :     val DOM { preorder = c, postorder = d, ... } = #node_info P y
340 :     in a <= c andalso b >= d
341 :     end
342 :    
343 :     fun strictly_postdominates (x,y) =
344 :     let val DOM { preorder = a, postorder = b, ... } = #node_info P x
345 :     val DOM { preorder = c, postorder = d, ... } = #node_info P y
346 :     in a < c andalso b > d
347 :     end
348 :    
349 :     fun control_equivalent (x,y) =
350 :     dominates(x,y) andalso postdominates(y,x) orelse
351 :     dominates(y,x) andalso postdominates(x,y)
352 :    
353 :     (* control equivalent partitions
354 :     * two nodes a and b are control equivalent iff
355 :     * a dominates b and b postdominates a (or vice versa)
356 :     * We use the following property of dominators to avoid wasteful work:
357 :     * If i dom j dom k and j not pdom i then
358 :     * k not pdom i
359 :     * This algorithm runs in O(n)
360 :     *)
361 :     fun control_equivalent_partitions() =
362 :     let fun walkDom([],S) = S
363 :     | walkDom(n::waiting,S) =
364 :     let val (waiting,S,S') =
365 :     findEquiv(n,#out_edges D n,waiting,S,[n])
366 :     in walkDom(waiting,S'::S)
367 :     end
368 :     and findEquiv(i,[],waiting,S,S') = (waiting,S,S')
369 :     | findEquiv(i,(_,j,_)::es,waiting,S,S') =
370 :     if postdominates(j,i) then
371 :     let val (waiting,S,S') = findEquiv(i,es,waiting,S,j::S')
372 :     in findEquiv(i,#out_edges D j,waiting,S,S')
373 :     end
374 :     else
375 :     findEquiv(i,es,j::waiting,S,S')
376 :    
377 :     val equivSets = walkDom(#entries D (),[])
378 :     in
379 :     equivSets
380 :     end
381 :    
382 :     (* Methods for dominators/postdominator manipulation *)
383 :     val methods = { dominates = dominates,
384 :     strictly_dominates = strictly_dominates,
385 :     postdominates = postdominates,
386 :     strictly_postdominates = strictly_postdominates,
387 :     control_equivalent = control_equivalent,
388 :     idom = idom,
389 :     idoms = idoms,
390 :     doms = doms,
391 :     ipdom = ipdom,
392 :     ipdoms = ipdoms,
393 :     pdoms = pdoms,
394 :     dom_level = dom_level,
395 :     pdom_level = pdom_level,
396 :     dom_lca = dom_lca,
397 :     pdom_lca = pdom_lca,
398 :     immediately_dominates = immediately_dominates,
399 :     immediately_postdominates = immediately_postdominates,
400 :     control_equivalent_partitions =
401 :     control_equivalent_partitions
402 :     }
403 :     fun get_methods _ = methods
404 :     in
405 :     #methods (#graph_info D) := get_methods;
406 :     #methods (#graph_info P) := get_methods;
407 :     (Dom, PDom)
408 :     end
409 :    
410 :     end
411 :    
412 :     (*
413 :     * $Log$
414 :     *)

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