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
 [smlnj] / sml / branches / SMLNJ / src / MLRISC / ir-moved / dominator.sml

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

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