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.