Trace Scheduling

Trace scheduling is a compiler optimization technique that extends instruction scheduling across basic block boundaries. Rather than scheduling within a single block, trace scheduling identifies likely execution paths — called traces — through the control flow graph and schedules instructions along these paths as if they were single extended blocks. When a trace prediction is wrong, compensation code restores correct program state.

The technique was pioneered by the Bulldog compiler in the 1980s and is most effective on architectures with exposed pipelines where the compiler, not the hardware, is responsible for finding parallelism. Trace scheduling exemplifies a broader principle in systems design: optimization requires betting on the future, and the cost of a wrong bet must be less than the gain from a right one.