Code Generation and Storage Allocation for Machines with Span-Dependent Instructions

ABSTRACT

Many machine languages have two instruction formats, one of which allows addressing of “nearby” operands with “short” (e.g. one word) instructions, while “faraway” operands require “long” format (e.g. two words). Because the distance between an instruction and its operand depends upon the formats of the intervening instructions, the formats of different instructions may be interdependent. An efficient technique is discussed which optimally assigns formats to instructions in a given program and is practical in space as well as time. The more sophisticated problem of arranging operands within programs is discussed. Unfortunately, it is unlikely that an efficient algorithm can guarantee even a good approximation for this problem, since it is shown that r-approximation is NP-complete. Finally, implications of these problems for hardware and software design are considered.

REFERENCES

• 1: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 2: Common assembler language user's manual. Interdata Corp., Oceanport, N.J., 1974.
• 3: Gideon Frieder , Harry J. Saal, A process for the determination of addresses in variable length addressing, Communications of the ACM, v.19 n.6, p.335-338, June 1976 [doi>10.1145/360238.360241]
• 4: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 5: GAREY, M.R., AND JOHNSON, D.S. Performance guarantees for heuristic algorithms. In Algorithms and Complexity: New Directions and Results, J.F. Traub, Ed., Academic Press, New York, 1976, pp. 41-52.
• 6: HARRIS, K. The design and implementation of a compiler for a mini-computer. M.S. paper, Comptr. Sci. Dept., Pennsylvania State U., University Park, Pa., Aug. 1976.
• 7: JOHNSON, D.S. Approximation algorithms for combinatorial problems. J. Comptr. Syst. Sci. 9, 3 (Dec. 1974), 256-278.
• 8: KARP, R.M. Reducibility among combinatorial problems. In Complexity of Computer Computat/ons, Miller and Thatcher, Eds., Plenum Press, New York, 1972.
• 9: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 10: Donald L. Richards, How to keep the addresses short, Communications of the ACM, v.14 n.5, p.346-349, May 1971 [doi>10.1145/362588.362596]
• 11: ROBERTSON, E.L. Code generation for short/long address machines. Tech. Suture. Rep. 1979, Math. Res. Ctr., U. of Wisconsin, Madison, Wis., Aug. 1977.
• 12: ROCHE, P. Code generation for PL 1600. M.S. paper, Comptr. Sci. Dept., Pennsylvania State U., University Park, Pa., Feb. 1977.
• 13: Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
• 14: Thomas G. Szymanski, Assembling code for machines with span-dependent instructions, Communications of the ACM, v.21 n.4, p.300-308, April 1978 [doi>10.1145/359460.359474]
• 15: 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: Code generation

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

General Terms:
Design, Languages, Performance, Theory