[MLton] genetic algorithms for SSA optimization phase ordering

[Stephen Weeks]

Sorry for the slow response on this one.  I didn't have too much to
contribute.

> I looked up the paper by Cooper et. al.
> (http://citeseer.nj.nec.com/cooper99optimizing.html) and thought it would
> be fairly easy to adapt to MLton.
...
> A key concern is how to design the fitness function.

There were a couple of what looked to be typos.  I mention them to
make sure they aren't also in the code.

> T is executed on each of the benchmarks to determine CT(bench), SB(bench),
!                                                                 ST(bench)
> and RB(bench).  The fitness of a test chromosome is given by:
!     RT(bench)
> fitness(T) =
>   let
>     t = Sum_{b in Bench} W(b)
>     c = (Sum_{b in Bench} (CT(b) / CB(b)) * W(b)) / t
>     s = (Sum_{b in Bench} (ST(b) / SB(b)) * W(b)) / t
>     r = (Sum_{b in Bench} (ST(b) / SB(b)) * W(b)) / t
!     r = (Sum_{b in Bench} (RT(b) / RB(b)) * W(b)) / t
>   in
>     ((c * CW) + (s * SW) + (r * RW)) / (CW + SW + RW)
>   end
...
> Any suggestions for how to set the weights; or a different fitness
> function altogether?

Only two simple ideas: emphasize run time and emphasize larger
benchmarks.

> In any event, no results, other than finding a long standing bug in the
> simplifyTypes pass, which was revealed pretty quickly when the ssa passes
> were randomized.

Definitely useful.

It might be nice to keep track of the chromosome that produced the
minimum (run time, say) for each benchmark.  It would be interesting
to see how that compares to what the baseline chromosome produces, as
well as to any better chromosome you find.