Editing Inline expansion (section)

== Implementation ==
Once the [[compiler]] has decided to inline a particular function, performing the inlining operation itself is usually simple. Depending on whether a compiler inlines functions across code in different languages, the compiler can inline on either a high-level [[intermediate representation]] (like [[abstract syntax tree]]s) or a low-level intermediate representation. In either case, the compiler simply computes the [[Parameter|arguments]], stores them in variables corresponding to the function's arguments, and then inserts the body of the function at the call site.

[[Linker (computing)|Linkers]] can also do function inlining. When a linker inlines functions, it may inline functions whose source is not available, such as library functions (see [[link-time optimization]]). A [[runtime system]] can inline a function also. [[Runtime (program lifecycle phase)|Runtime]] inlining can use dynamic profiling information to make better decisions about which functions to inline, as in the [[HotSpot (virtual machine)|Java HotSpot compiler]].<ref>[https://www.researchgate.net/publication/331408280_An_Optimization-Driven_Incremental_Inline_Substitution_Algorithm_for_Just-in-Time_Compilers] Description of the inliner used in the Graal JIT compiler for Java</ref>

Here is a simple example of inline expansion performed "by hand" at the source level in the [[C (programming language)|C language]]:
<syntaxhighlight lang="c">
int pred(int x)
{
    if (x == 0)
        return 0;
    else
        return x - 1;
}
</syntaxhighlight>

''Before inlining:''
<syntaxhighlight lang="c">
int func(int y) 
{
    return pred(y) + pred(0) + pred(y+1);
}
</syntaxhighlight>

''After inlining:''
<syntaxhighlight lang="c">
int func(int y) 
{
    int tmp;
    if (y   == 0) tmp  = 0; else tmp  = y - 1;       /* (1) */
    if (0   == 0) tmp += 0; else tmp += 0 - 1;       /* (2) */
    if (y+1 == 0) tmp += 0; else tmp += (y + 1) - 1; /* (3) */
    return tmp;
}
</syntaxhighlight>

Note that this is only an example. In an actual C application, it would be preferable to use an inlining language feature such as [[parameterized macro]]s or [[inline function]]s to tell the compiler to transform the code in this way. The next section lists ways to optimize this code.

=== Inlining by assembly macro expansion ===
[[Macro assembler#Macros|Assembler macros]] provide an alternative approach to inlining whereby a sequence of instructions can normally be generated inline by macro expansion from a single macro source statement (with zero or more parameters). One of the parameters might be an option to alternatively generate a one-time separate [[subroutine]] containing the sequence and processed instead by an inlined call to the function.
Example:
 MOVE FROM=array1,TO=array2,INLINE=NO

=== Heuristics ===
A range of different heuristics have been explored for inlining. Usually, an inlining algorithm has a certain code budget (an allowed increase in program size) and aims to inline the most valuable callsites without exceeding that budget. In this sense, many inlining algorithms are usually modeled after the [[Knapsack problem]].<ref>[https://dl.acm.org/citation.cfm?id=359830] Scheifler, An Analysis of Inline Substitution for a Structured Programming Language</ref> To decide which callsites are more valuable, an inlining algorithm must estimate their benefit—i.e. the expected decrease in the execution time. Commonly, inliners use profiling information about the frequency of the execution of different code paths to estimate the benefits.<ref>[https://dl.acm.org/citation.cfm?id=351416] Matthew Arnold, Stephen Fink, Vivek Sarkar, and Peter F. Sweeney, A Comparative Study of Static and Profile-based Heuristics for Inlining</ref>

In addition to profiling information, newer [[just-in-time compiler]]s apply several more advanced heuristics, such as:<ref name="prokopec2019">[https://www.researchgate.net/publication/331408280_An_Optimization-Driven_Incremental_Inline_Substitution_Algorithm_for_Just-in-Time_Compilers] Prokopec et al., An Optimization Driven Incremental Inline Substitution Algorithm for Just-In-Time Compilers, CGO'19 publication about the inliner used in the Graal compiler for the JVM</ref>
* Speculating which code paths will result in the best reduction in execution time (by enabling additional compiler optimizations as a result of inlining) and increasing the perceived benefit of such paths.
* Adaptively adjusting the benefit-per-cost threshold for inlining based on the size of the compiling unit and the amount of code already inlined.
* Grouping subroutines into clusters, and inlining entire clusters instead of singular subroutines. Here, the heuristic guesses the clusters by grouping those methods for which inlining just a proper subset of the cluster leads to a worse performance than inlining nothing at all.