Automatic storage optimization

ABSTRACT

Most studies of optimization techniques for higher level languages have focused on improving execution time of generated programs, often at the expense of increased storage. When storage optimization has been addressed, it is usually in conjunction with time optimization, such as in instruction-reducing code transformations. In the Bliss Compiler (WJWHG75), a storage-optimizing compiler, transformations that reduce register temporary storage are also performed, but automatic overlay of program variables is not addressed. The rising popularity of mini-computers and micro-processors suggests that the time has come to examine the problem of automatic storage optimization in its totality. Because lack of space has always been a problem in the small systems environment, the proliferation of small machines implies the growing importance of the problem. Although the decreasing cost of memory may mitigate this trend, a variant of Murphy's Law ensures that program size will always increase faster than the available storage. In other words, programmers always write programs that don't fit, and, as time goes on, more of them will be doing it.

REFERENCES

• 1: Allen, F. E. and Cocke, J., "A Catalogue of Optimizing Transformations," Design and Optimization of Compilers, Rustin, R. (ed.), Prentice-Hall, 1972, pp. 1-30.
• 2: A. V. Aho , S. C. Johnson , J. D. Ullman, Code generation for expressions with common subexpressions (Extended Abstract), Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.19-31, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811537]
• 3: Conversation with John Cocke, Ashok Chandra and Gregory Chaitin, IBM Research, 1977.
• 4: Conversation with Gregory Chaitin, IBM Research, 1979.
• 5: Janet Fabri, Automatic storage optimization., 1979
• 6: M. R. Garey , D. S. Johnson, The Complexity of Near-Optimal Graph Coloring, Journal of the ACM (JACM), v.23 n.1, p.43-49, Jan. 1976 [doi>10.1145/321921.321926]
• 7: Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57), North-Holland, 2004
• 8: Harrison, W., "Compiler Analysis of the Value Ranges for Variables," IEEE Transactions on Software Engineering, Volume 3, 1977, pp. 243-250.
• 9: Various conversations with Alan Hoffman, Ellis Johnson, and Larry Stockmeyer (IBM Research) and Martin Golumbic (Courant Institute of Mathematical Sciences, New York University), 1977, 1978, and 1979.
• 10: Brian W. Kernighan, Optimal Sequential Partitions of Graphs, Journal of the ACM (JACM), v.18 n.1, p.34-40, Jan. 1971 [doi>10.1145/321623.321627]
• 11: Luigi Logrippo, Renamings and Economy of Memory in Program Schemata, Journal of the ACM (JACM), v.25 n.1, p.10-22, Jan. 1978 [doi>10.1145/322047.322049]
• 12: Szekeres, G. and Wilf, H. S., "An Inequality for the Chromatic Number of a Graph," Journal of Combinatorial Theory, Volume 4 (1968), pp. 1-3.
• 13: Sethi, R., "Complete Register Allocation Problems," SIAM Journal of Computing, Volume 4, No. 1, 1975, pp. 226 ff..
• 14: 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
• 15: Warren, H. S., "Static Main Storage Packing Problems," Acta Informatica, Volume 9, pp. 355-376.
• 16: Yershov, A. E., "The ALPHA Automatic Programming System," Academic Press, 1971.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management

General Terms:
Management