[MLton-user] more optimization questions

Matthew Fluet fluet@cs.cornell.edu
Sun, 20 Nov 2005 18:10:22 -0500 (EST)


>> 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.
>> 
> I suppose I can figure this out from the intermediate files.
>
> I'm making an unguided attempt to do so, but finding something specific like 
> the selects will require a little guidance :-)

You want to compile with  -keep ssa -keep ssa2 -keep rssa  to keep the 
the major intermediate language forms of your program.

See: http://mlton.org/CompilerOverview
for an overview of these different intermediate languages and their 
corresponding optimization passes.  You would be looking for Select 
expressions, which will appear as  #n  expressions in the printed 
intermediate forms.

>> 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.
>
> I've got the source and I'm looking through it.
>
> Any docs ? :-)

See the CompilerOverview.

> Where in the compiler would the SLICMP live ?

In either the SSA optimization passes or the SSA2 optimization passes. 
I'd vote for SSA, since it is a slightly simpler intermediate language, 
though there has been some argument for migrating all the optimizations 
from SSA to SSA2 and then eliminating SSA.