Efficient Instruction Scheduling Using Finite State Automata

Vasanth Bala, Norman Rubin

Abstract

In this paper we present a method based on finite state automata, to conveniently model the state of the processor's pipeline resources during instruction scheduling, as well as techniques for simplifying certain complicated code motions that are essential for efficient instruction scheduling across basic blocks. We also discuss the implementation of our technique in a production compiler, and give results on automata we have developed for various processors.

Keywords

structural hazard, global instruction scheduling, finite state automaton, pipelined processor, compiler optimization

Talk Overheads (pages 1-4) (4,341,170 bytes)

Talk Overheads (pages 5-8) (8,793,818 bytes)

Talk Overheads (pages 9-12) (6,587,278 bytes)