Hi Folks -

[Cross-posted to VM-dev where this topic really belongs]

As others have noted, it's Really Hard (tm) to add a new immediate type. 
However, having said that, I would like to outline an approach that I've 
contemplated in the past (up to the point of actually implementing a 
major part of it). The main issue with tag bits is that they are for 
obvious reasons few and far inbetween so it's hard to get the maximum 
value out of changing the VM for a single new immediate type. In 
addition there is a major issue with the range of bits for SmallIntegers 
- each tag bit takes away from the number of bits available for small 
integers and that's not good since many algorithms are designed to fit 
into 32 bits and the more often you have to fall back to general large 
int arithmethic, the worse it gets.

Today, we use a single tag bit which differentiates small integers from 
"regular" pointer objects. (Not so) incidentally, this is bit zero so 
that pointer objects (which are always aligned to 32bits) have a 
"natural" LSB of zero for addressing. However, since pointer objects are 
32bit aligned, there is an UNUSED(!) bit pattern even if we leave small 
integers alone:

xxxxxxxx00 -> object pointer (tag bit not set; divisible by four)
xxxxxxxx10 -> Unused (tag bit not set; but not a valid pointer)
xxxxxxxx01 -> SmallInteger (tag bit set)
xxxxxxxx11 -> SmallInteger (tag bit set)

So what one could do is to use that formerly unused bit pattern for 
"something different". But wait! Unfortunately, the bit pattern is 
not-so-unused after all; the garbage collector makes use of it (see the 
definition of HeaderTypeGC in ObjectMemory) to flag objects that are 
currently being marked. This needs to be fixed before the bit pattern 
can be used and I'll leave that as an exercise for the interested reader 
because it's a strict prerequisite for anything that follows below and 
can be done independently (HINT: A cheap way out -and yes, there are 
others- is to relocate that bit; most people are likely just as happy 
with half of the addressable memory).

Once the GC usage of that flag is fixed we can decide what to do with 
the pattern. But given that we only have a single bit it's probably 
worthwhile to get a little bit more out of it than just one type. So 
instead of declaring "yet another immediate", I say let's use another 
6bit to index into an array(!) of immediate classes (very much like 
compact classes) and use the 24 remaining bits to represent the actual 
value (and note that you can obviously adjust that number for different 
trade offs of number of immediate class vs. bits of accuracy). Then you 
need primitives that convert back and forth between a small integer and 
one of those immediates but that's about it.

IIRC (it's been a while since I looked at it) those are the issues that 
you'd have to deal with. There are some more nice things about this 
particular scheme beside preserving small int bit range btw; for 
example, class lookup can test the low order two bits and if non-zero 
index into a 256 element array (with the odd slots filled with 
SmallInteger) so that there is no additional overhead for fetching the 
class of an object. Whether 24 bits are useful is another good question 
though; there are certainly some places that could use them since you 
can also split 24 bits into 2x12 (immediate points) and 3x8 (immediate 
colors) or 4x6 (dunno what you'd use that for though ;-)

So the bottom line is that, yes, while it is hard to add new immediate 
types, it is far from impossible - it's a goodly amount of work and (the 
way I look at it) not worth doing it for just a *single* new immediate 
type; but being able to have up to 64 immediate types just *may* be 
worth it.

In any case, I think that if anyone is interested in this issue the best 
way to go about it is to fix the usage of that xx10 bit pattern in the 
garbage collector and take it from there. Good Luck!

Cheers,
   - Andreas

Joerg Beekmann wrote:
> Can anyone comment on how much work would be involved in
> 1) Adding a new 32bit field to the object header
> 2) Adding a new immediate type like integer, presumable by adding 
> another tag bit.
> 
> I'm just looking for a very rough estimate. Do these tasks involve 
> tracking down a bunch of constants and then rebuilding everything, 
> tedious but a with a known path to follow. Or will this involve much more.
> 
> regards Joerg
>