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

Legend:
Removed from v.1152  
changed lines
  Added in v.1186

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