Re: variable length instructions, Chicken or the Egg?

anton@mips.complang.tuwien.ac.at (Anton Ertl)
18 Oct 2000 23:55:08 -0400

          From comp.compilers

Related articles
Re: Chicken or the Egg? michael@moria.de (2000-10-10)
Re: variable length instructions, Chicken or the Egg? joachim_d@gmx.de (Joachim Durchholz) (2000-10-12)
Re: variable length instructions, Chicken or the Egg? rhyde@cs.ucr.edu (Randall Hyde) (2000-10-15)
Re: variable length instructions, Chicken or the Egg? anton@mips.complang.tuwien.ac.at (2000-10-18)
Re: variable length instructions, Chicken or the Egg? walter@bytecraft.com (Walter Banks) (2000-10-19)
| List of all articles for this month |

From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Date: 18 Oct 2000 23:55:08 -0400
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 00-10-073 00-10-084 00-10-110
Keywords: linker, optimize

  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


Post a followup to this message

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