Lesson 17.7 — CFG simplification and jump threading¶

Techniques: CFG simplification (constant-branch folding, unreachable-block elimination, block merging, empty-block removal, speculation into select; LLVM's SimplifyCFG, the Clean algorithm of Cooper–Torczon); switch-to-lookup-table conversion; jump threading (Mueller–Whalley 1995; LLVM's JumpThreading with LazyValueInfo; GCC's backward threader) · Pebble implements: pebble-simplifycfg (exercise E4): constant branches, unreachable blocks, block merging · Prerequisites: Lesson 17.1 (SCCP leaves constant branches behind), Lesson 17.2 (LVI) · Time: 4–5 hours

1. Problem and motivation¶

Every optimization in this chapter leaves the control-flow graph messier than it found it: SCCP turns conditions into constants, ADCE turns branches into jumps and leaves empty blocks, GVN and PRE split edges. CFG simplification repairs this, and in doing so it enables the next round of dataflow analyses (fewer blocks, fewer joins, longer straight-line code for local optimizations). Jump threading goes one step further: when the outcome of a branch is known on some incoming edge, it duplicates the code in between so that edge jumps straight to the right successor.

CFG simplification¶

The classic formulation is Cooper and Torczon's Clean: fold a branch whose two targets are the same block, remove empty blocks, merge a block into its only predecessor, hoist a branch into an empty predecessor [EaC3, Ch. 10]; iterated to a fixed point it gives a canonical CFG. LLVM's SimplifyCFG does these and dozens more rewrites (sinking common code, turning two-entry phis into select, merging conditional branches) [LLVM-SimplifyCFG]; it is LLVM's most frequently run pass (8 instances in LLVM 23's default<O2> pipeline). pebble-simplifycfg implements the three core rewrites: constant branches, unreachable blocks, block merging.

Switch-to-lookup-table¶

A switch whose cases only select constants is a function from a dense range of integers to constants; it can be replaced by a bounds check and a load from a constant table. SimplifyCFG does this late in the pipeline, when the target can say whether a table is profitable (simplifySwitchLookup) [LLVM-SimplifyCFG].

Jump threading¶

Mueller and Whalley introduced "avoiding conditional branches by code replication": if a block \(B\) ends in a branch whose condition is known when \(B\) is entered from predecessor \(P\), redirect \(P\) to a copy of \(B\) that jumps directly (Mueller–Whalley, PLDI 1995; cited here through its production descendants). LLVM's JumpThreading asks LazyValueInfo (Lesson 17.2) for the value of the condition per predecessor and threads when the duplicated code is small (jump-threading-threshold, default 6 instructions) [LLVM-JumpThreading]; GCC threads in several places, most generally in its backward threader [GCC-TreeSSAPasses].

2. Definitions and algorithms¶

Definition 17.7.1 (CFG rewrites)

Let \(F\) be an SSA function. The core rewrites are: (R1) constant branch: a terminator br i1 c, T, F with constant \(c\), br c, T, T, or switch on a constant becomes br S for the selected successor \(S\); every other successor \(X\) loses the phi entries for this block. (R2) unreachable block: a block not reachable from the entry is deleted; its successors lose their phi entries for it; its values' remaining uses (only in other unreachable blocks, or in phis of such edges) are replaced by poison. (R3) block merge: if \(B \neq \mathrm{entry}\) has exactly one predecessor \(P\), \(P\) ends in br B, and \(B \neq P\), then \(B\)'s phis (one entry each) are replaced by their incoming values, \(P\)'s terminator is removed and \(B\)'s instructions are appended to \(P\); successors' phis naming \(B\) now name \(P\). (R4) empty block: a block containing only br S, whose removal does not make a phi of \(S\) ambiguous, is removed by redirecting its predecessors to \(S\).

Rewrites on @cleanup

In the §3 example br i1 true, label %t, label %f is R1; %island (no predecessors) is R2; %t → %mid → %join become one block by R3.

Algorithm 17.7.3 (SimplifyCFG-lite)

Input: an SSA function.
Output: the function after R1–R3 applied to a fixed point.
Precondition: the function verifies.
Postcondition: no terminator has a constant condition or equal targets; every block is reachable; no block has a single predecessor ending in an unconditional branch to it (except the entry); behavior unchanged (Theorem 17.7.8).
Invariant: the function verifies after every rewrite; the measure \(\lvert N \rvert + \lvert E \rvert + \lvert C \rvert\) (blocks, edges and conditional terminators) never increases, and each round that changes something decreases it (Theorem 17.7.9).

