Code scheduling and register allocation in large basic blocks

ABSTRACT

We discuss the issues about the interdependency between code scheduling and register allocation. We present two methods as solutions: (1) an integrated code scheduling technique; and (2) a DAG-driven register allocator. The integrated code scheduling method combines two scheduling techniques—one to reduce pipeline delays and the other to minimize register usage—into a single phase. By keeping track of the number of available registers, the scheduler can choose the appropriate scheduling technique to schedule a better code sequence. The DAG-driven register allocator uses a dependency graph to assist in assigning registers; it introduces much less extra dependency than does an ordinary register allocator. For large basic blocks, both approaches were shown to generate more efficient code sequences than conventional techniques in the simulations.

REFERENCES

• Aho77: 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]
• Aho86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• Ausl82: Marc Auslander , Martin Hopkins, An overview of the PL.8 compiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.22-31, June 23-25, 1982, Boston, Massachusetts, United States
• Cray82: Cray Research inc., Cray-1 Computer System S Series Mainframe Reference Manual (HR-0029), 1982.
• Davi86: Jack W. Davidson, A retargetable instruction reorganizer, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.234-241, June 25-27, 1986, Palo Alto, California, United States
• Dong79: Dongarra, J. J. and A. R. Jinds, "Unrolling I.x~ps in Fortran,'" Software Practice and Experience 9, 3, pp. 219-226, Mar., 1979
• Elli85: John R. Ellis, Bulldog: a compiler for vliw architectures (parallel computing, reduced-instruction-set, trace scheduling, scientific), 1985
• Fish81: Fisher, J., "Trace Scheduling: A Technique for Global Microcode Compaction," IEEE Transactions on Computers, Vol. C-30, No. 7, July 1981.
• Gibb86: Philip B. Gibbons , Steven S. Muchnick, Efficient instruction scheduling for a pipelined architecture, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.11-16, June 25-27, 1986, Palo Alto, California, United States
• Henn83: John L. Hennessy , Thomas Gross, Postpass Code Optimization of Pipeline Constraints, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.422-448, July 1983 [doi>10.1145/2166.357217]
• Henn84: Hennessy, J. L., "VLSI Processor Architecture," IEEE Transactions on Computers, Vol. c-33 No. 12, Dec., 1984.
• Hsu87: Hsu, Wei-Chung, "Register Allocation and Code Scheduling for Load/Store Architectures" UW Computer Science Technique Report #722, Oct., 1987
• Kogg81: Kogge, P. M., "The Architecture of Pipelined Computers,~' McGraw-Hill, New York, 1981
• McMa72: McMahon, F. H, "FORTRAN CPU Performance Analysis", Lawrence Livermore Laboratories, 1972
• Milu86: Veljko Milutinovic, GaAs: microprocessor technology, Computer, v.19 n.10, p.10-13, Oct. 1986 [doi>10.1109/MC.1986.1663062]
• Padu86: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• Seth70: Ravi Sethi , J. D. Ullman, The Generation of Optimal Code for Arithmetic Expressions, Journal of the ACM (JACM), v.17 n.4, p.715-728, Oct. 1970 [doi>10.1145/321607.321620]
• Thor70: J. E. Thornton, Design of a Computer—The Control Data 6600, Scott Foresman & Co, 1970
• Tjad70: Tjaden, G. S. and M. J. Plynn, "Detection and Parallel Execution of Independent lru~tmctions," IEEE Transactions on Computers 19(10):889-895, Oct., 1970
• Toma67: Tomasulo, R. M., "An Efficient Algorithm for Exploiting Multiple Arithmetic Units," IBM Journal of Research and Development V 11, pp. 25-33, Jan., 1967.
• Weis87: Shlomo Weiss , James E. Smith, A study of scalar compilation techniques for pipelined supercomputers, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.105-109, October 1987, Palo Alto, California, United States
• Youn85: Young, H., "Evaluation of a Decoupled Computer Architecture and the Design of A Vector Extension," Computer Sciences Technical Report #603, July, 1985

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

General Terms:
Design, Performance