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 744 - (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 :     * The
56 :     *)
57 :     val spillInstr : Annotations.annotations ref * I.C.cell *
58 :     RAGraph.spillLoc -> I.instruction list
59 :     (*
60 :     * This function is used to reload a register from some stack offset
61 :     *)
62 :     val reloadInstr : Annotations.annotations ref * I.C.cell *
63 :     RAGraph.spillLoc -> I.instruction list
64 :     end
65 :    
66 :     structure Float :
67 :     sig
68 :    
69 :     val avail : I.C.cell list (* list of available registers *)
70 :     val dedicated : I.C.cell list (* list of registers that are dedicated *)
71 :    
72 :     (* This functions is used to create copy instructions.
73 :     * Given dst/src lists, return a new copy instruction with the same
74 :     * temporary as the old one.
75 :     *)
76 :     val copy : (I.C.cell list * I.C.cell list) * I.instruction ->
77 :     I.instruction
78 :    
79 :     (* This function is used to spill the temporary used in the copy
80 :     * onto some stack offset.
81 :     *)
82 :     val spillCopyTmp : Annotations.annotations ref * I.instruction *
83 :     RAGraph.spillLoc -> I.instruction
84 :    
85 :     (* This function is used to spill a register onto some stack offset
86 :     * The
87 :     *)
88 :     val spillInstr : Annotations.annotations ref * I.C.cell *
89 :     RAGraph.spillLoc -> I.instruction list
90 :     (*
91 :     * This function is used to reload a register from some stack offset,
92 :     * and concatenate the reload code with the given instruction list.
93 :     *)
94 :     val reloadInstr : Annotations.annotations ref * I.C.cell *
95 :     RAGraph.spillLoc -> I.instruction list
96 :     end
97 :     ) : CLUSTER_OPTIMIZATION =
98 :     struct
99 :    
100 :     structure F = Flowgraph
101 :     structure I = F.I
102 :     structure P = InsnProps
103 :     structure C = I.C
104 :     structure G = RAGraph
105 :    
106 :     type flowgraph = F.cluster
107 :    
108 :     val name = "RISC_RA"
109 :    
110 :     (* Counters for register allocation *)
111 :     val intSpillsCnt = MLRiscControl.getCounter "ra-int-spills"
112 :     val intReloadsCnt = MLRiscControl.getCounter "ra-int-reloads"
113 :     val intRenamesCnt = MLRiscControl.getCounter "ra-int-renames"
114 :     val floatSpillsCnt = MLRiscControl.getCounter "ra-float-spills"
115 :     val floatReloadsCnt = MLRiscControl.getCounter "ra-float-reloads"
116 :     val floatRenamesCnt = MLRiscControl.getCounter "ra-float-renames"
117 :    
118 :     fun error msg = MLRiscErrorMsg.error("RISC RA "^architecture,msg)
119 :    
120 :     (*
121 :     * Make arithmetic non-overflow trapping.
122 :     * This makes sure that if we happen to run the compiler for a long
123 :     * period of time overflowing counters will not crash the compiler.
124 :     *)
125 :     fun x + y = Word.toIntX(Word.+(Word.fromInt x, Word.fromInt y))
126 :     fun x - y = Word.toIntX(Word.-(Word.fromInt x, Word.fromInt y))
127 :    
128 :     (* GetReg specialized to integer and floating point registers *)
129 :     local
130 :     val {low,high} = C.cellRange C.GP
131 :     in
132 :     structure GR = GetReg(val first=low val nRegs=high-low+1
133 :     val available=map C.registerId Int.avail)
134 :     val dedicatedR = Array.array(high+1,false)
135 :     val _ = app (fn r => Array.update(dedicatedR,C.registerId r,true))
136 :     Int.dedicated
137 :    
138 :     end
139 :     local
140 :     val {low,high} = C.cellRange C.FP
141 :     in
142 :     structure FR = GetReg(val first=low val nRegs=high-low+1
143 :     val available=map C.registerId Float.avail)
144 :     val dedicatedF = Array.array(high+1,false)
145 :     val _ = app (fn r => Array.update(dedicatedF,C.registerId r,true))
146 :     Float.dedicated
147 :     end
148 :    
149 :     (* Spill integer register *)
150 :     fun spillR{annotations,kill=true,reg,spillLoc,instr} =
151 :     if pure instr then {code=[], proh=[], newReg=NONE}
152 :     else spillR{annotations=annotations,kill=false,
153 :     spillLoc=spillLoc,
154 :     reg=reg,instr=instr}
155 :     | spillR{annotations,kill,reg,spillLoc,instr} =
156 :     let val _ = intSpillsCnt := !intSpillsCnt + 1
157 :     val newR = C.newReg()
158 :     val instr' = Rewrite.rewriteDef(instr, reg, newR)
159 :     in {code=instr'::Int.spillInstr(annotations,newR,spillLoc),
160 :     proh=[newR], newReg=SOME newR}
161 :     end
162 :    
163 :     fun spillReg{annotations,src,reg,spillLoc} =
164 :     (intSpillsCnt := !intSpillsCnt + 1;
165 :     Int.spillInstr(annotations,src,spillLoc)
166 :     )
167 :    
168 :     fun spillTmp{annotations,copy,spillLoc} =
169 :     (intSpillsCnt := !intSpillsCnt + 1;
170 :     Int.spillCopyTmp(annotations,copy,spillLoc)
171 :     )
172 :    
173 :     (* Spill floating point register *)
174 :     fun spillF{annotations,kill=true,reg,spillLoc,instr} =
175 :     if pure instr then {code=[], proh=[], newReg=NONE}
176 :     else spillF{annotations=annotations,kill=false,
177 :     spillLoc=spillLoc, reg=reg,instr=instr}
178 :     | spillF{annotations,kill,reg,spillLoc,instr} =
179 :     let val _ = floatSpillsCnt := !floatSpillsCnt + 1
180 :     val newR = C.newFreg()
181 :     val instr' = Rewrite.frewriteDef(instr, reg, newR)
182 :     in {code=instr'::Float.spillInstr(annotations,newR,spillLoc),
183 :     proh=[newR], newReg=SOME newR}
184 :     end
185 :    
186 :     fun spillFreg{annotations,reg,src,spillLoc} =
187 :     (floatSpillsCnt := !floatSpillsCnt + 1;
188 :     Float.spillInstr(annotations,src,spillLoc)
189 :     )
190 :    
191 :     fun spillFtmp{annotations,copy,spillLoc} =
192 :     (floatSpillsCnt := !floatSpillsCnt + 1;
193 :     Float.spillCopyTmp(annotations,copy,spillLoc)
194 :     )
195 :    
196 :     (* Rename integer register *)
197 :     fun renameR{fromSrc,toSrc,instr} =
198 :     let val _ = intRenamesCnt := !intRenamesCnt + 1
199 :     val instr' = Rewrite.rewriteUse(instr, fromSrc, toSrc)
200 :     in {code=[instr'], proh=[], newReg=SOME toSrc}
201 :     end
202 :    
203 :     (* Reload integer register *)
204 :     fun reloadR{annotations,reg,spillLoc,instr} =
205 :     let val _ = intReloadsCnt := !intReloadsCnt + 1
206 :     val newR = C.newReg()
207 :     val instr' = Rewrite.rewriteUse(instr, reg, newR)
208 :     in {code=Int.reloadInstr(annotations,newR,spillLoc) @ [instr'],
209 :     proh=[newR], newReg=SOME newR}
210 :     end
211 :    
212 :     fun reloadReg{annotations,reg,dst,spillLoc} =
213 :     (intReloadsCnt := !intReloadsCnt + 1;
214 :     Int.reloadInstr(annotations,dst,spillLoc)
215 :     )
216 :    
217 :     (* Rename floating point register *)
218 :     fun renameF{fromSrc,toSrc,instr} =
219 :     let val _ = floatRenamesCnt := !floatRenamesCnt + 1
220 :     val instr' = Rewrite.frewriteUse(instr, fromSrc, toSrc)
221 :     in {code=[instr'], proh=[], newReg=SOME toSrc}
222 :     end
223 :    
224 :     (* Reload floating point register *)
225 :     fun reloadF{annotations,reg,spillLoc,instr} =
226 :     let val _ = floatReloadsCnt := !floatReloadsCnt + 1
227 :     val newR = C.newFreg()
228 :     val instr' = Rewrite.frewriteUse(instr, reg, newR)
229 :     in {code=Float.reloadInstr(annotations,newR,spillLoc) @ [instr'],
230 :     proh=[newR], newReg=SOME newR}
231 :     end
232 :    
233 :     fun reloadFreg{annotations,reg,dst,spillLoc} =
234 :     (floatReloadsCnt := !floatReloadsCnt + 1;
235 :     Float.reloadInstr(annotations,dst,spillLoc)
236 :     )
237 :    
238 :     (* The generic register allocator *)
239 :     structure Ra =
240 :     RegisterAllocator
241 :     (SpillHeur)
242 :     (* (ChowHennessySpillHeur) *)
243 :     (ClusterRA
244 :     (structure Flowgraph = F
245 :     structure Asm = Asm
246 :     structure InsnProps = InsnProps
247 :     structure Spill = Spill
248 :     )
249 :     )
250 :    
251 :     val KR = length Int.avail
252 :     val KF = length Float.avail
253 :    
254 :     val params =
255 :     [ { cellkind = I.C.GP,
256 :     getreg = GR.getreg,
257 :     spill = spillR,
258 :     spillSrc = spillReg,
259 :     spillCopyTmp = spillTmp,
260 :     reload = reloadR,
261 :     reloadDst = reloadReg,
262 :     renameSrc = renameR,
263 :     K = KR,
264 :     dedicated = dedicatedR,
265 :     copyInstr = fn i => [Int.copy i],
266 :     spillProh = [],
267 :     memRegs = [],
268 :     mode = Ra.NO_OPTIMIZATION
269 :     } : Ra.raClient,
270 :     { cellkind = I.C.FP,
271 :     getreg = FR.getreg,
272 :     spill = spillF,
273 :     spillSrc = spillFreg,
274 :     spillCopyTmp = spillFtmp,
275 :     reload = reloadF,
276 :     reloadDst = reloadFreg,
277 :     renameSrc = renameF,
278 :     K = KF,
279 :     dedicated = dedicatedF,
280 :     copyInstr = fn i => [Float.copy i],
281 :     spillProh = [],
282 :     memRegs = [],
283 :     mode = Ra.NO_OPTIMIZATION
284 :     } : Ra.raClient
285 :     ] : Ra.raClient list
286 :    
287 :     fun run cluster =
288 :     (beginRA();
289 :     GR.reset();
290 :     FR.reset();
291 :     Ra.ra params cluster
292 :     )
293 :    
294 :     end

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