[MLton] leaf inlining

[skaller]

On Sun, 2007-06-24 at 22:46 -0500, Matthew Fluet wrote:

> I added an introduceLoops pass before inlining, since inlining can't be 
> applied to recursive functions (and recursive functions aren't leaf).

Huh? Is Mlton only inlining non-recursive leaves?

When you say 'pass' is this a single operation applied to
the whole program?

Is there any ordering?

I'm confused .. because Felix comes close to inlining
everything in a single pass. It inlines all children,
recursive or not, leaf or not, and all other non-recursive
calls. 

Inlining is done by recursive-descent with coloring
and trail to prevent cycles.

The 'text' which is about to be dumped into a body
after specialisation is optimised again (recursively).

So in effect inlining is idempotent.

This property was unfortunately lost when I introduced
typeclasses. Therefore, the result of polymorphic inlining
is monomorphised and inlining applied again. 

The polymorphic inlining pass has no semantics in that
case, but is retained to improve the performance of
the post mono-morphisation inliner.

I say 'close' to optimal because there are some nasties
I haven't solved. This relates to inlining functions which
have children .. the children have to be 'cloned' and
specialised too (I call this reparenting).

This can cause the number of functions
in the program to increase without bound if care is not
taken, since re-scanning the specialised code before
dumping it can retrigger the reparenting operation if
the target is recursive: that's because on reparenting
a recursive call can become non-recursive (because
the specialised code is calling the general code
which of course can't call it back, since the special
code is a fresh copy but the general code is immutable).

This actually happens because the inlining operation is
not entirely recursive, but uses rescanning. Rescanning
is mandatory because there are multiple context
sensitive rewrite rules (and recursion can't see context).

Optimisation by recursion and rescanning is much harder to get
right than multiple passes .. but it is much more effective.

For example: Felix has two value specialisation methods: 
eager (assign the argument to a variable) and lazy (replace
the parameter with the variable).

Even when eager specialisation is used, it still does some
low level dataflow analysis to try to replace uses of variables
by their values. This is done recursively during inlining,
because it can expose more inlining opportunities.

For the same reason every application is checked to see if
a virtual function can be replaced by its specialisation
(virtual function is my term for a method of a typeclass,
specialisation is a method of some instance).

[Typeclass virtual function replacement is similar to defunctorisation,
so I guess the same issues arise]

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net