hedrick@athos.rutgers.edu (Charles Hedrick) (01/01/88)
Some comments on the use of tags in the SPARC and DEC-20. We should not give the impression that either of these machines have hardware tagging in quite the generality of the Lisp Machine. It is true that both of these machines were designed specifically with Lisp in mind. However I believe the ability to use tags on the DEC-20 fell out by accident. Lisp was considered in the original PDP-10 design, but the main effect was all those half-word instructions. This allowed a full-word (36-bit) CONS cell, with half-word (18 bit) pointers for the CAR and CDR. Since the PDP-10 had 18 bit addresses, that was fine. One could also have 72-bit CONS cells with two tagged pointers, but nobody did that and I doubt that the designers had it in mind. With the DEC-20, the address space expanded to 30 bits (only 24 bits of which were actually implemented), and indexing was done in a manner that allowed a representation with 6-bit tag fields. We (I supervised the writing of two versions of DEC-20 Lisp) used it to give 32-bit integers and reals (using several adjacent type codes), and typed pointers. This cleaned up lots of code, and made for nice fast type dispatches. We were able to come up with a code sequence that resulted in almost no type-checking overhead for integer add and subtract (i.e. one or two extra instructions, for about a factor of 2 slowdown. But it is very unlikely that a high enough percentage of the instructions would be arithmetic that this would be noticable). Everything other than 32-bit integers trapped to a subroutine for handling. However as far as I can tell, the DEC-20 designers were not thinking of this when they did the design. It just fell out of the way addressing happened to work. Clearly the SPARC designers were thinking of Lisp. There are special opcodes for tagged add and subtract. The tag is the low-order two bits. Integer arithmetic is done. In addition to the other tests, if either operand has a non-zero tag field, overflow is set. I don't know how other implementors would use this, but I have some first thoughts. (Note however that I have no plans to do a SPARC Lisp. Several quite competent groups are doing it already.) Obviously a tag value of zero is used for 30-bit integers. I think I would use tag values of 1 and 3 for 31-bit reals and tag value 2 for numbers that need to be pointers (bignums and larger reals). I suggest type codes 1 and 3 for reals so that the 31 high-order bits are significant. Tag value 2 would indicate a pointer to an object whose first byte would be a further type code. Typical code would do the add or subtract instruction, and follow that immediately by a conditional branch, which would branch to an appropriate exception-handling routine. There would have to be several entry points to exception-handling, to handle arguments in various possible combinations of registers. (This is the reason for suggesting test on condition rather than a trap, although depending upon details that I haven't looked at, one might be able to win with a trap handler.) This implementation would add one extra instruction for each add or subtract that happened to be an integer (the conditional branch, which would not be taken). 31-bit floating point would require something on the order of 10 additional instructions, assuming we were willing to have the compiler compile specific code for each individual instance, and that no no-op's are needed. [branch, move arg 1, mask arg 1, indexed branch, move arg 2, mask arg 2, indexed branch, mask arg 1, mask arg 2, float operation, branch, assuming the no-ops can be eliminated]. If the machine is really 1.6 MFLOP and 16 RISC MIP, adding 10 non-floating point instructions per floating operation slows it down about a factor of 2, which I would find perfectly acceptable for generic arithmetic applied to floating point. 64-bit floating point would have the above 10 instructions, plus a CONS and some moves. Probably it would still be close to a factor of 2 slow-down, since a double-precision floating point is somewhat slower also. (Of course this doesn't count the overhead of the eventual garbage-collection.) The dispatch overhead for bignums would almost certainly be invisible. Let me hasten to say that I haven't really tried any of this, but I doubt that I'm off by much. In summary it seems to me that the SPARC design would get roughly the same results as the DEC-20, namely a slowdown of about a factor of 2 in arithmetic instructions. Since not all of your program is arithmetic instructions, the actual results should be better than that, like maybe 1.5. I find that quite acceptable for generic arithmetic, and can't imagine that people would bother to use type declarations except in very unusual cases. Without tag support what I think would be hurt the most is simple counting. I believe it would be slowed by roughly an order of magnitude over what you could get with optimal declarations. In addition, tag support on SPARC could be used to help in implementing type security. In order to do this right, one would have to live with 30-bit short floats, and use one of the tag values for characters (which are the only other object in Lisp that one would like to have not take up any heap space). With this encoding one could make sure that one did not try to follow pointers that were actually integer constants, etc. This would be based on the fact that SPARC requires full-word operations to be done on objects at full-word boundaries. In this encoding there would be only one tag value for objects that are pointers. Suppose that value is 3. Then representations for objects on the heap would be arranged so that full-word operations were done with an offset of 1, i.e. instructions like load ... 1(%i0). If such an instruction is done with anything not ending in 3 (i.e. an integer, short floating-point or char), an odd-address trap occurs. This is the first time I have ever heard the RISC alignment restriction advertised as an advantage, but I agree that in fact one could make use of it as such.