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

Annotation of /MLRISC/trunk/ir-archive/k-djgraph.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2126 - (view) (download)

1 : george 912 (*
2 :     * The algorithm for computing iterated dominance
3 :     * frontier is my own algorithm which uses the $k$-compressed DJ-graph,
4 :     * which is a variant of DJ-graph due to Sreedhar, Gao and Lee. Here,
5 :     * I've set k=2. The algorithm using $k$-compressed DJ-graph is significantly
6 :     * faster than the DJ-graph version when |DF(x)| <= k.
7 :     *
8 :     * The write up will be in my thesis.
9 :     *
10 :     * --Allen
11 :     *)
12 :    
13 :     functor K_DJGraph (Dom : DOMINATOR_TREE) : DJ_GRAPH =
14 :     struct
15 :    
16 :     structure G = Graph
17 :     structure Dom = Dom
18 :     structure A = Array
19 :    
20 :     type ('n,'e,'g) dj_graph = ('n,'e,'g) Dom.dominator_tree
21 :    
22 :     fun error msg = MLRiscErrorMsg.error("K_DJGraph",msg)
23 :    
24 :     val stats = true (* collect statistics? *)
25 :     val levelPrune = true
26 :     val domPrune = true
27 :     val pathPrune = true
28 :     val visitCount = MLRiscControl.getCounter "dj-visit-count"
29 :     val liveVisitCount = MLRiscControl.getCounter "dj-live-visit-count"
30 :     val debug = true
31 :     val K_max = 2
32 :    
33 :     fun DJ x = x
34 :    
35 :     (* Compute dominance frontier *)
36 :     fun DF (D as G.GRAPH dom) =
37 :     let val G.GRAPH cfg = Dom.cfg D
38 :     val L = Dom.max_levels D
39 :     val N = #capacity dom ()
40 :     val levels = Dom.levelsMap D
41 :     val in_DF = A.array(N,0) (* has appeared in the DF set? *)
42 :     val stamp = ref 0
43 :     fun new_stamp() = let val s = !stamp + 1 in stamp := s; s end
44 :    
45 :     fun unmarked(marked,i,stamp : int) =
46 :     let val s = A.sub(marked,i)
47 :     in if s = stamp then false else (A.update(marked,i,stamp); true)
48 :     end
49 :    
50 :     (*
51 :     * Compute the dominance frontiers of a node
52 :     * Dominance frontier of x:
53 :     * The set of all nodes y such that x dominates a predecessor
54 :     * of y but x doesn't strictly dominates y.
55 :     *)
56 :     fun DF x =
57 :     let val stamp = new_stamp()
58 :     val level_x = A.sub(levels,x)
59 :     fun walk(z, S) =
60 :     let fun scan((_,y,_)::es,S) =
61 :     if A.sub(levels,y) <= level_x andalso
62 :     unmarked(in_DF,y,stamp) then scan(es,y::S)
63 :     else scan(es,S)
64 :     | scan([],S) = S
65 :     val S = scan(#out_edges cfg z,S)
66 :     fun walkList([],S) = S
67 :     | walkList((_,z,_)::es,S) = walkList(es,walk(z,S))
68 :     in walkList(#out_edges dom z,S)
69 :     end
70 :     in walk(x,[])
71 :     end
72 :    
73 :     in DF end
74 :    
75 :     (* Compute iterated dominance frontier *)
76 :     fun IDFs (D as G.GRAPH dom) =
77 :     let val G.GRAPH cfg = Dom.cfg D
78 :     val L = Dom.max_levels D
79 :     val N = #capacity dom ()
80 :     val levels = Dom.levelsMap D
81 :     val in_DF = A.array(N,0) (* has appeared in the DF set? *)
82 :     val stamp = ref 0
83 :     fun new_stamp() = let val s = !stamp + 1 in stamp := s; s end
84 :    
85 :     fun unmarked(marked,i,stamp : int) =
86 :     let val s = A.sub(marked,i)
87 :     in if s = stamp then false else (A.update(marked,i,stamp); true)
88 :     end
89 :    
90 :     val in_alpha = A.array(N,0) (* has appeared in N_alpha? *)
91 :     val visited = A.array(N,0) (* has it been visited *)
92 :     val piggybank = A.array(L,[]) (* nodes in the piggy bank *)
93 :    
94 :     (*
95 :     * This algorithm is described in POPL 95
96 :     *)
97 :     fun IDFs xs =
98 :     let val stamp = new_stamp()
99 :     fun init([],l) = l
100 :     | init(x::xs,l) =
101 :     let val l_x = A.sub(levels,x)
102 :     in A.update(in_alpha,x,stamp);
103 :     A.update(piggybank,l_x,x::A.sub(piggybank,l_x));
104 :     init(xs,if l < l_x then l_x else l)
105 :     end
106 :     fun visit(y,level_x,S) =
107 :     let fun scan([],S) = S
108 :     | scan((_,z,_)::es,S) =
109 :     let val level_z = A.sub(levels,z)
110 :     in if level_z <= level_x andalso unmarked(in_DF,z,stamp)
111 :     then (if A.sub(in_alpha,z) <> stamp
112 :     then A.update(piggybank,level_z,
113 :     z::A.sub(piggybank,level_z))
114 :     else ();
115 :     scan(es,z::S))
116 :     else scan(es,S)
117 :     end
118 :     fun visitSucc([],S) = S
119 :     | visitSucc((_,z,_)::es,S) =
120 :     visitSucc(es,if unmarked(visited,z,stamp)
121 :     then visit(z,level_x,S) else S)
122 :     val S = scan(#out_edges cfg y,S)
123 :     in visitSucc(#out_edges dom y,S)
124 :     end
125 :    
126 :     fun visitAll(~1,S) = S
127 :     | visitAll(l,S) =
128 :     case A.sub(piggybank,l) of
129 :     [] => visitAll(l-1,S)
130 :     | x::xs => (A.update(visited,x,stamp);
131 :     A.update(piggybank,l,xs);
132 :     visitAll(l,visit(x,A.sub(levels,x),S)))
133 :    
134 :     val L = init(xs,~1)
135 :     in visitAll(L,[])
136 :     end
137 :    
138 :     in IDFs
139 :     end
140 :    
141 :    
142 :     (* Compute iterated dominance frontier intersected with liveness.
143 :     * This is my special algorithm! The idea is that when we find a
144 :     * new node b in IDF^+(S) we first check whether b is liveIn. If not,
145 :     * we can prune the search right there. If so, we continue as normal.
146 :     * Checking whether something is liveIn triggers the incremental liveness
147 :     * routine.
148 :     *
149 :     * -- Allen
150 :     *)
151 :     datatype kind = JOIN | DOM
152 :    
153 :     fun LiveIDFs(D as G.GRAPH dom) =
154 :     let val G.GRAPH cfg = Dom.cfg D
155 :     val L = Dom.max_levels D
156 :     val N = #capacity dom ()
157 :     val levels = Dom.levelsMap D
158 :    
159 :     val in_phi = A.array(N,0) (* has appeared in the DF set? *)
160 :     val stamp = ref 0
161 :     fun new_stamp() = let val s = !stamp + 2 in stamp := s; s end
162 :    
163 :     val in_alpha = A.array(N,0) (* has appeared in N_alpha? *)
164 :     val piggybank = A.array(L,[]) (* nodes in the piggy bank *)
165 :     val minJLevels = A.array(N,10000000)
166 :     val djGraph = A.array(N,[]) (* path compressed dj graph *)
167 :     val liveIn = A.array(N,0) (* is a variable live in *)
168 :     val visited = A.array(N,0)
169 :     val strictly_dominates = Dom.dominates D
170 :    
171 :     val K_inf = 255
172 :    
173 :     fun compressDJGraph(X, lvl) =
174 :     let val nextLvl = lvl + 1
175 :     val stamp = ~X
176 :    
177 :     (* merge join list, make sure there are no duplicates *)
178 :     fun mergeJoin(Z, E, n) =
179 :     if A.sub(visited, Z) = stamp orelse
180 :     A.sub(levels, Z) >= lvl then (E, n)
181 :     else (A.update(visited, Z, stamp);
182 :     (Z::E, n+1))
183 :    
184 :     fun mergeJoins([], E, n) = (E, n)
185 :     | mergeJoins(Z::Zs, E, n) =
186 :     let val (E, n) = mergeJoin(Z, E, n)
187 :     in mergeJoins(Zs, E, n)
188 :     end
189 :    
190 :     fun appendJoins([], E) = E
191 :     | appendJoins(Z::Zs, E) = appendJoins(Zs, (JOIN,Z)::E)
192 :    
193 :     fun collapse([], DJ_X) = DJ_X
194 :     | collapse((e as (DOM,_))::Zs, DJ_X) = collapse(Zs, e::DJ_X)
195 :     | collapse((e as (JOIN,Z))::Zs, DJ_X) =
196 :     if A.sub(levels, Z) <= lvl then collapse(Zs, e::DJ_X)
197 :     else collapse(Zs, DJ_X)
198 :    
199 :     (* L_X -- min level of all join edges in SubTree(X)
200 :     * DJ_X -- all dj-graph edges of X
201 :     * E_X -- all J-edges in SubTree(X) to level < lvl.
202 :     * K_X -- |E_X|
203 :     *)
204 :     fun walkDomSucc([], L_X, DJ_X, E_X, K_X) = (L_X, DJ_X, E_X, K_X)
205 :     | walkDomSucc((_,Y,_)::es, L_X, DJ_X, E_X, K_X) =
206 :     let val (L_Y, E_Y, K_Y) = compressDJGraph(Y, nextLvl)
207 :     val L_X = Int.min(L_X, L_Y)
208 :     in if pathPrune then
209 :     if L_Y >= nextLvl then
210 :     (* disconnect dom edge! *)
211 :     walkDomSucc(es, L_X, DJ_X, E_X, K_X)
212 :     else if K_Y <= K_max then
213 :     (* path compress! *)
214 :     let val (E_X, K_X) = mergeJoins(E_Y, E_X, K_X)
215 :     in walkDomSucc(es, L_X, appendJoins(E_Y, DJ_X), E_X, K_X)
216 :     end
217 :     else
218 :     let val Zs = A.sub(djGraph, Y)
219 :     in if length Zs <= K_max then
220 :     walkDomSucc(es, L_X, collapse(Zs,DJ_X), [], K_inf)
221 :     else
222 :     walkDomSucc(es, L_X, (DOM,Y)::DJ_X, [], K_inf)
223 :     end
224 :     else
225 :     walkDomSucc(es, L_X, (DOM,Y)::DJ_X, [], K_inf)
226 :     end
227 :     fun walkCFGSucc([], L_X, DJ_X, E_X, K_X) = (L_X, DJ_X, E_X, K_X)
228 :     | walkCFGSucc((_,Y,_)::es, L_X, DJ_X, E_X, K_X) =
229 :     let val L_X = Int.min(L_X, A.sub(levels, Y))
230 :     val (E_X, K_X) = mergeJoin(Y, E_X, K_X)
231 :     in walkCFGSucc(es, L_X, (JOIN,Y)::DJ_X, E_X, K_X)
232 :     end
233 :    
234 :     val (L_X, DJ_X, E_X, K_X) =
235 :     walkDomSucc(#out_edges dom X, 10000000, [], [], 0)
236 :     val (L_X, DJ_X, E_X, K_X) =
237 :     walkCFGSucc(#out_edges cfg X, L_X, DJ_X, E_X, K_X)
238 :    
239 :     in A.update(minJLevels, X, L_X);
240 :     A.update(djGraph, X, DJ_X);
241 :     (L_X, E_X, K_X)
242 :     end
243 :    
244 :     val [ENTRY] = #entries dom ()
245 :     val _ = compressDJGraph(ENTRY, 0)
246 :    
247 :    
248 :     fun LiveIDFs {defs, localLiveIn=[]} = [] (* special case *)
249 :     | LiveIDFs {defs=xs, localLiveIn} =
250 :     let val stamp = new_stamp()
251 :     (* val n = ref 0
252 :     val m = ref 0 *)
253 :    
254 :     fun initDefs([],maxLvl) = maxLvl
255 :     | initDefs(x::xs,maxLvl) =
256 :     let val lvl_x = A.sub(levels,x)
257 :     in A.update(in_alpha,x,stamp);
258 :     A.update(piggybank,lvl_x,x::A.sub(piggybank,lvl_x));
259 :     initDefs(xs,if maxLvl < lvl_x then lvl_x else maxLvl)
260 :     end
261 :    
262 :     fun markLiveIn(b) =
263 :     let fun markPred [] = ()
264 :     | markPred((j,_,_)::es) =
265 :     (if A.sub(liveIn,j) <> stamp andalso
266 :     A.sub(in_alpha,j) <> stamp then
267 :     markLiveIn j
268 :     else ();
269 :     markPred es
270 :     )
271 :     in (* m := !m + 1; *)
272 :     A.update(liveIn,b,stamp);
273 :     if stats then liveVisitCount := !liveVisitCount + 1 else ();
274 :     markPred(#in_edges cfg b)
275 :     end
276 :    
277 :     fun initLiveIn [] = ()
278 :     | initLiveIn(x::xs) = (markLiveIn x; initLiveIn xs)
279 :    
280 :     fun isLive b = A.sub(liveIn,b) = stamp
281 :    
282 :     fun visit(y,level_x,S) =
283 :     let fun foreach([],S) = S
284 :     | foreach((JOIN,z)::zs,S) =
285 :     let val level_z = A.sub(levels,z)
286 :     in if level_z <= level_x andalso
287 :     A.sub(in_phi,z) <> stamp andalso
288 :     isLive z
289 :     (* z is a new IDF^+ candidate;
290 :     * make sure it is live.
291 :     *)
292 :     then (A.update(in_phi,z,stamp);
293 :     if A.sub(in_alpha,z) <> stamp
294 :     then A.update(piggybank,level_z,
295 :     z::A.sub(piggybank,level_z))
296 :     else ();
297 :     foreach(zs,z::S)
298 :     )
299 :     else foreach(zs,S)
300 :     end
301 :     | foreach((DOM,z)::zs,S) =
302 :     foreach(zs,if isLive z andalso
303 :     A.sub(visited,z) <> stamp andalso
304 :     (not levelPrune orelse
305 :     A.sub(minJLevels,z) <= level_x)
306 :     then (A.update(visited,z,stamp);
307 :     visit(z,level_x,S)
308 :     )
309 :     else S)
310 :     in if stats then visitCount := !visitCount + 1 else ();
311 :     foreach(A.sub(djGraph, y),S)
312 :     end
313 :    
314 :     fun visitAll(~1,S) = S
315 :     | visitAll(l,S) =
316 :     case A.sub(piggybank,l) of
317 :     [] => visitAll(l-1,S)
318 :     | x::xs =>
319 :     let val _ = A.update(piggybank,l,xs)
320 :     val _ = A.update(visited,x,stamp);
321 :     val S = visit(x, A.sub(levels, x), S)
322 :     in
323 :     visitAll(l,S)
324 :     end
325 :    
326 :     fun domTest([x],uses) =
327 :     let fun loop [] = true
328 :     | loop(y::ys) = strictly_dominates(x,y) andalso loop ys
329 :     in loop uses end
330 :     | domTest _ = false
331 :    
332 :     in if domPrune andalso domTest(xs,localLiveIn) then []
333 :     else
334 :     let val L = initDefs(xs, ~1)
335 :     in initLiveIn(localLiveIn);
336 :     visitAll(L, [])
337 :     end
338 :     end
339 :    
340 :     in LiveIDFs
341 :     end
342 :    
343 :     end
344 :    

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