Efficient instruction scheduling for a pipelined architecture
- 1 July 1986
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 21 (7) , 11-16
- https://doi.org/10.1145/13310.13312
Abstract
As part of an effort to develop an optimizing compiler for a pipelined architecture, a code reorganization algorithm has been developed that significantly reduces the number of runtime pipeline interlocks. In a pass after code generation, the algorithm uses a dag representation to heuristically schedule the instructions in each basic block.Previous algorithms for reducing pipeline interlocks have had worst-case runtimes of at least O (n4). By using a dag representation which prevents scheduling deadlocks and a selection method that requires no lookahead, the resulting algorithm reorganizes instructions almost as effectively in practice, while having an O (n2) worst-case runtime.Keywords
This publication has 7 references indexed in Scilit:
- Effectiveness of a machine-level, global optimizerPublished by Association for Computing Machinery (ACM) ,1986
- Retargetable high-level alias analysisPublished by Association for Computing Machinery (ACM) ,1986
- Postpass Code Optimization of Pipeline ConstraintsACM Transactions on Programming Languages and Systems, 1983
- Local Code Generation and Compaction in Optimizing Microcode CompilersPublished by Defense Technical Information Center (DTIC) ,1982
- Coding guidelines for pipelined processorsPublished by Association for Computing Machinery (ACM) ,1982
- An overview of the PL.8 compilerPublished by Association for Computing Machinery (ACM) ,1982
- An Efficient Algorithm for Exploiting Multiple Arithmetic UnitsIBM Journal of Research and Development, 1967