Lesson 13.1 — Optimization scopes and constant folding¶

Techniques: optimization scopes (local, superlocal, regional, global, interprocedural) with superlocal value numbering as the scope-extension algorithm; constant folding and its pitfalls (overflow, division by zero, floating-point rounding, NaN and signed zeros, target-dependent folding) · Pebble implements: pebble-constfold (exercise E1) · Lab: the rewrite checker of Part B checks folds too · Prerequisites: Ch 8 (basic blocks, CFGs), Lesson 9.7 (poison, UB, refinement) · Time: 4 hours

add i32 %a, %b computed twice in one block is obviously redundant. Computed once in entry and again in a successor then, it is still redundant, because every path to then passes through entry. Computed on one arm of a branch and again after the join, it is redundant on only one path. How far an optimizer looks before it decides — one block, a chain of blocks, the dominator tree, the whole function — is its scope, and it decides both what the optimizer can find and what its correctness argument must cover. This lesson fixes the vocabulary of scopes that the rest of the chapter uses, and then studies the simplest local optimization of all, constant folding: replacing add i8 100, 100 by -56. Folding is easy to state and surprisingly easy to get wrong: overflow, division by zero, NaN, -0.0, rounding and the target's data layout all change the answer.

1. Problem and motivation¶

An optimizer transforms a program into a cheaper one with the same behaviors. Every transformation needs a justification: a fact about the program (this value was already computed, this operand is the constant 5) that holds wherever the transformation applies. The scope says where the facts are collected, and the kind of reasoning needed to combine them.

Optimization scopes¶

Cooper and Torczon organize optimizations by the size of the region they examine [EaC3, Ch. 8]: local methods look at one basic block, where control flows straight through and facts accumulate in order; superlocal methods extend that to an extended basic block (EBB), a tree of blocks whose non-root blocks each have a single predecessor, so every path in the tree is straight-line code; regional methods work on a dominator subtree or a loop nest; global (intraprocedural) methods reason about the whole control-flow graph (CFG), combining facts where paths merge, usually by dataflow analysis (Ch 14); interprocedural methods cross call boundaries (Ch 20). Local value numbering goes back to Cocke and Schwartz [CS70]; the superlocal extension is Cooper and Torczon's presentation of the value-numbering algorithms of the 1970s [EaC3, Ch. 8]; the dominator-based version is Briggs, Cooper and Simpson's [BCS97]. CompCert's verified CSE is superlocal ([Ler09], and the box in §7), and LLVM's EarlyCSE is dominator-scoped [LLVM-EarlyCSE]. In pebblec, the Chapter 13 passes are local: they run on each block of the LLVM IR the front end emits, and Chapters 16–17 widen the scope.

Constant folding¶

Constant folding evaluates, at compile time, an operation whose operands are known constants. It was part of the first optimizing compilers (FORTRAN I evaluated constant subexpressions [EaC3, Ch. 8]) and remains the most frequently applied transformation in every compiler: front ends fold C constant expressions, LLVM folds whenever it builds an instruction with constant operands (ConstantFold.cpp, ConstantFolding.cpp [LLVM-ConstantFolding]), and every later pass (propagation, inlining, unrolling) creates new folding opportunities. The difficulty is not evaluation but which evaluation: the compiler must compute exactly what the target machine would, in the target's integer widths, rounding mode and floating-point format, and it must not "fold away" undefined behavior into a defined value when the program relies on a trap (Pebble's division by zero traps; Lesson 9.7 Definition 9.7.1 says LLVM's udiv by zero is immediate UB). pebblec runs pebble-constfold first in its Chapter 13 pipeline (exercise E1).

2. Definitions and algorithms¶

Optimization scopes¶

Definition 13.1.1 (Extended basic block)

Let \(G = (N, E, r)\) be a CFG whose nodes are basic blocks. An extended basic block is a maximal set \(X \subseteq N\) with a root \(b_X \in X\) such that \(b_X = r\) or \(\lvert \mathrm{preds}(b_X) \rvert \ne 1\), and every \(b \in X \setminus \{b_X\}\) has exactly one predecessor, which is in \(X\). The edges between members of \(X\) form a tree rooted at \(b_X\); a root-to-node path in it is an EBB path.

EBBs of the running example

In @scopes below (CFG entry → then, else; then → join; else → join), then and else each have the single predecessor entry, and join has two. The EBBs are \(\{\mathit{entry}, \mathit{then}, \mathit{else}\}\) (root entry, paths entry, entry then, entry else) and \(\{\mathit{join}\}\).

Definition 13.1.2 (Optimization scope)

