Type tagging format

This entry was taken from my old Fenris development blog. It was originally posted on April 29, 2008. Although the Fenris project is now defunct, I think these old entries have some general appeal, so I've added them to this blog.

For the last several weeks, I've been working on the beginnings of a copying garbage collector for Fenris. So far, I've written an allocator and type tagging generation.

Type tags are small bitfields that describe the format of a heap block or stack frame to the collector at runtime. They are easy to generate for struct types and only slightly more difficult for functions in most respects, but non-volatile registers are turning out to be a serious problem.

General purpose registers can store either data or pointers to the heap. When a function is called, volatile registers may be saved onto the stack by the caller. Non-volatile registers may also be saved by the callee. For the caller, volatile registers are mapped to actual variables that are well-typed, which means the locations to which they are saved can be tagged. However, the callee has no way to know what kind of data are in the non-volatile registers (and it doesn't care). This means that the locations these are saved to cannot be tagged without modification of the calling convention.

In order to solve this, we need to establish some invariants. One option is to prohibit non-volatile registers from holding heap pointers. This might have a significant impact on performance since we would be spilling a lot more variables, but it would be very easy to implement and transparent to the programmer.

Another option is to abandon the whole type tagging system and instead use tag bits on all words on the stack, which is what OCaml does. Every pointer word in memory has a bit set indicating it is a pointer. Every non-pointer has the bit cleared. The compiler generates code to "fix" values as they are moved into and out of registers. Again, this has some impact on performance, although probably much less than the previous option. The main compromise is that data words are constrained to 31 bits, and code generation will be a real pain, especially when we get to floating point values. This is also incompatible with C functions, which we'd eventually like to support.

A third solution is to use a different algorithm. Garbage Collection by Jones and Lins mentions Mostly Copying collection in the context of non-conservative collectors for C. This conservatively scans the roots (stack frames, globals, etc.) but non-conservatively scans the rest of the heap. Effectively, everything is copied except objects referenced from the stack. However, this creates some fragmentation on the heap. We end up either making performance compromises on the allocator or making the whole system much more complicated. More research is necessary though.