Re: Vax span-dependent jumps

Well, the nastiest case in production is the Inmos Transputer, which has a
different instruction length for each 4 bits of offset. 4 bits is 1 byte
of instruction, 8 bits is 2 bytes, 12 bits is 3, etc. A worst-case jump is
8 bytes.


Since every constant in the program is expressed this way, the problem is
put off until the linker. The linker has a nasty habit of being slow.
Eventually Cogent Research (where I used to work) rewrote it. Basically,
they build a list of all the non-constant offsets and the labels they're
relative to. Keep track of the distance between labels, beginning by assuming
they're all one byte long. Then run over the list extending things until
it stabilizes. I'm sure someone could come up with an example which only
lengthens one instruction per scan, and each instruction lengthens a few times,
but as long as it's only label1-label2, it's monotonically increasing
and you have reasonable worst-case run-time (and a lot faster than the wierd
heuristics that were in use before, in practice).


If you allow stranger expressions, I suppose it's possible for this to
produce non-optimal results, but it won't happen very often in practice.
--
-Colin
--

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