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

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