The scope of a transformation is the region of code whose instructions it may use to justify rewriting an instruction \(i\):

scope	region used for \(i\) in block \(b\)	how facts combine
local	the instructions before \(i\) in \(b\)	in order
superlocal	the EBB path from the EBB root to \(b\)	in order along the path
regional (dominator-based)	the blocks that dominate \(b\)	in order along the dominator-tree path
global	every path from \(r\) to \(b\)	merged at joins (dataflow, Ch 14)
interprocedural	several functions	over the call graph (Ch 20)

Each scope contains the one above it: a block's predecessors in its EBB path dominate it, and dominators lie on every path.

Proposition 13.1.3 (EBB paths are straight-line code)

Let \(B_1 B_2 \cdots B_j\) be an EBB path. Every execution that enters \(B_j\) has executed \(B_1, \dots, B_{j-1}\), in this order and without any other block in between, immediately before.

Proof

By induction on \(j\). For \(j = 1\) there is nothing to show. For \(j > 1\), \(B_j\) has exactly one predecessor, \(B_{j-1}\) (Definition 13.1.1), so the block executed immediately before entering \(B_j\) is \(B_{j-1}\); by the induction hypothesis the execution entered \(B_{j-1}\) right after \(B_1 \cdots B_{j-2}\). The concatenation is the claim.

Algorithm 13.1.4 (Superlocal value numbering)

Input: a function in SSA form, its CFG \(G = (N, E, r)\).
Output: the same function with every instruction that recomputes an expression already computed on its EBB path removed.
Precondition: SSA: every value has one definition, so a value's number never changes.
Postcondition: no two remaining instructions on one EBB path have the same key.
Invariant: when Visit(b) starts, the scoped table holds exactly the keys of the instructions kept in the blocks of the EBB path from the root to b, excluding b.

function SuperlocalVN(G):
    for b in N with b = r or |preds(b)| ≠ 1:          # EBB roots
        T ← empty scoped hash table
        Visit(b, T)

function Visit(b, T):
    T.PushScope()
    for i in instructions(b):
        Step(i, T)
    for s in succs(b) with |preds(s)| = 1:            # s is in b's EBB
        Visit(s, T)
    T.PopScope()                                      # forget b's keys

function Step(i, T):                                  # i is "x ← op(y, z)"
    k ← (op, VN(y), VN(z)), operands sorted if op is commutative
    if k ∈ T:
        replace every use of x by T[k]; delete i; VN(x) ← VN(T[k])
    else:
        T[k] ← x; VN(x) ← a fresh number               # recorded in the top scope

Step is the loop body of local value numbering, developed in full (identities, constants, memory) in Lesson 13.5, Algorithm 13.5.3. A scoped table supports PushScope, PopScope (delete the keys inserted since the matching push) and lookups that see every open scope; LLVM's ScopedHashTable is one.

Constant folding¶

Definition 13.1.5 (Operation semantics)

For an integer operation \(\mathsf{op}\) with flag set \(F\) on \(\texttt{i}N\), \([\![\mathsf{op}_F]\!] : \mathbb{V}_N^{k} \to \mathbb{V}_N \cup \{\mathsf{UB}\}\) is the function given by the LangRef and summarized in Definitions 9.7.1–9.7.4: the exact result reduced modulo \(2^N\), or \(\mathsf{poison}\) when an operand is poison or a flag's condition fails, or \(\mathsf{UB}\) for immediate undefined behavior (division by zero or by poison, \(\mathrm{INT\_MIN} / -1\)). For a floating-point operation \([\![\mathsf{op}]\!]\) is the IEEE 754 operation of Definition 13.1.9, with the fast-math flags of Lesson 13.8.

Definition 13.1.6 (Constant folding)

An instruction \(i = \mathsf{op}_F(c_1, \dots, c_k)\) is foldable if every \(c_j\) is a constant (or \(\mathsf{poison}\)) and \(v = [\![\mathsf{op}_F]\!](c_1, \dots, c_k) \ne \mathsf{UB}\). Folding \(i\) replaces every use of \(i\) by the constant \(v\) and deletes \(i\). A select with a constant condition folds to the chosen operand even when that operand is not constant.

Folding on \(\texttt{i}8\)

\([\![\mathsf{add}]\!](100, 100) = 200 \bmod 256 = 200\), printed as the signed value \(-56\); \([\![\mathsf{add}_{\{nsw\}}]\!](100, 100) = \mathsf{poison}\) because \(200 \notin [-128, 128)\); \([\![\mathsf{shl}]\!](1, 40) = \mathsf{poison}\) on \(\texttt{i}32\) (shift amount \(\ge 32\)); \([\![\mathsf{udiv}]\!](7, 0) = \mathsf{UB}\), not foldable.

