Add mark for GC objects

22 files changed, 92 insertions, 66 deletions

diff --git a/runtime/meson.build b/runtime/meson.build
index 5c679a54..2b90b2fe 100644
--- a/runtime/meson.build
+++ b/runtime/meson.build
@@ -4,6 +4,7 @@ static_library(
     'src/patio/exceptions.c',
     'src/alloc.c',
     'src/effects.c',
+    'src/gc.c',
     'src/ints.c',
     'src/primitives.c',
     'src/strings.c',
diff --git a/runtime/src/gc.c b/runtime/src/gc.c
new file mode 100644
index 00000000..5c485b26
--- /dev/null
+++ b/runtime/src/gc.c
@@ -0,0 +1,18 @@
+#include <stdbool.h>
+
+#include "./patio/patio.h"
+#include "./gc.h"
+
+// The mark value for each object is initialized to 0. Each mark phase
+// alternates between using 0b010 and 0b100 as the mark value. We check only for
+// the bit set to 1, meaning static values can have a mark value of 0b110 to be
+// considered always marked.
+PatioInt current_mark_value = 0b010;
+
+void alternate_mark_value() {
+    current_mark_value ^= 0b110;
+}
+
+bool is_marked(struct ShedGcObjectHeader* object) {
+    return (object->mark & current_mark_value) == current_mark_value;
+}
diff --git a/runtime/src/gc.h b/runtime/src/gc.h
index d7f5f9af..f8da17d3 100644
--- a/runtime/src/gc.h
+++ b/runtime/src/gc.h
@@ -1,8 +1,11 @@
 #ifndef SHED_GC_H
 #define SHED_GC_H
 
+#include "./patio/patio.h"
+
 struct ShedGcObjectHeader {
     struct ShedGcObjectHeader* next;
+    PatioInt mark;
 };
 
 #endif
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenCallTests]/[method:canCallFunctionWithArgs(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenCallTests]/[method:canCallFunctionWithArgs(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index 2b03e3b6..b5430193 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenCallTests]/[method:canCallFunctionWithArgs(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenCallTests]/[method:canCallFunctionWithArgs(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -24,7 +24,7 @@ Instructions:
         memory-load
         (local "callFunctionPointer__0")
         pointer=(local "closurePointer__0")
-        layout=(struct (data-ptr (struct (function-ptr))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr))))
         offset=(1 0)
     )
     (call-pointer (local "tmp__0") (local "callFunctionPointer__0") ((local "closurePointer__0") (local "callArgPositional__0__0") (local "callArgPositional__1__0") (local "callArgNamed__a__0") (local "callArgNamed__b__0")))
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenCallTests]/[method:canCallFunctionWithNoArgs(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenCallTests]/[method:canCallFunctionWithNoArgs(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index 9e0d720f..548e0a83 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenCallTests]/[method:canCallFunctionWithNoArgs(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenCallTests]/[method:canCallFunctionWithNoArgs(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -16,7 +16,7 @@ Instructions:
         memory-load
         (local "callFunctionPointer__0")
         pointer=(local "closurePointer__0")
-        layout=(struct (data-ptr (struct (function-ptr))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr))))
         offset=(1 0)
     )
     (call-pointer (local "tmp__0") (local "callFunctionPointer__0") ((local "closurePointer__0")))
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineEffectTests]/[method:canGenerateCodeForDefineEffect(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineEffectTests]/[method:canGenerateCodeForDefineEffect(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index 401ed700..814be668 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineEffectTests]/[method:canGenerateCodeForDefineEffect(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineEffectTests]/[method:canGenerateCodeForDefineEffect(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -20,7 +20,7 @@ Compilation unit elements:
             memory-load
             (local "callFunctionPointer__0")
             pointer=(local "closurePointer__1")
-            layout=(struct (data-ptr (struct (function-ptr))))
+            layout=(struct ((struct (data-ptr int)) (struct (function-ptr))))
             offset=(1 0)
         )
         (call-pointer (local "tmp__0") (local "callFunctionPointer__0") ((local "closurePointer__1") (local "local__fence")))
@@ -40,7 +40,7 @@ Compilation unit elements:
             memory-load
             (local "callFunctionPointer__0")
             pointer=(local "closurePointer__1")
-            layout=(struct (data-ptr (struct (function-ptr))))
+            layout=(struct ((struct (data-ptr int)) (struct (function-ptr))))
             offset=(1 0)
         )
         (call-pointer (local "tmp__0") (local "callFunctionPointer__0") ((local "closurePointer__1") (local "local__arg0")))
@@ -59,12 +59,12 @@ Locals:
 Instructions:
 
 (
-    (alloc-heap (local "userDefinedEffectPointer__State__0") (struct (data-ptr (struct (int int)))))
-    (alloc-heap (local "closurePointer__read__0") (struct (data-ptr (struct (function-ptr (struct ()) (struct ()))))))
+    (alloc-heap (local "userDefinedEffectPointer__State__0") (struct ((struct (data-ptr int)) (struct (int int)))))
+    (alloc-heap (local "closurePointer__read__0") (struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct ()))))))
     (
         memory-store
         pointer=(local "closurePointer__read__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct ())))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct ())))))
         offset=(1 0)
         value=(function-ptr "shed__function__read__0")
     )
@@ -72,15 +72,15 @@ Instructions:
     (
         memory-store
         pointer=(local "userDefinedEffectPointer__State__0")
-        layout=(struct (data-ptr (struct (int int))))
+        layout=(struct ((struct (data-ptr int)) (struct (int int))))
         offset=(1 0)
         value=(local "userDefinedMethod__read__0")
     )
-    (alloc-heap (local "closurePointer__write__0") (struct (data-ptr (struct (function-ptr (struct ()) (struct ()))))))
+    (alloc-heap (local "closurePointer__write__0") (struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct ()))))))
     (
         memory-store
         pointer=(local "closurePointer__write__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct ())))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct ())))))
         offset=(1 0)
         value=(function-ptr "shed__function__write__0")
     )
@@ -88,7 +88,7 @@ Instructions:
     (
         memory-store
         pointer=(local "userDefinedEffectPointer__State__0")
-        layout=(struct (data-ptr (struct (int int))))
+        layout=(struct ((struct (data-ptr int)) (struct (int int))))
         offset=(1 1)
         value=(local "userDefinedMethod__write__0")
     )
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:canCaptureFreeVariablesThatAreSetAfterDefinition(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:canCaptureFreeVariablesThatAreSetAfterDefinition(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index dce8b665..8b99cead 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:canCaptureFreeVariablesThatAreSetAfterDefinition(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:canCaptureFreeVariablesThatAreSetAfterDefinition(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -11,14 +11,14 @@ Compilation unit elements:
             memory-load
             (local "local__a")
             pointer=(local "closurePointer__0")
-            layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (int int))))))
+            layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int))))))
             offset=(1 2 0)
         )
         (
             memory-load
             (local "local__b")
             pointer=(local "closurePointer__0")
-            layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (int int))))))
+            layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int))))))
             offset=(1 2 1)
         )
         (return (local "local__a"))
