Changes by: Nathaniel Gray (n8gray at caltech.edu)
Date: 2004-04-01 08:28:01 -0800 (Thu, 01 Apr 2004)
Revision: 5583
Log message:

      Added processing of || and &&.  The computer lab is closing so I guess I won't
      be able to do anything about the paper unless I can find a 24hr internet access
      site.  I don't really feel like I understand what's going on at your end anyhow,
      so it's probably best that I just leave it to you.
      

Changes by: Nathaniel Gray (n8gray at caltech.edu)
Date: 2004-04-02 00:23:46 -0800 (Fri, 02 Apr 2004)
Revision: 5589
Log message:

      Changed the mandel case to use the parser.  It doesn't compile yet because the
      backend doesn't know about shift operators.  It also takes a *long* time.
      Something's going super-linear in a bad way.
      

Changes by: Nathaniel Gray (n8gray at caltech.edu)
Date: 2004-04-02 00:25:25 -0800 (Fri, 02 Apr 2004)
Revision: 5590
Log message:

      No need for this anymore.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-04 11:38:44 -0700 (Sun, 04 Apr 2004)
Revision: 5592
Log message:

      Added a TODO list.  This will probably migrate to bugzilla.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-04 17:46:36 -0700 (Sun, 04 Apr 2004)
Revision: 5593
Log message:

      . Changed the way Reserve is handled to make it more general in
      . anticipation of other kinds of special operations.
      .
      .    1. The Core_special module defines special transformations
      .       that need to be performed before closure conversion.
      .    2. The Mcc_x86_prologue module defines a function prologue,
      .       where code for these operations is expanded.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-04 19:15:24 -0700 (Sun, 04 Apr 2004)
Revision: 5595
Log message:

      . Adding memory reservations for arrays, but there are two issues:
      .
      .    1. Somehow, the middle end does not work without naming.
      .       Filed as bug #179.
      .    2. The extra functions are annoying and inefficient.
      .       Filed as bug #180.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-04 20:40:13 -0700 (Sun, 04 Apr 2004)
Revision: 5596
Log message:

      Add a core optimization phase Core_opt1.
      
      Probably we need to reconsider the directory structure, because we shouldn't just
      drop optimizations into the core directory.
      
      However, core_opt1 is a special phase that undoes some of the core
      transformations when they are mistakes.  It probably belongs in the core.
      
      The only optimization currently is to eliminate spurious closure conversions:
         (lambda_c (params1). lambda_s (params2). e)(args1)(args2)
         <-->
         (lambda_d (params1 @ params2). e)(args1 @ args2)
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-04 20:43:05 -0700 (Sun, 04 Apr 2004)
Revision: 5597
Log message:

      Optimization should happen *before* memory reservation.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-05 10:39:27 -0700 (Mon, 05 Apr 2004)
Revision: 5598
Log message:

      Added "special" extension for special calls.  It is likely that we
      want to use special for extenal calls too.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-05 11:13:01 -0700 (Mon, 05 Apr 2004)
Revision: 5599
Log message:

      Added reserve as a special stage.  The old-style reserve is still
      around for constant-sized reserves.  Have to figure out whether to
      fold this in.
      
      Also, added Core_def, so we can use definitions in our code.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-05 11:21:08 -0700 (Mon, 05 Apr 2004)
Revision: 5600
Log message:

      Folded Core_opt1 into Core_optimize.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-05 11:45:13 -0700 (Mon, 05 Apr 2004)
Revision: 5601
Log message:

      Added reservations for arrays.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-05 12:16:02 -0700 (Mon, 05 Apr 2004)
Revision: 5602
Log message:

      Minor changes to on array reservations.
      Next: fix up the array initialization code.
      The assembly needs a loop for initialization,
      which is a hassle.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-05 12:33:33 -0700 (Mon, 05 Apr 2004)
Revision: 5603
Log message:

      More fixes to array initialization code.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-05 16:02:33 -0700 (Mon, 05 Apr 2004)
Revision: 5604
Log message:

      Adding closure conversion to the assembly.  Not finished yet.
      