Algorithm 13.1.7 (Worklist constant folding)

Input: a function \(f\).
Output: \(f\) with every foldable instruction folded, repeatedly, until none is left.
Precondition: none (any well-formed function).
Postcondition: no instruction of the result is foldable (Definition 13.1.6).
Invariant: every foldable instruction of the current function is in \(W\).

function ConstFold(f):
    W ← all instructions of f                      # a set: no duplicates
    while W ≠ ∅:
        i ← remove any element of W
        if i is foldable:
            v ← [[op]](operands of i)              # Definition 13.1.5
            for u in users(i): W ← W ∪ {u}          # u may have become foldable
            replace every use of i by v; delete i (and remove it from W)
    return f

This is the contract of exercise E1 (pebble-constfold), with \([\![\cdot]\!]\) implemented on APInt and APFloat only.

Definition 13.1.8 (Binary floating point)

A binary floating-point format with precision \(p\) and exponent range \([e_{\min}, e_{\max}]\) has the finite values \(\pm m \cdot 2^{e - p + 1}\) with integer \(0 \le m < 2^{p}\) (normal numbers have \(m \ge 2^{p-1}\)), plus \(+0\), \(-0\), \(+\infty\), \(-\infty\) and NaNs. double is \(p = 53\), float \(p = 24\) [IEEE754]. \(\mathrm{rn} : \mathbb{R} \to F\) rounds to the nearest representable value, ties to the one with even \(m\), overflowing to \(\pm\infty\).

Definition 13.1.9 (Correctly rounded operations)

For \(\circ \in \{+, -, \times, \div\}\) and finite non-zero-result cases, IEEE 754 defines \(a \mathbin{\circledast} b = \mathrm{rn}(a \circ b)\): the exact real result, rounded once. The special cases: \(x - x = +0\) and \((-0) + (+0) = +0\) in round-to-nearest, \((-0) + (-0) = -0\); \(0 \times \infty\), \(\infty - \infty\), \(0 / 0\) are NaN; \(x / 0 = \pm \infty\) for \(x \ne 0\); any operation with a NaN operand is NaN; every comparison with a NaN is false except \(\ne\) (unordered).

3. Worked example¶

Running example (the IR is in the box of §7):

flowchart TD
  entry([entry: x = add a,b]) --> then[then: y = add a,b]
  entry --> else[else: z = mul a,b]
  then --> join[join: v = add b,a; w = mul a,b; ...]
  else --> join

Optimization scopes¶

Superlocal value numbering (Algorithm 13.1.4), with value numbers \(a{:}0\), \(b{:}1\). The scoped table is shown as its open scopes, innermost last:

step	action	scopes of \(T\)	outcome
1	`Visit(entry)`: push	[ ]	—
2	`x = add a, b`: key (add, 0, 1)	[(add,0,1)→x]	new, VN(x) = 2
3	`Visit(then)`: push	[(add,0,1)→x] [ ]	—
4	`y = add a, b`: key (add, 0, 1)	[(add,0,1)→x] [ ]	found: y := x, delete
5	pop `then`	[(add,0,1)→x]	—
6	`Visit(else)`: push	[(add,0,1)→x] [ ]	—
7	`z = mul a, b`: key (mul, 0, 1)	[(add,0,1)→x] [(mul,0,1)→z]	new, VN(z) = 3
8	pop `else`, pop `entry`	—	table discarded
9	new EBB `join`: push	[ ]	—
10	`v = add b, a`: key (add, 0, 1) sorted	[(add,0,1)→v]	new (x is not visible)
11	`w = mul a, b`: key (mul, 0, 1)	[(add,0,1)→v] [(mul,0,1)→w]	new

Local numbering removes nothing here (no block repeats itself). Superlocal numbering removes y (step 4) but not v: join starts a new EBB, although entry dominates it. A dominator-scoped method removes v too, and only a global method with partial-redundancy elimination can do anything about w, which is available on the else path only. The box in §7 shows LLVM doing exactly these three things.

Constant folding¶

Algorithm 13.1.7 on @chain of tests/ch13/lit/constfold-int.ll:

define i32 @chain() {
  %a = add i32 20, 1
  %b = mul i32 %a, 2
  %c = icmp eq i32 %b, 42
  %d = select i1 %c, i32 %b, i32 0
  ret i32 %d
}

\(W\) is a stack here; the instructions are pushed in reverse program order, so %a is on top and is popped first:

