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

Annotation of /sml/trunk/src/MLRISC/ir-moved/djgraph.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 545 - (view) (download)

1 : monnier 245 (*
2 :     * The algorithm for dominance frontier and iterated dominance
3 :     * frontier is due to Sreedhar, Gao and Lee. The algorithm as cited
4 :     * uses the DJgraph. In order not to bother with constructing and
5 :     * maintaining the DJgraph, we'll just use a combination of the dominator tree
6 :     * and the original cfg. This alteration does not change the linear
7 :     * complexity of the algorithm. I'm also using a simple time stamp trick to
8 :     * avoid the data structure initialization step; this should make the
9 :     * algorithm sublinear in N in practice, where N is the number of nodes
10 :     * in the CFG.
11 :     *
12 :     * --Allen
13 :     *)
14 :    
15 : george 545 functor DJGraph (Dom : DOMINATOR_TREE) : DJ_GRAPH =
16 : monnier 245 struct
17 :    
18 :     structure G = Graph
19 :     structure Dom = Dom
20 :     structure A = Array
21 :    
22 :     type ('n,'e,'g) dj_graph = ('n,'e,'g) Dom.dominator_tree
23 :    
24 :     fun dj_graph (D as G.GRAPH dom) =
25 :     let val G.GRAPH cfg = Dom.cfg D
26 :     val L = Dom.max_levels D
27 :     val N = #capacity dom ()
28 : monnier 429 val levels = Dom.levelsMap D
29 : monnier 245 val in_DF = A.array(N,0) (* has appeared in the DF set? *)
30 :     val stamp = ref 0
31 :     fun new_stamp() = let val s = !stamp + 1 in stamp := s; s end
32 :    
33 : george 545 fun unmarked(marked,i,stamp : int) =
34 : monnier 245 let val s = A.sub(marked,i)
35 :     in if s = stamp then false else (A.update(marked,i,stamp); true)
36 :     end
37 :    
38 :     (*
39 :     * Compute the dominance frontiers of a node
40 :     * Dominance frontier of x:
41 :     * The set of all nodes y such that x dominates a predecessor
42 :     * of y but x doesn't strictly dominates y.
43 :     *)
44 :     fun DF x =
45 :     let val stamp = new_stamp()
46 : monnier 411 val level_x = A.sub(levels,x)
47 : monnier 245 fun walk(z, S) =
48 :     let fun scan((_,y,_)::es,S) =
49 : monnier 411 if A.sub(levels,y) <= level_x andalso
50 : monnier 245 unmarked(in_DF,y,stamp) then scan(es,y::S)
51 :     else scan(es,S)
52 :     | scan([],S) = S
53 :     val S = scan(#out_edges cfg z,S)
54 :     fun walkList([],S) = S
55 :     | walkList((_,z,_)::es,S) = walkList(es,walk(z,S))
56 :     in walkList(#out_edges dom z,S)
57 :     end
58 :     in walk(x,[])
59 :     end
60 :    
61 :     val in_alpha = A.array(N,0) (* has appeared in N_alpha? *)
62 :     val visited = A.array(N,0) (* has it been visited *)
63 :     val piggybank = A.array(L,[]) (* nodes in the piggy bank *)
64 :    
65 :     (*
66 :     * This algorithm is described in POPL 95
67 :     *)
68 :     fun IDFs xs =
69 :     let val stamp = new_stamp()
70 :     fun init([],l) = l
71 :     | init(x::xs,l) =
72 : monnier 411 let val l_x = A.sub(levels,x)
73 : monnier 245 in A.update(in_alpha,x,stamp);
74 :     A.update(piggybank,l_x,x::A.sub(piggybank,l_x));
75 :     init(xs,if l < l_x then l_x else l)
76 :     end
77 :     fun visit(y,level_x,S) =
78 :     let fun scan([],S) = S
79 :     | scan((_,z,_)::es,S) =
80 : monnier 411 let val level_z = A.sub(levels,z)
81 : monnier 245 in if level_z <= level_x andalso unmarked(in_DF,z,stamp)
82 :     then (if A.sub(in_alpha,z) <> stamp
83 :     then A.update(piggybank,level_z,
84 :     z::A.sub(piggybank,level_z))
85 :     else ();
86 :     scan(es,z::S))
87 :     else scan(es,S)
88 :     end
89 :     fun visitSucc([],S) = S
90 :     | visitSucc((_,z,_)::es,S) =
91 :     visitSucc(es,if unmarked(visited,z,stamp)
92 :     then visit(z,level_x,S) else S)
93 :     val S = scan(#out_edges cfg y,S)
94 :     in visitSucc(#out_edges dom y,S)
95 :     end
96 :    
97 :     fun visitAll(~1,S) = S
98 :     | visitAll(l,S) =
99 :     case A.sub(piggybank,l) of
100 :     [] => visitAll(l-1,S)
101 :     | x::xs => (A.update(visited,x,stamp);
102 :     A.update(piggybank,l,xs);
103 : monnier 411 visitAll(l,visit(x,A.sub(levels,x),S)))
104 : monnier 245
105 :     val L = init(xs,~1)
106 :     in visitAll(L,[])
107 :     end
108 :    
109 :     fun IDF x = IDFs [x]
110 :     in
111 :     { DF = DF, IDF = IDF, IDFs = IDFs }
112 :     end
113 :    
114 :     end
115 :    

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