Lesson 23.8 — Scheduling and register allocation: phase ordering and integration¶

Techniques: prepass vs postpass scheduling (the phase-ordering problem); integrated prepass scheduling (Goodman–Hsu IPS, pressure-sensitive schedulers); scheduler-sensitive register allocation (Pinter's parallelizable interference graph, Norris–Pollock) and post-allocation renaming · Prerequisites: Lesson 23.3, Ch 22 (interference graphs, coloring, spilling) · Time: 3 hours

Scheduling wants values in flight at the same time; register allocation wants as few values live at once as possible. Each phase changes the other's problem. Schedule first, and the allocator faces longer live ranges and may spill. Allocate first, and every register the allocator reuses adds an anti or output dependence that pins two computations in their original order, so the scheduler cannot overlap them. The running block of Lesson 23.2 shows the cost directly. Its g: r1 = load B[1] reuses r1, the register of a's value, as an allocator would. Rename g to a fresh register r8 and every list scheduler of Lesson 23.3 finds a schedule of length 9, the lower bound. With the reuse, the best is 10 and bottom-up gets 11. This lesson presents the three answers compilers use: order the phases and live with it, make the scheduler watch registers, or make the allocator watch the schedule.

1. Problem and motivation¶

Prepass vs postpass scheduling (phase ordering)¶

The first RISC compilers scheduled after register allocation (postpass). Hennessy and Gross's pipeline scheduler for MIPS worked on allocated code, because only then are all loads, stores and spills known [HG83]. Gibbons and Muchnick did the same on the HP Precision Architecture [GM86]. The price is the false dependences of allocated code. Scheduling before allocation (prepass) works on virtual registers without false dependences, but it cannot see spill code and may create it. Most compilers today do both. LLVM's MachineScheduler is prepass, with an optional post-RA scheduler (Lesson 23.7). GCC has sched1 (prepass, off by default on x86, where registers are scarce) and sched2 (postpass, on at -O2).

Integrated prepass scheduling¶

Goodman and Hsu proposed to keep scheduling before allocation but make the scheduler count registers. Their Integrated Prepass Scheduling (IPS) uses a latency-oriented priority while enough registers are free, and switches to a register-reducing priority when the count of available registers falls below a threshold [GH88]. The same paper gives DAG-driven register allocation, which allocates during scheduling and reuses the register freed longest ago to avoid creating false dependences. Every production prepass scheduler descends from IPS: LLVM's GenericScheduler with its excess/critical pressure criteria (Lesson 23.7), SelectionDAG's list-hybrid, and GCC's -fsched-pressure.

Scheduler-sensitive register allocation¶

The other direction changes the allocator. Pinter defined the parallelizable interference graph: the interference graph plus an edge between any two values whose defining operations could execute in parallel. A coloring of it introduces no false dependence that restricts the schedule [Pin93]. Norris and Pollock made a Chaitin-style allocator scheduler-sensitive: it adds such edges optimistically and removes them first when coloring would otherwise spill [NP93]. Bradlee, Eggers and Henry compared integrated strategies (RASE) on RISC machines and found that a loosely coupled prepass scheduler with pressure feedback gets most of the benefit [BEH91]. Compilers also use a cheap after-the-fact variant: renaming registers after allocation to remove the false dependences it created (GCC's regrename, LLVM's anti-dependence breakers of Lesson 23.7).

2. Definitions and algorithms¶

Definition 23.8.1 (Allocated DAG, false dependences introduced by allocation)

Let \(G\) be the dependence DAG of a block over virtual registers (each value has its own name) and let \(\rho\) assign a physical register to every value. The allocated DAG \(G_\rho\) is the DAG of the block with every value \(v\) renamed to \(\rho(v)\) (Algorithm 23.2.6). Its edges not in \(G\) are the false dependences introduced by \(\rho\): anti and output edges between values sharing a register.

Proposition 23.8.2 (Allocation can only remove schedules)

Every valid schedule of \(G_\rho\) is a valid schedule of \(G\), so \(\mathrm{CP}(G_\rho) \ge \mathrm{CP}(G)\) and the optimal length of \(G_\rho\) is at least that of \(G\).

Proof

Renaming preserves the true dependences: a use still reads the definition that reaches it, because \(\rho\) is a valid allocation (values that are live at the same time get different registers), so reaching definitions are unchanged. Memory edges do not depend on registers. Hence \(G \subseteq G_\rho\) with the same latencies on common edges, every constraint of \(G\) is a constraint of \(G_\rho\), and the claims follow from Theorem 23.2.12 and the definition of the optimum.

Prepass vs postpass scheduling (phase ordering)¶

Algorithm 23.8.3 (Prepass and postpass pipelines)

Input: a function in SSA machine code.
Output: allocated, scheduled code.
Precondition: a list scheduler (Lesson 23.3) and a register allocator (Ch 22).
Postcondition: valid code; the schedule respects \(G\) (prepass) or \(G_\rho\) (postpass).
Invariant: each phase preserves semantics (Theorem 23.2.11 for scheduling, the allocator's correctness for allocation).

function Postpass(F):  ρ ← Allocate(F);  return ListSchedule(G_ρ of F)
function Prepass(F):   F' ← ListSchedule(G of F);  return Allocate(F')     # may add spills
function Both(F):      F' ← ListSchedule(G of F, with pressure tracking)   # LLVM, GCC
                       ρ ← Allocate(F');  return ListSchedule(G_ρ of F')   # post-RA pass

Integrated prepass scheduling¶

Algorithm 23.8.4 (IPS, after Goodman and Hsu)

Input: a block's DAG over virtual registers; the number \(k\) of allocatable registers; a threshold \(\tau\).
Output: a schedule.
Precondition: \(k\) is at least the MaxLive of some order of the block.
Postcondition: a valid schedule; while \(\mathrm{AVLREG} \ge \tau\) the order follows latency (CSP), otherwise it reduces live registers (CSR).
Invariant: \(\mathrm{AVLREG} = k - (\text{number of live values at the current point})\).

function IPS(G, k, τ):
    AVLREG ← k − |live-in values|; ready ← roots
    while ready ≠ ∅:
        if AVLREG > τ:                                   # CSP: code scheduling for pipelines
            v ← the ready op with the largest height that does not stall;
                if every ready op stalls, the one with the largest height
        else:                                            # CSR: code scheduling to reduce registers
            v ← a ready op that frees registers (kills ≥ defines), preferring the most kills;
                else the ready op that starts the chain freeing a register soonest
        emit v; AVLREG ← AVLREG − defines(v) + kills(v); update ready

Algorithm 23.3.10 (the lab's pressure algorithm) is a variant with a hard cap \(K\) and the switch at \(K - 1\).

Scheduler-sensitive register allocation¶

Definition 23.8.5 (Parallelizable interference graph)

For the virtual DAG \(G\), two values \(u, v\) are parallelizable if neither's defining operation reaches the other's in \(G\) (no path either way). The parallelizable interference graph \(I_P\) has an edge between \(u\) and \(v\) if they interfere (both live at some point of the current order) or they are parallelizable.

Theorem 23.8.6 (Coloring \(I_P\) introduces no restricting false dependence)

If \(\rho\) is a proper coloring of \(I_P\), then two values share a register only if their definitions are ordered by a path of \(G\). In particular, every false dependence that \(\rho\) introduces lies between operations already ordered by \(G\), and no pair of operations that \(G\) allows to run in parallel is serialized by the allocation.

Proof sketch (full proof: [Pin93])

Values sharing a register are not adjacent in \(I_P\), so they are not parallelizable, so one definition reaches the other. A false edge introduced by the sharing (anti from the uses of the first value to the second definition, output between the definitions) connects operations on the two sides of that path. Pinter additionally shows that the anti edges from the uses are harmless whenever the uses are themselves ordered before the second definition in \(G\), and restricts the parallelizable relation to make that hold. The full statement and its proof are in [Pin93].

Algorithm 23.8.7 (Scheduler-sensitive graph coloring, after Norris and Pollock)

Input: the virtual DAG \(G\); the interference graph \(I\); \(k\) registers.
Output: an allocation \(\rho\) (with spills if needed).
Precondition: a Chaitin–Briggs allocator (Ch 22).
Postcondition: a valid allocation; parallelizable pairs share a register only when needed to avoid spilling.
Invariant: the working graph always contains \(I\); only "scheduler edges" are ever removed.

function SchedulerSensitiveColor(G, I, k):
    W ← I ∪ { (u, v) | u, v parallelizable in G }        # scheduler edges, marked
    loop:
        if Simplify(W, k) succeeds: return Select(W)        # Chaitin–Briggs on W
        if W has scheduler edges:
            remove the scheduler edges of the node blocking simplification with the fewest
                lost parallelism (for example, the pair whose operations have the least slack)
        else:
            spill as Chaitin–Briggs would; rebuild I and W

Algorithm 23.8.8 (Post-allocation renaming, as in GCC's regrename)

Input: allocated code of a block; liveness.
Output: code where some def-use chains use a different register.
Precondition: the chain (a definition and all the uses it reaches) is complete within the block and has no tied or fixed operands.
Postcondition: semantics preserved (Proposition 23.7.10); fewer anti and output edges.
Invariant: a replacement register is free (not live, not referenced) over the whole chain.

for each chain c in the block (in order):
    R' ← a register of c's class that is free over c's range and was freed longest ago
    if R' exists and R' ≠ c's register: rename c to R'

3. Worked examples¶

Prepass vs postpass scheduling (phase ordering)¶

The running block with and without the reuse of r1 (lab machine, lab algorithms; the renamed block has g: r8 = load B[1] and i: r7 = sub r6, r8):

algorithm	length, with `r1` reused (\(G_\rho\))	length, renamed (\(G\))	MaxLive renamed
`td-cp`	10	9	6
`td-succ`	11	9	6
`bu-cp`	11	9	6
`bu-succ`	11	9	6

Without the reuse, \(G\) lacks the anti edge d→g and the output edge a→g, so the load of B[1] can issue at cycle 3 (td-cp puts g at 3 instead of 5), and every algorithm reaches the lower bound \(\max(\mathrm{CP}, \mathrm{RB}) = 9\) (Proposition 23.8.2 in reverse: the extra edges cost one or two cycles). The in-order MaxLive of the renamed block is 5, so an allocator with five registers can color it only in an order close to in-order. That is the dilemma: a prepass schedule of length 9 needs 6 registers.

Integrated prepass scheduling¶

IPS on the renamed block with \(k = 5\) and \(\tau = 1\) behaves like Algorithm 23.3.10 with \(K = 5\) (Lesson 23.3 §3, which traces it on the original block): it follows heights until only one register is free, then prefers operations that kill values (d, which kills a's value, and the store h, which defines nothing) and delays the load of B[1] until registers die. The result trades one cycle for one register, exactly as in Lesson 23.3.

Scheduler-sensitive register allocation¶

In the renamed block the values of a (r1) and g (r8) do not interfere (a's last use d is before g's definition in program order). A Chaitin allocator may therefore give them the same register, which recreates the false edges. Their definitions are parallelizable (no path between a and g in \(G\)), so \(I_P\) has an edge a–g, and coloring \(I_P\) forces different registers (Theorem 23.8.6). If only five registers are available, Algorithm 23.8.7 removes that scheduler edge first, because a has slack 1, and accepts the serialization rather than spill.

4. Invariants and correctness¶

Prepass vs postpass scheduling (phase ordering)¶

Each phase preserves semantics on its own (Theorem 23.2.11 and the allocator's correctness), so any composition does. The quality question is formal only in one direction: Proposition 23.8.2 says postpass scheduling can never beat prepass scheduling on the same code. The prepass order can, however, force spills, which add operations. The two phase orders are therefore incomparable in general, as the §7 box shows.

Post-RA scheduling cannot undo the allocator's choices

A post-RA scheduler sees \(G_\rho\). If the allocator reused a register between two independent chains, the anti edge is as real to the scheduler as a true dependence, and no priority function helps. Only renaming (Algorithm 23.8.8 or an anti-dependence breaker) or a prepass schedule can recover the overlap. The AArch64 box in §7 shows 12 cycles lost this way.

Integrated prepass scheduling¶

IPS is a list scheduler, so validity is Lemma 23.3.11. The register count is a heuristic in the original IPS (it switches modes and does not cap). The capped variant with a fallback (Proposition 23.3.12) guarantees the limit.

Scheduler-sensitive register allocation¶

Algorithm 23.8.7 never removes an interference edge of \(I\), so the final coloring is a proper coloring of \(I\) and a valid allocation, as in Chaitin–Briggs. Theorem 23.8.6 describes what the scheduler edges buy while they last. Renaming (Algorithm 23.8.8) is correct by Proposition 23.7.10.

5. Complexity¶

Let \(n\) be the operations, \(e\) the DAG edges, \(v\) the values and \(k\) the registers.

Technique	Time	Notes
Prepass / postpass	the sum of the phases: list scheduling \(O((n + e)\log n)\), allocation as in Ch 22	a second (post-RA) scheduling pass doubles scheduling time
IPS (Alg. 23.8.4)	\(O((n + e)\log n)\) plus \(O(1)\) amortized register accounting per operation	as list scheduling
Parallelizable interference graph	\(O(v^2)\) edges in the worst case; reachability for all pairs \(O(n \cdot e / w)\) with bit sets	the graph can be dense
Scheduler-sensitive coloring (Alg. 23.8.7)	Chaitin–Briggs on \(O(v^2)\) edges, repeated after each removal round	removal rounds bounded by the number of scheduler edges

Justification. Pairwise reachability in a DAG is computed by a reverse-topological sweep, OR-ing successor bit sets of \(n\) bits: \(O(e)\) word operations of \(n/w\) words each.

Pathological family. A block of \(m\) independent chains (no edges between chains) makes every pair of values in different chains parallelizable: \(I_P\) contains a complete multipartite graph with \(\Theta(v^2)\) edges and chromatic number at least \(m\). With \(k < m\) registers every scheduler edge between chains must eventually be removed, so the integrated allocator does \(\Theta(v^2)\) extra work and then produces the same allocation as the plain one. This is why production compilers prefer pressure-aware prepass scheduling (IPS) to scheduler-sensitive allocation.

Prepass vs postpass scheduling (phase ordering)¶

Schedule twice (LLVM, GCC): prepass with pressure tracking, then a light postpass. This is the common compromise.
Iterate (reschedule after spilling): repeat allocation and scheduling until stable, as some VLIW compilers do. Better code, more compile time.

Integrated prepass scheduling¶

Pressure sets per register class (LLVM RegPressureTracker, GCC's per-class pressure with -fsched-pressure): a separate count and limit per class. Needed with separate integer and vector register files.
Occupancy-driven scheduling (AMDGPU): GPU register counts decide how many waves can run, so the scheduler minimizes registers first and ILP second.

Scheduler-sensitive register allocation¶

Combined formulations (integer programming for both, e.g. Kästner's work; constraint programming in Unison): optimal for small functions, too slow in general.
Register renaming in hardware: out-of-order cores rename architectural registers to physical ones, which removes most false dependences at run time. It is a large part of why post-RA scheduling matters less on such cores.

7. In real compilers¶

Prepass vs postpass scheduling (phase ordering)¶

TargetPassConfig::addMachinePasses (llvm/lib/CodeGen/TargetPassConfig.cpp) adds MachineScheduler before register allocation and PostRAScheduler or PostMachineScheduler after it, when the subtarget enables them [LLVM-TPC]. GCC's pass list runs sched1 (pass_sched) before and sched2 (pass_sched2) after reload in gcc/sched-rgn.cc [GCC-sched-rgn].

Postpass scheduling cannot recover what the allocator serialized (AArch64)

Reproduce (llc 23.1.2, llvm-mca 23.1.2; poly.ll from Lesson 23.3 §7):

for f in "-enable-misched=false -misched-postra-direction=topdown" \
         "-misched-prera-direction=topdown -enable-post-misched=false"; do
  echo "== $f"
  llc -O2 -mtriple=aarch64-linux-gnu -mcpu=cortex-a55 $f poly.ll -o - \
    | grep -P '^\t(ldp|madd|mul|eor)' | tee q.s
  llvm-mca -mtriple=aarch64-linux-gnu -mcpu=cortex-a55 -iterations=1 q.s | grep 'Total Cycles'
done

Output (complete):

== -enable-misched=false -misched-postra-direction=topdown
    ldp x8, x9, [x0]
    madd    x8, x8, x1, x9
    ldp x9, x10, [x0, #16]
    madd    x9, x9, x1, x10
    ldp x10, x11, [x0, #32]
    madd    x10, x10, x1, x11
    ldp x11, x12, [x0, #48]
    mul x8, x9, x8
    madd    x11, x11, x1, x12
    mul x9, x11, x10
    eor x0, x9, x8
Total Cycles:      32
== -misched-prera-direction=topdown -enable-post-misched=false
    ldp x8, x9, [x0]
    ldp x10, x11, [x0, #16]
    ldp x12, x13, [x0, #32]
    madd    x8, x8, x1, x9
    ldp x9, x14, [x0, #48]
    madd    x10, x10, x1, x11
    madd    x11, x12, x1, x13
    madd    x9, x9, x1, x14
    mul x8, x10, x8
    mul x9, x9, x11
    eor x0, x9, x8
Total Cycles:      20

What to notice: the first configuration schedules only after allocation (postpass, top-down). The allocator has reused x9 and x10: ldp x9, x10, [x0, #16] overwrites x9, which the first madd reads, an anti dependence of \(G_\rho\) (Definition 23.8.1). So the loads cannot move up, and 32 cycles remain. The second configuration schedules before allocation (prepass, top-down): the three loads start early and the allocator uses more registers (x12–x14), 20 cycles (Lesson 23.3's box). Proposition 23.8.2 in action.

Integrated prepass scheduling¶

LLVM's GenericScheduler tracks pressure per pressure set with RegPressureTracker and consults it first in tryCandidate (Lesson 23.7) [LLVM-MISched, LLVM-RegPressure]. GCC's -fsched-pressure (the sched_pressure modes in gcc/haifa-sched.cc, weighted or model-based) adds a pressure cost to each ready instruction [GCC-haifa].

GCC's pressure-aware scheduler at the register limit

Reproduce (gcc 14.2.0 on x86-64 Linux):

{ echo 'long p2(long *restrict a, long *restrict b) {'
  for i in $(seq 0 15); do echo "  long t$i = a[$i] * b[$i];"; done
  printf '  return ((t0 - t15) * (t1 - t14)) ^ ((t2 - t13) * (t3 - t12)) ^ ((t4 - t11) * (t5 - t10)) ^ ((t6 - t9) * (t7 - t8));\n}\n'
} > p2.c
gcc-14 -O2 -fschedule-insns -fsched-pressure -fsched-verbose=5 -fdump-rtl-sched1 -c p2.c -o p2.o
grep -o 'GENERAL_REGS:[0-9]*([-0-9]*)' p2.c.*r.sched1 | sort -t: -k2 -n | uniq -c
grep -c 'cost=12' p2.c.*r.sched1

Output (complete):

      4 GENERAL_REGS:2(-7)
     11 GENERAL_REGS:3(-6)
      3 GENERAL_REGS:4(-5)
      5 GENERAL_REGS:5(-4)
      4 GENERAL_REGS:6(-3)
     15 GENERAL_REGS:7(-2)
     20 GENERAL_REGS:8(-1)
     18 GENERAL_REGS:9(0)
92

What to notice: before each scheduling decision GCC prints the current pressure of each register class and, in parentheses, its distance from the class's limit (9 general registers available to the scheduler here). The pressure climbs as products are computed, and it stops at the limit (9(0)) and never exceeds it. The 92 ready-list lines with cost=12 are the moments when an instruction that would raise pressure beyond the limit carries a penalty, so the scheduler prefers the ones that consume values: IPS's CSR mode.

Scheduler-sensitive register allocation¶

No mainstream allocator is scheduler-sensitive in Pinter's sense. LLVM's greedy allocator uses hints and split costs but no parallelizable graph. Both compilers undo allocation-induced false dependences afterwards: GCC's regrename pass (gcc/regrename.cc, -frename-registers, on by default with -funroll-loops and on some targets) and LLVM's anti-dependence breakers (Lesson 23.7) [GCC-regrename].

GCC renames a register to free the scheduler

Reproduce (gcc 14.2.0; poly.c from Lesson 23.3 §7):

for f in "" "-frename-registers"; do echo "== gcc-14 -O2 $f"
  gcc-14 -O2 $f -S poly.c -o - | grep -P '^\t(mov|imul|add|xor)'
done
gcc-14 -O2 -frename-registers -fdump-rtl-rnreg -c poly.c -o poly.o
grep -E 'Creating chain|no available|renamed as' poly.c.*r.rnreg

Output (complete):

== gcc-14 -O2 
    movq    (%rdi), %rax
    movq    16(%rdi), %rdx
    imulq   %rsi, %rax
    addq    8(%rdi), %rax
    imulq   %rsi, %rdx
    addq    24(%rdi), %rdx
    imulq   %rdx, %rax
    movq    32(%rdi), %rdx
    imulq   %rsi, %rdx
    addq    40(%rdi), %rdx
    imulq   48(%rdi), %rsi
    addq    56(%rdi), %rsi
    imulq   %rsi, %rdx
    xorq    %rdx, %rax
== gcc-14 -O2 -frename-registers
    movq    (%rdi), %rax
    movq    16(%rdi), %rdx
    movq    32(%rdi), %rcx
    imulq   %rsi, %rax
    addq    8(%rdi), %rax
    imulq   %rsi, %rdx
    addq    24(%rdi), %rdx
    imulq   %rsi, %rcx
    addq    40(%rdi), %rcx
    imulq   48(%rdi), %rsi
    addq    56(%rdi), %rsi
    imulq   %rdx, %rax
    imulq   %rsi, %rcx
    xorq    %rcx, %rax
Creating chain ax (0) at insn 44
Creating chain dx (1) at insn 46
Creating chain dx (2) at insn 48
Register dx in insn 46; no available better choice
, renamed as cx

What to notice: GCC's allocator put the second and third partial results in the same register %rdx. That creates an anti dependence: movq 32(%rdi), %rdx must wait for imulq %rdx, %rax to read the old value, so the third chain starts late. regrename finds the def-use chain of the second %rdx (chain 2, starting at insn 48) and renames it to the free register %rcx (the dump splits that message over two lines). Then sched2 hoists the third load next to the other two (Algorithm 23.8.8, Proposition 23.7.10).

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Prepass vs postpass scheduling	postpass is limited by false edges (Proposition 23.8.2); prepass may spill	the sum of the phases	incomparable: the A55 box loses 12 cycles postpass; Lesson 23.3's box spills prepass	low (ordering passes)	LLVM and GCC: both, with pressure tracking prepass
Integrated prepass scheduling (IPS)	latency until registers run short, then register reduction	list scheduling	fewer spills at small cost in length (lab: MaxLive −12 %, length +4.6 %)	moderate: live-value accounting	LLVM GenericScheduler, SelectionDAG `list-hybrid`, GCC `-fsched-pressure`
Scheduler-sensitive register allocation	coloring \(I_P\) adds no restricting false dependence (Theorem 23.8.6)	\(\Theta(v^2)\) extra edges	best schedules when registers suffice; degrades to plain coloring otherwise	high: allocator changes	research compilers; renaming passes (GCC `regrename`, LLVM anti-dep breakers) in production

Choose prepass scheduling with pressure tracking (IPS) as the default. It is what both LLVM and GCC do. Add a postpass scheduler for in-order and VLIW cores, together with renaming so that the allocator's reuse does not pin the code. Choose scheduler-sensitive allocation only for statically scheduled machines with large register files, where every false dependence costs cycles and registers are rarely short.

9. Assessment¶

Quiz: false-deps-running (number), ips-modes (single), parallelizable-pairs (set), regrename-effect (number), and maxlive-running (Lesson 23.3). Tags phase-ordering, integrated-prepass, sched-sensitive-ra.
Drills: ./course drill list-schedule --difficulty hard includes register reuse, so its traces show false dependences; ./course drill critical-path --difficulty hard asks for anti and output edges. Integrated allocation is exercised by the lab's ★ pressure algorithm (E3) and the quiz; a drill for coloring \(I_P\) would duplicate Ch 22's interference-graph drills.
Flashcards: tags phase-ordering, integrated-prepass, sched-sensitive-ra.

References¶

See the chapter references.

Lesson 23.8 — Scheduling and register allocation: phase ordering and integration¶

1. Problem and motivation¶

Prepass vs postpass scheduling (phase ordering)¶

Integrated prepass scheduling¶

Scheduler-sensitive register allocation¶

2. Definitions and algorithms¶

Prepass vs postpass scheduling (phase ordering)¶

Integrated prepass scheduling¶

Scheduler-sensitive register allocation¶

3. Worked examples¶

Prepass vs postpass scheduling (phase ordering)¶

Integrated prepass scheduling¶

Scheduler-sensitive register allocation¶

4. Invariants and correctness¶

Prepass vs postpass scheduling (phase ordering)¶

Integrated prepass scheduling¶

Scheduler-sensitive register allocation¶

5. Complexity¶

6. Variants and refinements¶

Prepass vs postpass scheduling (phase ordering)¶

Integrated prepass scheduling¶

Scheduler-sensitive register allocation¶

7. In real compilers¶

Prepass vs postpass scheduling (phase ordering)¶

Integrated prepass scheduling¶

Scheduler-sensitive register allocation¶

8. Comparison¶

9. Assessment¶

References¶