step	pop	foldable?	fold to	\(W\) after (top last)
0	—	—	—	ret, %d, %c, %b, %a
1	`%a`	yes	21	ret, %d, %c, %b
2	`%b` = mul 21, 2	yes	42	ret, %d, %c
3	`%c` = icmp eq 42, 42	yes	true	ret, %d
4	`%d` = select true, 42, 0	yes	42	ret
5	`ret i32 42`	no	—	(empty)

Steps 1–3 re-insert users already in \(W\) (a set, so nothing changes). The result is ret i32 42; print<pebble-icount> goes from 5 to 1 (tests/ch13/lit/pipeline-icount.ll).

Try it

./course drill poison-propagation --seed 4 --difficulty hard --solution evaluates straight-line constant code with flags, exactly the \([\![\cdot]\!]\) of Definition 13.1.5; ./course drill lvn-table --seed 2 --difficulty easy includes folding inside value numbering.

4. Invariants and correctness¶

Optimization scopes¶

Lemma 13.1.10 (Scoped-table invariant)

In Algorithm 13.1.4, when Visit(b, T) is called, the keys visible in \(T\) are exactly the keys of the instructions kept in the blocks \(B_1, \dots, B_{j-1}\) of the EBB path \(B_1 \cdots B_{j-1} b\).

Proof

By induction on the depth of Visit calls. Initialization: the root is visited with an empty table and an empty path. Maintenance: inside Visit(b), the scope pushed for \(b\) receives exactly the keys of \(b\)'s kept instructions (Step inserts into the top scope), so each recursive Visit(s) for an in-EBB successor starts with the path's keys plus \(b\)'s, which is the invariant for \(s\), whose path is the old one followed by \(b\). PopScope removes \(b\)'s keys before Visit(b) returns, restoring the caller's state for its next successor.

Theorem 13.1.11 (Superlocal value numbering is correct)

Algorithm 13.1.4 terminates, and the transformed function refines the original (Definition 9.7.8).

Proof

Termination: each block is visited once (the EBB is a tree, Definition 13.1.1), and each visit is linear in the block. Soundness: suppose Step deletes \(i : x \gets \mathsf{op}(y, z)\) in block \(b\) because \(k \in T\) with \(T[k] = w\). By Lemma 13.1.10, \(w\) was defined by a kept instruction \(\mathsf{op}(y', z')\) with \(\mathrm{VN}(y') = \mathrm{VN}(y)\), \(\mathrm{VN}(z') = \mathrm{VN}(z)\) in a block on \(b\)'s EBB path (or earlier in \(b\)). By Proposition 13.1.3 that instruction executed before \(i\) in every execution reaching \(i\), and in SSA equal value numbers denote equal values (induction over the order of Step calls: numbers are only shared by equal keys of equal operands), so \(w\) holds exactly \(\mathsf{op}(y, z)\): the same value, the same poison. Replacing \(x\) by \(w\) therefore changes no behavior, except where the kept instruction has flags that \(i\) lacks: then \(w\) may be poison where \(x\) was not, which is why Lesson 13.5 (Theorem 13.5.6) intersects the flags of the two instructions.

When it breaks: without SSA, a later assignment to \(y\) invalidates keys that mention \(y\); the local algorithm then needs kill sets (Lesson 13.5 §6). Extending the table across a join (to join above) is unsound without dominance: had join also been reachable from a block that does not compute a + b, the reuse would read an undefined value.

Constant folding¶

Theorem 13.1.12 (Folding is a refinement)

Let \(i\) be foldable with value \(v\) (Definition 13.1.6). Replacing all uses of \(i\) by \(v\) and deleting \(i\) yields a program that refines the original. The same holds when \(v = \mathsf{poison}\) is replaced by an arbitrary constant of the type.

Proof

