SCM Repository

[smlnj] Diff of /sml/trunk/HISTORY

[smlnj] / sml / trunk / HISTORY

Diff of /sml/trunk/HISTORY

-revision 1049, Thu Jan 31 21:03:49 2002 UTC
+revision 1094, Mon Feb 25 09:58:56 2002 UTC
 Line 13
  Description:
  ----------------------------------------------------------------------
+ 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
+  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
+  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
+  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
+  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
+  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
+  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,
+ innstead 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:
+ 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:
+. 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.
+. 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.
+. 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.
+. 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:
+. It is not a VECTOR record.  The code generator currently does not handle
+        this case. VECTOR record uses double indirection like arrays.
+. 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
+ Minor bug fixes in the parser and rewriter
+ ----------------------------------------------------------------------
+ Name: Allen Leung
+ Date: 2002/02/21 20:20:00 EST
+ Tag: leunga-20020221-peephole
+ Regenerated the peephole files.  Some contained typos in the specification
+ and some didn't compile because of pretty printing bugs in the old version
+ of 'nowhere'.
+ ----------------------------------------------------------------------
+ Name: Allen Leung
+ Date: 2002/02/19 20:20:00 EST
+ Tag: leunga-20020219-mlrisc-tools
+ Description:
+    Minor bug fixes to the mlrisc-tools library:
+.  Fixed up parsing colon suffixed keywords
+.  Added the ability to shut the error messages up
+.  Reimplemented the pretty printer and fixed up/improved
+        the pretty printing of handle and -> types.
+.  Fixed up generation of literal symbols in the nowhere tool.
+.  Added some SML keywords to to sml.sty
+ ----------------------------------------------------------------------
+ Name: Matthias Blume
+ Date: 2002/02/19 16:20:00 EST
+ Tag: blume-20020219-cmffi
+ Description:
+ A wild mix of changes, some minor, some major:
+ * All C FFI-related libraries are now anchored under $c:
+     $/c.cm      --> $c/c.cm
+     $/c-int.cm  --> $c/internals/c-int.cm
+     $/memory.cm --> $c/memory/memory.cm
+ * "make" tool (in CM) now treats its argument pathname slightly
+   differently:
+. If the native expansion is an absolute name, then before invoking
+        the "make" command on it, CM will apply OS.Path.mkRelative
+        (with relativeTo = OS.FileSys.getDir()) to it.
+. The argument will be passed through to subsequent phases of CM
+        processing without "going native".  In particular, if the argument
+        was an anchored path, then "make" will not lose track of that anchor.
+ * Compiler backends now "know" their respective C calling conventions
+   instead of having to be told about it by ml-nlffigen.  This relieves
+   ml-nlffigen from one of its burdens.
+ * The X86Backend has been split into X86CCallBackend and X86StdCallBackend.
+ * Export C_DEBUG and C_Debug from $c/c.cm.
+ * C type encoding in ml-nlffi-lib has been improved to model the conceptual
+   subtyping relationship between incomplete pointers and their complete
+   counterparts.  For this, ('t, 'c) ptr has been changed to 'o ptr --
+   with the convention of instantiating 'o with ('t, 'c) obj whenever
+   the pointer target type is complete.  In the incomplete case, 'o
+   will be instantiated with some "'c iobj" -- a type obtained by
+   using one of the functors PointerToIncompleteType or PointerToCompleteType.
+   Operations that work on both incomplete and complete pointer types are
+   typed as taking an 'o ptr while operations that require the target to
+   be known are typed as taking some ('t, 'c) obj ptr.
+   voidptr is now a bit "more concrete", namely "type voidptr = void ptr'"
+   where void is an eqtype without any values.  This makes it possible
+   to work on voidptr values using functions meant to operate on light
+   incomplete pointers.
+ * As a result of the above, signature POINTER_TO_INCOMPLETE_TYPE has
+   been vastly simplified.
+ ----------------------------------------------------------------------
+ Name: Matthias Blume
+ Date: 2002/02/19 10:48:00 EST
+ Tag: blume-20020219-pqfix
+ Description:
+ Applied Chris Okasaki's bug fix for priority queues.
+ ----------------------------------------------------------------------
+ Name: Matthias Blume
+ Date: 2002/02/15 17:05:00
+ Tag: Release_110_39
+ Description:
+ Last-minute retagging is becoming a tradition... :-(
+ This is the working release 110.39.
+ ----------------------------------------------------------------------
+ Name: Matthias Blume
+ Date: 2002/02/15 16:00:00 EST
+ Tag: Release_110_39-orig
+ Description:
+ Working release 110.39.  New bootfiles.
+ (Update: There was a small bug in the installer so it wouldn't work
+ with all shells.  So I retagged. -Matthias)
+ ----------------------------------------------------------------------
+ Name: Matthias Blume
+ Date: 2002/02/15 14:17:00 EST
+ Tag: blume-20020215-showbindings
+ Description:
+ Added EnvRef.listBoundSymbols and CM.State.showBindings.  Especially
+ the latter can be useful for exploring what bindings are available at
+ the interactive prompt.  (The first function returns only the list
+ of symbols that are really bound, the second prints those but also the
+ ones that CM's autoloading mechanism knows about.)
+ ----------------------------------------------------------------------
+ Name: Matthias Blume
+ Date: 2002/02/15 12:08:00 EST
+ Tag: blume-20020215-iptrs
+ Description:
+ Two improvements to ml-nlffigen:
+. Write files only if they do not exist or if their current contents
+      do not coincide with what's being written.  (That is, avoid messing
+      with the time stamps unless absolutely necessary.)
+. Implement a "repository" mechanism for generated files related
+      to "incomplete pointer types".   See the README file for details.
+ ----------------------------------------------------------------------
+ Name: Matthias Blume
+ Date: 2002/02/14 11:50:00 EST
+ Tag: blume-20020214-quote
+ Description:
+ Added a type 't t_' to tag.sml (in ml-nlffi-lib.cm).  This is required
+ because of the new and improved tag generation scheme.  (Thanks to Allen
+ Leung for pointing it out.)
+ ----------------------------------------------------------------------
+ Name: Lal George
+ Date: 2002/02/14 09:55:27 EST 2002
+ Tag: george-20020214-isabelle-bug
+ Description:
+ Fixed the MLRISC bug sent by Markus Wenzel regarding the compilation
+ of Isabelle on the x86.
+ From Allen:
+ -----------
+  I've found the problem:
+      in ra-core.sml, I use the counter "blocked" to keep track of the
+      true number of elements in the freeze queue.  When the counter goes
+      to zero, I skip examining the queue.  But I've messed up the
+      bookkeeping in combine():
+          else ();
+          case !ucol of
+            PSEUDO => (if !cntv > 0 then
+                  (if !cntu > 0 then blocked := !blocked - 1 else ();
+                                     ^^^^^^^^^^^^^^^^^^^^^^^
+                   moveu := mergeMoveList(!movev, !moveu)
+                  )
+               else ();
+      combine() is called to coalesce two nodes u and v.
+      I think I was thinking that if the move counts of u and v are both
+      greater than zero then after they are coalesced then one node is
+      removed from the freeze queue.  Apparently I was thinking that
+      both u and v are of low degree, but that's clearly not necessarily true.
+/12/2002:
+     Here's the patch.  HOL now compiles.
+     I don't know how this impact on performance (compile
+     time or runtime).  This bug caused the RA (especially on the x86)
+     to go thru the potential spill phase when there are still nodes on the
+     freeze queue.
+ ----------------------------------------------------------------------
+ Name: Matthias Blume
+ Date: 2002/02/13 22:40:00 EST
+ Tag: blume-20020213-fptr-rtti
+ Description:
+ Fixed a bug in ml-nlffigen that was introduced with one of the previous
+ updates.
+ ----------------------------------------------------------------------
+ Name: Matthias Blume
+ Date: 2002/02/13 16:41:00 EST
+ Tag: blume-20020213-cmlpq
+ Description:
+ Added new priority queue export symbols (which have just been added to
+ smlnj-lib.cm) to CML's version of smlnj-lib.cm.  (Otherwise CML would
+ not compile and the installer would choke.)
+ ----------------------------------------------------------------------
+ Name: Matthias Blume
+ Date: 2002/02/13 16:15:00 EST
+ Tag: blume-20020213-various
+ Description:
+. More tweaks to ml-nlffigen:
+    - better internal datastructures (resulting in slight speedup)
+    - "-match" option requires exact match
+    - "localized" gensym counters (untagged structs/unions nested within
+      other structs/unions or within typedefs get a fresh counter; their
+      tag will be prefixed by a concatenation of their parents' tags)
+    - bug fixes (related to calculation of transitive closure of types
+      to be included in the output)
+. Minor Basis updates:
+    - added implementations for List.collate and Option.app
+ ----------------------------------------------------------------------
+ Name: Matthias Blume
+ Date: 2002/02/11 15:55:00 EST
+ Tag: blume-20020211-gensym
+ Description:
+ Added a "-gensym" option to command line of ml-nlffigen.  This can be
+ used to specify a "stem" -- a string that is inserted in all "gensym'd"
+ names (ML structure names that correspond to unnamed C structs, unions,
+ and enums), so that separate runs of ml-nlffigen do not clash.
+ ----------------------------------------------------------------------
+ Name: Matthias Blume
+ Date: 2002/02/11 12:05:00 EST
+ Tag: blume-20020211-gensml
+ Description:
+ A quick fix for a problem with GenSML (in the pgraph-util library):
+ Make generation of toplevel "local" optional.  (Strictly speaking,
+ signature definitions within "local" are not legal SML.)
+ Other than that: updates to INSTALL and cm/TODO.
+ ----------------------------------------------------------------------
+ Name: Matthias Blume
+ Date: 2002/02/08 15:00:00 EST
+ Tag: blume-20020208-uniquepid
+ Description:
+. Version number has been bumped to 110.38.1.  NEW BOOTFILES!!!
+. The installer (config/install.sh) has gotten smarter:
+      - Configuration options are a bit easier to specify now
+        (in config/targets).
+      - Bug in recognizing .tar.bz2 files fixed.
+      - Installer automatically resolves dependencies between
+        configuration options (e.g., if you ask for eXene, you will
+        also get cml -- regardless whether you asked for it or not).
+      - Installer can run in "quieter mode" by setting the environment
+        variable INSTALL_QUIETLY to "true".  "Quieter" does not mean
+        "completely silent", though.
+      - Build HashCons library as part of smlnj-lib.
+. A new scheme for assigning persistent identifiers to compilation
+    units (and, by extension, to types etc.) has been put into place.
+    This fixes a long-standing bug where types and even dynamic values
+    can get internally confused, thereby compromising type safety
+    (abstraction) and dynamic correctness.  See
+      http://cm.bell-labs.com/cm/cs/who/blume/pid-confusion.tgz
+    for an example of how things could go wrong until now.
+    The downside of the new scheme is that pids are not quite as
+    persistent as they used to be: CM will generate a fresh pid
+    for every compilation unit that it thinks it sees for the first
+    time.  That means that if you compile starting from a clean, fresh
+    source tree at two different times, you end up with different
+    binaries.
+    Cutoff recompilation, however, has not been compromised because
+    CM keeps pid information in special caches between runs.
+ ----------------------------------------------------------------------
+ Name: Lal George
+ Date: 2002/02/07 15:34:13 EST 2002
+ Tag: <none>
+ Description:
+ Compilers that generate assembly code may produce  global labels
+ whose value is resolved at link time. The various peephole optimization
+ modules did not take this in account.
+ TODO. The Labels.addrOf function should really return an option
+ type so that clients are forced to deal with this issue, rather
+ than an exception being raised.
+ ----------------------------------------------------------------------
+ Name: Lal George
+ Date: 2002/02/06 13:55:02 EST
+ Tag: george-20020206-ra-breakup
+ Description:
+. A bug fix from Allen.
+     A typo causes extra fstp %st(0)'s to be generated at compensation
+     edges, which might cause stack underflow traps at runtime.  This
+     occurs in fft where there are extraneous fstps right before the 'into'
+     trap instruction (in this case they are harmless since none of the
+     integers overflow.)
+. Pulled out various utility modules that were embedded in the modules
+    of the register allocator. I need these modules for other purposes, but
+    they are not complete enough to put into a library (just yet).
+ ----------------------------------------------------------------------
  Name: Matthias Blume
  Date: 2002/01/31 16:05:00 EST
  Tag: blume-20020131-sparc-ccalls
-Line 633
+Line 1105
  ----------------------------------------------------------------------
  Name: Matthias Blume
- >>>>>>> 1.169
  Date: 2001/09/18 15:35:00 EDT
  Tag: blume-20010918-readme11036
  Description:

 Legend:



Removed from v.1049
 


changed lines


 
Added in v.1094
 Legend:



Removed from v.1049
 


changed lines


 
Added in v.1094
-Removed from v.1049
+Added in v.1094

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