Skip to content

Lab 20B · Three inlining heuristics, measured

Chapter: 20 · Interprocedural & Whole-Program Optimization · Lessons: 20.3, 20.10 · Time: 2–4 hours after E2 · Tests: ./course test 20 (label ch20, suite ch20.lab, file tests/ch20/lab/inline-lab.test)

Goal

Compare the three heuristics of your pebble-inline (exercise E2) — a size threshold, the bottom-up cost/benefit model of Lesson 20.3 (Definitions 20.3.6–20.3.8), and the same model with profile-guided hot and cold call sites (Lesson 20.10, Algorithm 20.10.5 step 2) — on seven small C benchmarks. For each benchmark and heuristic the provided driver checks that the program still prints the same output and measures inlined call sites, code size, executed instructions and executed calls. You write no new pass here: the lab is the experiment, and its test checks that your inliner shows the orderings the lesson predicts.

Requirements

  • R1. Heuristics. pebble-inline<size>, pebble-inline<cost> and pebble-inline<profile=FILE> behave as E2 specifies (default thresholds: \(N = 12\); \(T = 225\); hot 3000, cold 45). The driver passes remarks and counts the inline lines.
  • R2. Semantics. Every optimized benchmark prints exactly what the original prints (--check).
  • R3. Orderings (totals over the corpus; checked by tests/ch20/lab/Inputs/order.py):
  • each heuristic executes fewer calls and fewer instructions than no inlining;
  • the cost model executes fewer calls than the size threshold;
  • on hot, the profile-guided mode executes fewer calls than the static cost model (it inlines the hot call the static model rejects);
  • the profile-guided mode executes at most as many instructions as the static cost model.

In addition, on hot both cost and profile inline exactly 2 call sites. - R4. Write-up. Fill in the table below and explain each difference between your numbers and the reference in one sentence.

The contract

The CLI of the provided driver:

measure.py --plugin PebblePasses.so [--opt OPT --lli LLI --clang CLANG] [--table] [--check]
           [--heuristics none,size,cost,profile] [--keep DIR] corpus/*.ll
measure.py regen corpus/*.c              rebuild corpus/*.ll from the C sources

For each benchmark (a module with main and no input): (1) a training run instrumented with Ch 12's pebble-bbcount produces the profile; (2) for each heuristic, pebble-inline<H;remarks> runs, followed by the same cleanup function(sroa,early-cse,instcombine,simplifycfg),globaldce (for none, the cleanup only); (3) the output is compared with the original's; (4) the optimized module is instrumented again and run to count executed IR instructions (phis excluded) and calls. Training and measurement use the same run — the best case for profile-guided inlining.

Input and output formats

Input: corpus/*.ll, produced from corpus/*.c by clang-23 -O1 -Xclang -disable-llvm-passes -fno-discard-value-names -S -emit-llvm followed by opt -passes=sroa (LLVM 23.1.2), with the target triple, data layout and CPU attributes removed so the files are portable (measure.py regen redoes this).

Benchmark What it stresses
vec tiny accessors called in loops (every heuristic should inline them)
mode a large function whose mode argument is a constant at every call: only a model that folds at the call site inlines it
interp a bytecode interpreter: hot arithmetic handlers in the dispatch loop, a large error handler that never runs (cold)
sort comparison and swap helpers of an insertion sort, and a checksum helper that runs once
hash an open-addressing hash table: hot hash and probe functions, a rarely called grow
geom struct-passing helpers and a large summary function called once (only the last-call bonus inlines it)
hot a large external mixing function called from two hot sites (above the static threshold), and an error reporter at two sites that never run

Output (--table):

benchmark  heuristic inlined  static  dyn-instrs  dyn-calls
geom       none            0      70      131982      16000
...
TOTAL      profile        53     666    81930638          8

inlined = call sites inlined; static = IR instructions in defined functions after cleanup; dyn-instrs = executed IR instructions; dyn-calls = executed calls.

Provided infrastructure

File What it gives you
tools/measure.py the driver above
corpus/*.c, corpus/*.ll the seven benchmarks and their IR
pebble/lib/Passes/Basics/provided/pebble_bbcount_rt.c the counter runtime of Ch 12's pebble-bbcount (your Ch 12 pass is used for the profile and the measurement)

What the tests check

Test Checks
inline-lab.test the driver runs all four heuristics on the corpus with --check (R2), order.py accepts the table (R3), and hot inlines 2 sites with cost and with profile

Milestones

  1. Finish E2 (inline-*.ll pass).
  2. Run the driver (from the repository root, with your build's plugin): python3 labs/ch20-inline/tools/measure.py --plugin build/linux/lib/PebblePasses.so --check --table labs/ch20-inline/corpus/*.ll
  3. ctest --preset linux -L '^ch20$' -R ch20.lab passes inline-lab.test.
  4. Fill in the table and write the explanations (R4).
Heuristic inlined static dyn-instrs dyn-calls reference (inlined / static / dyn-instrs / dyn-calls)
none 0 / 541 / 98 349 450 / 5 397 680
size (\(N = 12\)) 37 / 568 / 87 388 931 / 1 824 657
cost (\(T = 225\)) 54 / 569 / 82 430 638 / 300 008
profile (hot 3000, cold 45) 53 / 666 / 81 930 638 / 8

The reference numbers are the solution's (LLVM 23.1.2). Small differences in static are expected if your cost analysis folds slightly more or less; the orderings of R3 must hold.

Hints

Hint 1 — where to start

Run the driver with --heuristics none,size first, then add cost and profile. --keep DIR keeps every intermediate module, remark file and counter dump, so you can see why a call site was kept.

Hint 2 — the key idea

If an ordering fails, look at the benchmark that breaks it and read its remarks: the size threshold loses on mode because it cannot see that the constant mode argument removes most of the callee; the static cost model loses on hot because the callee's cost is above 225 although the call runs 300,000 times; the profile wins there and refuses the cold reporters that the static model inlined.

Hint 3 — what to explain

For each benchmark, compare dyn-calls (did the heuristic remove the calls that run often?) with static (what did it cost?). The profile-guided mode in hot is the lesson's trade-off in one row: +93 static instructions (compared with the static cost model) for 300,000 fewer executed calls.

Stretch goals

  • Measure a train ≠ test setting: change a benchmark's input constants after profiling (edit the .c, regen, keep the old profile with --keep) and see whether the profile's decisions still pay off.
  • Add a fourth heuristic of your own (for example, the knapsack-style greedy order of Algorithm 20.3.5 with a global size budget) as another parameter of your pass, and add it to HEURISTICS in your own copy of the driver.