Changes by: Aleksey Nogin (nogin at cs.caltech.edu)
Date: 2004-04-05 17:42:43 -0700 (Mon, 05 Apr 2004)
Revision: 5606
Log message:

      Updated the Files files to use the new mmc_ prefix.
      The "open" and "extends" directives still need to be updated.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-05 18:19:28 -0700 (Mon, 05 Apr 2004)
Revision: 5607
Log message:

      Updated "opens" and "extends" directives to use the Mmc_ prefix.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-05 18:47:09 -0700 (Mon, 05 Apr 2004)
Revision: 5608
Log message:

      Add Mmc_ prefix in the syntax.pho and .prla files.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-05 19:49:45 -0700 (Mon, 05 Apr 2004)
Revision: 5609
Log message:

      Removed core/mmc_core_util, and split it into util/mmc_tactic_util
      and util/mmc_dform_util.  These utilities were never specific to
      the core.
      
      Converting the backend to use the standard definition of recursive
      functions.  Not finished yet.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-05 20:00:06 -0700 (Mon, 05 Apr 2004)
Revision: 5610
Log message:

      Updated display forms for sequents to use an explicit
      sequent_arg{...}.
      
      The ml_dform to display contexts is unsatisfying...  We should
      think about pattern syntax for contexts.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-05 20:37:48 -0700 (Mon, 05 Apr 2004)
Revision: 5611
Log message:

      . One last reorganization.  Here is the structure:
      .     util/ : directory for utilities that are generally useful
      .        and not particular to mmc
      .     base/ : terms and operations that are broadly applicable
      .        to *all* mmc modules
      .     core/ : the compiler core
      .     extensions/ : language extensions
      .     arch/ : backends
      .     main/ : the main compiler theory
      .     test/ : test programs
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-06 08:36:36 -0700 (Tue, 06 Apr 2004)
Revision: 5612
Log message:

      Added closure conversion on assembly code.
      
      Functions in the assembly now use the Lambda["rec"] version
      of recursive functions (the recursive binding is final in the
      parameter list).
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-06 14:35:42 -0700 (Tue, 06 Apr 2004)
Revision: 5613
Log message:

      1. Variable-sized reserves are now implemented in the backend.
      2. Added x86 support for direct function calls (for functions that do not escape).
      Still haven't tested spilling on this new code.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-06 20:27:58 -0700 (Tue, 06 Apr 2004)
Revision: 5614
Log message:

      1. Updated standardization to start from index 1.
      2. Simple spilling works.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-07 10:39:32 -0700 (Wed, 07 Apr 2004)
