For garbage collection we need to know two things:
- Which memory regions were allocated?
- Given a memory region, is it reachable?
If in your instruction set
S must be a literal, then all memory addresses would be statically known. If
S can also read from
ACC, then you have unrestricted pointers and can write to arbitrary memory addresses. So neither does your VM have a concept of memory allocation nor is it possible to discuss reachability.
It is helpful to compare this with other systems.
C does know which memory regions were allocated because it is undefined behaviour to write to arbitrary addresses – you can access objects on the stack, you can malloc(), or you can use system calls mmap() to make a memory region available. In particular, malloc()/free() necessarily manage information that is largely comparable to a GC system.
Reachability in C is more complicated because any type information is erased at run time: you do not know whether a given word of memory is supposed to be a pointer. A GC system must therefore be conservative and assume that anything could be a pointer. However, you can only access memory without undefined behaviour if you hold a pointer into that memory region. Therefore, a GC system for C does not have to solve the Halting Problem, unless you are doing some seriously weird stuff like manually compressing pointers.
In a language designed for GC, pointer arithmetic is usually disallowed. You can only dereference pointers, not increment them. The only special case is arrays, which may contain metadata to allow runtime bounds checking. Since this is more restricted, it is easier to reason about such pointers and to perform a safer reachability analysis.
Many GC language implementations also keep runtime type information. Given an arbitrary memory region that has been properly allocated by the rules of that system, we can tell what type it has, which members it has, …. A GC system can then be exact and need not be conservative.
If such information is available at runtime we also have other options for better GC:
- Given a dependency graph between memory regions, we can move a memory region to a new location and update all pointers that point to it. This is useful for compacting garbage collectors: Since this prevents memory fragmentation, allocations can become much faster.
- If every memory region holds type metadata, it is easy to also add GC metadata, e.g. for tracing GC, or for reference counting.
It would be possible to adapt your instruction set to make a C-like conservative GC possible: just introduce an instructions to allocate memory, possibly free memory, and access memory at a variable offset to a pointer (you will need two registers for that). If it is undefined behaviour to perform arbitrary pointer arithmetic, the you can implement GC. However, that system is not memory safe and could still be used to access unallocated memory.
If you want to do better, you will have to tag each memory cell with GC metadata. A single bit flag to indicate whether this cell is a pointer or other value would suffice to perform an exact reachability analysis.