@@ -34,11 +34,11 @@ Locals:
 Instructions:
 
 (
-    (alloc-heap (local "closurePointer__f__0") (struct (data-ptr (struct (function-ptr (struct ()) (struct (int int)))))))
+    (alloc-heap (local "closurePointer__f__0") (struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int)))))))
     (
         memory-store
         pointer=(local "closurePointer__f__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (int int))))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int))))))
         offset=(1 0)
         value=(function-ptr "shed__function__f__0")
     )
@@ -47,7 +47,7 @@ Instructions:
     (
         memory-store
         pointer=(local "closurePointer__f__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (int int))))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int))))))
         offset=(1 2 0)
         value=(local "local__a")
     )
@@ -55,7 +55,7 @@ Instructions:
     (
         memory-store
         pointer=(local "closurePointer__f__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (int int))))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int))))))
         offset=(1 2 1)
         value=(local "local__b")
     )
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:canDefineMinimalFunction(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:canDefineMinimalFunction(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index aa138600..c9f8a0a6 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:canDefineMinimalFunction(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:canDefineMinimalFunction(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -19,11 +19,11 @@ Locals:
 Instructions:
 
 (
-    (alloc-heap (local "closurePointer__f__0") (struct (data-ptr (struct (function-ptr (struct ()) (struct ()))))))
+    (alloc-heap (local "closurePointer__f__0") (struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct ()))))))
     (
         memory-store
         pointer=(local "closurePointer__f__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct ())))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct ())))))
         offset=(1 0)
         value=(function-ptr "shed__function__f__0")
     )
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:effectHandlerMethodSwapsEffectHandlerInBody(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:effectHandlerMethodSwapsEffectHandlerInBody(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index 57e4ffa0..a59e32bd 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:effectHandlerMethodSwapsEffectHandlerInBody(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:effectHandlerMethodSwapsEffectHandlerInBody(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -24,7 +24,7 @@ Compilation unit elements:
             memory-load
             (local "effectHandler__1")
             pointer=(local "closurePointer__0")
-            layout=(struct (data-ptr (struct (function-ptr (struct (data-ptr)) (struct ())))))
+            layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct (data-ptr)) (struct ())))))
             offset=(1 1 0)
         )
         (call _ "shed__runtime__effects_set_handler" ((local "effectHandler__1")))
@@ -42,11 +42,11 @@ Locals:
 Instructions:
 
 (
-    (alloc-heap (local "closurePointer__f__0") (struct (data-ptr (struct (function-ptr (struct (data-ptr)) (struct ()))))))
+    (alloc-heap (local "closurePointer__f__0") (struct ((struct (data-ptr int)) (struct (function-ptr (struct (data-ptr)) (struct ()))))))
     (
         memory-store
         pointer=(local "closurePointer__f__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct (data-ptr)) (struct ())))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct (data-ptr)) (struct ())))))
         offset=(1 0)
         value=(function-ptr "shed__effectHandlerMethod__f__0")
     )
@@ -54,7 +54,7 @@ Instructions:
     (
         memory-store
         pointer=(local "closurePointer__f__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct (data-ptr)) (struct ())))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct (data-ptr)) (struct ())))))
         offset=(1 1 0)
         value=(local "effectHandlerCurrent__0")
     )
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:immutableFreeVariablesAreStoredInAndLoadedFromEnvironment(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:immutableFreeVariablesAreStoredInAndLoadedFromEnvironment(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index fab935e5..9a4d1e60 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:immutableFreeVariablesAreStoredInAndLoadedFromEnvironment(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:immutableFreeVariablesAreStoredInAndLoadedFromEnvironment(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -11,14 +11,14 @@ Compilation unit elements:
             memory-load
             (local "local__a")
             pointer=(local "closurePointer__0")
-            layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (int int))))))
+            layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int))))))
             offset=(1 2 0)
         )
         (
             memory-load
             (local "local__b")
             pointer=(local "closurePointer__0")
-            layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (int int))))))
+            layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int))))))
             offset=(1 2 1)
         )
         (return (local "local__a"))
