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

> 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.


> [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]


Ok, an example:


    jump destination (long)
    instruction (long)
    ...
    instruction (long)
destination


As I said, transputers encode _all address operands_ (jump, load,
store etc.) relative and nibblewise, which means the smallest jump is
a one-byte instruction and jumps 0-15 bytes forward. It suffices quite
often, given that the other instructions up to the destination are also
one-byte instructions and that's why it is suggested to start by assuming
that they are.


In the above example, you can not shorten the jump, because the
distance is quite large due to all the long instructions. The long
instructions can not be shortened for the same reason. A sequential
candidate selection will fail. Selecting candidates not sequentially,
but simultaneously, might work, but if you did that, you would in fact
start with short instructions. ;-)


The opposite example: AFAIK, a short jump on the 68k jumps +-32kbyte.
That's much further than what most jumps probably are, so you could
still use the short format, even if all instructions up to the target
are assumed to be long at this point. The algorithm will work fine.


My conclusion: If instructions don't vary much in length and in
particular, if short instructions still cover distances much larger
than actually needed, you probably won't see problems if starting with
long instructions, because the two fix points are very near each other.


Michael
[You iterate over the code until you don't find anything to shorten. In
the example above, assuming everything's a forward ref, I'd think you
could shorten the last long instruction, then the one before that, etc.
-John]

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