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 4960 - (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 4454 fun rkToCty (CPS.RK_FCONT | CPS.RK_FBLOCK) = CPS.FLTt 64 (* REAL32: FIXME *)
197 : jhr 4953 | rkToCty _ = U.BOGt
198 : leunga 1094
199 :     fun splittable CPS.RK_VECTOR = false (* not supported in backend (yet) *)
200 :     | splittable _ = true
201 :    
202 : jhr 4560 (* tagged integers *)
203 :     fun tagInt n = CPS.NUM{
204 :     ival = IntInf.fromInt n,
205 :     ty = {tag = true, sz = Target.defaultIntSz}
206 :     }
207 :    
208 : leunga 1094 (*-------------------------------------------------------------------------
209 :     *
210 :     * All CPS functions can be independently processed.
211 :     *
212 : jhr 4454 * Some complexity assumptions:
213 : leunga 1094 * Hashing is O(1)
214 :     * N = max{number of lvars, size of cps function}
215 :     *
216 :     *-------------------------------------------------------------------------*)
217 :    
218 :     (*------------------------------------------------------------------------
219 :     * markFpAndRec
220 :     * =============
221 :     * Mark all floating point variables and return a hash table
222 : jhr 4454 *
223 : leunga 1094 * This is needed because we do spilling of integer and floating
224 :     * point stuff separately.
225 :     *
226 :     * This function takes O(N) time and space
227 :     *-----------------------------------------------------------------------*)
228 : jhr 4454 fun markFpAndRec cpsFun =
229 : leunga 1094 let val (funKind, f, args, argTypes, body) = cpsFun : CPS.function
230 :     open SimpleSet
231 :     exception FloatSet
232 :     val floatSet = H.mkTable(32,FloatSet)
233 :     val addToFloatSet = H.insert floatSet
234 : jhr 4454 fun fp(r, CPS.FLTt _) = addToFloatSet(r,true)
235 :     | fp(r ,_) = ()
236 : leunga 1094 exception RecordSet
237 :     val recordSet = H.mkTable(32,RecordSet)
238 :     val markrec = H.insert recordSet
239 :     val findrec = H.find recordSet
240 :    
241 :     (* Mark all record uses *)
242 : jhr 4454 val recUses =
243 :     app (fn (CPS.VAR v,_) =>
244 : leunga 1094 (case findrec v of
245 :     NONE => () (* not a record address *)
246 : jhr 4454 | SOME n => markrec(v, n+1)
247 : leunga 1094 )
248 :     | _ => ()
249 : jhr 4454 )
250 : leunga 1094
251 : jhr 4842 fun markPure (p, w) = (case p
252 : jhr 4676 (* these pure operators actually allocate storage! *)
253 : jhr 4960 of P.WRAP(P.INT sz) => if (sz <= Target.defaultIntSz) then () else markrec(w, 0)
254 :     | (P.WRAP(P.FLOAT _) | P.NEWARRAY0 | P.MAKEREF | P.MKSPECIAL | P.RAWRECORD _) =>
255 : jhr 4842 markrec(w, 0)
256 :     | _ => ()
257 :     (* end case *))
258 : leunga 1094
259 : jhr 4960 fun markfp e = (case e
260 :     of CPS.APP _ => ()
261 :     | CPS.SWITCH(_,_,es) => app markfp es
262 :     | CPS.SELECT(_,_,w,t,e) => (fp(w,t); markfp e)
263 :     | CPS.RECORD(_,vl,w,e) => (recUses vl; markrec(w, 0); markfp e)
264 :     | CPS.OFFSET(_,_,_,e) => markfp e
265 :     | CPS.SETTER(_,_,e) => markfp e
266 :     | CPS.LOOKER(_,_,w,t,e) => (fp(w,t); markfp e)
267 :     | CPS.ARITH(_,_,w,t,e) => (fp(w,t); markfp e)
268 :     | CPS.PURE(p,_,w,t,e) => (markPure(p,w); fp(w,t); markfp e)
269 :     | CPS.RCC(_,_,_,_,wtl,e) => (app fp wtl; markfp e)
270 :     | CPS.BRANCH(_,_,_,e1,e2) => (markfp e1; markfp e2)
271 :     | CPS.FIX _ => error "FIX in Spill.markfp"
272 :     (* end case *))
273 : leunga 1094
274 :     val () = ListPair.app fp (args, argTypes) (* mark function parameters *)
275 :     val () = markfp body (* mark function body *)
276 :    
277 :     (* Filter out multiple uses of record values because these
278 :     * are not forward propagated by the backend.
279 :     *)
280 :     val () = if DEBUG then
281 :     H.appi (fn (v, n) =>
282 :     if n >= 2 then pr(LV.lvarName v^" uses="^i2s n^"\n") else ())
283 :     recordSet
284 :     else ()
285 :     val () = H.filter (fn n => n <= 1) recordSet
286 :     in (floatSet, recordSet)
287 :     end
288 :    
289 :     (*--------------------------------------------------------------------------
290 :     * needsSpilling
291 :     * =============
292 : jhr 4454 * This function checks whether we need to perform spilling for
293 :     * the current type, which is either gpr or fpr.
294 : leunga 1094 * Parameterized by type info. This is supposed to be a cheap check
295 :     * since most of the time this function should return false,
296 :     * so no information is saved.
297 :     *
298 :     * This function takes O(N log N) time and O(N) space.
299 :     *-------------------------------------------------------------------------*)
300 : jhr 4454 fun needsSpilling (TYPE_INFO{maxLive, isVar, ...}) cpsFun =
301 : leunga 1094 let val (funKind, f, args, argTypes, body) = cpsFun : CPS.function
302 :     open SimpleSet
303 :     exception TooMany
304 :    
305 :     val bandwidth = ref 0
306 :    
307 : jhr 4454 (* Make sure |S| is not too large.
308 : leunga 1094 * Note: card is a O(1) operation.
309 :     *)
310 : jhr 4454 fun check S =
311 :     let val n = card S
312 : leunga 1094 in if n > !bandwidth then bandwidth := n else ();
313 :     if n >= maxLive then raise TooMany else S
314 :     end
315 :    
316 :     (* This function inserts lvars of the current type into set S *)
317 : jhr 4454 fun uses(vs,S) =
318 :     let fun f((CPS.VAR x)::vs,S) =
319 : leunga 1094 f(vs, if isVar x then Set.add(S,x) else S)
320 :     | f(_::vs,S) = f(vs,S)
321 :     | f([],S) = check S
322 :     in f(vs,S)
323 :     end
324 :    
325 :     (* Remove w (a definition) from S. *)
326 :     fun def(w,S) = rmv(S,w)
327 :    
328 : jhr 4454 (* Union a list of sets S_1, ..., S_n
329 :     * Runs in O(m \log m) time and space
330 : leunga 1094 * where m = \sum_{i=1\ldots n} |S_i|
331 :     *)
332 :     val unions = List.foldr op\/ O
333 :    
334 :     (*
335 :     * Compute the set of free vars at each program point.
336 :     * Raise exception TooMany if the live set exceeds maxLive.
337 :     * This phase runs in total O(N log N) time and O(N) space.
338 :     *)
339 :     fun freevars e =
340 :     case e of
341 :     CPS.APP(v,args) => uses(v::args,O)
342 :     | CPS.SWITCH(v,c,l) => uses([v],unions(map freevars l))
343 :     | CPS.SELECT(_,v,w,t,e) => uses([v],def(w,freevars e))
344 :     | CPS.RECORD(_,l,w,e) => uses((map #1 l),def(w,freevars e))
345 :     | CPS.OFFSET(_,v,w,e) => uses([v],def(w,freevars e))
346 :     | CPS.SETTER(_,vl,e) => uses(vl,freevars e)
347 :     | CPS.LOOKER(_,vl,w,t,e) => uses(vl,def(w,freevars e))
348 :     | CPS.ARITH(_,vl,w,t,e) => uses(vl,def(w,freevars e))
349 :     | CPS.PURE(_,vl,w,t,e) => uses(vl,def(w,freevars e))
350 : mblume 1755 | CPS.RCC(_,_,_,vl,wtl,e) => uses(vl, foldl (fn((w,_),s) => def(w,s))
351 :     (freevars e) wtl)
352 : leunga 1094 | CPS.BRANCH(_,vl,c,e1,e2) => uses(vl,freevars e1 \/ freevars e2)
353 :     | CPS.FIX _ => error "FIX in Spill.freevars"
354 :    
355 :     val needsSpilling = (freevars body; false) handle TooMany => true
356 :     in {needsSpilling = needsSpilling,
357 :     bandwidth = !bandwidth
358 :     }
359 :     end (* needsSpilling *)
360 :    
361 :     (*--------------------------------------------------------------------------
362 :     * linearScan
363 :     * ==========
364 :     *
365 :     * Perform the actual spilling.
366 :     *
367 : jhr 4454 * The algorithm is derived from linear-scan RA algorithms.
368 : leunga 1094 * But since we are dealing with trees, (and because of immutable
369 :     * data structures), we'll do this in multiple passes rather than
370 :     * a single pass.
371 :     *
372 :     * What spilling means in CPS is transforming:
373 :     *
374 : jhr 4454 *
375 : leunga 1094 * v <- f(...) /* definition */
376 :     * ....
377 :     * ... <- g(... v ...) /* use */
378 :     *
379 :     * into:
380 :     *
381 : jhr 4454 * spilled <- rawrecord NONE m /* create an uninitialized spill record
382 : leunga 1094 * of length m */
383 :     * ....
384 :     * v <- f(...) /* definition */
385 : jhr 4454 * rawupdate(spilled, v_offset, v)
386 : leunga 1094 * ...
387 :     * ... <- g(... SELp(spilled,v_offset) ...) /* reload */
388 :     *
389 :     * Important notes:
390 : jhr 4454 * 1. The spill record is never live beyond the
391 : leunga 1094 * cps function, so we never even have to assign its
392 : jhr 4454 * record tag.
393 : leunga 1094 *
394 :     * 2. We spill all tagged/untagged values into a spill record,
395 : jhr 4454 * without segregating them by their types, so we are mixing
396 :     * 32-bit integers, 31-bit tagged ints, and pointers together.
397 : leunga 1094 * This is safe because of (1).
398 :     *
399 : jhr 4454 * This function takes a total of O(N log N) time and O(N) space.
400 : leunga 1094 *-------------------------------------------------------------------------*)
401 : jhr 4454 fun linearScan (TYPE_INFO{maxLive, isVar, itemSize, ...}) cpsFun =
402 : leunga 1094 let val (funKind, f, args, argTypes, body) = cpsFun : CPS.function
403 :     open RankedSet
404 :    
405 :     val () = dump("before", cpsFun)
406 :    
407 :     (* Information about each lvar *)
408 : jhr 4454 datatype lvar_info =
409 :     LVAR_INFO of
410 : leunga 1094 { useCount :int ref, (* number of uses in this function *)
411 :     defPoint :int, (* level of definition *)
412 :     defBlock :int, (* block of definition *)
413 :     cty :CPS.cty,
414 :     nearestUse :int ref (* min {level(x) | x in uses(v)} *)
415 : jhr 4454 }
416 : leunga 1094 exception LvarInfo
417 :    
418 : blume 1126 val () = if !debug_cps_spill_info
419 : leunga 1094 then pr "CPS Spill: linearScan\n" else ()
420 :    
421 :     val lvarInfo = H.mkTable(32,LvarInfo)
422 :     val lookupLvar = H.lookup lvarInfo
423 :    
424 : jhr 4454 fun spillCand v =
425 : leunga 1094 let val LVAR_INFO{nearestUse, useCount, defPoint, cty, ...} = lookupLvar v
426 :     val dist = !nearestUse - defPoint
427 :     val rank = dist (* for now *)
428 :     in SPILL_CANDIDATE{lvar=v, cty=cty, rank=rank}
429 :     end
430 : jhr 4454
431 : leunga 1094 (*----------------------------------------------------------------------
432 :     * Gather information about each lvar
433 : jhr 4454 * We partition the cps function into blocks.
434 : leunga 1094 * A block is a continuous group of statements without
435 : jhr 4454 * controlflow or store updates.
436 : leunga 1094 * This phase runs in O(N) time and space.
437 :     *---------------------------------------------------------------------*)
438 : jhr 4454 local
439 : leunga 1094 val infinity = 10000000
440 :     val enterLvar = H.insert lvarInfo
441 : jhr 4454 fun def(v,t,b,n) =
442 :     enterLvar(v, LVAR_INFO{useCount=ref 0,
443 : leunga 1094 defPoint=n,
444 :     defBlock=b,
445 :     cty=t,
446 :     nearestUse=ref infinity
447 :     }
448 :     )
449 : jhr 4454
450 :     fun use(CPS.VAR v, n) =
451 : leunga 1094 if isVar v then
452 : jhr 4454 let val LVAR_INFO{useCount, nearestUse, ...} = lookupLvar v
453 : leunga 1094 in useCount := !useCount + 1;
454 :     nearestUse := Int.min(!nearestUse, n)
455 :     end
456 :     else ()
457 :     | use _ = ()
458 :     fun uses([], n) = ()
459 :     | uses(v::vs, n) = (use(v, n); uses(vs, n))
460 :    
461 :     fun gather(e, b, n) =
462 :     let fun gathers([], b, n) = ()
463 :     | gathers(e::es,b,n) = (gather(e,b,n); gathers(es,b,n))
464 :     fun f0(vl, e) = (uses(vl, n); gather(e, b+1, n+1))
465 :     fun f1(v, w, t, e) = (use(v, n); def(w,t,b,n); gather(e,b,n+1))
466 :     fun fx(vl,w,t,e,b) = (uses(vl, n); def(w,t,b,n); gather(e,b,n+1))
467 :     in case e of
468 :     CPS.APP(v,args) => uses(v::args, n)
469 :     | CPS.SWITCH(v,c,l) => (use(v, n); gathers(l, b+1, n+1))
470 :     | CPS.SELECT(_,v,w,t,e) => f1(v, w, t, e)
471 : jhr 4953 | CPS.OFFSET(_,v,w,e) => f1(v, w, U.BOGt, e)
472 :     | CPS.RECORD(_,l,w,e) => fx(map #1 l, w, U.BOGt, e, b)
473 : leunga 1094 | CPS.SETTER(_,vl,e) => f0(vl, e)
474 :     | CPS.LOOKER(_,vl,w,t,e) => fx(vl, w, t, e, b)
475 :     | CPS.ARITH(_,vl,w,t,e) => fx(vl, w, t, e, b)
476 :     | CPS.PURE(_,vl,w,t,e) => fx(vl, w, t, e, b)
477 : mblume 1755 | CPS.RCC(_,_,_,vl,wtl,e)=>
478 :     let val b = b+1
479 :     in uses (vl, n);
480 :     app (fn (w, t) => def (w, t, b, n)) wtl;
481 :     gather (e, b, n+1)
482 :     end
483 : leunga 1094 | CPS.BRANCH(_,vl,c,x,y) => (uses(vl, n); gathers([x,y],b+1,n+1))
484 :     | CPS.FIX _ => error "FIX in Spill.gather"
485 :     end
486 :     in (* Always remember to define the arguments! *)
487 :     val () = ListPair.app (fn (v, t) => def(v, t, 0, 0)) (args, argTypes)
488 :     val () = gather(body, 1, 1)
489 :     end (* gather *)
490 :    
491 :     val () = if !debug_cps_spill then pr "CPS Spill: gather done\n" else ()
492 :    
493 :     (*-----------------------------------------------------------------
494 : jhr 4454 *
495 : leunga 1094 * Spill tables and utilities
496 :     *
497 :     *-----------------------------------------------------------------*)
498 :    
499 :     exception SpillTable
500 :     val spillTable = H.mkTable(32, SpillTable) :
501 :     (CPS.value * int * CPS.cty) H.hash_table
502 :     (* lvar -> spillRecord * spill offset * cty *)
503 : jhr 4454 val enterSpill = H.insert spillTable
504 : leunga 1094 val findSpill = H.find spillTable
505 :     val isSpilled = H.inDomain spillTable
506 :     val currentSpillRecord = ref (NONE : (CPS.lvar * CPS.value) option)
507 :    
508 :     (*
509 : jhr 4454 * Generate a new spill record variable
510 : leunga 1094 *)
511 : jhr 4454 fun genSpillRec() =
512 : leunga 1094 case !currentSpillRecord of
513 :     SOME x => x
514 : jhr 4454 | NONE =>
515 : leunga 1094 let val v = LV.namedLvar (Symbol.varSymbol "spillrec")
516 :     val e = CPS.VAR v
517 :     in currentSpillRecord := SOME(v,e); (v, e)
518 :     end
519 :    
520 :     (*
521 : jhr 4454 * This function finds up to m good spill candidates from the live set
522 : leunga 1094 *)
523 :     fun findGoodSpills(0, L, spOff) = (L, spOff)
524 :     | findGoodSpills(m, L, spOff) =
525 :     case next L of
526 :     (* no more spill candidates! *)
527 :     NONE => (L, spOff)
528 :     | SOME(SPILL_CANDIDATE{lvar, cty, rank, ...}, L) =>
529 :     let val offset = spOff (* should align when we have 64-bit values *)
530 :     val (_,spRecExp) = genSpillRec()
531 :     val () = enterSpill(lvar,(spRecExp,offset,cty))
532 : jhr 4454 fun inc(spOff,cty) = spOff + 1 (* should look at cty
533 :     * when we have 64-bit values
534 : leunga 1094 *)
535 :     in (* okay; it's actually live and hasn't been spilled! *)
536 :     if !debug_cps_spill then
537 :     pr("Spilling "^LV.lvarName lvar^" rank="^i2s rank^"\n")
538 :     else ();
539 :     findGoodSpills(m-1, L, inc(spOff, cty))
540 :     end
541 :    
542 :     (*
543 : jhr 4454 * Can and should the record be split?
544 : leunga 1094 * Split if,
545 :     * 1. we can handle the record type
546 :     * 2. if it has >= MAX_RECORD_LEN live lvars as arguments
547 :     * 3. All its arguments are defined in the same block as the record.
548 :     *)
549 : jhr 4454 fun shouldSplitRecord(rk,vl,b) =
550 : leunga 1094 SPLIT_LARGE_RECORDS andalso
551 :     let fun okPath(CPS.SELp(i,p)) = okPath p
552 :     | okPath(CPS.OFFp 0) = true
553 :     | okPath _ = false
554 : jhr 4454 fun f([], n) = n >= MAX_RECORD_LEN
555 : leunga 1094 | f((CPS.VAR v,p)::vl, n) =
556 :     let val LVAR_INFO{defBlock, ...} = lookupLvar v
557 :     in defBlock = b andalso okPath p andalso
558 : jhr 4454 (if isVar v andalso not(isSpilled v)
559 : leunga 1094 then f(vl, n+1)
560 :     else f(vl, n)
561 :     )
562 :     end
563 :     | f((_,CPS.OFFp 0)::vl, n) = f(vl, n)
564 :     | f _ = false
565 :     in splittable rk andalso f(vl, 0)
566 :     end
567 :    
568 :     (*
569 : jhr 4454 * Tables for splitting a record
570 : leunga 1094 *)
571 :     exception RecordTable
572 :     datatype split_record_item =
573 :     SPLIT_RECORD_ITEM of
574 :     { record : CPS.lvar,
575 :     kind : CPS.record_kind,
576 :     len : int,
577 :     offset : int,
578 :     path : CPS.accesspath,
579 :     numVars : int ref,
580 :     consts : (int * CPS.value) list
581 :     }
582 : jhr 4454
583 :     val recordAllocTable = H.mkTable(16, RecordTable)
584 : leunga 1094 val enterRecordItem = H.insert recordAllocTable
585 :     val findRecordItem = H.find recordAllocTable
586 : jhr 4454 val splitRecordTable = H.mkTable(16, RecordTable)
587 : leunga 1094 val markSplitRecord = H.insert splitRecordTable
588 :     fun insertRecordItem(v, x) =
589 :     enterRecordItem(v, x::getOpt(findRecordItem v,[]))
590 :    
591 :     (*
592 : jhr 4454 * Mark record w as being split.
593 : leunga 1094 * Enter the appropriate info to all its arguments.
594 : jhr 4454 *)
595 : leunga 1094 fun splitRecordConstruction(rk, vl, w) =
596 : jhr 4454 let fun f(i, (CPS.VAR v,offp)::vl, vars, consts) =
597 : leunga 1094 f(i+1, vl, (i,v,offp)::vars, consts)
598 : jhr 4454 | f(i, (c,CPS.OFFp 0)::vl, vars, consts) =
599 : leunga 1094 f(i+1, vl, vars, (i,c)::consts)
600 :     | f(_, [], vars, consts) = (vars, consts)
601 :     | f _ = error "CPS Spill.splitRecordConstruction"
602 :     val (vars, consts) = f(0, vl, [], [])
603 :     val n = length vars
604 : jhr 4454 val _ = if n = 0 then
605 : leunga 1094 error "CPS Spill: splitting constant record" else ()
606 :     val _ = if !debug_cps_spill_info then
607 :     pr("Splitting record "^LV.lvarName w^" len="^i2s n^"\n")
608 :     else ()
609 :     val len = length vl
610 :     val numVars = ref n
611 :     fun enter(i, v, path) =
612 : jhr 4454 let val item = SPLIT_RECORD_ITEM
613 : leunga 1094 { record = w,
614 :     kind = rk,
615 :     len = len,
616 : jhr 4454 offset = i,
617 :     path = path,
618 : leunga 1094 numVars = numVars,
619 :     consts = consts
620 :     }
621 :     in insertRecordItem(v, item)
622 :     end
623 :     in app enter vars;
624 :     markSplitRecord(w,true)
625 :     end
626 : jhr 4454
627 : leunga 1094 (*-----------------------------------------------------------------
628 :     * Linear scan spilling.
629 :     * This function marks all spill/reload sites.
630 :     *
631 :     * Parameters:
632 :     * e --- cps expression
633 :     * b --- current block
634 :     * spOff --- current available spill offset
635 :     *
636 :     * Return:
637 : jhr 4454 * L --- the set of live lvars in e
638 : leunga 1094 * spills --- the number of spills
639 : jhr 4454 *
640 : leunga 1094 * This phase takes O(N log N) time and O(N) space
641 :     *-----------------------------------------------------------------*)
642 : jhr 4454 fun scan(e, b, spOff) =
643 :     let
644 :     (* add uses to live set *)
645 : leunga 1094 fun addUses([], L) = L
646 :     | addUses(CPS.VAR v::vs, L) =
647 :     addUses(vs, if isVar v andalso not(isSpilled v) then
648 :     Set.add(L, spillCand v) else L)
649 : jhr 4454
650 : leunga 1094 | addUses(_::vs, L) = addUses(vs, L)
651 :    
652 :     (* This function kills a definition *)
653 :     fun kill(w, L) = if isVar w then rmv(L, spillCand w) else L
654 :    
655 :     (* This function find things to spill *)
656 : jhr 4454 fun genSpills(L, spOff) =
657 : leunga 1094 let val toSpills = card L - maxLive
658 :     in if toSpills > 0 then findGoodSpills(toSpills, L, spOff)
659 :     else (L, spOff)
660 :     end
661 :    
662 :     (* This function visits a list of continuations and
663 : jhr 4454 * gathers up the info
664 : leunga 1094 *)
665 : jhr 4454 fun scanList es =
666 : leunga 1094 let val b = b + 1
667 :     fun f [] = (O, 0)
668 :     | f [e] = scan(e, b, spOff)
669 : jhr 4454 | f(e::es) =
670 : leunga 1094 let val (L1, spOff1) = scan(e, b, spOff)
671 :     val (L2, spOff2) = f es
672 :     in (L1 \/ L2, Int.max(spOff1, spOff2))
673 :     end
674 :     in f es end
675 :    
676 : jhr 4454 (* This function scans normal cps operators
677 : leunga 1094 * with one definition and one continuation
678 :     *
679 :     * w : t <- f vs; e
680 :     *)
681 :     fun scanOp(vs, w, e, b) =
682 :     let val (L,spOff) = scan(e,b,spOff) (* do continuation *)
683 :     val L = kill(w, L) (* remove definition *)
684 :     val L = addUses(vs, L) (* add uses *)
685 :     val (L,spOff) = genSpills(L, spOff) (* find spill *)
686 : jhr 4454 in (L, spOff)
687 : leunga 1094 end
688 :    
689 :     (* This function scans stmts with multiple continuations *)
690 :     fun scanStmt(vs, es) =
691 :     let val (L,spOff) = scanList es (* do continuation *)
692 :     val L = addUses(vs, L) (* add uses *)
693 :     val (L, spOff) = genSpills(L,spOff) (* find spills *)
694 :     in (L, spOff)
695 :     end
696 :    
697 :     (* This function scans record constructors *)
698 : jhr 4454 fun scanRec(rk, vl, w, e) =
699 : leunga 1094 let val (L,spOff) = scan(e,b,spOff) (* do continuation *)
700 :     val (L, spOff) =
701 :     if shouldSplitRecord(rk, vl, b) then
702 :     (splitRecordConstruction(rk, vl, w); (L,spOff))
703 :     else
704 : jhr 4454 let val L = kill(w, L)
705 : leunga 1094 val L = addUses(map #1 vl, L)
706 :     in genSpills(L, spOff)
707 :     end
708 : jhr 4454 in (L, spOff)
709 : leunga 1094 end
710 :    
711 : jhr 4454 val (L, numSpills) =
712 : leunga 1094 case e of
713 :     CPS.APP(v,args) => scanStmt(v::args, [])
714 :     | CPS.SWITCH(v,c,es) => scanStmt([v], es)
715 :     | CPS.SELECT(i,v,w,t,e) => scanOp([v], w, e, b)
716 :     | CPS.OFFSET(i,v,w,e) => scanOp([v], w, e, b)
717 :     | CPS.RECORD(rk,l,w,e) => scanRec(rk, l, w, e)
718 :     | CPS.SETTER(p,vl,e) => scanStmt(vl,[e])
719 :     | CPS.LOOKER(p,vl,w,t,e) => scanOp(vl, w, e, b)
720 :     | CPS.ARITH(p,vl,w,t,e) => scanOp(vl, w, e, b)
721 :     | CPS.PURE(p,vl,w,t,e) => scanOp(vl, w, e, b)
722 : mblume 1755 | CPS.RCC(k,l,p,vl,wtl,e)=>
723 :     let val b = b+1
724 :     val (L,spOff) = scan(e,b,spOff)
725 :     val L = foldl (fn ((w, _), L) => kill (w, L)) L wtl
726 :     val L = addUses (vl, L)
727 :     val (L, spOff) = genSpills (L, spOff)
728 :     in (L, spOff)
729 :     end
730 : leunga 1094 | CPS.BRANCH(p,vl,c,x,y) => scanStmt(vl,[x,y])
731 :     | CPS.FIX _ => error "FIX in Spill.scan"
732 :    
733 :     in (L, numSpills)
734 :     end
735 :    
736 :     (* Scan the body *)
737 : jhr 4454 val (L, numSpills) = scan(body, 1, 0)
738 : leunga 1094
739 : jhr 4454 val () = if !debug_cps_spill then
740 : leunga 1094 pr("CPS Spill: scan done. Spilling "^i2s numSpills^"\n")
741 :     else ()
742 :     (*
743 :     * Generate reloads for a list of arguments.
744 :     * Returns:
745 :     * the rewritten list of arguments
746 :     * a function for inserting selects.
747 :     *)
748 :     fun emitReloads vs =
749 :     let fun g([], vs', f) = (rev vs', f)
750 :     | g((v as CPS.VAR x)::vs, vs', f) =
751 :     (case findSpill x of
752 :     NONE => g(vs, v::vs', f)
753 :     | SOME(spillRec, off, cty) =>
754 :     let val x' = LV.dupLvar x
755 :     val v' = CPS.VAR x'
756 :     fun f' e = CPS.SELECT(off,spillRec,x',cty, f e)
757 : jhr 4454 in g(vs, v'::vs', f')
758 : leunga 1094 end
759 :     )
760 :     | g(v::vs, vs', f) = g(vs, v::vs', f)
761 :     in g(vs, [], fn e => e)
762 :     end
763 :    
764 :     (*
765 :     * Generate reloads for record paths
766 :     * Returns:
767 :     * the rewritten list of record paths
768 :     *)
769 :     fun emitPathReloads vl =
770 :     let fun f([], vl') = rev vl'
771 :     | f((v as CPS.VAR x, p)::vl, vl') =
772 :     (case findSpill x of
773 :     NONE => f(vl, (v, p)::vl')
774 : jhr 4454 | SOME(spillRec, off, cty) =>
775 : leunga 1094 f(vl, (spillRec,CPS.SELp(off,p))::vl')
776 :     )
777 : jhr 4454 | f(v::vl, vl') = f(vl, v::vl')
778 : leunga 1094 in f(vl, [])
779 : jhr 4454 end
780 : leunga 1094
781 :     (* This function generate spill code for variable w *)
782 : jhr 4454 fun emitSpill(w, e) =
783 : leunga 1094 case findSpill w of
784 :     NONE => e
785 : jhr 4454 | SOME(spillRecord, off, cty) =>
786 : jhr 4960 CPS.SETTER(P.RAWUPDATE cty,
787 : jhr 4560 [spillRecord, tagInt off,CPS.VAR w], e)
788 : leunga 1094
789 :     (*
790 :     * Emit spill record code
791 :     *)
792 :     fun createSpillRecord(0, e) = e
793 : jhr 4454 | createSpillRecord(numSpills, e) =
794 : leunga 1094 let val (spillRecLvar,_) = genSpillRec()
795 :     val m = numSpills * itemSize
796 : jhr 4960 val e = CPS.PURE(P.RAWRECORD NONE,[tagInt m],
797 : jhr 4953 spillRecLvar,U.BOGt,e)
798 : leunga 1094 in currentSpillRecord := NONE; (* clear *)
799 :     e
800 :     end
801 :    
802 :     val recordIsSplit = H.inDomain splitRecordTable
803 :     val findSplitRecordArg = H.find recordAllocTable
804 :    
805 : jhr 4454 (*
806 : leunga 1094 * proj(v, path, e) ==> w <- v.path ; e[w/v]
807 :     *)
808 :     fun proj(v, CPS.OFFp 0, e) = e v
809 :     | proj(v, CPS.SELp(i,p), e) =
810 :     let val v' = LV.mkLvar()
811 :     val e = e v'
812 : jhr 4953 in CPS.SELECT(i, CPS.VAR v, v', U.BOGt, e)
813 : leunga 1094 end
814 : mblume 1334 | proj _ = error "SpillFn: proj"
815 : leunga 1094
816 :     (*
817 : jhr 4454 * generate
818 : leunga 1094 * record.offset <- v.path ; e
819 : jhr 4454 *)
820 :     fun initRecordItem(record, rk, offset, v, path, e) =
821 :     proj(v, path,
822 : jhr 4960 fn x => CPS.SETTER(P.RAWUPDATE(rkToCty rk),
823 : jhr 4560 [CPS.VAR record, tagInt offset, CPS.VAR x], e))
824 : jhr 4454
825 : leunga 1094 (*
826 :     * Generate code to create a record.
827 :     *)
828 :     fun createRecord(record, rk, len, consts, e) =
829 : jhr 4454 let val e = emitSpill(record, e)
830 : jhr 4960 val p = P.RAWUPDATE(rkToCty rk)
831 : jhr 4560 fun init((i, c),e) = CPS.SETTER(p,[CPS.VAR record, tagInt i, c], e)
832 : leunga 1094 val e = foldr init e consts
833 : jhr 4960 val e = CPS.PURE(P.RAWRECORD(SOME rk),[tagInt len],record,U.BOGt,e)
834 : leunga 1094 in e
835 :     end
836 :    
837 : jhr 4454 (*
838 : leunga 1094 * It is the definition of lvar v.
839 :     * Check to see if v is some component of split records.
840 : jhr 4454 * If so, generate code.
841 :     *
842 : leunga 1094 *)
843 : jhr 4454 fun assignToSplitRecord(v, e) =
844 : leunga 1094 case findSplitRecordArg v of
845 :     SOME inits =>
846 :     let fun gen(SPLIT_RECORD_ITEM
847 : jhr 4454 {record, kind, len, offset,
848 : leunga 1094 path, numVars, consts,...}, e) =
849 :     let val e = initRecordItem(record, kind, offset, v, path, e)
850 :     val n = !numVars - 1
851 :     in numVars := n;
852 :     if n = 0 then createRecord(record, kind, len, consts, e)
853 :     else e
854 :     end
855 :     in foldr gen e inits
856 :     end
857 :     | NONE => e
858 :    
859 :     (*-----------------------------------------------------------------
860 :     * Rebuild
861 :     *
862 :     * This function rewrites the cps expression and insert spill/reload
863 :     * code.
864 :     *
865 :     * This phase takes O(N) time and O(N) space
866 :     *-----------------------------------------------------------------*)
867 :    
868 : jhr 4454 fun rebuild e =
869 :     let
870 : leunga 1094
871 :     fun rewriteStmt(vs, es, f) =
872 :     let val es = map rebuild es
873 :     val (vs, g) = emitReloads vs
874 :     in g(f(vs, es)) end
875 :    
876 :     fun rewrite(vs, w, e, f) =
877 :     let val e = rebuild e
878 :     val e = emitSpill(w, e)
879 :     val e = assignToSplitRecord(w, e)
880 :     val (vs, g) = emitReloads vs
881 :     in g(f(vs, w, e))
882 :     end
883 :    
884 : mblume 1755 fun rewrite'(vs,wl,e,f) =
885 :     let val e = rebuild e
886 :     val e = foldl emitSpill e wl
887 :     val e = foldl assignToSplitRecord e wl
888 :     val (vs, g) = emitReloads vs
889 :     in g (f (vs, wl, e))
890 :     end
891 :    
892 : leunga 1094 fun rewriteRec(vl, w, e, f) =
893 :     let val e = rebuild e
894 :     val e = emitSpill(w, e)
895 :     val e = assignToSplitRecord(w, e)
896 :     in if recordIsSplit w then e
897 :     else f(emitPathReloads vl, w, e)
898 :     end
899 :    
900 : mblume 1334 (* wrappers -- make the match compiler shut up *)
901 :     fun s1 f (v :: vs, es) = f (v, vs, es)
902 :     | s1 _ _ = error "Spill: s1"
903 :    
904 :     fun e1 f ([v], w, e) = f (v, w, e)
905 :     | e1 _ _ = error "Spill: e1"
906 :    
907 :     fun s'1 f (vs, [e]) = f (vs, e)
908 :     | s'1 _ _ = error "Spill: s'1"
909 :    
910 :     fun s'2 f (vs, [x, y]) = f (vs, x, y)
911 :     | s'2 _ _ = error "Spill: s'2"
912 :    
913 : leunga 1094 (*
914 :     * Rewrite the expression
915 :     *)
916 : jhr 4454 val e =
917 : leunga 1094 case e of
918 : jhr 4454 CPS.APP(v,args) =>
919 : mblume 1334 rewriteStmt(v::args, [], s1 (fn (v, args,_) => CPS.APP(v,args)))
920 : jhr 4454 | CPS.SWITCH(v,c,es) =>
921 : mblume 1334 rewriteStmt([v], es, s1 (fn (v, _, es) => CPS.SWITCH(v, c, es)))
922 : jhr 4454 | CPS.SELECT(i,v,w,t,e) =>
923 : mblume 1334 rewrite([v], w, e, e1 (fn (v,w,e) => CPS.SELECT(i,v,w,t,e)))
924 : jhr 4454 | CPS.OFFSET(i,v,w,e) =>
925 : mblume 1334 rewrite([v], w, e, e1 (fn (v,w,e) => CPS.OFFSET(i,v,w,e)))
926 : jhr 4454 | CPS.RECORD(k,l,w,e) =>
927 : leunga 1094 rewriteRec(l,w,e,fn (l,w,e) => CPS.RECORD(k, l, w, e))
928 : jhr 4454 | CPS.SETTER(p,vl,e) =>
929 : mblume 1334 rewriteStmt(vl, [e], s'1 (fn (vl,e) => CPS.SETTER(p,vl,e)))
930 : leunga 1094 | CPS.LOOKER(p,vl,w,t,e) =>
931 :     rewrite(vl,w,e, fn (vl,w,e) => CPS.LOOKER(p,vl,w,t,e))
932 : jhr 4454 | CPS.ARITH(p,vl,w,t,e) =>
933 : leunga 1094 rewrite(vl,w,e, fn (vl,w,e) => CPS.ARITH(p,vl,w,t,e))
934 : jhr 4454 | CPS.PURE(p,vl,w,t,e) =>
935 : leunga 1094 rewrite(vl,w,e,fn (vl,w,e) => CPS.PURE(p,vl,w,t,e))
936 : jhr 4454 | CPS.RCC(k,l,p,vl,wtl,e) =>
937 : mblume 1755 rewrite' (vl, map #1 wtl, e,
938 :     fn (vl, wl, e) => CPS.RCC (k, l, p, vl,
939 :     ListPair.map (fn (w, (_, t)) => (w, t)) (wl, wtl),
940 :     e))
941 : jhr 4454 | CPS.BRANCH(p,vl,c,x,y) =>
942 : mblume 1334 rewriteStmt(vl,[x,y],
943 :     s'2 (fn (vl,x,y) => CPS.BRANCH(p,vl,c,x,y)))
944 : leunga 1094 | CPS.FIX _ => error "FIX in Spill.rebuild"
945 :    
946 :     in e
947 :     end (* rebuild *)
948 :    
949 :     (* insert spill/reload code *)
950 :     val body = rebuild body
951 :     val body = foldr emitSpill body args (* spill code for arguments *)
952 :     (*
953 :     * Insert spill record creation code.
954 :     *)
955 :     val body = createSpillRecord(numSpills, body)
956 :    
957 : blume 1126 val () = if !debug_cps_spill_info
958 : leunga 1094 then pr("CPS Spill: linearScan done "^i2s numSpills^" spilled\n")
959 :     else ()
960 :    
961 :     val cpsFun = (funKind, f, args, argTypes, body)
962 :    
963 :     val () = dump("after", cpsFun)
964 :    
965 :     in cpsFun
966 :     end (* linearScan *)
967 :    
968 :     (*-------------------------------------------------------------------------
969 :     * spillOne
970 :     * ========
971 :     *
972 :     * This is the driver to process only one CPS function.
973 :     *
974 :     * This routine takes a total of O(N log N) time and O(N) space
975 :     *
976 :     *-------------------------------------------------------------------------*)
977 : jhr 4454 fun spillOne cpsFun =
978 :     let
979 :     (*
980 : leunga 1094 * Perform spilling.
981 :     *)
982 :    
983 :     fun spillIt type_info cpsFun =
984 : jhr 4454 let val {needsSpilling, bandwidth, ...} = needsSpilling type_info cpsFun
985 : leunga 1094 val () = if !debug_cps_spill_info then
986 :     pr("CPS Spill bandwidth="^i2s bandwidth^"\n")
987 :     else ()
988 :     in if needsSpilling then linearScan type_info cpsFun
989 : jhr 4454 else cpsFun
990 : leunga 1094 end
991 : jhr 4454 (*
992 : leunga 1094 * If we have unboxed floats then we have to distinguish between
993 : jhr 4454 * fpr and gpr registers.
994 : leunga 1094 *)
995 :    
996 :     val (fpTable,recordTable) = markFpAndRec cpsFun (* collect fp type info *)
997 :    
998 :     val isMoveableRec = H.inDomain recordTable
999 :    
1000 : jhr 4454 val cpsFun =
1001 :     if MachSpec.unboxedFloats then
1002 : leunga 1094 let val isFP = H.inDomain fpTable
1003 :     fun isGP r = not(isFP r) andalso not(isMoveableRec r)
1004 :     val fp = TYPE_INFO{isVar=isFP, maxLive=maxfpfree, itemSize=2}
1005 :     val gp = TYPE_INFO{isVar=isGP, maxLive=maxgpfree, itemSize=1}
1006 :     val cpsFun = spillIt fp cpsFun (* do fp spills first *)
1007 :     val cpsFun = spillIt gp cpsFun (* do gp spills *)
1008 :     in cpsFun
1009 :     end
1010 : jhr 4454 else
1011 : leunga 1094 let fun isGP r = not(isMoveableRec r)
1012 : jhr 4454 in spillIt (TYPE_INFO{isVar=isGP, maxLive=maxgpfree, itemSize=1})
1013 : leunga 1094 cpsFun
1014 :     end
1015 :     in cpsFun
1016 :     end (* spillOne *)
1017 :    
1018 :    
1019 :     (* Main entry point *)
1020 :     val spill = map spillOne
1021 :    
1022 :     end (* SpillFn *)
1023 :    
1024 :     end (* local *)

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