Garbage collection (GC) states are stored within references stored on a heap memory to track a progress of GC operations with respect to the references. GC state may be stored in a non-addressable portion of references. Based on the GC state of a particular reference, a set of GC operations are selected and performed for the reference. However, references stored on a call stack do not include any indication of GC state. Hence, loading a reference from heap to call stack involves removing the indication of GC state. Writing a reference to heap involves adding the indication of GC state. References embedded within a compiled method also do not indicate any GC state. Metadata of the compiled method indicate a GC state, which is implicated to the embedded references. GC operations are selected and performed for each embedded reference based on the GC state of the compiled method.