In computer science, instruction scheduling is a compiler optimization used to improve instruction-level parallelism, which improves performance on machines with instruction pipelines. Put more simply, it tries to rearrange the order of instructions so that a value is not used right after it is computed, which causes pipeline stalls, without changing the meaning of the code.

Data dependencies

Instruction scheduling is typically done on a single basic block. In order to determine whether rearranging the block's instructions in a certain way preserves the behavior of that block, we need the concept of a data dependency. There are three types of dependencies, which also happen to be the three data hazards:

1. Read after Write (RAW): Instruction 1 writes a value used by later Instruction 2. Instruction 1 must come first, or Instruction 2 will read the old value instead of the new.
2. Write after Read (WAR): Instruction 1 reads a location that is later overwritten by Instruction 2. Instruction 1 must come first, or it will read the new value instead of the old.
3. Write after Write (WAW): Two instructions both write the same location. They must occur in their original order.

To make sure we respect these three types of dependencies, we construct a dependency graph, which is an undirected graph where each vertex is an instruction and there is an edge from I₁ to I₂ if I₁ must come before I₂ due to a dependency. Then, any topological sort of this graph is a valid instruction scheduling.