Home My Page Projects Code Snippets Project Openings SML/NJ
 Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

# SCM Repository

[smlnj] Diff of /sml/branches/SMLNJ/src/MLRISC/ir-moved/dominator.sml
 [smlnj] / sml / branches / SMLNJ / src / MLRISC / ir-moved / dominator.sml

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

revision 428, Wed Sep 8 09:47:00 1999 UTC revision 429, Wed Sep 8 09:47:00 1999 UTC
# Line 1  Line 1
1  (*  (*
2   * Computation of the dominator tree representation from the   * Computation of the dominator tree representation from the
3   * control flow graph.   Can also compute the DJgraph.   * control flow graph.  I'm using the old algorithm by Lengauer and Tarjan.
* I'm using the old algorithm by Lengauer and Tarjan.
4   *   *
5   * Note: to deal with CFG with endless loops,   * Note: to deal with CFG with endless loops,
6   * by default we assume instructions are postdominated by STOP.   * by default we assume instructions are postdominated by STOP.
7   *   *
* The algorithm for dominance frontier and iterated dominance
* frontier is due to Sreedhar, Gao and Lee.   The algorithm as cited
* uses the DJgraph.  In order not to bother with constructing and
* maintaining the DJgraph, we'll just use a combination of the dominator tree
* and the original cfg.
*
8   * -- Allen   * -- Allen
9   *)   *)
10
# Line 27  Line 20
20
21     exception Dominator     exception Dominator
22
23     datatype 'n dom_node =     type node = G.node_id
DOM of { node : 'n, level : int, preorder : int, postorder : int }

type dominator_methods =
{ dominates              : G.node_id * G.node_id -> bool,
immediately_dominates  : G.node_id * G.node_id -> bool,
strictly_dominates     : G.node_id * G.node_id -> bool,
postdominates          : G.node_id * G.node_id -> bool,
immediately_postdominates : G.node_id * G.node_id -> bool,
strictly_postdominates : G.node_id * G.node_id -> bool,
control_equivalent     : G.node_id * G.node_id -> bool,
idom         : G.node_id -> G.node_id,
idoms        : G.node_id -> G.node_id list,
doms         : G.node_id -> G.node_id list,
ipdom        : G.node_id -> G.node_id,
ipdoms       : G.node_id -> G.node_id list,
pdoms        : G.node_id -> G.node_id list,
dom_lca      : Graph.node_id * Graph.node_id -> Graph.node_id,
pdom_lca     : Graph.node_id * Graph.node_id -> Graph.node_id,
dom_level    : Graph.node_id -> int,
pdom_level   : Graph.node_id -> int,
control_equivalent_partitions : unit -> Graph.node_id list list
}
24
25     type ('n,'e,'g) dom_info =     datatype ('n,'e,'g) dom_info =
26         { cfg : ('n,'e,'g) G.graph, edge_label : string,         INFO of
27           methods : (unit -> dominator_methods) ref,         { 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           max_levels : int ref           max_levels : int ref
33         }         }
34     type ('n,'e,'g) dominator_tree     =     type ('n,'e,'g) dominator_tree     = ('n,unit,('n,'e,'g) dom_info) G.graph
35         ('n dom_node,unit,('n,'e,'g) dom_info) G.graph     type ('n,'e,'g) postdominator_tree = ('n,unit,('n,'e,'g) dom_info) G.graph
type ('n,'e,'g) postdominator_tree =
('n dom_node,unit,('n,'e,'g) dom_info) G.graph
36
37     fun graph_info (G.GRAPH dom) : ('n,'e,'g) dom_info = #graph_info dom     fun graph_info (G.GRAPH dom) : ('n,'e,'g) dom_info = #graph_info dom
38
39     fun cfg dom        = #cfg(graph_info dom)     fun cfg(G.GRAPH dom) = let val INFO{cfg,...} = #graph_info dom in cfg end
40     fun max_levels dom = !(#max_levels(graph_info dom))     fun max_levels(G.GRAPH dom) =
41     fun methods dom    = (!(#methods(graph_info dom)))()     let val INFO{max_levels,...} = #graph_info dom in !max_levels end
42
43     (*     (*
44      * This is the main Lengauer/Tarjan algorithm      * This is the main Lengauer/Tarjan algorithm
45      *)      *)
46     fun tarjan_lengauer (name,edge_label) (CFG as (G.GRAPH cfg)) =     fun tarjan_lengauer (name,edge_label) (origCFG,CFG as (G.GRAPH cfg)) =
47     let val N           = #order cfg ()     let val N           = #order cfg ()
48         val M           = #capacity cfg ()         val M           = #capacity cfg ()
49         val r           = case #entries cfg () of         val r           = case #entries cfg () of
# Line 81  Line 54
54         val dfnum       = A.array (M, ~1)         val dfnum       = A.array (M, ~1)
55         val vertex      = A.array (N, ~1)         val vertex      = A.array (N, ~1)
56         val parent      = A.array (M, ~1)         val parent      = A.array (M, ~1)
57         val bucket      = A.array (M, [])    : G.node_id list array         val bucket      = A.array (M, []) : node list array
58         val semi        = A.array (M, r)         val semi        = A.array (M, r)
59         val ancestor    = A.array (M, ~1)         val ancestor    = A.array (M, ~1)
60         val idom        = A.array (M, r)         val idom        = A.array (M, r)
61         val samedom     = A.array (M, ~1)         val samedom     = A.array (M, ~1)
62         val best        = A.array (M, ~1)         val best        = A.array (M, ~1)
63         val max_levels  = ref 0         val max_levels  = ref 0
64         val dom_info    = { cfg = CFG, edge_label = edge_label,         val levelsMap   = A.array(M,~1000000)
65                             methods = ref(fn _ => raise G.Graph "dom"),         val dom_info    = INFO{ cfg        = origCFG,
66                             max_levels = max_levels }                                 edge_label = edge_label,
67                                   levelsMap  = levelsMap,
68                                   preorder   = ref NONE,
69                                   postorder  = ref NONE,
70                                   max_levels = max_levels
71                                 }
72         val Dom as G.GRAPH domtree = GI.graph(name, dom_info, N)         val Dom as G.GRAPH domtree = GI.graph(name, dom_info, N)
73
74         (* step 1         (* step 1
# Line 201  Line 179
179         val _ = dumpArray "idom" idom         val _ = dumpArray "idom" idom
180          *)          *)
181
182         (* Create the nodes of the dominator tree *)         (* Create the nodes/edges of the dominator tree *)
183         fun addNode ~1 = ()         fun buildGraph(i,maxLevel) =
184           | addNode i  = let val v = A.sub(vertex,i)             if i < N then
185                          in  #add_node domtree (v,             let val v = A.sub(vertex,i)
186                                 DOM { node      = #node_info cfg v,             in  #add_node domtree (v,#node_info cfg v);
level     = 0,
preorder  = 0,
postorder = 0
});
end

(* Create the edges of the dominator tree *)
val _ = #forall_nodes domtree
(fn (v,_) =>
187                       if v <> r then                       if v <> r then
188                          let val w = A.sub(idom,v)                          let val w = A.sub(idom,v)
189                          in  #add_edge domtree (w,v,()) end                        val l = A.sub(levelsMap,w)+1
190                       else  ())                    in  A.update(levelsMap,v,l);
192         (* Compute the level/preorder/postorder numbers *)                        buildGraph(i+1,l)
193         fun computeNumbering(level,preorder,postorder,n) =                    end
194         let val DOM { node, ... } = #node_info domtree n                 else
195             val (preorder',postorder',max_level) =                   (A.update(levelsMap,v,0);
196                     computeNumbering'(level+1,preorder+1,postorder,                    buildGraph(i+1,maxLevel)
197                                       #succ domtree n)                   )
DOM{node=node,level=level,
preorder=preorder,postorder=postorder'});
(preorder',postorder'+1,max_level)
end

and computeNumbering'(level,preorder,postorder,[]) =
(preorder,postorder,level)
| computeNumbering'(level,preorder,postorder,n::ns) =
let val (preorder',postorder',max1) =
computeNumbering(level,preorder,postorder,n)
val (preorder',postorder',max2) =
computeNumbering'(level,preorder',postorder',ns)
in  (preorder',postorder',Int.max(max1,max2))
198               end               end
199               else maxLevel
200
201         val (_,_,max) = computeNumbering(0,0,0,r)         val max = buildGraph(0,1)
202     in     in
203         max_levels := max+1;         max_levels := max+1;
204         #set_entries domtree [r];         #set_entries domtree [r];
# Line 253  Line 206
206         Dom         Dom
207     end     end
208
(* The algorithm specialized to making dominators and postdominators *)
209
210     fun dominator_trees (cfg as (G.GRAPH g)) =     (* The algorithm specialized to making dominators and postdominators *)
211     let val Dom as G.GRAPH D =     fun makeDominator cfg = tarjan_lengauer("Dom","dom") (cfg,cfg)
212               tarjan_lengauer ("Dom","dom") cfg     fun makePostdominator cfg =
213         val PDom as G.GRAPH P =          tarjan_lengauer("PDom","pdom") (cfg,Rev.rev_view cfg)
tarjan_lengauer ("PDom","pdom") (Rev.rev_view cfg)
214
215         fun immediately_dominates (i,j) =     (* Methods *)
case #in_edges D j of
(k,_,_)::_ => i = k
|  _          => false
216
217         fun immediately_postdominates (i,j) =     (* Does i immediately dominate j? *)
218       fun immediately_dominates (G.GRAPH D) (i,j) =
219             case #in_edges D j of             case #in_edges D j of
220                (k,_,_)::_ => i = k                (k,_,_)::_ => i = k
221             |  _          => false             |  _          => false
222
223         (* immediate dominator of n *)         (* immediate dominator of n *)
224         fun idom n = case #in_edges D n of     fun idom (G.GRAPH D) n =
225           case #in_edges D n of
226                         (n,_,_)::_ => n                         (n,_,_)::_ => n
227                      |  _          => ~1                      |  _          => ~1
228
229         fun idoms n = #succ D n     (* nodes that n immediately dominates *)
230       fun idoms (G.GRAPH D) = #succ D
231
232         fun subtree (succ,[],S) = S     (* nodes that n dominates *)
233           | subtree (succ,n::ns,S) = subtree(succ,succ n,     fun doms (G.GRAPH D) =
234                                          subtree(succ,ns,n::S))     let fun subtree ([],S) = S
235             | subtree (n::ns,S) = subtree(#succ D n,subtree(ns,n::S))
236         fun dom_level i =     in  fn n => subtree([n], [])
237             let val DOM{level,...} = #node_info D i in level end     end
238         fun pdom_level i =
239             let val DOM{level,...} = #node_info P i in level end
240       fun prePostOrders(G.GRAPH dom) =
241             (* Least common ancestors *)     let val INFO{ preorder,postorder,...} = #graph_info dom
242         fun dom_lca(a,b) =         (* Compute the preorder/postorder numbers *)
243             let val l_a = dom_level a         fun computeThem() =
244                 val l_b = dom_level b         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               end
255
256               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
275       (* 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                 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                 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                 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)                 val a = up_a(a,l_a)
288                 val b = up_b(b,l_b)                 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)                 fun up_both(a,b) = if a = b then a else up_both(idom a,idom b)
290             in  up_both(a,b)     in  up_both(a,b) end
end
fun pdom_lca(a,b) =
let val l_a = pdom_level a
val l_b = pdom_level b
fun ipdom i = case #in_edges P i of (j,_,_)::_ => j
fun up_a(a,l_a) = if l_a > l_b then up_a(ipdom a,l_a-1) else a
fun up_b(b,l_b) = if l_b > l_a then up_b(ipdom b,l_b-1) else b
val a = up_a(a,l_a)
val b = up_b(b,l_b)
fun up_both(a,b) = if a = b then a else up_both(ipdom a,ipdom b)
in  up_both(a,b)
end

fun doms n = subtree(#succ D, [n], [])

(* immediate postdominator of n *)
fun ipdom n = case #in_edges P n of
(n,_,_)::_ => n
|  _          => ~1
fun ipdoms n = #succ P n
fun pdoms n  = subtree(#succ P, [n], [])
291
292        (* is x and ancestor of y in D?        (* is x and ancestor of y in D?
293         * This is true iff PREORDER(x) <= PREORDER(y) and         * This is true iff PREORDER(x) <= PREORDER(y) and
294         *                  POSTORDER(x) >= POSTORDER(y)         *                  POSTORDER(x) >= POSTORDER(y)
295         *)         *)
296        fun dominates (x,y) =     fun dominates Dom =
297        let val DOM { preorder = a, postorder = b, ... } = #node_info D x     let val (pre,post) = prePostOrders Dom
298            val DOM { preorder = c, postorder = d, ... } = #node_info D y     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        in  a <= c andalso b >= d
304        end        end
305       end
306
307        fun strictly_dominates (x,y) =     fun strictly_dominates Dom =
308        let val DOM { preorder = a, postorder = b, ... } = #node_info D x     let val (pre,post) = prePostOrders Dom
309            val DOM { preorder = c, postorder = d, ... } = #node_info D y     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        in  a < c andalso b > d
315        end        end

fun postdominates (x,y) =
let val DOM { preorder = a, postorder = b, ... } = #node_info P x
val DOM { preorder = c, postorder = d, ... } = #node_info P y
in  a <= c andalso b >= d
316        end        end
317
318        fun strictly_postdominates (x,y) =     fun control_equivalent (Dom,PDom) =
319        let val DOM { preorder = a, postorder = b, ... } = #node_info P x     let val dom  = dominates Dom
320            val DOM { preorder = c, postorder = d, ... } = #node_info P y         val pdom = dominates PDom
321        in  a < c andalso b > d     in  fn (x,y) => dom(x,y) andalso pdom(y,x) orelse dom(y,x) andalso pdom(x,y)
322        end        end
323
fun control_equivalent (x,y) =
dominates(x,y) andalso postdominates(y,x) orelse
dominates(y,x) andalso postdominates(x,y)

324        (* control equivalent partitions        (* control equivalent partitions
325         * two nodes a and b are control equivalent iff         * two nodes a and b are control equivalent iff
326         *    a dominates b and b postdominates a (or vice versa)         *    a dominates b and b postdominates a (or vice versa)
# Line 360  Line 329
329         *          k not pdom i         *          k not pdom i
330         * This algorithm runs in O(n)         * This algorithm runs in O(n)
331         *)         *)
332        fun control_equivalent_partitions() =     fun control_equivalent_partitions (G.GRAPH D,PDom) =
333        let fun walkDom([],S) = S     let val postdominates = dominates PDom
334           fun walkDom([],S) = S
335              | walkDom(n::waiting,S) =              | walkDom(n::waiting,S) =
336                 let val (waiting,S,S') =                 let val (waiting,S,S') =
337                         findEquiv(n,#out_edges D n,waiting,S,[n])                         findEquiv(n,#out_edges D n,waiting,S,[n])
# Line 381  Line 351
351            equivSets            equivSets
352        end        end
353
354           (* Methods for dominators/postdominator manipulation *)     fun levelsMap(G.GRAPH dom) =
355        val methods = { dominates              = dominates,     let val INFO{levelsMap,...} = #graph_info dom
356                        strictly_dominates     = strictly_dominates,     in  levelsMap end
postdominates          = postdominates,
strictly_postdominates = strictly_postdominates,
control_equivalent     = control_equivalent,
idom                   = idom,
idoms                  = idoms,
doms                   = doms,
ipdom                  = ipdom,
ipdoms                 = ipdoms,
pdoms                  = pdoms,
dom_level              = dom_level,
pdom_level             = pdom_level,
dom_lca                = dom_lca,
pdom_lca               = pdom_lca,
immediately_dominates  = immediately_dominates,
immediately_postdominates = immediately_postdominates,
control_equivalent_partitions =
control_equivalent_partitions
}
fun get_methods _ = methods
in
#methods (#graph_info D) := get_methods;
#methods (#graph_info P) := get_methods;
(Dom, PDom)
end

fun levels(G.GRAPH dom) =
let val levels = A.array(#capacity dom (),~1)
in  #forall_nodes dom (fn (i,DOM{level,...}) => A.update(levels,i,level));
levels
end
357
358     fun idoms(G.GRAPH dom) =     fun idomsMap(G.GRAPH dom) =
359     let val idoms = A.array(#capacity dom (),~1)     let val idoms = A.array(#capacity dom (),~1)
360     in  #forall_edges dom (fn (i,j,_) => A.update(idoms,j,i));     in  #forall_edges dom (fn (i,j,_) => A.update(idoms,j,i));
361         idoms         idoms

Legend:
 Removed from v.428 changed lines Added in v.429