I seek an algorithm to optimise the process of inlinling. Is there such an algorithm, or set of such algorithms? Is there an efficient functional algorithm?
To be specific assume we have an Algol like language with nested functions. There are two relevant graphs: the static nesting graph, and the call graph. Interestingly I was unable to find any description or papers regarding the relation of these (though such must exist).
The primary goal is to inline all functions, with recursions expanded once (except for self calls), with minimal rescanning.
I must add here one of the key problems. When a function is inlined into another you glue in the code with parameters replaced by arguments. But that is not enough, you must also clone all the children of the function being inlined, and their descendants, and add them as children of the function into which you're inlining. If you use simple renaming this makes it exceedingly difficult to prevent infinite expansion of recursive calls, since any trail you're keeping won't refer to these cloned children. The cloned children also have parameter replacement performed (including specialisation of type variables).
The algorithm I am using works and always terminates but is neither optimal, nor does it meet the design goal: I found it necessary to add a constraint that prevents sibling recursions being expanded (only recursions to children are expanded).
