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

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