inline.pl
Inlining of static functions on unchecked IR before promotion: --inline=small (docs/perf.md item 4) takes small leaves in two rounds; --inline=wide (item 20) goes callees first through the call graph and takes non-leaf callees, callees with one call site, and always_inline ones.
A call callRes, globalF, Args to a function F of the module is replaced by F's blocks when F is eligible and so is the caller. The calling block is split at the call: its first part copies the arguments into F's renamed parameters and jumps to F's renamed entry; each retV of F jumps to a join block, whose phi takes V, and the join block holds the rest of the calling block and its jump. F's blocks are placed right after the first part, so edges into and out of the body are forward and pizlonation, which polls by block order, polls exactly the cycles it polled before. Every allocation stays where it was, a fresh object at each execution; promotion takes the ones that do not escape (promote.pl promotes in any block).
Eligibility
| Callee F | Why |
|---|---|
local linkage | an exported definition can be interposed |
| no call to a function of the module (a leaf) | no recursion; two rounds give depth 2 |
no va_args, no setjmp, no tuple return | its own entry's argument snapshot, returns twice, two words |
a ret, strict SSA | the join needs a predecessor; promotion needs strict SSA |
| every alloc of constant size at most 256, promotable or escaping (filc), promotable (plain) | a local one that could not promote would become a heap object per call; a plain stack alloc would outlive the call |
| at most 120 instructions and jumps | size |
| Caller | Why |
|---|---|
| no setjmp | reference selection, temporaries live across returns-twice |
| in no cycle of direct calls | recursion depth before stack overflow is unchanged |
| at most 2000 instructions, growing by at most half its size or 120, whichever is more | frame size and compile time |
Wide
Each function, callees first, takes its admitted calls; then, with simplified callees, it is promoted, copy-propagated and simplified, and that body is what its callers inline (so depth is unbounded and sizes are the prepared ones). A callee is local, on no cycle of direct calls, not noinline, and inlinable/3 (as small, but calls of the module's functions, tuple returns and constant allocs of any size are fine). Its class decides admitted/5:
| Class | Admitted into |
|---|---|
always_inline (c_lower c_module/3) | any caller on no cycle and without setjmp, up to 4000 instructions |
single: one direct call site, no other reference | a caller of at most 2000 instructions before inlining that stays within 2000, up to 500 |
plain | as small: at most 120, within the caller's budget and the 2000 cap |
Afterwards a local function that no exported or weak function, data object or alias reaches is dropped, with its context: nothing can observe it, and a single-site callee's body would otherwise be emitted twice.
Function objects, getters and entries of inlined functions stay while anything refers to them, so their addresses are unchanged. Names are fresh in the caller: iR_N.X for round R and instance N, with N raised past any collision. Source contexts follow: callee records are renamed (origin and binding identities wrapped as inlR, N, Id), and the split block's sites are re-indexed.
M is M0 with two rounds of inlining of eligible calls. With Callees simplified, the functions that may be callees of the second round are first promoted, copy-propagated and simplified (prepared/4), as the pipeline does later, so their size and body are what they become. With Callees widePrep, Attributes, M is M0 with wide inlining (the header's Wide), Prep plain or simplified as above.
Wide inlining (--inline=wide)
inline_module(wide(Prep, Attributes), M0, M): each function, callees before callers, takes its admitted calls (admitted/5), and the result, prepared as prepared/3 prepares callees when Prep is simplified, is what its own callers inline. Functions on a cycle of direct calls take none and give none. Attributes are Sym-A pairs, A always_inline or noinline (c_lower c_module/3). Local functions that nothing refers to afterwards leave the module.
module_mode/2):wide_function/4, and release_stacks/0 after every 256th function: SWI's limit counts what is allocated, and one pass over SQLite's 3,000 functions otherwise leaves the garbage of all of them (sqlite3.c peaked 1.4 GB higher).
Name's calls inlined, its result in Out, and in Callees when it can be a callee: local, on no cycle, called, not noinline. Its class is always_inline, single (one call site and no other reference) or plain.
a function of Size before preparation may be admitted as a callee of Class once prepared. Preparation shrinks a body (its parameters' and locals' allocs, loads and stores go), so the limits are four times the admitted sizes, as for small's second round.
Cs lists the module's functions that Bs call directly, once per call.
Sites maps each function called directly to its number of call sites.
Others holds every symbol that Items refer to other than as the callee of a direct call: an operand global(S), a data item's sym(S, _), an alias's target.
Item refers to symbol S; with Calls operand, not counting a direct call's callee.
Items0 less the local functions, with their contexts, that no exported or weak function, data object or alias refers to, directly or through other functions.
Order holds each of Names after every function it reaches in Graph (name to callees), except along a cycle.
difference list Order0 gains, after what is already there, N's unseen callees' visits, then N.
with simplified, M is M0 with each function that could become a callee (local, no call to a function of the module, at most four callee limits) promoted, copy-propagated and simplified. Others are unchanged.
release_stacks: as main.pl's, collect the first round's and the preparation's garbage and return the stack memory before the second round (preparing SQLite's callees left 1.1 GB allocated, 200 MB live). SWI's limit counts what is allocated: without it, sqlite3.c overflows 1 GB with 200 MB live, and peaks 0.7 GB above --inline=none under the 4 GB limit its builds use.
Sizes holds each function's size before the first round: both caps on a caller are on that size, so the second round cannot reset them.
Set is an assoc with key each of Names, for lookups in SQLite's 3,000 functions and its large callers' names.
Eligibility
F's body can replace a call of it, whatever its size and its calls: local, no setjmp, a return, no va_args, constant allocs of at most Max bytes (any, with Max any) that promote or escape (allocs_ok/2), strict SSA. Small inlining takes 256 and also refuses a tuple return. Wide takes any size: an alloc that escapes is a heap object per execution inlined or not, and allocs_ok/2 refuses a local one that would not promote.
In filc mode every alloc either promotes or escapes, to a heap object per execution as before. In plain mode every alloc promotes: a stack alloc that stayed would live until the caller returns.
the ordset of functions on a cycle of direct calls between functions of the module. Functions that reach no cycle or that no cycle reaches are peeled off first; each remaining one is on a cycle if it reaches itself among them.
Core is Graph less, repeatedly, the nodes with no edge to a remaining node.
The transformation
F is F0 with its eligible calls inlined, as admitted/5 admits each under Policy. A callee that the budget counts (all of them under small) is admitted while F stays within its original size Orig plus half of Orig, or plus one callee limit for a small caller. Splits and callee records are collected as the blocks are walked and applied to the caller's records once at the end: SQLite's largest functions inline hundreds of calls over tens of thousands of records.
a callee of Class and Size may be inlined under Policy with Budget0 left, which leaves Budget. Under small every callee counts against the budget. Under wide(Orig), for a caller of original size Orig, an always_inline callee is admitted whatever the caller (up to a size that only guards against pathological headers), a callee called from one site only (its body then leaves the module) into a caller within the caller limit while the caller stays within grown_limit/1, and any other one as small would admit it.
small counts the budget; wide also the caller's current size, which single callees may grow to grown_limit/1.
Moves pairs each split block's label with the label of its last piece, which its successors' phis must now name. Used holds the caller's names before this round; the round's own names cannot collide with each other, since iR_N. determines N.
Block with its first eligible call inlined, and the rest of it recursively; Last is the label of the last piece. St collects each split as L-split(NPre, NCopies, Join) and each instance's records.
P is iR_N. for the first N from N0 at which no renamed callee name is in Used, and Join is P before the first of join, join_, ... that is neither a callee name nor, with P, in Used.
the callee's blocks and parameters with P before every temp and label, each return a jump to Join, Rets the join phi's arguments.
Source contexts
the caller's records for R after every split. A split of block L at a call with NPre instructions before it keeps the sites before the call, gives the call's origins to each of the NC parameter copies, and moves the rest to Join, shifted, where a later split of Join applies in turn. A split block's jump site moves to its last piece. (The callees' records name no split block.)
the callee's records renamed into the caller: temps and labels prefixed with P, origin and binding identities wrapped as inl(Round, N, Id). A return's jump site stays at its block, whose jump is now the goto to the join.