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 409 - (view) (download)

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

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