function SimplifyCFGLite(F):
    repeat:
        changed ← false
        for each block B:                                   # R1
            if B's terminator has a constant condition or equal targets:
                S ← selected successor; for each other successor X: X.removePredecessor(B)
                replace the terminator by `br S`; changed ← true
        R ← blocks reachable from the entry                 # R2
        for each block B ∉ R:
            for each successor X ∈ R: X.removePredecessor(B)
            replace remaining uses of B's values by poison; delete B; changed ← true
        for each block B ≠ entry:                            # R3
            if B has exactly one predecessor P ≠ B and P ends in `br B`:
                replace each phi of B by its only incoming value
                rename B to P in the phis of B's successors
                delete P's terminator; move B's instructions to the end of P; delete B; changed ← true
    until not changed

Definition 17.7.4 (Table-convertible switch)

A switch on an integer \(x\) with cases \(c_1 < \dots < c_k\) and a default is table-convertible if every case destination (and the default, or the default is unreachable) leads without side effects to one common block \(J\) where phis select, for each case, a constant \(r_i\). Its table is the array \(T[c - c_1] = r_i\) for \(c = c_i\), filled with the default's constant (or holes) for the other \(c\) in \([c_1, c_k]\); its size is \(c_k - c_1 + 1\).

Algorithm 17.7.5 (Switch to lookup table)

Input: a table-convertible switch (Definition 17.7.4).
Output: a range check, a load from a constant global table, and a phi at \(J\).
Precondition: the table's size is at most a threshold relative to the number of cases (density), and the target considers the table profitable.
Postcondition: the new code yields \(r_i\) for \(x = c_i\) and the default result otherwise (Theorem 17.7.10).
Invariant: none (a single rewrite).

function SwitchToLookup(switch x, J, results r_1..r_k, default d):
    idx ← x − c_1                                            # unsigned
    if idx <u size:  v ← T[idx]      # T a private constant array; holes filled with d
    else:            v ← d            # (or unreachable if the default is)
    replace J's phi by v; delete the case blocks

Definition 17.7.6 (Threadable edge)

Let block \(B\) end in br c, T, F (or a switch). An incoming edge \((P, B)\) is threadable if the value of \(c\) is known to be a constant \(k\) whenever control enters \(B\) from \(P\) — because \(c\) is a phi of \(B\) with a constant incoming value for \(P\), or an expression over such phis, or because LVI proves \(c = k\) on the edge. The threading target is the successor \(S_k\) that \(k\) selects.

Algorithm 17.7.7 (Jump threading)

Input: an SSA function; LazyValueInfo (or phi constants) to evaluate conditions per edge.
Output: the function with threadable edges redirected to copies of \(B\) that jump to \(S_k\).
Precondition: \(B\) is not a loop header whose threading would create irreducible control flow (unless allowed); the number of instructions duplicated is below a threshold.
Postcondition: the function computes the same results (Theorem 17.7.11); the branch in the copy is gone.
Invariant: after each threading step, SSA form is valid (values defined in \(B\) and used after it get phis in their use blocks).

function JumpThread(F):
    repeat until no change:
        for each block B ending in a conditional branch or switch on c:
            partition B's predecessors by the known value of c on the edge (or unknown)
            for each group G of predecessors with known value k (and G ≠ all predecessors):
                if cost(B) > threshold: skip
                B' ← copy of B without the phis; its phis' values for G become plain values
                B' ends in `br S_k`; redirect every P ∈ G from B to B'
                in S_k and the other successors: add phi entries for B'
                repair SSA: every value of B used outside B now gets phis merging it with its copy in B'

3. Worked example¶

CFG simplification¶

