Lesson 12.3 — Writing passes: analysis printers, strength reduction, counter instrumentation¶

Techniques: analysis passes and their printers (a function analysis cached by the new pass manager, printed in a documented format); strength reduction of multiplication and division by powers of two (and why sdiv is not an arithmetic shift); counter-based instrumentation (per-block counters, the spanning-tree placement of Knuth and Ball–Larus, the basis of profile-guided optimization) · Pebble implements: pebble-stats + print<pebble-stats> (E1), pebble-strength (E2), pebble-bbcount (E3), all in pebble/lib/Passes/Basics/ · Drill: peephole-verify · Prerequisites: Lesson 12.1, Ch 9 Lesson 9.7 (poison and flags) · Time: 4–6 hours

A pass has three shapes. An analysis computes facts and changes nothing; a transformation rewrites the IR and must say what it preserved; an instrumentation pass adds code whose only purpose is to observe the program when it runs. This lesson teaches one technique of each shape to full depth, because you implement all three in exercises E1–E3: they are the first passes of the course plugin. The transformation is small but instructive: replacing x / 4 by a shift is a textbook optimization that is wrong for negative x if done naively, and getting the overflow flags right needs a proof.

1. Problem and motivation¶

Analysis passes and printers¶

Most optimizations ask the same questions: how many blocks, which edges are critical, what does this loop nest look like. An analysis answers once per unit and the pass manager caches the answer (Lesson 12.1). A printer pass (print<domtree>, print<pebble-stats>) requests the analysis and prints it in a documented format, which makes the analysis testable with FileCheck (Lesson 12.4): the format is the analysis's test contract [LLVM-WNPM]. LLVM has printers for nearly every analysis; the course's registry (print<pebble-x>) follows the same convention.

Strength reduction by powers of two¶

"Strength reduction" originally meant replacing multiplications of induction variables by additions in loops (Allen, Cocke and Kennedy [ACK81], Chapter 18). Its local cousin replaces an expensive operation by a cheaper one with the same result: x * 8 by x << 3, x / 8 by x >> 3, x % 8 by x & 7. For unsigned operands this is immediate. For signed division it is not: C's / rounds toward zero, an arithmetic shift rounds toward $-\infty$, and they differ on every negative $x$ that is not a multiple of the divisor. The correct sequence adds a bias first [HD2, §10-1]; LLVM keeps sdiv by a power of two in the IR (it is the canonical form) and emits the biased sequence in the back end [LLVM-DAGCombiner]. In Pebble, E2's pebble-strength does it on IR, which lets you test it with lli equivalence.

Counter-based instrumentation¶

Profile-guided optimization (Chapter 20) needs execution counts. Instrumentation inserts counters into the program; running it on training inputs produces a profile. The naive method, one counter per basic block (pebble-bbcount), is simple but wasteful: Knuth observed that counts obey flow conservation, so counters on the edges outside a spanning tree of the control-flow graph determine all the others, and Ball and Larus proved this placement optimal and showed how to put counters on cold edges [BL94]. LLVM's IR PGO instrumentation (pgo-instr-gen) builds exactly this minimum spanning tree [LLVM-PGOInstr].

2. Definitions and algorithms¶

Definition 12.3.1 (Integers of width N)

A value of type iN is a bit string $x \in \{0,1\}^{N}$ read as unsigned $\lfloor x \rfloor_u \in [0, 2^N)$ or signed $\lfloor x \rfloor_s \in [-2^{N-1}, 2^{N-1})$. add, sub, mul and shl compute modulo $2^N$. For $0 \le k < N$: $\mathtt{shl}(x,k) = x \cdot 2^k \bmod 2^N$, $\mathtt{lshr}(x,k) = \lfloor \lfloor x \rfloor_u / 2^k \rfloor$, $\mathtt{ashr}(x,k) = \lfloor \lfloor x \rfloor_s / 2^k \rfloor$ (floor). udiv is $\lfloor x \rfloor_u \div \lfloor y \rfloor_u$ rounded down, sdiv is $\lfloor x \rfloor_s \div \lfloor y \rfloor_s$ rounded toward zero; division by zero and sdiv INT_MIN, -1 are undefined behavior (UB). A nuw (nsw) flag makes the result poison if the unsigned (signed) mathematical result is not representable; exact on a division or right shift makes it poison if the remainder (shifted-out bits) is not zero.

Analysis passes and printers¶

Definition 12.3.2 (CFG statistics, critical edge)

