Lesson 23.4 — Region scheduling: traces, superblocks and treegions¶

Techniques: trace scheduling with compensation (bookkeeping) code; superblock formation by tail duplication and superblock scheduling; treegion formation and scheduling (with GCC's region scheduler) · Drill: trace-select · Prerequisites: Lesson 23.3 (list scheduling), Ch 15 (dominance, post-dominance, regions), Ch 20 (profiles) · Time: 4–5 hours

Basic blocks in integer code are short: five or six instructions between branches is typical. A list scheduler working on one block at a time has little to reorder, and a 4-wide or 8-wide machine stays mostly idle. Region schedulers treat several blocks as one scheduling unit. They pick a region along the most frequently executed path, schedule it as if it were a single block, and then repair the paths that leave or enter the region in the middle. The three classic region shapes differ in how much repair they need. A trace (any path) needs compensation code on its side entrances and side exits. A superblock (a trace with no side entrances, obtained by duplicating code) needs repair only at exits. A treegion (a tree of blocks) needs no repair at joins at all, because it has none. These ideas came from VLIW compilers, but they live on wherever a compiler duplicates tails (GCC's tracer, LLVM's tail duplication in block placement) or schedules across blocks (GCC's region and selective schedulers).

The running example is the profiled CFG below: an acyclic region with edge counts from a profile (Ch 20). Each block holds a few operations:

flowchart TD
  A([A 100]) -->|70| B[B 70]
  A -->|30| C[C 30]
  B -->|70| D[D 90]
  C -->|20| D
  C -->|10| E[E 10]
  D -->|60| F[F 60]
  D -->|30| G[G 40]
  E -->|10| G
  F -->|60| H[H 100]
  G -->|40| H

A: x = load p;  br cA, B, C        E: z = 0;  jmp G
B: y = x + 1;   jmp D              F: w = z + 3;  jmp H
C: y = x - 1;   br cC, D, E        G: w = z - 3;  jmp H
D: z = y * 2;   br cD, F, G        H: store q, w

1. Problem and motivation¶

Trace scheduling¶

Fisher invented trace scheduling to compact horizontal microcode, and it became the basis of the first VLIW compilers [Fis81]. A trace is a path through the CFG, chosen from profile data as the most likely one. The scheduler treats the trace as one long block, so an operation can move across the branches and joins inside it. Every such move may break an off-trace path, so the scheduler inserts compensation (bookkeeping) code there. Ellis's Bulldog compiler worked out the bookkeeping rules and the engineering in full [Ell85]. The Multiflow TRACE compilers used it in production, and GCC's selective scheduler still generates bookkeeping copies [LFK+93, GCC-selsched]. pebblec does not trace-schedule: LLVM has no global scheduler, and it gets the effect partly from tail duplication during block placement (Lesson 23.9) and from out-of-order hardware.

Superblock scheduling¶

Most of the complexity of trace scheduling lies in the join compensation needed at side entrances. Hwu and his colleagues removed side entrances altogether. Tail duplication copies the part of the trace after the first side entrance, so that the off-trace paths enter the copy instead. The result is a superblock: a trace with one entry and several exits [HMC+93]. Scheduling a superblock only needs to handle side exits, typically by speculating operations above branches when that is safe. The IMPACT compiler used superblocks throughout, and GCC's -ftracer forms them for the benefit of later passes [GCC-tracer].

Treegion scheduling¶

A trace or superblock follows one path, so ops from the less likely successor of a branch get no benefit. Havanki, Banerjia and Conte proposed the treegion: a tree-shaped region of blocks in which every block except the root has exactly one predecessor [HBC98]. A treegion has no joins, so moving an op upward from a block into any ancestor never needs join compensation, and all paths through the tree benefit. Treegions need no profile to form. GCC's interblock scheduler (sched-rgn.cc, after Bernstein and Rodeh [BR91]) schedules acyclic regions of blocks with speculative motion upward from dominated blocks, and its extended-basic-block scheduler (sched-ebb.cc) schedules the same tree-shaped extended basic blocks along one path.

2. Definitions and algorithms¶

Definition 23.4.1 (Profiled region, trace, side exits and entrances)

A profiled region is an acyclic CFG \((N, E, r)\) with entry \(r\), an execution count \(\mathrm{cnt}(u \to v)\) per edge and \(\mathrm{cnt}(v) = \sum_u \mathrm{cnt}(u \to v)\) (the entry count is given). A trace is a path \(T = b_0 \to b_1 \to \dots \to b_k\). A side exit of \(T\) is an edge \(b_i \to v\) with \(v \ne b_{i+1}\) (for \(i < k\)). A side entrance is an edge \(u \to b_i\) with \(i \ge 1\) and \(u \ne b_{i-1}\). A superblock is a trace without side entrances.

Definition 23.4.2 (Mutual most likely)

For an edge \(u \to v\), \(v\) is \(u\)'s most likely successor if \(\mathrm{cnt}(u \to v)\) is maximal among \(u\)'s outgoing edges, and \(u\) is \(v\)'s most likely predecessor if it is maximal among \(v\)'s incoming edges (ties: the block earlier in a fixed topological order). The edge is mutually most likely if both hold.

Trace scheduling¶

Algorithm 23.4.3 (Trace selection, mutual most likely)

Input: a profiled region.
Output: a partition of \(N\) into traces, in the order they were selected.
Precondition: the region is acyclic (loops are handled by selecting inside loop bodies, or by unrolling first).
Postcondition: every block lies on exactly one trace, and consecutive blocks of a trace are joined by a mutually most likely edge with a nonzero count.
Invariant: visited is the union of the traces selected so far.

function SelectTraces(region):
    traces ← []; visited ← ∅
    while visited ≠ N:
        seed ← the unvisited block with the largest cnt (ties: earliest)
        T ← [seed]; visited ← visited ∪ {seed}
        cur ← seed
        loop:                                             # grow forward
            s ← most likely successor of cur
            if s undefined or s ∈ visited or cnt(cur→s) = 0 or cur ≠ most likely predecessor of s:
                break
            append s to T; visited ← visited ∪ {s}; cur ← s
        cur ← seed
        loop:                                             # grow backward
            p ← most likely predecessor of cur
            if p undefined or p ∈ visited or cnt(p→cur) = 0 or cur ≠ most likely successor of p:
                break
            prepend p to T; visited ← visited ∪ {p}; cur ← p
        traces.append(T)
    return traces

To schedule a trace, you schedule its operations as if they formed one block. The dependence DAG gets extra edges that no operation may cross: a branch stays in order with other branches, a store stays below the branches before it, and an operation that writes a register live on a side exit stays below that exit. Then you repair the off-trace paths. What must be repaired depends on how an operation moved relative to the trace's splits (blocks with side exits) and joins (blocks with side entrances).

Definition 23.4.4 (Code motion across splits and joins)

Let operation \(x\) originate in block \(b_i\) of a trace and be scheduled in block \(b_j\).

Upward across a split (\(j < i\) and some \(b_l\), \(j \le l < i\), has a side exit): \(x\) now runs on the side-exit path too (speculation).
Downward across a split (\(j > i\) and some \(b_l\), \(i \le l < j\), has a side exit): the side-exit path no longer runs \(x\).
Upward across a join (\(j < i\) and some \(b_l\), \(j < l \le i\), has a side entrance): the path entering at \(b_l\) no longer runs \(x\).
Downward across a join (\(j > i\) and some \(b_l\), \(i < l \le j\), has a side entrance): the path entering at \(b_l\) now runs \(x\) too.

Algorithm 23.4.5 (Trace scheduling with compensation, after Fisher and Ellis)

Input: a profiled region; a machine model; a list scheduler (Algorithm 23.3.2).
Output: a new region in which every trace is compacted, plus compensation blocks.
Precondition: traces from Algorithm 23.4.3, scheduled hottest first; operations already scheduled in an earlier trace are frozen.
Postcondition: every path of the new region computes the same results as the corresponding path of the old one (Theorem 23.4.10).
Invariant: after each trace, the region is semantically equivalent to the original.

function TraceSchedule(region):
    for T in SelectTraces(region):
        G ← dependence DAG of T's operations (Lesson 23.2), plus:
            branches totally ordered; stores and other side effects stay below earlier branches;
            x may not move above a split where x's destination is live on the side exit
            (unless it can be renamed) and x may not move above a split if it may trap;
            x may not move below a join                                          # rule R4
        σ ← ListSchedule(G)                                     # one "block" of cycles
        rebuild T from σ; each branch ends the block of the cycle it is scheduled in
        for each x moved downward across a split with side exit e:       # rule R2
            copy x onto e (into a new block on e), if x's result is live there
        for each x moved upward across a join with side entrance e:      # rule R3
            copy x onto e
        # rule R1: upward across a split needs no copy (it is speculation, legal by the DAG)
        freeze the operations of T

Superblock scheduling¶

Algorithm 23.4.6 (Tail duplication)

Input: a profiled region; a trace \(T = b_0, \dots, b_k\).
Output: a region in which \(T\) is a superblock.
Precondition: \(T\) is a path.
Postcondition: \(T\) has no side entrance, and the region's paths are in one-to-one correspondence with the old ones, block by block, up to replacing \(b_l\) by its copy \(b'_l\) (Theorem 23.4.11).
Invariant: the copies \(b'_i, \dots, b'_l\) made so far form a path whose only entrances are the redirected side entrances.

function TailDuplicate(region, T):
    i ← the smallest index ≥ 1 with a side entrance into b_i; if none: return
    for l in i..k: b'_l ← copy of b_l (same operations and branches)
    for l in i..k−1: the edge b'_l → b'_{l+1} replaces the copy of b_l → b_{l+1}
    for l in i..k: every other successor edge of b'_l goes where b_l's goes (off-trace targets)
    for every side entrance u → b_l (l ≥ i): redirect it to u → b'_l
    split the counts: cnt(b'_l) ← the counts of the paths now entering the copies

Definition 23.4.7 (Superblock scheduling)

Superblock scheduling list-schedules a superblock's operations as one block. The DAG includes the control edges of its side exits: an operation may move above a side exit only if it is speculable (no trap, no store, no write to a register live on the exit). Only rule R2 of Algorithm 23.4.5 (downward across a split) can require compensation, and superblock schedulers usually forbid that motion instead.

Treegion scheduling¶

Definition 23.4.8 (Treegion)

A treegion is a set of blocks forming a tree under the CFG edges, whose root has zero or several predecessors and whose every other block has exactly one predecessor (its parent). The treegion partition of a region puts every block \(v\) with \(\lvert \mathrm{preds}(v) \rvert \ne 1\) at the root of its own treegion and every other block in its unique predecessor's treegion.

Algorithm 23.4.9 (Treegion formation and scheduling)

Input: a region in topological order; a machine model.
Output: the treegion partition; each treegion scheduled.
Precondition: acyclic region.
Postcondition: each block is in exactly one treegion; every motion is upward from a block to an ancestor in the same treegion, and speculable.
Invariant: when block \(v\) is visited, the treegion of its unique predecessor is already known.

function Treegions(region):
    for v in topological order:
        owner[v] ← v if |preds(v)| ≠ 1 else owner[the predecessor of v]
    return the groups of blocks with the same owner

function ScheduleTreegion(R):
    for each path P from the root of R to a leaf, most frequent first:
        list-schedule P's operations as one block, allowing motion of a speculable
        operation from a block to any ancestor; operations already placed in a shared
        ancestor by an earlier path are frozen

3. Worked examples¶

Trace scheduling¶

Algorithm 23.4.3 on the running region. The counts are \(\mathrm{cnt}\): A 100, B 70, C 30, D 90, E 10, F 60, G 40, H 100.

step	seed (count)	forward growth	backward growth	trace
1	A (100; tie with H, A is earlier)	A→B (70, B's only pred) ✓; B→D (70 > C→D 20) ✓; D→F (60 > 30) ✓; F→H (60 > G→H 40) ✓; H has no successor	A has no predecessor	A B D F H
2	G (40)	G→H: H visited, stop	most likely pred of G is D (30 > 10): visited, stop	G
3	C (30)	C→D (20 > C→E 10): D visited, stop	C's pred A visited, stop	C
4	E (10)	E→G visited	E→C: C visited	E

The first trace has side entrances C→D (20) and G→H (40), and side exits A→C, D→G. Its operations, with the heights of a toy machine where load takes 3 cycles and ALU ops 1, are x = load p, y = x + 1, z = y * 2, w = z + 3, store q, w, and the branches br cA, br cD. The chain load → add → mul → add → store is the critical path. Trace scheduling produces, for example:

move	from → to	kind (Definition 23.4.4)	repair
`z = y * 2`	D → B	upward across the join at D (side entrance C→D)	copy `z = y * 2` onto C→D (R3)
`w = z + 3`	F → D	upward across the split at D (side exit D→G)	none: on the G path `w` is redefined before any use, so the speculative value is dead (R1)
`store q, w`	stays in H	moving it above the join at H would lose it on the G→H path; moving a store above a split is forbidden	—

After scheduling, the trace is A: x = load p; br cA; B: y = x + 1; z = y * 2; D: w = z + 3; br cD; F: (empty); H: store q, w. The C→D edge gets a new block with z = y * 2. The G path still computes w = z - 3 from the z of its own path (the copy on C→D provides it when coming from C; the E path defines z itself, as the listing says). The region runs the hot path one cycle shorter per moved operation that fills a slot, and the cold C path pays for one extra block.

Superblock scheduling¶

Tail duplication of trace 1 (Algorithm 23.4.6). The first side entrance is into D (from C), so D, F and H are copied into D′, F′, H′. C→D becomes C→D′ and G→H becomes G→H′. D′→F′ and D′→G remain, and so do F′→H′ and E→G.

flowchart TD
  A([A]) --> B[B]
  A --> C[C]
  B --> D[D]
  D --> F[F]
  F --> H[H]
  C --> D2[D']
  C --> E[E]
  D --> G[G]
  D2 --> F2[F']
  D2 --> G
  E --> G
  F2 --> H2[H']
  G --> H2
  classDef hl fill:#fde68a,stroke:#b45309;
  class A,B,D,F,H hl;

Now A B D F H (highlighted) has a single entry: scheduling it needs no join compensation, and z = y * 2 can move from D to B without any copy. The cost is three duplicated blocks (D′, F′, H′), about ⅜ of the region.

Treegion scheduling¶

Algorithm 23.4.9: D, G and H have two predecessors each, so they are roots. A is the entry. B, C and E have one predecessor and join the treegion of that predecessor:

block	preds	owner
A	—	A (entry)
B	A	A
C	A	A
D	B, C	D (join)
E	C	A
F	D	D
G	D, E	G (join)
H	F, G	H (join)

Treegions: {A, B, C, E}, {D, F}, {G}, {H}. Within {A, B, C, E}, y = x + 1 (B) and y = x - 1 (C) can both move up into A only if renamed (both write y, and each is live on the other's path). Within {D, F}, w = z + 3 can move into D as speculation, as in the trace example, with no copy.

Try it

./course drill trace-select --seed 2 --solution generates a profiled region and asks for the traces, the blocks tail duplication copies for the first trace, and the treegions.

4. Invariants and correctness¶

Trace scheduling¶

Theorem 23.4.10 (Compensation preserves semantics)

Suppose the list scheduler respects the DAG of Algorithm 23.4.5 (including its extra edges) and rules R2 and R3 insert their copies. Then along every path through the new region, each operation of the corresponding old path executes exactly once, in an order consistent with its dependences, except speculated operations, which may also execute on paths where their result is dead.

Proof sketch (full treatment: [Ell85], [Fis81])

Fix a path \(P\) of the old region and look at an operation \(x\) that originated in a block \(b_i\) of the trace. If \(P\) contains \(b_i\) it follows the trace for a contiguous stretch around \(b_i\). If \(x\) moved within that stretch, \(P\) still executes it. If \(x\) moved up past a join where \(P\) enters the trace, \(P\) would miss it, and R3 puts a copy on exactly that entrance edge. If \(x\) moved down past a split where \(P\) leaves, \(P\) would miss it, and R2 puts a copy on that exit edge. Moves down past a join are forbidden (R4), so no path gains a non-speculative execution. If \(P\) does not contain \(b_i\), it can only execute \(x\) if \(x\) moved up past a split where \(P\) leaves, which the DAG allows only for speculable \(x\) whose result is dead on \(P\). The order argument is Theorem 23.2.11 applied to the trace's DAG for the on-trace part, and to the new edge blocks, which keep their operations in original order, for the copies. An induction over traces (earlier traces are frozen and already correct) gives the theorem for the whole schedule.

Superblock scheduling¶

Theorem 23.4.11 (Tail duplication preserves semantics)

After Algorithm 23.4.6 there is a bijection between the paths of the old and the new region that maps each block to itself or to its copy, and corresponding paths execute the same operations in the same order. In the new region the trace has no side entrance.

Proof

Map a new path to an old one by replacing every copy \(b'_l\) by \(b_l\). It is a path of the old region: every edge \(b'_l \to b'_{l+1}\) maps to \(b_l \to b_{l+1}\), every other edge out of a copy maps to the same edge out of the original, and every redirected entrance \(u \to b'_l\) maps to the old side entrance \(u \to b_l\). Conversely, given an old path, walk it. While it is on the trace from \(b_0\) it stays on the originals. The first time it enters the trace through a side entrance at \(b_l\) (\(l \ge i\)) it continues in the copies until it leaves them through an off-trace edge. These two maps are inverse to each other, because the copies' only entrances are the redirected side entrances (the invariant) and the originals \(b_i..b_k\) keep only the entrance from \(b_{i-1}\). A copy contains the same operations as its original, so corresponding paths execute the same sequence. For the last claim: \(b_1 .. b_{i-1}\) had no side entrances by the choice of \(i\), and all side entrances of \(b_i..b_k\) were redirected.

Superblocks move the problem, they do not remove it

The duplicated tail (D′, F′, H′) has joins of its own: G→H′ enters the copy of H from G. If a second trace is selected through the copies, it has side entrances again. Compilers stop after the hot trace or limit duplication by size (--param tracer-max-code-growth in GCC, 100 % by default), because repeating tail duplication for every trace approaches path duplication.

Treegion scheduling¶

Proposition 23.4.12 (Treegions need no join compensation)

The treegion partition puts each block in exactly one treegion, and each treegion is a tree rooted at its root. Moving a speculable operation from a block \(v\) to an ancestor \(a\) in the same treegion changes the result of no path.

Proof

Partition: by induction in topological order each block gets exactly one owner, and every non-root block's owner equals its parent's, so following parents from any block reaches its root without leaving the group. The group is a tree because every non-root block has exactly one parent. Motion: a path that reaches \(v\) passes through \(a\) (every block in a treegion is reached only via its parent), so it still executes the operation, earlier, and it still executes every operation of \(v\) it depends on, which the DAG keeps above it. A path that passes through \(a\) but not \(v\) now executes the operation too, and because the operation is speculable its result is dead there and it has no side effect. No block other than the root has a second entry, so no path enters below \(a\) and misses the moved operation.

5. Complexity¶

Let \(n\) be the blocks, \(e\) the edges, \(s\) the operations in a region and \(\delta\) the maximum out-degree.

Technique	Time	Space	Code growth
Trace selection (Alg. 23.4.3)	\(O(n \log n + e)\) with a max-heap for seeds	\(O(n + e)\)	none
Trace scheduling (Alg. 23.4.5)	list scheduling of each trace, \(O((s + e_{\mathrm{DAG}}) \log s)\) in total, plus copies	\(O(s)\)	compensation copies: up to (side entrances) × (ops moved above them) per trace
Tail duplication (Alg. 23.4.6)	\(O(\text{size of the tail})\)	the copies	at most the trace length per superblock
Treegion formation (Alg. 23.4.9)	\(O(n + e)\)	\(O(n)\)	none

Justification. Selection visits every block once as part of a trace and inspects each edge a constant number of times (once for its source's most-likely successor, once for its target's most-likely predecessor); picking seeds from a heap keyed by count costs \(\log n\) each. Formation of treegions is one pass in topological order.

Pathological family (code growth). Take a chain of \(k\) diamonds \(A_i \to \{B_i, C_i\} \to J_i \to A_{i+1}\). There are \(2^k\) paths. Tail duplication of the hottest trace copies at most \(3k\) blocks. But if you keep selecting traces and making each a superblock, every trace through the copies meets new side entrances, and making every path a superblock (full path duplication) creates \(2^k\) superblocks of \(\Theta(k)\) blocks each, \(\Theta(k 2^k)\) blocks in total. Compensation code grows the same way in trace scheduling. Ellis measured it staying modest on real code in Bulldog [Ell85], but the worst case is why every compiler bounds duplication by a growth budget (GCC tracer-max-code-growth, LLVM -tail-dup-size).

Trace scheduling¶

Selective scheduling (Moon and Ebcioğlu [ME92]; GCC sel-sched.cc): moves operations upward through the CFG one "fence" at a time, over any path, generating bookkeeping copies and renaming registers when needed. It is more general than traces, and more expensive.
Percolation scheduling (Nicolau 1985): a set of local transformations (move-op, move-test, unify) that compose into global motion, with correctness proved per transformation.

Superblock scheduling¶

Profile-free superblocks (GCC -ftracer uses static estimates when there is no profile): cheaper to deploy, less accurate.
Superblock loop unrolling and peeling [HMC+93]: unroll the superblock of a loop body to expose more operations. Code growth trades against ILP.
General speculation with recovery (sentinel scheduling, IA-64 ld.s/chk.s): moves trapping loads above branches and defers the exception. Needs architectural support.

Treegion scheduling¶

Tail duplication into treegions [HBC98]: duplicate joins to make treegions larger. The same growth trade-off as superblocks.
Region scheduling on acyclic regions (Bernstein and Rodeh [BR91], GCC sched-rgn.cc): schedule a region of blocks with motion from dominated or equivalent blocks, speculative when the target does not post-dominate. It is more general than trees, and it needs more careful liveness checks.
Extended-basic-block scheduling (GCC sched-ebb.cc, -fsched2-use-superblocks): schedule along one path of a tree-shaped extended basic block.

7. In real compilers¶

Trace scheduling¶

GCC's selective scheduler (gcc/sel-sched.cc, move_op, generate_bookkeeping_insn) is the production descendant of trace scheduling: it moves instructions up across joins and emits bookkeeping copies on the other incoming edges [GCC-selsched]. It was developed for IA-64 and is optional elsewhere (-fselective-scheduling2). LLVM has no trace scheduler.

Bookkeeping copies in GCC's selective scheduler

Reproduce (gcc 14.2.0 on x86-64 Linux):

cat > reg.c <<'EOF'
long f(long *a, long n, long x) {
  long s = 0;
  for (long i = 0; i < n; i++) {
    long v = a[i];
    if (__builtin_expect(v > x, 1))
      s += v * 3;
    else
      s -= v >> 1;
    if (v & 1)
      s ^= i;
  }
  return s;
}
EOF
gcc-14 -O2 -fselective-scheduling2 -fsched-verbose=6 -fdump-rtl-sched2 -c reg.c -o reg.o
grep -E 'Best expression \(vliw|Generating bookkeeping|Scheduled [0-9]+ bookkeeping' reg.c.*r.sched2 \
  | grep -B1 -E 'Generating|Scheduled [1-9]'

Output (complete):

Best expression (vliw form): [((78;{cx=cx&0x1;clobber flags;};)type:use;count:6;)prio:5;orig_bb:6;]; cycle 5
Generating bookkeeping insn (5->6)
--
Best expression (vliw form): [((79;{cx=-cx;clobber flags;};)type:use;count:5;)prio:4;orig_bb:6;]; cycle 7
Generating bookkeeping insn (8->6)
--
Best expression (vliw form): [((39;pc={(flags!=0)?L37:pc};)type:jump_insn;count:4;)prio:1;orig_bb:10;]; cycle 12
Scheduled 2 bookkeeping copies, 2 insns needed bookkeeping, 0 insns renamed, 0 insns substituted

What to notice: insns 78 and 79 belong to block 6, the join after the if/else (they compute -(v & 1), the mask for s ^= i). The scheduler moved each up into one arm of the if, above the join, and generated a bookkeeping copy on the other incoming edge (5->6, 8->6): rule R3 of Algorithm 23.4.5. The last line counts two copies for the region.

Superblock scheduling¶

GCC's tracer (gcc/tracer.cc, tail_duplicate, find_trace) forms superblocks by tail duplication on GIMPLE with -ftracer (on by default with profile feedback) [GCC-tracer]. LLVM duplicates tails in TailDuplicator (llvm/lib/CodeGen/TailDuplicator.cpp), both early (early-tailduplication) and during block placement (-tail-dup-placement), which builds superblock-like layouts for the hot path [LLVM-TailDup].

GCC's tracer makes a superblock

Reproduce (gcc 14.2.0; reg.c from the previous box):

gcc-14 -O2 -ftracer -fdump-tree-tracer-details -c reg.c -o reg.o
grep -E '^Trace seed|^Duplicated' reg.c.*t.tracer

Output (complete):

Trace seed 3 [8900] forward 3 [8900],4 [8010],6 [8900]
Duplicated 6 as 8 [8010]
Duplicated 6 insns (37%)

What to notice: the numbers in brackets are estimated frequencies (block 3, the loop header, runs 8900 times per 1000 entries). The trace grows forward from the seed along the likely arm (block 4, v > x was marked likely with __builtin_expect) to the join (block 6). Block 6 has a side entrance from the unlikely arm (block 5), so it is duplicated as block 8, which becomes the tail of the superblock 3 → 4 → 8 (Algorithm 23.4.6). The last line is the code growth.

Treegion scheduling¶

GCC forms regions in gcc/sched-rgn.cc (find_rgns: natural loops without inner loops and single blocks otherwise) and schedules them with interblock and speculative motion (-fsched-interblock, -fsched-spec, on by default when -fschedule-insns is on) [GCC-sched-rgn]. Neither GCC nor LLVM forms treegions by that name. GCC's acyclic regions are their closest relative in production.

GCC's multi-block scheduling regions

Reproduce (gcc 14.2.0; reg.c from the first box):

gcc-14 -O2 -fschedule-insns -fsched-verbose=5 -fdump-rtl-sched1 -c reg.c -o reg.o
sed -n '/-- REGIONS --/,/rgn 1 /p' reg.c.*r.sched1; grep 'interblock/speculative' reg.c.*r.sched1

Output (complete):

;;   ------------ REGIONS ----------

;;  rgn 0 nr_blocks 4:
;;  bb/block:  0/4  1/5  2/6  3/7 

;;  rgn 1 nr_blocks 1:
;; Procedure interblock/speculative motions == 1/1

What to notice: region 0 is the loop body: four RTL blocks (4, 5, 6, 7) scheduled together as one acyclic region, the others are single blocks. The full dump shows insn 22 of the region's second block listed as 22/b1 in the ready list of the first block: it is a candidate for interblock motion, and the summary line counts one interblock motion, which was speculative (the source block does not post-dominate the target). That is the upward motion of Proposition 23.4.12 in GCC's more general acyclic regions.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Trace scheduling	any motion along the trace, repaired by compensation (Theorem 23.4.10)	list scheduling per trace plus copies	excellent on the hot path; compensation slows cold paths and grows code	very high (bookkeeping rules, liveness, frozen ops)	Multiflow, Bulldog; GCC selective scheduling (IA-64)
Superblock scheduling	motion within a single-entry trace; only exits need care (Theorem 23.4.11)	tail duplication linear in the tail; list scheduling	good on the hot path; code growth from copies (37 % of the loop in the tracer box)	moderate	IMPACT; GCC `-ftracer`, `-fsched2-use-superblocks`; LLVM tail duplication in block placement
Treegion scheduling	motion to ancestors on every path of a tree; no join repair (Proposition 23.4.12)	formation \(O(n + e)\)	helps all paths of a branch, not only the likely one	moderate	research compilers (HBC98); GCC's acyclic region scheduler is the production analog

Choose trace scheduling when a statically scheduled wide machine (VLIW) must extract ILP across many branches and the profile is reliable. Choose superblocks when you want most of the benefit with a much simpler scheduler and can afford some code growth. That is the usual choice today, often implemented as tail duplication before an ordinary block scheduler. Choose treegions, or GCC-style regions, when branches are not strongly biased and no profile exists.

9. Assessment¶

Quiz: trace-select-running (sequence), side-entrances (set), compensation-rule (single), tail-dup-blocks (set), treegions-running (number), speculation-legal (multi), find-bookkeeping (text: sel-sched.cc). Tags trace-scheduling, superblock, treegion.
Drills: ./course drill trace-select (easy: traces; medium: + tail-duplicated blocks; hard: + treegions). Compensation placement is taught by the worked example and quizzed, since the drill would need a full operation-level scheduler.
Flashcards: tags trace-scheduling, superblock, treegion.

References¶

See the chapter references.

Lesson 23.4 — Region scheduling: traces, superblocks and treegions¶

1. Problem and motivation¶

Trace scheduling¶

Superblock scheduling¶

Treegion scheduling¶

2. Definitions and algorithms¶

Trace scheduling¶

Superblock scheduling¶

Treegion scheduling¶

3. Worked examples¶

Trace scheduling¶

Superblock scheduling¶

Treegion scheduling¶

4. Invariants and correctness¶

Trace scheduling¶

Superblock scheduling¶

Treegion scheduling¶

5. Complexity¶

6. Variants and refinements¶

Trace scheduling¶

Superblock scheduling¶

Treegion scheduling¶

7. In real compilers¶

Trace scheduling¶

Superblock scheduling¶

Treegion scheduling¶

8. Comparison¶

9. Assessment¶

References¶