EFFICIENT INSTRUCTION SCHEDULING USING FINITE-STATE AUTOMATA

Modern compilers employ sophisticated instruction scheduling technique s to shorten the number of cycles taken to execute the instruction str eam. In addition to correctness, the instruction scheduler must also e nsure that hardware resources are not oversubscribed in any cycle. For a contemporary processor implementation with multiple pipelines and c omplex resource usage restrictions, this is not an easy task. The comp lexity involved in reasoning about such resource hazards is one of the primary factors that constrain the instruction scheduler from perform ing certain kinds of transformations that can result in improved sched ules. We extend a technique for detecting pipeline resource hazards ba sed on finite state automata, to support the efficient implementation of such transformations that are essential for aggressive instruction scheduling beyond basic blocks. Although similar code transformations can be supported by other schemes such as reservation tables, our sche me is superior in terms of space and time. A global instruction schedu ler using these techniques was implemented in the KSR compiler.