For a function with blocks $N$ and terminator successor lists, the edges are the pairs $(b, i)$ with $i$ an index into $b$'s successor list (a switch with two cases to the same target has two edges). An edge $(b, i)$ to $t$ is critical if $b$ has at least two successor edges and $t$ has at least two predecessor edges (counted with multiplicity), as llvm::isCriticalEdge(T, i, /*AllowIdenticalEdges=*/false). print<pebble-stats> prints, per defined function: blocks, edges, critical edges, instructions, and the opcode histogram sorted by opcode name (the exact format is in exercises.md, E1).

Algorithm 12.3.3 (The statistics analysis)

Input: a function $F$.
Output: $(\lvert N \rvert, e, c, i, h)$: blocks, edges, critical edges, instructions, opcode histogram.
Precondition: $F$ is a definition; every block has a terminator (the verifier holds).
Postcondition: the counts of Definition 12.3.2.
Invariant: after processing blocks $b_1..b_j$ the counters describe exactly those blocks.

function Stats(F):
    blocks, edges, critical, insts ← 0; hist ← empty map
    for b in blocks(F):
        blocks ← blocks + 1
        T ← terminator(b)
        for i ← 0 to NumSuccessors(T) - 1:
            edges ← edges + 1
            if NumSuccessors(T) ≥ 2 and NumPredEdges(Successor(T, i)) ≥ 2:
                critical ← critical + 1
        for I in b:
            insts ← insts + 1
            hist[OpcodeName(I)] ← hist[OpcodeName(I)] + 1
    return (blocks, edges, critical, insts, hist)

The result depends on every instruction, so its invalidate is the default one: invalidated unless preserved by name or by all (Definition 12.1.4). A printer requests it with getResult and returns PreservedAnalyses::all().

Strength reduction by powers of two¶

Algorithm 12.3.4 (Power-of-two strength reduction, pebble-strength)

Input: a function; every mul, udiv, urem, sdiv whose operand is a constant $C$ of scalar type iN.
Output: the function with each such instruction replaced when $C$ is a power of two.
Precondition: $N \ge 2$.
Postcondition: the new function refines the old one (Lemma 12.3.8, Theorems 12.3.9–12.3.10); CFG unchanged.
Invariant: every rewritten instruction's uses now use a value that refines it.

function StrengthReduce(F):
    changed ← false
    for I in a snapshot of the instructions of F:
        new ← Rewrite(I)
        if new ≠ none:
            replace all uses of I with new; erase I; changed ← true
    return changed ? {CFG analyses preserved} : all preserved

function Rewrite(I):                       # X is the non-constant operand, C the constant
    k ← log2(C) if C is 2^k as an unsigned N-bit value and k ≥ 1, else none
    case opcode(I):
      mul (either operand order): if k: return shl X, k   with nuw if I has nuw,
                                                          nsw if I has nsw and k ≤ N - 2
      udiv: if k: return lshr X, k                        with exact if I has exact
      urem: if k: return and X, C - 1
      sdiv: if k and C > 0 as a signed value (so k ≤ N - 2):
               if I has exact: return ashr exact X, k
               s ← ashr X, N - 1                          # all ones if X < 0, else 0
               b ← lshr s, N - k                          # 2^k - 1 if X < 0, else 0
               t ← add X, b
               return ashr t, k
    return none

Counter-based instrumentation¶

Definition 12.3.5 (Edge profile, flow conservation, extended CFG)

