Assembling code for machines with span-dependent instructions
Thomas G. Szymanski · Communications of the ACM · 1978
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.
Cited by 53 works. doi:10.1145/359460.359474 Open-access PDF
Authors
References
- The Design and Analysis of Computer Algorithms
- Reducibility among Combinatorial Problems
- The complexity of theorem-proving procedures
- Complexity of Computer Computations
- The UNIX time-sharing system
- The UNIX time-sharing system
- The design of an optimizing compiler
- How to keep the addresses short
- A process for the determination of addresses in variable length addressing