instruction scheduling

A modern processor does not finish one instruction before starting the next; it overlaps them on an assembly line called a pipeline, and it can even start several at once. But this only works if the next instruction is not waiting on a result that is not ready yet. Instruction scheduling is the back-end step that reorders instructions so the processor has independent work to do while slow results are still in flight, keeping the pipeline busy instead of stalling.

The reordering must respect dependencies: if instruction B uses the result of instruction A, B cannot move before A. The scheduler builds a dependency graph of the instructions and then chooses a legal order that hides latency. The classic case is a load: a value coming from memory may take many cycles to arrive, and an instruction that uses it immediately would stall waiting. The scheduler moves independent instructions in between, so the processor does useful work during the wait. It also considers which execution units the chip has (so it does not pile all the work on one unit) and the latency of each instruction. This is all done while preserving the program's meaning — only the order of independent operations changes.

It matters because on a deeply pipelined processor, good scheduling can be the difference between a loop that stalls constantly and one that runs near peak throughput. It is one reason a back end is tuned per microarchitecture. Two honest caveats. First, modern out-of-order processors reorder instructions in hardware at run time anyway, so the compiler's static scheduling matters most on simpler in-order chips and as a way to give the hardware good raw material; do not overstate its effect on a big out-of-order core. Second, this is the compiler reordering instructions for performance, and it is allowed to because the reordering preserves observable single-thread behavior — but that same freedom is exactly why memory operations seen by OTHER threads can appear reordered, which is the realm of the memory model, not something single-thread scheduling promises to preserve.