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

Diff of /sml/trunk/src/MLRISC/ir-archive/dominator.sml

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

revision 1333, Thu May 22 17:12:13 2003 UTC revision 1334, Thu May 22 22:46:30 2003 UTC
# Line 20  Line 20 
20    
21     exception Dominator     exception Dominator
22    
23       fun singleEntryOf (G.GRAPH g) =
24           case #entries g () of
25               [e] => e
26             | _ => raise Dominator
27    
28     type node = G.node_id     type node = G.node_id
29    
30     datatype ('n,'e,'g) dom_info =     datatype ('n,'e,'g) dom_info =
# Line 47  Line 52 
52     fun tarjan_lengauer (name,edge_label) (origCFG,CFG as (G.GRAPH cfg)) =     fun tarjan_lengauer (name,edge_label) (origCFG,CFG as (G.GRAPH cfg)) =
53     let val N           = #order cfg ()     let val N           = #order cfg ()
54         val M           = #capacity cfg ()         val M           = #capacity cfg ()
55         val r           = case #entries cfg () of         val r           = singleEntryOf CFG
                            [r] => r  
                          | _   => raise Dominator  
56         val in_edges    = #in_edges cfg         val in_edges    = #in_edges cfg
57         val succ        = #succ cfg         val succ        = #succ cfg
58         val dfnum       = A.array (M, ~1)         val dfnum       = A.array (M, ~1)
# Line 239  Line 242 
242     end     end
243    
244    
245     fun prePostOrders(G.GRAPH dom) =     fun prePostOrders(g as G.GRAPH dom) =
246     let val INFO{ preorder,postorder,...} = #graph_info dom     let val INFO{ preorder,postorder,...} = #graph_info dom
247         (* Compute the preorder/postorder numbers *)         (* Compute the preorder/postorder numbers *)
248         fun computeThem() =         fun computeThem() =
249         let val N   = #capacity dom ()         let val N   = #capacity dom ()
250             val [r] = #entries dom ()             val r = singleEntryOf g
251             val pre  = A.array(N,~1000000)             val pre  = A.array(N,~1000000)
252             val post = A.array(N,~1000000)             val post = A.array(N,~1000000)
253             fun computeNumbering(preorder,postorder,n) =             fun computeNumbering(preorder,postorder,n) =
# Line 280  Line 283 
283     in  fn i => A.sub(levelsMap,i) end     in  fn i => A.sub(levelsMap,i) end
284    
285     (* Entry position *)     (* Entry position *)
286     fun entryPos(G.GRAPH D) =     fun entryPos(g as G.GRAPH D) =
287     let val INFO{entryPos,...} = #graph_info D     let val INFO{entryPos,...} = #graph_info D
288     in  case !entryPos of     in  case !entryPos of
289           SOME t => t           SOME t => t
290         | NONE =>         | NONE =>
291           let val [ENTRY] = #entries D ()           let val entry = singleEntryOf g
292               val N       = #capacity D ()               val N       = #capacity D ()
293               val t       = A.array(N, ENTRY)               val t       = A.array(N, entry)
294               fun init(X,Y) =               fun init(X,Y) =
295                 (A.update(t,X,Y);                 (A.update(t,X,Y);
296                  app (fn Z => init(Z,Y)) (#succ D X)                  app (fn Z => init(Z,Y)) (#succ D X)
297                 )                 )
298           in  entryPos := SOME t;           in  entryPos := SOME t;
299               app (fn Z => init(Z,Z)) (#succ D ENTRY);               app (fn Z => init(Z,Z)) (#succ D entry);
300               t               t
301           end           end
302     end     end
# Line 302  Line 305 
305     fun lca (Dom as G.GRAPH D) (a,b) =     fun lca (Dom as G.GRAPH D) (a,b) =
306     let val l_a = level Dom a     let val l_a = level Dom a
307         val l_b = level Dom b         val l_b = level Dom b
308         fun idom i = case #in_edges D i of (j,_,_)::_ => j         fun idom i = case #in_edges D i of
309                            (j,_,_)::_ => j
310                          | [] => raise Fail "DominatorTree:lca:idom: []"
311         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
312         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
313         val a = up_a(a,l_a)         val a = up_a(a,l_a)

Legend:
Removed from v.1333  
changed lines
  Added in v.1334

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