Learning to Schedule Straight-Line Code

Program execution speed on modem computers is sensitive, by a factor of two or more, to the order in which instructions are presented to the processor. Torealize potential execution efficiency, an optimizing compiler must employ a heuristic algorithm for instruction scheduling. Such algorithms are painstakingly handcrafted, which is expensive and time-consuming. We show how to cast the instruction scheduling problem as a learning task, obtaining theheuristic scheduling algorithm automatically. Our focus is the narrower problem of scheduling straight-line code (also called basic blocks of instructions). Our empirical results show that just a few features are adequate forquite good performance at this task for a real modem processor, and that any of several supervised learning methods perform nearly optimally withrespect to the features used.