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
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

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  
                                    });  
                             addNode (i-1)  
                         end  
   
        val _ = addNode (N-1)  
   
        (* 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);
191                          #add_edge domtree (w,v,());
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)                   )
        in  #add_node 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

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