Algorithm 17.7.3 on @cleanup (the §7 box; pebble-simplifycfg produces the same final function as LLVM's simplifycfg):

entry:  br i1 true, label %t, label %f
t:      %x = add i32 %a, 1;  br label %mid
mid:    %y = mul i32 %x, 3;  br label %join
f:      %z = sub i32 %a, 1;  br label %join
island: br label %join                                   ; no predecessors
join:   %p = phi i32 [ %y, %mid ], [ %z, %f ], [ 0, %island ];  ret i32 %p

round	rule	change	blocks + edges
—	start		6 + 6 = 12
1	R1	`entry`: `br i1 true` → `br label %t`; `f` loses `entry` as a predecessor	6 + 5
1	R2	reachable: entry, t, mid, join; delete `f` and `island`, `join`'s phi drops their entries: `%p = phi [%y, %mid]`	4 + 3
1	R3	`t` has one predecessor `entry` ending in `br t`: merge into `entry`; then `mid` (its predecessor is now `entry`); then `join`: its phi `%p` is replaced by `%y`	1 + 0
2	—	nothing applies: fixed point	1 + 0

Result: entry: %x = add i32 %a, 1; %y = mul i32 %x, 3; ret i32 %y (§7 box).

Switch-to-lookup-table¶

days of the §7 box: 12 cases \(1 \dots 12\) with constant results, default 0. Table size \(12 - 1 + 1 = 12\) (fully dense), results fit in i8, so LLVM builds @switch.table.days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] as [12 x i8]: idx = month − 1; idx <u 12 selects the table load, otherwise 0. The 13-way branch becomes one comparison and one load.

Jump threading¶

classify of the §7 box after mem2reg:

entry:   %cmp = icmp slt i32 %x, 0;  br i1 %cmp, label %if.then, label %if.else
if.then: br label %if.end
if.else: br label %if.end
if.end:  %neg.0 = phi i32 [ 1, %if.then ], [ 0, %if.else ]
         %mul = mul nsw i32 %x, 2;  store i32 %mul, ptr %out
         %tobool = icmp ne i32 %neg.0, 0;  br i1 %tobool, label %if.then1, label %if.end2

step	action
1	\(B\) = `if.end`, condition `%tobool = icmp ne %neg.0, 0`. From `if.then`: `%neg.0 = 1`, so `%tobool = true` → target `if.then1`. From `if.else`: `%neg.0 = 0` → `false` → `if.end2`. Both predecessor groups are known.
2	cost of `if.end`: `mul`, `store` (the phi and the compare vanish in copies) — below the threshold 6: thread.
3	copy `if.end` for `if.then` (it becomes part of the path to `if.then1`) and for `if.else` (to `if.end2`); the `mul` and the `store` are duplicated (`%mul2` in the box).
4	the now empty `if.then`/`if.else` and the original `if.end` are cleaned up: `entry` branches on `%cmp` directly to the two copies.

The dynamic path has one conditional branch instead of two, at the price of one duplicated mul + store.

4. Invariants and correctness¶

Theorem 17.7.8 (R1–R4 preserve behavior)

Each rewrite of Definition 17.7.1 transforms a verifying SSA function into one that verifies and has the same observable behavior on every input.

Proof

R1. The removed edges are never taken: the condition is a constant (or both targets coincide), so every execution of \(B\) continues to \(S\). Phi entries for removed edges were never selected. SSA stays valid: the remaining edge set is a subset, so dominance only grows (every path in the new CFG is a path in the old). R2. An unreachable block never executes; removing it removes only never-selected phi entries. Uses of its values outside it can only be in blocks it dominates (strict SSA), which are unreachable too, or in phi entries for its outgoing edges, which were removed; any remaining use is in dead code and poison is a refinement there. R3. Every execution of \(B\) comes from \(P\) through the unconditional branch, and every execution of \(P\) continues into \(B\): concatenating the instruction sequences executes the same instructions in the same order. \(B\)'s phis have one entry (single predecessor), so they equal that value. Uses of \(B\)'s values remain dominated: \(P\) dominated everything \(B\) dominated. R4. Redirecting \(B\)'s predecessors to \(S\) skips only br S, provided each phi of \(S\) can take, for a redirected predecessor, the value it took for \(B\) without conflicting with an existing entry from that predecessor — exactly the condition of R4.

Theorem 17.7.9 (SimplifyCFG-lite terminates at a fixed point)

Let \(C\) be the set of conditional terminators (br i1 with two targets, and switch). Algorithm 17.7.3 terminates after at most \(\lvert N \rvert + \lvert E \rvert + \lvert C \rvert + 1\) rounds, and the result has none of the patterns R1–R3 apply to.

Proof

The measure \(\mu = \lvert N \rvert + \lvert E \rvert + \lvert C \rvert\) is a natural number (edges counted with multiplicity, one per successor slot). R1 replaces a conditional terminator by br, so \(\lvert C \rvert\) drops by one (and \(\lvert E \rvert\) usually too; a switch with no cases is the one R1 that keeps its single edge, which is why \(\lvert C \rvert\) is in the measure), R2 removes at least one block, R3 removes one block and one edge; none adds blocks, edges or conditional terminators. So every round that changes anything decreases \(\mu\) by at least 1, and the final round, which changes nothing, certifies that no rule applies to any block.

