[MLton] leaf inlining

[skaller]

On Mon, 2007-06-25 at 07:20 -0500, Matthew Fluet wrote:
> skaller wrote:
> > 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?
> 
> In the leafInline optimization pass, yes.  In the later general inlining 
> pass, there is a more permissive inlining heuristic.

Hmm .. what is a leaf? I this a leaf in the call graph,
or a leaf in the child tree?

> In MLton, a function is inlined at all of its call sites, or not at all. 
>   So, recursive functions may never be inlined.

Consider (Ocaml notation sorry):

	let f x = 
		let g x = G1 f x G2 in
		F1  g x F2

Here, both f and g are recursive, but you should inline g into F:

	let f x = F1 G1 f x G2 F1 

in particular if G2 and F2 are nops, f is now tail rec,
so you might convert it to a loop, in which case f isn't
recursive any more.

This could be done in the leaf optimisation pass.

> > When you say 'pass' is this a single operation applied to
> > the whole program?
> 
> An SSA optimization pass is an SSA IL program to SSA IL program 
> transformation.

I see .. sorry I don't know the MLton representations.

In Felix there is no 'program' as such, just a collection
of functions .. so ..

> > Is there any ordering?
> 
> There is a fixed sequence of optimization passes, applied in order.

.. what I actually meant was was there an ordering on optimising
functions, but perhaps this makes no sense in Mlton: in the
Felix IL, there is a discrete collection of functions with
bodies, and inlining into functions is done by:

	(a) before inlining into F, inline into its children
	(b) before inlining G into F, inline into G

in both cases provided inlining hasn't already commenced
(or completed).

During inlining, many other rewrite rules are applied,
for example self-tail-call-to-loop optimisation *must* be done
during inlining. See the example above.

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