Machine-independent register allocation

ABSTRACT

The context of this paper is a machine-independent Pascal optimizer that transforms an intermediate stack-machine pseudo-code program into a generally smaller and faster pseudo-code program. The emphasis of this current paper is on the approach taken for mapping registers and storage, using an abstract but practical definition of the target machine's storage hierarchy. A companion paper [7] describes the overall optimizer project. After starting on this project, additional input became available from a Fortran-to-Pcode compiler written at Stanford [2]. Our storage mapping design is sufficiently robust that the addition of Fortran EQUIVALENCE and COMMON statements required no changes. Our particular allocation algorithm is not unique or original, but the abstract description of the storage hierarchy, and its inclusion of practical considerations we feel to be an original contribution. The description framework has so far stood the test of describing the storage hierarchy of many commercially-available machines without needing to be extended or embellished. We hope that this is a good predictor for the future.

REFERENCES

• 1: Chow, F. 1979. "UCFORT," Stanford Artificial Intelligence Laboratory, Stanford, CA.
• 2: Day, W.H.E. 1970. "Compiler assignment of data items to registers," IBM Systems Journal 9:4, pp. 281-317.
• 3: R. A. Freiburghouse, Register allocation via usage counts, Communications of the ACM, v.17 n.11, p.638-642, Nov. 1974 [doi>10.1145/361179.361201]
• 4: Harrison, W. 1975. "A class of register allocation algorithms," IBM Research Report RC-5342.
• 5: Richard Karl Johnsson, An approach to global register allocation., 1976
• 6: Leverett, B.W. et al. 1979. "An overview of the production quality compiler-compiler project," Computer science report CS-79-105, Carnegie-Mellon University.
• 7: Daniel R. Perkins , Richard L. Sites, Machine-independent PASCAL code optimization, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.201-207, August 06-10, 1979, Denver, Colorado, United States
• 8: William Allan Wulf , Richard K. Johnsson , Charles B. Weinstock , Steven O. Hobbs , Charles M. Geschke, The Design of an Optimizing Compiler, Elsevier Science Inc., New York, NY, 1975

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Pascal

General Terms:
Algorithms, Languages