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 499 - (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 :     *
13 :     * -- Allen
14 :     *)
15 : monnier 498 functor RASpill(structure InsnProps : INSN_PROPERTIES
16 :     structure Asm : INSTRUCTION_EMITTER
17 :     sharing InsnProps.I = Asm.I
18 :     ) : RA_SPILL =
19 : monnier 467 struct
20 :    
21 :     structure I = InsnProps.I
22 :     structure P = InsnProps
23 :     structure C = I.C
24 :     structure G = RAGraph
25 :     structure Core = RACore
26 :     structure SL = SortedList
27 :    
28 :     fun error msg = MLRiscErrorMsg.error("RASpill",msg)
29 :    
30 : monnier 498 fun dec n = Word.toIntX(Word.fromInt n - 0w1)
31 :    
32 : monnier 467 type copyInstr =
33 : monnier 498 (C.cell list * C.cell list) * I.instruction -> I.instruction list
34 : monnier 467
35 : monnier 498 (*
36 :     * Spill the value associated with reg into spillLoc.
37 :     * All definitions of instr should be renamed to a new temporary newReg.
38 :     *)
39 : monnier 467 type spill =
40 :     {instr : I.instruction, (* instruction where spill is to occur *)
41 :     reg : C.cell, (* register to spill *)
42 :     spillLoc : int, (* logical spill location *)
43 :     kill : bool, (* can we kill the current node? *)
44 :     regmap : C.cell -> C.cell, (* current register map *)
45 :     annotations : Annotations.annotations ref (* annotations *)
46 :     } ->
47 : monnier 498 {code : I.instruction list, (* instruction + spill code *)
48 : monnier 467 proh : C.cell list, (* prohibited from future spilling *)
49 : monnier 498 newReg : C.cell option (* the spilled value is available here *)
50 : monnier 467 }
51 :    
52 : monnier 498 (* Spill the register src into spillLoc.
53 :     * The value is originally from register reg.
54 :     *)
55 :     type spillSrc =
56 :     {src : C.cell, (* register to spill from *)
57 :     reg : C.cell, (* the register *)
58 :     spillLoc : int, (* logical spill location *)
59 :     annotations : Annotations.annotations ref (* annotations *)
60 :     } -> I.instruction list (* spill code *)
61 :    
62 :     (*
63 :     * Spill the temporary associated with a copy into spillLoc
64 :     *)
65 :     type spillCopyTmp =
66 :     {copy : I.instruction, (* copy to spill *)
67 :     spillLoc : int, (* logical spill location *)
68 :     annotations : Annotations.annotations ref (* annotations *)
69 :     } -> I.instruction (* spill code *)
70 :    
71 :     (*
72 :     * Reload the value associated with reg from spillLoc.
73 :     * All uses of instr should be renamed to a new temporary newReg.
74 :     *)
75 : monnier 467 type reload =
76 :     {instr : I.instruction, (* instruction where spill is to occur *)
77 :     reg : C.cell, (* register to spill *)
78 :     spillLoc : int, (* logical spill location *)
79 :     regmap : C.cell -> C.cell, (* current register map *)
80 :     annotations : Annotations.annotations ref (* annotations *)
81 :     } ->
82 : monnier 498 {code : I.instruction list, (* instr + reload code *)
83 :     proh : C.cell list, (* prohibited from future spilling *)
84 :     newReg : C.cell option (* the reloaded value is here *)
85 : monnier 467 }
86 :    
87 :     (*
88 : monnier 498 * Rename all uses fromSrc to toSrc
89 :     *)
90 :     type renameSrc =
91 :     {instr : I.instruction, (* instruction where spill is to occur *)
92 :     fromSrc : C.cell, (* register to rename *)
93 :     toSrc : C.cell, (* register to rename to *)
94 :     regmap : C.cell -> C.cell (* current register map *)
95 :     } ->
96 :     {code : I.instruction list, (* renamed instr *)
97 :     proh : C.cell list, (* prohibited from future spilling *)
98 :     newReg : C.cell option (* the renamed value is here *)
99 :     }
100 :    
101 :     (* Reload the register dst from spillLoc.
102 :     * The value is originally from register reg.
103 :     *)
104 :     type reloadDst =
105 :     {dst : C.cell, (* register to reload to *)
106 :     reg : C.cell, (* the register *)
107 :     spillLoc : int, (* logical spill location *)
108 :     annotations : Annotations.annotations ref (* annotations *)
109 :     } -> I.instruction list (* reload code *)
110 :    
111 :     (*
112 : monnier 467 * The following function performs spilling.
113 :     *)
114 :     fun spillRewrite
115 :     {graph=G as G.GRAPH{showReg, spilledRegs, nodes,...},
116 : monnier 498 spill : spill,
117 :     spillCopyTmp : spillCopyTmp,
118 :     spillSrc : spillSrc,
119 :     renameSrc : renameSrc,
120 :     reload : reload,
121 :     reloadDst : reloadDst,
122 :     copyInstr : copyInstr,
123 :     cellkind,
124 :     spillSet, reloadSet, killSet
125 :     } =
126 : monnier 467 let
127 :     val regmap = Core.spillRegmap G (* This is the current regmap *)
128 :     val spillLocOf = Core.spillLoc G
129 :     val getnode = Intmap.map nodes
130 :    
131 :     val insnDefUse = P.defUse cellkind
132 :    
133 :     (* Merge prohibited registers *)
134 :     val enterSpill = Intmap.add spilledRegs
135 :     val addProh = app (fn r => enterSpill(r,true))
136 :    
137 : monnier 498 val getSpills : int -> C.cell list = Intmap.mapWithDefault(spillSet,[])
138 :     val getReloads : int -> C.cell list = Intmap.mapWithDefault(reloadSet,[])
139 :     val getKills : int -> C.cell list = Intmap.mapWithDefault(killSet,[])
140 : monnier 467
141 : monnier 475 fun getLoc(G.NODE{color=ref(G.ALIASED n), ...}) = getLoc n
142 : monnier 467 | getLoc(G.NODE{color=ref(G.SPILLED ~1), number, ...}) = number
143 :     | getLoc(G.NODE{color=ref(G.SPILLED c), ...}) = c
144 :     | getLoc(G.NODE{number, ...}) = number
145 :    
146 :     (*
147 : monnier 498 * Rewrite the instruction given that a bunch of registers have
148 :     * to be spilled and reloaded.
149 : monnier 467 *)
150 : monnier 498 fun spillRewrite{pt, instrs, annotations} =
151 :     let
152 :     (*
153 :     * Insert reloading code for an instruction.
154 :     * Note: reload code goes after the instruction, if any.
155 :     *)
156 :     fun reloadInstr(instr,regToSpill,spillLoc) =
157 :     let val {code, proh, newReg} =
158 :     reload{regmap=regmap,instr=instr,reg=regToSpill,
159 :     spillLoc=spillLoc,annotations=annotations}
160 :     in addProh(proh);
161 :     code
162 :     end
163 :    
164 :     (*
165 :     * Renaming the source for an instruction.
166 :     *)
167 :     fun renameInstr(instr,regToSpill,toSrc) =
168 :     let val {code, proh, newReg} =
169 :     renameSrc{regmap=regmap,instr=instr,
170 :     fromSrc=regToSpill,toSrc=toSrc}
171 :     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 :     if regmap rs = regToSpill then
182 :     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 :     * Check whether the regToSpill is in a list
225 :     *)
226 :     fun killable(regToSpill:int,[]) = false
227 :     | killable(regToSpill,r::rs) =
228 :     r = regToSpill orelse killable(regToSpill,rs)
229 :    
230 :     (*
231 :     * Insert spill code for an instruction.
232 :     * Spill code occur after the instruction.
233 :     * If the value in regToSpill is never used, the client also
234 :     * has the opportunity to remove the instruction.
235 :     *)
236 :     fun spillInstr(instr,regToSpill,spillLoc,kill) =
237 :     let val {code, proh, newReg} =
238 :     spill{regmap=regmap, instr=instr,
239 :     kill=kill, spillLoc=spillLoc,
240 :     reg=regToSpill, annotations=annotations}
241 :     in addProh(proh);
242 :     code
243 :     end
244 :    
245 :     (* Remove the definition regToSpill <- from
246 :     * parallel copies rds <- rss.
247 :     * Note, there is a guarantee that regToSpill is not aliased
248 :     * to another register in the rds set.
249 :     *)
250 :     fun extractDef(regToSpill,rds,rss,kill) =
251 :     let fun loop(rd::rds, rs::rss, rds', rss') =
252 :     if spillLocOf rd = spillLocOf rs then
253 :     (rs, rds@rds', rss@rss', true)
254 :     else if regmap rd = regToSpill then
255 :     (rs, rds@rds', rss@rss', kill)
256 :     else loop(rds, rss, rd::rds', rs::rss')
257 :     | loop _ =
258 :     (print("rds=");
259 :     app (fn r => print(Int.toString r^":"^
260 :     Int.toString(spillLocOf r)^" ")) rds;
261 :     print("\nrss=");
262 :     app (fn r => print(Int.toString r^":"^
263 :     Int.toString(spillLocOf r)^" ")) rss;
264 :     print "\n";
265 :     error("extractDef: "^Int.toString regToSpill))
266 :     in loop(rds, rss, [], []) end
267 :    
268 :     (*
269 :     * Insert spill code for a destination of a copy
270 :     * d1...dn <- s1...sn
271 :     * =>
272 :     * spill code
273 :     * d1...dn/r <- s1...sn/r
274 :     *
275 :     *)
276 :     fun spillCopyDst(instr,regToSpill,spillLoc,kill) =
277 :     let val (dst, src) = P.moveDstSrc instr
278 :     val (mvSrc,copyDst,copySrc,kill) =
279 :     extractDef(regToSpill,dst,src,kill)
280 :     val copy = case copyDst of
281 :     [] => []
282 :     | _ => copyInstr((copyDst,copySrc),instr)
283 :     in if kill
284 :     then (* kill the move *)
285 :     ((* print ("Copy "^Int.toString(hd mvDst)^" <- "^
286 :     Int.toString(hd mvSrc)^" removed\n"); *)
287 :     copy
288 :     )
289 :     else (* normal spill *)
290 :     let (* spill the move instruction *)
291 :     val spillCode = spillSrc{src=mvSrc,reg=regToSpill,
292 :     spillLoc=spillLoc,
293 :     annotations=annotations}
294 :     in spillCode @ copy
295 : monnier 467 end
296 :     end
297 : monnier 498
298 :     (*
299 :     * Insert spill code for a copy
300 :     *)
301 :     fun spillCopy(instr,regToSpill,spillLoc,kill) =
302 :     case P.moveTmpR instr of
303 :     NONE => spillCopyDst(instr,regToSpill,spillLoc,kill)
304 :     | SOME tmp =>
305 :     if regmap tmp = regToSpill
306 :     then [spillCopyTmp{copy=instr, spillLoc=spillLoc,
307 :     annotations=annotations}]
308 :     else spillCopyDst(instr,regToSpill,spillLoc,kill)
309 :    
310 :     (*
311 :     * Insert spill code
312 :     *)
313 :     fun spill(instr,regToSpill,spillLoc,killSet) =
314 :     let val kill = killable(regToSpill,killSet)
315 :     in if P.moveInstr instr then
316 :     spillCopy(instr,regToSpill,spillLoc,kill)
317 :     else
318 :     spillInstr(instr,regToSpill,spillLoc,kill)
319 :     end
320 : monnier 467
321 : monnier 498 fun contains([],reg) = false
322 : monnier 467 | contains(r::rs,reg) = regmap r = reg orelse contains(rs,reg)
323 :     fun hasDef(i,reg) = contains(#1(insnDefUse i),reg)
324 :     fun hasUse(i,reg) = contains(#2(insnDefUse i),reg)
325 :    
326 : monnier 475 fun spillOneReg([],_,_,killSet) = []
327 :     | spillOneReg(i::instrs,r,spillLoc,killSet) =
328 : monnier 467 if hasDef(i,r)
329 :     then
330 : monnier 498 spillOneReg(spill(i,r,spillLoc,killSet)@instrs,
331 : monnier 475 r,spillLoc,killSet)
332 :     else i::spillOneReg(instrs,r,spillLoc,killSet)
333 : monnier 467
334 : monnier 475 fun reloadOneReg([],_,_) = []
335 :     | reloadOneReg(i::instrs,r,spillLoc) =
336 : monnier 467 if hasUse(i,r)
337 : monnier 498 then reloadOneReg(reload(i,r,spillLoc)@instrs,
338 : monnier 475 r,spillLoc)
339 :     else i::reloadOneReg(instrs,r,spillLoc)
340 : monnier 467
341 :     (* This function spills a set of registers for an instruction *)
342 :     fun spillAll(instrs,[],killSet) = instrs
343 :     | spillAll(instrs,r::rs,killSet) =
344 :     let val node = getnode r
345 :     val spillLoc = getLoc node
346 : monnier 475 in spillAll(spillOneReg(instrs,r,spillLoc,killSet),
347 : monnier 467 rs,killSet)
348 :     end
349 :    
350 :     (* This function reloads a set of registers for an instruction *)
351 :     fun reloadAll(instrs,[]) = instrs
352 :     | reloadAll(instrs,r::rs) =
353 :     let val node = getnode r
354 :     val spillLoc = getLoc node
355 : monnier 475 in reloadAll(reloadOneReg(instrs,r,spillLoc),rs)
356 : monnier 467 end
357 :    
358 : monnier 498 fun loop([], pt, newInstrs) = newInstrs
359 :     | loop(instr::rest, pt, newInstrs) =
360 :     let val spillRegs = getSpills pt
361 :     val reloadRegs = getReloads pt
362 :     in case (spillRegs, reloadRegs) of
363 :     ([], []) => loop(rest, dec pt, instr::newInstrs)
364 :     | _ =>
365 :     (* Eliminate duplicates from the spill/reload candidates *)
366 :     let val killRegs = getKills pt
367 :     val spillRegs = SL.uniq spillRegs
368 :     val reloadRegs = SL.uniq reloadRegs
369 : monnier 467
370 : monnier 498 (*
371 :     val Asm.S.STREAM{emit, ...} = Asm.makeStream[]
372 :     val regs = app (fn r =>
373 :     print(Int.toString r^" ["^Int.toString
374 :     (getLoc (getnode r))^"] "))
375 :     *)
376 :    
377 :     val instrs = spillAll([instr],spillRegs,killRegs)
378 :    
379 :     (*
380 :     val _ =
381 :     (print("pt="^Int.toString pt^"\n");
382 :     if spillRegs = [] then () else
383 :     (print("Spilling ");
384 :     regs spillRegs; print "\n");
385 :     if reloadRegs = [] then () else
386 :     (print("Reloading ");
387 :     regs reloadRegs; print "\n");
388 :     print "Before:"; emit regmap instr)
389 :     *)
390 :    
391 :     val instrs = reloadAll(instrs,reloadRegs)
392 :    
393 :     (*
394 :     val _ =
395 :     (print "After:"; app (emit regmap) instrs;
396 :     print "------------------\n")
397 :     *)
398 :     fun concat([], l) = l
399 :     | concat(a::b, l) = concat(b, a::l)
400 :     in loop(rest, dec pt, concat(instrs, newInstrs))
401 :     end
402 :     end
403 :     in loop(rev instrs, pt, [])
404 : monnier 467 end
405 : monnier 498 in spillRewrite
406 : monnier 467 end
407 :    
408 :     end

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