--- sml/trunk/HISTORY 2002/02/22 05:56:29 1086
+++ sml/trunk/HISTORY 2002/03/20 20:52:51 1155
@@ -13,6 +13,602 @@
Description:
----------------------------------------------------------------------
+Name: Matthias Blume
+Date: 2002/03/20 15:55:00 EST
+Tag: blume-20020320-kmp
+Description:
+
+Implemented Knuth-Morris-Pratt string matching in PreString and used
+it for String.isSubstring, Substring.isSubstring, and
+Substring.position.
+
+(Might need some stress-testing. Simple examples worked fine.)
+
+----------------------------------------------------------------------
+Name: Matthias Blume
+Date: 2002/03/19 16:37:00 EST
+Tag: blume-20020319-witnesses
+Description:
+
+Added a structure C.W and functions convert/Ptr.convert to ml-nlffi-lib.
+
+This implements a generic mechanism for changing constness qualifiers
+anywhere within big C types without resorting to outright "casts".
+(So far, functions such as C.rw/C.ro or C.Ptr.rw/C.Ptr.ro only let you
+modify the constness at the outermost level.)
+The implementation of "convert" is based on the idea of "witness"
+values -- values that are not used by the operation but whose types
+"testify" to their applicability. On the implementation side, "convert"
+is simply a projection (returning its second curried argument). With
+cross-module inlining, it should not result in any machine code being
+generated.
+
+----------------------------------------------------------------------
+Name: Matthias Blume
+Date: 2002/03/15 16:40:00 EST
+Tag: blume-20020315-basis
+Description:
+
+Provided (preliminary?) implementations for
+
+ {String,Substring}.{concatWith,isSuffix,isSubstring}
+
+and
+
+ Substring.full
+
+Those are in the Basis spec but they were missing in SML/NJ.
+
+----------------------------------------------------------------------
+Name: Matthias Blume
+Date: 2002/03/14 21:30:00 EST
+Tag: blume-20020314-controls
+Description:
+
+Controls:
+---------
+
+1. Factored out the recently-added Controls : CONTROLS stuff and put
+ it into its own library $/controls-lib.cm. The source tree for
+ this is under src/smlnj-lib/Controls.
+
+2. Changed the names of types and functions in this interface, so they
+ make a bit more "sense":
+
+ module -> registry
+ 'a registry -> 'a group
+
+3. The interface now deals in ref cells only. The getter/setter interface
+ is (mostly) gone.
+
+4. Added a function that lets one register an already-existing ref cell.
+
+5. Made the corresponding modifications to the rest of the code so that
+ everything compiles again.
+
+6. Changed the implementation of Controls.MLRISC back to something closer
+ to the original. In particular, this module (and therefore MLRISC)
+ does not depend on Controls. There now is some link-time code in
+ int-sys.sml that registers the MLRISC controls with the Controls
+ module.
+
+CM:
+---
+
+ * One can now specify the lambda-split aggressiveness in init.cmi.
+
+----------------------------------------------------------------------
+Name: Allen Leung
+Date: 2002/03/13 17:30:00 EST
+Tag: leunga-20020313-x86-fp-unary
+Description:
+
+Bug fix for:
+
+> leunga@weaselbane:~/Yale/tmp/sml-dist{21} bin/sml
+> Standard ML of New Jersey v110.39.1 [FLINT v1.5], March 08, 2002
+> - fun f(x,(y,z)) = Real.~ y;
+> [autoloading]
+> [autoloading done]
+> fchsl (%eax), 184(%esp)
+> Error: MLRisc bug: X86MCEmitter.emitInstr
+>
+> uncaught exception Error
+> raised at: ../MLRISC/control/mlriscErrormsg.sml:16.14-16.19
+
+The problem was that the code generator did not generate any fp registers
+in this case, and the ra didn't know that it needed to run the X86FP phase to
+translate the pseudo fp instruction. This only happened with unary fp
+operators in certain situations.
+
+----------------------------------------------------------------------
+Name: Matthias Blume
+Date: 2002/03/13 14:00:00 EST
+Tag: blume-20020313-overload-etc
+Description:
+
+1. Added _overload as a synonym for overload for backward compatibility.
+ (Control.overloadKW must be true for either version to be accepted.)
+
+2. Fixed bug in install script that caused more things to be installed
+ than what was requested in config/targets.
+
+3. Made CM aware of the (_)overload construct so that autoloading
+ works.
+
+----------------------------------------------------------------------
+Name: Matthias Blume
+Date: 2002/03/12 22:03:00 EST
+Tag: blume-20020312-url
+Description:
+
+Forgot to update BOOT and srcarchiveurl.
+
+----------------------------------------------------------------------
+Name: Matthias Blume
+Date: 2002/03/12 17:30:00 EST
+Tag: blume-20020312-version110392
+Description:
+
+Yet another version number bump (because of small changes to the
+binfile format). Version number is now 110.39.2. NEW BOOTFILES!
+
+Changes:
+
+ The new pid generation scheme described a few weeks ago was overly
+ complicated. I implemented a new mechanism that is simpler and
+ provides a bit more "stability": Once CM has seen a compilation
+ unit, it keeps its identity constant (as long as you do not delete
+ those crucial CM/GUID/* files). This means that when you change
+ an interface, compile, then go back to the old interface, and
+ compile again, you arrive at the original pid.
+
+ There now also is a mechanism that instructs CM to use the plain
+ environment hash as a module's pid (effectively making its GUID
+ the empty string). For this, "noguid" must be specified as an
+ option to the .sml file in question within its .cm file.
+ This is most useful for code that is being generated by tools such
+ as ml-nlffigen (because during development programmers tend to
+ erase the tool's entire output directory tree including CM's cached
+ GUIDs). "noguid" is somewhat dangerous (since it can be used to locally
+ revert to the old, broken behavior of SML/NJ, but in specific cases
+ where there is no danger of interface confusion, its use is ok
+ (I think).
+
+ ml-nlffigen by default generates "noguid" annotations. They can be
+ turned off by specifying -guid in its command line.
+
+----------------------------------------------------------------------
+Name: Lal George
+Date: 2002/03/12 12 14:42:36 EST
+Tag: george-20020312-frequency-computation
+Description:
+
+Integrated jump chaining and static block frequency into the
+compiler. More details and numbers later.
+
+----------------------------------------------------------------------
+Name: Lal George
+Date: 2002/03/11 11 22:38:53 EST
+Tag: george-20020311-jump-chain-elim
+Description:
+
+Tested the jump chain elimination on all architectures (except the
+hppa). This is on by default right now and is profitable for the
+alpha and x86, however, it may not be profitable for the sparc and ppc
+when compiling the compiler.
+
+The gc test will typically jump to a label at the end of the cluster,
+where there is another jump to an external cluster containing the actual
+code to invoke gc. This is to allow factoring of common gc invocation
+sequences. That is to say, we generate:
+
+ f:
+ testgc
+ ja L1 % jump if above to L1
+
+ L1:
+ jmp L2
+
+
+After jump chain elimination the 'ja L1' instructions is converted to
+'ja L2'. On the sparc and ppc, many of the 'ja L2' instructions may end
+up being implemented in their long form (if L2 is far away) using:
+
+ jbe L3 % jump if below or equal to L3
+ jmp L2
+ L3:
+ ...
+
+
+For large compilation units L2 may be far away.
+
+
+----------------------------------------------------------------------
+Name: Matthias Blume
+Date: 2002/03/11 13:30:00 EST
+Tag: blume-20020311-mltreeeval
+Description:
+
+A functor parameter was missing.
+
+----------------------------------------------------------------------
+Name: Allen Leung
+Date: 2002/03/11 10:30:00 EST
+Tag: leunga-20020311-runtime-string0
+Description:
+
+ The representation of the empty string now points to a
+legal null terminated C string instead of unit. It is now possible
+to convert an ML string into C string with InlineT.CharVector.getData.
+This compiles into one single machine instruction.
+
+----------------------------------------------------------------------
+Name: Allen Leung
+Date: 2002/03/10 23:55:00 EST
+Tag: leunga-20020310-x86-call
+Description:
+
+ Added machine generation for CALL instruction (relative displacement mode)
+
+----------------------------------------------------------------------
+Name: Matthias Blume
+Date: 2002/03/08 16:05:00
+Tag: blume-20020308-entrypoints
+Description:
+
+Version number bumped to 110.39.1. NEW BOOTFILES!
+
+Entrypoints: non-zero offset into a code object where execution should begin.
+
+- Added the notion of an entrypoint to CodeObj.
+- Added reading/writing of entrypoint info to Binfile.
+- Made runtime system bootloader aware of entrypoints.
+- Use the address of the label of the first function given to mlriscGen
+ as the entrypoint. This address is currently always 0, but it will
+ not be 0 once we turn on block placement.
+- Removed the linkage cluster code (which was The Other Way(tm) of dealing
+ with entry points) from mlriscGen.
+
+----------------------------------------------------------------------
+Name: Allen Leung
+Date: 2002/03/07 20:45:00 EST
+Tag: leunga-20020307-x86-cmov
+Description:
+
+ Bug fixes for CMOVcc on x86.
+
+ 1. Added machine code generation for CMOVcc
+ 2. CMOVcc is now generated in preference over SETcc on PentiumPro or above.
+ 3. CMOVcc cannot have an immediate operand as argument.
+
+----------------------------------------------------------------------
+Name: Matthias Blume
+Date: 2002/03/07 16:15:00 EST
+Tag: blume-20020307-controls
+Description:
+
+This is a very large but mostly boring patch which makes (almost)
+every tuneable compiler knob (i.e., pretty much everything under
+Control.* plus a few other things) configurable via both the command
+line and environment variables in the style CM did its configuration
+until now.
+
+Try starting sml with '-h' (or, if you are brave, '-H')
+
+To this end, I added a structure Controls : CONTROLS to smlnj-lib.cm which
+implements the underlying generic mechanism.
+
+The interface to some of the existing such facilities has changed somewhat.
+For example, the MLRiscControl module now provides mkFoo instead of getFoo.
+(The getFoo interface is still there for backward-compatibility, but its
+use is deprecated.)
+
+The ml-build script passes -Cxxx=yyy command-line arguments through so
+that one can now twiddle the compiler settings when using this "batch"
+compiler.
+
+TODO items:
+
+We should go through and throw out all controls that are no longer
+connected to anything. Moreover, we should go through and provide
+meaningful (and correct!) documentation strings for those controls
+that still are connected.
+
+Currently, multiple calls to Controls.new are accepted (only the first
+has any effect). Eventually we should make sure that every control
+is being made (via Controls.new) exactly once. Future access can then
+be done using Controls.acc.
+
+Finally, it would probably be a good idea to use the getter-setter
+interface to controls rather than ref cells. For the time being, both
+styles are provided by the Controls module, but getter-setter pairs are
+better if thread-safety is of any concern because they can be wrapped.
+
+*****************************************
+
+One bug fix: The function blockPlacement in three of the MLRISC
+backpatch files used to be hard-wired to one of two possibilities at
+link time (according to the value of the placementFlag). But (I
+think) it should rather sense the flag every time.
+
+*****************************************
+
+Other assorted changes (by other people who did not supply a HISTORY entry):
+
+1. the cross-module inliner now works much better (Monnier)
+2. representation of weights, frequencies, and probabilities in MLRISC
+ changed in preparation of using those for weighted block placement
+ (Reppy, George)
+
+----------------------------------------------------------------------
+Name: Lal George
+Date: 2002/03/07 14:44:24 EST 2002
+Tag: george-20020307-weighted-block-placement
+
+Tested the weighted block placement optimization on all architectures
+(except the hppa) using AMPL to generate the block and edge frequencies.
+Changes were required in the machine properties to correctly
+categorize trap instructions. There is an MLRISC flag
+"weighted-block-placement" that can be used to enable weighted block
+placement, but this will be ineffective without block/edge
+frequencies (coming soon).
+
+
+----------------------------------------------------------------------
+Name: Lal George
+Date: 2002/03/05 17:24:48 EST
+Tag: george-20020305-linkage-cluster
+
+In order to support the block placement optimization, a new cluster
+is generated as the very first cluster (called the linkage cluster).
+It contains a single jump to the 'real' entry point for the compilation
+unit. Block placement has no effect on the linkage cluster itself, but
+all the other clusters have full freedom in the manner in which they
+reorder blocks or functions.
+
+On the x86 the typical linkage code that is generated is:
+ ----------------------
+ .align 2
+ L0:
+ addl $L1-L0, 72(%esp)
+ jmp L1
+
+
+ .align 2
+ L1:
+ ----------------------
+
+72(%esp) is the memory location for the stdlink register. This
+must contain the address of the CPS function being called. In the
+above example, it contains the address of L0; before
+calling L1 (the real entry point for the compilation unit), it
+must contain the address for L1, and hence
+
+ addl $L1-L0, 72(%esp)
+
+I have tested this on all architectures except the hppa.The increase
+in code size is of course negligible
+
+----------------------------------------------------------------------
+Name: Allen Leung
+Date: 2002/03/03 13:20:00 EST
+Tag: leunga-20020303-mlrisc-tools
+
+ Added #[ ... ] expressions to mlrisc tools
+
+----------------------------------------------------------------------
+Name: Matthias Blume
+Date: 2002/02/27 12:29:00 EST
+Tag: blume-20020227-cdebug
+Description:
+
+- made types in structure C and C_Debug to be equal
+- got rid of code duplication (c-int.sml vs. c-int-debug.sml)
+- there no longer is a C_Int_Debug (C_Debug is directly derived from C)
+
+----------------------------------------------------------------------
+Name: Matthias Blume
+Date: 2002/02/26 12:00:00 EST
+Tag: blume-20020226-ffi
+Description:
+
+1. Fixed a minor bug in CM's "noweb" tool:
+ If numbering is turned off, then truly don't number (i.e., do not
+ supply the -L option to noweb). The previous behavior was to supply
+ -L'' -- which caused noweb to use the "default" line numbering scheme.
+ Thanks to Chris Richards for pointing this out (and supplying the fix).
+
+2. Once again, I reworked some aspects of the FFI:
+
+ A. The incomplete/complete type business:
+
+ - Signatures POINTER_TO_INCOMPLETE_TYPE and accompanying functors are
+ gone!
+ - ML types representing an incomplete type are now *equal* to
+ ML types representing their corresponding complete types (just like
+ in C). This is still safe because ml-nlffigen will not generate
+ RTTI for incomplete types, nor will it generate functions that
+ require access to such RTTI. But when ML code generated from both
+ incomplete and complete versions of the C type meet, the ML types
+ are trivially interoperable.
+
+ NOTE: These changes restore the full generality of the translation
+ (which was previously lost when I eliminated functorization)!
+
+ B. Enum types:
+
+ - Structure C now has a type constructor "enum" that is similar to
+ how the "su" constructor works. However, "enum" is not a phantom
+ type because each "T enum" has values (and is isomorphic to
+ MLRep.Signed.int).
+ - There are generic access operations for enum objects (using
+ MLRep.Signed.int).
+ - ml-nlffigen will generate a structure E_foo for each "enum foo".
+ * The structure contains the definition of type "mlrep" (the ML-side
+ representation type of the enum). Normally, mlrep is the same
+ as "MLRep.Signed.int", but if ml-nlffigen was invoked with "-ec",
+ then mlrep will be defined as a datatype -- thus facilitating
+ pattern matching on mlrep values.
+ ("-ec" will be suppressed if there are duplicate values in an
+ enumeration.)
+ * Constructors ("-ec") or values (no "-ec") e_xxx of type mlrep
+ will be generated for each C enum constant xxx.
+ * Conversion functions m2i and i2m convert between mlrep and
+ MLRep.Signed.int. (Without "-ec", these functions are identities.)
+ * Coversion functions c and ml convert between mlrep and "tag enum".
+ * Access functions (get/set) fetch and store mlrep values.
+ - By default (unless ml-nlffigen was invoked with "-nocollect"), unnamed
+ enumerations are merged into one single enumeration represented by
+ structure E_'.
+
+----------------------------------------------------------------------
+Name: Allen Leung
+Date: 2002/02/25 04:45:00 EST
+Tag: leunga-20020225-cps-spill
+
+This is a new implementation of the CPS spill phase.
+The new phase is in the new file compiler/CodeGen/cpscompile/spill-new.sml
+In case of problems, replace it with the old file spill.sml
+
+The current compiler runs into some serious performance problems when
+constructing a large record. This can happen when we try to compile a
+structure with many items. Even a very simple structure like the following
+makes the compiler slow down.
+
+ structure Foo = struct
+ val x_1 = 0w1 : Word32.int
+ val x_2 = 0w2 : Word32.int
+ val x_3 = 0w3 : Word32.int
+ ...
+ val x_N = 0wN : Word32.int
+ end
+
+The following table shows the compile time, from N=1000 to N=4000,
+with the old compiler:
+
+N
+1000 CPS 100 spill 0.04u 0.00s 0.00g
+ MLRISC ra 0.06u 0.00s 0.05g
+ (spills = 0 reloads = 0)
+ TOTAL 0.63u 0.07s 0.21g
+
+1100 CPS 100 spill 8.25u 0.32s 0.64g
+ MLRISC ra 5.68u 0.59s 3.93g
+ (spills = 0 reloads = 0)
+ TOTAL 14.71u 0.99s 4.81g
+
+1500 CPS 100 spill 58.55u 2.34s 1.74g
+ MLRISC ra 5.54u 0.65s 3.91g
+ (spills = 543 reloads = 1082)
+ TOTAL 65.40u 3.13s 6.00g
+
+2000 CPS 100 spill 126.69u 4.84s 3.08g
+ MLRISC ra 0.80u 0.10s 0.55g
+ (spills = 42 reloads = 84)
+ TOTAL 129.42u 5.10s 4.13g
+
+3000 CPS 100 spill 675.59u 19.03s 11.64g
+ MLRISC ra 2.69u 0.27s 1.38g
+ (spills = 62 reloads = 124)
+ TOTAL 682.48u 19.61s 13.99g
+
+4000 CPS 100 spill 2362.82u 56.28s 43.60g
+ MLRISC ra 4.96u 0.27s 2.72g
+ (spills = 85 reloads = 170)
+ TOTAL 2375.26u 57.21s 48.00g
+
+As you can see the old cps spill module suffers from some serious
+performance problem. But since I cannot decipher the old code fully,
+instead of patching the problems up, I'm reimplementing it
+with a different algorithm. The new code is more modular,
+smaller when compiled, and substantially faster
+(O(n log n) time and O(n) space). Timing of the new spill module:
+
+4000 CPS 100 spill 0.02u 0.00s 0.00g
+ MLRISC ra 0.25u 0.02s 0.15g
+ (spills=1 reloads=3)
+ TOTAL 7.74u 0.34s 1.62g
+
+Implementation details:
+
+As far as I can tell, the purpose of the CPS spill module is to make sure the
+number of live variables at any program point (the bandwidth)
+does not exceed a certain limit, which is determined by the
+size of the spill area.
+
+When the bandwidth is too large, we decrease the register pressure by
+packing live variables into spill records. How we achieve this is
+completely different than what we did in the old code.
+
+First, there is something about the MLRiscGen code generator
+that we should be aware of:
+
+o MLRiscGen performs code motion!
+
+ In particular, it will move floating point computations and
+ address computations involving only the heap pointer to
+ their use sites (if there is only a single use).
+ What this means is that if we have a CPS record construction
+ statement
+
+ RECORD(k,vl,w,e)
+
+ we should never count the new record address w as live if w
+ has only one use (which is often the case).
+
+ We should do something similar to floating point, but the transformation
+ there is much more complex, so I won't deal with that.
+
+Secondly, there are now two new cps primops at our disposal:
+
+ 1. rawrecord of record_kind option
+ This pure operator allocates some uninitialized storage from the heap.
+ There are two forms:
+
+ rawrecord NONE [INT n] allocates a tagless record of length n
+ rawrecord (SOME rk) [INT n] allocates a tagged record of length n
+ and initializes the tag.
+
+ 2. rawupdate of cty
+ rawupdate cty (v,i,x)
+ Assigns to x to the ith component of record v.
+ The storelist is not updated.
+
+We use these new primops for both spilling and increment record construction.
+
+ 1. Spilling.
+
+ This is implemented with a linear scan algorithm (but generalized
+ to trees). The algorithm will create a single spill record at the
+ beginning of the cps function and use rawupdate to spill to it,
+ and SELECT or SELp to reload from it. So both spills and reloads
+ are fine-grain operations. In contrast, in the old algorithm
+ "spills" have to be bundled together in records.
+
+ Ideally, we should sink the spill record construction to where
+ it is needed. We can even split the spill record into multiple ones
+ at the places where they are needed. But CPS is not a good
+ representation for global code motion, so I'll keep it simple and
+ am not attempting this.
+
+ 2. Incremental record construction (aka record splitting).
+
+ Long records with many component values which are simulatenously live
+ (recall that single use record addresses are not considered to
+ be live) are constructed with rawrecord and rawupdate.
+ We allocate space on the heap with rawrecord first, then gradually
+ fill it in with rawupdate. This is the technique suggested to me
+ by Matthias.
+
+ Some restrictions on when this is applicable:
+ 1. It is not a VECTOR record. The code generator currently does not handle
+ this case. VECTOR record uses double indirection like arrays.
+ 2. All the record component values are defined in the same "basic block"
+ as the record constructor. This is to prevent speculative
+ record construction.
+
+----------------------------------------------------------------------
Name: Allen Leung
Date: 2002/02/22 01:02:00 EST
Tag: leunga-20020222-mlrisc-tools