of the dependency graph, appends it to the current instruction schedule and removes it from the graph. This may cause other vertices to be sources, which will then also be considered for scheduling. The algorithm terminates if the graph is empty. To arrive at a good schedule, stalls should be prevented. This is determined by the choice of the next instruction to be scheduled. A number of heuristics are in common use: The processor resources used by the already scheduled instructions are recorded. If a candidate uses a resource that is occupied, its priority will drop. If a candidate is scheduled closer to its predecessors than the associated latency, its priority will drop. If a candidate lies on the critical path of the graph, its priority will rise. This heuristic provides some form of look-ahead in an otherwise local decision process. If choosing a candidate will create many new sources, its priority will rise. This heuristic tends to generate more freedom for the scheduler. Phase order Instruction scheduling may be done either before or after register allocation or both before and after it. The advantage of doing it before register allocation is that this results in maximum parallelism. The disadvantage of doing it before register allocation is that this can result in the register allocator needing to use a number of registers exceeding those available. This will cause spill/fill code to be introduced, which will reduce the performance of the section of code in question. If the architecture being scheduled has instruction sequences that have potentially illegal combinations (due to a lack of instruction interlocks), the instructions must be scheduled after register allocation. This second scheduling pass will also improve the placement of the spill/fill code. If scheduling is only done after register allocation, then there will be false dependencies introduced by the register allocation that will limit the amount of instruction motion possible by the scheduler. Types There are several types of instruction scheduling: Local (basic block) scheduling: instructions can't move across basic block boundaries. Global scheduling: instructions can move across basic block boundaries. Modulo scheduling: an algorithm for generating software pipelining, which is a way of increasing instruction level parallelism by interleaving different iterations of an inner loop. Trace scheduling: the first practical approach for global scheduling, trace scheduling tries to optimize the control flow path that is executed most often. Superblock scheduling: a simplified form of trace