horst@techfak.uni-bielefeld.de (04/30/91)
Does anyone know what TAGGED DATA instructions are useful for and how to use them? Tagged data is assumed to be 30 bits wide followed by trwo bits set to zero. The SPARC allows add and subtract instructions on tagged data. HH [Most likely it's for immediate integers in a Lisp-like system that uses tagged pointers, but I hope someone who actually knows will tell us. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
moss@cs.umass.edu (Eliot Moss) (04/30/91)
Well, I cannot speak for SPARC and say what the instructions were DESIGNED for, but as the moderator pointed out, they can be used to good effect in implementing languages such as Smalltalk and LISP, which used tagging to distinguish (small, i.e., 30-bit) integers from pointers. One uses a tag of 00 in the low bits for integers, and a tag of 01 (say) for pointers. All offsets from pointers are scaled by -1 to compensate for the 01 in the low bits. Note that integer add/sub on pointers will be trapped (if you used the tagged add/sub instructions) and pointer access off an integer can also be trapped. This means you don't have to insert gobs of tag checking code all over the place. Multiply and divide tend to require scaling and adjustment anyway, and bsides, they take long enough, and are rare enough (compared with add/sub) that additional penalty in handling the tags is judged "acceptable". -- J. Eliot B. Moss, Assistant Professor Department of Computer and Information Science Lederle Graduate Research Center University of Massachusetts Amherst, MA 01003 (413) 545-4206, 545-1249 (fax); Moss@cs.umass.edu -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
William.Lott@cs.cmu.edu (04/30/91)
horst@techfak.uni-bielefeld.de writes: > Does anyone know what TAGGED DATA instructions are useful for and how to > use them? Tagged data is assumed to be 30 bits wide followed by trwo bits > set to zero. The SPARC allows add and subtract instructions on tagged > data. > > HH > [Most likely it's for immediate integers in a Lisp-like system that uses > tagged pointers, but I hope someone who actually knows will tell us. -John] > -- > Send compilers articles to compilers@iecc.cambridge.ma.us or > {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. The tagged-add and subtract instructions are just like the regular add and subtract instructions except that they check to make sure the two low bits of both operands are zeros and that the add doesn't overflow. One flavor sets the overflow flag if these conditions are not met, and the other flavor causes an exception. In CMU Common Lisp, we represent fixnums as 30 bits of data followed by two zero bits. (We had actually decided on this representation long before any of use knew anything about the SPARC.) We have found several ways to utilize these instructions. The most obvious use is when the arguments to an add are declared to be fixnums. Then we just use the taddcctv instruction which whill trap if either are is not a fixnum. We have the exception handler set up to distinguish between the case when the two fixnums form a bignum when added and the case when one of the operands wasn't really a fixnum. The non-trapping version can be used to check to see if something is a fixnum. Just add it to zero. If the overflow flag is set afterwards, it wasn't a fixnum. Basically, the only time these instructions are going to be useful is if you are representing some kind of signed integer with the two low bits zero. You can use them to check for this case in parallel with and add or a subtract. But unless your language tags run-time values, they aren't much use. -William Lott CMU Common Lisp Group
weaver@Sun.COM (Michael Weaver) (04/30/91)
In article <9104291542.AA11213@flora.techfak.uni-bielefeld.de> horst@techfak.uni-bielefeld.de writes: >Does anyone know what TAGGED DATA instructions are useful for and how to >use them? ... Tagged data instructions apparently were borrowed from the Berkeley SOAR (Smalltalk on a RISC) project. Studies have shown that much of the time in used by Smalltalk programs is taken up in adds and subtracts, even though for most adds and subtracts both operands are integers, because in practice for every add (etc.) a method lookup must be done. That is, the type of the both operands must be checked, and then a piece of code that will perform the operation on this combination of operand types must be found and invoked. Tagged instructions can be used (on SPARC) by generating instructions as though all these adds and subtracts were on integers, but using the tagged add (etc.) instruction rather than add. Integers are encoded by setting the two low-order bits of a word to zero to indicate an integer, and the upper 30 to represent the value. Data types other than integers must have at least one of the two lowest bits set, and the upper 30 bits can be encoded arbitrarily, so that the 32 bits can be used (by software) to determine the type and value of the operand. If two such integers are added with a tagged add, the result is the sum, similarly encoded. However, if either of the operands of a tagged add has either of its low bits set, then a trap is taken. The trap handler then can check both operands, dispatch to appropriate code to effect the add, and then resume execution following the add. The overall effect is that adds of integers happen quickly while adds of other types are slowed down a bit. If most of the adds are actually integers, the overall run times are improved. I imagine that Lisp can benefit from these instructions similarly. See Bush et. al. 'Compiling Smalltalk-80 to a RISC', in Proceedings Second International Conference on Architectural Support for Programing Languages and Operating Systems (ASPLOS II). Michael Weaver. -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.