What are the cons of inlining then optimizing and then reverse inlining?

Question

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

Answer 1

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.

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

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