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/branches/SMLNJ/src/compiler/CodeGen/main/regalloc.sml
ViewVC logotype

Annotation of /sml/branches/SMLNJ/src/compiler/CodeGen/main/regalloc.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 498 - (view) (download)

1 : monnier 427 (*
2 :     * This functor factors out the machine independent part of the register
3 :     * allocator. This works well for RISC machines; not applicable to x86.
4 :     *)
5 : monnier 475 functor RegAlloc
6 : monnier 427 (structure I : INSTRUCTIONS
7 :     structure MachSpec : MACH_SPEC
8 :     structure Flowgraph : FLOWGRAPH
9 :     structure CpsRegs : CPSREGS
10 :     structure InsnProps : INSN_PROPERTIES
11 :     structure Rewrite : REWRITE_INSTRUCTIONS
12 :     structure Asm : INSTRUCTION_EMITTER
13 :     sharing CpsRegs.T.Constant=Flowgraph.I.Constant
14 :     sharing InsnProps.I = Flowgraph.I = Asm.I = Rewrite.I = I
15 :     sharing Asm.P = CpsRegs.T.PseudoOp = Flowgraph.P
16 :    
17 : monnier 469 (* Is this a pure instruction *)
18 :     val pure : I.instruction -> bool
19 : monnier 427
20 :     (* These functions are used to create copy instructions for
21 :     * integer and floating point registers. Given dst/src lists,
22 :     * and a copy instruction, return a new copy instruction with the same
23 :     * temporary as the old one.
24 :     *)
25 : monnier 498 val copyR : (int list * int list) * I.instruction -> I.instruction
26 :     val copyF : (int list * int list) * I.instruction -> I.instruction
27 : monnier 427
28 :     (* These functions are used to spill the temporary used in the copy
29 :     * onto some stack offset.
30 :     *)
31 :     val spillCopyTmp : I.instruction * int -> I.instruction
32 :     val spillFcopyTmp : I.instruction * int -> I.instruction
33 :    
34 :     (*
35 :     * These functions are used to spill a register onto some stack offset
36 :     *)
37 :     val spillInstrR : I.C.cell * int -> I.instruction list
38 :     val spillInstrF : I.C.cell * int -> I.instruction list
39 :    
40 :     (*
41 :     * These functions are used to reload a register from some stack offset,
42 :     * and concatenate the reload code with the given instruction list.
43 :     *)
44 :     val reloadInstrR : I.C.cell * int * I.instruction list -> I.instruction list
45 :     val reloadInstrF : I.C.cell * int * I.instruction list -> I.instruction list
46 :     ) : REGALLOC =
47 :     struct
48 :    
49 :     structure F = Flowgraph
50 :     structure I = F.I
51 :     structure P = InsnProps
52 :     structure Cells = I.C
53 :    
54 :     (* Counters for register allocation *)
55 :     val intSpillsCnt = MLRiscControl.getCounter "ra-int-spills"
56 :     val intReloadsCnt = MLRiscControl.getCounter "ra-int-reloads"
57 : monnier 498 val intRenamesCnt = MLRiscControl.getCounter "ra-int-renames"
58 : monnier 427 val floatSpillsCnt = MLRiscControl.getCounter "ra-float-spills"
59 :     val floatReloadsCnt = MLRiscControl.getCounter "ra-float-reloads"
60 : monnier 498 val floatRenamesCnt = MLRiscControl.getCounter "ra-float-renames"
61 : monnier 427
62 :     fun error msg = MLRiscErrorMsg.error(MachSpec.architecture,msg)
63 :    
64 :     val itow = Word.fromInt
65 :    
66 : monnier 498 (*
67 :     * Make arithmetic non-overflow trapping.
68 :     * This makes sure that if we happen to run the compiler for a long
69 :     * period of time overflowing counters will not crash the compiler.
70 :     *)
71 :     fun x + y = Word.toIntX(Word.+(Word.fromInt x, Word.fromInt y))
72 :     fun x - y = Word.toIntX(Word.-(Word.fromInt x, Word.fromInt y))
73 :    
74 : monnier 427 (* GetReg specialized to integer and floating point registers *)
75 :     local
76 :     val {low,high} = Cells.cellRange Cells.GP
77 :     in
78 :     structure GR = GetReg(val first=low val nRegs=high-low+1
79 :     val available=CpsRegs.availR)
80 : monnier 469 val dedicatedR = Array.array(high+1,false)
81 :     val _ = app (fn r => Array.update(dedicatedR,r,true)) CpsRegs.dedicatedR
82 :    
83 : monnier 427 end
84 :     local
85 :     val {low,high} = Cells.cellRange Cells.FP
86 :     in
87 :     structure FR = GetReg(val first=low val nRegs=high-low+1
88 :     val available=CpsRegs.availF)
89 : monnier 469 val dedicatedF = Array.array(high+1,false)
90 :     val _ = app (fn r => Array.update(dedicatedF,r,true)) CpsRegs.dedicatedF
91 : monnier 427 end
92 :    
93 :     exception RegSpills and FregSpills
94 :     val initialSpillOffset = MachSpec.initialSpillOffset
95 :     val spillOffset = ref initialSpillOffset
96 :     val spillAreaSz = MachSpec.spillAreaSz
97 :     val regspills : int Intmap.intmap = Intmap.new(0,RegSpills)
98 :     val fregspills : int Intmap.intmap = Intmap.new(0,FregSpills)
99 :     val lookupReg = Intmap.map regspills
100 :     val enterReg = Intmap.add regspills
101 :     val lookupFreg = Intmap.map fregspills
102 :     val enterFreg = Intmap.add fregspills
103 :    
104 :     fun spillInit() =
105 :     ((* Reset the regspills/fregspills map by need. *)
106 :     if !spillOffset = initialSpillOffset then ()
107 :     else (Intmap.clear regspills;
108 :     Intmap.clear fregspills
109 :     )
110 :     ;
111 :     spillOffset := initialSpillOffset
112 :     )
113 :    
114 :     fun newOffset offset =
115 :     if offset >= spillAreaSz then error "spill area too small"
116 :     else spillOffset := offset
117 :    
118 :     (* Get spill location for integer registers *)
119 :     fun getRegLoc reg = lookupReg reg handle _ =>
120 :     let val offset = !spillOffset
121 :     in newOffset(offset+4);
122 :     enterReg (reg,offset);
123 :     offset
124 :     end
125 :    
126 :     (* Get spill location for floating point registers *)
127 :     fun getFregLoc freg = lookupFreg freg handle _ =>
128 :     let val offset = !spillOffset
129 :     val aligned = Word.toIntX (Word.andb(itow (offset+7), itow ~8))
130 :     in
131 :     newOffset(aligned+8);
132 :     enterFreg (freg, aligned);
133 :     aligned
134 :     end
135 :    
136 :     (* Spill integer register *)
137 : monnier 498 fun spillR{annotations,kill=true,regmap,reg,spillLoc,instr} =
138 :     if pure instr then {code=[], proh=[], newReg=NONE}
139 : monnier 469 else spillR{annotations=annotations,kill=false,
140 :     regmap=regmap,spillLoc=spillLoc,
141 : monnier 498 reg=reg,instr=instr}
142 :     | spillR{annotations,kill,regmap,reg,spillLoc,instr} =
143 : monnier 469 let val _ = intSpillsCnt := !intSpillsCnt + 1
144 : monnier 498 val loc = getRegLoc spillLoc
145 :     val newR = Cells.newReg()
146 :     val instr' = Rewrite.rewriteDef(regmap, instr, reg, newR)
147 :     in {code=instr'::spillInstrR(newR,loc), proh=[newR], newReg=SOME newR}
148 : monnier 427 end
149 :    
150 : monnier 498 fun spillReg{annotations,src,reg,spillLoc} =
151 :     (intSpillsCnt := !intSpillsCnt + 1;
152 :     spillInstrR(src,getRegLoc spillLoc)
153 :     )
154 :    
155 :     fun spillTmp{annotations,copy,spillLoc} =
156 :     (intSpillsCnt := !intSpillsCnt + 1;
157 :     spillCopyTmp(copy,getRegLoc spillLoc)
158 :     )
159 :    
160 : monnier 427 (* Spill floating point register *)
161 : monnier 498 fun spillF{annotations,kill=true,regmap,reg,spillLoc,instr} =
162 :     if pure instr then {code=[], proh=[], newReg=NONE}
163 : monnier 469 else spillF{annotations=annotations,kill=false,
164 :     regmap=regmap,spillLoc=spillLoc,
165 : monnier 498 reg=reg,instr=instr}
166 :     | spillF{annotations,kill,regmap,reg,spillLoc,instr} =
167 : monnier 469 let val _ = floatSpillsCnt := !floatSpillsCnt + 1
168 : monnier 498 val loc = getFregLoc spillLoc
169 :     val newR = Cells.newFreg()
170 :     val instr' = Rewrite.frewriteDef(regmap, instr, reg, newR)
171 :     in {code=instr'::spillInstrF(newR,loc), proh=[newR], newReg=SOME newR}
172 : monnier 427 end
173 :    
174 : monnier 498 fun spillFreg{annotations,reg,src,spillLoc} =
175 :     (floatSpillsCnt := !floatSpillsCnt + 1;
176 :     spillInstrF(src,getFregLoc spillLoc)
177 :     )
178 :    
179 :     fun spillFtmp{annotations,copy,spillLoc} =
180 :     (floatSpillsCnt := !floatSpillsCnt + 1;
181 :     spillFcopyTmp(copy,getFregLoc spillLoc)
182 :     )
183 :    
184 :     (* Rename integer register *)
185 :     fun renameR{regmap,fromSrc,toSrc,instr} =
186 :     let val _ = intRenamesCnt := !intRenamesCnt + 1
187 :     val instr' = Rewrite.rewriteUse(regmap, instr, fromSrc, toSrc)
188 :     in {code=[instr'], proh=[], newReg=SOME toSrc}
189 :     end
190 :    
191 : monnier 427 (* Reload integer register *)
192 : monnier 498 fun reloadR{annotations,regmap,reg,spillLoc,instr} =
193 :     let val _ = intReloadsCnt := !intReloadsCnt + 1
194 :     val loc = getRegLoc spillLoc
195 :     val newR = Cells.newReg()
196 :     val instr' = Rewrite.rewriteUse(regmap, instr, reg, newR)
197 :     in {code=reloadInstrR(newR,loc,[instr']), proh=[newR], newReg=SOME newR}
198 : monnier 427 end
199 : monnier 498
200 :     fun reloadReg{annotations,reg,dst,spillLoc} =
201 :     (intReloadsCnt := !intReloadsCnt + 1;
202 :     reloadInstrR(dst,getRegLoc spillLoc,[])
203 :     )
204 : monnier 427
205 : monnier 498 (* Rename floating point register *)
206 :     fun renameF{regmap,fromSrc,toSrc,instr} =
207 :     let val _ = floatRenamesCnt := !floatRenamesCnt + 1
208 :     val instr' = Rewrite.frewriteUse(regmap, instr, fromSrc, toSrc)
209 :     in {code=[instr'], proh=[], newReg=SOME toSrc}
210 :     end
211 :    
212 : monnier 427 (* Reload floating point register *)
213 : monnier 498 fun reloadF{annotations,regmap,reg,spillLoc,instr} =
214 :     let val _ = floatReloadsCnt := !floatReloadsCnt + 1
215 :     val loc = getFregLoc(spillLoc)
216 :     val newR = Cells.newFreg()
217 :     val instr' = Rewrite.frewriteUse(regmap, instr, reg, newR)
218 :     in {code=reloadInstrF(newR,loc,[instr']), proh=[newR], newReg=SOME newR}
219 : monnier 427 end
220 :    
221 : monnier 498 fun reloadFreg{annotations,reg,dst,spillLoc} =
222 :     (floatReloadsCnt := !floatReloadsCnt + 1;
223 :     reloadInstrF(dst,getFregLoc spillLoc,[])
224 :     )
225 :    
226 : monnier 469 (* The generic register allocator *)
227 :     structure Ra =
228 :     RegisterAllocator
229 : monnier 498 (ChaitinSpillHeur)
230 :     (* (ChowHennessySpillHeur) *)
231 : monnier 469 (ClusterRA
232 :     (structure Flowgraph = F
233 :     structure Asm = Asm
234 :     structure InsnProps = InsnProps
235 :     )
236 : monnier 427 )
237 :    
238 : monnier 469 val KR = length CpsRegs.availR
239 :     val KF = length CpsRegs.availF
240 : monnier 427
241 : monnier 469 val params =
242 : monnier 498 [ { cellkind = I.C.GP,
243 :     getreg = GR.getreg,
244 :     spill = spillR,
245 :     spillSrc = spillReg,
246 :     spillCopyTmp = spillTmp,
247 :     reload = reloadR,
248 :     reloadDst = reloadReg,
249 :     renameSrc = renameR,
250 :     K = KR,
251 :     dedicated = dedicatedR,
252 :     copyInstr = fn i => [copyR i],
253 :     spillProh = [],
254 :     firstMemReg = 0,
255 :     numMemRegs = 0,
256 :     mode = Ra.SPILL_COLORING
257 : monnier 469 },
258 : monnier 498 { cellkind = I.C.FP,
259 :     getreg = FR.getreg,
260 :     spill = spillF,
261 :     spillSrc = spillFreg,
262 :     spillCopyTmp = spillFtmp,
263 :     reload = reloadF,
264 :     reloadDst = reloadFreg,
265 :     renameSrc = renameF,
266 :     K = KF,
267 :     dedicated = dedicatedF,
268 :     copyInstr = fn i => [copyF i],
269 :     spillProh = [],
270 :     firstMemReg = 0,
271 :     numMemRegs = 0,
272 :     mode = Ra.NO_OPTIMIZATION
273 : monnier 469 }
274 : monnier 498 ] : Ra.raClient list
275 : monnier 469
276 : monnier 427 fun ra cluster =
277 : monnier 469 (spillInit();
278 :     GR.reset();
279 :     FR.reset();
280 : monnier 498 Ra.ra params cluster
281 : monnier 469 )
282 : monnier 427
283 :     end

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