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

Annotation of /sml/trunk/src/MLRISC/CHANGES

Parent Directory Parent Directory | Revision Log Revision Log


Revision 430 - (view) (download)

1 : monnier 409 Changes to the MLRISC system
2 :     ============================
3 :    
4 : monnier 429 110.20
5 :     ======
6 :     1. Changed the interface to MLTREECOMP. It now uses the STREAM interface.
7 :     2. Library code has been streamlined. Lot's of things are now replaced
8 :     by stuff in comp-lib and smlnj-lib.
9 :     3. Dominator tree code has been improved. It is now possible to
10 :     compute the dominator tree without also computing the postdominator
11 :     tree (and vice versa). What was I thinking?
12 :     4. Some changes to the RA that takes advantage of the new Intmap functions.
13 :     5. CFGGen and friends have been fixed. CFGGen is the functor that
14 :     builds the CFG directly. It now works! I recompiled the
15 :     compiler with it. But it is a few percentages slower because
16 :     we have to go thru the CFG -> cluster phase.
17 :     6. Labels have been improved/simplified.
18 :     7. Some additions to handle CVTI2I in MLTREE. Not yet tested.
19 :     8. Various fixes to x86PseudoR to handle annotation propagation and
20 :     non identity regmaps.
21 :     9. Factored the MLRISC sources into separate libraries.
22 :     10. A very subtle bug involving the entry labels has been fixed.
23 :     How did things work before?
24 :    
25 :     110.19
26 :     ======
27 :    
28 : monnier 409 1. MLTREE
29 :     ------
30 :     As per Lal's suggestions, the MLTREE language has be extended so that
31 :     all operators are now explicitly typed (by the data width). This
32 :     change involves drastically extending the instruction sets of all the
33 :     supported architectures to support 16/64 bit operations and single
34 :     precision floating points.
35 :    
36 :     STATUS: There are still a few rough spots but should be relatively
37 :     stable, at least for SML/NJ use. In any case the new system is
38 :     running under the SPARC, HPPA and x86 platforms for a while now.
39 :    
40 :     Lal is currently looking at the LI/LI32/LI64 business. These
41 :     may be replaced by LI of IntInf.int soon.
42 :    
43 :     2. MDGEN
44 :     -----
45 :    
46 :     Some of the new machine description modules, noteably the cells
47 :     modules, machine code emitter and the assemblers are generated by
48 :     a new machine description tool MDGEN.
49 :    
50 :     STATUS: The tool is quite rough right now. I consider this a
51 :     proof of concept. Eventually I want to make all it possible to
52 :     generate all the modules.
53 :    
54 :     NOTE: Most of the ideas in the tool are stolen from/inspired by
55 :     Norman Ramsey's Lambda RTL and his NJ Machine Code Toolkit.
56 :     However, I think my way to describing machine encoding is much more
57 :     natural than his scheme.
58 :    
59 :     GOOD SPOT: The alpha machine description is the cleanest.
60 :    
61 :     MISSING FEATURES: There should be extensions to deal with bit field
62 :     manipulations. The HPPA machine description is particularly ugly (lot's
63 :     of procedural code) because of this lack.
64 :    
65 :     3. Cells
66 :     -----
67 :    
68 :     The cells interface has been vastly expanded. Also, the encoding
69 :     of physical registers has been changed: all physical register
70 :     are now encoded uniquely. For example, on the Sparc, %g0 is encoding
71 :     as 0 and %f0 is encoding as 32. The client should use the
72 :     function Reg provided by the cells interface to compute these new encoding.
73 :    
74 :     val Reg : cellkind -> int -> register
75 :    
76 :     For example, to describe %f0, use
77 :    
78 :     SparcCells.Reg SparcCells.FP 0
79 :    
80 :     STATUS: Quite solid I think.
81 :    
82 :     4. RA
83 :     --
84 :    
85 :     The RA has been reorganized a bit; the new RA is functionally identical
86 :     to the old one but I think it is slightly faster than before. Some
87 :     of the internal data structures have been changed.
88 :    
89 :     STATUS: The GetReg interface has been changed. The change is needed
90 :     to support the new Cells encoding, and for improved efficiency.
91 :    
92 :     4a Newest RA
93 :     ---------
94 :    
95 :     There is a completely new RA that I'm building which incorporates a lot
96 :     of extensions: register pair coloring, priority base coalesce/freeze,
97 :     priority based spilling, support for splitting and rematerialization,
98 :     plus support for machine SSA.
99 :    
100 :     STATUS: Not all features are there yet. Don't use it.
101 :    
102 :     5. Instruction Selection Modules
103 :     -----------------------------
104 :    
105 :     The instruction selection modules have been changed to support the
106 :     new MLTREE language.
107 :    
108 :     6. MLTREE as RTL
109 :     -------------
110 :    
111 :     The SSA optimizations need a way of specifying semantics of instructions.
112 :     In the old system it was some combinator-like language I hacked up.
113 :     It worked but not entirely satisfactory. In the new system the MLTREE
114 :     language doubles as this purpose.
115 :    
116 :     STATUS: Getting there soon.
117 :    
118 :     7. MLTREE as High Level IR
119 :     -----------------------
120 :    
121 :     There is now a way of using the MLTREE language as if it were
122 :     a ``high level'' instruction set. Theoretically, it means that
123 :     all the optimizations I've developed for the low level instruction sets
124 :     can be directly applied to MLTREE.
125 :    
126 :     STATUS: Missing some machine descriptions. Untested.
127 :    
128 :     8. MLRISC IR
129 :     ---------
130 :    
131 :     MLRISC IR is the IR that I use for all optimizations. It includes
132 :     stuff like (post-)dominator tree, control dependence graph, interval
133 :     structure, static branch predication, liveness analysis, visualization etc.
134 :    
135 :     There is now a way to generate MLRISC IR directly from MLTREE, bypassing
136 :     the cluster representation. Of course, the cluster and the MLRISC IR
137 :     are still inter-convertible.
138 :    
139 :     STATUS: Pretty solid nowadays. Need some users/beta-testers.
140 :    
141 :     9. SSA
142 :     ---
143 :    
144 :     I'm in the process of porting/improving the SSA stuff. Lots of
145 :     changes here.
146 :    
147 :     STATUS: Not ready for primetime yet. Mainly because moving to a new
148 :     RTL, plus having to support the new instructions broke a lot of stuff.
149 :    
150 :     10. EPIC/VLIW support
151 :     -----------------
152 :    
153 :     I've incorporating all the stuff I've done for Nevin last summer
154 :     in this release. They are quite solid I think.
155 :    
156 :     NOTE: We need machine descriptions!
157 :    
158 :     11. Hyperblock scheduling/modulo scheduling
159 :     ---------------------------------------
160 :    
161 :     STATUS: Same as above.
162 :    
163 :     12. Superscalar scheduling
164 :     ----------------------
165 :    
166 :     STATUS: I'm rewriting these from scratch right now. Kind of
167 :     slow in progress since other things have the priority.
168 :    
169 :     NOTE: There used to be a tool that generates automata describing the
170 :     reservation table state during scheduling. This is written in Perl.
171 :     It should be ported to SML.
172 :    
173 :     13. GC Safety
174 :     ---------
175 :    
176 :     STATUS: Vapor for now.
177 :    
178 :     14. Annotations
179 :     -----------
180 :    
181 :     Annotations can now be propagated to the instructions.
182 :     I'm using it to propagate branch probabilities in the SML/NJ compiler:
183 :     GC tests are assigned branch probabilities of zero, so that all
184 :     optimizations that are frequency driven can take the correct action.
185 :    
186 :     STATUS: quite solid I think.
187 :    
188 :     15. Regions (Memory aliasing annotations)
189 :     -------------------------------------
190 :    
191 :     There is a new way to describing regions in the new MLRiscRegions
192 :     interface. This is the stuff that Fermin and I have been talking about.
193 :    
194 :     STATUS: Nobody is using it yet.
195 :    
196 :     16. Control Dependence
197 :     ------------------
198 :    
199 :     There should be a way of specifying control dependence (and anti-dependence)
200 :     in MLTREE. This lack is currently a major sore point for me since
201 :     I have to play tricks in my optimizations (moving loads and stores
202 :     correctly require these information.) This should be tied into
203 :     the Regions business.
204 :    
205 :     STATUS: Urgently needed but should be simple to implement.
206 :    
207 :     17. Instruction Stream
208 :     ------------------
209 :    
210 :     There is now a new concept of ``instruction stream'' in MLRISC.
211 :     It is mainly used to standarized a few common interfaces used
212 :     in the assemblers, machine code emitters, and the instruction
213 :     selection modules. The main advantage of the stream interface
214 :     is that it encapsulates all the state so that it is possible to
215 :     have multiple instances of the thing going.
216 :    
217 :     STATUS: very solid.
218 :    
219 :     18. Optimizations in the Instruction Selection Modules
220 :     --------------------------------------------------
221 :    
222 :     During the rewrite of the instruction selection modules, I've added
223 :     a few optimizations. These include support for more addressing modes
224 :     (HPPA), support for scale-and-add instructions (HPPA, Alpha), and
225 :     support for strength reduction of multiplication and division (all).
226 :    
227 :     To support the last bit, there is now a generic module for generating
228 :     better multiplication and division code. It is specialized
229 :     to the particular architecture at hand.
230 :    
231 :     STATUS: The algorithm used in this module should be improved.
232 :     Specifically, a dynamic programming algorithm should be used for
233 :     searching for good multiplication instruction sequences. The algorithm
234 :     in the recent paper in PLDI should be used to generate instructions
235 :     for division by a constant. Also, no 64-bit support is yet in.
236 :    
237 :     19. Delay Slot Filling
238 :     ------------------
239 :    
240 :     The module SpanDependencyResolution has been around for a few releases
241 :     now (since the sparc backend). It performs delay slot filling while
242 :     emitting machine code.
243 :    
244 :     In addition, a new module for delay slot filling for assembly
245 :     output is added. This should be useful for all backends that do not
246 :     directly emit machine code. For example C--.
247 :    
248 :     STATUS: Untested.
249 :    
250 :     20. Cluster
251 :     -------
252 :    
253 :     Frequencies annotations are added. This is part of my evil plan to
254 :     convert everything in MLRISC to be driven by frequencies.
255 :    
256 :     Also there is a now a module to gives clusters a graph view, and
257 :     a module for visualizing a cluster. These should be useful for
258 :     those who don't want to use the MLRISC IR stuff but still want to
259 :     take advantage of the visualization stuff.
260 :    
261 :     NOTE: Annotations on the block and edge level should be also added,
262 :     as in the MLRISC IR representation.
263 :    
264 :     21. Documentation
265 :     -------------
266 :    
267 :     The directory Doc is supposed to contain all the documentation
268 :     for the new stuff. But....
269 :    
270 :     STATUS: Not ready for primetime.
271 :    
272 :     Allen Leung (leunga@cs.nyu.edu)
273 :     June 6th, 1999

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