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 /MLRISC/trunk/ir-archive/dominator.sml
ViewVC logotype

Annotation of /MLRISC/trunk/ir-archive/dominator.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1334 - (view) (download)
Original Path: sml/trunk/src/MLRISC/ir-archive/dominator.sml

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

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