High speed compilation of efficient object code

ABSTRACT

A three-pass compiler with the following properties is briefly described: The last two passes scan an intermediate language produced by the preceding pass in essentially the reverse of the order in which it was generated, so that the first pass is the only one which has to read the relatively bulky problem-oriented input. The double scan, one in either direction, performed by the first two passes, allows the compiler to remove locally constant expressions and recursively calculable expressions from loops and to do the important part of common subexpression recognition. Optimization such as the effective use of index registers, although as important, is not discussed since the object code which would be most efficient is highly machine dependent. The discussion is in terms of a FORTRAN-like language, although the technique is applicable to most algebraic languages.

REFERENCES

• 1: Robert W. Floyd, An algorithm for coding efficient arithmetic operations, Communications of the ACM, v.4 n.1, p.42-51, Jan. 1961 [doi>10.1145/366062.366082]
• 2: GEAR, C.W. Optimization of the address field compilation in the ILLIAC II assembler. Comput. J . 6 (Jan. 1964), 332.
• 3: HUXTABLE, D. H. R. On Writing an Optimizing Translator for ALGOL 60. In Introduction to System Programming, P. Wegner (Ed.), Academic Press, 1964, 137.
• 4: IBM. Systems Manual for 704 FORTRAN and 709 FORTRAN Appl. Programming Dept., IBM, April, 1960.
• 5: K. Samelson , F. L. Bauer, Sequential formula translation, Communications of the ACM, v.3 n.2, p.76-83, Feb. 1960 [doi>10.1145/366959.366968]

INDEX TERMS

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

General Terms:
Design, Languages, Performance, Theory