Lesson 20.4 — Specialization and outlining: cloning, partial inlining, the outliners and hot/cold splitting¶

Techniques: procedure cloning (Cooper, Hall & Kennedy 1993) and LLVM's FunctionSpecialization inside IPSCCP; partial inlining (LLVM's PartialInliner, GCC's ipa-split); outlining — procedural abstraction by suffix trees (Fraser, Myers & Wendt 1984; LLVM's MachineOutliner), the IR outliner (IROutliner) and hot/cold splitting (HotColdSplitting) · Pebble implements: none of these (theory, drills-free quiz computations and real-world boxes); they are the "other half" of the inlining trade-off of Lesson 20.3 · Prerequisites: Lesson 20.3; SCCP (Ch 17); dominators and single-entry regions (Ch 15) · Time: 5–7 hours

Inlining copies a whole callee into one call site. The techniques of this lesson move code in finer-grained ways. Cloning makes a copy of a callee specialized for a class of call sites, without merging it into any caller. Partial inlining inlines only the part of a callee its callers need often. Outlining does the opposite of inlining — it turns repeated or cold code into a new function — to save size or improve locality. The three running examples are small: spec.c for specialization,

static int plus(int a, int b) { return a + b; }
static int times(int a, int b) { return a * b; }
static int fold(int (*op)(int, int), const int *v, int n, int init) {
  int acc = init;
  for (int i = 0; i < n; i++)
    acc = op(acc, v[i]);
  return acc;
}
int sum(const int *v, int n) { return fold(plus, v, n, 0); }
int product(const int *v, int n) { return fold(times, v, n, 1); }

a cached getter get (fast path: one load and a branch; slow path: a computation and a printf) for partial inlining, and three functions with a common tail for outlining (§3).

1. Problem and motivation¶

Cloning and function specialization¶

Interprocedural constant propagation (Lesson 20.5) merges the facts of all call sites: if fold is called with plus at one site and times at another, its parameter op is not a constant and the indirect call stays indirect. Cooper, Hall and Kennedy proposed procedure cloning: partition the call sites by the facts they provide and give each class its own copy of the procedure, so that propagation within each copy is precise; they bounded the code growth by merging classes whose facts do not matter [CHK93]. LLVM's FunctionSpecialization (a part of ipsccp<func-spec>; the -O2/-O3 pipelines enable it except in the ThinLTO/LTO pre-link step, and full LTO enables it) clones a function for call sites that pass constants — particularly function pointers and constant data — when its cost model predicts that the clone will simplify enough [LLVM-FuncSpec]. GCC's ipa-cp does the same (clones named .constprop.N) [GCC-IPACP].

Partial inlining¶

A function that is mostly an early exit — "if cached, return the cached value; otherwise compute" — is too big to inline because of its slow path, although every call would profit from inlining the first two instructions. Partial inlining splits the function: the rarely executed region is outlined into a new function, and the now-small remainder (the fast path plus a call to the outlined part) is inlined. LLVM's PartialInliner recognizes the early-return shape (optionally guided by profiles) [LLVM-PartialInliner]; GCC's ipa-split (fnsplit) splits a function into a header and a .part function at a split point chosen by estimated time and size, then lets the regular inliner inline the header [GCC-Split].

Outlining and hot/cold splitting¶

Outlining (procedural abstraction) finds instruction sequences that occur several times and replaces each by a call to one shared function. Fraser, Myers and Wendt did it on assembly code with a suffix tree [FMW84]; LLVM's MachineOutliner does it on machine instructions after register allocation (on by default at -Oz for AArch64 and RISC-V, available on x86) [LLVM-MachineOutliner]; the IROutliner does it on LLVM IR with a similarity analysis that tolerates different constants and operand names [LLVM-IROutliner]. Hot/cold splitting outlines code that is cold — never executed according to a profile, or leading only to unreachable, noreturn or cold calls — so that the hot code is denser in the instruction cache [LLVM-HotCold]; it is the static, per-function version of the layout optimizations that BOLT does after linking (Lesson 20.10), and descends from Pettis and Hansen's procedure splitting [PH90].

2. Definitions and algorithms¶

Definition 20.4.1 (Call-site facts, specialization, clone)

