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/README
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/README

Parent Directory Parent Directory | Revision Log Revision Log


Revision 409 - (view) (download)

1 : monnier 409 Changes in MLRISC++
2 :     -------------------
3 :     June 26, 1999
4 :     ============
5 :     Changed
6 :    
7 :     BOOL of ty * ccexp
8 :    
9 :     to the more general
10 :    
11 :     COND of ty * ccexp * rexp * rexp
12 :    
13 :     The semantics of COND(ty,cc,e1,e2) is
14 :    
15 :     if cc then e1 else e2
16 :    
17 :     except that the code generator has the freedom to eagerly evaluate both
18 :     e1 and e2.
19 :    
20 :     For example,
21 :    
22 :     COND(ty,cc,LI 1,LI 0) means the same as BOOL(ty,cc)
23 :    
24 :     COND(ty,LT,x,y) computes the minimum of x and y
25 :     COND(ty,GT,x,y) computes the maximum of x and y
26 :    
27 :     MV(ty,x,COND(ty,cc,y,REG(ty,x))) means the same as
28 :    
29 :     if cc then x <- y.
30 :    
31 :     June 23, 1999
32 :     ============
33 :    
34 :     Added
35 :    
36 :     BOOL of ty * ccexp
37 :    
38 :     to mltree.
39 :    
40 :     This operator converts a comparison into a zero/one boolean value.
41 :     It should be useful for C.
42 :    
43 :     June 21, 1999
44 :     ============
45 :     Added a new points-to analysis module.
46 :    
47 :     June 20, 1999
48 :     ============
49 :     Added BLOCK_ANNOTATION of annotation to MLTREE. This changes the
50 :     stream interface.
51 :    
52 :     June 14, 1999
53 :     ============
54 :     Fixed up the ppc instruction set a bit. Still not finished.
55 :    
56 :     June 12, 1999
57 :     ============
58 :     Added the group mechanism for all instruction set.
59 :     Extended INSN_PROPERTIES to include
60 :    
61 :     datatype instrKind = ...
62 :     IK_GROUP | IK_PHI | IK_SOURCE | IK_SINK
63 :    
64 :    
65 :     June 9, 1999
66 :     ============
67 :     Renamed MOD? -> REM? in MLTREE
68 :     Added rounding mode to CVTF2F
69 :    
70 :     June 8, 1999
71 :     ============
72 :    
73 :     Removed LOADCC/STORECC from MLTREE.
74 :     Renamed ROUND and TRUNC to CVTF2I
75 :    
76 :     Improved the delay slot filling module (spanDep.sml) so that it works
77 :     with the HPPA instruction set. Added delay slot filling to HPPA.
78 :    
79 :     June 3, 1999
80 :     ============
81 :    
82 :     Fixed up the x86 stuff so that it'll bootstrap on the new MLTREE stuff.
83 :    
84 :     In Cells, created a new regmap now adds the default bindings for
85 :     physical registers. The x86 seems to depend on this to work properly.
86 :    
87 :     May 24, 1999
88 :     ============
89 :    
90 :     I've added the functions
91 :    
92 :     val getCell : cellkind -> cellset -> register list
93 :     val updateCell : cellkind -> cellset * register list -> cellset
94 :    
95 :     into the cellset interface. This way, the cellset can now be
96 :     manipulated as an abstract datatype.
97 :    
98 :    
99 :     May 20, 1999
100 :     ============
101 :    
102 :     Converted the PPC instruction selection module to use the new MLTREE.
103 :    
104 :     Added V9 support for Sparc
105 :    
106 :    
107 :     May 19, 1999
108 :     ============
109 :     Replaced
110 :    
111 :     LIinf of IntInf.int
112 :    
113 :     by
114 :    
115 :     LI64 of Word64.word
116 :    
117 :     Make Alpha recognize the RET instruction.
118 :     Fixed a few assembly bugs on the Alpha.
119 :    
120 :     May 18, 1999
121 :     ============
122 :     Added the interface FREQUENCY_PROPERTIES for extracting frequency
123 :     information, like branch probability, from the instruction sets.
124 :    
125 :     May 16, 1999
126 :     ============
127 :     Added numerous improvements to the modular RA.
128 :    
129 :     Added IK_CALL to insnProps
130 :    
131 :     Apr 29, 1999
132 :     ============
133 :     The new hppa backend now works great. Please see README.hppa for details.
134 :    
135 :     Apr 27, 1999
136 :     ============
137 :     Fixed up the hppa backend in a major way. I'm hoping it'll now bootstrap.
138 :    
139 :     Apr 24, 1999
140 :     ============
141 :     Added frequency information to cluster.
142 :     The weight type in CFG and the freq cluster in cluster are now
143 :     the same type.
144 :    
145 :     Apr 20, 1999
146 :     ============
147 :    
148 :     Added more MLTREE and annotations stuff. We can now annotate
149 :     mltree. What to do with this?
150 :    
151 :     Added Regions to the x86 instruction set.
152 :     Displacement and indexing effect addresses and the CALL instruction
153 :     carries around a Region.
154 :    
155 :     Fixed up the x86 instruction selection to use the new interface
156 :     (not entirely satisfactory)
157 :    
158 :     Migrating the SSA to use MLTREE as semantics description (LOTS of WORK!)
159 :    
160 :     Apr 19, 1999
161 :     ============
162 :    
163 :     The directory x86 contains x86 sources from version 110.16.
164 :    
165 :     Apr 13, 1999
166 :     ============
167 :    
168 :     Instruction sets
169 :     ----------------
170 :    
171 :     I've added annotations to all the instruction sets. Each instruction
172 :     set now contains a constructor:
173 :    
174 :     ANNOTATION of {i:instruction, a:Annotations.annotation}
175 :    
176 :     which allows the client to attach arbitrary information to an instruction.
177 :    
178 :     Alpha and Hppa
179 :     --------------
180 :     Fixed up the instruction selection modules somewhat.
181 :    
182 :     RA
183 :     --
184 :     There is now a new RA using a more modular implementation.
185 :     See ra/ra-iteratedCoalescing.sml for details.
186 :     There is also an improvement to the function isDedicated,
187 :     which may improve the performance of RA a little bit.
188 :    
189 :     Instruction Properties
190 :     ----------------------
191 :    
192 :     Added the functions immedRange and loadImmed. This used to be
193 :     in SSA_PROPERTIES.
194 :    
195 :     Also added the functions
196 :    
197 :     hashOpn : operand -> word
198 :     eqOpn : operand * operand -> word
199 :    
200 :     These are useful for building hash tables on operands.
201 :    
202 :     Apr 8, 1999
203 :     ============
204 :    
205 :    
206 :     I've renamed MLRISC to MLRISC++ temporarily since there are lots and
207 :     lots of changes.
208 :    
209 :     Library
210 :     -------
211 :    
212 :     Added and changed a few interfaces. Added a merge sort using the algorithm
213 :     seen in the last NJPLS.
214 :    
215 :     CELLS
216 :     -----
217 :    
218 :     The cells interface has been changed as follows:
219 :    
220 :     1. Type cellclass is renamed cellkind.
221 :    
222 :     2. All physical registers must now have unique ids. For example,
223 :     on the Alpha integer registers are numbered as 0 .. 31, and floating
224 :     point registers are numbered as 32 .. 63. This affects all clients
225 :     that uses these functions.
226 :    
227 :     3. The Cells functors are now generated from the new MDGen tool.
228 :    
229 :     Instruction Stream
230 :     ------------------
231 :    
232 :     There is now an ``instruction stream'' concept, with the following
233 :     signature:
234 :    
235 :     signature INSTRUCTION_STREAM =
236 :     sig
237 :    
238 :     structure P : PSEUDO_OPS
239 :     structure B : BLOCK_NAMES
240 :    
241 :     datatype ('a,'b,'c) stream =
242 :     STREAM of
243 :     { init : int -> unit,
244 :     finish : 'c -> unit,
245 :     emit : (int -> int) -> 'a -> unit,
246 :     pseudoOp : P.pseudo_op -> unit,
247 :     defineLabel : Label.label -> unit,
248 :     entryLabel : Label.label -> unit,
249 :     comment : string -> unit,
250 :     blockName : B.name -> unit,
251 :     exitBlock : 'b -> unit
252 :     }
253 :     end
254 :    
255 :     An instruction stream accepts a sequence of instructions and does stuff
256 :     with it. Various modules are now expressed as transformations that
257 :     operate on instruction streams.
258 :    
259 :     INSN_PROPERTIES
260 :     ---------------
261 :    
262 :     I've added the instr_kind IK_COPY.
263 :     I've removed various functions that dealt with parallel copies. These
264 :     were either not used or inadequate given the new changes.
265 :    
266 :     Regions
267 :     -------
268 :    
269 :     I'm moving towards a new Regions interface as per discussion with Fermin.
270 :     This is needed for the new SSA stuff.
271 :    
272 :     MC and Asm
273 :     ----------
274 :    
275 :     These modules now uses the instruction stream interface. These modules
276 :     implement the function:
277 :    
278 :     val makeStream : unit -> (instruction,unit,unit) stream
279 :    
280 :     The state of the stream is hidden within the function. Each call of
281 :     makeStream() creates a new stream instance; you can have multiple streams
282 :     active at the same time. MC and Asm modules are now generated by
283 :     the MDGen tool.
284 :    
285 :     MLTREE
286 :     ------
287 :    
288 :     The mltree signature has been expanded to deal with different
289 :     floating point and integer types. Plus some SSA support has been put
290 :     in but these are not currently fully functional. Some of the MLTREE
291 :     stuff have been factored out so that they can be used for the semantics
292 :     description language (MLExp) used in SSA.
293 :    
294 :     I expect eventually the two will be merged somehow. This allows us to do
295 :     wonderful things like this: the backend can build up a big MLExp (MLTREE)
296 :     expression by composing the semantics of a sequence of instructions,
297 :     and apply simplification on it. It then creates a new instruction selection
298 :     module (see below) and asks it to give back a new (simplified)
299 :     sequence of instruction that has the same semantics as before. For this
300 :     to work nicely MLExp and MLTREE should be combined.
301 :    
302 :     MLTREECOMP (Instruction Selection Modules)
303 :     ------------------------------------------
304 :    
305 :     This interface has been changed as follows:
306 :    
307 :     signature MLTREECOMP = sig
308 :     structure T : MLTREE
309 :     structure I : INSTRUCTIONS
310 :     structure S : INSTRUCTION_STREAM
311 :     sharing S.B = T.BNames
312 :     sharing S.P = T.PseudoOp
313 :    
314 :     val selectInstructions :
315 :     (I.instruction,T.mlrisc list,I.C.regmap) S.stream ->
316 :     { mltreeComp : T.mltree -> unit,
317 :     mlriscComp : T.stm -> unit,
318 :     emitInstr : I.instruction -> unit
319 :     }
320 :     end
321 :    
322 :     Conceptually, an instruction selection module takes a stream
323 :     of mltree ``instructions'' (i.e. stm) and transform it into a stream of
324 :     actual instructions. I've rewritten them so that multiple instances
325 :     of these modules can now be active at the same time.
326 :    
327 :     They are also properly detached from the flowgen modules so that
328 :     they can be more flexibily reused in some other places. For example,
329 :     the backend can create mltree stms on the fly, pass them to a instruction
330 :     selection module, and get back a stream of instructions. In the old
331 :     MLRISC this is not possible.
332 :    
333 :     Also, if we don't care about register allocation, we can be tie
334 :     an instruction selection module directly to an assembly emitter stream.
335 :    
336 :     Ideally, selectionInstructions should have signature
337 :    
338 :     val selectInstructions :
339 :     (I.instruction,T.mlrisc list,I.C.regmap) S.stream ->
340 :     (T.stm,T.mlrisc list,I.C.regmap) S.stream
341 :    
342 :     but for various reasons I'll stick with something closer to the old
343 :     signature for now.
344 :    
345 :     I've rewritten the ones for Sparc, Hppa and Alpha to take advantage
346 :     of the new MLTREEE. Only the one on the sparc has been tested.
347 :    
348 :     Alpha
349 :     -----
350 :    
351 :     The alpha instruction set has been drastically expanded to handle 64 bit
352 :     quantities. Lots of floating point ops are still missing though. They
353 :     deal with different types of rounding and trapping modes. I don't know
354 :     how they fit into the picture yet. Conditional Moves are also added; these
355 :     are not used yet. I have renamed Alpha32 to Alpha.
356 :    
357 :     Hppa and Sparc
358 :     --------------
359 :    
360 :     Some additions to deal with single precision floating points.
361 :     I think these are 64 bit processors but I don't have up-to-date manuals.
362 :    
363 :     Flowgen
364 :     -------
365 :    
366 :     The flowgen module is used to build a flowgraph from a stream of
367 :     instructions. The flowgen interface now makes no mention of flowgraph
368 :     representation. This allows us to use other representations than FLOWGRAPH.
369 :     Flowgen has the following interface:
370 :    
371 :     signature FLOWGRAPH_GEN =
372 :     sig
373 :    
374 :     structure C : CELLS
375 :     structure I : INSTRUCTIONS
376 :     structure T : MLTREE
377 :     structure B : BLOCK_NAMES
378 :     structure S : INSTRUCTION_STREAM
379 :    
380 :     sharing I.C = C
381 :     sharing T.Constant = I.Constant
382 :     sharing T.PseudoOp = S.P
383 :     sharing T.BNames = B = S.B
384 :    
385 :     val newStream : unit -> (I.instruction,T.mlrisc list,C.regmap) S.stream
386 :     end
387 :    
388 :     flowgen.sml has been renamed to clustergen.sml. The module ClusterGen
389 :     serves the same function as FlowgraphGen before: it takes a stream
390 :     of instructions, build a cluster, then pass it onto the next phase.
391 :    
392 :     An alternative module, CFGGen, also exists. This module builds a CFG
393 :     instead. Eventually, we should have modules that can directly build
394 :     an SSA.
395 :    
396 :    
397 :     SSA, IR, ir
398 :     -----------
399 :     Too many changes to list here.
400 :    
401 :     The new ssa datatype will have a distinct representation than instructions.
402 :     Merging them turned out to be easy on paper but hard in practice.
403 :    
404 :     However, there is a new way to make ssa_ops behave just like instructions.
405 :     See the signature ssa-instructions.sig for details. So all the machinary
406 :     developed on top of instructions can be reused.
407 :    
408 :     MD++
409 :     ----
410 :    
411 :     This directory contains the MDGen tool. The machine description
412 :     files have suffixes md. To run the MDGen tool, go into SML in directory
413 :     MLRISC++. Type ``use "make.sml"'' This automatically regenerates all
414 :     files dependent on the machine description files.
415 :    
416 :     Currently, only *Cells.sml, *Instr.sml, *MC.sml, *Asm.sml files are
417 :     generated from *.md. Eventually, more things will be automated.
418 :    
419 :     RA
420 :     --
421 :    
422 :     I'm in the process of splitting the RA into more manageable pieces.
423 :     See ra/ra-graph.s* ra/ra-core.s* etc.
424 :    
425 :     The idea is that the build/rebuild and spill phases should be split from
426 :     the core of the register allocator, so that we can customize them by
427 :     incorporating different heuristics. This is needed for the coming SSA work.
428 :     The core of the register allocator will not reference any flowgraph
429 :     data structures since those can change.
430 :    
431 :     How about register-pair allocation?

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