Report Number: CSL-TR-81-224
Institution: Stanford University, Computer Systems Laboratory
Title: Code generation and reorganization in the presence of pipeline constraints
Author: Hennessy, John L.
Author: Gross, Thomas
Date: November 1981
Abstract: Pipeline interlocks are used in a pipelined architecture to prevent the execution of a machine instruction before its operands are available. An alternative to this complex piece of hardware is to rearrange the instructions at compile-time to avoid pipeline interlocks. This problem, called code reorganization, is studied. The basic problem of reorganization of machine level instructions at compile-time is shown to be NP-complete. A heuristic algorithm is proposed and its properties and effectiveness are explored. The impact of code reorganization techniques on the rest of a compiler system are discussed.