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 467 - (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 :     * and reload. We write the instruction until all instances of these
11 :     * registers are rewritten.
12 :     *
13 :     * -- Allen
14 :     *)
15 :     functor RASpill(InsnProps : INSN_PROPERTIES) : RA_SPILL =
16 :     struct
17 :    
18 :     structure I = InsnProps.I
19 :     structure P = InsnProps
20 :     structure C = I.C
21 :     structure G = RAGraph
22 :     structure Core = RACore
23 :     structure SL = SortedList
24 :    
25 :     fun error msg = MLRiscErrorMsg.error("RASpill",msg)
26 :    
27 :     type copyInstr =
28 :     (C.cell list * C.cell list) * I.instruction -> I.instruction
29 :    
30 :     type spill =
31 :     {instr : I.instruction, (* instruction where spill is to occur *)
32 :     reg : C.cell, (* register to spill *)
33 :     spillLoc : int, (* logical spill location *)
34 :     node : RAGraph.node, (* the current node *)
35 :     kill : bool, (* can we kill the current node? *)
36 :     regmap : C.cell -> C.cell, (* current register map *)
37 :     annotations : Annotations.annotations ref (* annotations *)
38 :     } ->
39 :     {code : I.instruction list, (* spill code *)
40 :     proh : C.cell list, (* prohibited from future spilling *)
41 :     instr : I.instruction option (* possibly changed instruction *)
42 :     }
43 :    
44 :     type reload =
45 :     {instr : I.instruction, (* instruction where spill is to occur *)
46 :     reg : C.cell, (* register to spill *)
47 :     spillLoc : int, (* logical spill location *)
48 :     node : RAGraph.node, (* the current node *)
49 :     regmap : C.cell -> C.cell, (* current register map *)
50 :     annotations : Annotations.annotations ref (* annotations *)
51 :     } ->
52 :     {code : I.instruction list, (* reload code *)
53 :     proh : C.cell list (* prohibited from future spilling *)
54 :     }
55 :    
56 :     (*
57 :     * The following function performs spilling.
58 :     *)
59 :     fun spillRewrite
60 :     {graph=G as G.GRAPH{showReg, spilledRegs, nodes,...},
61 :     spill, reload, copyInstr, cellkind} =
62 :     let
63 :     val regmap = Core.spillRegmap G (* This is the current regmap *)
64 :     val spillLocOf = Core.spillLoc G
65 :     val getnode = Intmap.map nodes
66 :    
67 :     val insnDefUse = P.defUse cellkind
68 :    
69 :     (* Merge prohibited registers *)
70 :     val enterSpill = Intmap.add spilledRegs
71 :     val addProh = app (fn r => enterSpill(r,true))
72 :    
73 :     fun add(NONE,l) = l
74 :     | add(SOME i,l) = i::l
75 :    
76 :    
77 :     fun getLoc(G.NODE{color=ref(G.ALIASED_SPILL n), ...}) = getLoc n
78 :     | getLoc(G.NODE{color=ref(G.SPILLED ~1), number, ...}) = number
79 :     | getLoc(G.NODE{color=ref(G.SPILLED c), ...}) = c
80 :     | getLoc(G.NODE{number, ...}) = number
81 :    
82 :     (*
83 :     * Insert reloading code for an instruction.
84 :     * Note: reload code goes after the instruction, if any.
85 :     *)
86 :     fun reloadInstr(instr,spillReg,spillLoc,node,annotations) =
87 :     let val {code,proh} =
88 :     reload{regmap=regmap,instr=instr,reg=spillReg,
89 :     spillLoc=spillLoc,node=node,annotations=annotations}
90 :     in addProh(proh);
91 :     code
92 :     end
93 :    
94 :     (*
95 :     * Remove uses of spillReg from a set of parallel copies.
96 :     * If there are multiple uses, then return multiple moves.
97 :     *)
98 :     fun extractUses(spillReg, rds, rss) =
99 :     let fun loop(rd::rds, rs::rss, newMvs, rds', rss') =
100 :     if regmap rs = spillReg then
101 :     loop(rds, rss, ([rd], [rs])::newMvs, rds', rss')
102 :     else
103 :     loop(rds, rss, newMvs, rd::rds', rs::rss')
104 :     | loop(_, _, newMvs, rds', rss') = (newMvs, rds', rss')
105 :     in loop(rds, rss, [], [], []) end
106 :    
107 :     (*
108 :     * Insert reload code for the sources of a copy.
109 :     * Transformation:
110 :     * d1..dn <- s1..sn
111 :     * =>
112 :     * d1..dn/r <- s1...sn/r.
113 :     * reload code
114 :     * reload copies
115 :     *
116 :     *)
117 :     fun reloadCopySrc(instr,dst,src,spillReg,spillLoc,node,annotations) =
118 :     let val (mvs, copyDst, copySrc) = extractUses(spillReg, dst, src)
119 :     fun processMoves([], reloadCode) = reloadCode
120 :     | processMoves(mv::mvs, reloadCode) =
121 :     let val mv = copyInstr(mv, instr)
122 :     val {code, proh} =
123 :     reload{regmap=regmap,instr=mv,spillLoc=spillLoc,
124 :     node=node,reg=spillReg,annotations=annotations}
125 :     in addProh(proh);
126 :     processMoves(mvs, code@reloadCode)
127 :     end
128 :     val reloadCode = processMoves(mvs, [])
129 :     in case copyDst of
130 :     [] => reloadCode
131 :     | _ => copyInstr((copyDst, copySrc), instr)::reloadCode
132 :     end
133 :    
134 :     (*
135 :     * Insert reload code
136 :     *)
137 :     fun reload(instr,spillReg,spillLoc,node,annotations) =
138 :     if P.moveInstr instr then
139 :     let val (dst,src) = P.moveDstSrc instr
140 :     in case dst of
141 :     [_] => reloadInstr(instr,spillReg,spillLoc,node,annotations)
142 :     | _ => reloadCopySrc(instr,dst,src,spillReg,
143 :     spillLoc,node,annotations)
144 :     end
145 :     else
146 :     reloadInstr(instr,spillReg,spillLoc,node,annotations)
147 :    
148 :     (*
149 :     * Check whether the spillReg is in a list
150 :     *)
151 :     fun killable(spillReg:int,[]) = false
152 :     | killable(spillReg,r::rs) = r = spillReg orelse killable(spillReg,rs)
153 :    
154 :     (*
155 :     * Insert spill code for an instruction.
156 :     * Spill code occur after the instruction.
157 :     * If the value in spillReg is never used, the client also
158 :     * has the opportunity to remove the instruction.
159 :     *)
160 :     fun spillInstr(instr,spillReg,spillLoc,node,annotations,kill) =
161 :     let val {code, instr, proh} =
162 :     spill{regmap=regmap, instr=instr,
163 :     node=node, kill=kill, spillLoc=spillLoc,
164 :     reg=spillReg, annotations=annotations}
165 :     in addProh(proh);
166 :     add(instr,code)
167 :     end
168 :    
169 :     (* Remove the definition spillReg <- from
170 :     * parallel copies rds <- rss.
171 :     * Note, there is a guarantee that spillReg is not aliased
172 :     * to another register in the rds set.
173 :     *)
174 :     fun extractDef(spillReg,rds,rss,kill) =
175 :     let fun loop(rd::rds, rs::rss, rds', rss') =
176 :     if spillLocOf rd = spillLocOf rs then
177 :     ([rd], [rs], rds@rds', rss@rss', true)
178 :     else if regmap rd = spillReg then
179 :     ([rd], [rs], rds@rds', rss@rss', kill)
180 :     else loop(rds, rss, rd::rds', rs::rss')
181 :     | loop _ = error "extractDef"
182 :     in loop(rds, rss, [], []) end
183 :    
184 :     (*
185 :     * Insert spill code for a destination of a copy
186 :     * d1...dn <- s1...sn
187 :     * =>
188 :     * spill code
189 :     * d1...dn/r <- s1...sn/r
190 :     *
191 :     *)
192 :     fun spillCopyDst(instr,spillReg,spillLoc,node,annotations,kill) =
193 :     let val (dst, src) = P.moveDstSrc instr
194 :     val (mvDst,mvSrc,copyDst,copySrc,kill) =
195 :     extractDef(spillReg,dst,src,kill)
196 :     val copy = copyInstr((copyDst,copySrc),instr)
197 :     in if kill
198 :     then (* kill the move *)
199 :     ((* print ("Copy "^Int.toString(hd mvDst)^" <- "^
200 :     Int.toString(hd mvSrc)^" removed\n"); *)
201 :     [copy]
202 :     )
203 :     else (* normal spill *)
204 :     let val mvInstr = copyInstr((mvDst,mvSrc),instr)
205 :     (* spill the move instruction *)
206 :     val spillCode = spillInstr(mvInstr,spillReg,spillLoc,
207 :     node,annotations,false)
208 :     in spillCode @ [copy]
209 :     end
210 :     end
211 :    
212 :     (*
213 :     * Insert spill code for a copy
214 :     *)
215 :     fun spillCopy(instr,spillReg,spillLoc,node,annotations,kill) =
216 :     case P.moveTmpR instr of
217 :     NONE => spillCopyDst(instr,spillReg,spillLoc,node,annotations,kill)
218 :     | SOME tmp =>
219 :     if regmap tmp = spillReg
220 :     then spillInstr(instr,spillReg,spillLoc,node,annotations,false)
221 :     else spillCopyDst(instr,spillReg,spillLoc,node,annotations,kill)
222 :    
223 :     (*
224 :     * Insert spill code
225 :     *)
226 :     fun spill(instr,spillReg,spillLoc,node,annotations,killSet) =
227 :     let val kill = killable(spillReg,killSet)
228 :     in if P.moveInstr instr then
229 :     spillCopy(instr,spillReg,spillLoc,node,annotations,kill)
230 :     else
231 :     spillInstr(instr,spillReg,spillLoc,node,annotations,kill)
232 :     end
233 :    
234 :     (*
235 :     * Rewrite the instruction given that a bunch of registers have
236 :     * to be spilled and reloaded.
237 :     *)
238 :     fun rewrite{spillRegs,reloadRegs,killRegs,instr,annotations} =
239 :     let fun contains([],reg) = false
240 :     | contains(r::rs,reg) = regmap r = reg orelse contains(rs,reg)
241 :     fun hasDef(i,reg) = contains(#1(insnDefUse i),reg)
242 :     fun hasUse(i,reg) = contains(#2(insnDefUse i),reg)
243 :    
244 :     fun spillOneReg([],_,_,_,killSet) = []
245 :     | spillOneReg(i::instrs,r,spillLoc,node,killSet) =
246 :     if hasDef(i,r)
247 :     then
248 :     spillOneReg(spill(i,r,spillLoc,node,annotations,killSet)@instrs,
249 :     r,spillLoc,node,killSet)
250 :     else i::spillOneReg(instrs,r,spillLoc,node,killSet)
251 :    
252 :     fun reloadOneReg([],_,_,_) = []
253 :     | reloadOneReg(i::instrs,r,spillLoc,node) =
254 :     if hasUse(i,r)
255 :     then reloadOneReg(reload(i,r,spillLoc,node,annotations)@instrs,
256 :     r,spillLoc,node)
257 :     else i::reloadOneReg(instrs,r,spillLoc,node)
258 :    
259 :     (* This function spills a set of registers for an instruction *)
260 :     fun spillAll(instrs,[],killSet) = instrs
261 :     | spillAll(instrs,r::rs,killSet) =
262 :     let val node = getnode r
263 :     val spillLoc = getLoc node
264 :     in spillAll(spillOneReg(instrs,r,spillLoc,node,killSet),
265 :     rs,killSet)
266 :     end
267 :    
268 :     (* This function reloads a set of registers for an instruction *)
269 :     fun reloadAll(instrs,[]) = instrs
270 :     | reloadAll(instrs,r::rs) =
271 :     let val node = getnode r
272 :     val spillLoc = getLoc node
273 :     in reloadAll(reloadOneReg(instrs,r,spillLoc,node),rs)
274 :     end
275 :    
276 :     (* Eliminate duplicates from the spill/reload candidates *)
277 :     val spillRegs = SL.uniq spillRegs
278 :     val reloadRegs = SL.uniq reloadRegs
279 :    
280 :     val instrs = spillAll([instr],spillRegs,killRegs)
281 :     val instrs = reloadAll(instrs,reloadRegs)
282 :     in { code = instrs }
283 :     end
284 :     in rewrite
285 :     end
286 :    
287 :     end

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