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 5015 - (view) (download)

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

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