[MLton-user] more optimization questions

Stephen Weeks sweeks@sweeks.com
Sat, 19 Nov 2005 21:21:31 -0800


Speaking of common-subexpression elimination and loop optimizations, I
misspoke when I said that there would be no record destructuring when
doing 3-d array subscript.  Looking at the code again:

>      fun index (A3{n1, n2, n3, ...}, i, j, k) =
>          (* 2 mults/2 adds for each index count *)
>          k + n3 * (j + n2 * i)
>
>      fun sub (arr as A3{elems, ...}, i, j, k) =
>          Array.sub(elems, index(arr, i, j, k))

There will be no tuple construction/select for getting arr, i, j, k.
However, there may be record selects to get elems, n1, n2, n3.  MLton
doesn't do loop-invariant code motion, so those selects will not get
lifted outside the loop automatically.  Since MLton does
common-subexpression elimination, it should be possible to convince it
to move the selects of elems, n1, n2, n3 outside the loop by doing
those same selects in some code that dominates the loop (e.g. by
creating a loop header that is the only entry) and doesn't get
optimized away.  Easier said than done, and I don't have a ready idea
at hand.  But it might be worth looking into, after first verifying
from the generated code that the selects indeed aren't lifted out.

Another alternative is to write a simple loop-invariant code motion
pass for MLton :-).  It shouldn't be too hard to get this sort of
thing; it's just that none of us has ever found the time.