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/compiler/CodeGen/cpscompile/spill-new.sml
ViewVC logotype

Annotation of /sml/trunk/compiler/CodeGen/cpscompile/spill-new.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1094 - (view) (download)
Original Path: sml/trunk/src/compiler/CodeGen/cpscompile/spill-new.sml

1 : leunga 1094 (* spill.sml
2 :     *
3 :     * Copyright 2002 by Bell Laboratories
4 :     *)
5 :    
6 :     (*
7 :     * This is a complete rewrite of the old Spill module.
8 :     * The old module suffers from some serious performance problem but
9 :     * I cannot decipher the old code fully, so instead of patching the problems up,
10 :     * I'm reimplementing it with a different algorithm. The new code is more
11 :     * modular, smaller when compiled, and substantially faster
12 :     * (O(n log n) time and O(n) space).
13 :     *
14 :     * As far as I can tell, the purpose of this module is to make sure the
15 :     * number of live variables at any program point (the bandwidth)
16 :     * does not exceed a certain limit, which is determined by the
17 :     * size of the spill area.
18 :     *
19 :     * When the bandwidth is too large, we decrease the register pressure by
20 :     * packing live variables into spill records. How we achieve this is
21 :     * completely different than what we did in the old code.
22 :     *
23 :     * First, there is something that MLRiscGen code generator does
24 :     * that we should be aware of:
25 :     *
26 :     * o MLRiscGen performs code motion!
27 :     *
28 :     * In particular, it will move floating point computations and
29 :     * address computations involving only the heap pointer to
30 :     * their use sites (if there is only a single use).
31 :     * What this means is that if we have a CPS record construction
32 :     * statement
33 :     *
34 :     * RECORD(k,vl,w,e)
35 :     *
36 :     * we should never count the new record address w as live if w
37 :     * has only one use (which is often the case).
38 :     *
39 :     * We should do something similar to floating point, but the transformation
40 :     * there is much more complex, so I won't deal with that.
41 :     *
42 :     * Secondly, there are now two new cps primops at our disposal:
43 :     *
44 :     * 1. rawrecord of record_kind option
45 :     * This pure operator allocates some uninitialized storage from the heap.
46 :     * There are two forms:
47 :     *
48 :     * rawrecord NONE [INT n] allocates a tagless record of length n
49 :     * rawrecord (SOME rk) [INT n] allocates a tagged record of length n
50 :     * and initializes the tag.
51 :     *
52 :     * 2. rawupdate of cty
53 :     * rawupdate cty (v,i,x)
54 :     * Assigns to x to the ith component of record v.
55 :     * The storelist is not updated.
56 :     *
57 :     * We use these new primops for both spilling and increment record construction.
58 :     *
59 :     * 1. Spilling.
60 :     *
61 :     * This is implemented with a linear scan algorithm (but generalized
62 :     * to trees). The algorithm will create a single spill record at the
63 :     * beginning of the cps function and use rawupdate to spill to it,
64 :     * and SELECT or SELp to reload from it. So both spills and reloads
65 :     * are fine-grain operations. In contrast, in the old algorithm
66 :     * "spills" have to be bundled together in records.
67 :     *
68 :     * Ideally, we should sink the spill record construction to where
69 :     * it is needed. We can even split the spill record into multiple ones
70 :     * at the places where they are needed. But CPS is not a good
71 :     * representation for global code motion, so I'll keep it simple and
72 :     * am not attempting this.
73 :     *
74 :     * 2. Incremental record construction (aka record splitting).
75 :     *
76 :     * Records with many values which are simulatenously live
77 :     * (recall that single use record addresses are not considered to
78 :     * be live) are constructed with rawrecord and rawupdate.
79 :     * We allocate space on the heap with rawrecord first, then gradually
80 :     * fill it in with rawupdate. This is the technique suggested to me
81 :     * by Matthias.
82 :     *
83 :     * Some restrictions on when this is applicable:
84 :     * 1. It is not a VECTOR record. The code generator currently
85 :     * does not handle this case. VECTOR record uses double
86 :     * indirection like arrays.
87 :     * 2. All the record component values are defined in the same "basic block"
88 :     * as the record constructor. This is to prevent speculative
89 :     * record construction.
90 :     *
91 :     * -- Allen
92 :     *)
93 :    
94 :     signature SPILL = sig
95 :     val spill : CPS.function list -> CPS.function list
96 :     end (* signature SPILL *)
97 :    
98 :     local
99 :    
100 :     val DEBUG = false
101 :     val MAX_BANDWIDTH = 100 (* Kick in spilling when this many values
102 :     * are live at the same time
103 :     *)
104 :     val SPLIT_LARGE_RECORDS = true (* True if record splitting is enabled *)
105 :     val MAX_RECORD_LEN = 16 (* Split record of this size or larger *)
106 :    
107 :     in
108 :    
109 :     functor SpillFn (MachSpec : MACH_SPEC) : SPILL =
110 :     struct
111 :    
112 :     structure CPS = CPS
113 :     structure P = CPS.P
114 :     structure LV = LambdaVar
115 :     structure H = IntHashTable (* For mapping from lvar *)
116 :    
117 :     val debug_cps_spill = Control.MLRISC.getFlag "debug-cps-spill"
118 :     val debug_cps_spill_info = Control.MLRISC.getFlag "debug-cps-spill-info"
119 :    
120 :     infix 6 \/
121 :     infix 7 /\
122 :     infix 5 --
123 :    
124 :     val error = ErrorMsg.impossible
125 :     val pr = Control.Print.say
126 :     val i2s = Int.toString
127 :    
128 :     val maxgpfree =
129 :     Int.min(MachSpec.spillAreaSz div (2 * MachSpec.valueSize),MAX_BANDWIDTH)
130 :     val maxfpfree =
131 :     Int.min(MachSpec.spillAreaSz div (2 * MachSpec.realSize),MAX_BANDWIDTH)
132 :    
133 :     (* Pretty printing *)
134 :     fun dump(title, cpsFun) =
135 :     if !debug_cps_spill
136 :     then (pr ("------------ "^title^" the spill phase ---------- \n");
137 :     PPCps.printcps0 cpsFun;
138 :     pr "--------------------------------------\n\n")
139 :     else ()
140 :    
141 :     (*
142 :     * The following data structure groups together type specific functions.
143 :     *)
144 :     datatype type_info =
145 :     TYPE_INFO of
146 :     { maxLive : int, (* max live values allowed *)
147 :     isVar : CPS.lvar -> bool, (* is variable a candidate for spilling? *)
148 :     itemSize : int (* number of words per item *)
149 :     }
150 :    
151 :     datatype spill_candidate =
152 :     SPILL_CANDIDATE of
153 :     { lvar : CPS.lvar,
154 :     cty : CPS.cty,
155 :     rank : int (* distance to next use *)
156 :     }
157 :    
158 :     (* Cheap set representation *)
159 :     structure SimpleSet =
160 :     struct
161 :     structure Set = IntRedBlackSet
162 :     val op \/ = Set.union
163 :     val op /\ = Set.intersection
164 :     val op -- = Set.difference
165 :     val O = Set.empty
166 :     val card = Set.numItems (* cardinality *)
167 :     fun rmv(S, x) = Set.delete(S, x) handle _ => S
168 :     end
169 :    
170 :     (* Spill candidates set representation; this one has to be ranked *)
171 :     structure RankedSet =
172 :     struct
173 :     structure Set = RedBlackSetFn
174 :     (type ord_key = spill_candidate
175 :     fun compare(SPILL_CANDIDATE{rank=r1,lvar=v1,...},
176 :     SPILL_CANDIDATE{rank=r2,lvar=v2,...}) =
177 :     case Int.compare(r1,r2) of
178 :     EQUAL => Int.compare(v1,v2)
179 :     | ord => ord
180 :     )
181 :     exception Item of Set.item
182 :     (* as priority queue *)
183 :     fun next S =
184 :     Set.foldr (fn (x,_) => raise Item x) NONE S
185 :     handle Item x => SOME(x, Set.delete(S, x))
186 :     (* Abbreviations for set operations *)
187 :     val op \/ = Set.union
188 :     val op /\ = Set.intersection
189 :     val op -- = Set.difference
190 :     val O = Set.empty
191 :     val card = Set.numItems (* cardinality *)
192 :     fun rmv(S, x) = Set.delete(S, x) handle _ => S
193 :     end
194 :    
195 :     fun rkToCty (CPS.RK_FCONT | CPS.RK_FBLOCK) = CPS.FLTt
196 :     | rkToCty _ = CPS.BOGt
197 :    
198 :     fun splittable CPS.RK_VECTOR = false (* not supported in backend (yet) *)
199 :     | splittable _ = true
200 :    
201 :     (*-------------------------------------------------------------------------
202 :     *
203 :     * All CPS functions can be independently processed.
204 :     *
205 :     * Some complexity assumptions:
206 :     * Hashing is O(1)
207 :     * N = max{number of lvars, size of cps function}
208 :     *
209 :     *-------------------------------------------------------------------------*)
210 :    
211 :     (*------------------------------------------------------------------------
212 :     * markFpAndRec
213 :     * =============
214 :     * Mark all floating point variables and return a hash table
215 :     *
216 :     * This is needed because we do spilling of integer and floating
217 :     * point stuff separately.
218 :     *
219 :     * This function takes O(N) time and space
220 :     *-----------------------------------------------------------------------*)
221 :     fun markFpAndRec cpsFun =
222 :     let val (funKind, f, args, argTypes, body) = cpsFun : CPS.function
223 :     open SimpleSet
224 :     exception FloatSet
225 :     val floatSet = H.mkTable(32,FloatSet)
226 :     val addToFloatSet = H.insert floatSet
227 :     fun fp(r,CPS.FLTt) = addToFloatSet(r,true)
228 :     | fp(r,_) = ()
229 :     exception RecordSet
230 :     val recordSet = H.mkTable(32,RecordSet)
231 :     val markrec = H.insert recordSet
232 :     val findrec = H.find recordSet
233 :    
234 :     (* Mark all record uses *)
235 :     val recUses =
236 :     app (fn (CPS.VAR v,_) =>
237 :     (case findrec v of
238 :     NONE => () (* not a record address *)
239 :     | SOME n => markrec(v, n+1)
240 :     )
241 :     | _ => ()
242 :     )
243 :    
244 :     fun markPure(p,w) =
245 :     case p of
246 :     (* these pure operators actually allocates storage! *)
247 :     (P.fwrap | P.iwrap | P.i32wrap | P.newarray0 |
248 :     P.makeref | P.mkspecial | P.rawrecord _
249 :     ) => markrec(w, 0)
250 :     | _ => ()
251 :    
252 :     fun markfp e =
253 :     case e of
254 :     CPS.APP _ => ()
255 :     | CPS.SWITCH(_,_,es) => app markfp es
256 :     | CPS.SELECT(_,_,w,t,e) => (fp(w,t); markfp e)
257 :     | CPS.RECORD(_,vl,w,e) => (recUses vl; markrec(w, 0); markfp e)
258 :     | CPS.OFFSET(_,_,_,e) => markfp e
259 :     | CPS.SETTER(_,_,e) => markfp e
260 :     | CPS.LOOKER(_,_,w,t,e) => (fp(w,t); markfp e)
261 :     | CPS.ARITH(_,_,w,t,e) => (fp(w,t); markfp e)
262 :     | CPS.PURE(p,_,w,t,e) => (markPure(p,w); fp(w,t); markfp e)
263 :     | CPS.RCC(_,_,w,t,e) => (fp(w,t); markfp e)
264 :     | CPS.BRANCH(_,_,_,e1,e2) => (markfp e1; markfp e2)
265 :     | CPS.FIX _ => error "FIX in Spill.markfp"
266 :    
267 :     val () = ListPair.app fp (args, argTypes) (* mark function parameters *)
268 :     val () = markfp body (* mark function body *)
269 :    
270 :     (* Filter out multiple uses of record values because these
271 :     * are not forward propagated by the backend.
272 :     *)
273 :     val () = if DEBUG then
274 :     H.appi (fn (v, n) =>
275 :     if n >= 2 then pr(LV.lvarName v^" uses="^i2s n^"\n") else ())
276 :     recordSet
277 :     else ()
278 :     val () = H.filter (fn n => n <= 1) recordSet
279 :     in (floatSet, recordSet)
280 :     end
281 :    
282 :     (*--------------------------------------------------------------------------
283 :     * needsSpilling
284 :     * =============
285 :     * This function checks whether we need to perform spilling for
286 :     * the current type, which is either gpr or fpr.
287 :     * Parameterized by type info. This is supposed to be a cheap check
288 :     * since most of the time this function should return false,
289 :     * so no information is saved.
290 :     *
291 :     * This function takes O(N log N) time and O(N) space.
292 :     *-------------------------------------------------------------------------*)
293 :     fun needsSpilling (TYPE_INFO{maxLive, isVar, ...}) cpsFun =
294 :     let val (funKind, f, args, argTypes, body) = cpsFun : CPS.function
295 :     open SimpleSet
296 :     exception TooMany
297 :    
298 :     val bandwidth = ref 0
299 :    
300 :     (* Make sure |S| is not too large.
301 :     * Note: card is a O(1) operation.
302 :     *)
303 :     fun check S =
304 :     let val n = card S
305 :     in if n > !bandwidth then bandwidth := n else ();
306 :     if n >= maxLive then raise TooMany else S
307 :     end
308 :    
309 :     (* This function inserts lvars of the current type into set S *)
310 :     fun uses(vs,S) =
311 :     let fun f((CPS.VAR x)::vs,S) =
312 :     f(vs, if isVar x then Set.add(S,x) else S)
313 :     | f(_::vs,S) = f(vs,S)
314 :     | f([],S) = check S
315 :     in f(vs,S)
316 :     end
317 :    
318 :     (* Remove w (a definition) from S. *)
319 :     fun def(w,S) = rmv(S,w)
320 :    
321 :     (* Union a list of sets S_1, ..., S_n
322 :     * Runs in O(m \log m) time and space
323 :     * where m = \sum_{i=1\ldots n} |S_i|
324 :     *)
325 :     val unions = List.foldr op\/ O
326 :    
327 :     (*
328 :     * Compute the set of free vars at each program point.
329 :     * Raise exception TooMany if the live set exceeds maxLive.
330 :     * This phase runs in total O(N log N) time and O(N) space.
331 :     *)
332 :     fun freevars e =
333 :     case e of
334 :     CPS.APP(v,args) => uses(v::args,O)
335 :     | CPS.SWITCH(v,c,l) => uses([v],unions(map freevars l))
336 :     | CPS.SELECT(_,v,w,t,e) => uses([v],def(w,freevars e))
337 :     | CPS.RECORD(_,l,w,e) => uses((map #1 l),def(w,freevars e))
338 :     | CPS.OFFSET(_,v,w,e) => uses([v],def(w,freevars e))
339 :     | CPS.SETTER(_,vl,e) => uses(vl,freevars e)
340 :     | CPS.LOOKER(_,vl,w,t,e) => uses(vl,def(w,freevars e))
341 :     | CPS.ARITH(_,vl,w,t,e) => uses(vl,def(w,freevars e))
342 :     | CPS.PURE(_,vl,w,t,e) => uses(vl,def(w,freevars e))
343 :     | CPS.RCC(_,vl,w,t,e) => uses(vl,def(w,freevars e))
344 :     | CPS.BRANCH(_,vl,c,e1,e2) => uses(vl,freevars e1 \/ freevars e2)
345 :     | CPS.FIX _ => error "FIX in Spill.freevars"
346 :    
347 :     val needsSpilling = (freevars body; false) handle TooMany => true
348 :     in {needsSpilling = needsSpilling,
349 :     bandwidth = !bandwidth
350 :     }
351 :     end (* needsSpilling *)
352 :    
353 :     (*--------------------------------------------------------------------------
354 :     * linearScan
355 :     * ==========
356 :     *
357 :     * Perform the actual spilling.
358 :     *
359 :     * The algorithm is derived from linear-scan RA algorithms.
360 :     * But since we are dealing with trees, (and because of immutable
361 :     * data structures), we'll do this in multiple passes rather than
362 :     * a single pass.
363 :     *
364 :     * What spilling means in CPS is transforming:
365 :     *
366 :     *
367 :     * v <- f(...) /* definition */
368 :     * ....
369 :     * ... <- g(... v ...) /* use */
370 :     *
371 :     * into:
372 :     *
373 :     * spilled <- rawrecord NONE m /* create an uninitialized spill record
374 :     * of length m */
375 :     * ....
376 :     * v <- f(...) /* definition */
377 :     * rawupdate(spilled, v_offset, v)
378 :     * ...
379 :     * ... <- g(... SELp(spilled,v_offset) ...) /* reload */
380 :     *
381 :     * Important notes:
382 :     * 1. The spill record is never live beyond the
383 :     * cps function, so we never even have to assign its
384 :     * record tag.
385 :     *
386 :     * 2. We spill all tagged/untagged values into a spill record,
387 :     * without segregating them by their types, so we are mixing
388 :     * 32-bit integers, 31-bit tagged ints, and pointers together.
389 :     * This is safe because of (1).
390 :     *
391 :     * This function takes a total of O(N log N) time and O(N) space.
392 :     *-------------------------------------------------------------------------*)
393 :     fun linearScan (TYPE_INFO{maxLive, isVar, itemSize, ...}) cpsFun =
394 :     let val (funKind, f, args, argTypes, body) = cpsFun : CPS.function
395 :     open RankedSet
396 :    
397 :     val () = dump("before", cpsFun)
398 :    
399 :     (* Information about each lvar *)
400 :     datatype lvar_info =
401 :     LVAR_INFO of
402 :     { useCount :int ref, (* number of uses in this function *)
403 :     defPoint :int, (* level of definition *)
404 :     defBlock :int, (* block of definition *)
405 :     cty :CPS.cty,
406 :     nearestUse :int ref (* min {level(x) | x in uses(v)} *)
407 :     }
408 :     exception LvarInfo
409 :    
410 :     val () = if !debug_cps_spill_info
411 :     then pr "CPS Spill: linearScan\n" else ()
412 :    
413 :     val lvarInfo = H.mkTable(32,LvarInfo)
414 :     val lookupLvar = H.lookup lvarInfo
415 :    
416 :     fun spillCand v =
417 :     let val LVAR_INFO{nearestUse, useCount, defPoint, cty, ...} = lookupLvar v
418 :     val dist = !nearestUse - defPoint
419 :     val rank = dist (* for now *)
420 :     in SPILL_CANDIDATE{lvar=v, cty=cty, rank=rank}
421 :     end
422 :    
423 :     (*----------------------------------------------------------------------
424 :     * Gather information about each lvar
425 :     * We partition the cps function into blocks.
426 :     * A block is a continuous group of statements without
427 :     * controlflow or store updates.
428 :     * This phase runs in O(N) time and space.
429 :     *---------------------------------------------------------------------*)
430 :     local
431 :     val infinity = 10000000
432 :     val enterLvar = H.insert lvarInfo
433 :     fun def(v,t,b,n) =
434 :     enterLvar(v, LVAR_INFO{useCount=ref 0,
435 :     defPoint=n,
436 :     defBlock=b,
437 :     cty=t,
438 :     nearestUse=ref infinity
439 :     }
440 :     )
441 :    
442 :     fun use(CPS.VAR v, n) =
443 :     if isVar v then
444 :     let val LVAR_INFO{useCount, nearestUse, ...} = lookupLvar v
445 :     in useCount := !useCount + 1;
446 :     nearestUse := Int.min(!nearestUse, n)
447 :     end
448 :     else ()
449 :     | use _ = ()
450 :     fun uses([], n) = ()
451 :     | uses(v::vs, n) = (use(v, n); uses(vs, n))
452 :    
453 :     fun gather(e, b, n) =
454 :     let fun gathers([], b, n) = ()
455 :     | gathers(e::es,b,n) = (gather(e,b,n); gathers(es,b,n))
456 :     fun f0(vl, e) = (uses(vl, n); gather(e, b+1, n+1))
457 :     fun f1(v, w, t, e) = (use(v, n); def(w,t,b,n); gather(e,b,n+1))
458 :     fun fx(vl,w,t,e,b) = (uses(vl, n); def(w,t,b,n); gather(e,b,n+1))
459 :     in case e of
460 :     CPS.APP(v,args) => uses(v::args, n)
461 :     | CPS.SWITCH(v,c,l) => (use(v, n); gathers(l, b+1, n+1))
462 :     | CPS.SELECT(_,v,w,t,e) => f1(v, w, t, e)
463 :     | CPS.OFFSET(_,v,w,e) => f1(v, w, CPS.BOGt, e)
464 :     | CPS.RECORD(_,l,w,e) => fx(map #1 l, w, CPS.BOGt, e, b)
465 :     | CPS.SETTER(_,vl,e) => f0(vl, e)
466 :     | CPS.LOOKER(_,vl,w,t,e) => fx(vl, w, t, e, b)
467 :     | CPS.ARITH(_,vl,w,t,e) => fx(vl, w, t, e, b)
468 :     | CPS.PURE(_,vl,w,t,e) => fx(vl, w, t, e, b)
469 :     | CPS.RCC(_,vl,w,t,e) => fx(vl, w, t, e, b+1)
470 :     | CPS.BRANCH(_,vl,c,x,y) => (uses(vl, n); gathers([x,y],b+1,n+1))
471 :     | CPS.FIX _ => error "FIX in Spill.gather"
472 :     end
473 :     in (* Always remember to define the arguments! *)
474 :     val () = ListPair.app (fn (v, t) => def(v, t, 0, 0)) (args, argTypes)
475 :     val () = gather(body, 1, 1)
476 :     end (* gather *)
477 :    
478 :     val () = if !debug_cps_spill then pr "CPS Spill: gather done\n" else ()
479 :    
480 :     (*-----------------------------------------------------------------
481 :     *
482 :     * Spill tables and utilities
483 :     *
484 :     *-----------------------------------------------------------------*)
485 :    
486 :     exception SpillTable
487 :     val spillTable = H.mkTable(32, SpillTable) :
488 :     (CPS.value * int * CPS.cty) H.hash_table
489 :     (* lvar -> spillRecord * spill offset * cty *)
490 :     val enterSpill = H.insert spillTable
491 :     val findSpill = H.find spillTable
492 :     val isSpilled = H.inDomain spillTable
493 :     val currentSpillRecord = ref (NONE : (CPS.lvar * CPS.value) option)
494 :    
495 :     (*
496 :     * Generate a new spill record variable
497 :     *)
498 :     fun genSpillRec() =
499 :     case !currentSpillRecord of
500 :     SOME x => x
501 :     | NONE =>
502 :     let val v = LV.namedLvar (Symbol.varSymbol "spillrec")
503 :     val e = CPS.VAR v
504 :     in currentSpillRecord := SOME(v,e); (v, e)
505 :     end
506 :    
507 :     (*
508 :     * This function finds up to m good spill candidates from the live set
509 :     *)
510 :     fun findGoodSpills(0, L, spOff) = (L, spOff)
511 :     | findGoodSpills(m, L, spOff) =
512 :     case next L of
513 :     (* no more spill candidates! *)
514 :     NONE => (L, spOff)
515 :     | SOME(SPILL_CANDIDATE{lvar, cty, rank, ...}, L) =>
516 :     let val offset = spOff (* should align when we have 64-bit values *)
517 :     val (_,spRecExp) = genSpillRec()
518 :     val () = enterSpill(lvar,(spRecExp,offset,cty))
519 :     fun inc(spOff,cty) = spOff + 1 (* should look at cty
520 :     * when we have 64-bit values
521 :     *)
522 :     in (* okay; it's actually live and hasn't been spilled! *)
523 :     if !debug_cps_spill then
524 :     pr("Spilling "^LV.lvarName lvar^" rank="^i2s rank^"\n")
525 :     else ();
526 :     findGoodSpills(m-1, L, inc(spOff, cty))
527 :     end
528 :    
529 :     (*
530 :     * Can and should the record be split?
531 :     * Split if,
532 :     * 1. we can handle the record type
533 :     * 2. if it has >= MAX_RECORD_LEN live lvars as arguments
534 :     * 3. All its arguments are defined in the same block as the record.
535 :     *)
536 :     fun shouldSplitRecord(rk,vl,b) =
537 :     SPLIT_LARGE_RECORDS andalso
538 :     let fun okPath(CPS.SELp(i,p)) = okPath p
539 :     | okPath(CPS.OFFp 0) = true
540 :     | okPath _ = false
541 :     fun f([], n) = n >= MAX_RECORD_LEN
542 :     | f((CPS.VAR v,p)::vl, n) =
543 :     let val LVAR_INFO{defBlock, ...} = lookupLvar v
544 :     in defBlock = b andalso okPath p andalso
545 :     (if isVar v andalso not(isSpilled v)
546 :     then f(vl, n+1)
547 :     else f(vl, n)
548 :     )
549 :     end
550 :     | f((_,CPS.OFFp 0)::vl, n) = f(vl, n)
551 :     | f _ = false
552 :     in splittable rk andalso f(vl, 0)
553 :     end
554 :    
555 :     (*
556 :     * Tables for splitting a record
557 :     *)
558 :     exception RecordTable
559 :     datatype split_record_item =
560 :     SPLIT_RECORD_ITEM of
561 :     { record : CPS.lvar,
562 :     kind : CPS.record_kind,
563 :     len : int,
564 :     offset : int,
565 :     path : CPS.accesspath,
566 :     numVars : int ref,
567 :     consts : (int * CPS.value) list
568 :     }
569 :    
570 :     val recordAllocTable = H.mkTable(16, RecordTable)
571 :     val enterRecordItem = H.insert recordAllocTable
572 :     val findRecordItem = H.find recordAllocTable
573 :     val splitRecordTable = H.mkTable(16, RecordTable)
574 :     val markSplitRecord = H.insert splitRecordTable
575 :     fun insertRecordItem(v, x) =
576 :     enterRecordItem(v, x::getOpt(findRecordItem v,[]))
577 :    
578 :     (*
579 :     * Mark record w as being split.
580 :     * Enter the appropriate info to all its arguments.
581 :     *)
582 :     fun splitRecordConstruction(rk, vl, w) =
583 :     let fun f(i, (CPS.VAR v,offp)::vl, vars, consts) =
584 :     f(i+1, vl, (i,v,offp)::vars, consts)
585 :     | f(i, (c,CPS.OFFp 0)::vl, vars, consts) =
586 :     f(i+1, vl, vars, (i,c)::consts)
587 :     | f(_, [], vars, consts) = (vars, consts)
588 :     | f _ = error "CPS Spill.splitRecordConstruction"
589 :     val (vars, consts) = f(0, vl, [], [])
590 :     val n = length vars
591 :     val _ = if n = 0 then
592 :     error "CPS Spill: splitting constant record" else ()
593 :     val _ = if !debug_cps_spill_info then
594 :     pr("Splitting record "^LV.lvarName w^" len="^i2s n^"\n")
595 :     else ()
596 :     val len = length vl
597 :     val numVars = ref n
598 :     fun enter(i, v, path) =
599 :     let val item = SPLIT_RECORD_ITEM
600 :     { record = w,
601 :     kind = rk,
602 :     len = len,
603 :     offset = i,
604 :     path = path,
605 :     numVars = numVars,
606 :     consts = consts
607 :     }
608 :     in insertRecordItem(v, item)
609 :     end
610 :     in app enter vars;
611 :     markSplitRecord(w,true)
612 :     end
613 :    
614 :     (*-----------------------------------------------------------------
615 :     * Linear scan spilling.
616 :     * This function marks all spill/reload sites.
617 :     *
618 :     * Parameters:
619 :     * e --- cps expression
620 :     * b --- current block
621 :     * spOff --- current available spill offset
622 :     *
623 :     * Return:
624 :     * e --- transformed cps expression
625 :     * L --- the set of live lvars in e
626 :     * spills --- the number of spills
627 :     *
628 :     * This phase takes O(N log N) time and O(N) space
629 :     *-----------------------------------------------------------------*)
630 :     fun scan(e, b, spOff) =
631 :     let
632 :     (* add uses to live set *)
633 :     fun addUses([], L) = L
634 :     | addUses(CPS.VAR v::vs, L) =
635 :     addUses(vs, if isVar v andalso not(isSpilled v) then
636 :     Set.add(L, spillCand v) else L)
637 :    
638 :     | addUses(_::vs, L) = addUses(vs, L)
639 :    
640 :     (* This function kills a definition *)
641 :     fun kill(w, L) = if isVar w then rmv(L, spillCand w) else L
642 :    
643 :     (* This function find things to spill *)
644 :     fun genSpills(L, spOff) =
645 :     let val toSpills = card L - maxLive
646 :     in if toSpills > 0 then findGoodSpills(toSpills, L, spOff)
647 :     else (L, spOff)
648 :     end
649 :    
650 :     (* This function visits a list of continuations and
651 :     * gathers up the info
652 :     *)
653 :     fun scanList es =
654 :     let val b = b + 1
655 :     fun f [] = (O, 0)
656 :     | f [e] = scan(e, b, spOff)
657 :     | f(e::es) =
658 :     let val (L1, spOff1) = scan(e, b, spOff)
659 :     val (L2, spOff2) = f es
660 :     in (L1 \/ L2, Int.max(spOff1, spOff2))
661 :     end
662 :     in f es end
663 :    
664 :     (* This function scans normal cps operators
665 :     * with one definition and one continuation
666 :     *
667 :     * w : t <- f vs; e
668 :     *)
669 :     fun scanOp(vs, w, e, b) =
670 :     let val (L,spOff) = scan(e,b,spOff) (* do continuation *)
671 :     val L = kill(w, L) (* remove definition *)
672 :     val L = addUses(vs, L) (* add uses *)
673 :     val (L,spOff) = genSpills(L, spOff) (* find spill *)
674 :     in (L, spOff)
675 :     end
676 :    
677 :     (* This function scans stmts with multiple continuations *)
678 :     fun scanStmt(vs, es) =
679 :     let val (L,spOff) = scanList es (* do continuation *)
680 :     val L = addUses(vs, L) (* add uses *)
681 :     val (L, spOff) = genSpills(L,spOff) (* find spills *)
682 :     in (L, spOff)
683 :     end
684 :    
685 :     (* This function scans record constructors *)
686 :     fun scanRec(rk, vl, w, e) =
687 :     let val (L,spOff) = scan(e,b,spOff) (* do continuation *)
688 :     val (L, spOff) =
689 :     if shouldSplitRecord(rk, vl, b) then
690 :     (splitRecordConstruction(rk, vl, w); (L,spOff))
691 :     else
692 :     let val L = kill(w, L)
693 :     val L = addUses(map #1 vl, L)
694 :     in genSpills(L, spOff)
695 :     end
696 :     in (L, spOff)
697 :     end
698 :    
699 :     val (L, numSpills) =
700 :     case e of
701 :     CPS.APP(v,args) => scanStmt(v::args, [])
702 :     | CPS.SWITCH(v,c,es) => scanStmt([v], es)
703 :     | CPS.SELECT(i,v,w,t,e) => scanOp([v], w, e, b)
704 :     | CPS.OFFSET(i,v,w,e) => scanOp([v], w, e, b)
705 :     | CPS.RECORD(rk,l,w,e) => scanRec(rk, l, w, e)
706 :     | CPS.SETTER(p,vl,e) => scanStmt(vl,[e])
707 :     | CPS.LOOKER(p,vl,w,t,e) => scanOp(vl, w, e, b)
708 :     | CPS.ARITH(p,vl,w,t,e) => scanOp(vl, w, e, b)
709 :     | CPS.PURE(p,vl,w,t,e) => scanOp(vl, w, e, b)
710 :     | CPS.RCC(p,vl,w,t,e) => scanOp(vl, w, e, b+1)
711 :     | CPS.BRANCH(p,vl,c,x,y) => scanStmt(vl,[x,y])
712 :     | CPS.FIX _ => error "FIX in Spill.scan"
713 :    
714 :     in (L, numSpills)
715 :     end
716 :    
717 :     (* Scan the body *)
718 :     val (L, numSpills) = scan(body, 1, 0)
719 :    
720 :     val () = if !debug_cps_spill then
721 :     pr("CPS Spill: scan done. Spilling "^i2s numSpills^"\n")
722 :     else ()
723 :     (*
724 :     * Generate reloads for a list of arguments.
725 :     * Returns:
726 :     * the rewritten list of arguments
727 :     * a function for inserting selects.
728 :     *)
729 :     fun emitReloads vs =
730 :     let fun g([], vs', f) = (rev vs', f)
731 :     | g((v as CPS.VAR x)::vs, vs', f) =
732 :     (case findSpill x of
733 :     NONE => g(vs, v::vs', f)
734 :     | SOME(spillRec, off, cty) =>
735 :     let val x' = LV.dupLvar x
736 :     val v' = CPS.VAR x'
737 :     fun f' e = CPS.SELECT(off,spillRec,x',cty, f e)
738 :     in g(vs, v'::vs', f')
739 :     end
740 :     )
741 :     | g(v::vs, vs', f) = g(vs, v::vs', f)
742 :     in g(vs, [], fn e => e)
743 :     end
744 :    
745 :     (*
746 :     * Generate reloads for record paths
747 :     * Returns:
748 :     * the rewritten list of record paths
749 :     *)
750 :     fun emitPathReloads vl =
751 :     let fun f([], vl') = rev vl'
752 :     | f((v as CPS.VAR x, p)::vl, vl') =
753 :     (case findSpill x of
754 :     NONE => f(vl, (v, p)::vl')
755 :     | SOME(spillRec, off, cty) =>
756 :     f(vl, (spillRec,CPS.SELp(off,p))::vl')
757 :     )
758 :     | f(v::vl, vl') = f(vl, v::vl')
759 :     in f(vl, [])
760 :     end
761 :    
762 :     (* This function generate spill code for variable w *)
763 :     fun emitSpill(w, e) =
764 :     case findSpill w of
765 :     NONE => e
766 :     | SOME(spillRecord, off, cty) =>
767 :     CPS.SETTER(P.rawupdate cty,
768 :     [spillRecord, CPS.INT off,CPS.VAR w], e)
769 :    
770 :     (*
771 :     * Emit spill record code
772 :     *)
773 :     fun createSpillRecord(0, e) = e
774 :     | createSpillRecord(numSpills, e) =
775 :     let val (spillRecLvar,_) = genSpillRec()
776 :     val m = numSpills * itemSize
777 :     val e = CPS.PURE(P.rawrecord NONE,[CPS.INT m],
778 :     spillRecLvar,CPS.BOGt,e)
779 :     in currentSpillRecord := NONE; (* clear *)
780 :     e
781 :     end
782 :    
783 :     val recordIsSplit = H.inDomain splitRecordTable
784 :     val findSplitRecordArg = H.find recordAllocTable
785 :    
786 :     (*
787 :     * proj(v, path, e) ==> w <- v.path ; e[w/v]
788 :     *)
789 :     fun proj(v, CPS.OFFp 0, e) = e v
790 :     | proj(v, CPS.SELp(i,p), e) =
791 :     let val v' = LV.mkLvar()
792 :     val e = e v'
793 :     in CPS.SELECT(i, CPS.VAR v, v', CPS.BOGt, e)
794 :     end
795 :    
796 :     (*
797 :     * generate
798 :     * record.offset <- v.path ; e
799 :     *)
800 :     fun initRecordItem(record, rk, offset, v, path, e) =
801 :     proj(v, path,
802 :     fn x => CPS.SETTER(P.rawupdate(rkToCty rk),
803 :     [CPS.VAR record, CPS.INT offset, CPS.VAR x], e))
804 :    
805 :     (*
806 :     * Generate code to create a record.
807 :     *)
808 :     fun createRecord(record, rk, len, consts, e) =
809 :     let val e = emitSpill(record, e)
810 :     val p = P.rawupdate(rkToCty rk)
811 :     fun init((i, c),e) = CPS.SETTER(p,[CPS.VAR record, CPS.INT i, c], e)
812 :     val e = foldr init e consts
813 :     val e = CPS.PURE(P.rawrecord(SOME rk),[CPS.INT len],record,CPS.BOGt,e)
814 :     in e
815 :     end
816 :    
817 :     (*
818 :     * It is the definition of lvar v.
819 :     * Check to see if v is some component of split records.
820 :     * If so, generate code.
821 :     *
822 :     *)
823 :     fun assignToSplitRecord(v, e) =
824 :     case findSplitRecordArg v of
825 :     SOME inits =>
826 :     let fun gen(SPLIT_RECORD_ITEM
827 :     {record, kind, len, offset,
828 :     path, numVars, consts,...}, e) =
829 :     let val e = initRecordItem(record, kind, offset, v, path, e)
830 :     val n = !numVars - 1
831 :     in numVars := n;
832 :     if n = 0 then createRecord(record, kind, len, consts, e)
833 :     else e
834 :     end
835 :     in foldr gen e inits
836 :     end
837 :     | NONE => e
838 :    
839 :     (*-----------------------------------------------------------------
840 :     * Rebuild
841 :     *
842 :     * This function rewrites the cps expression and insert spill/reload
843 :     * code.
844 :     *
845 :     * This phase takes O(N) time and O(N) space
846 :     *-----------------------------------------------------------------*)
847 :    
848 :     fun rebuild e =
849 :     let
850 :    
851 :     fun rewriteStmt(vs, es, f) =
852 :     let val es = map rebuild es
853 :     val (vs, g) = emitReloads vs
854 :     in g(f(vs, es)) end
855 :    
856 :     fun rewrite(vs, w, e, f) =
857 :     let val e = rebuild e
858 :     val e = emitSpill(w, e)
859 :     val e = assignToSplitRecord(w, e)
860 :     val (vs, g) = emitReloads vs
861 :     in g(f(vs, w, e))
862 :     end
863 :    
864 :     fun rewriteRec(vl, w, e, f) =
865 :     let val e = rebuild e
866 :     val e = emitSpill(w, e)
867 :     val e = assignToSplitRecord(w, e)
868 :     in if recordIsSplit w then e
869 :     else f(emitPathReloads vl, w, e)
870 :     end
871 :    
872 :     (*
873 :     * Rewrite the expression
874 :     *)
875 :     val e =
876 :     case e of
877 :     CPS.APP(v,args) =>
878 :     rewriteStmt(v::args, [], fn (v::args,_) => CPS.APP(v,args))
879 :     | CPS.SWITCH(v,c,es) =>
880 :     rewriteStmt([v], es, fn ([v], es) => CPS.SWITCH(v, c, es))
881 :     | CPS.SELECT(i,v,w,t,e) =>
882 :     rewrite([v], w, e, fn ([v],w,e) => CPS.SELECT(i,v,w,t,e))
883 :     | CPS.OFFSET(i,v,w,e) =>
884 :     rewrite([v], w, e, fn ([v],w,e) => CPS.OFFSET(i,v,w,e))
885 :     | CPS.RECORD(k,l,w,e) =>
886 :     rewriteRec(l,w,e,fn (l,w,e) => CPS.RECORD(k, l, w, e))
887 :     | CPS.SETTER(p,vl,e) =>
888 :     rewriteStmt(vl,[e],fn (vl,[e]) => CPS.SETTER(p,vl,e))
889 :     | CPS.LOOKER(p,vl,w,t,e) =>
890 :     rewrite(vl,w,e, fn (vl,w,e) => CPS.LOOKER(p,vl,w,t,e))
891 :     | CPS.ARITH(p,vl,w,t,e) =>
892 :     rewrite(vl,w,e, fn (vl,w,e) => CPS.ARITH(p,vl,w,t,e))
893 :     | CPS.PURE(p,vl,w,t,e) =>
894 :     rewrite(vl,w,e,fn (vl,w,e) => CPS.PURE(p,vl,w,t,e))
895 :     | CPS.RCC(p,vl,w,t,e) =>
896 :     rewrite(vl,w,e,fn (vl,w,e) => CPS.RCC(p,vl,w,t,e))
897 :     | CPS.BRANCH(p,vl,c,x,y) =>
898 :     rewriteStmt(vl,[x,y], fn (vl,[x,y]) => CPS.BRANCH(p,vl,c,x,y))
899 :     | CPS.FIX _ => error "FIX in Spill.rebuild"
900 :    
901 :     in e
902 :     end (* rebuild *)
903 :    
904 :     (* insert spill/reload code *)
905 :     val body = rebuild body
906 :     val body = foldr emitSpill body args (* spill code for arguments *)
907 :     (*
908 :     * Insert spill record creation code.
909 :     *)
910 :     val body = createSpillRecord(numSpills, body)
911 :    
912 :     val () = if !debug_cps_spill_info
913 :     then pr("CPS Spill: linearScan done "^i2s numSpills^" spilled\n")
914 :     else ()
915 :    
916 :     val cpsFun = (funKind, f, args, argTypes, body)
917 :    
918 :     val () = dump("after", cpsFun)
919 :    
920 :     in cpsFun
921 :     end (* linearScan *)
922 :    
923 :     (*-------------------------------------------------------------------------
924 :     * spillOne
925 :     * ========
926 :     *
927 :     * This is the driver to process only one CPS function.
928 :     *
929 :     * This routine takes a total of O(N log N) time and O(N) space
930 :     *
931 :     *-------------------------------------------------------------------------*)
932 :     fun spillOne cpsFun =
933 :     let
934 :     (*
935 :     * Perform spilling.
936 :     *)
937 :    
938 :     fun spillIt type_info cpsFun =
939 :     let val {needsSpilling, bandwidth, ...} = needsSpilling type_info cpsFun
940 :     val () = if !debug_cps_spill_info then
941 :     pr("CPS Spill bandwidth="^i2s bandwidth^"\n")
942 :     else ()
943 :     in if needsSpilling then linearScan type_info cpsFun
944 :     else cpsFun
945 :     end
946 :     (*
947 :     * If we have unboxed floats then we have to distinguish between
948 :     * fpr and gpr registers.
949 :     *)
950 :    
951 :     val (fpTable,recordTable) = markFpAndRec cpsFun (* collect fp type info *)
952 :    
953 :     val isMoveableRec = H.inDomain recordTable
954 :    
955 :     val cpsFun =
956 :     if MachSpec.unboxedFloats then
957 :     let val isFP = H.inDomain fpTable
958 :     fun isGP r = not(isFP r) andalso not(isMoveableRec r)
959 :     val fp = TYPE_INFO{isVar=isFP, maxLive=maxfpfree, itemSize=2}
960 :     val gp = TYPE_INFO{isVar=isGP, maxLive=maxgpfree, itemSize=1}
961 :     val cpsFun = spillIt fp cpsFun (* do fp spills first *)
962 :     val cpsFun = spillIt gp cpsFun (* do gp spills *)
963 :     in cpsFun
964 :     end
965 :     else
966 :     let fun isGP r = not(isMoveableRec r)
967 :     in spillIt (TYPE_INFO{isVar=isGP, maxLive=maxgpfree, itemSize=1})
968 :     cpsFun
969 :     end
970 :     in cpsFun
971 :     end (* spillOne *)
972 :    
973 :    
974 :     (* Main entry point *)
975 :     val spill = map spillOne
976 :    
977 :     end (* SpillFn *)
978 :    
979 :     end (* local *)

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