[MLton-devel] optimizations needed?

[Stephen Weeks]

>   I'm taking a class on compiler optimizations this semester and I was
> thinking of doing a back-end optimization in MLTon for my semester
> project.  Can you suggest an optimization that's not implemented yet? It
> would be best if it could be written as a self-contained pass, was not an
> ML-specific optimization (though I am not entirely opposed) and was likely
> to produce positive results...
> 
>   For instance, is partial redundancy elimination (or something that
> subsumes it) implemented in mlton?

Hi Tom.  This sounds like a great idea to me!  Probably the right
place for you to work is on the SSA IL (ssa/ssa-tree.sig), a variant
of traditional SSA.  In our SSA IL, a program is a collection of
mutually recursive simply-typed first-order functions (see datatype
Program.t).  Each function is represented as a set of basic blocks
(see Function.dest) implicitly defining a control-flow graph.  Our
main difference from traditional SSA is that instead of using
phi-functions, our basic blocks take arguments and gotos pass them.
Another way to think of it is that the blocks in a function are
themselves a collection of mutually recursive functions that share the
same stack frame.

Anyways, MLton's optimizer is structured as a pipeline of
self-contained SSA-to-SSA transformations.  For an overview of the
optimizer, see ssa/simplify.fun.  You should be able to pattern match
off of all of the optimizations defined there and add your own pass to
the simplifier pipeline (val passes).  Once you have it there, you can
run all the benchmarks with {,-drop-pass <pass-name>} to compare them
with and without your pass.

As to partial redundancy elimination, I would love to see it.  Or
anything else that does loop-invariant code motion, which we don't do
now.  We do do common-subexpression elimination
(ssa/common-subexp.fun) using a simple traversal of the dominator
tree.  But of course this will only eliminate something from a loop if
it happens to be computed in a block that dominates the loop header.
Anyways, you might want to look at this pass to try to start
understanding our SSA IL and what a pass should look like.

I would hope to see decent improvements from PRE.  One of the things
that I've always thought was a shame about MLton is that we do all
this great stuff (higher-order flow analysis, contification, inlining,
...) to get really nice control-flow graphs and then don't do any loop
optimizations.

You should take care to make the PRE work for all of the expressions
(datatype Exp.t) that can appear in a basic block statement.  This
will get both the functional stuff as well as the more traditional
arithmetic optimizations.  You also need to pay attention to the
arithmetic that can happen in Transfer.Arith, which handles overflow
detection.

I hope that's enough to get you started.  Please feel free to send
mail with any questions, no matter how small.  We realize that there's
no documentation and don't want that to cause you problems.  Also,
please be sure to send everything to MLton@mlton.org, since others who
read the list, especially Matthew Fluet, also have a good working
knowledge of our SSA IL.  You'll always get at least as fast a
response sending to MLton as you will to me.

Good luck!


-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel