How to add new immediate types (was: Re: Adding a new imediate type)

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: