optimial inlining algo?

optimial inlining algo?

[skaller]

I am trying to reduce a set of routines, with certain routines
deemed roots, to an optimal configuration by inlining. A configuration
is optimal if, apart from the roots, the only routines left are
self-recursive.

You can easily extend this to non-tail-recursive. For the purpose
of the discussion functional values don't exist (although the
real algorithm also tries to eliminate closures, and should
ensure this is the case if an argument is an anonymous function).

The inlining process consists of making a copy of a function
and all its children, except its parameters. The copies are then
type specialised based on the call, and parameter specialised
by replacing parameters with arguments (the real algorithm
also permits copying the parameter and assigning the argument
to it).

The application is then replaced by a fresh variable, which is
initialised by inlining the modified function body, replacing
return statements with initialisation of this variable.

The code to do the mechanics of inlining isn't the issue here,
the problem is deciding whether to inline the application.

In principle, this problem just involves two related graphs:
the call graph and child graph. The problem is that the graphs
are subject to both reduction (removing functions by inlining
them) and also expansion (adding specialised copies of children).

My actual algorithm does this: before optimising a function,
optimise its children. Before inlining a function, optimise
that function. Optimisation is a mutator: functional code would
be hopelessly inefficient.

The difficulty is ensuring recursions like

	A has child B has child C
	A calls B calls C calls C

are flattened by inlining C into B, then B into A.
A call to A, however, must not be inlined.

I'm trying to build a rule based on three properties:

	a) the call in A to B is recursive
	b) the function F is recursive
		(equivalent to F contains a recursive call)
	c) A is the parent of B

together with an ordering of optimisations. I can't find
a rule that actually works (it either fails to produce 
optimal results, or clones children infinitely)

Anyone have any ideas?

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