Diff of /sml/trunk/HISTORY

Parent Directory | Revision Log | Patch

	revision 1055, Thu Feb 7 20:38:59 2002 UTC	revision 1126, Thu Mar 7 21:16:28 2002 UTC
#	Line 13	Line 13
13	Description:	Description:
14
15	----------------------------------------------------------------------	----------------------------------------------------------------------
16		Name: Matthias Blume
17		Date: 2002/03/07 16:15:00 EST
18		Tag: blume-20020307-controls
19		Description:
20
21		This is a very large but mostly boring patch which makes (almost)
22		every tuneable compiler knob (i.e., pretty much everything under
23		Control.* plus a few other things) configurable via both the command
24		line and environment variables in the style CM did its configuration
25		until now.
26
27		Try starting sml with '-h' (or, if you are brave, '-H')
28
29		To this end, I added a structure Controls : CONTROLS to smlnj-lib.cm which
30		implements the underlying generic mechanism.
31
32		The interface to some of the existing such facilities has changed somewhat.
33		For example, the MLRiscControl module now provides mkFoo instead of getFoo.
34		(The getFoo interface is still there for backward-compatibility, but its
35		use is deprecated.)
36
37		The ml-build script passes -Cxxx=yyy command-line arguments through so
38		that one can now twiddle the compiler settings when using this "batch"
39		compiler.
40
41		TODO items:
42
43		We should go through and throw out all controls that are no longer
44		connected to anything.  Moreover, we should go through and provide
45		meaningful (and correct!) documentation strings for those controls
46		that still are connected.
47
48		Currently, multiple calls to Controls.new are accepted (only the first
49		has any effect).  Eventually we should make sure that every control
50		is being made (via Controls.new) exactly once.  Future access can then
51		be done using Controls.acc.
52
53		Finally, it would probably be a good idea to use the getter-setter
54		interface to controls rather than ref cells.  For the time being, both
55		styles are provided by the Controls module, but getter-setter pairs are
56		better if thread-safety is of any concern because they can be wrapped.
57
58		*****************************************
59
60		One bug fix: The function blockPlacement in three of the MLRISC
61		backpatch files used to be hard-wired to one of two possibilities at
62		link time (according to the value of the placementFlag).  But (I
63		think) it should rather sense the flag every time.
64
65		*****************************************
66
67		Other assorted changes (by other people who did not supply a HISTORY entry):
68
69		1. the cross-module inliner now works much better (Monnier)
70		2. representation of weights, frequencies, and probabilities in MLRISC
71		changed in preparation of using those for weighted block placement
72		(Reppy, George)
73
74		----------------------------------------------------------------------
75		Name: Lal George
76		Date: 2002/03/07 14:44:24 EST 2002
77		Tag: george-20020307-weighted-block-placement
78
79		Tested the weighted block placement optimization on all architectures
80		(except the hppa) using AMPL to generate the block and edge frequencies.
81		Changes were required in the machine properties to correctly
82		categorize trap instructions. There is an MLRISC flag
83		"weighted-block-placement" that can be used to enable weighted block
84		placement, but this will be ineffective without block/edge
85		frequencies (coming soon).
86
87
88		----------------------------------------------------------------------
89		Name: Lal George
90		Date: 2002/03/05 17:24:48 EST
91		Tag: george-20020305-linkage-cluster
92
93		In order to support the block placement optimization, a new cluster
94		is generated as the very first cluster (called the linkage cluster).
95		It contains a single jump to the 'real' entry point for the compilation
96		unit. Block placement has no effect on the linkage cluster itself, but
97		all the other clusters  have full freedom in the manner in which they
98		reorder blocks or functions.
99
100		On the x86 the typical linkage code that is generated is:
101		----------------------
102		.align 2
103		L0:
104		addl    $L1-L0, 72(%esp)
105		jmp     L1
106
107
108		.align  2
109		L1:
110		----------------------
111
112		72(%esp) is the memory location for the stdlink register. This
113		must contain the address of the CPS function being called. In the
114		above example, it contains the address of  L0; before
115		calling L1 (the real entry point for the compilation unit), it
116		must contain the address for L1, and hence
117
118		addl $L1-L0, 72(%esp)
119
120		I have tested this on all architectures except the hppa.The increase
121		in code size is of course negligible
122
123		----------------------------------------------------------------------
124		Name: Allen Leung
125		Date: 2002/03/03 13:20:00 EST
126		Tag: leunga-20020303-mlrisc-tools
127
128		Added #[ ... ] expressions to mlrisc tools
129
130		----------------------------------------------------------------------
131		Name: Matthias Blume
132		Date: 2002/02/27 12:29:00 EST
133		Tag: blume-20020227-cdebug
134		Description:
135
136		- made types in structure C and C_Debug to be equal
137		- got rid of code duplication (c-int.sml vs. c-int-debug.sml)
138		- there no longer is a C_Int_Debug (C_Debug is directly derived from C)
139
140		----------------------------------------------------------------------
141		Name: Matthias Blume
142		Date: 2002/02/26 12:00:00 EST
143		Tag: blume-20020226-ffi
144		Description:
145
146		1. Fixed a minor bug in CM's "noweb" tool:
147		If numbering is turned off, then truly don't number (i.e., do not
148		supply the -L option to noweb).  The previous behavior was to supply
149		-L'' -- which caused noweb to use the "default" line numbering scheme.
150		Thanks to Chris Richards for pointing this out (and supplying the fix).
151
152		2. Once again, I reworked some aspects of the FFI:
153
154		A. The incomplete/complete type business:
155
156		- Signatures POINTER_TO_INCOMPLETE_TYPE and accompanying functors are
157		gone!
158		- ML types representing an incomplete type are now *equal* to
159		ML types representing their corresponding complete types (just like
160		in C).  This is still safe because ml-nlffigen will not generate
161		RTTI for incomplete types, nor will it generate functions that
162		require access to such RTTI.   But when ML code generated from both
163		incomplete and complete versions of the C type meet, the ML types
164		are trivially interoperable.
165
166		NOTE:  These changes restore the full generality of the translation
167		(which was previously lost when I eliminated functorization)!
168
169		B. Enum types:
170
171		- Structure C now has a type constructor "enum" that is similar to
172		how the "su" constructor works.  However, "enum" is not a phantom
173		type because each "T enum" has values (and is isomorphic to
174		MLRep.Signed.int).
175		- There are generic access operations for enum objects (using
176		MLRep.Signed.int).
177		- ml-nlffigen will generate a structure E_foo for each "enum foo".
178		* The structure contains the definition of type "mlrep" (the ML-side
179		representation type of the enum).  Normally, mlrep is the same
180		as "MLRep.Signed.int", but if ml-nlffigen was invoked with "-ec",
181		then mlrep will be defined as a datatype -- thus facilitating
182		pattern matching on mlrep values.
183		("-ec" will be suppressed if there are duplicate values in an
184		enumeration.)
185		* Constructors ("-ec") or values (no "-ec") e_xxx of type mlrep
186		will be generated for each C enum constant xxx.
187		* Conversion functions m2i and i2m convert between mlrep and
188		MLRep.Signed.int.  (Without "-ec", these functions are identities.)
189		* Coversion functions c and ml convert between mlrep and "tag enum".
190		* Access functions (get/set) fetch and store mlrep values.
191		- By default (unless ml-nlffigen was invoked with "-nocollect"), unnamed
192		enumerations are merged into one single enumeration represented by
193		structure E_'.
194
195		----------------------------------------------------------------------
196		Name: Allen Leung
197		Date: 2002/02/25 04:45:00 EST
198		Tag: leunga-20020225-cps-spill
199
200		This is a new implementation of the CPS spill phase.
201		The new phase is in the new file compiler/CodeGen/cpscompile/spill-new.sml
202		In case of problems, replace it with the old file spill.sml
203
204		The current compiler runs into some serious performance problems when
205		constructing a large record.  This can happen when we try to compile a
206		structure with many items.  Even a very simple structure like the following
207		makes the compiler slow down.
208
209		structure Foo = struct
210		val x_1 = 0w1 : Word32.int
211		val x_2 = 0w2 : Word32.int
212		val x_3 = 0w3 : Word32.int
213		...
214		val x_N = 0wN : Word32.int
215		end
216
217		The following table shows the compile time, from N=1000 to N=4000,
218		with the old compiler:
219
220		N
221		1000   CPS 100 spill                           0.04u  0.00s  0.00g
222		MLRISC ra                               0.06u  0.00s  0.05g
223		(spills = 0 reloads = 0)
224		TOTAL                                   0.63u  0.07s  0.21g
225
226		1100   CPS 100 spill                           8.25u  0.32s  0.64g
227		MLRISC ra                               5.68u  0.59s  3.93g
228		(spills = 0 reloads = 0)
229		TOTAL                                   14.71u  0.99s  4.81g
230
231		1500   CPS 100 spill                           58.55u  2.34s  1.74g
232		MLRISC ra                               5.54u  0.65s  3.91g
233		(spills = 543 reloads = 1082)
234		TOTAL                                   65.40u  3.13s  6.00g
235
236		2000   CPS 100 spill                           126.69u  4.84s  3.08g
237		MLRISC ra                               0.80u  0.10s  0.55g
238		(spills = 42 reloads = 84)
239		TOTAL                                   129.42u  5.10s  4.13g
240
241		3000   CPS 100 spill                           675.59u  19.03s  11.64g
242		MLRISC ra                               2.69u  0.27s  1.38g
243		(spills = 62 reloads = 124)
244		TOTAL                                   682.48u  19.61s  13.99g
245
246		4000   CPS 100 spill                           2362.82u  56.28s  43.60g
247		MLRISC ra                               4.96u  0.27s  2.72g
248		(spills = 85 reloads = 170)
249		TOTAL                                   2375.26u  57.21s  48.00g
250
251		As you can see the old cps spill module suffers from some serious
252		performance problem.  But since I cannot decipher the old code fully,
253		instead of patching the problems up, I'm reimplementing it
254		with a different algorithm.  The new code is more modular,
255		smaller when compiled, and substantially faster
256		(O(n log n) time and O(n) space).  Timing of the new spill module:
257
258		4000  CPS 100 spill                           0.02u  0.00s  0.00g
259		MLRISC ra                               0.25u  0.02s  0.15g
260		(spills=1 reloads=3)
261		TOTAL                                   7.74u  0.34s  1.62g
262
263		Implementation details:
264
265		As far as I can tell, the purpose of the CPS spill module is to make sure the
266		number of live variables at any program point (the bandwidth)
267		does not exceed a certain limit, which is determined by the
268		size of the spill area.
269
270		When the bandwidth is too large, we decrease the register pressure by
271		packing live variables into spill records.  How we achieve this is
272		completely different than what we did in the old code.
273
274		First, there is something about the MLRiscGen code generator
275		that we should be aware of:
276
277		o MLRiscGen performs code motion!
278
279		In particular, it will move floating point computations and
280		address computations involving only the heap pointer to
281		their use sites (if there is only a single use).
282		What this means is that if we have a CPS record construction
283		statement
284
285		RECORD(k,vl,w,e)
286
287		we should never count the new record address w as live if w
288		has only one use (which is often the case).
289
290		We should do something similar to floating point, but the transformation
291		there is much more complex, so I won't deal with that.
292
293		Secondly, there are now two new cps primops at our disposal:
294
295		1. rawrecord of record_kind option
296		This pure operator allocates some uninitialized storage from the heap.
297		There are two forms:
298
299		rawrecord NONE [INT n]  allocates a tagless record of length n
300		rawrecord (SOME rk) [INT n] allocates a tagged record of length n
301		and initializes the tag.
302
303		2. rawupdate of cty
304		rawupdate cty (v,i,x)
305		Assigns to x to the ith component of record v.
306		The storelist is not updated.
307
308		We use these new primops for both spilling and increment record construction.
309
310		1. Spilling.
311
312		This is implemented with a linear scan algorithm (but generalized
313		to trees).  The algorithm will create a single spill record at the
314		beginning of the cps function and use rawupdate to spill to it,
315		and SELECT or SELp to reload from it.  So both spills and reloads
316		are fine-grain operations.  In contrast, in the old algorithm
317		"spills" have to be bundled together in records.
318
319		Ideally, we should sink the spill record construction to where
320		it is needed.  We can even split the spill record into multiple ones
321		at the places where they are needed.  But CPS is not a good
322		representation for global code motion, so I'll keep it simple and
323		am not attempting this.
324
325		2. Incremental record construction (aka record splitting).
326
327		Long records with many component values which are simulatenously live
328		(recall that single use record addresses are not considered to
329		be live) are constructed with rawrecord and rawupdate.
330		We allocate space on the heap with rawrecord first, then gradually
331		fill it in with rawupdate.  This is the technique suggested to me
332		by Matthias.
333
334		Some restrictions on when this is applicable:
335		1. It is not a VECTOR record.  The code generator currently does not handle
336		this case. VECTOR record uses double indirection like arrays.
337		2. All the record component values are defined in the same "basic block"
338		as the record constructor.  This is to prevent speculative
339		record construction.
340
341		----------------------------------------------------------------------
342		Name: Allen Leung
343		Date: 2002/02/22 01:02:00 EST
344		Tag: leunga-20020222-mlrisc-tools
345
346		Minor bug fixes in the parser and rewriter
347
348		----------------------------------------------------------------------
349		Name: Allen Leung
350		Date: 2002/02/21 20:20:00 EST
351		Tag: leunga-20020221-peephole
352
353		Regenerated the peephole files.  Some contained typos in the specification
354		and some didn't compile because of pretty printing bugs in the old version
355		of 'nowhere'.
356
357		----------------------------------------------------------------------
358		Name: Allen Leung
359		Date: 2002/02/19 20:20:00 EST
360		Tag: leunga-20020219-mlrisc-tools
361		Description:
362
363		Minor bug fixes to the mlrisc-tools library:
364
365		1.  Fixed up parsing colon suffixed keywords
366		2.  Added the ability to shut the error messages up
367		3.  Reimplemented the pretty printer and fixed up/improved
368		the pretty printing of handle and -> types.
369		4.  Fixed up generation of literal symbols in the nowhere tool.
370		5.  Added some SML keywords to to sml.sty
371
372		----------------------------------------------------------------------
373		Name: Matthias Blume
374		Date: 2002/02/19 16:20:00 EST
375		Tag: blume-20020219-cmffi
376		Description:
377
378		A wild mix of changes, some minor, some major:
379
380		* All C FFI-related libraries are now anchored under $c:
381		$/c.cm      --> $c/c.cm
382		$/c-int.cm  --> $c/internals/c-int.cm
383		$/memory.cm --> $c/memory/memory.cm
384
385		* "make" tool (in CM) now treats its argument pathname slightly
386		differently:
387		1. If the native expansion is an absolute name, then before invoking
388		the "make" command on it, CM will apply OS.Path.mkRelative
389		(with relativeTo = OS.FileSys.getDir()) to it.
390		2. The argument will be passed through to subsequent phases of CM
391		processing without "going native".  In particular, if the argument
392		was an anchored path, then "make" will not lose track of that anchor.
393
394		* Compiler backends now "know" their respective C calling conventions
395		instead of having to be told about it by ml-nlffigen.  This relieves
396		ml-nlffigen from one of its burdens.
397
398		* The X86Backend has been split into X86CCallBackend and X86StdCallBackend.
399
400		* Export C_DEBUG and C_Debug from $c/c.cm.
401
402		* C type encoding in ml-nlffi-lib has been improved to model the conceptual
403		subtyping relationship between incomplete pointers and their complete
404		counterparts.  For this, ('t, 'c) ptr has been changed to 'o ptr --
405		with the convention of instantiating 'o with ('t, 'c) obj whenever
406		the pointer target type is complete.  In the incomplete case, 'o
407		will be instantiated with some "'c iobj" -- a type obtained by
408		using one of the functors PointerToIncompleteType or PointerToCompleteType.
409
410		Operations that work on both incomplete and complete pointer types are
411		typed as taking an 'o ptr while operations that require the target to
412		be known are typed as taking some ('t, 'c) obj ptr.
413
414		voidptr is now a bit "more concrete", namely "type voidptr = void ptr'"
415		where void is an eqtype without any values.  This makes it possible
416		to work on voidptr values using functions meant to operate on light
417		incomplete pointers.
418
419		* As a result of the above, signature POINTER_TO_INCOMPLETE_TYPE has
420		been vastly simplified.
421
422		----------------------------------------------------------------------
423		Name: Matthias Blume
424		Date: 2002/02/19 10:48:00 EST
425		Tag: blume-20020219-pqfix
426		Description:
427
428		Applied Chris Okasaki's bug fix for priority queues.
429
430		----------------------------------------------------------------------
431		Name: Matthias Blume
432		Date: 2002/02/15 17:05:00
433		Tag: Release_110_39
434		Description:
435
436		Last-minute retagging is becoming a tradition... :-(
437
438		This is the working release 110.39.
439
440		----------------------------------------------------------------------
441		Name: Matthias Blume
442		Date: 2002/02/15 16:00:00 EST
443		Tag: Release_110_39-orig
444		Description:
445
446		Working release 110.39.  New bootfiles.
447
448		(Update: There was a small bug in the installer so it wouldn't work
449		with all shells.  So I retagged. -Matthias)
450
451		----------------------------------------------------------------------
452		Name: Matthias Blume
453		Date: 2002/02/15 14:17:00 EST
454		Tag: blume-20020215-showbindings
455		Description:
456
457		Added EnvRef.listBoundSymbols and CM.State.showBindings.  Especially
458		the latter can be useful for exploring what bindings are available at
459		the interactive prompt.  (The first function returns only the list
460		of symbols that are really bound, the second prints those but also the
461		ones that CM's autoloading mechanism knows about.)
462
463		----------------------------------------------------------------------
464		Name: Matthias Blume
465		Date: 2002/02/15 12:08:00 EST
466		Tag: blume-20020215-iptrs
467		Description:
468
469		Two improvements to ml-nlffigen:
470
471		1. Write files only if they do not exist or if their current contents
472		do not coincide with what's being written.  (That is, avoid messing
473		with the time stamps unless absolutely necessary.)
474
475		2. Implement a "repository" mechanism for generated files related
476		to "incomplete pointer types".   See the README file for details.
477
478		----------------------------------------------------------------------
479		Name: Matthias Blume
480		Date: 2002/02/14 11:50:00 EST
481		Tag: blume-20020214-quote
482		Description:
483
484		Added a type 't t_' to tag.sml (in ml-nlffi-lib.cm).  This is required
485		because of the new and improved tag generation scheme.  (Thanks to Allen
486		Leung for pointing it out.)
487
488		----------------------------------------------------------------------
489		Name: Lal George
490		Date: 2002/02/14 09:55:27 EST 2002
491		Tag: george-20020214-isabelle-bug
492		Description:
493
494		Fixed the MLRISC bug sent by Markus Wenzel regarding the compilation
495		of Isabelle on the x86.
496
497		From Allen:
498		-----------
499		I've found the problem:
500
501		in ra-core.sml, I use the counter "blocked" to keep track of the
502		true number of elements in the freeze queue.  When the counter goes
503		to zero, I skip examining the queue.  But I've messed up the
504		bookkeeping in combine():
505
506		else ();
507		case !ucol of
508		PSEUDO => (if !cntv > 0 then
509		(if !cntu > 0 then blocked := !blocked - 1 else ();
510		^^^^^^^^^^^^^^^^^^^^^^^
511		moveu := mergeMoveList(!movev, !moveu)
512		)
513		else ();
514
515		combine() is called to coalesce two nodes u and v.
516		I think I was thinking that if the move counts of u and v are both
517		greater than zero then after they are coalesced then one node is
518		removed from the freeze queue.  Apparently I was thinking that
519		both u and v are of low degree, but that's clearly not necessarily true.
520
521
522		02/12/2002:
523		Here's the patch.  HOL now compiles.
524
525		I don't know how this impact on performance (compile
526		time or runtime).  This bug caused the RA (especially on the x86)
527		to go thru the potential spill phase when there are still nodes on the
528		freeze queue.
529
530
531
532
533		----------------------------------------------------------------------
534		Name: Matthias Blume
535		Date: 2002/02/13 22:40:00 EST
536		Tag: blume-20020213-fptr-rtti
537		Description:
538
539		Fixed a bug in ml-nlffigen that was introduced with one of the previous
540		updates.
541
542		----------------------------------------------------------------------
543		Name: Matthias Blume
544		Date: 2002/02/13 16:41:00 EST
545		Tag: blume-20020213-cmlpq
546		Description:
547
548		Added new priority queue export symbols (which have just been added to
549		smlnj-lib.cm) to CML's version of smlnj-lib.cm.  (Otherwise CML would
550		not compile and the installer would choke.)
551
552		----------------------------------------------------------------------
553		Name: Matthias Blume
554		Date: 2002/02/13 16:15:00 EST
555		Tag: blume-20020213-various
556		Description:
557
558		1. More tweaks to ml-nlffigen:
559
560		- better internal datastructures (resulting in slight speedup)
561		- "-match" option requires exact match
562		- "localized" gensym counters (untagged structs/unions nested within
563		other structs/unions or within typedefs get a fresh counter; their
564		tag will be prefixed by a concatenation of their parents' tags)
565		- bug fixes (related to calculation of transitive closure of types
566		to be included in the output)
567
568		2. Minor Basis updates:
569
570		- added implementations for List.collate and Option.app
571
572		----------------------------------------------------------------------
573		Name: Matthias Blume
574		Date: 2002/02/11 15:55:00 EST
575		Tag: blume-20020211-gensym
576		Description:
577
578		Added a "-gensym" option to command line of ml-nlffigen.  This can be
579		used to specify a "stem" -- a string that is inserted in all "gensym'd"
580		names (ML structure names that correspond to unnamed C structs, unions,
581		and enums), so that separate runs of ml-nlffigen do not clash.
582
583		----------------------------------------------------------------------
584		Name: Matthias Blume
585		Date: 2002/02/11 12:05:00 EST
586		Tag: blume-20020211-gensml
587		Description:
588
589		A quick fix for a problem with GenSML (in the pgraph-util library):
590		Make generation of toplevel "local" optional.  (Strictly speaking,
591		signature definitions within "local" are not legal SML.)
592
593		Other than that: updates to INSTALL and cm/TODO.
594
595		----------------------------------------------------------------------
596		Name: Matthias Blume
597		Date: 2002/02/08 15:00:00 EST
598		Tag: blume-20020208-uniquepid
599		Description:
600
601		0. Version number has been bumped to 110.38.1.  NEW BOOTFILES!!!
602
603		1. The installer (config/install.sh) has gotten smarter:
604
605		- Configuration options are a bit easier to specify now
606		(in config/targets).
607		- Bug in recognizing .tar.bz2 files fixed.
608		- Installer automatically resolves dependencies between
609		configuration options (e.g., if you ask for eXene, you will
610		also get cml -- regardless whether you asked for it or not).
611		- Installer can run in "quieter mode" by setting the environment
612		variable INSTALL_QUIETLY to "true".  "Quieter" does not mean
613		"completely silent", though.
614		- Build HashCons library as part of smlnj-lib.
615
616		2. A new scheme for assigning persistent identifiers to compilation
617		units (and, by extension, to types etc.) has been put into place.
618		This fixes a long-standing bug where types and even dynamic values
619		can get internally confused, thereby compromising type safety
620		(abstraction) and dynamic correctness.  See
621
622		http://cm.bell-labs.com/cm/cs/who/blume/pid-confusion.tgz
623
624		for an example of how things could go wrong until now.
625
626		The downside of the new scheme is that pids are not quite as
627		persistent as they used to be: CM will generate a fresh pid
628		for every compilation unit that it thinks it sees for the first
629		time.  That means that if you compile starting from a clean, fresh
630		source tree at two different times, you end up with different
631		binaries.
632
633		Cutoff recompilation, however, has not been compromised because
634		CM keeps pid information in special caches between runs.
635
636		----------------------------------------------------------------------
637	Name: Lal George	Name: Lal George
638	Date: 2002/02/07 15:34:13 EST 2002	Date: 2002/02/07 15:34:13 EST 2002
639	Tag: <none>	Tag: <none>

---

Colored Diff Long Colored Diff Unidiff Context Diff Side by Side

Legend: Removed from v.1055   changed lines   Added in v.1126

---

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