<p>In many programming languages, not all functions may be inlined. However, assuming that a language is designed in such a way that all functions may be inlined, what the disadvantages of inlining all functions, performing optimizations, and then reverse inlining what can be compacted?</p>
<p>If code is converted to a stack based intermediate representation, then reversing the inlining operation should be as simple as identifying repeating sequences of code using an algorithm such as a modified version of byte-pair encoding, followed by re-inlining functions that only occur once. Then the stack intermediate representation can be converted back into four address code.</p>
<p>Some problems that I might guess might be asymptotic worst case space and time complexity of the compiler and cases where very little can be reversed. However, other people might have other ideas.</p>
<p>A similar question is <a href="https://langdev.stackexchange.com/questions/1574/what-are-the-disadvantages-of-automatically-inlining-all-functions">What are the disadvantages of automatically inlining all functions?</a>. However, reverse inlining might decrease the pressure on the processor's instruction cache, and it might reduce spilling into the stack, and thus many of the responses to that question might apply significantly less.</p>

<compilers><implementation><inlining>
What are the cons of inlining then optimizing and then reverse inlining?
<h3>Cons, not necessary</h3>
<blockquote>
<p>In many programming languages, not all functions may be inlined. However, assuming that a language is designed in such a way that all functions may be inlined, what the disadvantages of inlining all functions, performing optimizations, and then reverse inlining what can be compacted?</p>
</blockquote>
<p>All optimizations that are possible with block inlining and reverse inlining can also be done <a href="https://reviews.llvm.org/D93838" rel="nofollow noreferrer">generating specializations</a> of each group of pairwise functions, in successive rounds, until no new pairwise functions can be specialized.</p>
<p>You may not be wanting to generate copies of functions, but optimize the declared functions based on caller usage. This is only possible if you know all callers. This is in the realm of <a href="https://en.wikipedia.org/wiki/Interprocedural_optimization" rel="nofollow noreferrer">whole program optimizations</a>.</p>
<p>The first one generate faster but potentially bigger code (function copies), and the second one is focused in generating smaller code, with few optimization opportunities (two distinct callers may restrict optimizations in one called function).</p>

CC BY-SA 4.0
2024-04-29T15:05:17.083Z
2024-04-29T15:05:17.083Z
André L F S Bacci
CC BY-SA 4.0
2024-04-29T17:47:00.650Z
It's not immediately obvious to me why inlining and reverse inlining cannot be more powerful than the approach you describe.
Eldritch Conundrum
CC BY-SA 4.0
2024-12-23T00:11:31.660Z
In many cases, I would think that in cases where some of a function's arguments will be constants, attempting to inline the function, seeing if everything collapses to be simpler than a function call, and otherwise using a function call would be a simple way to reap some big benefits in common scenarios, without excessive cost in others.
supercat
<p>First, many of the disadvantages in <a href="https://langdev.stackexchange.com/questions/1574/what-are-the-disadvantages-of-automatically-inlining-all-functions">What are the disadvantages of automatically inlining all functions?</a> still apply, since you must be able to <em>tentatively</em> inline every function call.  This means your language cannot have recursion, mutual recursion, function pointers, virtual methods, shared or precompiled libraries, dynamically loaded modules, etc.</p>
<p>Your point about worst-case complexity is important.  For instance, imagine a program that looks like</p>
<pre><code>void a() {
    // some code
}

void b() {
    if (cond1) a();
    if (cond2) a();
}

void c() {
    if (cond1) b();
    if (cond2) b();
}
</code></pre>
<p>and so on.  If you iterate this n times, then you have to, at least tentatively, inline 2^n copies of the function <code>a()</code>, even if you deinline them later.  Thus your compiler can require memory and running time that is exponential in the size of the input source code, even when the running time of the program itself may be much less (e.g. if many of the <code>if</code> conditions are false at runtime).  There are mainstream compilers which do optimizations that have exponential worst-case behavior (e.g. register allocation via graph coloring is NP-complete) but usually only in rare cases, and they can usually shortcut the process and just emit less optimal code if it is taking too long.  But your compiler would have no choice but to crunch through it all, and hope it finishes before the universe suffers heat death.</p>
<p>Another concern: it could happen that, given two different call sites, they may be optimized differently enough that they cannot be recognized as similar enough to be candidates for reverse inlining, even if that would otherwise be a win.  Constant propagation would likely cause this issue, for example.</p>

CC BY-SA 4.0
2024-05-03T01:49:06.247Z
2024-05-03T01:49:06.247Z
Nate Eldredge
CC BY-SA 4.0
2024-05-03T03:43:51.307Z
Actually, any recursive function can theoretically be rewritten as one using a loop and a stack. This isn't very difficult when a function is only recursive with itself. However, it often hurts performance, as extra memory must be allocated for a stack unless the function is tail-recursive. Conversion to loops would help performance for tail recursive functions. However, unless the compiler has sufficient loop optimizations, the conversion to loops would defeat much of the purpose of inlining the function.
ggZQX6YPvD
CC BY-SA 4.0
2024-05-03T04:01:42.140Z
If having sane performance were to not matter (it does matter), all of those impossible features are theoretically possible if the language is turing complete; however, some of them may explode code size while defeating the whole purpose of the inlining in the first place. Precompiled libraries could be inlined if inline assembly is allowed. However, a compiler almost certainly cannot optimize the inline assembly, and inline assembly can turn many variables volatile, which could hurt performance. Function pointers could be turned into enormous switch statements with many function calls, etc.
ggZQX6YPvD
CC BY-SA 4.0
2024-05-03T04:24:12.297Z
The problem with the complexity causing it to not be finished by the heat death of the universe could be addressed by simply rejecting all programs that take too long to compile. This would not involve crunching through to the heat death of the universe. However, that might impede on the usability and expressiveness of the language, and also if a user didn't understand the workings of the compiler, they might be left wondering why their perfectly correct program with no errors was completely rejected. The program wouldn't nessesarially look anywhere near as long as it could expand to.
ggZQX6YPvD
# What are the cons of inlining then optimizing and then reverse inlining?
Posted by: username_0 on 2024-04-29
In many programming languages, not all functions may be inlined. However, assuming that a language is designed in such a way that all functions may be inlined, what the disadvantages of inlining all functions, performing optimizations, and then reverse inlining what can be compacted?

