Efficient instruction scheduling using finite state automata
Authors:
- V. BalaVBV. Bala
- N. RubinNRN. Rubin
- 1 November 1995
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10724451,p. 46-56
Abstract
Modern compilers employ sophisticated instruction scheduling techniques to shorten the number of cycles taken to execute the instruction stream. In addition to correctness, the instruction scheduler must also ensure that hardware resources are not oversubscribed in any cycle. For a contemporary processor implementation with multiple pipelines and complex resource usage restrictions, this is not an easy task. The complexity involved in reasoning about such resource hazards is one of the primary factors that constrain the instruction scheduler from performing many aggressive transformations. For example, the ability to do code motion or instruction replacement in the middle of an already scheduled block would be a very powerful transformation if it could be performed efficiently. We extend a technique for detecting pipeline resource hazards based 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 scheme is superior in terms of space and time. A global instruction scheduler that used these techniques was implemented in the KSR compiler.Keywords
This publication has 7 references indexed in Scilit:
- Detecting pipeline structural hazards quickly1994
- Improving resource utilization of the MIPS R8000 via post-scheduling global instruction distribution1994
- Compiling for the CydraThe Journal of Supercomputing, 1993
- The multiflow trace scheduling compilerThe Journal of Supercomputing, 1993
- Instruction scheduling for the Motorola 881101993
- Scanning regular languages by dual finite automataACM SIGPLAN Notices, 1992
- Trace Scheduling: A Technique for Global Microcode CompactionIEEE Transactions on Computers, 1981