Linear-time, Optimal Code Scheduling for Delayed-Load Architectures

A fast, optimal code scheduling algorithm for processors with a delayed lo,ad of 1 instruction cycle is described. The algorithm minimizes both execution time and register use and runs in time proportional to the size of the expression tree. Extensions that spill registers when too few are available are also presented. The algorithm also performs very well for delayed loads of greater than 1 instruction cycle. For machines with load delays greater than 1, bounds are given for the minimal number of registers needed for optimally evaluating an expression tree.