Postpass Code Optimization of Pipeline Constraints

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 is called code reorganization and is studied here. 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. Empirical data from MIPS, a VLSI processor design, are given. The impact of code reorganization techniques on the rest of a compiler system is discussed.