How hard is compiler code generation?

• Abdel-Wahab, H. M., and T. Kameda [1977]. Scheduling to minimize maximum cumulative cost subject to series-parallel precedence constraints, Operations Research, to appear.

  Google Scholar 

• Aho, A. V., J. E. Hopcroft, and J. D. Ullman [1974]. The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass.

  Google Scholar 

• Aho, A. V., and S. C. Johnson [1976]. Optimal code generation for expression trees, J. ACM 23:3, 488–501.

  Google Scholar 

• Aho, A. V., S. C. Johnson, and J. D. Ullman [1977a]. Code generation for machines with multiregister operations, Proc. Fourth ACM Symposium on Principles of Programming Languages, pp. 21–28.

  Google Scholar 

• Aho, A. V., S. C. Johnson, and J. D. Ullman [1977b]. Code generation for expressions with common subexpressions, J. ACM 24:1, 146–160.

  Google Scholar 

• Aho, A. V., and J. D. Ullman [1972]. Optimization of straight-line programs, SIAM J. Computing 1:1, 1–19.

  Google Scholar 

• Aho, A. V., and J. D. Ullman [1973]. The Theory of Parsing, Translation, and Compiling. Vol. 2: Compiling, Prentice-Hall, Englewood Cliffs, N. J.

  Google Scholar 

• Aho, A. V., and J. D. Ullman [1977]. Principles of Compiler Design, Addison-Wesley, Reading, Mass.

  Google Scholar 

• Anderson, J. P. [1964]. A note on some compiling algorithms. Comm. ACM 7:3, 149–150.

  Google Scholar 

• Beatty, J. C. [1972]. An axiomatic approach to code optimization for expressions, J. ACM 19:4, 613–640. Errata, 20:1 (Jan. 1973) 188, and 20:3 (July 1973) 538.

  Google Scholar 

• Beatty, J. C. [1974]. Register assignment algorithm for generation of highly optimized object code, IBM J. Res. Develop. 18:1, 20–39.

  Google Scholar 

• Belady, L. A. [1966]. A study of replacement algorithms for a virtual storage computer, IBM Systems J. 5:2, 78–101.

  Google Scholar 

• Bruno, J., and T. Lassagne [1975]. The generation of optimal code for stack machines, J. ACM 22:3, 382–396.

  Google Scholar 

• Bruno, J., and R. Sethi [1976]. Code generation for a one-register machine, J. ACM 23:3, 502–510.

  Google Scholar 

• Chroust, G. [1971]. Scope conserving expression evaluation, IFIP71, TA-3, 178–182.

  Google Scholar 

• Cocke, J., and J. T. Schwartz [1970]. Programming Languages and Their Compilers, Preliminary Notes, Second Revised Version, Courant Institute of Mathematical Sciences, New York.

  Google Scholar 

• Cook, S. A. [1974]. An observation on time-storage tradeoff, JCSS 9:3, 308–316.

  Google Scholar 

• Cook, S. A., and R. Sethi [1976]. Storage requirements for deterministic polynomial time recognizable languages, JCSS 13:1, 25–37.

  Google Scholar 

• Day, W. H. E. [1970]. Compiler assignment of data items to registers, IBM Systems J. 9:4, 281–317.

  Google Scholar 

• Donegan, M. K. [1973]. An approach to the automatic generation of code generators, Laboratory for Computer Science and Engineering, Rice University, Houston, Texas.

  Google Scholar 

• Ershov, A. P. [1958]. On programming of arithmetic operations, Comm. ACM 1:8, 3–6.

  Google Scholar 

• Harrison, W. [1975]. A class of register allocation algorithms, RC-5342, IBM Thomas J. Watson Research Center, Yorktown Heights, New York.

  Google Scholar 

• Hopcroft, J. E., W. J. Paul, and L. G. Valiant [1975]. On time versus space and related problems, Proc. 16th Annual Symposium on Foundations of Computer Science, pp. 57–64.

  Google Scholar 

• Horowitz, L. P., R. M. Karp, R. E. Miller, and S. Winograd [1966]. Index register allocation, J. ACM 13:1, 43–61.

  Google Scholar 

• Johnson, S. C. [1975]. YACC—yet another compiler-compiler, CSTR-32, Bell Laboratories, Murray Hill, N. J.

  Google Scholar 

