Abstract

Learning to Schedule Straight-Line Code

Execution speed of programs on modern computer architectures is sen- sitive, by a factor of two or more, to the order in which instructions are presented to the processor. To realize potential execution efciency, it is customary for an optimizing compiler to employ a heuristic algorithm for instruction scheduling. These algorithms are painstakingly hand-crafted, which is expensive and time-consuming. We show how to cast the instruction scheduling problem as a learning task, so that one obtains the heuristic scheduling algorithm automatically. Our focus is the narro wer problem of scheduling straight-line code, also known as a basic bloc k of instructions. Our empirical results sho w that just a fe w features are adequate for quite good performance at this task for a real modern processor, and that any of several supervised learning methods perform nearly optimally with respect to the features used.