Editing Inline expansion (section)

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