Re: variable length instructions, Chicken or the Egg?

  Randall Hyde <rhyde@cs.ucr.edu> writes:
>It is also the case that that optimizing jump lengths is an
>intractable problem (i.e., NP-Complete or thereabouts).


You probably think of: Szymanski, T.G.: Assembling code for machines
with span-dependent instructions, CACM 21, p. 300-308.


Note that if you just use simple target addresses of the form
"label+/-constant", the problem is tractable. Only if you allow more
complex address expressions, such as label+label-label, you run into
NP-completeness.


Concerning our dear moderator's question, the paper reports compiling
a Unix kernel with the Unix assembler (which starts by assuming large
instructions, but performs only one intermediate pass of reducing
instruction sizes) and the optimal assembler described in the paper
(which uses a graph data structure to represent the dependences
between instructions): 27KB generated PDP-11 code containing 1424
span-dependent instructions; the original assembler used the long form
for 80 instructions, the new assembler for 60 (this seems unreasonably
high to me). The new assembler was also 25% faster than the original
one.


- anton

Return to the comp.compilers page.
Search the comp.compilers archives again.