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/risc-ra.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 823 - (view) (download)

1 : leunga 744 (*
2 :     * This functor factors out the machine independent part of the register
3 :     * allocator. It performs integer and floating register allocation.
4 :     * This works well for RISC machines; but not applicable to x86.
5 :     *)
6 :     functor RISC_RA
7 :     (structure I : INSTRUCTIONS
8 :     structure Flowgraph : FLOWGRAPH
9 :     structure InsnProps : INSN_PROPERTIES
10 :     structure Rewrite : REWRITE_INSTRUCTIONS
11 :     structure Asm : INSTRUCTION_EMITTER
12 :    
13 :     (* Spilling heuristics determines which node should be spilled.
14 :     * You can use Chaitin, ChowHenessey, or one of your own.
15 :     *)
16 :     structure SpillHeur : RA_SPILL_HEURISTICS
17 :    
18 :     (* The Spill module figures out the strategies for inserting
19 :     * spill code. You can use RASpill, or RASpillWithRenaming,
20 :     * or write your own if you are feeling adventurous.
21 :     *)
22 :     structure Spill : RA_SPILL where I = I
23 :    
24 :     sharing InsnProps.I = Flowgraph.I = Asm.I = Rewrite.I = I
25 :     sharing Asm.P = Flowgraph.P
26 :    
27 :     val architecture : string
28 :    
29 :     (* Is this a pure instruction *)
30 :     val pure : I.instruction -> bool
31 :    
32 :     (* Called before RA begins *)
33 :     val beginRA : unit -> unit
34 :    
35 :     structure Int :
36 :     sig
37 :    
38 :     val avail : I.C.cell list (* list of available registers *)
39 :     val dedicated : I.C.cell list (* list of registers that are dedicated *)
40 :    
41 :     (* This functions is used to create copy instructions.
42 :     * Given dst/src lists, return a new copy instruction with the same
43 :     * temporary as the old one.
44 :     *)
45 :     val copy : (I.C.cell list * I.C.cell list) * I.instruction ->
46 :     I.instruction
47 :    
48 :     (* This function is used to spill the temporary used in the copy
49 :     * onto some stack offset.
50 :     *)
51 :     val spillCopyTmp : Annotations.annotations ref * I.instruction *
52 :     RAGraph.spillLoc -> I.instruction
53 :    
54 :     (* This function is used to spill a register onto some stack offset
55 :     *)
56 : leunga 796 val spillInstr : {an:Annotations.annotations ref, src:I.C.cell,
57 :     spilledCell:I.C.cell, spillLoc:RAGraph.spillLoc}
58 :     -> I.instruction list
59 :    
60 : leunga 744 (*
61 :     * This function is used to reload a register from some stack offset
62 :     *)
63 : leunga 796 val reloadInstr : {an:Annotations.annotations ref, dst:I.C.cell,
64 :     spilledCell:I.C.cell, spillLoc:RAGraph.spillLoc}
65 :     -> I.instruction list
66 :    
67 :     (* Mode for RA optimizations *)
68 :     val mode : RAGraph.mode
69 : leunga 744 end
70 :    
71 :     structure Float :
72 :     sig
73 :    
74 :     val avail : I.C.cell list (* list of available registers *)
75 :     val dedicated : I.C.cell list (* list of registers that are dedicated *)
76 :    
77 :     (* This functions is used to create copy instructions.
78 :     * Given dst/src lists, return a new copy instruction with the same
79 :     * temporary as the old one.
80 :     *)
81 :     val copy : (I.C.cell list * I.C.cell list) * I.instruction ->
82 :     I.instruction
83 :    
84 :     (* This function is used to spill the temporary used in the copy
85 :     * onto some stack offset.
86 :     *)
87 :     val spillCopyTmp : Annotations.annotations ref * I.instruction *
88 :     RAGraph.spillLoc -> I.instruction
89 :    
90 :     (* This function is used to spill a register onto some stack offset
91 :     * The
92 :     *)
93 :     val spillInstr : Annotations.annotations ref * I.C.cell *
94 :     RAGraph.spillLoc -> I.instruction list
95 :     (*
96 :     * This function is used to reload a register from some stack offset,
97 :     * and concatenate the reload code with the given instruction list.
98 :     *)
99 :     val reloadInstr : Annotations.annotations ref * I.C.cell *
100 :     RAGraph.spillLoc -> I.instruction list
101 : leunga 796
102 :     (* Mode for RA optimizations *)
103 :     val mode : RAGraph.mode
104 : leunga 744 end
105 :     ) : CLUSTER_OPTIMIZATION =
106 :     struct
107 :    
108 :     structure F = Flowgraph
109 :     structure I = F.I
110 :     structure P = InsnProps
111 :     structure C = I.C
112 :     structure G = RAGraph
113 :    
114 :     type flowgraph = F.cluster
115 :    
116 :     val name = "RISC_RA"
117 :    
118 :     (* Counters for register allocation *)
119 :     val intSpillsCnt = MLRiscControl.getCounter "ra-int-spills"
120 :     val intReloadsCnt = MLRiscControl.getCounter "ra-int-reloads"
121 :     val intRenamesCnt = MLRiscControl.getCounter "ra-int-renames"
122 :     val floatSpillsCnt = MLRiscControl.getCounter "ra-float-spills"
123 :     val floatReloadsCnt = MLRiscControl.getCounter "ra-float-reloads"
124 :     val floatRenamesCnt = MLRiscControl.getCounter "ra-float-renames"
125 :    
126 :     fun error msg = MLRiscErrorMsg.error("RISC RA "^architecture,msg)
127 :    
128 :     (*
129 :     * Make arithmetic non-overflow trapping.
130 :     * This makes sure that if we happen to run the compiler for a long
131 :     * period of time overflowing counters will not crash the compiler.
132 :     *)
133 :     fun x + y = Word.toIntX(Word.+(Word.fromInt x, Word.fromInt y))
134 :     fun x - y = Word.toIntX(Word.-(Word.fromInt x, Word.fromInt y))
135 :    
136 :     (* GetReg specialized to integer and floating point registers *)
137 : george 823 fun isDedicated (len, arr, others) r =
138 :     (r < len andalso Array.sub(arr, r)) orelse List.exists (fn d => r = d) others
139 :    
140 :     fun mark(arr, _, [], others) = others
141 :     | mark(arr, len, r::rs, others) = let
142 :     val r = C.registerId r
143 :     in
144 :     if r >= len then mark(arr, len, rs, r::others)
145 :     else (Array.update(arr, r, true); mark(arr, len, rs, others))
146 :     end
147 :    
148 :    
149 :    
150 : leunga 744 local
151 : george 823 val {low,high} = C.cellRange C.GP
152 :     val arr = Array.array(high+1,false)
153 :     val others = mark(arr, high+1, Int.dedicated, [])
154 : leunga 744 in
155 :     structure GR = GetReg(val first=low val nRegs=high-low+1
156 :     val available=map C.registerId Int.avail)
157 : george 823 val dedicatedR : int -> bool = isDedicated (high+1, arr, others)
158 : leunga 744 end
159 :     local
160 :     val {low,high} = C.cellRange C.FP
161 : george 823 val arr = Array.array(high+1,false)
162 :     val others = mark(arr, high+1, Float.dedicated, [])
163 : leunga 744 in
164 :     structure FR = GetReg(val first=low val nRegs=high-low+1
165 :     val available=map C.registerId Float.avail)
166 : george 823 val dedicatedF : int -> bool = isDedicated(high+1, arr, others)
167 : leunga 744 end
168 :    
169 :     (* Spill integer register *)
170 :     fun spillR{annotations,kill=true,reg,spillLoc,instr} =
171 :     if pure instr then {code=[], proh=[], newReg=NONE}
172 :     else spillR{annotations=annotations,kill=false,
173 :     spillLoc=spillLoc,
174 :     reg=reg,instr=instr}
175 :     | spillR{annotations,kill,reg,spillLoc,instr} =
176 :     let val _ = intSpillsCnt := !intSpillsCnt + 1
177 :     val newR = C.newReg()
178 :     val instr' = Rewrite.rewriteDef(instr, reg, newR)
179 : leunga 796 in {code=instr'::Int.spillInstr{an=annotations,src=newR,
180 :     spilledCell=reg,spillLoc=spillLoc},
181 : leunga 744 proh=[newR], newReg=SOME newR}
182 :     end
183 :    
184 :     fun spillReg{annotations,src,reg,spillLoc} =
185 :     (intSpillsCnt := !intSpillsCnt + 1;
186 : leunga 796 Int.spillInstr{an=annotations,src=src,spilledCell=reg,
187 :     spillLoc=spillLoc}
188 : leunga 744 )
189 :    
190 : leunga 815 fun spillTmp{annotations,reg,copy,spillLoc} =
191 : leunga 744 (intSpillsCnt := !intSpillsCnt + 1;
192 :     Int.spillCopyTmp(annotations,copy,spillLoc)
193 :     )
194 :    
195 :     (* Spill floating point register *)
196 :     fun spillF{annotations,kill=true,reg,spillLoc,instr} =
197 :     if pure instr then {code=[], proh=[], newReg=NONE}
198 :     else spillF{annotations=annotations,kill=false,
199 :     spillLoc=spillLoc, reg=reg,instr=instr}
200 :     | spillF{annotations,kill,reg,spillLoc,instr} =
201 :     let val _ = floatSpillsCnt := !floatSpillsCnt + 1
202 :     val newR = C.newFreg()
203 :     val instr' = Rewrite.frewriteDef(instr, reg, newR)
204 :     in {code=instr'::Float.spillInstr(annotations,newR,spillLoc),
205 :     proh=[newR], newReg=SOME newR}
206 :     end
207 :    
208 :     fun spillFreg{annotations,reg,src,spillLoc} =
209 :     (floatSpillsCnt := !floatSpillsCnt + 1;
210 :     Float.spillInstr(annotations,src,spillLoc)
211 :     )
212 :    
213 : leunga 815 fun spillFtmp{annotations,reg,copy,spillLoc} =
214 : leunga 744 (floatSpillsCnt := !floatSpillsCnt + 1;
215 :     Float.spillCopyTmp(annotations,copy,spillLoc)
216 :     )
217 :    
218 :     (* Rename integer register *)
219 :     fun renameR{fromSrc,toSrc,instr} =
220 :     let val _ = intRenamesCnt := !intRenamesCnt + 1
221 :     val instr' = Rewrite.rewriteUse(instr, fromSrc, toSrc)
222 :     in {code=[instr'], proh=[], newReg=SOME toSrc}
223 :     end
224 :    
225 :     (* Reload integer register *)
226 :     fun reloadR{annotations,reg,spillLoc,instr} =
227 :     let val _ = intReloadsCnt := !intReloadsCnt + 1
228 :     val newR = C.newReg()
229 :     val instr' = Rewrite.rewriteUse(instr, reg, newR)
230 : leunga 796 in {code=Int.reloadInstr{an=annotations,dst=newR,spilledCell=reg,
231 :     spillLoc=spillLoc} @ [instr'],
232 : leunga 744 proh=[newR], newReg=SOME newR}
233 :     end
234 :    
235 :     fun reloadReg{annotations,reg,dst,spillLoc} =
236 :     (intReloadsCnt := !intReloadsCnt + 1;
237 : leunga 796 Int.reloadInstr{an=annotations,dst=dst,spilledCell=reg,
238 :     spillLoc=spillLoc}
239 : leunga 744 )
240 :    
241 :     (* Rename floating point register *)
242 :     fun renameF{fromSrc,toSrc,instr} =
243 :     let val _ = floatRenamesCnt := !floatRenamesCnt + 1
244 :     val instr' = Rewrite.frewriteUse(instr, fromSrc, toSrc)
245 :     in {code=[instr'], proh=[], newReg=SOME toSrc}
246 :     end
247 :    
248 :     (* Reload floating point register *)
249 :     fun reloadF{annotations,reg,spillLoc,instr} =
250 :     let val _ = floatReloadsCnt := !floatReloadsCnt + 1
251 :     val newR = C.newFreg()
252 :     val instr' = Rewrite.frewriteUse(instr, reg, newR)
253 :     in {code=Float.reloadInstr(annotations,newR,spillLoc) @ [instr'],
254 :     proh=[newR], newReg=SOME newR}
255 :     end
256 :    
257 :     fun reloadFreg{annotations,reg,dst,spillLoc} =
258 :     (floatReloadsCnt := !floatReloadsCnt + 1;
259 :     Float.reloadInstr(annotations,dst,spillLoc)
260 :     )
261 :    
262 :     (* The generic register allocator *)
263 :     structure Ra =
264 :     RegisterAllocator
265 :     (SpillHeur)
266 :     (* (ChowHennessySpillHeur) *)
267 :     (ClusterRA
268 :     (structure Flowgraph = F
269 :     structure Asm = Asm
270 :     structure InsnProps = InsnProps
271 :     structure Spill = Spill
272 :     )
273 :     )
274 :    
275 :     val KR = length Int.avail
276 :     val KF = length Float.avail
277 :    
278 :     val params =
279 :     [ { cellkind = I.C.GP,
280 :     getreg = GR.getreg,
281 :     spill = spillR,
282 :     spillSrc = spillReg,
283 :     spillCopyTmp = spillTmp,
284 :     reload = reloadR,
285 :     reloadDst = reloadReg,
286 :     renameSrc = renameR,
287 :     K = KR,
288 :     dedicated = dedicatedR,
289 :     copyInstr = fn i => [Int.copy i],
290 :     spillProh = [],
291 :     memRegs = [],
292 : leunga 796 mode = Int.mode
293 : leunga 744 } : Ra.raClient,
294 :     { cellkind = I.C.FP,
295 :     getreg = FR.getreg,
296 :     spill = spillF,
297 :     spillSrc = spillFreg,
298 :     spillCopyTmp = spillFtmp,
299 :     reload = reloadF,
300 :     reloadDst = reloadFreg,
301 :     renameSrc = renameF,
302 :     K = KF,
303 :     dedicated = dedicatedF,
304 :     copyInstr = fn i => [Float.copy i],
305 :     spillProh = [],
306 :     memRegs = [],
307 : leunga 796 mode = Float.mode
308 : leunga 744 } : Ra.raClient
309 :     ] : Ra.raClient list
310 :    
311 :     fun run cluster =
312 :     (beginRA();
313 :     GR.reset();
314 :     FR.reset();
315 :     Ra.ra params cluster
316 :     )
317 :    
318 :     end
319 : leunga 796

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