Diff of /sml/trunk/HISTORY

Parent Directory | Revision Log | Patch

	revision 1067, Fri Feb 15 17:08:17 2002 UTC	revision 1175, Mon Mar 25 03:38:44 2002 UTC
#	Line 14	Line 14
14
15	----------------------------------------------------------------------	----------------------------------------------------------------------
16	Name: Matthias Blume	Name: Matthias Blume
17		Date: 2002/03/24 22:40:00 EST
18		Tag: blume-20020324-bootfiles
19		Description:
20
21		Made the bootfiles that Allen asked for.
22
23		----------------------------------------------------------------------
24		Name: Allen Leung
25		Date: 2002/03/23 15:50:00 EST
26		Tag: leunga-20020323-flint-cps-rcc-primops
27		Description:
28
29		1. Changes to FLINT primops:
30
31		(* make a call to a C-function;
32		* The primop carries C function prototype information and specifies
33		* which of its (ML-) arguments are floating point. C prototype
34		* information is for use by the backend, ML information is for
35		* use by the CPS converter. *)
36		| RAW_CCALL of { c_proto: CTypes.c_proto,
37		ml_args: ccall_type list,
38		ml_res_opt: ccall_type option,
39		reentrant : bool
40		} option
41		(* Allocate uninitialized storage on the heap.
42		* The record is meant to hold short-lived C objects, i.e., they
43		* are not ML pointers.  With the tag, the representation is
44		* the same as RECORD with tag tag_raw32 (sz=4), or tag_fblock (sz=8)
45		*)
46		| RAW_RECORD of {tag:bool,sz:int}
47		and ccall_type = CCALL_INT32 | CCALL_REAL64 | CCALL_ML_PTR
48
49		2.  These CPS primops are now overloaded:
50
51		rawload of {kind:numkind}
52		rawstore of {kind:numkind}
53
54		The one argument form is:
55
56		rawload {kind} address
57
58		The two argument form is:
59
60		rawload {kind} [ml object, byte-offset]
61
62		3. RAW_CCALL/RCC now takes two extra arguments:
63
64		a. The first is whether the C call is reentrant, i.e., whether
65		ML state should be saved and restored.
66		b. The second argument is a string argument specifying the name of
67		library and the C function.
68
69		These things are currently not handled in the code generator, yet.
70
71		4. In CProto,
72
73		An encoding type of "bool" means "ml object" and is mapped into
74		C prototype of PTR.  Note that "bool" is different than "string",
75		even though "string" is also mapped into PTR, because "bool"
76		is assigned an CPS type of BOGt, while "string" is assigned INT32t.
77
78		5. Pickler/unpicker
79
80		Changed to handle RAW_RECORD and newest RAW_CCALL
81
82		6. MLRiscGen,
83
84		1. Changed to handle the new rawload/rawstore/rawrecord operators.
85		2. Code for handling C Calls has been moved to a new module CPSCCalls,
86		in the file CodeGen/cpscompile/cps-c-calls.sml
87
88		7. Added the conditional move operator
89
90		condmove of branch
91
92		to cps.  Generation of this is still buggy so it is currently
93		disabled.
94
95		----------------------------------------------------------------------
96		Name: Lal George
97		Date: 2002/03/22 14:18:25 EST
98		Tag: george-20020322-cps-branch-prob
99		Description:
100
101		Implemented the Ball-Larus branch prediction-heuristics, and
102		incorporated graphical viewers for control flow graphs.
103
104		Ball-Larus Heuristics:
105		---------------------
106		See the file compiler/CodeGen/cpscompile/cpsBranchProb.sml.
107
108		By design it uses the Dempster-Shafer theory for combining
109		probabilities.  For example, in the function:
110
111		fun f(n,acc) = if n = 0 then acc else f(n-1, n*acc)
112
113		the ball-larus heuristics predicts that the n=0 is unlikely
114		(OH-heuristic), and the 'then' branch is unlikely because of the
115		RH-heuristic -- giving the 'then' branch an even lower combined
116		probability using the Dempster-Shafer theory.
117
118		Finally, John Reppy's loop analysis in MLRISC, further lowers the
119		probability of the 'then' branch because of the loop in the else
120		branch.
121
122
123		Graphical Viewing:
124		------------------
125		I merely plugged in Allen's graphical viewers into the compiler. The
126		additional code is not much. At the top level, saying:
127
128		Control.MLRISC.getFlag "cfg-graphical-view" := true;
129
130		will display the graphical view of the control flow graph just before
131		back-patching.  daVinci must be in your path for this to work. If
132		daVinci is not available, then the default viewer can be changed
133		using:
134
135		Control.MLRISC.getString "viewer"
136
137		which can be set to "dot" or "vcg" for the corresponding viewers. Of
138		course, these viewers must be in your path.
139
140		The above will display the compilation unit at the level of clusters,
141		many of which are small, boring, and un-interesting. Also setting:
142
143		Control.MLRISC.getInt "cfg-graphical-view_size"
144
145		will display clusters that are larger than the value set by the above.
146
147
148		----------------------------------------------------------------------
149		Name: Matthias Blume
150		Date: 2002/03/21 22:20:00 EST
151		Tag: blume-20020321-kmp-bugfix
152		Description:
153
154		Changed the interface to the KMP routine in PreString and fixed
155		a minor bug in one place where it was used.
156
157		----------------------------------------------------------------------
158		Name: Allen Leung
159		Date: 2002/03/21 20:30:00 EST
160		Tag: leunga-20020321-cfg
161		Description:
162
163		Fixed a potential problem in cfg edge splitting.
164
165		----------------------------------------------------------------------
166		Name: Allen Leung
167		Date: 2002/03/21 17:15:00 EST
168		Tag: leunga-20020321-x86-fp-cfg
169		Description:
170
171		1. Recoded the buggy parts of x86-fp.
172
173		a. All the block reordering code has been removed.
174		We now depend on the block placement phases to do this work.
175
176		b. Critical edge splitting code has been simplified and moved into the
177		CFG modules, as where they belong.
178
179		Both of these were quite buggy and complex.  The code is now much, much
180		simpler.
181
182		2. X86 backend.
183
184		a. Added instructions for 64-bit support.  Instruction selection for
185		64-bit has not been committed, however, since that
186		requires changes to MLTREE which haven't been approved by
187		Lal and John.
188
189		b. Added support for FUCOMI and FUCOMIP when generating code for
190		PentiumPro and above.  We only generate these instructions in
191		the fast-fp mode.
192
193		c. Added cases for JP and JNP in X86FreqProps.
194
195		3. CFG
196
197		CFG now has a bunch of methods for edge splitting and merging.
198
199		4. Machine description.
200
201		John's simplification of MLTREE_BASIS.fcond broke a few machine
202		description things:
203
204		rtl-build.{sig,sml} and hppa.mdl fixed.
205
206		NOTE: the machine description stuff in the repository is still broken.
207		Again, I can't put my fixes in because that involves
208		changes to MLTREE.
209
210		----------------------------------------------------------------------
211		Name: Matthias Blume
212		Date: 2002/03/20 15:55:00 EST
213		Tag: blume-20020320-kmp
214		Description:
215
216		Implemented Knuth-Morris-Pratt string matching in PreString and used
217		it for String.isSubstring, Substring.isSubstring, and
218		Substring.position.
219
220		(Might need some stress-testing.  Simple examples worked fine.)
221
222		----------------------------------------------------------------------
223		Name: Matthias Blume
224		Date: 2002/03/19 16:37:00 EST
225		Tag: blume-20020319-witnesses
226		Description:
227
228		Added a structure C.W and functions convert/Ptr.convert to ml-nlffi-lib.
229
230		This implements a generic mechanism for changing constness qualifiers
231		anywhere within big C types without resorting to outright "casts".
232		(So far, functions such as C.rw/C.ro or C.Ptr.rw/C.Ptr.ro only let you
233		modify the constness at the outermost level.)
234		The implementation of "convert" is based on the idea of "witness"
235		values -- values that are not used by the operation but whose types
236		"testify" to their applicability.  On the implementation side, "convert"
237		is simply a projection (returning its second curried argument).  With
238		cross-module inlining, it should not result in any machine code being
239		generated.
240
241		----------------------------------------------------------------------
242		Name: Matthias Blume
243		Date: 2002/03/15 16:40:00 EST
244		Tag: blume-20020315-basis
245		Description:
246
247		Provided (preliminary?) implementations for
248
249		{String,Substring}.{concatWith,isSuffix,isSubstring}
250
251		and
252
253		Substring.full
254
255		Those are in the Basis spec but they were missing in SML/NJ.
256
257		----------------------------------------------------------------------
258		Name: Matthias Blume
259		Date: 2002/03/14 21:30:00 EST
260		Tag: blume-20020314-controls
261		Description:
262
263		Controls:
264		---------
265
266		1. Factored out the recently-added Controls : CONTROLS stuff and put
267		it into its own library $/controls-lib.cm.  The source tree for
268		this is under src/smlnj-lib/Controls.
269
270		2. Changed the names of types and functions in this interface, so they
271		make a bit more "sense":
272
273		module -> registry
274		'a registry -> 'a group
275
276		3. The interface now deals in ref cells only.  The getter/setter interface
277		is (mostly) gone.
278
279		4. Added a function that lets one register an already-existing ref cell.
280
281		5. Made the corresponding modifications to the rest of the code so that
282		everything compiles again.
283
284		6. Changed the implementation of Controls.MLRISC back to something closer
285		to the original.  In particular, this module (and therefore MLRISC)
286		does not depend on Controls.  There now is some link-time code in
287		int-sys.sml that registers the MLRISC controls with the Controls
288		module.
289
290		CM:
291		---
292
293		* One can now specify the lambda-split aggressiveness in init.cmi.
294
295		----------------------------------------------------------------------
296		Name: Allen Leung
297		Date: 2002/03/13 17:30:00 EST
298		Tag: leunga-20020313-x86-fp-unary
299		Description:
300
301		Bug fix for:
302
303		> leunga@weaselbane:~/Yale/tmp/sml-dist{21} bin/sml
304		> Standard ML of New Jersey v110.39.1 [FLINT v1.5], March 08, 2002
305		> - fun f(x,(y,z)) = Real.~ y;
306		> [autoloading]
307		> [autoloading done]
308		>       fchsl   (%eax), 184(%esp)
309		> Error: MLRisc bug: X86MCEmitter.emitInstr
310		>
311		> uncaught exception Error
312		>   raised at: ../MLRISC/control/mlriscErrormsg.sml:16.14-16.19
313
314		The problem was that the code generator did not generate any fp registers
315		in this case, and the ra didn't know that it needed to run the X86FP phase to
316		translate the pseudo fp instruction.   This only happened with unary fp
317		operators in certain situations.
318
319		----------------------------------------------------------------------
320		Name: Matthias Blume
321		Date: 2002/03/13 14:00:00 EST
322		Tag: blume-20020313-overload-etc
323		Description:
324
325		1. Added _overload as a synonym for overload for backward compatibility.
326		(Control.overloadKW must be true for either version to be accepted.)
327
328		2. Fixed bug in install script that caused more things to be installed
329		than what was requested in config/targets.
330
331		3. Made CM aware of the (_)overload construct so that autoloading
332		works.
333
334		----------------------------------------------------------------------
335		Name: Matthias Blume
336		Date: 2002/03/12 22:03:00 EST
337		Tag: blume-20020312-url
338		Description:
339
340		Forgot to update BOOT and srcarchiveurl.
341
342		----------------------------------------------------------------------
343		Name: Matthias Blume
344		Date: 2002/03/12 17:30:00 EST
345		Tag: blume-20020312-version110392
346		Description:
347
348		Yet another version number bump (because of small changes to the
349		binfile format).  Version number is now 110.39.2.  NEW BOOTFILES!
350
351		Changes:
352
353		The new pid generation scheme described a few weeks ago was overly
354		complicated.  I implemented a new mechanism that is simpler and
355		provides a bit more "stability":  Once CM has seen a compilation
356		unit, it keeps its identity constant (as long as you do not delete
357		those crucial CM/GUID/* files).  This means that when you change
358		an interface, compile, then go back to the old interface, and
359		compile again, you arrive at the original pid.
360
361		There now also is a mechanism that instructs CM to use the plain
362		environment hash as a module's pid (effectively making its GUID
363		the empty string).  For this, "noguid" must be specified as an
364		option to the .sml file in question within its .cm file.
365		This is most useful for code that is being generated by tools such
366		as ml-nlffigen (because during development programmers tend to
367		erase the tool's entire output directory tree including CM's cached
368		GUIDs).  "noguid" is somewhat dangerous (since it can be used to locally
369		revert to the old, broken behavior of SML/NJ, but in specific cases
370		where there is no danger of interface confusion, its use is ok
371		(I think).
372
373		ml-nlffigen by default generates "noguid" annotations.  They can be
374		turned off by specifying -guid in its command line.
375
376		----------------------------------------------------------------------
377		Name: Lal George
378		Date: 2002/03/12 12 14:42:36 EST
379		Tag: george-20020312-frequency-computation
380		Description:
381
382		Integrated jump chaining and static block frequency into the
383		compiler. More details and numbers later.
384
385		----------------------------------------------------------------------
386		Name: Lal George
387		Date: 2002/03/11 11 22:38:53 EST
388		Tag: george-20020311-jump-chain-elim
389		Description:
390
391		Tested the jump chain elimination on all architectures (except the
392		hppa).  This is on by default right now and is profitable for the
393		alpha and x86, however, it may not be profitable for the sparc and ppc
394		when compiling the compiler.
395
396		The gc test will typically jump to a label at the end of the cluster,
397		where there is another jump to an external cluster containing the actual
398		code to invoke gc. This is to allow factoring of common gc invocation
399		sequences. That is to say, we generate:
400
401		f:
402		testgc
403		ja   L1      % jump if above to L1
404
405		L1:
406		jmp L2
407
408
409		After jump chain elimination the 'ja L1' instructions is converted to
410		'ja L2'. On the sparc and ppc, many of the 'ja L2' instructions may end
411		up being implemented in their long form (if L2 is far away) using:
412
413		jbe     L3      % jump if below or equal to L3
414		jmp     L2
415		L3:
416		...
417
418
419		For large compilation units L2  may be far away.
420
421
422		----------------------------------------------------------------------
423		Name: Matthias Blume
424		Date: 2002/03/11 13:30:00 EST
425		Tag: blume-20020311-mltreeeval
426		Description:
427
428		A functor parameter was missing.
429
430		----------------------------------------------------------------------
431		Name: Allen Leung
432		Date: 2002/03/11 10:30:00 EST
433		Tag: leunga-20020311-runtime-string0
434		Description:
435
436		The representation of the empty string now points to a
437		legal null terminated C string instead of unit.  It is now possible
438		to convert an ML string into C string with InlineT.CharVector.getData.
439		This compiles into one single machine instruction.
440
441		----------------------------------------------------------------------
442		Name: Allen Leung
443		Date: 2002/03/10 23:55:00 EST
444		Tag: leunga-20020310-x86-call
445		Description:
446
447		Added machine generation for CALL instruction (relative displacement mode)
448
449		----------------------------------------------------------------------
450		Name: Matthias Blume
451		Date: 2002/03/08 16:05:00
452		Tag: blume-20020308-entrypoints
453		Description:
454
455		Version number bumped to 110.39.1.  NEW BOOTFILES!
456
457		Entrypoints: non-zero offset into a code object where execution should begin.
458
459		- Added the notion of an entrypoint to CodeObj.
460		- Added reading/writing of entrypoint info to Binfile.
461		- Made runtime system bootloader aware of entrypoints.
462		- Use the address of the label of the first function given to mlriscGen
463		as the entrypoint.  This address is currently always 0, but it will
464		not be 0 once we turn on block placement.
465		- Removed the linkage cluster code (which was The Other Way(tm) of dealing
466		with entry points) from mlriscGen.
467
468		----------------------------------------------------------------------
469		Name: Allen Leung
470		Date: 2002/03/07 20:45:00 EST
471		Tag: leunga-20020307-x86-cmov
472		Description:
473
474		Bug fixes for CMOVcc on x86.
475
476		1. Added machine code generation for CMOVcc
477		2. CMOVcc is now generated in preference over SETcc on PentiumPro or above.
478		3. CMOVcc cannot have an immediate operand as argument.
479
480		----------------------------------------------------------------------
481		Name: Matthias Blume
482		Date: 2002/03/07 16:15:00 EST
483		Tag: blume-20020307-controls
484		Description:
485
486		This is a very large but mostly boring patch which makes (almost)
487		every tuneable compiler knob (i.e., pretty much everything under
488		Control.* plus a few other things) configurable via both the command
489		line and environment variables in the style CM did its configuration
490		until now.
491
492		Try starting sml with '-h' (or, if you are brave, '-H')
493
494		To this end, I added a structure Controls : CONTROLS to smlnj-lib.cm which
495		implements the underlying generic mechanism.
496
497		The interface to some of the existing such facilities has changed somewhat.
498		For example, the MLRiscControl module now provides mkFoo instead of getFoo.
499		(The getFoo interface is still there for backward-compatibility, but its
500		use is deprecated.)
501
502		The ml-build script passes -Cxxx=yyy command-line arguments through so
503		that one can now twiddle the compiler settings when using this "batch"
504		compiler.
505
506		TODO items:
507
508		We should go through and throw out all controls that are no longer
509		connected to anything.  Moreover, we should go through and provide
510		meaningful (and correct!) documentation strings for those controls
511		that still are connected.
512
513		Currently, multiple calls to Controls.new are accepted (only the first
514		has any effect).  Eventually we should make sure that every control
515		is being made (via Controls.new) exactly once.  Future access can then
516		be done using Controls.acc.
517
518		Finally, it would probably be a good idea to use the getter-setter
519		interface to controls rather than ref cells.  For the time being, both
520		styles are provided by the Controls module, but getter-setter pairs are
521		better if thread-safety is of any concern because they can be wrapped.
522
523		*****************************************
524
525		One bug fix: The function blockPlacement in three of the MLRISC
526		backpatch files used to be hard-wired to one of two possibilities at
527		link time (according to the value of the placementFlag).  But (I
528		think) it should rather sense the flag every time.
529
530		*****************************************
531
532		Other assorted changes (by other people who did not supply a HISTORY entry):
533
534		1. the cross-module inliner now works much better (Monnier)
535		2. representation of weights, frequencies, and probabilities in MLRISC
536		changed in preparation of using those for weighted block placement
537		(Reppy, George)
538
539		----------------------------------------------------------------------
540		Name: Lal George
541		Date: 2002/03/07 14:44:24 EST 2002
542		Tag: george-20020307-weighted-block-placement
543
544		Tested the weighted block placement optimization on all architectures
545		(except the hppa) using AMPL to generate the block and edge frequencies.
546		Changes were required in the machine properties to correctly
547		categorize trap instructions. There is an MLRISC flag
548		"weighted-block-placement" that can be used to enable weighted block
549		placement, but this will be ineffective without block/edge
550		frequencies (coming soon).
551
552
553		----------------------------------------------------------------------
554		Name: Lal George
555		Date: 2002/03/05 17:24:48 EST
556		Tag: george-20020305-linkage-cluster
557
558		In order to support the block placement optimization, a new cluster
559		is generated as the very first cluster (called the linkage cluster).
560		It contains a single jump to the 'real' entry point for the compilation
561		unit. Block placement has no effect on the linkage cluster itself, but
562		all the other clusters  have full freedom in the manner in which they
563		reorder blocks or functions.
564
565		On the x86 the typical linkage code that is generated is:
566		----------------------
567		.align 2
568		L0:
569		addl    $L1-L0, 72(%esp)
570		jmp     L1
571
572
573		.align  2
574		L1:
575		----------------------
576
577		72(%esp) is the memory location for the stdlink register. This
578		must contain the address of the CPS function being called. In the
579		above example, it contains the address of  L0; before
580		calling L1 (the real entry point for the compilation unit), it
581		must contain the address for L1, and hence
582
583		addl $L1-L0, 72(%esp)
584
585		I have tested this on all architectures except the hppa.The increase
586		in code size is of course negligible
587
588		----------------------------------------------------------------------
589		Name: Allen Leung
590		Date: 2002/03/03 13:20:00 EST
591		Tag: leunga-20020303-mlrisc-tools
592
593		Added #[ ... ] expressions to mlrisc tools
594
595		----------------------------------------------------------------------
596		Name: Matthias Blume
597		Date: 2002/02/27 12:29:00 EST
598		Tag: blume-20020227-cdebug
599		Description:
600
601		- made types in structure C and C_Debug to be equal
602		- got rid of code duplication (c-int.sml vs. c-int-debug.sml)
603		- there no longer is a C_Int_Debug (C_Debug is directly derived from C)
604
605		----------------------------------------------------------------------
606		Name: Matthias Blume
607		Date: 2002/02/26 12:00:00 EST
608		Tag: blume-20020226-ffi
609		Description:
610
611		1. Fixed a minor bug in CM's "noweb" tool:
612		If numbering is turned off, then truly don't number (i.e., do not
613		supply the -L option to noweb).  The previous behavior was to supply
614		-L'' -- which caused noweb to use the "default" line numbering scheme.
615		Thanks to Chris Richards for pointing this out (and supplying the fix).
616
617		2. Once again, I reworked some aspects of the FFI:
618
619		A. The incomplete/complete type business:
620
621		- Signatures POINTER_TO_INCOMPLETE_TYPE and accompanying functors are
622		gone!
623		- ML types representing an incomplete type are now *equal* to
624		ML types representing their corresponding complete types (just like
625		in C).  This is still safe because ml-nlffigen will not generate
626		RTTI for incomplete types, nor will it generate functions that
627		require access to such RTTI.   But when ML code generated from both
628		incomplete and complete versions of the C type meet, the ML types
629		are trivially interoperable.
630
631		NOTE:  These changes restore the full generality of the translation
632		(which was previously lost when I eliminated functorization)!
633
634		B. Enum types:
635
636		- Structure C now has a type constructor "enum" that is similar to
637		how the "su" constructor works.  However, "enum" is not a phantom
638		type because each "T enum" has values (and is isomorphic to
639		MLRep.Signed.int).
640		- There are generic access operations for enum objects (using
641		MLRep.Signed.int).
642		- ml-nlffigen will generate a structure E_foo for each "enum foo".
643		* The structure contains the definition of type "mlrep" (the ML-side
644		representation type of the enum).  Normally, mlrep is the same
645		as "MLRep.Signed.int", but if ml-nlffigen was invoked with "-ec",
646		then mlrep will be defined as a datatype -- thus facilitating
647		pattern matching on mlrep values.
648		("-ec" will be suppressed if there are duplicate values in an
649		enumeration.)
650		* Constructors ("-ec") or values (no "-ec") e_xxx of type mlrep
651		will be generated for each C enum constant xxx.
652		* Conversion functions m2i and i2m convert between mlrep and
653		MLRep.Signed.int.  (Without "-ec", these functions are identities.)
654		* Coversion functions c and ml convert between mlrep and "tag enum".
655		* Access functions (get/set) fetch and store mlrep values.
656		- By default (unless ml-nlffigen was invoked with "-nocollect"), unnamed
657		enumerations are merged into one single enumeration represented by
658		structure E_'.
659
660		----------------------------------------------------------------------
661		Name: Allen Leung
662		Date: 2002/02/25 04:45:00 EST
663		Tag: leunga-20020225-cps-spill
664
665		This is a new implementation of the CPS spill phase.
666		The new phase is in the new file compiler/CodeGen/cpscompile/spill-new.sml
667		In case of problems, replace it with the old file spill.sml
668
669		The current compiler runs into some serious performance problems when
670		constructing a large record.  This can happen when we try to compile a
671		structure with many items.  Even a very simple structure like the following
672		makes the compiler slow down.
673
674		structure Foo = struct
675		val x_1 = 0w1 : Word32.int
676		val x_2 = 0w2 : Word32.int
677		val x_3 = 0w3 : Word32.int
678		...
679		val x_N = 0wN : Word32.int
680		end
681
682		The following table shows the compile time, from N=1000 to N=4000,
683		with the old compiler:
684
685		N
686		1000   CPS 100 spill                           0.04u  0.00s  0.00g
687		MLRISC ra                               0.06u  0.00s  0.05g
688		(spills = 0 reloads = 0)
689		TOTAL                                   0.63u  0.07s  0.21g
690
691		1100   CPS 100 spill                           8.25u  0.32s  0.64g
692		MLRISC ra                               5.68u  0.59s  3.93g
693		(spills = 0 reloads = 0)
694		TOTAL                                   14.71u  0.99s  4.81g
695
696		1500   CPS 100 spill                           58.55u  2.34s  1.74g
697		MLRISC ra                               5.54u  0.65s  3.91g
698		(spills = 543 reloads = 1082)
699		TOTAL                                   65.40u  3.13s  6.00g
700
701		2000   CPS 100 spill                           126.69u  4.84s  3.08g
702		MLRISC ra                               0.80u  0.10s  0.55g
703		(spills = 42 reloads = 84)
704		TOTAL                                   129.42u  5.10s  4.13g
705
706		3000   CPS 100 spill                           675.59u  19.03s  11.64g
707		MLRISC ra                               2.69u  0.27s  1.38g
708		(spills = 62 reloads = 124)
709		TOTAL                                   682.48u  19.61s  13.99g
710
711		4000   CPS 100 spill                           2362.82u  56.28s  43.60g
712		MLRISC ra                               4.96u  0.27s  2.72g
713		(spills = 85 reloads = 170)
714		TOTAL                                   2375.26u  57.21s  48.00g
715
716		As you can see the old cps spill module suffers from some serious
717		performance problem.  But since I cannot decipher the old code fully,
718		instead of patching the problems up, I'm reimplementing it
719		with a different algorithm.  The new code is more modular,
720		smaller when compiled, and substantially faster
721		(O(n log n) time and O(n) space).  Timing of the new spill module:
722
723		4000  CPS 100 spill                           0.02u  0.00s  0.00g
724		MLRISC ra                               0.25u  0.02s  0.15g
725		(spills=1 reloads=3)
726		TOTAL                                   7.74u  0.34s  1.62g
727
728		Implementation details:
729
730		As far as I can tell, the purpose of the CPS spill module is to make sure the
731		number of live variables at any program point (the bandwidth)
732		does not exceed a certain limit, which is determined by the
733		size of the spill area.
734
735		When the bandwidth is too large, we decrease the register pressure by
736		packing live variables into spill records.  How we achieve this is
737		completely different than what we did in the old code.
738
739		First, there is something about the MLRiscGen code generator
740		that we should be aware of:
741
742		o MLRiscGen performs code motion!
743
744		In particular, it will move floating point computations and
745		address computations involving only the heap pointer to
746		their use sites (if there is only a single use).
747		What this means is that if we have a CPS record construction
748		statement
749
750		RECORD(k,vl,w,e)
751
752		we should never count the new record address w as live if w
753		has only one use (which is often the case).
754
755		We should do something similar to floating point, but the transformation
756		there is much more complex, so I won't deal with that.
757
758		Secondly, there are now two new cps primops at our disposal:
759
760		1. rawrecord of record_kind option
761		This pure operator allocates some uninitialized storage from the heap.
762		There are two forms:
763
764		rawrecord NONE [INT n]  allocates a tagless record of length n
765		rawrecord (SOME rk) [INT n] allocates a tagged record of length n
766		and initializes the tag.
767
768		2. rawupdate of cty
769		rawupdate cty (v,i,x)
770		Assigns to x to the ith component of record v.
771		The storelist is not updated.
772
773		We use these new primops for both spilling and increment record construction.
774
775		1. Spilling.
776
777		This is implemented with a linear scan algorithm (but generalized
778		to trees).  The algorithm will create a single spill record at the
779		beginning of the cps function and use rawupdate to spill to it,
780		and SELECT or SELp to reload from it.  So both spills and reloads
781		are fine-grain operations.  In contrast, in the old algorithm
782		"spills" have to be bundled together in records.
783
784		Ideally, we should sink the spill record construction to where
785		it is needed.  We can even split the spill record into multiple ones
786		at the places where they are needed.  But CPS is not a good
787		representation for global code motion, so I'll keep it simple and
788		am not attempting this.
789
790		2. Incremental record construction (aka record splitting).
791
792		Long records with many component values which are simulatenously live
793		(recall that single use record addresses are not considered to
794		be live) are constructed with rawrecord and rawupdate.
795		We allocate space on the heap with rawrecord first, then gradually
796		fill it in with rawupdate.  This is the technique suggested to me
797		by Matthias.
798
799		Some restrictions on when this is applicable:
800		1. It is not a VECTOR record.  The code generator currently does not handle
801		this case. VECTOR record uses double indirection like arrays.
802		2. All the record component values are defined in the same "basic block"
803		as the record constructor.  This is to prevent speculative
804		record construction.
805
806		----------------------------------------------------------------------
807		Name: Allen Leung
808		Date: 2002/02/22 01:02:00 EST
809		Tag: leunga-20020222-mlrisc-tools
810
811		Minor bug fixes in the parser and rewriter
812
813		----------------------------------------------------------------------
814		Name: Allen Leung
815		Date: 2002/02/21 20:20:00 EST
816		Tag: leunga-20020221-peephole
817
818		Regenerated the peephole files.  Some contained typos in the specification
819		and some didn't compile because of pretty printing bugs in the old version
820		of 'nowhere'.
821
822		----------------------------------------------------------------------
823		Name: Allen Leung
824		Date: 2002/02/19 20:20:00 EST
825		Tag: leunga-20020219-mlrisc-tools
826		Description:
827
828		Minor bug fixes to the mlrisc-tools library:
829
830		1.  Fixed up parsing colon suffixed keywords
831		2.  Added the ability to shut the error messages up
832		3.  Reimplemented the pretty printer and fixed up/improved
833		the pretty printing of handle and -> types.
834		4.  Fixed up generation of literal symbols in the nowhere tool.
835		5.  Added some SML keywords to to sml.sty
836
837		----------------------------------------------------------------------
838		Name: Matthias Blume
839		Date: 2002/02/19 16:20:00 EST
840		Tag: blume-20020219-cmffi
841		Description:
842
843		A wild mix of changes, some minor, some major:
844
845		* All C FFI-related libraries are now anchored under $c:
846		$/c.cm      --> $c/c.cm
847		$/c-int.cm  --> $c/internals/c-int.cm
848		$/memory.cm --> $c/memory/memory.cm
849
850		* "make" tool (in CM) now treats its argument pathname slightly
851		differently:
852		1. If the native expansion is an absolute name, then before invoking
853		the "make" command on it, CM will apply OS.Path.mkRelative
854		(with relativeTo = OS.FileSys.getDir()) to it.
855		2. The argument will be passed through to subsequent phases of CM
856		processing without "going native".  In particular, if the argument
857		was an anchored path, then "make" will not lose track of that anchor.
858
859		* Compiler backends now "know" their respective C calling conventions
860		instead of having to be told about it by ml-nlffigen.  This relieves
861		ml-nlffigen from one of its burdens.
862
863		* The X86Backend has been split into X86CCallBackend and X86StdCallBackend.
864
865		* Export C_DEBUG and C_Debug from $c/c.cm.
866
867		* C type encoding in ml-nlffi-lib has been improved to model the conceptual
868		subtyping relationship between incomplete pointers and their complete
869		counterparts.  For this, ('t, 'c) ptr has been changed to 'o ptr --
870		with the convention of instantiating 'o with ('t, 'c) obj whenever
871		the pointer target type is complete.  In the incomplete case, 'o
872		will be instantiated with some "'c iobj" -- a type obtained by
873		using one of the functors PointerToIncompleteType or PointerToCompleteType.
874
875		Operations that work on both incomplete and complete pointer types are
876		typed as taking an 'o ptr while operations that require the target to
877		be known are typed as taking some ('t, 'c) obj ptr.
878
879		voidptr is now a bit "more concrete", namely "type voidptr = void ptr'"
880		where void is an eqtype without any values.  This makes it possible
881		to work on voidptr values using functions meant to operate on light
882		incomplete pointers.
883
884		* As a result of the above, signature POINTER_TO_INCOMPLETE_TYPE has
885		been vastly simplified.
886
887		----------------------------------------------------------------------
888		Name: Matthias Blume
889		Date: 2002/02/19 10:48:00 EST
890		Tag: blume-20020219-pqfix
891		Description:
892
893		Applied Chris Okasaki's bug fix for priority queues.
894
895		----------------------------------------------------------------------
896		Name: Matthias Blume
897		Date: 2002/02/15 17:05:00
898		Tag: Release_110_39
899		Description:
900
901		Last-minute retagging is becoming a tradition... :-(
902
903		This is the working release 110.39.
904
905		----------------------------------------------------------------------
906		Name: Matthias Blume
907		Date: 2002/02/15 16:00:00 EST
908		Tag: Release_110_39-orig
909		Description:
910
911		Working release 110.39.  New bootfiles.
912
913		(Update: There was a small bug in the installer so it wouldn't work
914		with all shells.  So I retagged. -Matthias)
915
916		----------------------------------------------------------------------
917		Name: Matthias Blume
918		Date: 2002/02/15 14:17:00 EST
919		Tag: blume-20020215-showbindings
920		Description:
921
922		Added EnvRef.listBoundSymbols and CM.State.showBindings.  Especially
923		the latter can be useful for exploring what bindings are available at
924		the interactive prompt.  (The first function returns only the list
925		of symbols that are really bound, the second prints those but also the
926		ones that CM's autoloading mechanism knows about.)
927
928		----------------------------------------------------------------------
929		Name: Matthias Blume
930	Date: 2002/02/15 12:08:00 EST	Date: 2002/02/15 12:08:00 EST
931	Tag: blume-20020215-iptrs	Tag: blume-20020215-iptrs
932	Description:	Description:

---

Colored Diff Long Colored Diff Unidiff Context Diff Side by Side

Legend: Removed from v.1067   changed lines   Added in v.1175

---

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