[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.