Method for minimizing spill in code scheduled by a list scheduler

摘要

A technique of ordering machine instructions to reduce spill code. For each machine instruction that is ready for scheduling, an amount is determined by which the size of a committed set of machine instructions would increase upon the scheduling of the machine instruction. The machine instruction for which the determined amount is smallest is then scheduled. The currently committed instructions may be determined to be the machine instructions that are already scheduled as well as the machine instructions that are descendent from already scheduled machine instructions. The result is that new computations upon which a target processor will embark tend to be deferred. Bit vectors may be employed for efficiency during the assessment of candidate instructions that are ready for scheduling. The technique may be triggered when the risk of registers becoming overcommitted becomes high, as may occur when the number of available processor registers drops below a certain threshold.