Let $G = (N, E, r)$ be a CFG with a single exit block $x$ (add one otherwise). The extended CFG $G^{+}$ adds a virtual edge $x \to r$. An execution count assigns $\mathrm{cnt}(u \to v) \in \mathbb{N}$ to every edge of $G^{+}$ for a set of complete runs; the virtual edge counts the runs. Every block satisfies flow conservation (Kirchhoff's law): $\sum_{p \to v} \mathrm{cnt}(p \to v) = \sum_{v \to s} \mathrm{cnt}(v \to s)$, and a block's count is either side. A flow is any vector $\mathrm{cnt} \in \mathbb{Z}^{E^{+}}$ satisfying conservation at every block. A set $C \subseteq E^{+}$ of instrumented edges is sufficient if the values on $C$ determine the values on all edges, for every flow.

Algorithm 12.3.6 (Per-block counters, pebble-bbcount)

Input: a module.
Output: the module with one 64-bit counter per block of every defined function, incremented at the block's first insertion point, and a destructor that reports all counters at exit.
Precondition: the module is not instrumented yet (no @__pebble_bbcount_counters).
Postcondition: program behavior is unchanged except for the report on stderr; after a normal exit counter $j$ equals the number of executions of block $j$.
Invariant: during the run, counter $j$ equals the number of times control has entered block $j$ so far.

function BBCount(M):
    if M has global @__pebble_bbcount_counters: return all preserved
    blocks ← [b | f in functions(M), f defined, b in blocks(f)]   # module order, then block order
    create @__pebble_bbcount_counters : [|blocks| x i64] = zeroinitializer
    create @__pebble_bbcount_names : [|blocks| x ptr] = ["f:b" or "f:#i" for each block]
    for j, b in enumerate(blocks):
        at FirstInsertionPoint(b):                 # after phis and landing pads
            c ← load counters[j]; store c + 1 → counters[j]
    create internal @__pebble_bbcount_at_exit() { call @__pebble_bbcount_dump(counters, names, |blocks|) }
    append it to @llvm.global_dtors
    return none preserved

Algorithm 12.3.7 (Spanning-tree counter placement, after Knuth and Ball–Larus)

Input: $G^{+}$; optional edge weights $w$ (estimated frequencies).
Output: a set $C$ of instrumented edges; and, after a run, all edge counts.
Precondition: $G^{+}$ is connected (every block is reachable from $r$ and reaches $x$).
Postcondition: $C = E^{+} \setminus T$ for a spanning tree $T$ of the undirected $G^{+}$ of maximum weight; $\lvert C \rvert = \lvert E^{+} \rvert - \lvert N \rvert + 1$; the reconstructed counts equal the true ones (Theorem 12.3.12).
Invariant (reconstruction): every unknown edge incident to a block whose other incident edges are all known is determined by flow conservation.

function Place(G+, w):
    T ← maximum-weight spanning tree of G+ (Kruskal: edges by decreasing w, union-find)
    return E+ \ T                              # hot edges stay uninstrumented

function Reconstruct(G+, T, counts on E+ \ T):
    known ← E+ \ T
    while some edge is unknown:
        pick a block v with exactly one unknown incident edge u     # exists: T restricted to unknowns is a forest
        cnt(u) ← (sum of known edges on the other side of v) − (sum of known edges on u's side of v)
        known ← known ∪ {u}
    return cnt

3. Worked example¶

Statistics. loop.c below, compiled at -O0 with -disable-O0-optnone, gives main seven blocks: entry, for.cond, for.body, if.then, if.end, for.inc, for.end.

#include <stdio.h>
int sq(int x) { return x * x; }
int main(void) {
  int s = 0;
  for (int i = 0; i < 10; i++)
    if (i % 3 == 0)
      s += sq(i);
  printf("%d\n", s);
  return 0;
}

flowchart TD
  entry([entry]) --> cond[for.cond]
  cond --> body[for.body]
  cond --> end[for.end]
  body --> then[if.then]
  body --> ifend[if.end]
  then --> ifend
  ifend --> inc[for.inc]
  inc --> cond
  classDef hl fill:#fde68a,stroke:#b45309;
  class body hl;

Algorithm 12.3.3 over the blocks in order:

block	successors	edges so far	critical?	instructions so far
entry	for.cond	1	no (1 successor)	7
for.cond	for.body, for.end	3	no, no (each target has 1 predecessor)	10
for.body	if.then, if.end	5	no; yes (`for.body` has 2 successors, `if.end` 2 predecessors)	14
if.then	if.end	6	no	20
if.end	for.inc	7	no	21
for.inc	for.cond	8	no	25
for.end	—	8	—	28

giving blocks: 7, edges: 8, critical-edges: 1, instructions: 28 (the real printer output is in §7).

Signed division by 4. Algorithm 12.3.4 on sdiv i32 %x, 4 ($N = 32$, $k = 2$) for three inputs:

$x$	$s$: `ashr x, 31`	$b$: `lshr s, 30`	$t = x + b$	`ashr t, 2`	$x \div 4$ toward 0	naive `ashr x, 2`
7	0	0	7	1	1	1
−7	−1 (all ones)	3	−4	−1	−1	−2
−8	−1	3	−5	−2	−2	−2

The naive shift is wrong exactly on negative non-multiples of 4 (Theorem 12.3.9 below).

Counter placement. For main, $G^{+}$ adds for.end → entry: $\lvert N \rvert = 7$, $\lvert E^{+} \rvert = 9$, so $9 - 7 + 1 = 3$ counters suffice (Theorem 12.3.12). Take the spanning tree $T = \{$entry→for.cond, for.cond→for.body, for.cond→for.end, for.body→if.then, for.body→if.end, if.end→for.inc$\}$ and instrument $C = \{$for.end→entry, if.then→if.end, for.inc→for.cond$\}$. One run measures 1, 4 and 10. Reconstruction (Algorithm 12.3.7), one row per step:

step	block used	unknown edge solved	equation	value
1	entry	entry→for.cond	in = for.end→entry	1
2	for.end	for.cond→for.end	out = for.end→entry	1
3	for.cond	for.cond→for.body	in (1 + 10) − for.cond→for.end (1)	10
4	for.inc	if.end→for.inc	out = for.inc→for.cond	10
5	if.then	for.body→if.then	out = if.then→if.end	4
6	if.end	for.body→if.end	out (10) − if.then→if.end (4)	6

Check at for.body: in 10 = out 4 + 6. Block counts follow: entry 1, for.cond 11, for.body 10, if.then 4, if.end 10, for.inc 10, for.end 1 — exactly what pebble-bbcount prints with seven counters instead of three.

Try it

./course drill peephole-verify --seed 5 --solution checks strength-reduction rewrites (with and without flags) on i4 by exhaustion.

4. Invariants and correctness¶

Lemma 12.3.8 (Unsigned rewrites)

For $1 \le k \le N-1$ and every iN value $x$: $\mathtt{mul}(x, 2^k) = \mathtt{shl}(x, k)$, $\mathtt{udiv}(x, 2^k) = \mathtt{lshr}(x, k)$ and $\mathtt{urem}(x, 2^k) = \mathtt{and}(x, 2^k - 1)$. With flags: mul nuw and shl nuw are poison on the same inputs; udiv exact and lshr exact too.

Proof

Multiplication by $2^k$ modulo $2^N$ is $x \cdot 2^k \bmod 2^N$, which is shl by Definition 12.3.1. Writing $\lfloor x \rfloor_u = q\,2^k + r$ with $0 \le r < 2^k$, udiv gives $q$, and $q = \lfloor \lfloor x \rfloor_u / 2^k \rfloor$ is lshr; the remainder $r$ is the low $k$ bits, i.e. $x$ AND $2^k - 1$. For nuw: the unsigned product overflows iff $\lfloor x \rfloor_u \cdot 2^k \ge 2^N$ iff some of the top $k$ bits of $x$ is set iff shl nuw shifts out a one. For exact: the remainder $r$ is nonzero iff a shifted-out bit is one. ∎

Theorem 12.3.9 (Signed division by a power of two)

Let $1 \le k \le N-2$ and $d = 2^k$ (a positive signed value). For every iN $x$ with signed value $v$:

$\mathtt{ashr}(x, k) = \lfloor v / d \rfloor$, which equals $\mathtt{sdiv}(x, d)$ iff $v \ge 0$ or $d \mid v$;
with $b = 2^k - 1$ if $v < 0$ and $b = 0$ otherwise, $\mathtt{ashr}(x + b, k) = \mathtt{sdiv}(x, d)$, and the sequence of Algorithm 12.3.4 computes this $b$;
sdiv exact x, d and ashr exact x, k agree, including on poison.

Proof

(1) By Definition 12.3.1, ashr is floor division. Truncation toward zero equals floor for $v \ge 0$, and for $v < 0$ exactly when the division has no remainder; otherwise $\lceil v/d \rceil = \lfloor v/d \rfloor + 1$. (2) For $v \ge 0$, $b = 0$ and the claim is (1). For $v < 0$: $v + (d - 1)$ is representable (it lies in $[-2^{N-1} + d - 1, d - 2]$), and $\lfloor (v + d - 1)/d \rfloor = \lceil v / d \rceil$ (the standard identity $\lceil a/d \rceil = \lfloor (a + d - 1)/d \rfloor$ for integers $a$ and $d > 0$), which is truncation toward zero for negative $v$. The bias: ashr x, N-1 is the all-ones word if $v < 0$ and zero otherwise; lshr of all ones by $N - k$ leaves the low $k$ bits set, i.e. $2^k - 1$; of zero, zero. (3) With exact, both are poison iff $d \nmid v$ (the shifted-out bits of $x$ are the remainder bits, for negative $v$ in two's complement too); when $d \mid v$ both give $v / d$ by (1). ∎

Theorem 12.3.10 (When nsw survives)

For $1 \le k \le N - 2$, mul nsw x, 2^k and shl nsw x, k are poison on exactly the same $x$. For $k = N - 1$ the constant $2^{N-1}$ is $-2^{N-1}$ as a signed value, and there is an $x$ on which mul nsw x, 2^(N-1) is defined but shl nsw x, N-1 is poison: transferring nsw is unsound.

Proof

For $k \le N-2$, $2^k$ is positive as a signed value, the signed product $v \cdot 2^k$ is representable iff $-2^{N-1} \le v\,2^k < 2^{N-1}$, and shl nsw is poison iff shifting back arithmetically does not give $v$, which is the same condition. For $k = N-1$ take $x = 1$: the signed product is $1 \cdot (-2^{N-1}) = -2^{N-1}$, representable, so mul nsw gives INT_MIN; shl nsw 1, N-1 shifts a one into the sign bit, and ashr of the result by $N-1$ gives $-1 \ne 1$, so it is poison. Dropping nsw (plain shl) is sound by Lemma 12.3.8. ∎

Lemma 12.3.11 (Instrumentation invariant)

In a program instrumented by Algorithm 12.3.6, at every point of execution counter $j$ equals the number of times control has entered block $j$, and all other state equals that of the original program.

Proof

The inserted instructions touch only the new global array. Every entry into block $j$ executes its first insertion point exactly once before anything else of the block that can transfer control (phis and landing pads do not), incrementing counter $j$ by one; no other code writes it. The destructor runs after main returns, so it does not affect earlier state. By induction on the number of executed blocks the claim holds. (Threads would need atomic increments; the pass is for single-threaded programs, like the course's.) ∎

Theorem 12.3.12 (Optimal counter placement; Knuth, Ball and Larus)

Let $G^{+}$ be connected with $n$ blocks and $e$ edges. (a) For every spanning tree $T$ of $G^{+}$ (ignoring edge directions), the counts on $E^{+} \setminus T$ determine all edge counts, and Algorithm 12.3.7 reconstructs them. (b) No set of fewer than $e - n + 1$ edges is sufficient (Definition 12.3.5).

Proof

(a) The unknown edges always form a subforest of $T$. A finite nonempty forest has a leaf block $v$ with exactly one unknown incident edge $u$; flow conservation at $v$ is one linear equation in which every other term is known, so it determines $\mathrm{cnt}(u)$. Removing $u$ keeps a forest, so induction on the number of unknown edges terminates with all counts known. Uniqueness is the same argument read backwards: the values are forced. (b) The flows (edge vectors satisfying conservation at every block) form a vector space, the cycle space of the undirected connected graph, of dimension $e - n + 1$ (a spanning tree has $n - 1$ edges and each non-tree edge closes one independent cycle). A sufficient set $C$ must make the linear map "restrict a flow to $C$" injective on this space; an injective linear map from a space of dimension $e - n + 1$ needs a target of dimension at least $e - n + 1$, so $\lvert C \rvert \ge e - n + 1$. (Ball and Larus [BL94] prove the same bound and add the weighting that puts counters on cold edges.) ∎

Instrumenting a critical edge needs a new block

A counter "on an edge" $u \to v$ must execute exactly when control takes that edge. If $u$ has one successor, put it at the end of $u$; if $v$ has one predecessor, at the start of $v$; if the edge is critical (Definition 12.3.2), neither works and the edge must be split. This is why pebble-stats reports critical edges, and why LLVM's FuncPGOInstrumentation calls SplitCriticalEdge for counters that must go on a critical edge.

5. Complexity¶

Let $n$ be the number of blocks, $e$ the number of edges, $I$ the number of instructions.

Technique	Compile time	Run-time overhead	Space	Notes
Statistics analysis (Alg. 12.3.3)	$\Theta(I + e)$ once per cache miss	none	$O(\#\text{opcodes})$	predecessor counts via use lists: $O(e)$ total
Strength reduction (Alg. 12.3.4)	$\Theta(I)$; $O(1)$ per rewrite (at most 4 new instructions)	removes a hardware division for 1–4 single-cycle instructions	$O(1)$ extra	the sdiv sequence is 4 instructions; x86 uses 4 (lea, test, cmov, sar), AArch64 4 (§7)
Per-block counters (Alg. 12.3.6)	$\Theta(n + I)$	one load/add/store per executed block	$8n$ bytes + names	simple; counts blocks directly
Spanning-tree counters (Alg. 12.3.7)	$O(e \log e)$ for Kruskal with union-find	one increment per executed instrumented edge; $e - n + 1$ counters	$8(e - n + 1)$ bytes	reconstruction $O(e)$ after the run

Justification. Algorithm 12.3.3 visits each instruction and each successor slot once; predecessor counts come from the successor's use list, whose total length is $e$. Kruskal sorts $e$ edges ($O(e \log e)$) and does $O(e)$ union-find operations. Pathological family for per-block counters: a chain of $n$ blocks each with one successor and one predecessor, executed $m$ times, costs $n \cdot m$ increments with Algorithm 12.3.6, but the extended graph is one cycle ($e = n$), so $e - n + 1 = 1$ counter suffices: $m$ increments, a factor $n$ fewer. In the worked example 3 counters replace 7.

Analysis passes and printers¶

Printers with options (print<memoryssa;no-ensure-optimized-uses>, the course's print<pebble-x;params>): one analysis, several views. Trade-off: the format grows options that tests must pin.
Statistics and remarks (-stats, -pass-remarks=<regex>): counters and messages instead of a printer; statistics need an assertions-enabled LLVM. Trade-off: not a stable format.

Strength reduction by powers of two¶

Division by arbitrary constants with a multiply-high by a "magic number" and shifts (Granlund and Montgomery [GM94]; Hacker's Delight chapter 10 [HD2]), used by every back end, including LLVM's TargetLowering::BuildSDIV. Trade-off: 3–6 instructions and a multiplier.
Negative powers of two: $x \div (-2^k) = -(x \div 2^k)$ (truncation is odd-symmetric), one extra sub. Trade-off: none, except the INT_MIN divisor, which is excluded.
Loop strength reduction of induction variables ([ACK81], LLVM's LoopStrengthReduce, Chapter 18): replaces i * c by a running sum. Trade-off: needs SCEV and register-pressure modeling.

Counter-based instrumentation¶

Maximum-weight spanning trees put counters on cold edges using estimated frequencies [BL94]; LLVM's CFGMST does this with BranchProbabilityInfo. Trade-off: needs a good static estimate.
Path profiling (Ball and Larus, 1996) counts acyclic paths with one counter update per path. Trade-off: path numbering and larger tables.
Sampling instead of counters (AutoFDO, -fprofile-sample-use, Chapter 20): no instrumentation overhead. Trade-off: statistical, needs debug info to map samples.

7. In real compilers¶

Analysis passes and printers¶

LLVM: every analysis has a printer registered in llvm/lib/Passes/PassRegistry.def (print<domtree>, print<branch-prob>, ...) [LLVM-PassRegistry]; the course's print<pebble-stats> is registered in your E1 file through pebble/include/pebble/Passes/Registry.h. GCC's equivalent is dump files (-fdump-tree-<pass>-details).

Two analysis printers on the running example

Reproduce (clang 23.1.2, opt 23.1.2, the course plugin built by ./course test 12 --solution; $SOL is that build: SOL=$PWD/build/ci-solutions-linux from the repository root, ci-solutions-macos on macOS):

cat > loop.c <<'EOF'
#include <stdio.h>
int sq(int x) { return x * x; }
int main(void) {
  int s = 0;
  for (int i = 0; i < 10; i++)
    if (i % 3 == 0)
      s += sq(i);
  printf("%d\n", s);
  return 0;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm loop.c -o loop.ll
opt -load-pass-plugin=$SOL/lib/PebblePasses.so -passes='print<pebble-stats>' \
    -disable-output loop.ll 2>&1
opt -passes='print<branch-prob>' -disable-output loop.ll 2>&1 | grep -E 'for.body|analysis.*main'

Output:

pebble-stats: function 'sq'
  blocks: 1
  edges: 0
  critical-edges: 0
  instructions: 6
  opcodes: alloca=1 load=2 mul=1 ret=1 store=1
pebble-stats: function 'main'
  blocks: 7
  edges: 8
  critical-edges: 1
  instructions: 28
  opcodes: add=2 alloca=3 br=6 call=2 icmp=2 load=6 ret=1 srem=1 store=5
Printing analysis 'Branch Probability Analysis' for function 'main':
  edge %for.cond -> %for.body probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
  edge %for.body -> %if.then probability is 0x30000000 / 0x80000000 = 37.50%
  edge %for.body -> %if.end probability is 0x50000000 / 0x80000000 = 62.50%

What to notice: the numbers of the §3 trace, printed by the reference pebble-stats (your E1 must print the same). LLVM's static branch probabilities are an analysis estimate of what Algorithm 12.3.7 would measure: the loop edge is "hot", and the if is guessed 37.5 % taken — the run below measures 4 of 10 = 40 %.

Strength reduction by powers of two¶

LLVM: llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp — InstCombinerImpl::visitMul, visitUDiv, visitSDiv (turns mul into shl, udiv into lshr, sdiv exact into ashr exact, and leaves sdiv by $2^k$ alone) [LLVM-InstCombineMulDiv]; llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp — DAGCombiner::visitSDIV, DAGCombiner::BuildSDIVPow2 (the biased sequence, or a target hook) [LLVM-DAGCombiner]. GCC: gcc/expmed.cc, expand_sdiv_pow2 (gcc-15) [GCC-Expmed].

LLVM keeps sdiv in IR and lowers it with a bias

Reproduce (opt 23.1.2, llc 23.1.2):

cat > sd.ll <<'EOF'
define i32 @sdiv4(i32 %x) {
  %r = sdiv i32 %x, 4
  ret i32 %r
}
define i32 @sdiv4_exact(i32 %x) {
  %r = sdiv exact i32 %x, 4
  ret i32 %r
}
EOF
opt -passes=instcombine -S sd.ll | grep '%r = '
llc -O2 -mtriple=x86_64-linux-gnu sd.ll -o - | sed 's/\s*#.*//' | grep -vE '^\s*[.]|^$'
llc -O2 -mtriple=aarch64-linux-gnu sd.ll -o - | sed 's|\s*//.*||' | grep -vE '^\s*[.]|^$'

Output:

  %r = sdiv i32 %x, 4
  %r = ashr exact i32 %x, 2
sdiv4:
    leal    3(%rdi), %eax
    testl   %edi, %edi
    cmovnsl %edi, %eax
    sarl    $2, %eax
    retq
sdiv4_exact:
    movl    %edi, %eax
    sarl    $2, %eax
    retq
sdiv4:
    add w8, w0, #3
    cmp w0, #0
    csel    w8, w8, w0, mi
    asr w0, w8, #2
    ret
sdiv4_exact:
    asr w0, w0, #2
    ret

What to notice: InstCombine applies Theorem 12.3.9(3) (exact → ashr exact) but keeps plain sdiv as the canonical IR form. Both back ends compute Theorem 12.3.9(2)'s $x + 3$ and select it when $x < 0$ (cmovns/csel mi) instead of the branch-free ashr/lshr bias of Algorithm 12.3.4 — the same function, cheaper on these targets. pebble-strength does it in IR so that lli can check it.

Counter-based instrumentation¶

LLVM: llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp — FuncPGOInstrumentation, the pgo-instr-gen pass [LLVM-PGOInstr]; llvm/include/llvm/Transforms/Instrumentation/CFGMST.h — CFGMST::buildEdges, CFGMST::computeMinimumSpanningTree [LLVM-CFGMST]; runtime in compiler-rt/lib/profile. GCC: gcc/profile.cc (-fprofile-arcs, spanning-tree placement, gcc-15).

LLVM's IR PGO uses 3 counters where pebble-bbcount uses 7

Reproduce (clang 23.1.2, llvm-profdata 23.1.2, and the compiler-rt 23.1.2 profile runtime: Homebrew's llvm ships it — drop -resource-dir="$RD"; on Linux $RD is a resource directory with compiler-rt added, built as in the chapter's tools outside the course toolchain; $SOL is the reference build of ./course test 12 --solution: SOL=$PWD/build/ci-solutions-linux from the repository root, ci-solutions-macos on macOS):

cat > loop.c <<'EOF'
#include <stdio.h>
int sq(int x) { return x * x; }
int main(void) {
  int s = 0;
  for (int i = 0; i < 10; i++)
    if (i % 3 == 0)
      s += sq(i);
  printf("%d\n", s);
  return 0;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm loop.c -o loop.ll
opt -passes=pgo-instr-gen -S loop.ll | grep -E 'instrprof.increment\(ptr @__profn_main'
clang-23 -resource-dir="$RD" -O0 -fprofile-generate loop.c -o loop.pgo
LLVM_PROFILE_FILE=loop.profraw ./loop.pgo
llvm-profdata merge -o loop.profdata loop.profraw
llvm-profdata show --all-functions --counts loop.profdata | sed -n '1,9p'
opt -load-pass-plugin=$SOL/lib/PebblePasses.so -passes=pebble-bbcount loop.ll -o loop.bb.bc
clang-23 -S -emit-llvm -O0 pebble/lib/Passes/Basics/provided/pebble_bbcount_rt.c -o rt.ll
lli -extra-module=rt.ll loop.bb.bc 2>&1 >/dev/null

Output:

  call void @llvm.instrprof.increment(ptr @__profn_main, i64 536873291982496694, i32 3, i32 2)
  call void @llvm.instrprof.increment(ptr @__profn_main, i64 536873291982496694, i32 3, i32 1)
  call void @llvm.instrprof.increment(ptr @__profn_main, i64 536873291982496694, i32 3, i32 0)
126
Counters:
  main:
    Hash: 0x07735b6a2202e3b6
    Counters: 3
    Block counts: [10, 4, 1]
  sq:
    Hash: 0x0a4d0ad3efffffff
    Counters: 1
    Block counts: [4]
pebble-bbcount: 8 blocks
4 sq:entry
1 main:entry
11 main:for.cond
10 main:for.body
4 main:if.then
10 main:if.end
10 main:for.inc
1 main:for.end

What to notice: pgo-instr-gen inserts $e - n + 1 = 3$ counters in main (Theorem 12.3.12), placed in entry, if.then and for.inc — blocks that stand for the non-tree edges of §3 — and the run measures [10, 4, 1], exactly the three values from which §3 reconstructed every count. pebble-bbcount reports those same seven block counts directly, with seven counters. (126 is the program's own output.)

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Analysis passes and printers	Exact facts about the current IR; cached per unit	$\Theta(I + e)$ per computation, reused until invalidated	A documented, FileCheck-able format	Low (analysis + printer + registration)	Every LLVM analysis; the course's `print<pebble-x>` contracts
Strength reduction by powers of two	Exact (Theorems 12.3.9–12.3.10); only power-of-two constants	$\Theta(I)$; replaces a multi-cycle hardware divide by 1–4 single-cycle instructions	Wrong if done naively (sdiv → ashr, nsw kept at $k = N-1$)	Low, but the proofs matter	InstCombine (mul/udiv/urem/exact sdiv), DAGCombiner (sdiv), `pebble-strength`
Counter-based instrumentation	Exact counts of the training runs; spanning tree: minimum counters (Theorem 12.3.12)	One increment per executed block (naive) or per instrumented edge (MST)	Per-block counts for PGO; needs a runtime	Low (naive) to medium (MST + reconstruction)	`-fprofile-generate`, `-fprofile-arcs`, gcov, `pebble-bbcount`

Choose an analysis with a printer when several passes need the same facts or you need to test the facts themselves. Choose power-of-two strength reduction when a target's division is slow — which is always — but keep sdiv canonical in IR if a later pass may still want to reason about the division, as LLVM does. Choose per-block counters when simplicity and direct readability matter (teaching, quick coverage); choose spanning-tree counters when instrumented binaries run for real (PGO training), where the overhead matters.

9. Assessment¶

Quiz: stats-critical-edges (number), stats-invalidate, sr-sdiv-bias (mapping), sr-nsw-top, instr-counters (number), instr-reconstruct (mapping), llvm-where-sdiv-pow2.
Drill: ./course drill peephole-verify (strength reductions and their flags, on i4/i5).
Flashcards: tags analysis-printers, strength-reduction, instrumentation.
Exercises: E1 (pebble-stats), E2 (pebble-strength), E3 (pebble-bbcount) in exercises.md.
Find where LLVM does it: in llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp, which member function turns sdiv x, 2^k into shifts?

References¶

See the chapter references.

Technique	Compile time	Run-time overhead	Space	Notes
Statistics analysis (Alg. 12.3.3)	\(\Theta(I + e)\) once per cache miss	none	\(O(\#\text{opcodes})\)	predecessor counts via use lists: \(O(e)\) total
Strength reduction (Alg. 12.3.4)	\(\Theta(I)\); \(O(1)\) per rewrite (at most 4 new instructions)	removes a hardware division for 1–4 single-cycle instructions	\(O(1)\) extra	the sdiv sequence is 4 instructions; x86 uses 4 (lea, test, cmov, sar), AArch64 4 (§7)
Per-block counters (Alg. 12.3.6)	\(\Theta(n + I)\)	one load/add/store per executed block	\(8n\) bytes + names	simple; counts blocks directly
Spanning-tree counters (Alg. 12.3.7)	\(O(e \log e)\) for Kruskal with union-find	one increment per executed instrumented edge; \(e - n + 1\) counters	\(8(e - n + 1)\) bytes	reconstruction \(O(e)\) after the run

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Analysis passes and printers	Exact facts about the current IR; cached per unit	\(\Theta(I + e)\) per computation, reused until invalidated	A documented, FileCheck-able format	Low (analysis + printer + registration)	Every LLVM analysis; the course's `print<pebble-x>` contracts
Strength reduction by powers of two	Exact (Theorems 12.3.9–12.3.10); only power-of-two constants	\(\Theta(I)\); replaces a multi-cycle hardware divide by 1–4 single-cycle instructions	Wrong if done naively (sdiv → ashr, nsw kept at \(k = N-1\))	Low, but the proofs matter	InstCombine (mul/udiv/urem/exact sdiv), DAGCombiner (sdiv), `pebble-strength`
Counter-based instrumentation	Exact counts of the training runs; spanning tree: minimum counters (Theorem 12.3.12)	One increment per executed block (naive) or per instrumented edge (MST)	Per-block counts for PGO; needs a runtime	Low (naive) to medium (MST + reconstruction)	`-fprofile-generate`, `-fprofile-arcs`, gcov, `pebble-bbcount`

Lesson 12.3 — Writing passes: analysis printers, strength reduction, counter instrumentation¶

1. Problem and motivation¶

Analysis passes and printers¶

Strength reduction by powers of two¶

Counter-based instrumentation¶

2. Definitions and algorithms¶

Analysis passes and printers¶

Strength reduction by powers of two¶

Counter-based instrumentation¶

3. Worked example¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

Analysis passes and printers¶

Strength reduction by powers of two¶

Counter-based instrumentation¶

7. In real compilers¶

Analysis passes and printers¶

Strength reduction by powers of two¶

Counter-based instrumentation¶

8. Comparison¶

9. Assessment¶

References¶