In every execution that reaches \(i\), \(i\) evaluates to \([\![\mathsf{op}_F]\!](c_1, \dots, c_k) = v\), because its operands are the constants \(c_j\) in every execution. So the constant \(v\) and the instruction \(i\) denote the same value at every use, and by Theorem 9.7.16 (refinement is a congruence for straight-line contexts; each use is such a context) every use computes the same result; \(i\) itself has no side effect (it is not UB, by the foldability condition). If \(v = \mathsf{poison}\), any constant \(c\) refines \(v\) (Definition 9.7.8: a poison source value is refined by every value), and the congruence lifts this to the uses. This is why LLVM may fold add nsw i8 100, 100 either to poison (exercise E1) or to -56 (LLVM's own folder, box in §7): both refine poison.

Theorem 13.1.13 (Worklist folding terminates at a fixed point)

Algorithm 13.1.7 terminates after at most \(n + \sum_i \lvert \mathrm{users}(i) \rvert\) iterations, where \(n\) is the initial number of instructions, and its result contains no foldable instruction.

Proof

Termination: each iteration removes one element of \(W\). Elements enter \(W\) once initially (\(n\) insertions) and once per (folded instruction, user) pair; each instruction is folded at most once because folding deletes it. So the total number of insertions, hence of iterations, is bounded as stated. Fixed point: the invariant (every foldable instruction is in \(W\)) holds initially. Folding \(i\) can make only \(i\)'s users newly foldable, since foldability depends only on an instruction's operands; they are added. A popped instruction that is not foldable stays non-foldable until an operand changes, which re-adds it. At termination \(W = \emptyset\), so no instruction is foldable.

Proposition 13.1.14 (Floating-point folding pitfalls)

Over IEEE 754 double (Definition 13.1.9): (a) \(x + 0.0 = x\) fails for \(x = -0\); (b) \(x \times 0.0 = 0.0\) fails for \(x \in \{\mathrm{NaN}, \pm\infty\}\) and gives \(-0\) for \(x < 0\); (c) \((a + b) + c = a + (b + c)\) fails for \(a = 1\), \(b = 10^{16}\), \(c = -10^{16}\); (d) folding with host arithmetic of a wider format (x87 80-bit) can differ from the target's double result.

Proof

(a) \((-0) + (+0) = +0 \ne -0\) in round-to-nearest (Definition 13.1.9). (b) \(\mathrm{NaN} \times 0 = \mathrm{NaN}\), \(\infty \times 0 = \mathrm{NaN}\), \((-1) \times 0 = -0\). (c) \(10^{16}\) lies in \([2^{53}, 2^{54})\), where consecutive doubles are 2 apart, so \(1 + 10^{16}\) is exactly half-way between \(10^{16}\) and \(10^{16} + 2\) and rounds to the one with the even significand, \(10^{16}\); hence \((1 + 10^{16}) - 10^{16} = 0\), while \(1 + (10^{16} - 10^{16}) = 1\). (d) An operation computed in 64-bit precision and then rounded to 53 bits rounds twice; for sums that land exactly half-way between two doubles after the first rounding, the second rounding (ties to even) can pick the other neighbour than the single correct rounding. This is why LLVM folds with the soft-float APFloat in the target's format, never with host double arithmetic, except for library functions such as sin (box in §7).

Integer pitfalls. Folding must use the IR's width and wrapping (C's int overflow is UB in the source, but the folded IR add wraps and add nsw is poison); must not turn immediate UB into a value when the language promises a trap (Pebble's checked division lowers to a test and pebble_trap before the sdiv, so folding never sees it — but a folder that folds udiv 7, 0 to 0 in a language without that check silently removes a trap); and must use the target's DataLayout for sizes and pointer widths (box in §7).

5. Complexity¶

Technique	Time (worst)	Time (typical)	Space	Variables
Local value numbering (per block)	\(O(n)\) expected, \(O(n^2)\) with adversarial hash collisions	linear	\(O(n)\)	\(n\) instructions
Superlocal value numbering	\(O(n)\) expected over the function	linear	\(O(n)\) for the scope stack	\(n\) instructions
Worklist constant folding	\(O(n + u)\)	linear	\(O(n)\)	\(n\) instructions, \(u = \sum_i \lvert \mathrm{users}(i) \rvert\)
Naive re-scan folding (repeat whole-function passes until no change)	\(O(n^2)\)	1–2 passes	\(O(1)\) extra	\(n\) instructions

Justification. Superlocal VN visits every block once (Theorem 13.1.11) and every instruction does one expected-\(O(1)\) hash operation; each key is inserted and popped once. Worklist folding: Theorem 13.1.13 bounds the iterations by \(n + u\), and each iteration folds in \(O(1)\) for fixed-width arithmetic.

Pathological family. Let \(f_n\) be the chain \(t_1 = 1 + 1\), \(t_2 = t_1 + 1\), …, \(t_n = t_{n-1} + 1\) in one block. A round-based folder that scans the block bottom-up (in reverse program order, as a sweep that also deletes dead code naturally does) folds only \(t_1\) in the first round, \(t_2\) in the second, and so on: \(n\) rounds plus a final no-change round, \(\Theta(n^2)\) instruction visits. The worklist folds the chain in at most \(2n\) iterations whatever the initial order (Theorem 13.1.13). For value numbering, an adversary who knows the hash function can make all \(n\) keys collide, turning each lookup into a list scan: \(\Theta(n^2)\); LLVM's DenseMap hashes with per-type mixing functions, not randomized, so the bound is a worst case, not a typical case.

Scale. InstCombine, which includes folding, is one of the most expensive mid-level passes in -O2 because it runs several times per pipeline, not because a single fold is expensive; EarlyCSE is designed as "a simple and fast domtree-based CSE pass" [LLVM-EarlyCSE].

Optimization scopes¶

Dominator-based value numbering (DVNT) [BCS97]: walk the dominator tree instead of EBB trees, with scoped tables; catches v in the example; LLVM's EarlyCSE [LLVM-EarlyCSE]. Trade-off: needs the dominator tree (Ch 15), and phi operands need care.
Global value numbering (hash-based or partition-based, Alpern–Wegman–Zadeck) and PRE handle joins and partial redundancy (Ch 17); trade-off: iteration and code motion.
Superblocks and traces: tail-duplicate to make larger single-entry regions, then optimize locally; trade-off: code growth (Ch 23).

Constant folding¶

Constant propagation (Kildall 1973) and sparse conditional constant propagation [WZ91]: fold across blocks and through phis, and prune unreachable code; covered in Ch 14 and Ch 17.
Folding library calls and intrinsics (sin, sqrt, ctpop) with the host math library or MPFR; trade-off: host-dependence (GCC uses MPFR for correctly rounded results; LLVM calls the host libm, box in §7).
Folding in the front end: C "integer constant expressions" must be folded by the language rules (Clang's constant evaluator, GCC's fold-const.cc); trade-off: two folders that must agree.
Folding to poison vs. to a wrapped value: both refine (Theorem 13.1.12); poison enables more later folds, a wrapped value is friendlier to debugging.

7. In real compilers¶

Optimization scopes¶

Local, dominator-scoped and global redundancy in LLVM

Reproduce (opt 23.1.2; any OS):

cat > scopes.ll <<'EOF'
define i32 @scopes(i32 %a, i32 %b, i1 %c) {
entry:
  %x = add i32 %a, %b
  br i1 %c, label %then, label %else
then:
  %y = add i32 %a, %b        ; same EBB as %x: superlocal
  br label %join
else:
  %z = mul i32 %a, %b
  br label %join
join:
  %p = phi i32 [ %y, %then ], [ %z, %else ]
  %v = add i32 %b, %a        ; dominated by %x: dominator-scoped
  %w = mul i32 %a, %b        ; available on one path only: partial
  %r = add i32 %p, %w
  %s = add i32 %r, %v
  %t = mul i32 %s, %x
  ret i32 %t
}
EOF
echo "=== early-cse"; opt -passes=early-cse -S scopes.ll | sed -n '/^then:/,/^}/p'
echo "=== gvn";       opt -passes=gvn -S scopes.ll | sed -n '/^then:/,/^}/p'

Output (complete):

=== early-cse
then:                                             ; preds = %entry
  br label %join

else:                                             ; preds = %entry
  %z = mul i32 %a, %b
  br label %join

join:                                             ; preds = %else, %then
  %p = phi i32 [ %x, %then ], [ %z, %else ]
  %w = mul i32 %a, %b
  %r = add i32 %p, %w
  %s = add i32 %r, %x
  %t = mul i32 %s, %x
  ret i32 %t
}
=== gvn
then:                                             ; preds = %entry
  %.pre = mul i32 %a, %b
  br label %join