Theorem 17.7.10 (Lookup tables compute the switch)

Under Definition 17.7.4 and Algorithm 17.7.5, the value at \(J\) equals the value the phi would have selected, for every \(x\).

Proof

Case \(x = c_i\): \(\mathit{idx} = c_i - c_1 \in [0, \mathit{size})\) as an unsigned number, so the table branch is taken and \(T[c_i - c_1] = r_i\) by construction. Case \(x \in [c_1, c_k]\) not a case: the switch takes the default, the table holds the default's constant there. Case \(x \notin [c_1, c_k]\): work modulo \(2^w\), where \(w\) is the bit width. The map \(x \mapsto (x - c_1) \bmod 2^w\) is a bijection of the \(2^w\) bit patterns, and it sends the \(\mathit{size}\) patterns of \([c_1, c_k]\) exactly onto \(\{0, \dots, \mathit{size} - 1\}\). Every other \(x\) therefore lands on an unsigned value \(\geq \mathit{size}\), the check fails and the default is taken. The case blocks had no side effects (Definition 17.7.4), so removing them changes nothing else.

Theorem 17.7.11 (Jump threading preserves behavior)

If the edge value used in Algorithm 17.7.7 is sound (the condition equals \(k\) whenever \(B\) is entered from a predecessor in \(G\)), then after threading every execution performs the same side effects and returns the same value.

Proof

Consider an execution entering \(B\) from \(P \in G\). In the old program it executes \(B\)'s instructions with the phis set to their \(P\) entries, evaluates the condition to \(k\) (soundness) and goes to \(S_k\). In the new program it enters \(B'\), which executes the same instructions with the phis' \(P\) values substituted, and goes to \(S_k\) unconditionally: the same side effects and values. Executions entering from other predecessors see the unchanged \(B\). At \(S_k\) and at blocks after it, values defined in \(B\) now have two definitions (in \(B\) and \(B'\)); the SSA repair step inserts phis selecting the copy by the path taken, so every use reads the value of the block that actually executed — the value the old program had. Successor phis get entries for \(B'\) equal to their entries for \(B\) (with \(B\)'s values replaced by their copies).

