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/HISTORY
 [smlnj] / sml / trunk / HISTORY

# Diff of /sml/trunk/HISTORY

revision 1124, Thu Mar 7 19:49:22 2002 UTC revision 1180, Tue Mar 26 22:24:24 2002 UTC
# Line 13  Line 13
13  Description:  Description:
14
15  ----------------------------------------------------------------------  ----------------------------------------------------------------------
16    Name: Matthias Blume
17    Date: 2002/03/25 17:25:00 EST
18    Tag: blume-20020325-divmod
19    Description:
20
21    I improved (hopefully without breaking them) the implementation of Int.div,
22    Int.mod, and Int.rem.   For this, the code in translate.sml now takes
23    advantage of the following observations:
24
25      Let  q = x quot y      r = x rem y
26           d = x div  y      m = x mod y
27
28    where "quot" is the round-to-zero version of integer division that
29    hardware usually provides.  Then we have:
30
31         r = x - q * y        where neither the * nor the - will overflow
32         d = if q >= 0 orelse x = q * y then q else q - 1
33                              where neither the * nor the - will overflow
34         m = if q >= 0 orelse r = 0 then r else r + y
35                              where the + will not overflow
36
37    This results in substantial simplification of the generated code.
38    The following table shows the number of CFG nodes and edges generated
39    for
40            fun f (x, y) = x OPER y
41            (* with OPER \in div, mod, quot, rem *)
42
43
44        OPER | nodes(old) | edges(old) | nodes(new) | edges(new)
45        --------------------------------------------------------
46         div |         24 |         39 |         12 |         16
47         mod |         41 |         71 |         12 |         16
48        quot |          8 |         10 |          8 |         10
49         rem |         10 |         14 |          8 |         10
50
51
52    ----------------------------------------------------------------------
53    Name: Matthias Blume
54    Date: 2002/03/25 22:06:00 EST
55    Tag: blume-20020325-cprotobug
56    Description:
57
58    Fixed a bug in cproto (c prototype decoder).
59
60    ----------------------------------------------------------------------
61    Name: Matthias Blume
62    Date: 2002/03/25 16:00:00 EST
63    Tag: blume-20020325-raw-primops
64    Description:
65
66    I did some cleanup to Allen's new primop code and
67    replaced yesterday's bootfiles with new ones.
68    (But they are stored in the same place.)
69
70    ----------------------------------------------------------------------
71    Name: Matthias Blume
72    Date: 2002/03/24 22:40:00 EST
73    Tag: blume-20020324-bootfiles
74    Description:
75
77
78    ----------------------------------------------------------------------
79    Name: Allen Leung
80    Date: 2002/03/23 15:50:00 EST
81    Tag: leunga-20020323-flint-cps-rcc-primops
82    Description:
83
84      1. Changes to FLINT primops:
85
86        (* make a call to a C-function;
87         * The primop carries C function prototype information and specifies
88         * which of its (ML-) arguments are floating point. C prototype
89         * information is for use by the backend, ML information is for
90         * use by the CPS converter. *)
91      | RAW_CCALL of { c_proto: CTypes.c_proto,
92                       ml_args: ccall_type list,
93                       ml_res_opt: ccall_type option,
94                       reentrant : bool
95                     } option
96       (* Allocate uninitialized storage on the heap.
97        * The record is meant to hold short-lived C objects, i.e., they
98        * are not ML pointers.  With the tag, the representation is
99        * the same as RECORD with tag tag_raw32 (sz=4), or tag_fblock (sz=8)
100        *)
101      | RAW_RECORD of {tag:bool,sz:int}
102      and ccall_type = CCALL_INT32 | CCALL_REAL64 | CCALL_ML_PTR
103
104      2.  These CPS primops are now overloaded:
105
107           rawstore of {kind:numkind}
108
109          The one argument form is:
110
112
113          The two argument form is:
114
115             rawload {kind} [ml object, byte-offset]
116
117      3. RAW_CCALL/RCC now takes two extra arguments:
118
119         a. The first is whether the C call is reentrant, i.e., whether
120            ML state should be saved and restored.
121         b. The second argument is a string argument specifying the name of
122            library and the C function.
123
124         These things are currently not handled in the code generator, yet.
125
126      4. In CProto,
127
128         An encoding type of "bool" means "ml object" and is mapped into
129         C prototype of PTR.  Note that "bool" is different than "string",
130         even though "string" is also mapped into PTR, because "bool"
131         is assigned an CPS type of BOGt, while "string" is assigned INT32t.
132
133      5. Pickler/unpicker
134
135         Changed to handle RAW_RECORD and newest RAW_CCALL
136
137      6. MLRiscGen,
138
139         1. Changed to handle the new rawload/rawstore/rawrecord operators.
140         2. Code for handling C Calls has been moved to a new module CPSCCalls,
141            in the file CodeGen/cpscompile/cps-c-calls.sml
142
143      7. Added the conditional move operator
144
145             condmove of branch
146
147         to cps.  Generation of this is still buggy so it is currently
148         disabled.
149
150    ----------------------------------------------------------------------
151    Name: Lal George
152    Date: 2002/03/22 14:18:25 EST
153    Tag: george-20020322-cps-branch-prob
154    Description:
155
156    Implemented the Ball-Larus branch prediction-heuristics, and
157    incorporated graphical viewers for control flow graphs.
158
159    Ball-Larus Heuristics:
160    ---------------------
161    See the file compiler/CodeGen/cpscompile/cpsBranchProb.sml.
162
163    By design it uses the Dempster-Shafer theory for combining
164    probabilities.  For example, in the function:
165
166        fun f(n,acc) = if n = 0 then acc else f(n-1, n*acc)
167
168    the ball-larus heuristics predicts that the n=0 is unlikely
169    (OH-heuristic), and the 'then' branch is unlikely because of the
170    RH-heuristic -- giving the 'then' branch an even lower combined
171    probability using the Dempster-Shafer theory.
172
173    Finally, John Reppy's loop analysis in MLRISC, further lowers the
174    probability of the 'then' branch because of the loop in the else
175    branch.
176
177
178    Graphical Viewing:
179    ------------------
180    I merely plugged in Allen's graphical viewers into the compiler. The
181    additional code is not much. At the top level, saying:
182
183            Control.MLRISC.getFlag "cfg-graphical-view" := true;
184
185    will display the graphical view of the control flow graph just before
186    back-patching.  daVinci must be in your path for this to work. If
187    daVinci is not available, then the default viewer can be changed
188    using:
189
190            Control.MLRISC.getString "viewer"
191
192    which can be set to "dot" or "vcg" for the corresponding viewers. Of
193    course, these viewers must be in your path.
194
195    The above will display the compilation unit at the level of clusters,
196    many of which are small, boring, and un-interesting. Also setting:
197
198            Control.MLRISC.getInt "cfg-graphical-view_size"
199
200    will display clusters that are larger than the value set by the above.
201
202
203    ----------------------------------------------------------------------
204    Name: Matthias Blume
205    Date: 2002/03/21 22:20:00 EST
206    Tag: blume-20020321-kmp-bugfix
207    Description:
208
209    Changed the interface to the KMP routine in PreString and fixed
210    a minor bug in one place where it was used.
211
212    ----------------------------------------------------------------------
213    Name: Allen Leung
214    Date: 2002/03/21 20:30:00 EST
215    Tag: leunga-20020321-cfg
216    Description:
217
218      Fixed a potential problem in cfg edge splitting.
219
220    ----------------------------------------------------------------------
221    Name: Allen Leung
222    Date: 2002/03/21 17:15:00 EST
223    Tag: leunga-20020321-x86-fp-cfg
224    Description:
225
226      1. Recoded the buggy parts of x86-fp.
227
228         a. All the block reordering code has been removed.
229            We now depend on the block placement phases to do this work.
230
231         b. Critical edge splitting code has been simplified and moved into the
232            CFG modules, as where they belong.
233
234         Both of these were quite buggy and complex.  The code is now much, much
235         simpler.
236
237      2. X86 backend.
238
239         a. Added instructions for 64-bit support.  Instruction selection for
240            64-bit has not been committed, however, since that
241            requires changes to MLTREE which haven't been approved by
242            Lal and John.
243
244         b. Added support for FUCOMI and FUCOMIP when generating code for
245            PentiumPro and above.  We only generate these instructions in
246            the fast-fp mode.
247
248         c. Added cases for JP and JNP in X86FreqProps.
249
250      3. CFG
251
252         CFG now has a bunch of methods for edge splitting and merging.
253
254      4. Machine description.
255
256         John's simplification of MLTREE_BASIS.fcond broke a few machine
257         description things:
258
259         rtl-build.{sig,sml} and hppa.mdl fixed.
260
261         NOTE: the machine description stuff in the repository is still broken.
262               Again, I can't put my fixes in because that involves
263               changes to MLTREE.
264
265    ----------------------------------------------------------------------
266    Name: Matthias Blume
267    Date: 2002/03/20 15:55:00 EST
268    Tag: blume-20020320-kmp
269    Description:
270
271    Implemented Knuth-Morris-Pratt string matching in PreString and used
272    it for String.isSubstring, Substring.isSubstring, and
273    Substring.position.
274
275    (Might need some stress-testing.  Simple examples worked fine.)
276
277    ----------------------------------------------------------------------
278    Name: Matthias Blume
279    Date: 2002/03/19 16:37:00 EST
280    Tag: blume-20020319-witnesses
281    Description:
282
283    Added a structure C.W and functions convert/Ptr.convert to ml-nlffi-lib.
284
285    This implements a generic mechanism for changing constness qualifiers
286    anywhere within big C types without resorting to outright "casts".
287    (So far, functions such as C.rw/C.ro or C.Ptr.rw/C.Ptr.ro only let you
288    modify the constness at the outermost level.)
289    The implementation of "convert" is based on the idea of "witness"
290    values -- values that are not used by the operation but whose types
291    "testify" to their applicability.  On the implementation side, "convert"
292    is simply a projection (returning its second curried argument).  With
293    cross-module inlining, it should not result in any machine code being
294    generated.
295
296    ----------------------------------------------------------------------
297    Name: Matthias Blume
298    Date: 2002/03/15 16:40:00 EST
299    Tag: blume-20020315-basis
300    Description:
301
302    Provided (preliminary?) implementations for
303
304      {String,Substring}.{concatWith,isSuffix,isSubstring}
305
306    and
307
308      Substring.full
309
310    Those are in the Basis spec but they were missing in SML/NJ.
311
312    ----------------------------------------------------------------------
313    Name: Matthias Blume
314    Date: 2002/03/14 21:30:00 EST
315    Tag: blume-20020314-controls
316    Description:
317
318    Controls:
319    ---------
320
321    1. Factored out the recently-added Controls : CONTROLS stuff and put
322       it into its own library \$/controls-lib.cm.  The source tree for
323       this is under src/smlnj-lib/Controls.
324
325    2. Changed the names of types and functions in this interface, so they
326       make a bit more "sense":
327
328          module -> registry
329          'a registry -> 'a group
330
331    3. The interface now deals in ref cells only.  The getter/setter interface
332       is (mostly) gone.
333
334    4. Added a function that lets one register an already-existing ref cell.
335
336    5. Made the corresponding modifications to the rest of the code so that
337       everything compiles again.
338
339    6. Changed the implementation of Controls.MLRISC back to something closer
340       to the original.  In particular, this module (and therefore MLRISC)
341       does not depend on Controls.  There now is some link-time code in
342       int-sys.sml that registers the MLRISC controls with the Controls
343       module.
344
345    CM:
346    ---
347
348      * One can now specify the lambda-split aggressiveness in init.cmi.
349
350    ----------------------------------------------------------------------
351    Name: Allen Leung
352    Date: 2002/03/13 17:30:00 EST
353    Tag: leunga-20020313-x86-fp-unary
354    Description:
355
356    Bug fix for:
357
358    > leunga@weaselbane:~/Yale/tmp/sml-dist{21} bin/sml
359    > Standard ML of New Jersey v110.39.1 [FLINT v1.5], March 08, 2002
360    > - fun f(x,(y,z)) = Real.~ y;
363    >       fchsl   (%eax), 184(%esp)
364    > Error: MLRisc bug: X86MCEmitter.emitInstr
365    >
366    > uncaught exception Error
367    >   raised at: ../MLRISC/control/mlriscErrormsg.sml:16.14-16.19
368
369    The problem was that the code generator did not generate any fp registers
370    in this case, and the ra didn't know that it needed to run the X86FP phase to
371    translate the pseudo fp instruction.   This only happened with unary fp
372    operators in certain situations.
373
374    ----------------------------------------------------------------------
375    Name: Matthias Blume
376    Date: 2002/03/13 14:00:00 EST
378    Description:
379
381       (Control.overloadKW must be true for either version to be accepted.)
382
383    2. Fixed bug in install script that caused more things to be installed
384       than what was requested in config/targets.
385
387       works.
388
389    ----------------------------------------------------------------------
390    Name: Matthias Blume
391    Date: 2002/03/12 22:03:00 EST
392    Tag: blume-20020312-url
393    Description:
394
395    Forgot to update BOOT and srcarchiveurl.
396
397    ----------------------------------------------------------------------
398    Name: Matthias Blume
399    Date: 2002/03/12 17:30:00 EST
400    Tag: blume-20020312-version110392
401    Description:
402
403    Yet another version number bump (because of small changes to the
404    binfile format).  Version number is now 110.39.2.  NEW BOOTFILES!
405
406    Changes:
407
408      The new pid generation scheme described a few weeks ago was overly
409      complicated.  I implemented a new mechanism that is simpler and
410      provides a bit more "stability":  Once CM has seen a compilation
411      unit, it keeps its identity constant (as long as you do not delete
412      those crucial CM/GUID/* files).  This means that when you change
413      an interface, compile, then go back to the old interface, and
414      compile again, you arrive at the original pid.
415
416      There now also is a mechanism that instructs CM to use the plain
417      environment hash as a module's pid (effectively making its GUID
418      the empty string).  For this, "noguid" must be specified as an
419      option to the .sml file in question within its .cm file.
420      This is most useful for code that is being generated by tools such
421      as ml-nlffigen (because during development programmers tend to
422      erase the tool's entire output directory tree including CM's cached
423      GUIDs).  "noguid" is somewhat dangerous (since it can be used to locally
424      revert to the old, broken behavior of SML/NJ, but in specific cases
425      where there is no danger of interface confusion, its use is ok
426      (I think).
427
428      ml-nlffigen by default generates "noguid" annotations.  They can be
429      turned off by specifying -guid in its command line.
430
431    ----------------------------------------------------------------------
432    Name: Lal George
433    Date: 2002/03/12 12 14:42:36 EST
434    Tag: george-20020312-frequency-computation
435    Description:
436
437    Integrated jump chaining and static block frequency into the
438    compiler. More details and numbers later.
439
440    ----------------------------------------------------------------------
441    Name: Lal George
442    Date: 2002/03/11 11 22:38:53 EST
443    Tag: george-20020311-jump-chain-elim
444    Description:
445
446    Tested the jump chain elimination on all architectures (except the
447    hppa).  This is on by default right now and is profitable for the
448    alpha and x86, however, it may not be profitable for the sparc and ppc
449    when compiling the compiler.
450
451    The gc test will typically jump to a label at the end of the cluster,
452    where there is another jump to an external cluster containing the actual
453    code to invoke gc. This is to allow factoring of common gc invocation
454    sequences. That is to say, we generate:
455
456            f:
457               testgc
458               ja   L1      % jump if above to L1
459
460            L1:
461               jmp L2
462
463
464    After jump chain elimination the 'ja L1' instructions is converted to
465    'ja L2'. On the sparc and ppc, many of the 'ja L2' instructions may end
466    up being implemented in their long form (if L2 is far away) using:
467
468            jbe     L3      % jump if below or equal to L3
469            jmp     L2
470         L3:
471            ...
472
473
474    For large compilation units L2  may be far away.
475
476
477    ----------------------------------------------------------------------
478    Name: Matthias Blume
479    Date: 2002/03/11 13:30:00 EST
480    Tag: blume-20020311-mltreeeval
481    Description:
482
483    A functor parameter was missing.
484
485    ----------------------------------------------------------------------
486    Name: Allen Leung
487    Date: 2002/03/11 10:30:00 EST
488    Tag: leunga-20020311-runtime-string0
489    Description:
490
491       The representation of the empty string now points to a
492    legal null terminated C string instead of unit.  It is now possible
493    to convert an ML string into C string with InlineT.CharVector.getData.
494    This compiles into one single machine instruction.
495
496    ----------------------------------------------------------------------
497    Name: Allen Leung
498    Date: 2002/03/10 23:55:00 EST
499    Tag: leunga-20020310-x86-call
500    Description:
501
502       Added machine generation for CALL instruction (relative displacement mode)
503
504    ----------------------------------------------------------------------
505    Name: Matthias Blume
506    Date: 2002/03/08 16:05:00
507    Tag: blume-20020308-entrypoints
508    Description:
509
510    Version number bumped to 110.39.1.  NEW BOOTFILES!
511
512    Entrypoints: non-zero offset into a code object where execution should begin.
513
514    - Added the notion of an entrypoint to CodeObj.
517    - Use the address of the label of the first function given to mlriscGen
518      as the entrypoint.  This address is currently always 0, but it will
519      not be 0 once we turn on block placement.
520    - Removed the linkage cluster code (which was The Other Way(tm) of dealing
521      with entry points) from mlriscGen.
522
523    ----------------------------------------------------------------------
524    Name: Allen Leung
525    Date: 2002/03/07 20:45:00 EST
526    Tag: leunga-20020307-x86-cmov
527    Description:
528
529       Bug fixes for CMOVcc on x86.
530
531       1. Added machine code generation for CMOVcc
532       2. CMOVcc is now generated in preference over SETcc on PentiumPro or above.
533       3. CMOVcc cannot have an immediate operand as argument.
534
535    ----------------------------------------------------------------------
536    Name: Matthias Blume
537    Date: 2002/03/07 16:15:00 EST
538    Tag: blume-20020307-controls
539    Description:
540
541    This is a very large but mostly boring patch which makes (almost)
542    every tuneable compiler knob (i.e., pretty much everything under
543    Control.* plus a few other things) configurable via both the command
544    line and environment variables in the style CM did its configuration
545    until now.
546
547    Try starting sml with '-h' (or, if you are brave, '-H')
548
549    To this end, I added a structure Controls : CONTROLS to smlnj-lib.cm which
550    implements the underlying generic mechanism.
551
552    The interface to some of the existing such facilities has changed somewhat.
553    For example, the MLRiscControl module now provides mkFoo instead of getFoo.
554    (The getFoo interface is still there for backward-compatibility, but its
555    use is deprecated.)
556
557    The ml-build script passes -Cxxx=yyy command-line arguments through so
558    that one can now twiddle the compiler settings when using this "batch"
559    compiler.
560
561    TODO items:
562
563    We should go through and throw out all controls that are no longer
564    connected to anything.  Moreover, we should go through and provide
565    meaningful (and correct!) documentation strings for those controls
566    that still are connected.
567
568    Currently, multiple calls to Controls.new are accepted (only the first
569    has any effect).  Eventually we should make sure that every control
570    is being made (via Controls.new) exactly once.  Future access can then
571    be done using Controls.acc.
572
573    Finally, it would probably be a good idea to use the getter-setter
574    interface to controls rather than ref cells.  For the time being, both
575    styles are provided by the Controls module, but getter-setter pairs are
576    better if thread-safety is of any concern because they can be wrapped.
577
578    *****************************************
579
580    One bug fix: The function blockPlacement in three of the MLRISC
581    backpatch files used to be hard-wired to one of two possibilities at
582    link time (according to the value of the placementFlag).  But (I
583    think) it should rather sense the flag every time.
584
585    *****************************************
586
587    Other assorted changes (by other people who did not supply a HISTORY entry):
588
589    1. the cross-module inliner now works much better (Monnier)
590    2. representation of weights, frequencies, and probabilities in MLRISC
591       changed in preparation of using those for weighted block placement
592       (Reppy, George)
593
594    ----------------------------------------------------------------------
595  Name: Lal George  Name: Lal George
596  Date: 2002/03/07 14:44:24 EST 2002  Date: 2002/03/07 14:44:24 EST 2002
597  Tag: george-20020307-weighted-block-placement  Tag: george-20020307-weighted-block-placement

Legend:
 Removed from v.1124 changed lines Added in v.1180