else:                                             ; preds = %entry
  %z = mul i32 %a, %b
  br label %join

join:                                             ; preds = %else, %then
  %w.pre-phi = phi i32 [ %z, %else ], [ %.pre, %then ]
  %p = phi i32 [ %x, %then ], [ %z, %else ]
  %r = add i32 %p, %w.pre-phi
  %s = add i32 %r, %x
  %t = mul i32 %s, %x
  ret i32 %t
}

What to notice: EarlyCSE, the dominator-scoped value numbering of §6, replaced %y (superlocal: same EBB as %x) and %v (dominated by %x but in another EBB) by %x, and left %w: mul %a, %b is computed on the else path only. GVN, a global method with PRE, made %w fully redundant by inserting %.pre on the then path and a phi. Superlocal numbering (Algorithm 13.1.4) would stop after %y (§3), and the local pebble-lvn of exercise E3 changes nothing in this function.

Source: llvm/lib/Transforms/Scalar/EarlyCSE.cpp, class EarlyCSE, "a simple and fast domtree-based CSE pass" with ScopedHashTables and EarlyCSE::processNode (LLVM 23.1.2) [LLVM-EarlyCSE].

CompCert's verified CSE is superlocal

Reproduce (CompCert 3.15 sources; curl):

CC=https://raw.githubusercontent.com/AbsInt/CompCert/v3.15
curl -sL $CC/backend/CSE.v | sed -n '13,14p'
curl -sL $CC/backend/CSEproof.v | grep -A1 '^Theorem transf_program_correct'

