Re: variable length instructions, Chicken or the Egg?

Randall Hyde <rhyde@cs.ucr.edu>
15 Oct 2000 16:30:10 -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: Randall Hyde <rhyde@cs.ucr.edu>
Newsgroups: comp.compilers
Date: 15 Oct 2000 16:30:10 -0400
Organization: Posted via Supernews, http://www.supernews.com
References: 00-10-073 00-10-084
Keywords: linker, optimize

Joachim Durchholz at joachim_d@gmx.de wrote on 10/13/00 10:01 AM:
> John wrote:
>> [... I always preferred
>> the other approach, start with everything long, then shorten until
>> there's nothing left to shorten, which has the advantage of being
>> fail-safe, all of the intermediate stages being valid code. -John]
>
> Why?
>
> I'd think that the only validity constraint on the intermediate forms is
> that they are suitable for the next round of lengthening.
>
> Regards,
> Joachim
> [I suppse, but I like a scheme that produces valid code even if it
> doesn't get quite to optimal. -John]


Elaboration on John's response:
It is also the case that that optimizing jump lengths is an
intractable problem (i.e., NP-Complete or thereabouts). By starting
with the longest opcode and working towards the shorter one, you can
always bail on the process if the code is degenerate and looks like
it's going to take to long to optimize it. Of course, it real
programs you never encounter the degenerate case, so the direction of
optimization is probably immaterial (i.e., worst case is NP-Complete,
but average case is probably O(n)). Randy Hyde


Post a followup to this message

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