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

Diff of /sml/trunk/HISTORY

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

revision 1158, Fri Mar 22 01:21:25 2002 UTC revision 1189, Fri May 10 20:40:33 2002 UTC
# Line 13  Line 13 
13  Description:  Description:
14    
15  ----------------------------------------------------------------------  ----------------------------------------------------------------------
16    Name: Matthias Blume
17    Date: 2002/05/10 16:40:00 EDT
18    Tag: blume-20020510-erg-textio
19    Description:
20    
21    Applied the following bugfix provided by Emden Gansner:
22    
23        Output is corrupted when outputSubstr is used rather than output.
24    
25        The problem occurs when a substring
26    
27            ss = (s, dataStart, dataLen)
28    
29        where dataStart > 0, fills a stream buffer with avail bytes left.
30        avail bytes of s, starting at index dataStart, are copied into the
31        buffer, the buffer is flushed, and then the remaining dataLen-avail
32        bytes of ss are copied into the beginning of the buffer. Instead of
33        starting this copy at index dataStart+avail in s, the current code
34        starts the copy at index avail.
35    
36        Fix:
37        In text-io-fn.sml, change line 695 from
38             val needsFlush = copyVec(v, avail, dataLen-avail, buf, 0)
39        to
40             val needsFlush = copyVec(v, dataStart+avail, dataLen-avail, buf, 0)
41    
42    ----------------------------------------------------------------------
43    Name: Matthias Blume
44    Date: 2002/04/12 13:55:00 EDT
45    Tag: blume-20020412-assyntax
46    Description:
47    
48    1. Grabbed newer assyntax.h from the XFree86 project.
49    2. Fiddled with how to compile X86.prim.asm without warnings.
50    3. (Very) Minor cleanup in CM.
51    
52    ----------------------------------------------------------------------
53    Name: Matthias Blume
54    Date: 2002/04/01 (no joke!) 17:07:00 EST
55    Tag: blume-20020401-x86div
56    Description:
57    
58    Added full support for div/mod/rem/quot on the x86, using the machine
59    instruction's two results (without clumsily recomputing the remainder)
60    directly where appropriate.
61    
62    Some more extensive power-of-two support was added to the x86 instruction
63    selector (avoiding expensive divs, mods, and muls where they can be
64    replaced with cheaper shifts and masks).  However, this sort of thing
65    ought to be done earlier, e.g., within the CPS optimizer so that
66    all architectures benefit from it.
67    
68    The compiler compiles to a fixed point, but changes might be somewhat
69    fragile nevertheless.  Please, report any strange things that you might
70    see wrt. div/mod/quot/rem...
71    
72    ----------------------------------------------------------------------
73    Name: Matthias Blume
74    Date: 2002/03/29 17:22:00
75    Tag: blume-20020329-div
76    Description:
77    
78    Fixed my broken div/mod logic.  Unfortunately, this means that the
79    inline code for div/mod now has one more comparison than before.
80    Fast paths (quotient > 0 or remainder = 0) are not affected, though.
81    The problem was with quotient = 0, because that alone does not tell
82    us which way the rounding went.  One then has to look at whether
83    remainder and divisor have the same sign...  :(
84    
85    Anyway, I replaced the bootfiles with fresh ones...
86    
87    ----------------------------------------------------------------------
88    Name: Matthias Blume
89    Date: 2002/03/29 14:10:00 EST
90    Tag: blume-20020329-inlprims
91    Description:
92    
93    NEW BOOTFILES!!!    Version number bumped to 110.39.3.
94    
95    Primops have changed. This means that the bin/boot-file formats have
96    changed as well.
97    
98    To make sure that there is no confusion, I made a new version.
99    
100    
101    CHANGES:
102    
103    * removed REMT from mltree (remainder should never overflow).
104    
105    * added primops to deal with divisions of all flavors to the frontend
106    
107    * handled these primops all the way through so they map to their respective
108      MLRISC support
109    
110    * used these primops in the implementation of Int, Int32, Word, Word32
111    
112    * removed INLDIV, INLMOD, and INLREM as they are no longer necessary
113    
114    * parameterized INLMIN, INLMAX, and INLABS by a numkind
115    
116    * translate.sml now deals with all flavors of INL{MIN,MAX,ABS}, including
117      floating point
118    
119    * used INL{MIN,MAX,ABS} in the implementation of Int, Int32, Word, Word32,
120      and Real (but Real.abs maps to a separate floating-point-only primop)
121    
122    
123    TODO items:
124    
125    * Hacked Alpha32 instruction selection, disabling the selection of REMx
126      instructions because the machine instruction encoder cannot handle
127      them.  (Hppa, PPC, and Sparc instruction selection did not handle
128      REM in the first place, and REM is supported by the x86 machine coder.)
129    
130    * Handle DIV and MOD with DIV_TO_NEGINF directly in the x86 instruction
131      selection phase.  (The two can be streamlined because the hardware
132      delivers both quotient and remainder at the same time anyway.)
133    
134    * Think about what to do with "valOf(Int32.minInt) div ~1" and friends.
135      (Currently the behavior is inconsistent both across architectures and
136      wrt. the draft Basis spec.)
137    
138    * Word8 should eventually be handled natively, too.
139    
140    * There seems to be one serious bug in mltree-gen.sml.  It appears, though,
141      as if there currently is no execution path that could trigger it in
142      SML/NJ.  (The assumptions underlying functions arith and promotable do not
143      hold for things like multiplication and division.)
144    
145    ----------------------------------------------------------------------
146    Name: Matthias Blume
147    Date: 2002/03/27 16:27:00 EST
148    Tag: blume-20020327-mlrisc-divisions
149    Description:
150    
151    Added support for all four division operations (ML's div, mod, quot,
152    and rem) to MLRISC.  In the course of doing so, I also rationalized
153    the naming (no more annoying switch-around of DIV and QUOT), by
154    parameterizing the operation by div_rounding_mode (which can be either
155    DIV_TO_ZERO or DIV_TO_NEGINF).
156    
157    The generic MLTreeGen functor takes care of compiling all four
158    operations down to only round-to-zero div.
159    
160    Missing pieces:
161    
162      * Doing something smarter than relying on MLTreeGen on architectures
163        like, e.g., the x86 where hardware division delivers both quotient and
164        remainder at the same time.  With this, the implementation of the
165        round-to-neginf operations could be further streamlined.
166    
167      * Remove inlining support for div/mod/rem from the frontend and replace it
168        with primops that get carried through to the backend.  Do this for all
169        int and word types.
170    
171    ----------------------------------------------------------------------
172    Name: Matthias Blume
173    Date: 2002/03/25 17:25:00 EST
174    Tag: blume-20020325-divmod
175    Description:
176    
177    I improved (hopefully without breaking them) the implementation of Int.div,
178    Int.mod, and Int.rem.   For this, the code in translate.sml now takes
179    advantage of the following observations:
180    
181      Let  q = x quot y      r = x rem y
182           d = x div  y      m = x mod y
183    
184    where "quot" is the round-to-zero version of integer division that
185    hardware usually provides.  Then we have:
186    
187         r = x - q * y        where neither the * nor the - will overflow
188         d = if q >= 0 orelse x = q * y then q else q - 1
189                              where neither the * nor the - will overflow
190         m = if q >= 0 orelse r = 0 then r else r + y
191                              where the + will not overflow
192    
193    This results in substantial simplification of the generated code.
194    The following table shows the number of CFG nodes and edges generated
195    for
196            fun f (x, y) = x OPER y
197            (* with OPER \in div, mod, quot, rem *)
198    
199    
200        OPER | nodes(old) | edges(old) | nodes(new) | edges(new)
201        --------------------------------------------------------
202         div |         24 |         39 |         12 |         16
203         mod |         41 |         71 |         12 |         16
204        quot |          8 |         10 |          8 |         10
205         rem |         10 |         14 |          8 |         10
206    
207    
208    ----------------------------------------------------------------------
209    Name: Matthias Blume
210    Date: 2002/03/25 22:06:00 EST
211    Tag: blume-20020325-cprotobug
212    Description:
213    
214    Fixed a bug in cproto (c prototype decoder).
215    
216    ----------------------------------------------------------------------
217    Name: Matthias Blume
218    Date: 2002/03/25 16:00:00 EST
219    Tag: blume-20020325-raw-primops
220    Description:
221    
222    I did some cleanup to Allen's new primop code and
223    replaced yesterday's bootfiles with new ones.
224    (But they are stored in the same place.)
225    
226    ----------------------------------------------------------------------
227    Name: Matthias Blume
228    Date: 2002/03/24 22:40:00 EST
229    Tag: blume-20020324-bootfiles
230    Description:
231    
232    Made the bootfiles that Allen asked for.
233    
234    ----------------------------------------------------------------------
235    Name: Allen Leung
236    Date: 2002/03/23 15:50:00 EST
237    Tag: leunga-20020323-flint-cps-rcc-primops
238    Description:
239    
240      1. Changes to FLINT primops:
241    
242        (* make a call to a C-function;
243         * The primop carries C function prototype information and specifies
244         * which of its (ML-) arguments are floating point. C prototype
245         * information is for use by the backend, ML information is for
246         * use by the CPS converter. *)
247      | RAW_CCALL of { c_proto: CTypes.c_proto,
248                       ml_args: ccall_type list,
249                       ml_res_opt: ccall_type option,
250                       reentrant : bool
251                     } option
252       (* Allocate uninitialized storage on the heap.
253        * The record is meant to hold short-lived C objects, i.e., they
254        * are not ML pointers.  With the tag, the representation is
255        * the same as RECORD with tag tag_raw32 (sz=4), or tag_fblock (sz=8)
256        *)
257      | RAW_RECORD of {tag:bool,sz:int}
258      and ccall_type = CCALL_INT32 | CCALL_REAL64 | CCALL_ML_PTR
259    
260      2.  These CPS primops are now overloaded:
261    
262           rawload of {kind:numkind}
263           rawstore of {kind:numkind}
264    
265          The one argument form is:
266    
267             rawload {kind} address
268    
269          The two argument form is:
270    
271             rawload {kind} [ml object, byte-offset]
272    
273      3. RAW_CCALL/RCC now takes two extra arguments:
274    
275         a. The first is whether the C call is reentrant, i.e., whether
276            ML state should be saved and restored.
277         b. The second argument is a string argument specifying the name of
278            library and the C function.
279    
280         These things are currently not handled in the code generator, yet.
281    
282      4. In CProto,
283    
284         An encoding type of "bool" means "ml object" and is mapped into
285         C prototype of PTR.  Note that "bool" is different than "string",
286         even though "string" is also mapped into PTR, because "bool"
287         is assigned an CPS type of BOGt, while "string" is assigned INT32t.
288    
289      5. Pickler/unpicker
290    
291         Changed to handle RAW_RECORD and newest RAW_CCALL
292    
293      6. MLRiscGen,
294    
295         1. Changed to handle the new rawload/rawstore/rawrecord operators.
296         2. Code for handling C Calls has been moved to a new module CPSCCalls,
297            in the file CodeGen/cpscompile/cps-c-calls.sml
298    
299      7. Added the conditional move operator
300    
301             condmove of branch
302    
303         to cps.  Generation of this is still buggy so it is currently
304         disabled.
305    
306    ----------------------------------------------------------------------
307    Name: Lal George
308    Date: 2002/03/22 14:18:25 EST
309    Tag: george-20020322-cps-branch-prob
310    Description:
311    
312    Implemented the Ball-Larus branch prediction-heuristics, and
313    incorporated graphical viewers for control flow graphs.
314    
315    Ball-Larus Heuristics:
316    ---------------------
317    See the file compiler/CodeGen/cpscompile/cpsBranchProb.sml.
318    
319    By design it uses the Dempster-Shafer theory for combining
320    probabilities.  For example, in the function:
321    
322        fun f(n,acc) = if n = 0 then acc else f(n-1, n*acc)
323    
324    the ball-larus heuristics predicts that the n=0 is unlikely
325    (OH-heuristic), and the 'then' branch is unlikely because of the
326    RH-heuristic -- giving the 'then' branch an even lower combined
327    probability using the Dempster-Shafer theory.
328    
329    Finally, John Reppy's loop analysis in MLRISC, further lowers the
330    probability of the 'then' branch because of the loop in the else
331    branch.
332    
333    
334    Graphical Viewing:
335    ------------------
336    I merely plugged in Allen's graphical viewers into the compiler. The
337    additional code is not much. At the top level, saying:
338    
339            Control.MLRISC.getFlag "cfg-graphical-view" := true;
340    
341    will display the graphical view of the control flow graph just before
342    back-patching.  daVinci must be in your path for this to work. If
343    daVinci is not available, then the default viewer can be changed
344    using:
345    
346            Control.MLRISC.getString "viewer"
347    
348    which can be set to "dot" or "vcg" for the corresponding viewers. Of
349    course, these viewers must be in your path.
350    
351    The above will display the compilation unit at the level of clusters,
352    many of which are small, boring, and un-interesting. Also setting:
353    
354            Control.MLRISC.getInt "cfg-graphical-view_size"
355    
356    will display clusters that are larger than the value set by the above.
357    
358    
359    ----------------------------------------------------------------------
360    Name: Matthias Blume
361    Date: 2002/03/21 22:20:00 EST
362    Tag: blume-20020321-kmp-bugfix
363    Description:
364    
365    Changed the interface to the KMP routine in PreString and fixed
366    a minor bug in one place where it was used.
367    
368    ----------------------------------------------------------------------
369  Name: Allen Leung  Name: Allen Leung
370  Date: 2002/03/21 20:30:00 EST  Date: 2002/03/21 20:30:00 EST
371  Tag: leunga-20020321-cfg  Tag: leunga-20020321-cfg

Legend:
Removed from v.1158  
changed lines
  Added in v.1189

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