Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Diff of /sml/trunk/NOTES/HISTORY
ViewVC logotype

Diff of /sml/trunk/NOTES/HISTORY

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1136, Tue Mar 12 19:44:02 2002 UTC revision 1181, Wed Mar 27 21:27:27 2002 UTC
# Line 11  Line 11 
11  Date: yyyy/mm/dd  Date: yyyy/mm/dd
12  Tag: <post-commit CVS tag>  Tag: <post-commit CVS tag>
13  Description:  Description:
14    
15    ----------------------------------------------------------------------
16    Name: Matthias Blume
17    Date: 2002/03/27 16:27:00 EST
18    Tag: blume-20020327-mlrisc-divisions
19    Description:
20    
21    Added support for all four division operations (ML's div, mod, quot,
22    and rem) to MLRISC.  In the course of doing so, I also rationalized
23    the naming (no more annoying switch-around of DIV and QUOT), by
24    parameterizing the operation by div_rounding_mode (which can be either
25    DIV_TO_ZERO or DIV_TO_NEGINF).
26    
27    The generic MLTreeGen functor takes care of compiling all four
28    operations down to only round-to-zero div.
29    
30    Missing pieces:
31    
32      * Doing something smarter than relying on MLTreeGen on architectures
33        like, e.g., the x86 where hardware division delivers both quotient and
34        remainder at the same time.  With this, the implementation of the
35        round-to-neginf operations could be further streamlined.
36    
37      * Remove inlining support for div/mod/rem from the frontend and replace it
38        with primops that get carried through to the backend.  Do this for all
39        int and word types.
40    
41    ----------------------------------------------------------------------
42    Name: Matthias Blume
43    Date: 2002/03/25 17:25:00 EST
44    Tag: blume-20020325-divmod
45    Description:
46    
47    I improved (hopefully without breaking them) the implementation of Int.div,
48    Int.mod, and Int.rem.   For this, the code in translate.sml now takes
49    advantage of the following observations:
50    
51      Let  q = x quot y      r = x rem y
52           d = x div  y      m = x mod y
53    
54    where "quot" is the round-to-zero version of integer division that
55    hardware usually provides.  Then we have:
56    
57         r = x - q * y        where neither the * nor the - will overflow
58         d = if q >= 0 orelse x = q * y then q else q - 1
59                              where neither the * nor the - will overflow
60         m = if q >= 0 orelse r = 0 then r else r + y
61                              where the + will not overflow
62    
63    This results in substantial simplification of the generated code.
64    The following table shows the number of CFG nodes and edges generated
65    for
66            fun f (x, y) = x OPER y
67            (* with OPER \in div, mod, quot, rem *)
68    
69    
70        OPER | nodes(old) | edges(old) | nodes(new) | edges(new)
71        --------------------------------------------------------
72         div |         24 |         39 |         12 |         16
73         mod |         41 |         71 |         12 |         16
74        quot |          8 |         10 |          8 |         10
75         rem |         10 |         14 |          8 |         10
76    
77    
78    ----------------------------------------------------------------------
79    Name: Matthias Blume
80    Date: 2002/03/25 22:06:00 EST
81    Tag: blume-20020325-cprotobug
82    Description:
83    
84    Fixed a bug in cproto (c prototype decoder).
85    
86    ----------------------------------------------------------------------
87    Name: Matthias Blume
88    Date: 2002/03/25 16:00:00 EST
89    Tag: blume-20020325-raw-primops
90    Description:
91    
92    I did some cleanup to Allen's new primop code and
93    replaced yesterday's bootfiles with new ones.
94    (But they are stored in the same place.)
95    
96    ----------------------------------------------------------------------
97    Name: Matthias Blume
98    Date: 2002/03/24 22:40:00 EST
99    Tag: blume-20020324-bootfiles
100    Description:
101    
102    Made the bootfiles that Allen asked for.
103    
104    ----------------------------------------------------------------------
105    Name: Allen Leung
106    Date: 2002/03/23 15:50:00 EST
107    Tag: leunga-20020323-flint-cps-rcc-primops
108    Description:
109    
110      1. Changes to FLINT primops:
111    
112        (* make a call to a C-function;
113         * The primop carries C function prototype information and specifies
114         * which of its (ML-) arguments are floating point. C prototype
115         * information is for use by the backend, ML information is for
116         * use by the CPS converter. *)
117      | RAW_CCALL of { c_proto: CTypes.c_proto,
118                       ml_args: ccall_type list,
119                       ml_res_opt: ccall_type option,
120                       reentrant : bool
121                     } option
122       (* Allocate uninitialized storage on the heap.
123        * The record is meant to hold short-lived C objects, i.e., they
124        * are not ML pointers.  With the tag, the representation is
125        * the same as RECORD with tag tag_raw32 (sz=4), or tag_fblock (sz=8)
126        *)
127      | RAW_RECORD of {tag:bool,sz:int}
128      and ccall_type = CCALL_INT32 | CCALL_REAL64 | CCALL_ML_PTR
129    
130      2.  These CPS primops are now overloaded:
131    
132           rawload of {kind:numkind}
133           rawstore of {kind:numkind}
134    
135          The one argument form is:
136    
137             rawload {kind} address
138    
139          The two argument form is:
140    
141             rawload {kind} [ml object, byte-offset]
142    
143      3. RAW_CCALL/RCC now takes two extra arguments:
144    
145         a. The first is whether the C call is reentrant, i.e., whether
146            ML state should be saved and restored.
147         b. The second argument is a string argument specifying the name of
148            library and the C function.
149    
150         These things are currently not handled in the code generator, yet.
151    
152      4. In CProto,
153    
154         An encoding type of "bool" means "ml object" and is mapped into
155         C prototype of PTR.  Note that "bool" is different than "string",
156         even though "string" is also mapped into PTR, because "bool"
157         is assigned an CPS type of BOGt, while "string" is assigned INT32t.
158    
159      5. Pickler/unpicker
160    
161         Changed to handle RAW_RECORD and newest RAW_CCALL
162    
163      6. MLRiscGen,
164    
165         1. Changed to handle the new rawload/rawstore/rawrecord operators.
166         2. Code for handling C Calls has been moved to a new module CPSCCalls,
167            in the file CodeGen/cpscompile/cps-c-calls.sml
168    
169      7. Added the conditional move operator
170    
171             condmove of branch
172    
173         to cps.  Generation of this is still buggy so it is currently
174         disabled.
175    
176    ----------------------------------------------------------------------
177    Name: Lal George
178    Date: 2002/03/22 14:18:25 EST
179    Tag: george-20020322-cps-branch-prob
180    Description:
181    
182    Implemented the Ball-Larus branch prediction-heuristics, and
183    incorporated graphical viewers for control flow graphs.
184    
185    Ball-Larus Heuristics:
186    ---------------------
187    See the file compiler/CodeGen/cpscompile/cpsBranchProb.sml.
188    
189    By design it uses the Dempster-Shafer theory for combining
190    probabilities.  For example, in the function:
191    
192        fun f(n,acc) = if n = 0 then acc else f(n-1, n*acc)
193    
194    the ball-larus heuristics predicts that the n=0 is unlikely
195    (OH-heuristic), and the 'then' branch is unlikely because of the
196    RH-heuristic -- giving the 'then' branch an even lower combined
197    probability using the Dempster-Shafer theory.
198    
199    Finally, John Reppy's loop analysis in MLRISC, further lowers the
200    probability of the 'then' branch because of the loop in the else
201    branch.
202    
203    
204    Graphical Viewing:
205    ------------------
206    I merely plugged in Allen's graphical viewers into the compiler. The
207    additional code is not much. At the top level, saying:
208    
209            Control.MLRISC.getFlag "cfg-graphical-view" := true;
210    
211    will display the graphical view of the control flow graph just before
212    back-patching.  daVinci must be in your path for this to work. If
213    daVinci is not available, then the default viewer can be changed
214    using:
215    
216            Control.MLRISC.getString "viewer"
217    
218    which can be set to "dot" or "vcg" for the corresponding viewers. Of
219    course, these viewers must be in your path.
220    
221    The above will display the compilation unit at the level of clusters,
222    many of which are small, boring, and un-interesting. Also setting:
223    
224            Control.MLRISC.getInt "cfg-graphical-view_size"
225    
226    will display clusters that are larger than the value set by the above.
227    
228    
229    ----------------------------------------------------------------------
230    Name: Matthias Blume
231    Date: 2002/03/21 22:20:00 EST
232    Tag: blume-20020321-kmp-bugfix
233    Description:
234    
235    Changed the interface to the KMP routine in PreString and fixed
236    a minor bug in one place where it was used.
237    
238    ----------------------------------------------------------------------
239    Name: Allen Leung
240    Date: 2002/03/21 20:30:00 EST
241    Tag: leunga-20020321-cfg
242    Description:
243    
244      Fixed a potential problem in cfg edge splitting.
245    
246    ----------------------------------------------------------------------
247    Name: Allen Leung
248    Date: 2002/03/21 17:15:00 EST
249    Tag: leunga-20020321-x86-fp-cfg
250    Description:
251    
252      1. Recoded the buggy parts of x86-fp.
253    
254         a. All the block reordering code has been removed.
255            We now depend on the block placement phases to do this work.
256    
257         b. Critical edge splitting code has been simplified and moved into the
258            CFG modules, as where they belong.
259    
260         Both of these were quite buggy and complex.  The code is now much, much
261         simpler.
262    
263      2. X86 backend.
264    
265         a. Added instructions for 64-bit support.  Instruction selection for
266            64-bit has not been committed, however, since that
267            requires changes to MLTREE which haven't been approved by
268            Lal and John.
269    
270         b. Added support for FUCOMI and FUCOMIP when generating code for
271            PentiumPro and above.  We only generate these instructions in
272            the fast-fp mode.
273    
274         c. Added cases for JP and JNP in X86FreqProps.
275    
276      3. CFG
277    
278         CFG now has a bunch of methods for edge splitting and merging.
279    
280      4. Machine description.
281    
282         John's simplification of MLTREE_BASIS.fcond broke a few machine
283         description things:
284    
285         rtl-build.{sig,sml} and hppa.mdl fixed.
286    
287         NOTE: the machine description stuff in the repository is still broken.
288               Again, I can't put my fixes in because that involves
289               changes to MLTREE.
290    
291    ----------------------------------------------------------------------
292    Name: Matthias Blume
293    Date: 2002/03/20 15:55:00 EST
294    Tag: blume-20020320-kmp
295    Description:
296    
297    Implemented Knuth-Morris-Pratt string matching in PreString and used
298    it for String.isSubstring, Substring.isSubstring, and
299    Substring.position.
300    
301    (Might need some stress-testing.  Simple examples worked fine.)
302    
303    ----------------------------------------------------------------------
304    Name: Matthias Blume
305    Date: 2002/03/19 16:37:00 EST
306    Tag: blume-20020319-witnesses
307    Description:
308    
309    Added a structure C.W and functions convert/Ptr.convert to ml-nlffi-lib.
310    
311    This implements a generic mechanism for changing constness qualifiers
312    anywhere within big C types without resorting to outright "casts".
313    (So far, functions such as C.rw/C.ro or C.Ptr.rw/C.Ptr.ro only let you
314    modify the constness at the outermost level.)
315    The implementation of "convert" is based on the idea of "witness"
316    values -- values that are not used by the operation but whose types
317    "testify" to their applicability.  On the implementation side, "convert"
318    is simply a projection (returning its second curried argument).  With
319    cross-module inlining, it should not result in any machine code being
320    generated.
321    
322    ----------------------------------------------------------------------
323    Name: Matthias Blume
324    Date: 2002/03/15 16:40:00 EST
325    Tag: blume-20020315-basis
326    Description:
327    
328    Provided (preliminary?) implementations for
329    
330      {String,Substring}.{concatWith,isSuffix,isSubstring}
331    
332    and
333    
334      Substring.full
335    
336    Those are in the Basis spec but they were missing in SML/NJ.
337    
338    ----------------------------------------------------------------------
339    Name: Matthias Blume
340    Date: 2002/03/14 21:30:00 EST
341    Tag: blume-20020314-controls
342    Description:
343    
344    Controls:
345    ---------
346    
347    1. Factored out the recently-added Controls : CONTROLS stuff and put
348       it into its own library $/controls-lib.cm.  The source tree for
349       this is under src/smlnj-lib/Controls.
350    
351    2. Changed the names of types and functions in this interface, so they
352       make a bit more "sense":
353    
354          module -> registry
355          'a registry -> 'a group
356    
357    3. The interface now deals in ref cells only.  The getter/setter interface
358       is (mostly) gone.
359    
360    4. Added a function that lets one register an already-existing ref cell.
361    
362    5. Made the corresponding modifications to the rest of the code so that
363       everything compiles again.
364    
365    6. Changed the implementation of Controls.MLRISC back to something closer
366       to the original.  In particular, this module (and therefore MLRISC)
367       does not depend on Controls.  There now is some link-time code in
368       int-sys.sml that registers the MLRISC controls with the Controls
369       module.
370    
371    CM:
372    ---
373    
374      * One can now specify the lambda-split aggressiveness in init.cmi.
375    
376    ----------------------------------------------------------------------
377    Name: Allen Leung
378    Date: 2002/03/13 17:30:00 EST
379    Tag: leunga-20020313-x86-fp-unary
380    Description:
381    
382    Bug fix for:
383    
384    > leunga@weaselbane:~/Yale/tmp/sml-dist{21} bin/sml
385    > Standard ML of New Jersey v110.39.1 [FLINT v1.5], March 08, 2002
386    > - fun f(x,(y,z)) = Real.~ y;
387    > [autoloading]
388    > [autoloading done]
389    >       fchsl   (%eax), 184(%esp)
390    > Error: MLRisc bug: X86MCEmitter.emitInstr
391    >
392    > uncaught exception Error
393    >   raised at: ../MLRISC/control/mlriscErrormsg.sml:16.14-16.19
394    
395    The problem was that the code generator did not generate any fp registers
396    in this case, and the ra didn't know that it needed to run the X86FP phase to
397    translate the pseudo fp instruction.   This only happened with unary fp
398    operators in certain situations.
399    
400    ----------------------------------------------------------------------
401    Name: Matthias Blume
402    Date: 2002/03/13 14:00:00 EST
403    Tag: blume-20020313-overload-etc
404    Description:
405    
406    1. Added _overload as a synonym for overload for backward compatibility.
407       (Control.overloadKW must be true for either version to be accepted.)
408    
409    2. Fixed bug in install script that caused more things to be installed
410       than what was requested in config/targets.
411    
412    3. Made CM aware of the (_)overload construct so that autoloading
413       works.
414    
415    ----------------------------------------------------------------------
416    Name: Matthias Blume
417    Date: 2002/03/12 22:03:00 EST
418    Tag: blume-20020312-url
419    Description:
420    
421    Forgot to update BOOT and srcarchiveurl.
422    
423    ----------------------------------------------------------------------
424    Name: Matthias Blume
425    Date: 2002/03/12 17:30:00 EST
426    Tag: blume-20020312-version110392
427    Description:
428    
429    Yet another version number bump (because of small changes to the
430    binfile format).  Version number is now 110.39.2.  NEW BOOTFILES!
431    
432    Changes:
433    
434      The new pid generation scheme described a few weeks ago was overly
435      complicated.  I implemented a new mechanism that is simpler and
436      provides a bit more "stability":  Once CM has seen a compilation
437      unit, it keeps its identity constant (as long as you do not delete
438      those crucial CM/GUID/* files).  This means that when you change
439      an interface, compile, then go back to the old interface, and
440      compile again, you arrive at the original pid.
441    
442      There now also is a mechanism that instructs CM to use the plain
443      environment hash as a module's pid (effectively making its GUID
444      the empty string).  For this, "noguid" must be specified as an
445      option to the .sml file in question within its .cm file.
446      This is most useful for code that is being generated by tools such
447      as ml-nlffigen (because during development programmers tend to
448      erase the tool's entire output directory tree including CM's cached
449      GUIDs).  "noguid" is somewhat dangerous (since it can be used to locally
450      revert to the old, broken behavior of SML/NJ, but in specific cases
451      where there is no danger of interface confusion, its use is ok
452      (I think).
453    
454      ml-nlffigen by default generates "noguid" annotations.  They can be
455      turned off by specifying -guid in its command line.
456    
457  ----------------------------------------------------------------------  ----------------------------------------------------------------------
458  Name: Lal George  Name: Lal George
459  Date: 2002/03/12 12 14:42:36 EST  Date: 2002/03/12 12 14:42:36 EST
# Line 68  Line 511 
511  ----------------------------------------------------------------------  ----------------------------------------------------------------------
512  Name: Allen Leung  Name: Allen Leung
513  Date: 2002/03/11 10:30:00 EST  Date: 2002/03/11 10:30:00 EST
514  Tag: leunga-20020310-runtime-string0  Tag: leunga-20020311-runtime-string0
515  Description:  Description:
516    
517     The representation of the empty string now points to a     The representation of the empty string now points to a

Legend:
Removed from v.1136  
changed lines
  Added in v.1181

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