<p>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?</p>

<p>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). </p>

<p>The primary goal is to inline all functions, with recursions expanded once (except for self calls), with minimal rescanning.</p>

<p>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).</p>

<p>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).</p>

CC BY-SA 3.0
2012-01-02T22:48:00.903Z
(1) What is the motivation for looking at what you call the “optimal inlining”?  Even without recursions, inlining all the functions can make the program size exponentially larger, and therefore it is definitely not “optimal” in usual compilers.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-02T22:48:09.187Z
(2) I thought that it is straightforward to handle Algol-like nested functions (where functions cannot be used as a return value) by converting nested functions to usual functions with an additional argument representing the parent environment, and with this, it should be possible to forget about nested functions and just deal with non-nested functions.  So I do not get why existence of nested functions matters.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-03T04:17:47.757Z
(1) The motivation is to do the inlining process quickly. Without care, it is an exponential time algorithm. The issue is unrelated to the inline or not question.
Yttrill
CC BY-SA 3.0
2012-01-03T04:26:42.643Z
(2) How you represent the static scope is not relevant. When you inline a function P into some function F, P can no longer pass a pointer to its stack frame to child C, because the code is now part of F. You must make a new function C', which takes the stack frame of F as an argument, to get at the original variables of P. I hope this explains the problem.
Yttrill
CC BY-SA 3.0
2012-01-03T04:38:31.740Z
BTW: inlining "almost all" functions actually reduces programs size, since typically most functions do almost nothing and almost all the code is interfacing (call, return, etc, even worse if the functions are modelled as heap allocated objects (i.e. closures)). The secret of high performance is to optimise away all that stuff, and inlining is the way to do it. The question of how to obtain a balance between performance and code size is interesting but it isn't what I am asking about.
Yttrill
<ds.algorithms><graph-algorithms><compilers>
Optimal inlining algorithm
Yttrill
# Optimal inlining algorithm

(Asked by: username_0 on 2012-01-02)

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

**Tags:** ds.algorithms, graph-algorithms, compilers
> **Comments:**
> **username_1**: (1) What is the motivation for looking at what you call the “optimal inlining”?  Even without recursions, inlining all the functions can make the program size exponentially larger, and therefore it is definitely not “optimal” in usual compilers.  
> **username_1**: (2) I thought that it is straightforward to handle Algol-like nested functions (where functions cannot be used as a return value) by converting nested functions to usual functions with an additional argument representing the parent environment, and with this, it should be possible to forget about nested functions and just deal with non-nested functions.  So I do not get why existence of nested functions matters.  
> **username_0**: (1) The motivation is to do the inlining process quickly. Without care, it is an exponential time algorithm. The issue is unrelated to the inline or not question.  
> **username_0**: (2) How you represent the static scope is not relevant. When you inline a function P into some function F, P can no longer pass a pointer to its stack frame to child C, because the code is now part of F. You must make a new function C', which takes the stack frame of F as an argument, to get at the original variables of P. I hope this explains the problem.  
> **username_0**: BTW: inlining "almost all" functions actually reduces programs size, since typically most functions do almost nothing and almost all the code is interfacing (call, return, etc, even worse if the functions are modelled as heap allocated objects (i.e. closures)). The secret of high performance is to optimise away all that stuff, and inlining is the way to do it. The question of how to obtain a balance between performance and code size is interesting but it isn't what I am asking about.  

---

## 0 answers