Output (complete):

(** Common subexpression elimination over RTL.  This optimization
  proceeds by value numbering over extended basic blocks. *)
Theorem transf_program_correct:
  forward_simulation (RTL.semantics prog) (RTL.semantics tprog).

What to notice: CompCert's CSE pass is value numbering over extended basic blocks, the superlocal scope of Definition 13.1.2, and it comes with a machine-checked proof that the transformed RTL program simulates the original (Lesson 13.9, [Ler09]).

Constant folding¶

LLVM's constant folder: overflow, UB, NaN, signed zeros, rounding

Reproduce (opt 23.1.2; any OS):

cat > fold.ll <<'EOF'
define i8 @wrap()           { %r = add i8 100, 100            ret i8 %r }
define i8 @wrap_nsw()       { %r = add nsw i8 100, 100        ret i8 %r }
define i32 @div0()          { %r = udiv i32 7, 0              ret i32 %r }
define i32 @int_min_div()   { %r = sdiv i32 -2147483648, -1   ret i32 %r }
define i32 @shift_big()     { %r = shl i32 1, 40              ret i32 %r }
define double @neg_zero()   { %r = fadd double -0.0, 0.0      ret double %r }
define double @nan()        { %r = fdiv double 0.0, 0.0       ret double %r }
define float @round()       { %r = fadd float 16777216.0, 1.0 ret float %r }
define double @mulzero(double %x)      { %r = fmul double %x, 0.0          ret double %r }
define double @mulzero_fast(double %x) { %r = fmul nnan nsz double %x, 0.0 ret double %r }
EOF
opt -passes=instsimplify -S fold.ll | grep -v '^;\|^$\|source_filename'

Output (complete):

define i8 @wrap() {
  ret i8 -56
}
define i8 @wrap_nsw() {
  ret i8 -56
}
define i32 @div0() {
  ret i32 poison
}
define i32 @int_min_div() {
  ret i32 poison
}
define i32 @shift_big() {
  ret i32 poison
}
define double @neg_zero() {
  ret double 0.000000e+00
}
define double @nan() {
  ret double +qnan
}
define float @round() {
  ret float f0x4B800000
}
define double @mulzero(double %x) {
  %r = fmul double %x, 0.000000e+00
  ret double %r
}
define double @mulzero_fast(double %x) {
  ret double 0.000000e+00
}

