Re: variable length instructions, Chicken or the Egg?

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

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