Revision: 5616
Log message:

      . Still working on spilling.
      .
      . Stopped at a MetaPRL bug, I'll file this on Bugzilla when I get a chance.
      .
      . var_subst does not avoid capture.
      . Example:
      .    var_subst << lambda{x. 'x + 'x} >> << 'x + 'x >> z -->
      .       << lambda{x. 'z} >>
      . Oops.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-07 14:12:10 -0700 (Wed, 07 Apr 2004)
Revision: 5617
Log message:

      Updated var_subst to avoid capture.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-07 20:20:58 -0700 (Wed, 07 Apr 2004)
Revision: 5618
Log message:

      . Corrected a problem with implicit moves in liveness analysis.
      . Suppose we have a 3-operand instruction that does not directly
      . map to the hardware.  For example, consider this instruction:
      .
      .     add %v1, %v2, v3. // v3 <- v1 + v2
      .
      . The hardware has only 2-operand instructions, so v2 and v3 must be
      . the same register.  This works if we add an "implicit" move before
      . the instruction.  This is the sequence that is emitted:
      .
      .     mov %v2, %v3 // v3 <- v2  (implicit mov)
      .     add %v1, %v3 // v3 += v1
      .
      . This is no problem.  However, the liveness analysis should not
      . treat the implicit move like a real move.  The allocator should
      . try to coalesce v2 and v3, but it should not consider that
      . this sequence has 2 definitions of v3.  The *length* of the
      . definition should be computed as if the definition happens
      . at the add.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-08 10:14:09 -0700 (Thu, 08 Apr 2004)
Revision: 5620
Log message:

      A few changes:
      
         1. Trying to get rid of the naming stage.  This stage should be used
            only when needed, not arbitrarily.  It might happen that naming
            is required for type inference, because of let-polymorphism,
            then we might want to add it back.
      
         2. Removed the || and && transformations from naming, and added
            a Mmc_core_front stage that is applied before CPS.  This is
            also where loops get transformed into recursive functions.
      
      One issue: currently it is the CPS transformation that ensures that
      conditionals don't return a value.  However, we want to apply this
      transformation even if we don't use CPS.
      
         3. Added an extension for unit values.
      
         4. Added an extension for loops.  Currently, we just have a while-loop.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-08 12:02:47 -0700 (Thu, 08 Apr 2004)
Revision: 5621
Log message:

      1. Removed the naming stage.
      2. Added the Mmc_core_front, for front-end transformations that
         are performed after type checking.  For example, this is the
         stage for eliminating:
            a. Short-circuit Boolean operations && and ||
            b. Loops
            c. Conditionals nested in an expression
      3. Added "direct" functions for functions that do not escape.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-08 12:29:49 -0700 (Thu, 08 Apr 2004)
Revision: 5622
Log message:

      Add the type of the continuation to the Front transformation.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-08 13:01:25 -0700 (Thu, 08 Apr 2004)
Revision: 5623
Log message:

      Working on type checking for direct functions.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-08 20:24:23 -0700 (Thu, 08 Apr 2004)
Revision: 5624
Log message:

      Stuck in CPS conversion without naming.  There is a bug in CPS;
      it generates code of the form:
      
         let cont : (int -> void) = lambda (res: int). res in ...
      
      No good.  This can be reproduced in Mmc_int_test.test_cps.
      
      There is another longer term problem.  We are starting to get some
      code duplication.  For example, suppose we have a rule that is defined
      for a specific param.  Consider the following:
      
         prim foo :
            ... Lambda["std"] ...
      
      Later, we add a new kind of lambda that is slightly different.  So we copy
      the rule text, just changing the parameter:
      
         prim foo_bar :
            ... Lambda["bar"] ...
      
      This is painful.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-09 15:27:36 -0700 (Fri, 09 Apr 2004)
Revision: 5625
Log message:

      A shorter example Mmc_int_test.test_cps1 that shows that CPS
      is broken.
      

Changes by: Aleksey Nogin (nogin at cs.caltech.edu)
Date: 2004-04-09 16:47:40 -0700 (Fri, 09 Apr 2004)
Revision: 5626
Log message:

      - The CPS for Ops was very wrong, fixed.
      
      - Updated the mcc script not to expect a specific theory name
        (and renamed it into mmc)
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-09 19:09:14 -0700 (Fri, 09 Apr 2004)
Revision: 5627
Log message:

      Direct calls are closer to working.  However, perhaps a different
      approach is better.  In the new approach, we would use normal
      std and rec functions before closure conversion, and only introduce
      direct calls after closure conversion as an optimization.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-10 15:33:53 -0700 (Sat, 10 Apr 2004)
Revision: 5628
Log message:

      Initial version of direct function calls.  This is now a pure optimization,
      so I'll move it to the opt/ directory.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-10 16:44:10 -0700 (Sat, 10 Apr 2004)
Revision: 5629
Log message:

      The direct function call phase is now an optimization.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-10 17:31:44 -0700 (Sat, 10 Apr 2004)
Revision: 5630
Log message:

      Moved beta reduction into the Mmc_core_inline module.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-10 18:52:04 -0700 (Sat, 10 Apr 2004)
Revision: 5631
Log message:

      Added a dead code elimination phase to get rid of at least some of the junk.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-10 18:53:05 -0700 (Sat, 10 Apr 2004)
Revision: 5632
Log message:

      The value judgment, used by dead code elimination.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-11 12:18:19 -0700 (Sun, 11 Apr 2004)
Revision: 5635
Log message:

      1. Change the opnames in Mmc_core_ast by adding a "U" prefix.
         For example, instead of Lambda[tag:s], we use ULambda[tag:s].
         There are far too many modules that include both Mmc_core_ast
         and Mmc_core_tast, and incorrect naming has been plaguing us.
      
      2. Changing recursive functions to a new form:
      
         sequent [Lambda["rec"]] { f: ty >- sequent [Lambda["std"]] { <H> -> 'e }}
      
         This expression is normally treated as a unit (meaning,
         the Lambda["rec"] doesn't make sense unless its body
         is a Lambda["std"]).
      
         This is cleaner, and allows recursion around other kinds
         of functions.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-11 15:23:21 -0700 (Sun, 11 Apr 2004)
Revision: 5637
Log message:

      Front-end transformations for recursive functions.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-11 15:59:17 -0700 (Sun, 11 Apr 2004)
Revision: 5639
Log message:

      Added closure conversion for recursive functions.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-11 18:42:45 -0700 (Sun, 11 Apr 2004)
Revision: 5640
Log message:

      Added direct-call optimizations for recursive functions.
      Finally, factorial is a loop.
      
      Not quite complete; the types are wrong at the moment.
      

Changes by: Nathaniel Gray (n8gray at caltech.edu)
Date: 2004-04-14 16:17:25 -0700 (Wed, 14 Apr 2004)
Revision: 5650
Log message:

      This is a stab at a PPC backend for the compiler.  It's not working yet so don't
      bother trying to use it.  I'm mostly committing this so that I'll have a backup
      and version history in CVS, and so that others in the group are aware of what
      I'm doing.
      
      These files are essentially just ports of the x86 versions with a few
      intelligent changes and a few not-so-intelligent changes made.  I think I've
      done a decent job adapting the asm and frame to PPC but other areas are not
      well thought out yet.
      

Changes by: Nathaniel Gray (n8gray at caltech.edu)
Date: 2004-04-15 17:11:39 -0700 (Thu, 15 Apr 2004)
Revision: 5653
Log message:

      Killed ast_util.  Nobody uses it.
      
      A couple of trivial additions for the ppc backend and comment corrections.
      

Changes by: Nathaniel Gray (n8gray at caltech.edu)
Date: 2004-04-15 18:21:48 -0700 (Thu, 15 Apr 2004)
Revision: 5654
Log message:

      Forgot to remove ast_util from the Files.
      

Changes by: Aleksey Nogin (nogin at cs.caltech.edu)
Date: 2004-04-15 18:25:40 -0700 (Thu, 15 Apr 2004)
Revision: 5655
Log message:

      - Added a Constrain to the let_var_optimize to keep it "information preserving".
      - Added couple more simple optimizations for the typed language.
      - Added stuckC reporting to Front.
      - Added a Front conversion for TyLambda.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-15 19:38:03 -0700 (Thu, 15 Apr 2004)
Revision: 5656
Log message:

      Added a comment on the front-end conversion of short-circuit
      Boolean operations.
      
      Note: as discussed the entire front stage (Mmc_core_front) is
      going away.  Some notes to whoever is in charge of this:
      
      Requirements:
         1. There should be a stage before the backend that makes sure
            that all control-flow operations (conditionals) are in
            tail position.
      
         2. There needs to be a stage to remove syntactic sugar from
            the source program.  Ideally, this should be done after type
            inference.
      
      Items to consider:
         1. I am not entirely sure that all syntactic sugar is context-free,
            but perhaps it is.  We can live with "macro-expansion" for now.
            The code for conditionals will be clearly suboptimal, but
            perhaps we can fix this up in a later optimization.
      
         2. For now, let's keep the core language after front-end
            conversions as small as possible.  Clearly, we can get
            more optimal code if we preserve the constructs (like
            loops, short-circuit Boolean operations, etc).  However,
            I think we should think about correctness first, optimization
            later.  In particular, if we can assume that If{'e1; 'e2; 'e3}
            is the only operator having non-strict evaluation, we will
            have fewer headaches.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-15 19:39:40 -0700 (Thu, 15 Apr 2004)
Revision: 5657
Log message:

      Loops should use "rec" functions, not "direct".  Lambda["direct"]
      are only introduced after closure conversion as an optimization.
      

Changes by: Aleksey Nogin (nogin at cs.caltech.edu)
Date: 2004-04-16 17:31:37 -0700 (Fri, 16 Apr 2004)
Revision: 5663
Log message:

      Declared a "default_extract" term and killed all those annoying "= it".
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-19 15:22:32 -0700 (Mon, 19 Apr 2004)
Revision: 5675
Log message:

      This is the update corresponding to yesterday's Lm_format
      change in MetaPRL.  Forgot to do the separate commit.
      

Changes by: Aleksey Nogin (nogin at cs.caltech.edu)
Date: 2004-04-20 20:34:22 -0700 (Tue, 20 Apr 2004)
Revision: 5683
Log message:

      Use the new resource syntax in MMC.
      

Changes by: Nathaniel Gray (n8gray at caltech.edu)
Date: 2004-04-21 18:58:36 -0700 (Wed, 21 Apr 2004)
Revision: 5690
Log message:

      Use a better .cvsignore
      

Changes by: Aleksey Nogin (nogin at cs.caltech.edu)
Date: 2004-04-21 22:35:30 -0700 (Wed, 21 Apr 2004)
Revision: 5693
Log message:

      The MMC part of the AutoMustComplete change.
      

Changes by: Nathaniel Gray (n8gray at caltech.edu)
Date: 2004-04-22 16:49:20 -0700 (Thu, 22 Apr 2004)
Revision: 5697
Log message:

      Preparing to start on the LIR.
      

Changes by: Nathaniel Gray (n8gray at caltech.edu)
Date: 2004-04-22 18:08:02 -0700 (Thu, 22 Apr 2004)
Revision: 5698
Log message:

      More notes.
      

Changes by: Nathaniel Gray (n8gray at caltech.edu)
Date: 2004-04-23 14:32:48 -0700 (Fri, 23 Apr 2004)
Revision: 5705
Log message:

      Won't try to build the x86 runtime on ppc architecture anymore.  In the future
      we'll want to fix this to allow cross-compilation.  We also probably want to
      push the architecture detection up into OMake.
      

Changes by: Nathaniel Gray (n8gray at caltech.edu)
Date: 2004-04-23 17:57:30 -0700 (Fri, 23 Apr 2004)
Revision: 5707
Log message:

      Started to add some lir files.  Now you guys can tell me how I did it wrong.
      Take a look at mmc_lir_of_ast.ml and let me know how it's really supposed to
      work.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-23 19:18:36 -0700 (Fri, 23 Apr 2004)
Revision: 5709
Log message:

      This is the matching commit against the MetaPRL update, for MMC to use Lm_printf.
      

Changes by: Jason Hickey (jyh at cs.caltech.edu)
Date: 2004-04-24 17:34:12 -0700 (Sat, 24 Apr 2004)
Revision: 5715
Log message:

      Matching IO commit for MMC.
      

Changes by: Aleksey Nogin (nogin at cs.caltech.edu)
Date: 2004-04-27 22:43:09 -0700 (Tue, 27 Apr 2004)
Revision: 5737
Log message:

      - BoundsCheck belongs to ext_array, not core_mem
      - We need two versions of Reserve - Reserve[i] in core_mem
      and reserve[e] in ext_array.
      

Changes by: Aleksey Nogin (nogin at cs.caltech.edu)
Date: 2004-04-28 14:56:59 -0700 (Wed, 28 Apr 2004)
Revision: 5738
Log message:

      Notes updates from the compiler meeting.
      

Changes by: Nathaniel Gray (n8gray at caltech.edu)
Date: 2004-04-29 19:36:27 -0700 (Thu, 29 Apr 2004)
Revision: 5742
Log message:

      The new file mmc_lir_simplify is a first draft of the code to eliminate all
      "closure" and "std" lambdas/apply's/tyfun's.  There are problems with types that
      aren't (and can't be) available.  As Aleksey realized this evening, closures
      should have existential type (the caller of a function can't know about the
      function's environment type).  So should we add this as an extension or as a
      core feature?  The other option is to push this stage back into the weakly-typed
      stage of the compiler and just fudge it.
      

Changes by: Aleksey Nogin (nogin at cs.caltech.edu)
Date: 2004-04-30 04:18:35 -0700 (Fri, 30 Apr 2004)
Revision: 5743
Log message:

      Added an extension for an existential type with pack/unpack. Untested.
      

Changes by: Nathaniel Gray (n8gray at caltech.edu)
Date: 2004-04-30 17:21:09 -0700 (Fri, 30 Apr 2004)
Revision: 5747
Log message:

      Finished renaming tyexists extension.
      

Changes by: Nathaniel Gray (n8gray at caltech.edu)
Date: 2004-04-30 17:22:52 -0700 (Fri, 30 Apr 2004)
Revision: 5748
Log message:

      More commits from renaming tyexists extension.