Assembling code for machines with span-dependent instructions

ABSTRACT

Many modern computers contain instructions whose lengths depend on the distance from a given instance of such an instruction to the operand of that instruction. This paper considers the problem of minimizing the lengths of programs for such machines. An efficient solution is presented for the case in which the operand of every such “span-dependent” instruction is either a label or an assembly-time expression of a certain restricted form. If this restriction is relaxed by allowing these operands to be more general assembly-time expressions, then the problem is shown to be NP-complete.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: 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]
• 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: Karp, R.M. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds., Plenum Press, New York, 1972.
• 5: PDP-I 1 Processor Handbood. Digital Equipment Corp., Maynard, Mass., 1975.
• 6: 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]
• 7: Dennis M. Ritchie , Ken Thompson, The UNIX time-sharing system, Communications of the ACM, v.17 n.7, p.365-375, July 1974 [doi>10.1145/361011.361061]
• 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: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

General Terms:
Design, Languages, Performance, Theory

Keywords:
NP-complete, assemblers, code generation, compilers, computational complexity, span-dependent instructions, variable-length addressing