Re: variable length instructions, was Chicken or the Egg?

> [there can be two fixpoints]


> [As I think we've said three times now, this is certainly possible in
> theory. I'd still like to hear whether it occurs in practice often
> enough to matter. -John]


I think it depends on the architecture. On transputers, you shift
constants nibble-wise in the operand register on top of the register
stack. That means constants up to 4 bit plus 4 bit opcode fit in a
single byte. On the contrary, a 32 bit operand takes 8 bytes in
total, as you need 7 pfix/nfix instructions plus the final instruction
with the last 4 bits and the opcode. (It's cheaper to load it from a
nearby memory location and there are other optimisations, but that's
beside the point.)


You would enlarge programs a lot by starting with the assumption that
the instruction needs 8 bytes instead of one and I am sure that it
will increase overall code size, so it does matter. Programs for CPUs
like the 68k with short and long jumps probably rarely experience that
problem and being able to terminate with a legal program after a fixed
number of passes in certainly interesting.


And, as I wrote, if you do not only encode relative addresses that
way, there will be examples where either algorithm produces the worse
result. Starting with small instructions does not garuantee to yield
the shortest program.


To finally answer the question: I never checked what would happen if
you started with long instructions, because for Transputers, it
sounded like a useless thing to do. Sorry, I have no facts, just
guesses.


Michael
[The algorithm is to start with all branches that might need to be
long as long, then look for candidates to shorten until you don't find
any more. I don't see any reason to think that wouldn't work on a
Transputer, even if nearly all the branches end up being shortened. -John]

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