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

Annotation of /MLRISC/releases/release-110.64/ra/ra-spill.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 933 - (view) (download)
Original Path: sml/trunk/src/MLRISC/ra/ra-spill.sml

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 : leunga 744
51 :     local
52 :    
53 :     val debug = false
54 :    
55 :     in
56 :    
57 :     functor RASpill
58 :     (structure InsnProps : INSN_PROPERTIES
59 :     structure Asm : INSTRUCTION_EMITTER
60 : george 933 where I = InsnProps.I
61 : leunga 744 ) : RA_SPILL =
62 : monnier 467 struct
63 :    
64 :     structure I = InsnProps.I
65 :     structure P = InsnProps
66 :     structure C = I.C
67 :     structure Core = RACore
68 : leunga 744 structure G = Core.G
69 : george 889 structure CB = CellsBasis
70 : monnier 467
71 :     fun error msg = MLRiscErrorMsg.error("RASpill",msg)
72 :    
73 : monnier 498 fun dec n = Word.toIntX(Word.fromInt n - 0w1)
74 :    
75 : leunga 744 structure T = RASpillTypes(I)
76 :     open T
77 : monnier 467
78 : george 889 fun uniq s = CB.SortedCells.return(CB.SortedCells.uniq s)
79 : leunga 744 val i2s = Int.toString
80 : monnier 467
81 : leunga 744 val Asm.S.STREAM{emit, ...} = Asm.makeStream[]
82 : monnier 498
83 : george 545 (* val spilledCopyTmps = MLRiscControl.getCounter "ra-spilled-copy-temps" *)
84 :    
85 : monnier 498 (*
86 : monnier 467 * The following function performs spilling.
87 :     *)
88 :     fun spillRewrite
89 : george 545 {graph=G as G.GRAPH{showReg, spilledRegs, nodes, mode, ...},
90 : monnier 498 spill : spill,
91 :     spillCopyTmp : spillCopyTmp,
92 :     spillSrc : spillSrc,
93 :     renameSrc : renameSrc,
94 :     reload : reload,
95 :     reloadDst : reloadDst,
96 :     copyInstr : copyInstr,
97 :     cellkind,
98 :     spillSet, reloadSet, killSet
99 :     } =
100 : monnier 467 let
101 : leunga 744 (* Must do this to make sure the interference graph is
102 :     * reflected to the cells
103 :     *)
104 :     val _ = Core.updateCellAliases G
105 :    
106 :     val getSpillLoc = Core.spillLoc G
107 : george 889 fun spillLocOf(CB.CELL{id, ...}) = getSpillLoc id
108 : george 545 val spillLocsOf = map spillLocOf
109 : blume 733 val getnode = IntHashTable.lookup nodes
110 : george 889 val getnode = fn CB.CELL{id, ...} => getnode id
111 : monnier 467
112 :     val insnDefUse = P.defUse cellkind
113 :    
114 :     (* Merge prohibited registers *)
115 : blume 733 val enterSpill = IntHashTable.insert spilledRegs
116 : george 889 val addProh = app (fn c => enterSpill(CellsBasis.registerId c,true))
117 : monnier 467
118 : leunga 744 val getSpills = G.PPtHashTable.find spillSet
119 :     val getSpills = fn p => case getSpills p of SOME s => s | NONE => []
120 :     val getReloads = G.PPtHashTable.find reloadSet
121 :     val getReloads = fn p => case getReloads p of SOME s => s | NONE => []
122 :     val getKills = G.PPtHashTable.find killSet
123 :     val getKills = fn p => case getKills p of SOME s => s | NONE => []
124 : monnier 467
125 : monnier 475 fun getLoc(G.NODE{color=ref(G.ALIASED n), ...}) = getLoc n
126 : leunga 744 | getLoc(G.NODE{color=ref(G.MEMREG(_, m)), ...}) = G.MEM_REG m
127 :     | getLoc(G.NODE{color=ref(G.SPILL_LOC s), ...}) = G.FRAME s
128 :     | getLoc(G.NODE{color=ref(G.SPILLED), number, ...}) = G.FRAME number
129 :     | getLoc(G.NODE{color=ref(G.PSEUDO), number, ...}) = G.FRAME number
130 :     | getLoc _ = error "getLoc"
131 : monnier 467
132 : leunga 744 fun printRegs regs =
133 : george 889 app (fn r => print(CellsBasis.toString r^" ["^
134 :     Core.spillLocToString G (CellsBasis.cellId r)^"] ")) regs
135 : leunga 744
136 :     val parallelCopies = Word.andb(Core.HAS_PARALLEL_COPIES, mode) <> 0w0
137 :    
138 : george 889 fun chase(CB.CELL{col=ref(CB.ALIASED c), ...}) = chase c
139 : leunga 744 | chase c = c
140 :    
141 : george 889 fun cellId(CB.CELL{id, ...}) = id
142 : leunga 744
143 : george 889 fun sameCell(CB.CELL{id=x,...}, CB.CELL{id=y, ...}) = x=y
144 : leunga 744
145 :     fun same(x,regToSpill) = sameCell(chase x,regToSpill)
146 :    
147 : monnier 467 (*
148 : monnier 498 * Rewrite the instruction given that a bunch of registers have
149 :     * to be spilled and reloaded.
150 : monnier 467 *)
151 : monnier 498 fun spillRewrite{pt, instrs, annotations} =
152 :     let
153 :     (*
154 :     * Insert reloading code for an instruction.
155 :     * Note: reload code goes after the instruction, if any.
156 :     *)
157 :     fun reloadInstr(instr,regToSpill,spillLoc) =
158 :     let val {code, proh, newReg} =
159 : leunga 744 reload{instr=instr,reg=regToSpill,
160 : monnier 498 spillLoc=spillLoc,annotations=annotations}
161 :     in addProh(proh);
162 :     code
163 :     end
164 :    
165 :     (*
166 :     * Renaming the source for an instruction.
167 :     *)
168 :     fun renameInstr(instr,regToSpill,toSrc) =
169 :     let val {code, proh, newReg} =
170 : leunga 744 renameSrc{instr=instr, fromSrc=regToSpill,toSrc=toSrc}
171 : monnier 498 in addProh(proh);
172 :     code
173 :     end
174 : monnier 467
175 : monnier 498 (*
176 :     * Remove uses of regToSpill from a set of parallel copies.
177 :     * If there are multiple uses, then return multiple moves.
178 :     *)
179 :     fun extractUses(regToSpill, rds, rss) =
180 :     let fun loop(rd::rds, rs::rss, newRds, rds', rss') =
181 : leunga 744 if same(rs,regToSpill) then
182 : monnier 498 loop(rds, rss, rd::newRds, rds', rss')
183 :     else
184 :     loop(rds, rss, newRds, rd::rds', rs::rss')
185 :     | loop(_, _, newRds, rds', rss') = (newRds, rds', rss')
186 :     in loop(rds, rss, [], [], []) end
187 :    
188 :     (*
189 :     * Insert reload code for the sources of a copy.
190 :     * Transformation:
191 :     * d1..dn <- s1..sn
192 :     * =>
193 :     * d1..dn/r <- s1...sn/r.
194 :     * reload code
195 :     * reload copies
196 :     *
197 :     *)
198 :     fun reloadCopySrc(instr,regToSpill,spillLoc) =
199 :     let val (dst, src) = P.moveDstSrc instr
200 :     val (rds, copyDst, copySrc) = extractUses(regToSpill, dst, src)
201 :     fun processMoves([], reloadCode) = reloadCode
202 :     | processMoves(rd::rds, reloadCode) =
203 :     let val code =
204 :     reloadDst{spillLoc=spillLoc,reg=regToSpill,
205 :     dst=rd,annotations=annotations}
206 :     in processMoves(rds, code@reloadCode)
207 :     end
208 :     val reloadCode = processMoves(rds, [])
209 :     in case copyDst of
210 :     [] => reloadCode
211 :     | _ => copyInstr((copyDst, copySrc), instr) @ reloadCode
212 :     end
213 :    
214 :     (*
215 :     * Insert reload code
216 :     *)
217 :     fun reload(instr,regToSpill,spillLoc) =
218 :     if P.moveInstr instr then
219 :     reloadCopySrc(instr,regToSpill,spillLoc)
220 :     else
221 :     reloadInstr(instr,regToSpill,spillLoc)
222 :    
223 :     (*
224 : leunga 744 * Check whether the id is in a list
225 : monnier 498 *)
226 : leunga 744 fun containsId(id,[]) = false
227 : george 889 | containsId(id:CB.cell_id,r::rs) = r = id orelse containsId(id,rs)
228 : leunga 744 fun spillConflict(G.FRAME loc, rs) = containsId(~loc, rs)
229 : george 889 | spillConflict(G.MEM_REG(CB.CELL{id, ...}), rs) =
230 : leunga 744 containsId(id, rs)
231 :    
232 :     fun contains(r',[]) = false
233 :     | contains(r',r::rs) = sameCell(r',r) orelse contains(r',rs)
234 :    
235 : monnier 498 (*
236 :     * Insert spill code for an instruction.
237 :     * Spill code occur after the instruction.
238 :     * If the value in regToSpill is never used, the client also
239 :     * has the opportunity to remove the instruction.
240 :     *)
241 :     fun spillInstr(instr,regToSpill,spillLoc,kill) =
242 :     let val {code, proh, newReg} =
243 : leunga 744 spill{instr=instr,
244 : monnier 498 kill=kill, spillLoc=spillLoc,
245 :     reg=regToSpill, annotations=annotations}
246 :     in addProh(proh);
247 :     code
248 :     end
249 :    
250 :     (* Remove the definition regToSpill <- from
251 :     * parallel copies rds <- rss.
252 :     * Note, there is a guarantee that regToSpill is not aliased
253 :     * to another register in the rds set.
254 :     *)
255 :     fun extractDef(regToSpill,rds,rss,kill) =
256 :     let fun loop(rd::rds, rs::rss, rds', rss') =
257 :     if spillLocOf rd = spillLocOf rs then
258 :     (rs, rds@rds', rss@rss', true)
259 : leunga 744 else if same(rd, regToSpill) then
260 : monnier 498 (rs, rds@rds', rss@rss', kill)
261 :     else loop(rds, rss, rd::rds', rs::rss')
262 :     | loop _ =
263 :     (print("rds=");
264 : george 889 app (fn r => print(CellsBasis.toString r^":"^
265 : leunga 744 i2s(spillLocOf r)^" ")) rds;
266 : monnier 498 print("\nrss=");
267 : george 889 app (fn r => print(CellsBasis.toString r^":"^
268 : leunga 744 i2s(spillLocOf r)^" ")) rss;
269 : monnier 498 print "\n";
270 : george 889 error("extractDef: "^CellsBasis.toString regToSpill))
271 : monnier 498 in loop(rds, rss, [], []) end
272 :    
273 :     (*
274 :     * Insert spill code for a destination of a copy
275 : george 545 * suppose d = r and we have a copy d <- s in
276 : monnier 498 * d1...dn <- s1...sn
277 : george 545 *
278 :     * d1...dn <- s1...sn
279 : monnier 498 * =>
280 : george 545 * spill s to spillLoc
281 :     * d1...dn/d <- s1...sn/s
282 :     *
283 :     * However, if the spill code may ovewrite the spill location
284 :     * shared by other uses, we do the following less
285 :     * efficient scheme:
286 :     *
287 :     * /* save the result of d */
288 :     * d1...dn, tmp <- s1...sn, s
289 :     * spill tmp to spillLoc /* spill d */
290 : monnier 498 *
291 :     *)
292 : george 545 fun spillCopyDst(instr,regToSpill,spillLoc,kill,don'tOverwrite) =
293 : monnier 498 let val (dst, src) = P.moveDstSrc instr
294 :     val (mvSrc,copyDst,copySrc,kill) =
295 :     extractDef(regToSpill,dst,src,kill)
296 :     val copy = case copyDst of
297 :     [] => []
298 :     | _ => copyInstr((copyDst,copySrc),instr)
299 :     in if kill
300 :     then (* kill the move *)
301 :     ((* print ("Copy "^Int.toString(hd mvDst)^" <- "^
302 :     Int.toString(hd mvSrc)^" removed\n"); *)
303 :     copy
304 :     )
305 :     else (* normal spill *)
306 : leunga 744 if spillConflict(spillLoc, don'tOverwrite) then
307 : george 545 let (* cycle found *)
308 :     (*val _ = print("Register r"^Int.toString regToSpill^
309 :     " overwrites ["^Int.toString spillLoc^"]\n")*)
310 : george 889 val tmp = C.newVar regToSpill (* new temporary *)
311 : george 545 val copy = copyInstr((tmp::copyDst, mvSrc::copySrc),
312 :     instr)
313 :     val spillCode = spillSrc{src=tmp,reg=regToSpill,
314 :     spillLoc=spillLoc,
315 :     annotations=annotations}
316 :     in copy @ spillCode
317 :     end
318 :     else
319 :     let (* spill the move instruction *)
320 :     val spillCode = spillSrc{src=mvSrc,reg=regToSpill,
321 :     spillLoc=spillLoc,
322 :     annotations=annotations}
323 :     in spillCode @ copy
324 :     end
325 : monnier 467 end
326 : monnier 498
327 :     (*
328 :     * Insert spill code for a copy
329 :     *)
330 : george 545 fun spillCopy(instr,regToSpill,spillLoc,kill,don'tOverwrite) =
331 : monnier 498 case P.moveTmpR instr of
332 : george 545 NONE => spillCopyDst(instr,regToSpill,spillLoc,kill,
333 :     don'tOverwrite)
334 : monnier 498 | SOME tmp =>
335 : leunga 744 if same(tmp, regToSpill)
336 : george 545 then ((* spilledCopyTmps := !spilledCopyTmps + 1; *)
337 : leunga 815 [spillCopyTmp{copy=instr, reg=regToSpill,
338 :     spillLoc=spillLoc,
339 : george 545 annotations=annotations}])
340 :     else spillCopyDst(instr,regToSpill,spillLoc,kill,
341 :     don'tOverwrite)
342 : monnier 498
343 :     (*
344 :     * Insert spill code
345 :     *)
346 : george 545 fun spill(instr,regToSpill,spillLoc,killSet,don'tOverwrite) =
347 :     let val kill = contains(regToSpill,killSet)
348 : monnier 498 in if P.moveInstr instr then
349 : george 545 spillCopy(instr,regToSpill,spillLoc,kill,don'tOverwrite)
350 : monnier 498 else
351 :     spillInstr(instr,regToSpill,spillLoc,kill)
352 :     end
353 : monnier 467
354 : monnier 498 fun contains([],reg) = false
355 : leunga 744 | contains(r::rs,reg) = same(r,reg) orelse contains(rs,reg)
356 : monnier 467 fun hasDef(i,reg) = contains(#1(insnDefUse i),reg)
357 :     fun hasUse(i,reg) = contains(#2(insnDefUse i),reg)
358 :    
359 : george 545 fun spillOneReg([],_,_,_,_) = []
360 :     | spillOneReg(i::instrs,r,spillLoc,killSet,don'tOverwrite) =
361 : monnier 467 if hasDef(i,r)
362 :     then
363 : george 545 spillOneReg(spill(i,r,spillLoc,killSet,don'tOverwrite)@instrs,
364 :     r,spillLoc,killSet,don'tOverwrite)
365 :     else i::spillOneReg(instrs,r,spillLoc,killSet,don'tOverwrite)
366 : monnier 467
367 : monnier 475 fun reloadOneReg([],_,_) = []
368 :     | reloadOneReg(i::instrs,r,spillLoc) =
369 : monnier 467 if hasUse(i,r)
370 : monnier 498 then reloadOneReg(reload(i,r,spillLoc)@instrs,
371 : monnier 475 r,spillLoc)
372 :     else i::reloadOneReg(instrs,r,spillLoc)
373 : monnier 467
374 :     (* This function spills a set of registers for an instruction *)
375 : george 545 fun spillAll(instrs,[],killSet,don'tOverwrite) = instrs
376 :     | spillAll(instrs,r::rs,killSet,don'tOverwrite) =
377 : monnier 467 let val node = getnode r
378 :     val spillLoc = getLoc node
379 : george 545 in spillAll(
380 :     spillOneReg(instrs,r,spillLoc,killSet,don'tOverwrite),
381 :     rs,killSet,don'tOverwrite)
382 : monnier 467 end
383 :    
384 :     (* This function reloads a set of registers for an instruction *)
385 :     fun reloadAll(instrs,[]) = instrs
386 :     | reloadAll(instrs,r::rs) =
387 :     let val node = getnode r
388 :     val spillLoc = getLoc node
389 : monnier 475 in reloadAll(reloadOneReg(instrs,r,spillLoc),rs)
390 : monnier 467 end
391 :    
392 : monnier 498 fun loop([], pt, newInstrs) = newInstrs
393 :     | loop(instr::rest, pt, newInstrs) =
394 :     let val spillRegs = getSpills pt
395 :     val reloadRegs = getReloads pt
396 :     in case (spillRegs, reloadRegs) of
397 :     ([], []) => loop(rest, dec pt, instr::newInstrs)
398 :     | _ =>
399 :     (* Eliminate duplicates from the spill/reload candidates *)
400 :     let val killRegs = getKills pt
401 : leunga 744 val spillRegs = uniq spillRegs
402 :     val reloadRegs = uniq reloadRegs
403 : monnier 467
404 : george 545 (* spill locations that we can't overwrite if we
405 :     * are spilling a parallel copy
406 :     *)
407 :     val don'tOverwrite =
408 :     if parallelCopies then spillLocsOf reloadRegs
409 :     else []
410 :    
411 :     val instrs = spillAll([instr],spillRegs,killRegs,
412 :     don'tOverwrite)
413 : monnier 498
414 : leunga 744 val _ = if debug then
415 :     (print("pt="^i2s pt^"\n");
416 :     case spillRegs of
417 :     [] => ()
418 :     | _ => (print("Spilling ");
419 :     printRegs spillRegs;
420 :     print "\n");
421 :     case reloadRegs of
422 :     [] => ()
423 :     | _ => (print("Reloading ");
424 :     printRegs reloadRegs;
425 :     print "\n");
426 :     print "Before:"; emit instr
427 :     ) else ()
428 : monnier 498
429 :     val instrs = reloadAll(instrs,reloadRegs)
430 :    
431 : leunga 744 val _ = if debug then
432 :     (print "After:"; app emit instrs;
433 : monnier 498 print "------------------\n")
434 : leunga 744 else ()
435 : george 545
436 : monnier 498 fun concat([], l) = l
437 :     | concat(a::b, l) = concat(b, a::l)
438 :     in loop(rest, dec pt, concat(instrs, newInstrs))
439 :     end
440 :     end
441 :     in loop(rev instrs, pt, [])
442 : monnier 467 end
443 : monnier 498 in spillRewrite
444 : monnier 467 end
445 :     end
446 : leunga 744
447 :     end (* local *)

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