What breaks it. Threading through a loop header can turn a natural loop into an irreducible region (two entries), which is why LLVM does not thread across loop headers by default (jump-threading-across-loop-headers=false). Speculating a block into a select (SimplifyCFG's foldTwoEntryPHINode) must not execute instructions that can trap or have side effects on the path that did not execute them.

5. Complexity¶

\(n\) blocks, \(e\) edges, \(I\) instructions, \(t\) the jump-threading duplication threshold.

Technique	Time (worst)	Time (typical)	Space	Justification
SimplifyCFG-lite	\(O((n + e) \cdot (n + e + I))\): at most \(2n + e + 1\) rounds (\(\lvert C \rvert \leq n\)), each linear	2–3 rounds	\(O(n + e)\)	Theorem 17.7.9; each round visits every block once and the reachability walk is linear
Switch to lookup table	\(O(k \log k + \mathit{size})\) for \(k\) cases	linear	\(O(\mathit{size})\) table	sort cases, fill the table
Jump threading	each threading step duplicates at most \(t\) instructions; repeated to a fixed point	few steps per function	code growth up to \(t\) per threaded edge	LVI queries dominate (Lesson 17.2)

Pathological family for jump threading. A chain of \(m\) tests of the same flag, each followed by a small block: if (f) A1; if (f) A2; …; if (f) Am. Each join's branch is known from both predecessors, so threading can turn the chain into two straight paths — but every threading step duplicates the blocks between tests, and without the threshold the code can grow by a factor of 2 per unknown flag when different flags interleave (\(2^m\) paths for \(m\) independent flags tested twice each). The per-block threshold (6 instructions) and the requirement that a whole predecessor group have a known value keep the growth linear in practice. At scale: SimplifyCFG appears 8 times and jump threading twice in LLVM 23's default<O2> pipeline (opt -passes='default<O2>' -print-pipeline-passes).

Speculation into select — a two-entry phi whose arms are cheap and safe becomes a select (the simplifycfg output in the §7 box of jump threading); trade-off: executes both arms.
Sinking and hoisting common code — SimplifyCFG's sinkCommonCodeFromPredecessors, GVN-sink (Lesson 17.5); trade-off: shorter code, fewer scheduling choices.
Switch lowering alternatives — lookup tables, bit tests, jump tables, binary search trees (SelectionDAG's switch lowering, Ch 11); trade-off: memory vs branches.
DFA jump threading — threads across loop back edges for state machines (dfa-jump-threading in LLVM's -O2), duplicating whole paths; trade-off: large code growth for big speedups on interpreters and lexers.
Path duplication and superblocks — more aggressive tail duplication (Ch 23).
Structured simplification (MLIR) — region-based canonicalization of scf ops rather than CFG edits.

7. In real compilers¶

CFG simplification¶

LLVM: llvm/lib/Transforms/Utils/SimplifyCFG.cpp — SimplifyCFGOpt::simplifyOnce removes blocks without predecessors, calls ConstantFoldTerminator, MergeBlockIntoPredecessor, foldTwoEntryPHINode, foldBranchToCommonDest and many more; llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp iterates to a fixed point [LLVM-SimplifyCFG]. GCC's cleanup_tree_cfg (tree-cfgcleanup.cc) does the same after every GIMPLE pass that changes the CFG.

LLVM simplifycfg and pebble-simplifycfg on @cleanup

Reproduce (opt 23.1.2; PebblePasses.so from a solution build of the course, build/<dir>/lib/):

cat > cfg.ll <<'EOF'
define i32 @cleanup(i32 %a) {
entry:
  br i1 true, label %t, label %f   ; constant branch
t:
  %x = add i32 %a, 1
  br label %mid                    ; mid has one predecessor: merge
mid:
  %y = mul i32 %x, 3
  br label %join
f:
  %z = sub i32 %a, 1
  br label %join
island:                            ; no predecessors
  br label %join
join:
  %p = phi i32 [ %y, %mid ], [ %z, %f ], [ 0, %island ]
  ret i32 %p
}
EOF
opt -passes=simplifycfg -S cfg.ll | sed -n '/^define/,/^}/p'

Output:

define i32 @cleanup(i32 %a) {
entry:
  %x = add i32 %a, 1
  %y = mul i32 %x, 3
  ret i32 %y
}

What to notice: the §3 trace's result: R1 folded br i1 true, R2 deleted %f and %island (and the phi entries), R3 merged the chain into entry, and the phi with one entry became %y. opt -load-pass-plugin=<build>/lib/PebblePasses.so -passes=pebble-simplifycfg prints the same function.

Switch-to-lookup-table¶

LLVM: simplifySwitchLookup and shouldBuildLookupTable in llvm/lib/Transforms/Utils/SimplifyCFG.cpp, enabled by the switch-to-lookup option of simplifycfg (set late in the -O2 pipeline) [LLVM-SimplifyCFG].

A switch becomes a table

Reproduce (clang 23.1.2, opt 23.1.2):

cat > sw.c <<'EOF'
int days(int month) {
  switch (month) {
  case 1: return 31; case 2: return 28; case 3: return 31; case 4: return 30;
  case 5: return 31; case 6: return 30; case 7: return 31; case 8: return 31;
  case 9: return 30; case 10: return 31; case 11: return 30; case 12: return 31;
  default: return 0;
  }
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm sw.c -o sw.O0.ll
opt -passes=mem2reg -S sw.O0.ll -o sw.ll
opt -passes='simplifycfg<switch-to-lookup>' -S sw.ll | sed -n '/^@switch/p;/^define/,/^}/p'

Output:

@switch.table.days = private unnamed_addr constant [12 x i8] c"\1F\1C\1F\1E\1F\1E\1F\1F\1E\1F\1E\1F", align 4
define dso_local i32 @days(i32 noundef %month) #0 {
entry:
  %switch.tableidx = sub i32 %month, 1
  %0 = icmp ult i32 %switch.tableidx, 12
  br i1 %0, label %switch.lookup, label %return

switch.lookup:                                    ; preds = %entry
  %1 = zext nneg i32 %switch.tableidx to i64
  %switch.gep = getelementptr inbounds [12 x i8], ptr @switch.table.days, i64 0, i64 %1
  %switch.load = load i8, ptr %switch.gep, align 1
  %switch.ext = zext i8 %switch.load to i32
  br label %return

return:                                           ; preds = %entry, %switch.lookup
  %retval.0 = phi i32 [ %switch.ext, %switch.lookup ], [ 0, %entry ]
  ret i32 %retval.0
}

What to notice: Algorithm 17.7.5 exactly: idx = month − 1, the unsigned range check idx <u 12 (Theorem 17.7.10's argument for out-of-range values), and a table of i8 (the results fit) — \1F is 31, \1C is 28, \1E is 30.

Jump threading¶

LLVM: llvm/lib/Transforms/Scalar/JumpThreading.cpp — JumpThreadingPass::processThreadableEdges groups predecessors by computeValueKnownInPredecessors (which asks LVI), threadEdge duplicates the block and repairs SSA; the jump-threading-threshold option bounds the duplicated size [LLVM-JumpThreading]. GCC: gcc/tree-ssa-threadbackward.cc, class back_threader, which searches backwards from a branch for paths on which its condition is constant, using Ranger.

jump-threading duplicates a block to skip a known branch

Reproduce (clang 23.1.2, opt 23.1.2):

cat > jt.c <<'EOF'
int classify(int x, int *out) {
  int neg;
  if (x < 0)
    neg = 1;
  else
    neg = 0;
  *out = x * 2;       // work between the two tests
  if (neg)            // the same decision again: known on each incoming edge
    return -1;
  return 1;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm jt.c -o jt.O0.ll
opt -passes=mem2reg -S jt.O0.ll -o jt.ll
opt -passes=jump-threading -S jt.ll | sed -n '/^define/,/^}/p'

Output:

define dso_local i32 @classify(i32 noundef %x, ptr noundef %out) #0 {
entry:
  %cmp = icmp slt i32 %x, 0
  br i1 %cmp, label %if.then1, label %if.end2

if.then1:                                         ; preds = %entry
  %mul2 = mul nsw i32 %x, 2
  store i32 %mul2, ptr %out, align 4
  br label %return

if.end2:                                          ; preds = %entry
  %mul = mul nsw i32 %x, 2
  store i32 %mul, ptr %out, align 4
  br label %return

return:                                           ; preds = %if.end2, %if.then1
  %retval.0 = phi i32 [ -1, %if.then1 ], [ 1, %if.end2 ]
  ret i32 %retval.0
}

What to notice: the §3 trace: the second test is gone, entry branches straight to the two outcomes, and the mul + store of if.end were duplicated (%mul2). (Running simplifycfg instead turns the same function into two selects — speculation, §6 — with no duplication and no branch at all.)

Find where LLVM does it. In llvm/lib/Transforms/Scalar/JumpThreading.cpp, what is the name and default of the command-line option that limits how many instructions a block may have to be duplicated? (Quiz llvm-where-jt-threshold.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
CFG simplification	Canonical CFG: no constant branches, no unreachable blocks, no mergeable chains	rounds × linear · cheap, run often	Fewer blocks and edges; `select`s	Low for the core rules, high for LLVM's full set	After every CFG-changing pass (LLVM 8× at `-O2`)
Switch-to-lookup-table	Dense constant switches only	\(O(k \log k + \mathit{size})\)	A constant table + range check	Medium (profitability, holes, types)	Late SimplifyCFG in LLVM
Jump threading	Removes branches whose outcome is known per edge (with LVI: ranges, predicates)	LVI queries + bounded duplication	Duplicated blocks	Medium–high (SSA repair, loop headers)	LLVM `jump-threading` 2× at `-O2`; GCC threaders

Choose CFG simplification after any pass that folds conditions or deletes code: it is cheap and makes every later analysis faster. Choose lookup tables when a switch maps a dense range to constants and the target loads cheaply. Choose jump threading when correlated branches (the same flag or range tested twice) sit on hot paths and the duplicated code is small.

9. Assessment¶

Quiz: simplifycfg-rounds, simplifycfg-merge (tag simplifycfg); lookup-table-size, lookup-range-check (tag switch-lookup); jt-known-edge, llvm-where-jt-threshold (tag jump-threading).
Drill: none of this chapter's drills generates CFG-rewrite problems: the rewrites are local and their outcomes are checked by the E4 tests on concrete IR; the quiz asks for the rounds, the table and the threaded edges on given functions.
Flashcards: tags simplifycfg, switch-lookup, jump-threading.
Exercises: E4 pebble-simplifycfg.

References¶

See the chapter references.

Lesson 17.7 — CFG simplification and jump threading¶

1. Problem and motivation¶

CFG simplification¶

Switch-to-lookup-table¶

Jump threading¶

2. Definitions and algorithms¶

3. Worked example¶

CFG simplification¶

Switch-to-lookup-table¶

Jump threading¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

7. In real compilers¶

CFG simplification¶

Switch-to-lookup-table¶

Jump threading¶

8. Comparison¶

9. Assessment¶

References¶