@@ -34,25 +34,25 @@ Locals:
 Instructions:
 
 (
-    (alloc-heap (local "closurePointer__f__0") (struct (data-ptr (struct (function-ptr (struct ()) (struct (int int)))))))
+    (alloc-heap (local "closurePointer__f__0") (struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int)))))))
     (
         memory-store
         pointer=(local "closurePointer__f__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (int int))))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int))))))
         offset=(1 0)
         value=(function-ptr "shed__function__f__0")
     )
     (
         memory-store
         pointer=(local "closurePointer__f__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (int int))))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int))))))
         offset=(1 2 0)
         value=(local "local__a")
     )
     (
         memory-store
         pointer=(local "closurePointer__f__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (int int))))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int))))))
         offset=(1 2 1)
         value=(local "local__b")
     )
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:pointersToFreeMutableVariablesAreStoredInAndLoadedFromEnvironment(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:pointersToFreeMutableVariablesAreStoredInAndLoadedFromEnvironment(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index c9c6eaa9..29af5f7c 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:pointersToFreeMutableVariablesAreStoredInAndLoadedFromEnvironment(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:pointersToFreeMutableVariablesAreStoredInAndLoadedFromEnvironment(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -11,14 +11,14 @@ Compilation unit elements:
             memory-load
             (local "local__a")
             pointer=(local "closurePointer__0")
-            layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (data-ptr data-ptr))))))
+            layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (data-ptr data-ptr))))))
             offset=(1 2 0)
         )
         (
             memory-load
             (local "local__b")
             pointer=(local "closurePointer__0")
-            layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (data-ptr data-ptr))))))
+            layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (data-ptr data-ptr))))))
             offset=(1 2 1)
         )
         (return (local "local__a"))
