How to find gc roots in a stack machine?

Question

I am writing a compiler for a fairly standard stack machine. Now I want to add a garbage collector. I see that I could generate some kind of "stack cards" to find out which variables are the gc roots in each activation record. However, I have no idea how to deal with intermediate values ​​pushed onto the stack at runtime. The language I'm compiling is Pascal-like, so I don’t need, and I don’t want to use tags to define pointers from other data types.

I would appreciate any hints / pointers on how

• Find the roots of gc on the stack at any given time (i.e. how to determine which of the intermediate values ​​that were inserted on the stack are the roots of gc).
• The usual forms of encoding this information (that is, how to create and encode "stack cards").

Many thanks! Nicolas

Answer 1

A simple solution is to explicitly store the type of each stack entry. Then you do not need a stack card; if the type is a "reference", then the entry is the root of the GC. This approach is especially convenient for debugging, as you can easily display the (typed) contents of the stack.

If you really want to use stack cards, a simple solution is to create a stack card for each instruction. You do this by tracking the contents of the stack during compilation or by performing a second pass on compiled instructions. Then, when searching for GC roots, for each frame on the stack, you use the card that comes with the current instruction.

Answer 2

Another option is to use a shadow stack: the stop link that you support. This is the easiest way to implement.