I suppose the reason why it "doesn't have too much written about it online" is because almost no one seems to call it "relaxation" - as someone who has been working in Asm for decades, this is the first time I've heard of that term. Everyone usually calls this "jump offset optimisation", "instruction encoding selection/optimisation", or some other variant of those words. Incidentally, the article doesn't mention the terms "near" and "short" jumps (16/32 and 8-bit displacement, respectively), which places it in a bit of an island with respect to others looking for related information on this topic. Instead I was expecting a post about how relaxing it is to read/write assembly language...
This goes all the way back to OPTASM in the 80s, if not earlier:
Essentially, the byte array holding the instruction has to be re-allocated because it has to grow larger
No it doesn't - just do one pass to figure out the maximum size (i.e. all instructions are the longest variant), and allocate a buffer of that size. You can be somewhat more intelligent by not increasing the size for the jumps that won't ever grow - e.g. backward ones ones whose target has been resolved already, and there aren't enough possibly-growing jumps between it and the current position to overflow the offset. Now iterate the code generation, moving the necessary bytes in the buffer forward when you hit a forward reference that's too far, until you reach the end. All done and ready to output, without any excess copying or messing around with linked lists. That's what the older assemblers which had this optimisation did, and they were plenty fast. (Rule of thumb: pointer chasing and small allocations are bad. Arrays and big blocks are good.)
In the fall of 1978, I was taking Prof. Szymanski's EECS 217 class, in which the main project was to write a toy assembler. He mentioned this paper of his, but it was not part of the course. At the time, nobody was doing anything with microprocessors in the department; we had a PDP-11/45 running Unix, and the university had an IBM 360/91 for card-punch batch jobs and a new 370/148 (158?) with graphics terminals. The later machines had different length jump instructions, I believe, so perhaps that inspired him.
The ld program distributed with binutils refers to this process as relaxation pretty extensively - you can see it in the ".map" file output or by greping the source for ld.
EDIT: The term is even in the wikipedia article for linker [1], although with a broader definition.
It took me an embarrassingly long time to figure out what the obscure ld error messages about relaxation were actually referring to.
Optimising call distances in the assembler is pretty easy, but the big win is in the linker, because this allows you to optimise calls between procedures. Of course, you then need a linker which knows how to edit compiled machine code to change the kind of call. FWIW, I do a lot of embedded stuff, and I have very rarely met an embedded architecture where ld would do relaxation properly, and usually end up turning it off.
I always kind of figured that the first pass would emit the most general form of a jump, then shorten it if possible, but I guess it works the other way around too.
If you start with the most general form you won't always get an optimal solution, because two jumps may be blocking each other from optimizing. TASM does it that way. Consider (16-bit NASM):
This is interesting. For a while, like a few, I thought the solution was to assume the maximum and then iteratively optimize to shorter sequences. I think I even read that in that book on Assemblers and Linkers online. The counter example below by @rer0tsaz showed me that I wasn't thinking hard enough about the problem :-)
Is this a general problem. For example, is this a limited form of Bin Packing?
Or is there a general solution for problems like these?
11 comments
[ 3.2 ms ] story [ 37.5 ms ] threadThis goes all the way back to OPTASM in the 80s, if not earlier:
http://archives.scovetta.com/pub/walnut-creek/JSAGE/ZNODE3/I...
https://books.google.com/books?id=FC-L2faxEVkC&pg=PA43&lpg=P...
FASM is well known for this too:
https://en.wikipedia.org/wiki/FASM#Design
Essentially, the byte array holding the instruction has to be re-allocated because it has to grow larger
No it doesn't - just do one pass to figure out the maximum size (i.e. all instructions are the longest variant), and allocate a buffer of that size. You can be somewhat more intelligent by not increasing the size for the jumps that won't ever grow - e.g. backward ones ones whose target has been resolved already, and there aren't enough possibly-growing jumps between it and the current position to overflow the offset. Now iterate the code generation, moving the necessary bytes in the buffer forward when you hit a forward reference that's too far, until you reach the end. All done and ready to output, without any excess copying or messing around with linked lists. That's what the older assemblers which had this optimisation did, and they were plenty fast. (Rule of thumb: pointer chasing and small allocations are bad. Arrays and big blocks are good.)
http://dl.acm.org/citation.cfm?id=359474
Interesting paper, by a rather familiar author. I noticed the date coincides with the introduction of the 8086, but the paper makes no mention of it.
EDIT: The term is even in the wikipedia article for linker [1], although with a broader definition.
[1] https://en.wikipedia.org/wiki/Linker_(computing)#Relaxation
https://en.wikipedia.org/wiki/Linker_(computing)#Relaxation
It took me an embarrassingly long time to figure out what the obscure ld error messages about relaxation were actually referring to.
Optimising call distances in the assembler is pretty easy, but the big win is in the linker, because this allows you to optimise calls between procedures. Of course, you then need a linker which knows how to edit compiled machine code to change the kind of call. FWIW, I do a lot of embedded stuff, and I have very rarely met an embedded architecture where ld would do relaxation properly, and usually end up turning it off.
@rer0tsaz - this is a great counter example.
Is there a general form for these types of problems and solutions?
Also, I wonder how often instruction sequences like that would occur.
Is this a general problem. For example, is this a limited form of Bin Packing? Or is there a general solution for problems like these?