@@ -34,25 +34,25 @@ Locals:
 Instructions:
 
 (
-    (alloc-heap (local "closurePointer__f__0") (struct (data-ptr (struct (function-ptr (struct ()) (struct (data-ptr data-ptr)))))))
+    (alloc-heap (local "closurePointer__f__0") (struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (data-ptr data-ptr)))))))
     (
         memory-store
         pointer=(local "closurePointer__f__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (data-ptr data-ptr))))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (data-ptr data-ptr))))))
         offset=(1 0)
         value=(function-ptr "shed__function__f__0")
     )
     (
         memory-store
         pointer=(local "closurePointer__f__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (data-ptr data-ptr))))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (data-ptr data-ptr))))))
         offset=(1 2 0)
         value=(local "local__a")
     )
     (
         memory-store
         pointer=(local "closurePointer__f__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (data-ptr data-ptr))))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (data-ptr data-ptr))))))
         offset=(1 2 1)
         value=(local "local__b")
     )
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:positionalAndNamedParamsAreDefined(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:positionalAndNamedParamsAreDefined(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index c702a0d1..ad7919da 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:positionalAndNamedParamsAreDefined(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineFunctionTests]/[method:positionalAndNamedParamsAreDefined(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -17,14 +17,14 @@ Compilation unit elements:
             memory-load
             (local "local__a")
             pointer=(local "closurePointer__0")
-            layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (int int))))))
+            layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int))))))
             offset=(1 2 0)
         )
         (
             memory-load
             (local "local__b")
             pointer=(local "closurePointer__0")
-            layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (int int))))))
+            layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int))))))
             offset=(1 2 1)
         )
         (call (local "binaryOpResult__0") "shed__runtime__int_add" ((local "local__a") (local "local__param1")))