If code is converted to a stack based intermediate representation, then reversing the inlining operation should be as simple as identifying repeating sequences of code using an algorithm such as a modified version of byte-pair encoding, followed by re-inlining functions that only occur once. Then the stack intermediate representation can be converted back into four address code.

Some problems that I might guess might be asymptotic worst case space and time complexity of the compiler and cases where very little can be reversed. However, other people might have other ideas.

A similar question is [What are the disadvantages of automatically inlining all functions?](https://langdev.stackexchange.com/questions/1574/what-are-the-disadvantages-of-automatically-inlining-all-functions). However, reverse inlining might decrease the pressure on the processor's instruction cache, and it might reduce spilling into the stack, and thus many of the responses to that question might apply significantly less.
**Tags:** compilers implementation inlining
---
## 2 answers
### Answer by username_4 on 2024-05-03. Score: 2 | Accepted answer
First, many of the disadvantages in What are the disadvantages of automatically inlining all functions? still apply, since you must be able to tentatively inline every function call.  This means your language cannot have recursion, mutual recursion, function pointers, virtual methods, shared or precompiled libraries, dynamically loaded modules, etc.
Your point about worst-case complexity is important.  For instance, imagine a program that looks like
void a() {
    // some code
}

void b() {
    if (cond1) a();
    if (cond2) a();
}

void c() {
    if (cond1) b();
    if (cond2) b();
}

and so on.  If you iterate this n times, then you have to, at least tentatively, inline 2^n copies of the function a(), even if you deinline them later.  Thus your compiler can require memory and running time that is exponential in the size of the input source code, even when the running time of the program itself may be much less (e.g. if many of the if conditions are false at runtime).  There are mainstream compilers which do optimizations that have exponential worst-case behavior (e.g. register allocation via graph coloring is NP-complete) but usually only in rare cases, and they can usually shortcut the process and just emit less optimal code if it is taking too long.  But your compiler would have no choice but to crunch through it all, and hope it finishes before the universe suffers heat death.
Another concern: it could happen that, given two different call sites, they may be optimized differently enough that they cannot be recognized as similar enough to be candidates for reverse inlining, even if that would otherwise be a win.  Constant propagation would likely cause this issue, for example.
> **Comments:**
> **username_0** (2024-05-03): Actually, any recursive function can theoretically be rewritten as one using a loop and a stack. This isn't very difficult when a function is only recursive with itself. However, it often hurts performance, as extra memory must be allocated for a stack unless the function is tail-recursive. Conversion to loops would help performance for tail recursive functions. However, unless the compiler has sufficient loop optimizations, the conversion to loops would defeat much of the purpose of inlining the function.  
> **username_0** (2024-05-03): If having sane performance were to not matter (it does matter), all of those impossible features are theoretically possible if the language is turing complete; however, some of them may explode code size while defeating the whole purpose of the inlining in the first place. Precompiled libraries could be inlined if inline assembly is allowed. However, a compiler almost certainly cannot optimize the inline assembly, and inline assembly can turn many variables volatile, which could hurt performance. Function pointers could be turned into enormous switch statements with many function calls, etc.  
> **username_0** (2024-05-03): The problem with the complexity causing it to not be finished by the heat death of the universe could be addressed by simply rejecting all programs that take too long to compile. This would not involve crunching through to the heat death of the universe. However, that might impede on the usability and expressiveness of the language, and also if a user didn't understand the workings of the compiler, they might be left wondering why their perfectly correct program with no errors was completely rejected. The program wouldn't nessesarially look anywhere near as long as it could expand to.  
---
### Answer by username_1 on 2024-04-29. Score: 2
### Cons, not necessary

> In many programming languages, not all functions may be inlined. However, assuming that a language is designed in such a way that all functions may be inlined, what the disadvantages of inlining all functions, performing optimizations, and then reverse inlining what can be compacted?

All optimizations that are possible with block inlining and reverse inlining can also be done [generating specializations](https://reviews.llvm.org/D93838) of each group of pairwise functions, in successive rounds, until no new pairwise functions can be specialized.

You may not be wanting to generate copies of functions, but optimize the declared functions based on caller usage. This is only possible if you know all callers. This is in the realm of [whole program optimizations](https://en.wikipedia.org/wiki/Interprocedural_optimization).

The first one generate faster but potentially bigger code (function copies), and the second one is focused in generating smaller code, with few optimization opportunities (two distinct callers may restrict optimizations in one called function).
> **Comments:**
> **username_2** (2024-04-29): It's not immediately obvious to me why inlining and reverse inlining cannot be more powerful than the approach you describe.  
> **username_3** (2024-12-23): In many cases, I would think that in cases where some of a function's arguments will be constants, attempting to inline the function, seeing if everything collapses to be simpler than a function call, and otherwise using a function call would be a simple way to reap some big benefits in common scenarios, without excessive cost in others.  
---
