Misusing Floating-Point Arithmetic for Fun and Profit
You may recall that this compiler worked on System/360 , a line of computers with four floating-point registers, one of which it used for all floating-point computation, and two others of which it used to count how many statements had executed. Strange though that technique may seem, it is nothing compared with how the compiler used the fourth register: It initialized the register to zero and never changed it.
It turns out that there were several distinct reasons to keep zero in a floating-point register.
The most obvious reason was that occasionally it was useful to be able to set a floating-point value to zero, either in memory or in another register, and having zero already in a floating-point register made it easier to do so.
A less obvious reason was that, as on most computers, the usual representation of floating-point zero is the same bit pattern as fixed-point zero, namely all bits zero. Therefore, the compiler could use the floating-point register to store a fixed-point zero in memory. Of course, a fixed-point register could have been used for this purpose, but this particular compiler did so little floating-point arithmetic that it was more convenient to use a floating-point register.
However, the real point of keeping zero in a floating-point register was to make it easier to do address comparisons. This notion is so weird that it warrants an explanation.
System/360 was introduced to the world in 1964. At the time, its designers felt that 16 megabytes of memory would be enough for the foreseeable future, so they gave the machine 24-bit addresses and 32-bit integer registers. As a result, it was common for programs — including the SPITBOL compiler — to store an address in the low-order 24 bits of a word along with other information in the high-order 8 bits. In general, instructions that dealt with addresses would disregard those high-order 8 bits.
Suppose you have a linked list in which each link consists of a 24-bit address with 8 high-order bits that are not part of the address. How would you figure out whether you had come to the end of the list? The answer, of course, is that you would check whether the address part of the link is zero.
However, this check was not as easy as it looks. Although using a word as an address disregarded the high-order bits, there was no instruction to compare addresses. Instead, a program would have to
- Load the entire word into a register
- Execute a separate instruction to turn off the high-order 8 bits
- Check whether the result was zero
This operation would require three instructions, and would also need a register devoted to it.
What the SPITBOL compiler did instead was to use a short-precision floating-point compare instruction to compare the word to the register that it kept permanently zero. Short-precision was 32 bits; long-precision was 64 bits. This comparison would work because of the nature of the System/360 floating-point format: The low-order 24 bits of a short-precision floating-point number were the fraction, and a floating-point value is zero if and only if every fraction bit is zero. In other words, the high-order 8 bits, which the program wanted to ignore, corresponded to the sign bit and the exponent, which a floating-point comparison would disregard.
As a result of this technique, every place in which the compiler followed a linked list could execute a single floating-point compare instruction, instead of executing the three instructions. In either case, the instruction(s) would be followed by a conditional jump.
This code makes me cringe every time I think about it — although on reflection, I am not sure why. At least the first objections that come to mind don't apply:
- System/360 floating-point arithmetic is precisely defined, so there is no question about whether the technique works in all cases: It does.
- It's not reasonable to object that the technique is nonportable: The compiler is in assembly language, so it's not portable anyway!
- Although the technique is tricky enough that I would not have come up with it myself, it was well documented: Once you've read the documentation, it isn't particularly hard to understand.
So this is probably one more of those circumstances in which a programming technique that looks truly awful at first glance turns out to be the best way to solve its particular problem.