Assembling Code for Machines with Span-Dependent Instructions 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 formf this restriction is relaxed by allowing these operands to be more general assembly-time expressions, then the problem is shown to be NP-complete. CACM April, 1978 Szymanski, T. Span-dependent instructions, variable-length addressing, code generation, assemblers, compilers, NP-complete, computational complexity. 4.11 4.12 5.25 CA780406 DH February 26, 1979 3:49 PM 2626 4 3110 2786 4 3110 2840 4 3110 2858 4 3110 2919 4 3110 3017 4 3110 3110 4 3110 3110 4 3110 3110 4 3110 3174 4 3110 2194 5 3110 2629 5 3110 2858 5 3110 3110 5 3110 3110 5 3110 3110 5 3110