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 815 - (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 :     local
138 :     val {low,high} = C.cellRange C.GP
139 :     in
140 :     structure GR = GetReg(val first=low val nRegs=high-low+1
141 :     val available=map C.registerId Int.avail)
142 :     val dedicatedR = Array.array(high+1,false)
143 :     val _ = app (fn r => Array.update(dedicatedR,C.registerId r,true))
144 :     Int.dedicated
145 :    
146 :     end
147 :     local
148 :     val {low,high} = C.cellRange C.FP
149 :     in
150 :     structure FR = GetReg(val first=low val nRegs=high-low+1
151 :     val available=map C.registerId Float.avail)
152 :     val dedicatedF = Array.array(high+1,false)
153 :     val _ = app (fn r => Array.update(dedicatedF,C.registerId r,true))
154 :     Float.dedicated
155 :     end
156 :    
157 :     (* Spill integer register *)
158 :     fun spillR{annotations,kill=true,reg,spillLoc,instr} =
159 :     if pure instr then {code=[], proh=[], newReg=NONE}
160 :     else spillR{annotations=annotations,kill=false,
161 :     spillLoc=spillLoc,
162 :     reg=reg,instr=instr}
163 :     | spillR{annotations,kill,reg,spillLoc,instr} =
164 :     let val _ = intSpillsCnt := !intSpillsCnt + 1
165 :     val newR = C.newReg()
166 :     val instr' = Rewrite.rewriteDef(instr, reg, newR)
167 : leunga 796 in {code=instr'::Int.spillInstr{an=annotations,src=newR,
168 :     spilledCell=reg,spillLoc=spillLoc},
169 : leunga 744 proh=[newR], newReg=SOME newR}
170 :     end
171 :    
172 :     fun spillReg{annotations,src,reg,spillLoc} =
173 :     (intSpillsCnt := !intSpillsCnt + 1;
174 : leunga 796 Int.spillInstr{an=annotations,src=src,spilledCell=reg,
175 :     spillLoc=spillLoc}
176 : leunga 744 )
177 :    
178 : leunga 815 fun spillTmp{annotations,reg,copy,spillLoc} =
179 : leunga 744 (intSpillsCnt := !intSpillsCnt + 1;
180 :     Int.spillCopyTmp(annotations,copy,spillLoc)
181 :     )
182 :    
183 :     (* Spill floating point register *)
184 :     fun spillF{annotations,kill=true,reg,spillLoc,instr} =
185 :     if pure instr then {code=[], proh=[], newReg=NONE}
186 :     else spillF{annotations=annotations,kill=false,
187 :     spillLoc=spillLoc, reg=reg,instr=instr}
188 :     | spillF{annotations,kill,reg,spillLoc,instr} =
189 :     let val _ = floatSpillsCnt := !floatSpillsCnt + 1
190 :     val newR = C.newFreg()
191 :     val instr' = Rewrite.frewriteDef(instr, reg, newR)
192 :     in {code=instr'::Float.spillInstr(annotations,newR,spillLoc),
193 :     proh=[newR], newReg=SOME newR}
194 :     end
195 :    
196 :     fun spillFreg{annotations,reg,src,spillLoc} =
197 :     (floatSpillsCnt := !floatSpillsCnt + 1;
198 :     Float.spillInstr(annotations,src,spillLoc)
199 :     )
200 :    
201 : leunga 815 fun spillFtmp{annotations,reg,copy,spillLoc} =
202 : leunga 744 (floatSpillsCnt := !floatSpillsCnt + 1;
203 :     Float.spillCopyTmp(annotations,copy,spillLoc)
204 :     )
205 :    
206 :     (* Rename integer register *)
207 :     fun renameR{fromSrc,toSrc,instr} =
208 :     let val _ = intRenamesCnt := !intRenamesCnt + 1
209 :     val instr' = Rewrite.rewriteUse(instr, fromSrc, toSrc)
210 :     in {code=[instr'], proh=[], newReg=SOME toSrc}
211 :     end
212 :    
213 :     (* Reload integer register *)
214 :     fun reloadR{annotations,reg,spillLoc,instr} =
215 :     let val _ = intReloadsCnt := !intReloadsCnt + 1
216 :     val newR = C.newReg()
217 :     val instr' = Rewrite.rewriteUse(instr, reg, newR)
218 : leunga 796 in {code=Int.reloadInstr{an=annotations,dst=newR,spilledCell=reg,
219 :     spillLoc=spillLoc} @ [instr'],
220 : leunga 744 proh=[newR], newReg=SOME newR}
221 :     end
222 :    
223 :     fun reloadReg{annotations,reg,dst,spillLoc} =
224 :     (intReloadsCnt := !intReloadsCnt + 1;
225 : leunga 796 Int.reloadInstr{an=annotations,dst=dst,spilledCell=reg,
226 :     spillLoc=spillLoc}
227 : leunga 744 )
228 :    
229 :     (* Rename floating point register *)
230 :     fun renameF{fromSrc,toSrc,instr} =
231 :     let val _ = floatRenamesCnt := !floatRenamesCnt + 1
232 :     val instr' = Rewrite.frewriteUse(instr, fromSrc, toSrc)
233 :     in {code=[instr'], proh=[], newReg=SOME toSrc}
234 :     end
235 :    
236 :     (* Reload floating point register *)
237 :     fun reloadF{annotations,reg,spillLoc,instr} =
238 :     let val _ = floatReloadsCnt := !floatReloadsCnt + 1
239 :     val newR = C.newFreg()
240 :     val instr' = Rewrite.frewriteUse(instr, reg, newR)
241 :     in {code=Float.reloadInstr(annotations,newR,spillLoc) @ [instr'],
242 :     proh=[newR], newReg=SOME newR}
243 :     end
244 :    
245 :     fun reloadFreg{annotations,reg,dst,spillLoc} =
246 :     (floatReloadsCnt := !floatReloadsCnt + 1;
247 :     Float.reloadInstr(annotations,dst,spillLoc)
248 :     )
249 :    
250 :     (* The generic register allocator *)
251 :     structure Ra =
252 :     RegisterAllocator
253 :     (SpillHeur)
254 :     (* (ChowHennessySpillHeur) *)
255 :     (ClusterRA
256 :     (structure Flowgraph = F
257 :     structure Asm = Asm
258 :     structure InsnProps = InsnProps
259 :     structure Spill = Spill
260 :     )
261 :     )
262 :    
263 :     val KR = length Int.avail
264 :     val KF = length Float.avail
265 :    
266 :     val params =
267 :     [ { cellkind = I.C.GP,
268 :     getreg = GR.getreg,
269 :     spill = spillR,
270 :     spillSrc = spillReg,
271 :     spillCopyTmp = spillTmp,
272 :     reload = reloadR,
273 :     reloadDst = reloadReg,
274 :     renameSrc = renameR,
275 :     K = KR,
276 :     dedicated = dedicatedR,
277 :     copyInstr = fn i => [Int.copy i],
278 :     spillProh = [],
279 :     memRegs = [],
280 : leunga 796 mode = Int.mode
281 : leunga 744 } : Ra.raClient,
282 :     { cellkind = I.C.FP,
283 :     getreg = FR.getreg,
284 :     spill = spillF,
285 :     spillSrc = spillFreg,
286 :     spillCopyTmp = spillFtmp,
287 :     reload = reloadF,
288 :     reloadDst = reloadFreg,
289 :     renameSrc = renameF,
290 :     K = KF,
291 :     dedicated = dedicatedF,
292 :     copyInstr = fn i => [Float.copy i],
293 :     spillProh = [],
294 :     memRegs = [],
295 : leunga 796 mode = Float.mode
296 : leunga 744 } : Ra.raClient
297 :     ] : Ra.raClient list
298 :    
299 :     fun run cluster =
300 :     (beginRA();
301 :     GR.reset();
302 :     FR.reset();
303 :     Ra.ra params cluster
304 :     )
305 :    
306 :     end
307 : leunga 796

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