Lesson 23.9 — Code layout: block placement, ext-TSP and branch folding¶

Techniques: Pettis–Hansen code positioning (bottom-up chain merging; LLVM's MachineBlockPlacement); ext-TSP block placement (Newell–Pupyrev); branch folding and tail merging · Drill: code-layout · Prerequisites: Lesson 23.4 (profiled regions), Ch 20 (profiles) · Time: 3 hours

After scheduling, the compiler still chooses the order of the basic blocks in memory. Every edge whose target is the next block is a fall-through, which costs nothing. Every other edge needs a taken branch, which costs a redirect in the front end, a branch-target-buffer entry and, if the target is far away, an instruction-cache line. Placing blocks so that frequent edges fall through and hot code is packed together is worth several percent on large programs: this is what profile-guided layout and post-link optimizers (Lesson 23.10) are mostly about. The same pass also merges identical code (tail merging) and removes branches to branches (branch folding).

The running example is the profiled region of Lesson 23.4 (entry count 100). Here it is with block sizes in bytes:

block	A	B	C	D	E	F	G	H
count	100	70	30	90	10	60	40	100
size (bytes)	16	8	24	16	32	8	16	8

and edges A→B 70, A→C 30, B→D 70, C→D 20, C→E 10, D→F 60, D→G 30, E→G 10, F→H 60, G→H 40.

1. Problem and motivation¶

Pettis–Hansen code positioning¶

Pettis and Hansen's 1990 paper introduced profile-guided code positioning at three levels: procedures (place procedures that call each other often near each other), basic blocks (make frequent edges fall-throughs) and procedure splitting (move never-executed blocks out of line) [PH90]. Their basic-block algorithm merges blocks into chains bottom-up along the heaviest edges. LLVM's MachineBlockPlacement is a descendant: it builds chains of blocks greedily by edge probability, with loop-aware rules, and lays them out with tail duplication where profitable [LLVM-MBP]. GCC's bb-reorder.cc implements trace-based reordering (the software trace cache of Ramírez et al.) and, with -freorder-blocks-algorithm=simple, a simpler variant [GCC-bbreorder]. pebblec gets LLVM's placement at -O1 and above.

Ext-TSP block placement¶

Fall-throughs are not the whole story. A short forward jump is cheaper than a long one because the target is probably in the same cache line. A backward jump in a loop is cheaper than a far one. Newell and Pupyrev modeled this as the extended TSP (ext-TSP) score: fall-throughs count fully, and short forward and backward jumps count partially, decreasing with distance. Their greedy chain-merging algorithm maximizes the score and beats Pettis–Hansen-style layouts on large binaries [NP20]. It is the default layout algorithm of BOLT (Lesson 23.10), and LLVM uses it in MachineBlockPlacement with -enable-ext-tsp-block-placement (from profile data) [LLVM-CodeLayout].

Branch folding and tail merging¶

Other passes leave code with jumps to unconditional jumps, blocks that only jump, and several predecessors that end with the same instructions before jumping to the same block. Branch folding retargets branches past empty blocks and removes the empty ones. Tail merging keeps one copy of a common tail and branches into it, which saves code size at the cost of a jump. LLVM's BranchFolder does both, before and after block placement [LLVM-BranchFolding]. GCC's cross-jumping (-fcrossjumping, try_crossjump_bb in cfgcleanup.cc) is the same idea.

2. Definitions and algorithms¶

Definition 23.9.1 (Layout, fall-through weight)

A layout of a CFG with blocks \(N\) and entry \(r\) is a permutation \(\pi = (b_1, \dots, b_n)\) with \(b_1 = r\). Edge \(u \to v\) is a fall-through in \(\pi\) if \(v\) immediately follows \(u\). The fall-through weight \(\Phi(\pi)\) is the sum of the counts of the fall-through edges.

Pettis–Hansen code positioning¶

Algorithm 23.9.2 (Bottom-up chain merging, after Pettis and Hansen)

Input: a CFG with edge counts.
Output: a layout.
Precondition: none (loops allowed).
Postcondition: a permutation starting at the entry; every edge used to merge two chains is a fall-through (Proposition 23.9.3).
Invariant: the chains partition \(N\); each chain is a path of merge edges.

function PettisHansen(G):
    chain(b) ← [b] for every block
    for (u → v) in edges by decreasing count (ties: by source, then target order):
        if chain(u) ≠ chain(v) and u is the last block of chain(u) and v is the first of chain(v):
            concatenate chain(u) · chain(v)
    place chain(entry) first, then the other chains by decreasing count of their first block
    return the concatenation

Pettis and Hansen order the remaining chains top-down by connection weight. The lab's drill uses the simpler "hottest first" order above, and LLVM uses loop-aware rules (§7).

Proposition 23.9.3 (Chain merging is sound and keeps its merges)

Algorithm 23.9.2 returns a layout, and every edge that caused a merge is a fall-through in it, so \(\Phi(\pi)\) is at least the total count of the merge edges.

Proof

Invariant: initially the chains are singletons. A merge concatenates two different chains at a tail and a head, so the result is again a sequence of distinct blocks, and the chains still partition \(N\). The merge edge \(u \to v\) joins \(u\) (the old tail) directly to \(v\) (the old head). Later merges only add blocks before a head or after a tail, never between two adjacent blocks of a chain, so the adjacency persists. Layout: the output concatenates all chains, each block once, with the entry's chain first. The entry is the head of its chain, because no edge enters the entry (by the convention of Definition 23.9.1; with a back edge to the entry, keep it unmerged). Each merge edge is a fall-through, which gives the bound on \(\Phi\).

Theorem 23.9.4 (Maximum fall-through layout is NP-hard)

Deciding whether a CFG with edge counts has a layout with \(\Phi(\pi) \ge K\) is NP-complete.

Proof

In NP: a layout is a certificate checkable in linear time. Hardness by reduction from the Hamiltonian path problem with a fixed start vertex \(s\) in a directed graph \(H\) (NP-complete, [GJ79, GT39]). Build a CFG with the same vertices and edges, entry \(s\), and count 1 on every edge. A layout has \(\Phi = n - 1\) iff all \(n - 1\) consecutive pairs are edges of \(H\), i.e. iff \(\pi\) is a Hamiltonian path from \(s\). So \(H\) has one iff the CFG has a layout with \(\Phi \ge n - 1\).

Ext-TSP block placement¶

Definition 23.9.5 (Ext-TSP score)

Given block sizes \(s(b)\) and a layout, let \(a(b)\) be the address of \(b\) (sum of the sizes before it) and, for an edge \(u \to v\) with count \(c\), \(e = a(u) + s(u)\) (the end of \(u\)). The edge scores

\[ \mathrm{score}(u \to v) = c \cdot \begin{cases} w_f & \text{if } a(v) = e \ \ (\text{fall-through}), \\ 0.1 \cdot (1 - d/1024) & \text{if } d = a(v) - e \in (0, 1024] \ \ (\text{forward}), \\ 0.1 \cdot (1 - d/640) & \text{if } d = e - a(v) \in (0, 640] \ \ (\text{backward}), \\ 0 & \text{otherwise}, \end{cases} \]

with \(w_f = 1\) for a conditional source (two or more successors) and \(w_f = 1.05\) for an unconditional one (LLVM 23's defaults). The ext-TSP score of the layout is the sum over all edges.

Algorithm 23.9.6 (Greedy ext-TSP chain merging, after Newell and Pupyrev)

Input: a CFG with counts and sizes.
Output: a layout.
Precondition: none.
Postcondition: a layout starting at the entry, with a locally maximal score under the merge moves below.
Invariant: the chains partition \(N\); the entry is the first block of its chain.

function ExtTSP(G):
    chain(b) ← [b] for every block
    loop:
        best ← none
        for each pair of chains X ≠ Y connected by an edge:
            for each split point k of X (if |X| ≤ split threshold, else only k = |X|):
                X1, X2 ← X[..k], X[k..]
                for merged in [X·Y, Y·X, X1·Y·X2, Y·X2·X1, X2·X1·Y]:
                    if the entry is not first in merged when X or Y contains it: skip
                    gain ← Score(merged) − Score(X) − Score(Y)        # only edges inside them
                    if gain > gain(best): best ← (X, Y, merged)
        if best = none or gain(best) ≤ 0: break
        replace X and Y by merged
    return chain(entry) followed by the other chains by decreasing density (count per byte)

Corollary 23.9.7 (Ext-TSP optimization is NP-hard)

Deciding whether a CFG with counts and sizes has a layout with ext-TSP score \(\ge K\) is NP-hard.

Proof

Reduce from the Hamiltonian-path instance of Theorem 23.9.4. Keep its vertices and edges with count 1, add one sink block \(t\) and an edge of count 0 from every vertex to \(t\), and give every block size \(2000\) bytes. Every block now has at least two successors, so every fall-through weighs \(w_f = 1\), and every non-fall-through jump spans at least \(2000 > 1024\) bytes and scores 0. Count-0 edges score 0. So the score of a layout is its number of fall-through edges of count 1, and a layout scores \(n - 1\) (\(n\) the vertices of \(H\)) iff consecutive vertices of \(H\) form a Hamiltonian path from \(s\) (with \(t\) placed last, or anywhere after the path). Hence deciding score \(\ge n - 1\) decides the Hamiltonian path problem.

Branch folding and tail merging¶

Definition 23.9.8 (Common tail)

Two blocks \(P_1, P_2\) that both end with an unconditional jump to (or fall into) the same block \(J\) have a common tail of length \(k\) if their last \(k\) non-branch instructions are identical (same opcodes, operands and memory operands). Tail merging creates a block \(T\) holding the common tail followed by a jump to \(J\), cuts the tail from \(P_1\) and \(P_2\), and makes both jump to \(T\). Branch folding replaces a branch to a block that contains only an unconditional jump by a branch to that jump's target, and deletes blocks that become unreachable.

Algorithm 23.9.9 (Tail merging, after LLVM's BranchFolder)

Input: a function; a minimum tail length \(m\) (-tail-merge-size, default 3).
Output: the function with common tails merged.
Precondition: instructions compare equal only if they have identical semantics (MachineInstr::isIdenticalTo, no side-effect differences).
Postcondition: semantics preserved (Proposition 23.9.10); the size shrinks when \((\#\text{preds} - 1) \cdot k\) exceeds the added jumps.
Invariant: every block still ends with a valid terminator sequence.

function TailMerge(F):
    for each block J with at least 2 predecessors (or all blocks ending in a return):
        group J's predecessors that reach J unconditionally by a hash of their last instruction
        for each group with ≥ 2 blocks:
            (P1, P2, k) ← the pair with the longest common tail
            if k ≥ m (or the tails are whole blocks):
                create T with the common tail; P1, P2 jump to T; T jumps to J
                add any other group member with the same tail

3. Worked examples¶

Pettis–Hansen code positioning¶

Algorithm 23.9.2 on the running region (edges by decreasing count; "tail/head" checks the chain positions):

step	edge (count)	merge?	chain of the source afterwards
1	A→B (70)	yes	A B
2	B→D (70)	yes (B tail, D head)	A B D
3	D→F (60)	yes	A B D F
4	F→H (60)	yes	A B D F H
5	G→H (40)	no: H is not a head any more	G
6	A→C (30)	no: A is not a tail	A B D F H
7	D→G (30)	no: D is not a tail	A B D F H
8	C→D (20)	no: D is not a head	C
9	C→E (10)	yes	C E
10	E→G (10)	yes	C E G

Chains: A B D F H and C E G. Layout: A B D F H C E G, with fall-through weight \(70 + 70 + 60 + 60 + 10 + 10 = 280\) out of the 400 edge executions. The source order A B C D E F G H has only \(70 + 20 + 40 = 130\). LLVM's MachineBlockPlacement produces exactly this layout for the same CFG (§7).

Try it

./course drill code-layout --seed 4 --solution builds Pettis–Hansen chains for a random profiled region and (medium/hard) asks for the fall-through weight and the ext-TSP score of the result.

Ext-TSP block placement¶

The ext-TSP score of both layouts, edge by edge (sizes from the table above; "fall" = fall-through, "fwd d" / "bwd d" = jump distance in bytes):

edge	count	source order	score	Pettis–Hansen order	score
A→B	70	fall	70.00	fall	70.00
A→C	30	fwd 8	2.98	fwd 40	2.88
B→D	70	fwd 24	6.84	fall (uncond. ×1.05)	73.50
C→D	20	fall	20.00	bwd 56	1.83
C→E	10	fwd 16	0.98	fall	10.00
D→F	60	fwd 32	5.81	fall	60.00
D→G	30	fwd 40	2.88	fwd 72	2.79
E→G	10	fwd 8	0.99	fall (×1.05)	10.50
F→H	60	fwd 16	5.91	fall (×1.05)	63.00
G→H	40	fall (×1.05)	42.00	bwd 80	3.50
total			158.39		298.00

For example, A→C in the Pettis–Hansen order jumps from the end of A (byte 16) over B, D, F, H (8 + 16 + 8 + 8 = 40 bytes) to C: \(30 \cdot 0.1 \cdot (1 - 40/1024) = 2.88\). LLVM's ext-TSP implementation chooses the same layout for this region, and a different one from the default placement once the region is inside a loop (§7 box).

Branch folding and tail merging¶

Two predecessors L and R of a return block both end with call g; call h(y); call h(7); call h(8), after different argument setups (g(1) vs g(2)). The longest common tail is the four calls with their argument moves, apart from the first argument of g: \(k = 7\) machine instructions on x86-64 ≥ 3. Tail merging keeps one copy in a new block J, L sets %edi = 1 and jumps to J, and R sets %edi = 2 and falls into J. That saves 7 instructions and costs one jump (§7 box).

4. Invariants and correctness¶

Pettis–Hansen code positioning¶

Layout never changes semantics as long as every edge that is not a fall-through gets an explicit branch. MachineBlockPlacement repairs terminators after placement (updateTerminator), inserting or removing unconditional branches and inverting conditions. Proposition 23.9.3 is the quality statement, and Theorem 23.9.4 explains why every production algorithm is greedy.

Ext-TSP block placement¶

Each merge move of Algorithm 23.9.6 produces a sequence of the blocks of \(X\) and \(Y\), each exactly once, and keeps the entry first. So the invariant holds and the result is a layout. The loop terminates because every accepted merge strictly increases the score of a finite set of layouts, and the number of chains decreases by one per merge.

The best layout for the profile is not the best layout for every input

Both algorithms optimize for the profile they are given. A training input that exercises the wrong path makes the "hot" chain cold at run time. With no profile, LLVM uses static branch probabilities, which are guesses. This is why AutoFDO and post-link tools (Ch 20, Lesson 23.10) collect profiles from production runs.

Branch folding and tail merging¶

Proposition 23.9.10 (Tail merging and branch folding preserve semantics)

After tail merging \(P_1\) and \(P_2\) into \(T\), every execution performs the same sequence of instructions (up to unconditional jumps) as before. After branch folding, the same holds.

Proof

An execution entering \(P_i\) runs its unchanged prefix, jumps to \(T\), runs the common tail (identical instructions, by Definition 23.9.8), and jumps to \(J\), where it would have gone before. Jumps have no effect other than control transfer. The merged tail reads the same registers and memory in both cases, because it was identical in both predecessors and nothing between the prefix and the tail changed. Branch folding replaces "branch to \(X\); \(X\): jump to \(Y\)" by "branch to \(Y\)", removing only a jump from every execution through \(X\), and it deletes only unreachable blocks.

5. Complexity¶

Let \(n\) be the blocks, \(e\) the edges, and \(t\) the split threshold of ext-TSP.

Technique	Time	Notes
Pettis–Hansen chain merging (Alg. 23.9.2)	\(O(e \log e + n)\)	sort, then union-like chain updates (each block moves at most \(O(\log n)\) times if the smaller chain is relinked)
Ext-TSP (Alg. 23.9.6)	naive \(O(n \cdot e \cdot t \cdot n)\); LLVM caches merge gains per chain pair, near-linear in practice for \(n \le\) `-ext-tsp-block-placement-max-blocks`	split moves only for chains up to `-ext-tsp-chain-split-threshold` (128) blocks
Tail merging (Alg. 23.9.9)	\(O(\sum_J \lvert\mathrm{preds}(J)\rvert^2 \cdot k)\) worst case	hashing the last instruction groups candidates; `-tail-merge-threshold` caps predecessors (150)

Justification. Chain merging does one constant-time check per edge after sorting. Ext-TSP evaluates, for each connected chain pair, up to \(5t\) merged sequences whose scores cost the number of edges inside them. Tail merging compares suffixes of all candidate pairs of one group.

Pathological family. A switch with \(p\) cases that all end with the same long tail of \(k\) instructions and jump to the same block: the pairwise tail comparison costs \(\Theta(p^2 k)\). That is why LLVM caps predecessors with -tail-merge-threshold. For layout, Theorem 23.9.4's reduction shows that no greedy algorithm is optimal. A Hamiltonian-path gadget in which the heaviest edges lead into a dead end makes Pettis–Hansen merge the dead end first and lose the long path.

Pettis–Hansen code positioning¶

Procedure ordering (Pettis–Hansen's call-graph clustering; hfsort and C³, Ottoni and Maher [OM17]): place functions that call each other close together, for I-cache and I-TLB locality. It is used by linkers with symbol-ordering files and by BOLT.
Hot/cold splitting (Pettis–Hansen "procedure splitting"; LLVM MachineFunctionSplitter, hot-cold-split): move never-executed blocks into a separate section. This shrinks the hot working set.
Loop-aware chain building (LLVM): build chains inside loops first and rotate loops so that the exit test falls through. It uses frequencies, not just counts.

Ext-TSP block placement¶

CDSort (codelayout::computeCacheDirectedLayout): a function-ordering variant of the same greedy merging with a cache model. It is used for function layout in BOLT and in LLVM.
ext-TSP for size (-apply-ext-tsp-for-size): with different weights, optimize code size instead of speed.

Branch folding and tail merging¶

Hoisting common heads (BranchFolder::HoistCommonCode): the mirror of tail merging, moving identical leading instructions of two successors into their common predecessor.
Machine outlining (MachineOutliner, Ch 20): factor repeated sequences anywhere into functions. Larger savings, and a call per use.

7. In real compilers¶

Pettis–Hansen code positioning¶

MachineBlockPlacement (llvm/lib/CodeGen/MachineBlockPlacement.cpp: buildChain, selectBestSuccessor, buildLoopChains, rotateLoop) builds chains greedily by edge probability, weighted by block frequency, and tail-duplicates during placement (-tail-dup-placement) [LLVM-MBP]. GCC's pass_reorder_blocks (gcc/bb-reorder.cc, the software trace cache algorithm, -freorder-blocks-algorithm=stc) is the default at -O2 [GCC-bbreorder].

LLVM places the running region like Pettis and Hansen

Reproduce (llc 23.1.2):

cat > lay.ll <<'EOF'
declare void @work(i32)
define void @f(i32 %x, i32 %y) !prof !0 {
A:
  call void @work(i32 0)
  %cA = icmp sgt i32 %x, 0
  br i1 %cA, label %B, label %C, !prof !1
B:
  call void @work(i32 1)
  br label %D
C:
  call void @work(i32 2)
  %cC = icmp sgt i32 %y, 0
  br i1 %cC, label %D, label %E, !prof !2
D:
  call void @work(i32 3)
  %cD = icmp sgt i32 %y, 5
  br i1 %cD, label %F, label %G, !prof !3
E:
  call void @work(i32 4)
  br label %G
F:
  call void @work(i32 5)
  br label %H
G:
  call void @work(i32 6)
  br label %H
H:
  call void @work(i32 7)
  ret void
}
!0 = !{!"function_entry_count", i64 100}
!1 = !{!"branch_weights", i32 70, i32 30}
!2 = !{!"branch_weights", i32 20, i32 10}
!3 = !{!"branch_weights", i32 60, i32 30}
EOF
for f in "-disable-block-placement" ""; do printf '%-28s' "== $f"
  llc -O2 -mtriple=x86_64-linux-gnu $f lay.ll -o - | grep -oE '# %[A-H]$' | tr -d '# %' | tr '\n' ' '; echo
done

Output (complete):

== -disable-block-placement A B C D F E G H 
==                          A B D F H C E G

What to notice: the profile (branch_weights) reproduces the counts of the running region. Without placement, the blocks stay close to source order. With MachineBlockPlacement the hot path A B D F H is one chain and C E G follow it: the layout of Algorithm 23.9.2 (the §3 trace), with fall-through weight 280 instead of 130.

Ext-TSP block placement¶

codelayout::computeExtTspLayout and calcExtTspScore in llvm/lib/Transforms/Utils/CodeLayout.cpp implement Algorithm 23.9.6 and Definition 23.9.5 (extTSPScore, with ForwardDistance 1024, BackwardDistance 640, fall-through weights 1.0 and 1.05). MachineBlockPlacement::applyExtTsp uses it when -enable-ext-tsp-block-placement is set and the function has a profile [LLVM-CodeLayout, LLVM-MBP]. BOLT's -reorder-blocks=ext-tsp uses the same library.

Ext-TSP and the default placement, without and with a loop

Reproduce (llc 23.1.2; lay.ll from the previous box; lay2.ll wraps it in a loop):

sed -e 's/^A:/entry:\n  br label %A\nA:/' \
    -e 's/  ret void/  %cH = icmp sgt i32 %x, 9\n  br i1 %cH, label %A, label %X, !prof !4\nX:\n  ret void/' \
    lay.ll > lay2.ll
echo '!4 = !{!"branch_weights", i32 99, i32 1}' >> lay2.ll
for file in lay.ll lay2.ll; do for f in "" "-enable-ext-tsp-block-placement"; do
  printf '%-8s %-34s' $file "$f"
  llc -O2 -mtriple=x86_64-linux-gnu $f $file -o - | grep -oE '# %[A-HX]$' | tr -d '# %' | tr '\n' ' '; echo
done; done

Output (complete):

lay.ll                                     A B D F H C E G 
lay.ll   -enable-ext-tsp-block-placement   A B D F H C E G 
lay2.ll                                    E G H A B D F C X 
lay2.ll  -enable-ext-tsp-block-placement   C E G H A B D F X

What to notice: on the acyclic region both algorithms choose the layout of §3. Inside a loop (H jumps back to A 99 % of the time) both place the latch H right before the header A so that the backedge falls through, but they differ in where the cold blocks go. The default placement rotates the loop and leaves E G at the top, ahead of H, and C at the end. Ext-TSP puts the whole cold region C E G first, because in its score (Definition 23.9.5) the short jumps between C, E, G and H still earn points. Different objectives, different layouts.

Branch folding and tail merging¶

BranchFolder::OptimizeFunction in llvm/lib/CodeGen/BranchFolding.cpp runs TailMergeBlocks, OptimizeBranches and HoistCommonCode, both as the branch-folder pass and inside IfConverter. -enable-tail-merge, -tail-merge-size and -tail-merge-threshold control it [LLVM-BranchFolding]. GCC's equivalent is cross-jumping in gcc/cfgcleanup.cc (try_crossjump_to_edge).

Tail merging two calls sequences

Reproduce (llc 23.1.2):

cat > tm.ll <<'EOF'
declare void @g(i32)
declare void @h(i32)
define void @t(i32 %x, i32 %y) {
entry:
  %c = icmp sgt i32 %x, 0
  br i1 %c, label %L, label %R
L:
  call void @g(i32 1)
  call void @h(i32 %y)
  call void @h(i32 7)
  call void @h(i32 8)
  br label %J
R:
  call void @g(i32 2)
  call void @h(i32 %y)
  call void @h(i32 7)
  call void @h(i32 8)
  br label %J
J:
  ret void
}
EOF
for f in "-enable-tail-merge=false" ""; do echo "== $f"
  llc -O2 -mtriple=x86_64-linux-gnu $f tm.ll -o - | sed -n '/^t:/,/Lfunc_end/p' \
    | grep -vE '^\s*\.(cfi|p2align|size|Lfunc)|^t:|^\s*#\s*--|pushq|popq|^\s*$'
done

Output (complete):

== -enable-tail-merge=false
# %bb.0:                                # %entry
    movl    %esi, %ebx
    testl   %edi, %edi
    jle .LBB0_2
# %bb.1:                                # %L
    movl    $1, %edi
    callq   g@PLT
    movl    %ebx, %edi
    callq   h@PLT
    movl    $7, %edi
    callq   h@PLT
    movl    $8, %edi
    callq   h@PLT
    retq
.LBB0_2:                                # %R
    movl    $2, %edi
    callq   g@PLT
    movl    %ebx, %edi
    callq   h@PLT
    movl    $7, %edi
    callq   h@PLT
    movl    $8, %edi
    callq   h@PLT
    retq
== 
# %bb.0:                                # %entry
    movl    %esi, %ebx
    testl   %edi, %edi
    jle .LBB0_2
# %bb.1:                                # %L
    movl    $1, %edi
    jmp .LBB0_3
.LBB0_2:                                # %R
    movl    $2, %edi
.LBB0_3:                                # %J
    callq   g@PLT
    movl    %ebx, %edi
    callq   h@PLT
    movl    $7, %edi
    callq   h@PLT
    movl    $8, %edi
    callq   h@PLT
    retq

What to notice: without tail merging, the ret was duplicated into both arms, and the arms differ only in their first instruction. The branch folder merges the common tail (7 instructions plus the epilogue, which the filter hides) into .LBB0_3, at the cost of one jmp in L: Algorithm 23.9.9 with \(k \ge\) -tail-merge-size.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Pettis–Hansen code positioning	greedy maximum fall-through; every merge is a fall-through (Proposition 23.9.3); optimum is NP-hard (Theorem 23.9.4)	\(O(e \log e)\)	280/400 fall-through weight on the running region vs 130 in source order	low (LLVM's loop-aware version: high)	LLVM `MachineBlockPlacement`, GCC `bb-reorder`, linkers' function ordering
Ext-TSP block placement	models jump distance too (Definition 23.9.5); NP-hard (Corollary 23.9.7)	greedy with cached gains, near-linear in practice	score 298 vs 158 on the running region; better I-cache use on large binaries [NP20]	moderate (a library)	BOLT's default, LLVM with profiles (`-enable-ext-tsp-block-placement`)
Branch folding and tail merging	removes duplicate tails and jump chains; semantics-preserving (Proposition 23.9.10)	\(O(p^2 k)\) per join worst case, capped	smaller code; one extra jump per merged predecessor	moderate	LLVM `BranchFolder` (twice per pipeline), GCC cross-jumping

Choose Pettis–Hansen-style chains when you have edge frequencies and want a fast, predictable layout. Choose ext-TSP when binaries are large and I-cache or I-TLB misses matter, with a real profile. Choose tail merging when code size matters and the merged tail is not on a hot path that the extra jump would slow down. LLVM weighs this with block frequencies.

9. Assessment¶

Quiz: ph-chains (sequence), fallthrough-weight (number), exttsp-edge (number), layout-np (single), tailmerge-size (number), branchfold-single (single), find-exttsp-distance (number: find it in LLVM, ForwardDistance). Tags pettis-hansen, ext-tsp, branch-folding.
Drills: ./course drill code-layout (Pettis–Hansen chains and layout; fall-through weight; ext-TSP score). Tail merging is checked by the worked example and quiz; its interesting part, instruction equality, needs real machine code.
Flashcards: tags pettis-hansen, ext-tsp, branch-folding.

References¶

See the chapter references.

Lesson 23.9 — Code layout: block placement, ext-TSP and branch folding¶

1. Problem and motivation¶

Pettis–Hansen code positioning¶

Ext-TSP block placement¶

Branch folding and tail merging¶

2. Definitions and algorithms¶

Pettis–Hansen code positioning¶

Ext-TSP block placement¶

Branch folding and tail merging¶

3. Worked examples¶

Pettis–Hansen code positioning¶

Ext-TSP block placement¶

Branch folding and tail merging¶

4. Invariants and correctness¶

Pettis–Hansen code positioning¶

Ext-TSP block placement¶

Branch folding and tail merging¶

5. Complexity¶

6. Variants and refinements¶

Pettis–Hansen code positioning¶

Ext-TSP block placement¶

Branch folding and tail merging¶

7. In real compilers¶

Pettis–Hansen code positioning¶

Ext-TSP block placement¶

Branch folding and tail merging¶

8. Comparison¶

9. Assessment¶

References¶