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 498 - (view) (download)

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

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