• Kennedy, K. W. [1972]. Index register allocation in straight-line code and simple loops, in Rustin, R. (ed.) Design and Optimization of Compilers, Prentice-Hall, Englewood Cliffs, N. J., pp. 51–64.

  Google Scholar 

• Kim, J., and C. J. Tan [1976]. Register assignment algorithm — II, Report RC 6262, IBM Thomas J. Watson Research Center, Yorktown Heights, New York.

  Google Scholar 

• Knuth, D. E. [1977]. A generalization of Dijkstra's algorithm, Dept. of Computer Science, Stanford University.

  Google Scholar 

• Lesk, M. E. [1975]. LEX—a lexical analyzer generator, CSTR-39, Bell Laboratories, Murray Hill, N. J.

  Google Scholar 

• Lowry, E. S., and C. W. Medlock [1969]. Object code optimization, Comm. ACM 12:1, 13–22.

  Google Scholar 

• Luccio, F. [1969] A comment on index register allocation, Comm. ACM 10:9, 572–574.

  Google Scholar 

• Marrill, T. [1962]. Computational chains and the simplification of computer programs, IRE Trans. on Electronic Computers, EC-11:2, 173–180.

  Google Scholar 

• Miller, P. L. [1970]. Automatic Code-Generation from an Object-Machine Description, MAC TM 18, Massachusetts Institute of Technology, Cambridge, Mass.

  Google Scholar 

• Nakata, I. [1967]. On compiling algorithms for arithmetic expressions, Comm. ACM 10:8, 492–494.

  Google Scholar 

• Newcomer, J. M. [1975]. Machine-independent generation of optimal local code, Ph. D. Thesis, Computer Science Department, Carnegie-Mellon University.

  Google Scholar 

• Paterson, M. S., and C. E. Hewitt [1970]. Comparative schematology, Record of Project MAC Conference on Concurrent Systems and Parallel Computation, pp. 119–128.

  Google Scholar 

• Paul, W. J., R. E. Tarjan, and J. R. Celoni [1976]. Space bounds for a game on graphs, Proc. 8th Annual ACM Symposium on Theory of Computing, pp. 149–160.

  Google Scholar 

• Prabhala, B., and R. Sethi [1977]. A comparison of instruction sets for stack machines, Proc. 9th Annual Symposium on Theory of Computing.

  Google Scholar 

• Redziejowski, R. R. [1969]. On arithmetic expressions and trees, Comm. ACM 12:2, 81–84.

  Google Scholar 

• Schneider, V. B. [1971]. On the number of registers needed to evaluate arithmetic expressions, BIT 11:1, 84–93.

  Google Scholar 

• Sethi, R. [1975]. Complete register allocation problems, SIAM J. Computing 4:3, 226–248.

  Google Scholar 

• Sethi, R., and J. D. Ullman [1970]. The generation of optimal code for arithmetic expressions, J. ACM 17:4, 715–728.

  Google Scholar 

• Simon, R., and R. C. T. Lee [1971]. On the optimal solution to AND/OR series-parallel graphs, J. ACM 18:3, 354–372.

  Google Scholar 

• Stockhausen, P. F. [1973]. Adapting optimal code generation for arithmetic expressions to the instruction sets available on present-day computers, Comm. ACM 16:6, 353–354. Errata, 17:10 (Oct. 1974) 591.

  Google Scholar 

• Ullman, J. D. [1976]. The complexity of code generation, in J. F. Traub (ed.) Algorithms and Complexity, Academic Press, New York, pp. 53–70.

  Google Scholar 

• Waite, W. M. [1974]. Optimization, in Bauer and Eickel (eds.) Compiler Construction: An Advanced Course, Springer-Verlag, New York, pp. 549–602.

  Google Scholar 

• Walker, S. A., and H. R. Strong [1973]. Characterization of flowchartable recursions, JCSS 7:4, 404–447.

  Google Scholar 

• Wasilew, S. G. [1971]. A compiler-writing system with optimization capabilities for complex order structures, Ph. D. Thesis, Northwestern University, Evanston, Ill.

  Google Scholar 

• Yhap, E. F. [1975]. General register assignment in presence of data flow, RC-5645, IBM Thomas J. Watson Research Center, Yorktown Heights, New York.

  Google Scholar 

Download references