[MLton] Optimizations done by GCC 4.0

[Stephen Weeks]

> * Strength reduction
> 
> Ah, the good old optimization. I expect MLton to do this, though there
> is no pass explicitly mentioning this. (loopInvariant maybe?)

A very little bit of strength reduction is done in atoms/prim.fun in
the apply function, which, among other things, rewrites primapps to
primapps.  For example, it will change a multiply by ~1 into a negate.

> * Dead store elimination
> 
> A store to something never used is dead, so it can be removed.

MLton has a whole-program analysis in ssa/useless.fun that covers
this somewhat.  The pass eliminates ref cells that are never read
from.  I guess also that some combination of localFlatten, the
shrinker, and removeUnused will get these.

> I was wondering if this applies to MLton at all. Most of them are
> already done, so I am wondering about the things MLton does not do,
> and if it would give anything. I think there might be a reason why
> they are not implemented (too little gain for too much analysis and
> too specialized comes to mind).

One never knows, and as MLton continues to improve it becomes harder
and harder to find effective optimizations.  I agree with Matthew that
PRE would be nice.  My overall feeling on most of these low-level
optimizations, though, is that because SML source is so different from
C source, there are often higher-level optimizations that will give
more gains (e.g. flattening).  One other thing to keep in mind is that
SML is a very effectful language when you start looking at a compiler
IL, because overflowing arithmetic ops can raise exceptions.  This
tends to make code motion hard.

> Actually, those responses were to a query from Tom Murphy.  He and
> Brendan McMahan at CMU went on to do a project that implemented PRE
> for MLton's SSA: http://www-2.cs.cmu.edu/~tom7/ssapre/
> Unfortunately, we've never seen the code or benchmark results.

I don't think they ever got far enough to do benchmarks.  Here's a
pointer to my summary of their final report 

	http://www.mlton.org/pipermail/mlton/2003-May/013942.html

> > Is there a complete description of all passes MLton does? If not, would
> > there be a point in having one?
...
> In the SSA IL, we current do the following:
...

Hopefully I will add a Wiki soon and we can put this up there.