[MLton] Possible contributions to optimization

[Matthew Fluet]

Hi Kristopher,

If you are interested in contributing to MLton, you should subscribe to 
the MLton development list (mlton at mlton.org; link available from 
http://mlton.org/Contact).

The wiki contains a number of pages that point towards various aspects of 
development:
   http://mlton.org/Development -- overview of development pages
   http://mlton.org/CompilerOverview -- overview of compiler structure,
     including links to various intermediate languages and optimization
     passes (themselves with links to the corresponding source files).
   http://mlton.org/Projects -- short list of suggested projects
   http://mlton.org/Talk -- a very brief overview talk of the compiler
   http://mlton.org/References#Weeks06 -- a longer talk about the compiler

Based on your self-description, I would probably suggest thinking about 
implementing a loop-invariant code motion optimization pass in the SSA IL.
Because MLton uses a defunctionalization technique 
(http://mlton.org/References#CejtinEtAl00) to turn higher-order functions 
into first-order functions, the SSA IL looks very much like one you would 
see in a first-order language compiler (like one for C).  This means that 
a lot of "traditional" compiler optimizations can be implemented in a 
fairly straightforward manner.  Nearly every compiler textbook will have a 
description of loop-invariant code motion, and there is a good chance that 
it would have some measurable impact on code.  It should also be fairly 
easy to adapt to the SSA IL.

Some starting points would be to familiarize yourself with the SSA IL, 
familiarize yourself with some of the other SSA IL optimizations 
(http://mlton.org/SSASimplify; the CommonSubexp optimization is fairly 
straightforward and should be familar from a compiler textbook).  You can 
use the "-keep-pass passName" and "-diag-pass passName" compiler options 
to dump the program as it appears before and after a pass and to dump 
various diagnostics generated by the pass.  Also, the "-keep ssa" compiler 
option will dump the final SSA IL program during the compilation. 
Browsing through some of the dumped .ssa files will help you see what the 
intermediate code looks like.

And, of course, feel free to ask questions on the development list.

-Matthew

On Sun, 2 Mar 2008, Kristopher Micinski wrote:
> Hello all MLton developers,
>
>    I've been writing code in SML and other functional languages for a
> little more than a year (after being converted from a 7 year C
> tenure). I'm a HS senior, and have pretty much completed my
> requirements for schooling other than formalities. I now have a bit of
> time on my hands (a few months or so, before I head off to college,
> and I don't know where I'll be going yet) to work on whatever I want.
> I want to look at working on the MLton compiler, perhaps improving
> some optimization it makes. Does anyone have any input as to what I
> should start doing (other than reading the source) or what some good
> optimizations might be. I am aware of the projects page, and have a
> little compiler experience. I've written a C parser and a part of the
> backend, and a compiler for another language. Both have targeted
> virtual machines; I don't have much experience with the low level
> instruction coding of architectures. I also have no experience with
> compiling functional languages, but I'd like to help a little.
>
>    -- Kristopher Micinski
>
> _______________________________________________
> MLton mailing list
> MLton at mlton.org
> http://mlton.org/mailman/listinfo/mlton
>