What to notice: add nsw i8 100, 100 folds to -56, not poison: both refine the poison result (Theorem 13.1.12). udiv 7, 0 and sdiv INT_MIN, -1 are immediate UB and fold to poison (UB is refined by anything; exercise E1 leaves them, as Pebble relies on explicit checks before division). -0.0 + 0.0 is +0.0, 0/0 is +qnan (LLVM 23's new FP literal syntax), and \(2^{24} + 1\) rounds to \(2^{24}\) (f0x4B800000) in float (Proposition 13.1.14). x * 0.0 stays until nnan nsz allow it.

Source: llvm/lib/Analysis/ConstantFolding.cpp — ConstantFoldInstruction, ConstantFoldBinaryOpOperands, ConstantFoldCall; llvm/lib/IR/ConstantFold.cpp — ConstantFoldBinaryInstruction (target-independent part) (LLVM 23.1.2) [LLVM-ConstantFolding].

Target-dependent folding: sizes from the DataLayout, sin() from the host

Reproduce (clang 23.1.2; any OS):

cat > sizeof.ll <<'EOF'
%pair = type { i8, i64 }
define i64 @sizeof_pair() {
  %p = getelementptr %pair, ptr null, i64 1
  %n = ptrtoint ptr %p to i64
  ret i64 %n
}
define double @sin1() {
  %r = call double @llvm.sin.f64(double 1.0)
  ret double %r
}
EOF
for triple in x86_64-unknown-linux-gnu i386-unknown-linux-gnu; do
  echo "=== $triple"
  clang-23 --target=$triple -Wno-override-module -x ir -S -emit-llvm -O1 sizeof.ll -o - | grep -A1 '^define'
done

Output (complete):

=== x86_64-unknown-linux-gnu
define noundef i64 @sizeof_pair() local_unnamed_addr #0 {
  ret i64 16
--
define noundef double @sin1() local_unnamed_addr #0 {
  ret double f0x3FEAED548F090CEE
=== i386-unknown-linux-gnu
define noundef i64 @sizeof_pair() local_unnamed_addr #0 {
  ret i64 12
--
define noundef double @sin1() local_unnamed_addr #0 {
  ret double f0x3FEAED548F090CEE

What to notice: the same IR folds sizeof({i8, i64}) to 16 on x86-64 and 12 on i386, whose DataLayout aligns i64 to 4 bytes: folding GEP arithmetic needs the target. llvm.sin.f64(1.0) folds to the bit pattern of \(\sin 1\) on both, computed by calling the host's sin (ConstantFoldFP(sin, ...) in ConstantFolding.cpp): a cross-compiler whose host libm rounds differently could produce a different constant.

Folding in the front ends: clang and GCC

Reproduce (clang 23.1.2, gcc 13.3.0; Linux):

cat > cf.c <<'EOF'
int overflow(void) { return 2147483647 + 1; }
int divzero(int x) { return x / 0; }
double negzero(void) { return -0.0 + 0.0; }
EOF
clang-23 -O0 -S -emit-llvm cf.c -o - 2>/dev/null | grep -A1 '^define.*@\(overflow\|negzero\)'
gcc -O0 -c cf.c -fdump-tree-original=- -o /dev/null 2>/dev/null | grep -A2 '^{'

Output (complete):

define dso_local i32 @overflow() #0 {
  ret i32 -2147483648
--
define dso_local double @negzero() #0 {
  ret double 0.000000e+00
{
  return -2147483648(OVF);
}
--
{
  return x / 0;
}
--
{
  return 0.0;
}

What to notice: both front ends fold 2147483647 + 1 (with a warning, since signed overflow is UB in C): clang emits ret i32 -2147483648, GCC marks the constant (OVF) (its TREE_OVERFLOW bit) in the GENERIC dump. Neither folds x / 0; both fold -0.0 + 0.0 to 0.0. GCC's folder is gcc/fold-const.cc (const_binop, int_const_binop) at releases/gcc-15.1.0 [GCC-fold-const].

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Local scope (one block)	Only redundancy/constants within a block	\(O(n)\) · fastest	Simple, easy to debug	Lowest	Peepholes, LVN, block-level combiners (SelectionDAG)
Superlocal scope (EBB)	+ facts along EBB paths	\(O(n)\) with a scoped table	Same as local, path by path	Low	CompCert CSE; historical VN
Regional (dominator tree)	+ facts from all dominators	\(O(n)\) + dominator tree	Misses join and partial redundancy	Low–medium	EarlyCSE, DVNT
Global (whole CFG)	Joins, partial redundancy, loops	Iterative dataflow / SSA · slower	Most precise intraprocedural	High	GVN, PRE, SCCP (Ch 14, 17)
Constant folding	Exactly the constant subexpressions	\(O(n + u)\) worklist · negligible	Exact if it models the target; pitfalls in §4	Low per op, high to get every corner right	Everywhere: front ends, IRBuilder, InstSimplify

Choose local scope when the transformation is a peephole or must be very cheap (it also has the simplest correctness proof). Choose superlocal when you want more redundancy without a dominator tree. Choose dominator-based as the default fast CSE in an SSA compiler (it is what LLVM runs early). Choose global methods when joins and loops matter and you can afford dataflow. Choose constant folding always — the question is only how carefully: fold with the target's semantics (APInt/APFloat), never across UB that the language defines as a trap.

9. Assessment¶

Technique	Quiz questions	Drills	Flashcards	Exercises
Optimization scopes	`scope-ebb`, `scope-classify`	`./course drill lvn-table` (local), `./course drill dominators` (Ch 15, for regional)	tag `scopes`	—
Constant folding	`fold-values`, `fold-fp`	`./course drill poison-propagation` (Ch 9), `./course drill rewrite-validity`	tag `constant-folding`	E1 (`pebble-constfold`)

References¶

See the chapter references.

Lesson 13.1 — Optimization scopes and constant folding¶

1. Problem and motivation¶

Optimization scopes¶

Constant folding¶

2. Definitions and algorithms¶

Optimization scopes¶

Constant folding¶

3. Worked example¶

Optimization scopes¶

Constant folding¶

4. Invariants and correctness¶

Optimization scopes¶

Constant folding¶

5. Complexity¶

6. Variants and refinements¶

Optimization scopes¶

Constant folding¶

7. In real compilers¶

Optimization scopes¶

Constant folding¶

8. Comparison¶

9. Assessment¶

References¶