Code generation and reorganization in the presence of pipeline constraints

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.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977 [doi>10.1145/321992.322001]
• 3: Baskett, F. Puzzle: an informal compute bound benchmark. Widely circulated and run.
• 4: Davidson, S., Landskov, D., Shriver, B.D., and Mallett, P.W. "Some Experiments in Local Microcode Compaction for Horizontal Machines." Trans.on Computers C-30, 7 (July 1981), 460 -- 477.
• 5: Peter J. Denning, ACM president's letter: computer architecture: some old ideas that haven't quite made it yet, Communications of the ACM, v.24 n.9, p.553-554, Sept. 1981 [doi>10.1145/358746.358747]
• 6: Hennessy, J.L., Jouppi, N., Baskett, F., and Gill,J. MIPS: A VLSI Processor Architecture. Proc. CMU Conference on VLSI Systems and Computations, October, 1981.
• 7: John Hennessy, Symbolic Debugging of Optimized Code, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.323-344, July 1982 [doi>10.1145/357172.357173]
• 8: S. C. Johnson, A portable compiler: theory and practice, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-104, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512771]
• 9: Lampson, B.W., McDaniel, G.A. and S.M. Ornstein. An Instruction Fetch Unit for a High Performance Personal Computer. Tech. Rept. CSL-81-1, Xerox PARC, Jan, 1981.
• 10: McLellan. "IBM, A Radical Departure." Datamation 25, 11 (October 1979), 53--55.
• 11: David A. Patterson , Carlo H. Sequin, RISC I: A Reduced Instruction Set VLSI Computer, Proceedings of the 8th annual symposium on Computer Architecture, p.443-457, May 12-14, 1981, Minneapolis, Minnesota, United States
• 12: David A. Patterson , David R. Ditzel, The case for the reduced instruction set computer, ACM SIGARCH Computer Architecture News, v.8 n.6, p.25-33, October 1980 [doi>10.1145/641914.641917]
• 13: Sethi, R. "Complete register allocation problems." SIAM J. Computing 4, 3 (1975), 226--248.
• 14: Tokoro, M., Tamura, E. and Takizuka, T. "Optimization of Microprograms." Trans. on Computers C-30, 7 (July 1981), 491--504.
• 15: Widdoes, L.C. The S-1 Project: Developing high performance digital computers. Proc. Compcon, IEEE, San Francisco, Feb, 1980.
• 16: Wulf, W.A. "Compilers and Computer Architecture." Computer 14, 7 (July 1981), 41--48.