@@ -42,25 +42,25 @@ Locals:
 Instructions:
 
 (
-    (alloc-heap (local "closurePointer__f__0") (struct (data-ptr (struct (function-ptr (struct ()) (struct (int int)))))))
+    (alloc-heap (local "closurePointer__f__0") (struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int)))))))
     (
         memory-store
         pointer=(local "closurePointer__f__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (int int))))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int))))))
         offset=(1 0)
         value=(function-ptr "shed__function__f__0")
     )
     (
         memory-store
         pointer=(local "closurePointer__f__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (int int))))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int))))))
         offset=(1 2 0)
         value=(local "local__a")
     )
     (
         memory-store
         pointer=(local "closurePointer__f__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct (int int))))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct (int int))))))
         offset=(1 2 1)
         value=(local "local__b")
     )
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineStructTests]/[method:canGenerateCodeForDefineStruct(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineStructTests]/[method:canGenerateCodeForDefineStruct(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index d05ee160..2ccf0329 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineStructTests]/[method:canGenerateCodeForDefineStruct(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenDefineStructTests]/[method:canGenerateCodeForDefineStruct(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -7,25 +7,25 @@ Compilation unit elements:
     locals=((param "closurePointer__0" data-ptr) (param "local__isActive" int) (param "local__name" int) (val "structValuePointer__0" data-ptr) (val "structValue__0" int))
     return-type=int
     body=(
-        (alloc-heap (local "structValuePointer__0") (struct (data-ptr (struct (int (struct (int int)))))))
+        (alloc-heap (local "structValuePointer__0") (struct ((struct (data-ptr int)) (struct (int (struct (int int)))))))
         (
             memory-store
             pointer=(local "structValuePointer__0")
-            layout=(struct (data-ptr (struct (int (struct (int int))))))
+            layout=(struct ((struct (data-ptr int)) (struct (int (struct (int int))))))
             offset=(1 0)
             value=(int 0)
         )
         (
             memory-store
             pointer=(local "structValuePointer__0")
-            layout=(struct (data-ptr (struct (int (struct (int int))))))
+            layout=(struct ((struct (data-ptr int)) (struct (int (struct (int int))))))
             offset=(1 1 0)
             value=(local "local__name")
         )
         (
             memory-store
             pointer=(local "structValuePointer__0")
-            layout=(struct (data-ptr (struct (int (struct (int int))))))
+            layout=(struct ((struct (data-ptr int)) (struct (int (struct (int int))))))
             offset=(1 1 1)
             value=(local "local__isActive")
         )
@@ -41,11 +41,11 @@ Locals:
 Instructions:
 
 (
-    (alloc-heap (local "closurePointer__User__0") (struct (data-ptr (struct (function-ptr (struct ()) (struct ()))))))
+    (alloc-heap (local "closurePointer__User__0") (struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct ()))))))
     (
         memory-store
         pointer=(local "closurePointer__User__0")
-        layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct ())))))
+        layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct ())))))
         offset=(1 0)
         value=(function-ptr "shed__function__User__0")
     )
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenFieldLoadTests]/[method:canGenerateCodeForStructFieldLoad(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenFieldLoadTests]/[method:canGenerateCodeForStructFieldLoad(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index 8459b4c5..8ed8ffbd 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenFieldLoadTests]/[method:canGenerateCodeForStructFieldLoad(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenFieldLoadTests]/[method:canGenerateCodeForStructFieldLoad(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -13,7 +13,7 @@ Instructions:
         memory-load
         (local "tmp__id__0")
         pointer=(local "structValuePointer__0")
-        layout=(struct (data-ptr (struct (int (struct (int int int))))))
+        layout=(struct ((struct (data-ptr int)) (struct (int (struct (int int int))))))
         offset=(1 1 1)
     )
 )
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenFieldLoadTests]/[method:canGenerateCodeForUserDefinedEffectFieldLoad(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenFieldLoadTests]/[method:canGenerateCodeForUserDefinedEffectFieldLoad(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index cbdc2fba..069a083d 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenFieldLoadTests]/[method:canGenerateCodeForUserDefinedEffectFieldLoad(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenFieldLoadTests]/[method:canGenerateCodeForUserDefinedEffectFieldLoad(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -13,7 +13,7 @@ Instructions:
         memory-load
         (local "tmp__fence__0")
         pointer=(local "userDefinedEffectPointer__0")
-        layout=(struct (data-ptr (struct (int int int))))
+        layout=(struct ((struct (data-ptr int)) (struct (int int int))))
         offset=(1 1)
     )
 )
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenNamespaceTests]/[method:canDefineNamespace(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenNamespaceTests]/[method:canDefineNamespace(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index b31937c4..abbc0b67 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenNamespaceTests]/[method:canDefineNamespace(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenNamespaceTests]/[method:canDefineNamespace(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -19,11 +19,11 @@
         locals=((val "closure__f__0" int) (val "closurePointer__f__0" data-ptr))
         return-type=void
         body=(
-            (alloc-heap (local "closurePointer__f__0") (struct (data-ptr (struct (function-ptr (struct ()) (struct ()))))))
+            (alloc-heap (local "closurePointer__f__0") (struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct ()))))))
             (
                 memory-store
                 pointer=(local "closurePointer__f__0")
-                layout=(struct (data-ptr (struct (function-ptr (struct ()) (struct ())))))
+                layout=(struct ((struct (data-ptr int)) (struct (function-ptr (struct ()) (struct ())))))
                 offset=(1 0)
                 value=(function-ptr "shed__function__f__0")
             )
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenPushStringTests]/[method:canHaveMultipleStrings(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenPushStringTests]/[method:canHaveMultipleStrings(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index d8ea95b2..88f6b7f1 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenPushStringTests]/[method:canHaveMultipleStrings(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenPushStringTests]/[method:canHaveMultipleStrings(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -1,7 +1,7 @@
 Compilation unit elements:
 
-(data-immutable "shed__string__0" (struct ((int 0) (struct ((int 5) (array byte ((byte 0x68) (byte 0x65) (byte 0x6c) (byte 0x6c) (byte 0x6f))))))))
-(data-immutable "shed__string__1" (struct ((int 0) (struct ((int 5) (array byte ((byte 0x77) (byte 0x6f) (byte 0x72) (byte 0x6c) (byte 0x64))))))))
+(data-immutable "shed__string__0" (struct ((struct ((int 0) (int 6))) (struct ((int 5) (array byte ((byte 0x68) (byte 0x65) (byte 0x6c) (byte 0x6c) (byte 0x6f))))))))
+(data-immutable "shed__string__1" (struct ((struct ((int 0) (int 6))) (struct ((int 5) (array byte ((byte 0x77) (byte 0x6f) (byte 0x72) (byte 0x6c) (byte 0x64))))))))
 
 Locals:
  * (val "string__0" int)
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenPushStringTests]/[method:pushStringIsCompiledToDataAndIndexToData(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenPushStringTests]/[method:pushStringIsCompiledToDataAndIndexToData(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index 04540bea..86fe840f 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenPushStringTests]/[method:pushStringIsCompiledToDataAndIndexToData(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenPushStringTests]/[method:pushStringIsCompiledToDataAndIndexToData(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -1,6 +1,6 @@
 Compilation unit elements:
 
-(data-immutable "shed__string__0" (struct ((int 0) (struct ((int 5) (array byte ((byte 0x68) (byte 0x65) (byte 0x6c) (byte 0x6c) (byte 0x6f))))))))
+(data-immutable "shed__string__0" (struct ((struct ((int 0) (int 6))) (struct ((int 5) (array byte ((byte 0x68) (byte 0x65) (byte 0x6c) (byte 0x6c) (byte 0x6f))))))))
 
 Locals:
  * (val "string__0" int)
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenSwitchTests]/[method:canGenerateCodeForSwitchWithSingleResult(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenSwitchTests]/[method:canGenerateCodeForSwitchWithSingleResult(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index ced7cded..63a389bc 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenSwitchTests]/[method:canGenerateCodeForSwitchWithSingleResult(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenSwitchTests]/[method:canGenerateCodeForSwitchWithSingleResult(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -32,7 +32,7 @@ Instructions:
         memory-load
         (local "switchTag__0")
         pointer=(local "structValuePointer__0")
-        layout=(struct (data-ptr (struct (int))))
+        layout=(struct ((struct (data-ptr int)) (struct (int))))
         offset=(1 0)
     )
     (
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenTupleCreateTests]/[method:canGenerateCodeForTupleCreate(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenTupleCreateTests]/[method:canGenerateCodeForTupleCreate(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index 2ae12c42..33df6608 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenTupleCreateTests]/[method:canGenerateCodeForTupleCreate(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenTupleCreateTests]/[method:canGenerateCodeForTupleCreate(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -14,25 +14,25 @@ Instructions:
     (local-store (local "tupleElement__2__0") (local "d"))
     (local-store (local "tupleElement__1__0") (local "c"))
     (local-store (local "tupleElement__0__0") (local "b"))
-    (alloc-heap (local "tuplePointer__0") (struct (data-ptr (struct (int int int)))))
+    (alloc-heap (local "tuplePointer__0") (struct ((struct (data-ptr int)) (struct (int int int)))))
     (
         memory-store
         pointer=(local "tuplePointer__0")
-        layout=(struct (data-ptr (struct (int int int))))
+        layout=(struct ((struct (data-ptr int)) (struct (int int int))))
         offset=(1 0)
         value=(local "tupleElement__0__0")
     )
     (
         memory-store
         pointer=(local "tuplePointer__0")
-        layout=(struct (data-ptr (struct (int int int))))
+        layout=(struct ((struct (data-ptr int)) (struct (int int int))))
         offset=(1 1)
         value=(local "tupleElement__1__0")
     )
     (
         memory-store
         pointer=(local "tuplePointer__0")
-        layout=(struct (data-ptr (struct (int int int))))
+        layout=(struct ((struct (data-ptr int)) (struct (int int int))))
         offset=(1 2)
         value=(local "tupleElement__2__0")
     )
diff --git a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenTupleGetTests]/[method:canGenerateCodeForTupleGet(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenTupleGetTests]/[method:canGenerateCodeForTupleGet(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
index 920fbfa8..4889ebf9 100644
--- a/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenTupleGetTests]/[method:canGenerateCodeForTupleGet(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
+++ b/snapshots/[engine:junit-jupiter]/[class:org.shedlang.compiler.patio.PatioCodeGenTupleGetTests]/[method:canGenerateCodeForTupleGet(org.shedlang.compiler.testing.snapshots.Snapshotter)].expected
@@ -13,7 +13,7 @@ Instructions:
         memory-load
         (local "tupleElement__2__0")
         pointer=(local "tuple__0")
-        layout=(struct (data-ptr (struct (int int int))))
+        layout=(struct ((struct (data-ptr int)) (struct (int int int))))
         offset=(1 2)
     )
 )
diff --git a/src/main/java/org/shedlang/compiler/patio/PatioCodeGenGc.java b/src/main/java/org/shedlang/compiler/patio/PatioCodeGenGc.java
index 4178510f..78f19a19 100644
--- a/src/main/java/org/shedlang/compiler/patio/PatioCodeGenGc.java
+++ b/src/main/java/org/shedlang/compiler/patio/PatioCodeGenGc.java
@@ -1,9 +1,6 @@
 package org.shedlang.compiler.patio;
 
-import org.shedlang.compiler.patio.ast.types.PatioDataLayout;
-import org.shedlang.compiler.patio.ast.types.PatioDataLayouts;
-import org.shedlang.compiler.patio.ast.types.PatioDataValue;
-import org.shedlang.compiler.patio.ast.types.PatioDataValues;
+import org.shedlang.compiler.patio.ast.types.*;
 import org.shedlang.compiler.util.Lists;
 
 import java.util.List;
@@ -14,7 +11,10 @@ public class PatioCodeGenGc {
 
     public static PatioDataLayout gcObjectDataLayout(PatioDataLayout valueLayout) {
         return PatioDataLayouts.struct(List.of(
-            PatioDataLayouts.DATA_POINTER,
+            PatioDataLayouts.struct(List.of(
+                PatioDataLayouts.DATA_POINTER, // next
+                PatioDataLayouts.INT // mark
+            )),
             valueLayout
         ));
     }
@@ -29,7 +29,11 @@ public class PatioCodeGenGc {
      */
     public static PatioDataValue gcObjectStaticDataValue(PatioDataValue value) {
         return PatioDataValues.struct(List.of(
-            PatioDataValues.int_(0),
+            PatioDataValues.struct(List.of(
+                PatioDataValues.int_(0),
+                // Static values are always marked: see gc.c
+                PatioDataValues.int_(0b110)
+            )),
             value
         ));
     }