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/src/MLRISC/ra/ra-spill.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/ra/ra-spill.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 545 - (view) (download)

1 : monnier 467 (*
2 :     * This module manages the spill/reload process.
3 :     * The reason this is detached from the main module is that
4 :     * I can't understand the old code.
5 :     *
6 :     * Okay, now I understand the code.
7 :     *
8 :     * The new code does things slightly differently.
9 :     * Here, we are given an instruction and a list of registers to spill
10 : monnier 498 * and reload. We rewrite the instruction until all instances of these
11 : monnier 467 * registers are rewritten.
12 : george 545 *
13 :     * (12/13/99) Some major caveats when spill coalescing/coloring is used:
14 :     * When parallel copies are generated and spill coalescing/coloring is used,
15 :     * two special cases have to be identified:
16 :     *
17 :     * Case 1 (spillLoc dst = spillLoc src)
18 :     * Suppose we have a parallel copy
19 :     * (u,v) <- (x,y)
20 :     * where u has to be spilled and y has to reloaded. When both
21 :     * u and y are mapped to location M. The following wrong code may
22 :     * be generated:
23 :     * M <- x (spill u)
24 :     * v <- M (reload y)
25 :     * This is incorrect. Instead, we generate a dummy copy and
26 :     * delay the spill after the reload, like this:
27 :     *
28 :     * tmp <- x (save value of u)
29 :     * v <- M (reload y)
30 :     * M <- tmp (spill u)
31 :     * Case 2 (spillLoc copyTmp = spillLoc src)
32 :     * Another case that can cause problems is when the spill location of
33 :     * the copy temporary is the same as that of one of the sources:
34 :     *
35 :     * (a, b, v) <- (b, a, u) where spillLoc(u) = spillLoc(tmp) = v
36 :     *
37 :     * The incorrect code is
38 :     * (a, b) <- (b, a)
39 :     * v <- M
40 :     * But then the shuffle code for the copy can clobber the location M.
41 :     *
42 :     * tmp <- M
43 :     * (a, b) <- (b, a)
44 :     * v <- tmp
45 :     *
46 :     * (Note that spillLoc copyTmp = spillLoc src can never happen)
47 : monnier 467 *
48 :     * -- Allen
49 :     *)
50 : monnier 498 functor RASpill(structure InsnProps : INSN_PROPERTIES
51 :     structure Asm : INSTRUCTION_EMITTER
52 :     sharing InsnProps.I = Asm.I
53 :     ) : RA_SPILL =
54 : monnier 467 struct
55 :    
56 :     structure I = InsnProps.I
57 :     structure P = InsnProps
58 :     structure C = I.C
59 :     structure G = RAGraph
60 :     structure Core = RACore
61 :     structure SL = SortedList
62 :    
63 :     fun error msg = MLRiscErrorMsg.error("RASpill",msg)
64 :    
65 : monnier 498 fun dec n = Word.toIntX(Word.fromInt n - 0w1)
66 :    
67 : monnier 467 type copyInstr =
68 : monnier 498 (C.cell list * C.cell list) * I.instruction -> I.instruction list
69 : monnier 467
70 : monnier 498 (*
71 :     * Spill the value associated with reg into spillLoc.
72 :     * All definitions of instr should be renamed to a new temporary newReg.
73 :     *)
74 : monnier 467 type spill =
75 :     {instr : I.instruction, (* instruction where spill is to occur *)
76 :     reg : C.cell, (* register to spill *)
77 :     spillLoc : int, (* logical spill location *)
78 :     kill : bool, (* can we kill the current node? *)
79 :     regmap : C.cell -> C.cell, (* current register map *)
80 :     annotations : Annotations.annotations ref (* annotations *)
81 :     } ->
82 : monnier 498 {code : I.instruction list, (* instruction + spill code *)
83 : monnier 467 proh : C.cell list, (* prohibited from future spilling *)
84 : monnier 498 newReg : C.cell option (* the spilled value is available here *)
85 : monnier 467 }
86 :    
87 : monnier 498 (* Spill the register src into spillLoc.
88 :     * The value is originally from register reg.
89 :     *)
90 :     type spillSrc =
91 :     {src : C.cell, (* register to spill from *)
92 :     reg : C.cell, (* the register *)
93 :     spillLoc : int, (* logical spill location *)
94 :     annotations : Annotations.annotations ref (* annotations *)
95 :     } -> I.instruction list (* spill code *)
96 :    
97 :     (*
98 :     * Spill the temporary associated with a copy into spillLoc
99 :     *)
100 :     type spillCopyTmp =
101 :     {copy : I.instruction, (* copy to spill *)
102 :     spillLoc : int, (* logical spill location *)
103 :     annotations : Annotations.annotations ref (* annotations *)
104 :     } -> I.instruction (* spill code *)
105 :    
106 :     (*
107 :     * Reload the value associated with reg from spillLoc.
108 :     * All uses of instr should be renamed to a new temporary newReg.
109 :     *)
110 : monnier 467 type reload =
111 :     {instr : I.instruction, (* instruction where spill is to occur *)
112 :     reg : C.cell, (* register to spill *)
113 :     spillLoc : int, (* logical spill location *)
114 :     regmap : C.cell -> C.cell, (* current register map *)
115 :     annotations : Annotations.annotations ref (* annotations *)
116 :     } ->
117 : monnier 498 {code : I.instruction list, (* instr + reload code *)
118 :     proh : C.cell list, (* prohibited from future spilling *)
119 :     newReg : C.cell option (* the reloaded value is here *)
120 : monnier 467 }
121 :    
122 :     (*
123 : monnier 498 * Rename all uses fromSrc to toSrc
124 :     *)
125 :     type renameSrc =
126 :     {instr : I.instruction, (* instruction where spill is to occur *)
127 :     fromSrc : C.cell, (* register to rename *)
128 :     toSrc : C.cell, (* register to rename to *)
129 :     regmap : C.cell -> C.cell (* current register map *)
130 :     } ->
131 :     {code : I.instruction list, (* renamed instr *)
132 :     proh : C.cell list, (* prohibited from future spilling *)
133 :     newReg : C.cell option (* the renamed value is here *)
134 :     }
135 :    
136 :     (* Reload the register dst from spillLoc.
137 :     * The value is originally from register reg.
138 :     *)
139 :     type reloadDst =
140 :     {dst : C.cell, (* register to reload to *)
141 :     reg : C.cell, (* the register *)
142 :     spillLoc : int, (* logical spill location *)
143 :     annotations : Annotations.annotations ref (* annotations *)
144 :     } -> I.instruction list (* reload code *)
145 :    
146 : george 545 (* val spilledCopyTmps = MLRiscControl.getCounter "ra-spilled-copy-temps" *)
147 :    
148 : monnier 498 (*
149 : monnier 467 * The following function performs spilling.
150 :     *)
151 :     fun spillRewrite
152 : george 545 {graph=G as G.GRAPH{showReg, spilledRegs, nodes, mode, ...},
153 : monnier 498 spill : spill,
154 :     spillCopyTmp : spillCopyTmp,
155 :     spillSrc : spillSrc,
156 :     renameSrc : renameSrc,
157 :     reload : reload,
158 :     reloadDst : reloadDst,
159 :     copyInstr : copyInstr,
160 :     cellkind,
161 :     spillSet, reloadSet, killSet
162 :     } =
163 : monnier 467 let
164 :     val regmap = Core.spillRegmap G (* This is the current regmap *)
165 :     val spillLocOf = Core.spillLoc G
166 : george 545 val spillLocsOf = map spillLocOf
167 : monnier 467 val getnode = Intmap.map nodes
168 :    
169 :     val insnDefUse = P.defUse cellkind
170 :    
171 :     (* Merge prohibited registers *)
172 :     val enterSpill = Intmap.add spilledRegs
173 :     val addProh = app (fn r => enterSpill(r,true))
174 :    
175 : monnier 498 val getSpills : int -> C.cell list = Intmap.mapWithDefault(spillSet,[])
176 :     val getReloads : int -> C.cell list = Intmap.mapWithDefault(reloadSet,[])
177 :     val getKills : int -> C.cell list = Intmap.mapWithDefault(killSet,[])
178 : monnier 467
179 : monnier 475 fun getLoc(G.NODE{color=ref(G.ALIASED n), ...}) = getLoc n
180 : monnier 467 | getLoc(G.NODE{color=ref(G.SPILLED ~1), number, ...}) = number
181 :     | getLoc(G.NODE{color=ref(G.SPILLED c), ...}) = c
182 :     | getLoc(G.NODE{number, ...}) = number
183 :    
184 : george 545 val parallelCopies = Word.andb(RACore.HAS_PARALLEL_COPIES, mode) <> 0w0
185 : monnier 467 (*
186 : monnier 498 * Rewrite the instruction given that a bunch of registers have
187 :     * to be spilled and reloaded.
188 : monnier 467 *)
189 : monnier 498 fun spillRewrite{pt, instrs, annotations} =
190 :     let
191 :     (*
192 :     * Insert reloading code for an instruction.
193 :     * Note: reload code goes after the instruction, if any.
194 :     *)
195 :     fun reloadInstr(instr,regToSpill,spillLoc) =
196 :     let val {code, proh, newReg} =
197 :     reload{regmap=regmap,instr=instr,reg=regToSpill,
198 :     spillLoc=spillLoc,annotations=annotations}
199 :     in addProh(proh);
200 :     code
201 :     end
202 :    
203 :     (*
204 :     * Renaming the source for an instruction.
205 :     *)
206 :     fun renameInstr(instr,regToSpill,toSrc) =
207 :     let val {code, proh, newReg} =
208 :     renameSrc{regmap=regmap,instr=instr,
209 :     fromSrc=regToSpill,toSrc=toSrc}
210 :     in addProh(proh);
211 :     code
212 :     end
213 : monnier 467
214 : monnier 498 (*
215 :     * Remove uses of regToSpill from a set of parallel copies.
216 :     * If there are multiple uses, then return multiple moves.
217 :     *)
218 :     fun extractUses(regToSpill, rds, rss) =
219 :     let fun loop(rd::rds, rs::rss, newRds, rds', rss') =
220 :     if regmap rs = regToSpill then
221 :     loop(rds, rss, rd::newRds, rds', rss')
222 :     else
223 :     loop(rds, rss, newRds, rd::rds', rs::rss')
224 :     | loop(_, _, newRds, rds', rss') = (newRds, rds', rss')
225 :     in loop(rds, rss, [], [], []) end
226 :    
227 :     (*
228 :     * Insert reload code for the sources of a copy.
229 :     * Transformation:
230 :     * d1..dn <- s1..sn
231 :     * =>
232 :     * d1..dn/r <- s1...sn/r.
233 :     * reload code
234 :     * reload copies
235 :     *
236 :     *)
237 :     fun reloadCopySrc(instr,regToSpill,spillLoc) =
238 :     let val (dst, src) = P.moveDstSrc instr
239 :     val (rds, copyDst, copySrc) = extractUses(regToSpill, dst, src)
240 :     fun processMoves([], reloadCode) = reloadCode
241 :     | processMoves(rd::rds, reloadCode) =
242 :     let val code =
243 :     reloadDst{spillLoc=spillLoc,reg=regToSpill,
244 :     dst=rd,annotations=annotations}
245 :     in processMoves(rds, code@reloadCode)
246 :     end
247 :     val reloadCode = processMoves(rds, [])
248 :     in case copyDst of
249 :     [] => reloadCode
250 :     | _ => copyInstr((copyDst, copySrc), instr) @ reloadCode
251 :     end
252 :    
253 :     (*
254 :     * Insert reload code
255 :     *)
256 :     fun reload(instr,regToSpill,spillLoc) =
257 :     if P.moveInstr instr then
258 :     reloadCopySrc(instr,regToSpill,spillLoc)
259 :     else
260 :     reloadInstr(instr,regToSpill,spillLoc)
261 :    
262 :     (*
263 :     * Check whether the regToSpill is in a list
264 :     *)
265 : george 545 fun contains(regToSpill:int,[]) = false
266 :     | contains(regToSpill,r::rs) =
267 :     r = regToSpill orelse contains(regToSpill,rs)
268 : monnier 498
269 :     (*
270 :     * Insert spill code for an instruction.
271 :     * Spill code occur after the instruction.
272 :     * If the value in regToSpill is never used, the client also
273 :     * has the opportunity to remove the instruction.
274 :     *)
275 :     fun spillInstr(instr,regToSpill,spillLoc,kill) =
276 :     let val {code, proh, newReg} =
277 :     spill{regmap=regmap, instr=instr,
278 :     kill=kill, spillLoc=spillLoc,
279 :     reg=regToSpill, annotations=annotations}
280 :     in addProh(proh);
281 :     code
282 :     end
283 :    
284 :     (* Remove the definition regToSpill <- from
285 :     * parallel copies rds <- rss.
286 :     * Note, there is a guarantee that regToSpill is not aliased
287 :     * to another register in the rds set.
288 :     *)
289 :     fun extractDef(regToSpill,rds,rss,kill) =
290 :     let fun loop(rd::rds, rs::rss, rds', rss') =
291 :     if spillLocOf rd = spillLocOf rs then
292 :     (rs, rds@rds', rss@rss', true)
293 :     else if regmap rd = regToSpill then
294 :     (rs, rds@rds', rss@rss', kill)
295 :     else loop(rds, rss, rd::rds', rs::rss')
296 :     | loop _ =
297 :     (print("rds=");
298 :     app (fn r => print(Int.toString r^":"^
299 :     Int.toString(spillLocOf r)^" ")) rds;
300 :     print("\nrss=");
301 :     app (fn r => print(Int.toString r^":"^
302 :     Int.toString(spillLocOf r)^" ")) rss;
303 :     print "\n";
304 :     error("extractDef: "^Int.toString regToSpill))
305 :     in loop(rds, rss, [], []) end
306 :    
307 :     (*
308 :     * Insert spill code for a destination of a copy
309 : george 545 * suppose d = r and we have a copy d <- s in
310 : monnier 498 * d1...dn <- s1...sn
311 : george 545 *
312 :     * d1...dn <- s1...sn
313 : monnier 498 * =>
314 : george 545 * spill s to spillLoc
315 :     * d1...dn/d <- s1...sn/s
316 :     *
317 :     * However, if the spill code may ovewrite the spill location
318 :     * shared by other uses, we do the following less
319 :     * efficient scheme:
320 :     *
321 :     * /* save the result of d */
322 :     * d1...dn, tmp <- s1...sn, s
323 :     * spill tmp to spillLoc /* spill d */
324 : monnier 498 *
325 :     *)
326 : george 545 fun spillCopyDst(instr,regToSpill,spillLoc,kill,don'tOverwrite) =
327 : monnier 498 let val (dst, src) = P.moveDstSrc instr
328 :     val (mvSrc,copyDst,copySrc,kill) =
329 :     extractDef(regToSpill,dst,src,kill)
330 :     val copy = case copyDst of
331 :     [] => []
332 :     | _ => copyInstr((copyDst,copySrc),instr)
333 :     in if kill
334 :     then (* kill the move *)
335 :     ((* print ("Copy "^Int.toString(hd mvDst)^" <- "^
336 :     Int.toString(hd mvSrc)^" removed\n"); *)
337 :     copy
338 :     )
339 :     else (* normal spill *)
340 : george 545 if contains(spillLoc, don'tOverwrite) then
341 :     let (* cycle found *)
342 :     (*val _ = print("Register r"^Int.toString regToSpill^
343 :     " overwrites ["^Int.toString spillLoc^"]\n")*)
344 :     val tmp = I.C.newCell cellkind () (* new temporary *)
345 :     val copy = copyInstr((tmp::copyDst, mvSrc::copySrc),
346 :     instr)
347 :     val spillCode = spillSrc{src=tmp,reg=regToSpill,
348 :     spillLoc=spillLoc,
349 :     annotations=annotations}
350 :     in copy @ spillCode
351 :     end
352 :     else
353 :     let (* spill the move instruction *)
354 :     val spillCode = spillSrc{src=mvSrc,reg=regToSpill,
355 :     spillLoc=spillLoc,
356 :     annotations=annotations}
357 :     in spillCode @ copy
358 :     end
359 : monnier 467 end
360 : monnier 498
361 :     (*
362 :     * Insert spill code for a copy
363 :     *)
364 : george 545 fun spillCopy(instr,regToSpill,spillLoc,kill,don'tOverwrite) =
365 : monnier 498 case P.moveTmpR instr of
366 : george 545 NONE => spillCopyDst(instr,regToSpill,spillLoc,kill,
367 :     don'tOverwrite)
368 : monnier 498 | SOME tmp =>
369 :     if regmap tmp = regToSpill
370 : george 545 then ((* spilledCopyTmps := !spilledCopyTmps + 1; *)
371 :     [spillCopyTmp{copy=instr, spillLoc=spillLoc,
372 :     annotations=annotations}])
373 :     else spillCopyDst(instr,regToSpill,spillLoc,kill,
374 :     don'tOverwrite)
375 : monnier 498
376 :     (*
377 :     * Insert spill code
378 :     *)
379 : george 545 fun spill(instr,regToSpill,spillLoc,killSet,don'tOverwrite) =
380 :     let val kill = contains(regToSpill,killSet)
381 : monnier 498 in if P.moveInstr instr then
382 : george 545 spillCopy(instr,regToSpill,spillLoc,kill,don'tOverwrite)
383 : monnier 498 else
384 :     spillInstr(instr,regToSpill,spillLoc,kill)
385 :     end
386 : monnier 467
387 : monnier 498 fun contains([],reg) = false
388 : monnier 467 | contains(r::rs,reg) = regmap r = reg orelse contains(rs,reg)
389 :     fun hasDef(i,reg) = contains(#1(insnDefUse i),reg)
390 :     fun hasUse(i,reg) = contains(#2(insnDefUse i),reg)
391 :    
392 : george 545 fun spillOneReg([],_,_,_,_) = []
393 :     | spillOneReg(i::instrs,r,spillLoc,killSet,don'tOverwrite) =
394 : monnier 467 if hasDef(i,r)
395 :     then
396 : george 545 spillOneReg(spill(i,r,spillLoc,killSet,don'tOverwrite)@instrs,
397 :     r,spillLoc,killSet,don'tOverwrite)
398 :     else i::spillOneReg(instrs,r,spillLoc,killSet,don'tOverwrite)
399 : monnier 467
400 : monnier 475 fun reloadOneReg([],_,_) = []
401 :     | reloadOneReg(i::instrs,r,spillLoc) =
402 : monnier 467 if hasUse(i,r)
403 : monnier 498 then reloadOneReg(reload(i,r,spillLoc)@instrs,
404 : monnier 475 r,spillLoc)
405 :     else i::reloadOneReg(instrs,r,spillLoc)
406 : monnier 467
407 :     (* This function spills a set of registers for an instruction *)
408 : george 545 fun spillAll(instrs,[],killSet,don'tOverwrite) = instrs
409 :     | spillAll(instrs,r::rs,killSet,don'tOverwrite) =
410 : monnier 467 let val node = getnode r
411 :     val spillLoc = getLoc node
412 : george 545 in spillAll(
413 :     spillOneReg(instrs,r,spillLoc,killSet,don'tOverwrite),
414 :     rs,killSet,don'tOverwrite)
415 : monnier 467 end
416 :    
417 :     (* This function reloads a set of registers for an instruction *)
418 :     fun reloadAll(instrs,[]) = instrs
419 :     | reloadAll(instrs,r::rs) =
420 :     let val node = getnode r
421 :     val spillLoc = getLoc node
422 : monnier 475 in reloadAll(reloadOneReg(instrs,r,spillLoc),rs)
423 : monnier 467 end
424 :    
425 : monnier 498 fun loop([], pt, newInstrs) = newInstrs
426 :     | loop(instr::rest, pt, newInstrs) =
427 :     let val spillRegs = getSpills pt
428 :     val reloadRegs = getReloads pt
429 :     in case (spillRegs, reloadRegs) of
430 :     ([], []) => loop(rest, dec pt, instr::newInstrs)
431 :     | _ =>
432 :     (* Eliminate duplicates from the spill/reload candidates *)
433 :     let val killRegs = getKills pt
434 :     val spillRegs = SL.uniq spillRegs
435 :     val reloadRegs = SL.uniq reloadRegs
436 : monnier 467
437 : george 545 (* spill locations that we can't overwrite if we
438 :     * are spilling a parallel copy
439 :     *)
440 :     val don'tOverwrite =
441 :     if parallelCopies then spillLocsOf reloadRegs
442 :     else []
443 :    
444 : monnier 498 (*
445 :     val Asm.S.STREAM{emit, ...} = Asm.makeStream[]
446 :     val regs = app (fn r =>
447 : george 545 print(Int.toString(regmap r)^" ["^Int.toString
448 : monnier 498 (getLoc (getnode r))^"] "))
449 :     *)
450 : george 545
451 :     val instrs = spillAll([instr],spillRegs,killRegs,
452 :     don'tOverwrite)
453 : monnier 498
454 : george 545 (*
455 : monnier 498 val _ =
456 :     (print("pt="^Int.toString pt^"\n");
457 :     if spillRegs = [] then () else
458 :     (print("Spilling ");
459 :     regs spillRegs; print "\n");
460 :     if reloadRegs = [] then () else
461 :     (print("Reloading ");
462 :     regs reloadRegs; print "\n");
463 :     print "Before:"; emit regmap instr)
464 :     *)
465 :    
466 :     val instrs = reloadAll(instrs,reloadRegs)
467 :    
468 : george 545 (*
469 : monnier 498 val _ =
470 :     (print "After:"; app (emit regmap) instrs;
471 :     print "------------------\n")
472 :     *)
473 : george 545
474 : monnier 498 fun concat([], l) = l
475 :     | concat(a::b, l) = concat(b, a::l)
476 :     in loop(rest, dec pt, concat(instrs, newInstrs))
477 :     end
478 :     end
479 :     in loop(rev instrs, pt, [])
480 : monnier 467 end
481 : monnier 498 in spillRewrite
482 : monnier 467 end
483 :    
484 :     end

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