[MLton] Optimizations done by GCC 4.0
Wed, 13 Oct 2004 10:08:46 -0700
> * 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
> > 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.