Assembler Relaxation(eli.thegreenplace.net)
eli.thegreenplace.net
Assembler Relaxation
http://eli.thegreenplace.net/2013/01/03/assembler-relaxation
3 comments
'Relaxation' seems to be linker terminology:
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.
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.
The term to search for papers is "span-dependent instruction", which goes back to 1978.
This one?
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.
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.
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.
[1] https://en.wikipedia.org/wiki/Linker_(computing)#Relaxation
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
[deleted]
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?
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?
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):
a:
times 124 nop
jmp b
jmp a
times 125 nop
b:@SloopJon - I thought the same thing when I looked at this years ago. In fact, many older books/articles mentioned.
@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.
@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.
This 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.)