For a function \(g\) with parameters \(p_1, \dots, p_k\) and a call site \(c\), the facts of \(c\) are the partial map \(\varphi_c : \{p_i\} \rightharpoonup \mathit{Const}\) of parameters whose actual argument at \(c\) is a constant (a number, a global's address, a function). A specialization of \(g\) for a map \(\varphi\) is a copy \(g_\varphi\) in which every use of \(p_i \in \mathrm{dom}(\varphi)\) is replaced by \(\varphi(p_i)\); a call site \(c\) may be redirected to \(g_\varphi\) iff \(\varphi \subseteq \varphi_c\) (every assumed constant is actually passed).

Algorithm 20.4.2 (Function specialization, in the style of LLVM's FunctionSpecializer)

Input: a module after an IPSCCP solve (lattice values for arguments and call sites).
Output: clones \(g_\varphi\) and redirected call sites; IPSCCP is re-run on the clones.
Precondition: \(g\) is internal or its original is kept for unknown callers; \(g\) is not noinline/optnone.
Postcondition: every redirected call site \(c\) satisfies \(\varphi \subseteq \varphi_c\) (Theorem 20.4.4); the number of clones per function is bounded (funcspec-max-clones, 3 by default).
Invariant: the set of candidates only shrinks; each chosen specialization's estimated score exceeds its estimated code-size cost.

function Specialize(M):
    repeat up to MaxIterations times:
        candidates ← []
        for each function g (internal, not too small, not too large):
            for each call site c of g with constant arguments φ_c:
                bonus ← EstimateSimplification(g, φ_c)       # instructions that fold, branches that die,
                                                              # indirect calls that become direct (inlining bonus)
                if bonus.score ≥ MinScore × size(g): candidates.append((g, φ_c, bonus))
        if candidates = []: stop
        keep the best candidates per function (up to MaxClones), merging equal φ's
        for (g, φ, _) in kept:
            g_φ ← clone(g) with p_i := φ(p_i)
            redirect every call site c with φ ⊆ φ_c to g_φ
            mark g_φ's arguments as the constants φ in the SCCP solver
        re-run the IPSCCP solver; delete g if it is internal and has no calls left

Definition 20.4.3 (Single-entry region, extraction)

A set \(R\) of blocks of \(f\) is a single-entry region if it has one block \(h \in R\) (the entry) that dominates every block of \(R\) and every edge into \(R\) from outside goes to \(h\). Its inputs are the values defined outside \(R\) and used in \(R\); its outputs are the values defined in \(R\) and used outside it; its exits are the edges leaving \(R\). Extracting \(R\) creates a function \(f_R\) whose parameters are the inputs (plus a pointer per output), whose body is \(R\) with each exit replaced by a return of an exit number, and replaces \(R\) in \(f\) by one block that calls \(f_R\) and switches on the returned exit number (LLVM's CodeExtractor).

Theorem 20.4.4 (Specialization and extraction preserve semantics)

(a) Redirecting a call site \(c\) to \(g_\varphi\) with \(\varphi \subseteq \varphi_c\) preserves the program's behavior. (b) Extracting a single-entry region \(R\) that contains no alloca whose address escapes \(R\), no return, no exception pad entered from outside \(R\), and no instruction that depends on the identity of the frame (returnaddress, va_start, returns_twice calls) preserves the behavior of \(f\).

Proof

(a) In every execution of the call \(c\), parameter \(p_i \in \mathrm{dom}(\varphi)\) receives the argument of \(c\), which is the constant \(\varphi_c(p_i) = \varphi(p_i)\). So in \(g\)'s activation every use of \(p_i\) reads \(\varphi(p_i)\), and \(g_\varphi\) — which is \(g\) with those uses replaced by that constant — performs the same instructions on the same values, step by step.

(b) A single entry means every execution enters \(R\) at \(h\), with the inputs defined (they dominate their uses in \(R\), by SSA's dominance property, and are defined outside \(R\), hence before \(h\)). The call to \(f_R\) passes exactly those values; inside \(f_R\) each instruction of \(R\) computes the same values; stores through output pointers deliver the outputs, and the returned exit number selects the successor \(f\) would have branched to. The excluded features are exactly those whose meaning depends on which frame executes: an escaping alloca would die when \(f_R\) returns, a return of \(f\) cannot be executed from \(f_R\), an EH pad entered from outside breaks single entry for the unwind edge, and the frame-identity intrinsics observe the new call.

Algorithm 20.4.5 (Partial inlining of an early-return function)

Input: a function \(g\) whose entry ends in br cond, RET, REST where RET reaches the return without side effects, and its call sites.
Output: an outlined \(g_{\mathrm{slow}}\) (the region dominated by REST), and at every call site an inlined copy of the fast path with a call to \(g_{\mathrm{slow}}\).
Precondition: the region is extractable (Theorem 20.4.4 (b)); the cost model (or a profile) says the entry path is the likely one.
Postcondition: each call site executes the fast path inline, and the slow path out of line; semantics preserved.
Invariant: the original \(g\) is kept until all its call sites are rewritten (then deleted if internal).

function PartialInline(g):
    (entry, RET, REST) ← match the early-return shape of g, or give up
    R ← blocks dominated by REST (up to the return block)
    g' ← clone(g);  g_slow ← Extract(R from g')                  # g' = entry + call g_slow + return
    for each call site c of g:
        if InlineCost(c, g') < threshold: InlineFunction(c, g')   # only the small g' is inlined
    if g is internal and unused: delete g

Definition 20.4.6 (Repeated sequences, outlining benefit)

Map every instruction of the program to a symbol (equal symbols for instructions that are interchangeable: same opcode, same operands after register allocation for the MachineOutliner; same opcode and operand structure for the IROutliner), with a unique symbol at every point outlining must not cross (a call's return address dependence, a stack adjustment, a basic block boundary for the simple version). A candidate is a string \(w\) of length \(\ell \ge 2\) occurring at least \(k \ge 2\) times without overlap. With a per-call cost \(\kappa_c\) (the call instruction, extra saves) and a per-function cost \(\kappa_f\) (the return, alignment), its benefit is \(b(w) = k \ell - (k \kappa_c + \ell + \kappa_f)\) instructions: \(k\) copies of length \(\ell\) become \(k\) calls and one function body.

Algorithm 20.4.7 (Suffix-tree outlining, as in the MachineOutliner)

Input: the program as one string \(s\) over the symbols of Definition 20.4.6 (all functions concatenated, separated by unique symbols).
Output: outlined functions and the call sites that replace each chosen occurrence.
Precondition: the target can call and return without disturbing the live registers of each occurrence (the outliner checks liveness and picks a call variant: call + ret, a tail call, or saving the link register).
Postcondition: no two chosen occurrences overlap; every chosen candidate had \(b(w) > 0\) when chosen.
Invariant: the occurrences removed so far are disjoint; remaining candidates' counts refer only to occurrences not yet removed.

function Outline(s):
    T ← SuffixTree(s)                                   # O(|s|) (Ukkonen)
    C ← []
    for each internal node v of T with string depth ℓ ≥ 2 and ≥ 2 leaves:
        occ ← the start positions of the leaves below v            # repeated occurrences of w = label(v)
        C.append((w, occ))
    sort C by benefit b(w), largest first                       # Definition 20.4.6, with the target's costs
    for (w, occ) in C:
        occ' ← the occurrences of w that do not overlap an already outlined one
        if b(w) with k = |occ'| > 0:
            create OUTLINED_FUNCTION_i with body w (+ ret, or as a tail-call target)
            replace each occurrence in occ' by a call

Algorithm 20.4.8 (Hot/cold splitting)

Input: a function \(f\); block temperatures (profile counts, or static coldness: blocks that only reach unreachable, a cold call, or a noreturn call).
Output: \(f\) with maximal cold single-entry regions extracted into f.cold.N functions marked cold.
Precondition: the regions are extractable (Theorem 20.4.4 (b)).
Postcondition: every extracted block was cold; every region's estimated benefit (size removed from \(f\) minus the call overhead) exceeds -hotcoldsplit-threshold.
Invariant: a block is marked cold only if every path from it leads to cold code or back to cold code (backward propagation over the CFG).

function HotColdSplit(f):
    cold ← blocks that are statically cold or have profile count 0
    propagate: a block all of whose successors are cold is cold (to a fixed point, over the post-dominator tree)
    for each cold block b, in RPO, not yet in a region:
        R ← the largest single-entry region with entry b made of cold blocks   # grow over the dominator tree
        if Benefit(R) > threshold and Extractable(R): Extract(R) as f.cold.N (attributes: cold, minsize)

3. Worked example¶

Cloning and function specialization¶

fold has two call sites, \(\varphi_{\mathtt{sum}} = \{op \mapsto \mathtt{plus}, init \mapsto 0\}\) and \(\varphi_{\mathtt{product}} = \{op \mapsto \mathtt{times}, init \mapsto 1\}\). Before specialization IPSCCP joins them: \(op = \top\), \(init = \top\), and the loop's op(acc, v[i]) is an indirect call. Algorithm 20.4.2 estimates, for each site, the simplification a constant op enables: the indirect call becomes a direct call to a small function (an inlining bonus), and init folds into the loop phi. Both candidates pass, so two clones are made:

step	candidates	clone	redirected site	after re-running IPSCCP in the clone
1	(fold, sum site), (fold, product site)	—	—	—
2	keep both (max 3 clones)	`fold.specialized.2` for	`sum`	loop phi starts at 0; `call i32 @plus(...)` direct
3		`fold.specialized.1` for	`product`	loop phi starts at 1; `call i32 @times(...)` direct
4	none left	the original `fold` has no calls: deleted

The clones still pass @plus/@times as the first argument (arguments are not removed; dead-argument elimination, Lesson 20.6, would do that), but inside each clone the call is direct — ready for the inliner.

Partial inlining¶

get has entry: %ok = load @cache_ok; br %ok, %return, %slow. Algorithm 20.4.5: the early-return shape matches with RET = return, REST = slow; \(R = \{\mathtt{slow}\}\) (the return block is shared and stays). Inputs of \(R\): %x; outputs: none (the slow path stores to globals); exits: one (to return). Extraction creates get.1.slow(i32 %x), and the remainder entry + codeRepl + return (one load, one branch, one call, one load, ret) is small enough to inline at both callers a and b. Every call of get now costs a load and a well-predicted branch on the fast path.

Outlining and hot/cold splitting¶

Suffix-tree outlining on the symbol string of three functions that share a tail (AArch64 after register allocation; each letter is one instruction, # unique separators):

f1 = X1 A B C D E F G H, f2 = X2 A B C D E F G H, f3 = X3 A B C D E F G H, so \(s\) = X1 ABCDEFGH r # X2 ABCDEFGH r # X3 ABCDEFGH r # with r the return.

candidate \(w\)	\(\ell\)	\(k\)	\(b(w)\) with \(\kappa_c = 1\), \(\kappa_f = 0\) (tail call: the copy's `r` is dropped)
`ABCDEFGH r`	9	3	\(27 - (3 + 9 + 0) = 15\)
`ABCDEFGH`	8	3	\(24 - (3 + 8 + 1) = 12\) (needs its own `ret`: \(\kappa_f = 1\))
`CDEFGH r`	7	3	\(21 - (3 + 7) = 11\), but overlaps the first

The best candidate, ABCDEFGH r, is outlined as a tail-call target: each function keeps its own first instruction and ends with b OUTLINED_FUNCTION_0 — exactly what llc produces for the three functions of §7, where the shared tail is 18 instructions (8 of them adrp/ldr address computations).

Hot/cold splitting on checked_div (§7): the block if.then calls report, declared cold, so it is statically cold; its successor return is shared with the hot path, so the region is \(\{\mathtt{if.then}\}\) with input %a, no outputs, one exit. Extracting it gives checked_div.cold.1(i32 %a) and leaves in checked_div only the compare, the branch, the division and a call.

4. Invariants and correctness¶

Theorem 20.4.4 covers the semantics of the three families. Two further facts justify their use.

Proposition 20.4.9 (Specialization never loses constants)

Let \(V\) be the IPSCCP solution of a program and \(V'\) the solution after redirecting some call sites to clones. For every value \(v\) of the original function \(g\) and its copy \(v_\varphi\) in a clone, \(V'(v_\varphi) \sqsubseteq V(v)\) in the constant lattice (the clone knows at least as much), and \(V'\) equals \(V\) on functions that were not cloned and do not call a clone.

Proof

IPSCCP computes the least solution of monotone equations where a parameter's value is the join of its arguments over the (executable) call sites. The clone \(g_\varphi\) has a subset of \(g\)'s call sites, so each parameter's join is over fewer arguments and is \(\sqsubseteq\) the original; for \(p_i \in \mathrm{dom}(\varphi)\) it is the constant. The equations inside \(g_\varphi\) are those of \(g\) with smaller inputs; by monotonicity their least solution is smaller. Functions that neither were cloned nor call a clone have unchanged equations. (The original \(g\) may gain precision too: its remaining call sites are fewer.)

Proposition 20.4.10 (Suffix trees find every repeated substring)

In the suffix tree of \(s\), a string \(w\) occurs at least twice in \(s\) iff \(w\) is a prefix of the label of some internal node; the occurrences of \(w\) are the leaves below the highest such node. Hence Algorithm 20.4.7's candidate list contains every repeated substring that is maximal in the sense of ending at a branching point.

Proof sketch (full proof: [Gus97, Ch. 7])

A suffix tree has one leaf per suffix and branches exactly where two suffixes first differ. If \(w\) occurs at positions \(i \neq j\), the suffixes starting at \(i\) and \(j\) share the prefix \(w\), so the path spelling \(w\) is shared by two leaves and ends at or inside an edge above an internal node. Conversely an internal node with label \(u\) has at least two leaves, whose suffixes start with \(u\): two occurrences. Overlapping occurrences are removed afterwards, which is why the algorithm recounts \(k\) before outlining.

Outlining costs speed

Every outlined occurrence becomes a call (and, if the link register is live, a save and a restore). The MachineOutliner is therefore enabled by default only for minimum size (-Oz on AArch64/RISC-V), and hot/cold splitting only moves code the profile (or a cold/noreturn call) says is cold. Outlining a sequence inside a hot loop adds a call and a return to every iteration to save a few bytes.

5. Complexity¶

\(n\) = instructions, \(s\) = call sites of the function, \(c\) = clones, \(\lvert g \rvert\) = size of the specialized function.

Technique	Time (worst)	Time (typical)	Space	Justification
Function specialization	\(O(s \cdot \lvert g \rvert)\) bonus estimation + \(c\) IPSCCP re-solves	bounded by clone and iteration limits	\(c \cdot \lvert g \rvert\) code growth	each site's estimate walks \(g\) once; each clone adds \(\lvert g \rvert\)
Partial inlining	\(O(\lvert g \rvert)\) per function + inlining cost	cheap, pattern-driven	one outlined function per candidate	extraction is linear in the region (inputs/outputs by a def-use scan)
Suffix-tree outlining	\(O(n)\) tree + \(O(n \log n)\) sorting candidates	a few percent of `llc` time at `-Oz`	\(O(n)\) tree	Ukkonen's construction is linear for a constant alphabet; hashing instructions gives integer symbols
Hot/cold splitting	\(O(n)\) per function (propagation + regions)	linear	one function per region	dominator tree + one backward propagation

Pathological family (cloning). A function \(g(p_1, \dots, p_m)\) with \(2^m\) call sites passing every combination of constants \(\{0, 1\}^m\): unrestricted cloning creates \(2^m\) copies. Cooper, Hall and Kennedy merge call sites whose facts lead to the same simplifications [CHK93]; LLVM caps clones per function (3) and requires a minimum score per unit of size.

At scale. On the three three-function example of §7, the MachineOutliner replaces 3 × 18 shared instructions by one 18-instruction function and three branches: 54 → 21 instructions for the shared part.

Specialization on constant data (LLVM -funcspec-for-literal-constant, on by default, and -funcspec-on-address, off): cloning for literal constants and for constant globals passed by address — broader coverage, riskier growth.
Goal-directed cloning [CHK93]: clone only when a later optimization (vectorization, a folded branch) is known to need the fact.
GCC ipa-cp with known aggregate contents and bits [GCC-IPACP]: also propagates constant fields of structures passed by reference.
Profile-guided partial inlining (-partial-inlining-extra-penalty, BFI-driven region choice): outline regions that the profile says are cold rather than only early-return shapes.
Function merging (LLVM mergefunc, and the "function merging by sequence alignment" line of work): merge whole similar functions into one with a selector argument — the function-level cousin of outlining.
Repeated outlining (-machine-outliner-reruns): outlining the outlined functions again finds nested repeats, for a little more size.

7. In real compilers¶

Cloning and function specialization¶

LLVM: llvm/lib/Transforms/IPO/FunctionSpecialization.cpp — FunctionSpecializer::run, findSpecializations and the bonus estimation (InstCostVisitor::getCodeSizeSavingsForArg for folded instructions, FunctionSpecializer::getInliningBonus for calls that become direct), run from runIPSCCP in llvm/lib/Transforms/IPO/SCCP.cpp [LLVM-FuncSpec, LLVM-IPSCCP]. GCC: gcc/ipa-cp.cc — decide_about_value and create_specialized_node [GCC-IPACP].

LLVM specializes fold for both function pointers

Reproduce (clang 23.1.2, opt 23.1.2; spec.c as in the introduction):

clang-23 -O1 -Xclang -disable-llvm-passes -fno-discard-value-names -S -emit-llvm spec.c -o - | opt -passes=sroa -S -o spec.ll
opt -passes='ipsccp<func-spec>' -funcspec-min-function-size=1 -S spec.ll -o spec.out.ll
grep -E '^define|call i32' spec.out.ll

Output:

define dso_local i32 @sum(ptr noundef %v, i32 noundef %n) #0 {
  %call = call i32 @fold.specialized.2(ptr noundef @plus, ptr noundef %v, i32 noundef %n, i32 noundef 0)
define internal i32 @plus(i32 noundef %a, i32 noundef %b) #0 {
define dso_local i32 @product(ptr noundef %v, i32 noundef %n) #0 {
  %call = call i32 @fold.specialized.1(ptr noundef @times, ptr noundef %v, i32 noundef %n, i32 noundef 1)
define internal i32 @times(i32 noundef %a, i32 noundef %b) #0 {
define internal i32 @fold.specialized.1(ptr noundef %op, ptr noundef %v, i32 noundef %n, i32 noundef %init) #0 {
  %call = call i32 @times(i32 noundef %acc.0, i32 noundef %0)
define internal i32 @fold.specialized.2(ptr noundef %op, ptr noundef %v, i32 noundef %n, i32 noundef %init) #0 {
  %call = call i32 @plus(i32 noundef %acc.0, i32 noundef %0)

What to notice: two clones, one per call-site class; inside each, the indirect op(...) became a direct call (which the inliner can now take), and the original fold is gone. -funcspec-min-function-size=1 lowers the minimum function size so that this tiny example qualifies (the default, 500 instructions, leaves small functions to the inliner).

Partial inlining¶

LLVM: llvm/lib/Transforms/IPO/PartialInlining.cpp — PartialInlinerImpl::tryPartialInline, with computeOutliningInfo recognizing the early-return shape [LLVM-PartialInliner]. GCC: gcc/ipa-split.cc — find_split_points and split_function create .part functions [GCC-Split] (the GCC box of Lesson 20.3 shows big.part.0).

LLVM partially inlines a cached getter

Reproduce (opt 23.1.2):

cat > pi.ll <<'EOF'
@cache_ok = internal global i1 false
@cached = internal global i32 0
@.str = private constant [13 x i8] c"computed %d\0A\00"
declare i32 @printf(ptr, ...)
define internal i32 @get(i32 %x) {
entry:
  %ok = load i1, ptr @cache_ok
  br i1 %ok, label %return, label %slow
slow:
  %sq = mul i32 %x, %x
  %s = add i32 %sq, 17
  call i32 (ptr, ...) @printf(ptr @.str, i32 %s)
  store i32 %s, ptr @cached
  store i1 true, ptr @cache_ok
  br label %return
return:
  %c = load i32, ptr @cached
  ret i32 %c
}
define i32 @a(i32 %x) {
  %r = call i32 @get(i32 %x)
  %s = add i32 %r, 1
  ret i32 %s
}
define i32 @b(i32 %x) {
  %r = call i32 @get(i32 %x)
  %s = mul i32 %r, 2
  ret i32 %s
}
EOF
opt -passes=partial-inliner -skip-partial-inlining-cost-analysis -pass-remarks=partial-inlining -S pi.ll -o pi.out.ll
sed -n '/define i32 @a/,/^}/p;/define internal void @get.1.slow/,/^}/p' pi.out.ll

Output:

remark: <unknown>:0:0: get partially inlined into a
remark: <unknown>:0:0: get partially inlined into b
remark: <unknown>:0:0: Partially inlined into at least one caller
define i32 @a(i32 %x) {
  %ok.i = load i1, ptr @cache_ok, align 1
  br i1 %ok.i, label %get.1.exit, label %codeRepl.i

codeRepl.i:                                       ; preds = %0
  call void @get.1.slow(i32 %x), !inline_history !0
  br label %get.1.exit

get.1.exit:                                       ; preds = %0, %codeRepl.i
  %c.i = load i32, ptr @cached, align 4
  %s = add i32 %c.i, 1
  ret i32 %s
}
define internal void @get.1.slow(i32 %x) {
newFuncRoot:
  br label %slow

slow:                                             ; preds = %newFuncRoot
  %sq = mul i32 %x, %x
  %s = add i32 %sq, 17
  %0 = call i32 (ptr, ...) @printf(ptr @.str, i32 %s)
  store i32 %s, ptr @cached, align 4
  store i1 true, ptr @cache_ok, align 1
  br label %return.exitStub

return.exitStub:                                  ; preds = %slow
  ret void
}

What to notice: Algorithm 20.4.5 step by step: the region {slow} became get.1.slow with the input %x as its parameter and a single exit (returning void, no outputs), and the fast path — one load and a branch — is inlined into a (and b). Without -skip-partial-inlining-cost-analysis the pass needs a profile or a larger outlined region to find the transformation profitable.

Outlining and hot/cold splitting¶

LLVM: llvm/lib/CodeGen/MachineOutliner.cpp — MachineOutliner::findCandidates walks a SuffixTree over hashed instructions, the target hooks (getOutliningCandidateInfo) price each call variant [LLVM-MachineOutliner]; llvm/lib/Transforms/IPO/IROutliner.cpp — IROutliner::doOutline uses IRSimilarityIdentifier [LLVM-IROutliner]; llvm/lib/Transforms/IPO/HotColdSplitting.cpp — HotColdSplitting::outlineColdRegions [LLVM-HotCold].

The MachineOutliner shares a common tail (AArch64, -Oz)

Reproduce (clang 23.1.2):

cat > mo.c <<'EOF'
extern int g1, g2, g3, g4;
void f1(int x) { g1 = x * 3 + 7; g2 = g1 ^ 0x55; g3 = g2 + g1; g4 = g3 - 9; }
void f2(int x) { g1 = x * 5 + 7; g2 = g1 ^ 0x55; g3 = g2 + g1; g4 = g3 - 9; }
void f3(int x) { g1 = x * 9 + 7; g2 = g1 ^ 0x55; g3 = g2 + g1; g4 = g3 - 9; }
EOF
clang-23 --target=aarch64-linux-gnu -Oz -S mo.c -o - -mllvm -enable-machine-outliner | grep -vE '^\s*\.(cfi|p2align|type|size|file|ident|section|text|addrsig|globl)'

Output:

f1:                                     // @f1
// %bb.0:
    add w8, w0, w0, lsl #1
    b   OUTLINED_FUNCTION_0
.Lfunc_end0:
                                        // -- End function
f2:                                     // @f2
// %bb.0:
    add w8, w0, w0, lsl #2
    b   OUTLINED_FUNCTION_0
.Lfunc_end1:
                                        // -- End function
f3:                                     // @f3
// %bb.0:
    add w8, w0, w0, lsl #3
    b   OUTLINED_FUNCTION_0
.Lfunc_end2:
                                        // -- End function
OUTLINED_FUNCTION_0:                    // @OUTLINED_FUNCTION_0 Tail Call
// %bb.0:
    adrp    x9, :got:g1
    adrp    x11, :got:g2
    ldr x9, [x9, :got_lo12:g1]
    mov w10, #85                        // =0x55
    ldr x11, [x11, :got_lo12:g2]
    add w8, w8, #7
    str w8, [x9]
    eor w9, w8, w10
    adrp    x10, :got:g3
    ldr x10, [x10, :got_lo12:g3]
    str w9, [x11]
    add w8, w9, w8
    adrp    x9, :got:g4
    ldr x9, [x9, :got_lo12:g4]
    str w8, [x10]
    sub w8, w8, #9
    str w8, [x9]
    ret
.Lfunc_end3:
                                        // -- End function

What to notice: the §3 table's best candidate — the whole common tail including ret — outlined as a tail call (b, no link-register save): \(\kappa_c = 1\), \(\kappa_f = 0\). The differing multiply (lsl #1/#2/#3) stays in each function; everything after it matched after register allocation.

Hot/cold splitting of an error path

Reproduce (clang 23.1.2, opt 23.1.2):

cat > hc.c <<'EOF'
int printf(const char *, ...);
__attribute__((cold)) void report(const char *what, int v);
int checked_div(int a, int b) {
  if (b == 0) {
    printf("division of %d by zero\n", a);
    report("div", a);
    return 0;
  }
  return a / b;
}
EOF
clang-23 -O1 -Xclang -disable-llvm-passes -fno-discard-value-names -S -emit-llvm hc.c -o - | opt -passes=sroa,simplifycfg -S -o hc.ll
opt -passes=hotcoldsplit -hotcoldsplit-threshold=0 -pass-remarks=hotcoldsplit -S hc.ll -o hc.out.ll
sed -n '/^define dso_local i32 @checked_div/,/^}/p' hc.out.ll

Output:

remark: <unknown>:0:0: checked_div split cold code into checked_div.cold.1
define dso_local i32 @checked_div(i32 noundef %a, i32 noundef %b) #0 {
entry:
  %cmp = icmp eq i32 %b, 0
  br i1 %cmp, label %codeRepl, label %if.end

codeRepl:                                         ; preds = %entry
  call void @checked_div.cold.1(i32 %a) #4
  br label %return

if.end:                                           ; preds = %entry
  %div = sdiv i32 %a, %b
  br label %return

return:                                           ; preds = %codeRepl, %if.end
  %retval.0 = phi i32 [ 0, %codeRepl ], [ %div, %if.end ]
  ret i32 %retval.0
}

What to notice: the call to the cold function made if.then statically cold; the region {if.then} (input %a, no outputs) was extracted into checked_div.cold.1, which the code generator can place far from the hot code. -hotcoldsplit-threshold=0 accepts regions this small; the default threshold (2) wants a little more code to move.

Find where LLVM does it. Open llvm/lib/Transforms/IPO/FunctionSpecialization.cpp and find the member function of FunctionSpecializer that decides, for one function, which call sites to specialize for and with which score. What is its name? (Quiz llvm-where-funcspec.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Cloning / function specialization	Per-call-site-class constants without inlining; turns indirect calls direct	estimation \(O(s \lvert g \rvert)\) + re-solves · bounded clones	Clones named `.specialized.N` / `.constprop.N`	Medium (on top of IPSCCP)	LLVM `ipsccp<func-spec>` (-O3, LTO), GCC `ipa-cp`
Partial inlining	Inlines the hot entry path only	\(O(\lvert g \rvert)\) · cheap	`.1.slow` / `.part.N` functions	Medium (code extraction)	LLVM `partial-inliner`, GCC `fnsplit`
Outlining / hot/cold splitting	Size: shares repeats (MachineOutliner, IROutliner); locality: moves cold code (HotColdSplitting)	\(O(n)\) suffix tree / linear regions	`OUTLINED_FUNCTION_N`, `.cold.N`	High (liveness and call variants per target) / medium	`-Oz` on AArch64/RISC-V (mobile), hot/cold with profiles; BOLT does the post-link version

Choose specialization when a function is called with different constants that each unlock simplification (function pointers, mode flags) and inlining it everywhere is too big. Choose partial inlining when a function is an early exit plus a slow path. Choose outlining when code size is the goal (-Oz, embedded, mobile); hot/cold splitting when you have profiles or clear cold paths and care about instruction-cache locality.

9. Assessment¶

Quiz (./course quiz 20): funcspec-clones, llvm-where-funcspec (tag cloning); partial-inline-region, partial-inline-why (tag partial-inline); outline-benefit, hotcold-cold-blocks (tag outlining).
Drill: none. The computations of this lesson are small arithmetic (outlining benefit, region inputs and outputs), which the quiz questions outline-benefit and partial-inline-region ask on concrete instances; the underlying mechanics are the inline cost model (drill inline-decision) and IPSCCP (Lesson 20.5).
Flashcards: tags cloning, partial-inline, outlining.
Exercises: none required; exercise E2's lab measurements show what partial inlining would save on the interp benchmark's cold error handler.

References¶

See the chapter references.

Lesson 20.4 — Specialization and outlining: cloning, partial inlining, the outliners and hot/cold splitting¶

1. Problem and motivation¶

Cloning and function specialization¶

Partial inlining¶

Outlining and hot/cold splitting¶

2. Definitions and algorithms¶

3. Worked example¶

Cloning and function specialization¶

Partial inlining¶

Outlining and hot/cold splitting¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

7. In real compilers¶

Cloning and function specialization¶

Partial inlining¶

Outlining and hot/cold splitting¶

8. Comparison¶

9. Assessment¶

References¶