Revert "Revert "This commit implements the Object Shapes technique in CRuby.""

This reverts commit 9a6803c90b817f70389cae10d60b50ad752da48f.

1 files changed, 336 insertions, 403 deletions

diff --git a/variable.c b/variable.c
index 056a1000b8..b5e95b7f1c 100644
--- a/variable.c
+++ b/variable.c
@@ -34,6 +34,7 @@
 #include "ruby/st.h"
 #include "ruby/util.h"
 #include "transient_heap.h"
+#include "shape.h"
 #include "variable.h"
 #include "vm_core.h"
 #include "ractor_core.h"
@@ -63,12 +64,9 @@ static VALUE rb_const_search(VALUE klass, ID id, int exclude, int recurse, int v
 static st_table *generic_iv_tbl_;
 
 struct ivar_update {
-    union {
-        st_table *iv_index_tbl;
-        struct gen_ivtbl *ivtbl;
-    } u;
-    st_data_t index;
-    int iv_extended;
+    struct gen_ivtbl *ivtbl;
+    uint32_t iv_index;
+    rb_shape_t* shape;
 };
 
 void
@@ -896,30 +894,6 @@ rb_alias_variable(ID name1, ID name2)
     entry1->var = entry2->var;
 }
 
-static bool
-iv_index_tbl_lookup(struct st_table *tbl, ID id, uint32_t *indexp)
-{
-    st_data_t ent_data;
-    int r;
-
-    if (tbl == NULL) return false;
-
-    RB_VM_LOCK_ENTER();
-    {
-        r = st_lookup(tbl, (st_data_t)id, &ent_data);
-    }
-    RB_VM_LOCK_LEAVE();
-
-    if (r) {
-        struct rb_iv_index_tbl_entry *ent = (void *)ent_data;
-        *indexp = ent->index;
-        return true;
-    }
-    else {
-        return false;
-    }
-}
-
 static void
 IVAR_ACCESSOR_SHOULD_BE_MAIN_RACTOR(ID id)
 {
@@ -957,7 +931,20 @@ generic_ivtbl_no_ractor_check(VALUE obj)
 }
 
 static int
-gen_ivtbl_get(VALUE obj, ID id, struct gen_ivtbl **ivtbl)
+gen_ivtbl_get_unlocked(VALUE obj, ID id, struct gen_ivtbl **ivtbl)
+{
+    st_data_t data;
+
+    if (st_lookup(generic_ivtbl(obj, id, false), (st_data_t)obj, &data)) {
+        *ivtbl = (struct gen_ivtbl *)data;
+        return 1;
+    }
+
+    return 0;
+}
+
+MJIT_FUNC_EXPORTED int
+rb_gen_ivtbl_get(VALUE obj, ID id, struct gen_ivtbl **ivtbl)
 {
     st_data_t data;
     int r = 0;
@@ -977,63 +964,7 @@ gen_ivtbl_get(VALUE obj, ID id, struct gen_ivtbl **ivtbl)
 MJIT_FUNC_EXPORTED int
 rb_ivar_generic_ivtbl_lookup(VALUE obj, struct gen_ivtbl **ivtbl)
 {
-    return gen_ivtbl_get(obj, 0, ivtbl);
-}
-
-MJIT_FUNC_EXPORTED VALUE
-rb_ivar_generic_lookup_with_index(VALUE obj, ID id, uint32_t index)
-{
-    struct gen_ivtbl *ivtbl;
-
-    if (gen_ivtbl_get(obj, id, &ivtbl)) {
-        if (LIKELY(index < ivtbl->numiv)) {
-            VALUE val = ivtbl->ivptr[index];
-            return val;
-        }
-    }
-
-    return Qundef;
-}
-
-static VALUE
-generic_ivar_delete(VALUE obj, ID id, VALUE undef)
-{
-    struct gen_ivtbl *ivtbl;
-
-    if (gen_ivtbl_get(obj, id, &ivtbl)) {
-        st_table *iv_index_tbl = RCLASS_IV_INDEX_TBL(rb_obj_class(obj));
-        uint32_t index;
-
-        if (iv_index_tbl && iv_index_tbl_lookup(iv_index_tbl, id, &index)) {
-            if (index < ivtbl->numiv) {
-                VALUE ret = ivtbl->ivptr[index];
-
-                ivtbl->ivptr[index] = Qundef;
-                return ret == Qundef ? undef : ret;
-            }
-        }
-    }
-    return undef;
-}
-
-static VALUE
-generic_ivar_get(VALUE obj, ID id, VALUE undef)
-{
-    struct gen_ivtbl *ivtbl;
-
-    if (gen_ivtbl_get(obj, id, &ivtbl)) {
-        st_table *iv_index_tbl = RCLASS_IV_INDEX_TBL(rb_obj_class(obj));
-        uint32_t index;
-
-        if (iv_index_tbl && iv_index_tbl_lookup(iv_index_tbl, id, &index)) {
-            if (index < ivtbl->numiv) {
-                VALUE ret = ivtbl->ivptr[index];
-
-                return ret == Qundef ? undef : ret;
-            }
-        }
-    }
-    return undef;
+    return rb_gen_ivtbl_get(obj, 0, ivtbl);
 }
 
 static size_t
@@ -1045,6 +976,8 @@ gen_ivtbl_bytes(size_t n)
 static struct gen_ivtbl *
 gen_ivtbl_resize(struct gen_ivtbl *old, uint32_t n)
 {
+    RUBY_ASSERT(n > 0);
+
     uint32_t len = old ? old->numiv : 0;
     struct gen_ivtbl *ivtbl = xrealloc(old, gen_ivtbl_bytes(n));
 
@@ -1069,18 +1002,6 @@ gen_ivtbl_dup(const struct gen_ivtbl *orig)
 }
 #endif
 
-static uint32_t
-iv_index_tbl_newsize(struct ivar_update *ivup)
-{
-    if (!ivup->iv_extended) {
-        return (uint32_t)ivup->u.iv_index_tbl->num_entries;
-    }
-    else {
-        uint32_t index = (uint32_t)ivup->index;	/* should not overflow */
-        return (index+1) + (index+1)/4; /* (index+1)*1.25 */
-    }
-}
-
 static int
 generic_ivar_update(st_data_t *k, st_data_t *v, st_data_t u, int existing)
 {
@@ -1091,53 +1012,22 @@ generic_ivar_update(st_data_t *k, st_data_t *v, st_data_t u, int existing)
 
     if (existing) {
         ivtbl = (struct gen_ivtbl *)*v;
-        if (ivup->index < ivtbl->numiv) {
-            ivup->u.ivtbl = ivtbl;
+        if (ivup->iv_index < ivtbl->numiv) {
+            ivup->ivtbl = ivtbl;
             return ST_STOP;
         }
     }
     FL_SET((VALUE)*k, FL_EXIVAR);
-    uint32_t newsize = iv_index_tbl_newsize(ivup);
-    ivtbl = gen_ivtbl_resize(ivtbl, newsize);
+    ivtbl = gen_ivtbl_resize(ivtbl, ivup->shape->iv_count);
+    // Reinsert in to the hash table because ivtbl might be a newly resized chunk of memory
     *v = (st_data_t)ivtbl;
-    ivup->u.ivtbl = ivtbl;
+    ivup->ivtbl = ivtbl;
+#if !SHAPE_IN_BASIC_FLAGS
+    ivtbl->shape_id = rb_shape_id(ivup->shape);
+#endif
     return ST_CONTINUE;
 }
 
-static VALUE
-generic_ivar_defined(VALUE obj, ID id)
-{
-    struct gen_ivtbl *ivtbl;
-    st_table *iv_index_tbl = RCLASS_IV_INDEX_TBL(rb_obj_class(obj));
-    uint32_t index;
-
-    if (!iv_index_tbl_lookup(iv_index_tbl, id, &index)) return Qfalse;
-    if (!gen_ivtbl_get(obj, id, &ivtbl)) return Qfalse;
-
-    return RBOOL((index < ivtbl->numiv) && (ivtbl->ivptr[index] != Qundef));
-}
-
-static int
-generic_ivar_remove(VALUE obj, ID id, VALUE *valp)
-{
-    struct gen_ivtbl *ivtbl;
-    uint32_t index;
-    st_table *iv_index_tbl = RCLASS_IV_INDEX_TBL(rb_obj_class(obj));
-
-    if (!iv_index_tbl) return 0;
-    if (!iv_index_tbl_lookup(iv_index_tbl, id, &index)) return 0;
-    if (!gen_ivtbl_get(obj, id, &ivtbl)) return 0;
-
-    if (index < ivtbl->numiv) {
-        if (ivtbl->ivptr[index] != Qundef) {
-            *valp = ivtbl->ivptr[index];
-            ivtbl->ivptr[index] = Qundef;
-            return 1;
-        }
-    }
-    return 0;
-}
-
 static void
 gen_ivtbl_mark(const struct gen_ivtbl *ivtbl)
 {
@@ -1153,7 +1043,7 @@ rb_mark_generic_ivar(VALUE obj)
 {
     struct gen_ivtbl *ivtbl;
 
-    if (gen_ivtbl_get(obj, 0, &ivtbl)) {
+    if (rb_gen_ivtbl_get(obj, 0, &ivtbl)) {
         gen_ivtbl_mark(ivtbl);
     }
 }
@@ -1182,11 +1072,35 @@ rb_generic_ivar_memsize(VALUE obj)
 {
     struct gen_ivtbl *ivtbl;
 
-    if (gen_ivtbl_get(obj, 0, &ivtbl))
+    if (rb_gen_ivtbl_get(obj, 0, &ivtbl))
         return gen_ivtbl_bytes(ivtbl->numiv);
     return 0;
 }
 
+#if !SHAPE_IN_BASIC_FLAGS
+MJIT_FUNC_EXPORTED shape_id_t
+rb_generic_shape_id(VALUE obj)
+{
+    struct gen_ivtbl *ivtbl = 0;
+    shape_id_t shape_id = 0;
+
+    RB_VM_LOCK_ENTER();
+    {
+        st_table* global_iv_table = generic_ivtbl(obj, 0, false);
+
+        if (global_iv_table && st_lookup(global_iv_table, obj, (st_data_t *)&ivtbl)) {
+            shape_id = ivtbl->shape_id;
+        }
+        else if (OBJ_FROZEN(obj)) {
+            shape_id = FROZEN_ROOT_SHAPE_ID;
+        }
+    }
+    RB_VM_LOCK_LEAVE();
+
+    return shape_id;
+}
+#endif
+
 static size_t
 gen_ivtbl_count(const struct gen_ivtbl *ivtbl)
 {
@@ -1254,23 +1168,16 @@ VALUE
 rb_ivar_lookup(VALUE obj, ID id, VALUE undef)
 {
     if (SPECIAL_CONST_P(obj)) return undef;
+
+    shape_id_t shape_id;
+    VALUE * ivar_list;
+    rb_shape_t * shape;
+
+#if SHAPE_IN_BASIC_FLAGS
+    shape_id = RBASIC_SHAPE_ID(obj);
+#endif
+
     switch (BUILTIN_TYPE(obj)) {
-      case T_OBJECT:
-        {
-            uint32_t index;
-            uint32_t len = ROBJECT_NUMIV(obj);
-            VALUE *ptr = ROBJECT_IVPTR(obj);
-            VALUE val;
-
-            if (iv_index_tbl_lookup(ROBJECT_IV_INDEX_TBL(obj), id, &index) &&
-                index < len &&
-                (val = ptr[index]) != Qundef) {
-                return val;
-            }
-            else {
-                break;
-            }
-        }
       case T_CLASS:
       case T_MODULE:
         {
@@ -1287,14 +1194,37 @@ rb_ivar_lookup(VALUE obj, ID id, VALUE undef)
                 return val;
             }
             else {
-                break;
+                return undef;
             }
         }
+      case T_OBJECT:
+        {
+#if !SHAPE_IN_BASIC_FLAGS
+            shape_id = ROBJECT_SHAPE_ID(obj);
+#endif
+            ivar_list = ROBJECT_IVPTR(obj);
+            break;
+        }
       default:
-        if (FL_TEST(obj, FL_EXIVAR))
-            return generic_ivar_get(obj, id, undef);
+        if (FL_TEST_RAW(obj, FL_EXIVAR)) {
+            struct gen_ivtbl *ivtbl;
+            rb_gen_ivtbl_get(obj, id, &ivtbl);
+#if !SHAPE_IN_BASIC_FLAGS
+            shape_id = ivtbl->shape_id;
+#endif
+            ivar_list = ivtbl->ivptr;
+        } else {
+            return undef;
+        }
         break;
     }
+
+    attr_index_t index = 0;
+    shape = rb_shape_get_shape_by_id(shape_id);
+    if (rb_shape_get_iv_index(shape, id, &index)) {
+        return ivar_list[index];
+    }
+
     return undef;
 }
 
@@ -1315,26 +1245,12 @@ rb_attr_get(VALUE obj, ID id)
 static VALUE
 rb_ivar_delete(VALUE obj, ID id, VALUE undef)
 {
-    VALUE *ptr;
-    struct st_table *iv_index_tbl;
-    uint32_t len, index;
-
     rb_check_frozen(obj);
-    switch (BUILTIN_TYPE(obj)) {
-      case T_OBJECT:
-        len = ROBJECT_NUMIV(obj);
-        ptr = ROBJECT_IVPTR(obj);
-        iv_index_tbl = ROBJECT_IV_INDEX_TBL(obj);
-        if (iv_index_tbl_lookup(iv_index_tbl, id, &index) &&
-            index < len) {
-            VALUE val = ptr[index];
-            ptr[index] = Qundef;
 
-            if (val != Qundef) {
-                return val;
-            }
-        }
-        break;
+    VALUE val = Qnil;
+    attr_index_t index;
+
+    switch (BUILTIN_TYPE(obj)) {
       case T_CLASS:
       case T_MODULE:
         IVAR_ACCESSOR_SHOULD_BE_MAIN_RACTOR(id);
@@ -1345,11 +1261,33 @@ rb_ivar_delete(VALUE obj, ID id, VALUE undef)
             }
         }
         break;
-      default:
-        if (FL_TEST(obj, FL_EXIVAR))
-            return generic_ivar_delete(obj, id, undef);
+      case T_OBJECT: {
+        rb_shape_t * shape = rb_shape_get_shape(obj);
+        if (rb_shape_get_iv_index(shape, id, &index)) {
+            rb_shape_transition_shape_remove_ivar(obj, id, shape);
+            val = ROBJECT_IVPTR(obj)[index];
+            ROBJECT_IVPTR(obj)[index] = Qundef;
+            return val;
+        }
+
         break;
+      }
+      default: {
+        rb_shape_t * shape = rb_shape_get_shape(obj);
+
+        if (rb_shape_get_iv_index(shape, id, &index)) {
+            rb_shape_transition_shape_remove_ivar(obj, id, shape);
+            struct gen_ivtbl *ivtbl;
+            rb_gen_ivtbl_get(obj, id, &ivtbl);
+            val = ivtbl->ivptr[index];
+            ivtbl->ivptr[index] = Qundef;
+            return val;
+        }
+
+        break;
+      }
     }
+
     return undef;
 }
 
@@ -1359,67 +1297,31 @@ rb_attr_delete(VALUE obj, ID id)
     return rb_ivar_delete(obj, id, Qnil);
 }
 
-static st_table *
-iv_index_tbl_make(VALUE obj, VALUE klass)
-{
-    st_table *iv_index_tbl;
-
-    if (UNLIKELY(!klass)) {
-        rb_raise(rb_eTypeError, "hidden object cannot have instance variables");
-    }
-
-    if ((iv_index_tbl = RCLASS_IV_INDEX_TBL(klass)) == NULL) {
-        RB_VM_LOCK_ENTER();
-        if ((iv_index_tbl = RCLASS_IV_INDEX_TBL(klass)) == NULL) {
-            iv_index_tbl = RCLASS_IV_INDEX_TBL(klass) = st_init_numtable();
-        }
-        RB_VM_LOCK_LEAVE();
-    }
-
-    return iv_index_tbl;
-}
-
-static void
-iv_index_tbl_extend(struct ivar_update *ivup, ID id, VALUE klass)
-{
-    ASSERT_vm_locking();
-    st_data_t ent_data;
-    struct rb_iv_index_tbl_entry *ent;
-
-    if (st_lookup(ivup->u.iv_index_tbl, (st_data_t)id, &ent_data)) {
-        ent = (void *)ent_data;
-        ivup->index = ent->index;
-        return;
-    }
-    if (ivup->u.iv_index_tbl->num_entries >= INT_MAX) {
-        rb_raise(rb_eArgError, "too many instance variables");
-    }
-    ent = ALLOC(struct rb_iv_index_tbl_entry);
-    ent->index = ivup->index = (uint32_t)ivup->u.iv_index_tbl->num_entries;
-    ent->class_value = klass;
-    ent->class_serial = RCLASS_SERIAL(klass);
-    st_add_direct(ivup->u.iv_index_tbl, (st_data_t)id, (st_data_t)ent);
-    ivup->iv_extended = 1;
-}
-
 static void
 generic_ivar_set(VALUE obj, ID id, VALUE val)
 {
-    VALUE klass = rb_obj_class(obj);
     struct ivar_update ivup;
-    ivup.iv_extended = 0;
-    ivup.u.iv_index_tbl = iv_index_tbl_make(obj, klass);
+    // The returned shape will have `id` in its iv_table
+    rb_shape_t * shape = rb_shape_get_next(rb_shape_get_shape(obj), obj, id);
+    ivup.shape = shape;
 
     RB_VM_LOCK_ENTER();
     {
-        iv_index_tbl_extend(&ivup, id, klass);
-        st_update(generic_ivtbl(obj, id, false), (st_data_t)obj, generic_ivar_update,
-                  (st_data_t)&ivup);
+        attr_index_t ent_data;
+        if (rb_shape_get_iv_index(shape, id, &ent_data)) {
+            ivup.iv_index = (uint32_t) ent_data;
+        }
+        else {
+            rb_bug("unreachable.  Shape was not found for id: %s", rb_id2name(id));
+        }
+
+        st_update(generic_ivtbl(obj, id, false), (st_data_t)obj, generic_ivar_update, (st_data_t)&ivup);
     }
     RB_VM_LOCK_LEAVE();
 
-    ivup.u.ivtbl->ivptr[ivup.index] = val;
+    ivup.ivtbl->ivptr[ivup.iv_index] = val;
 
+    rb_shape_set_shape(obj, shape);
     RB_OBJ_WRITTEN(obj, Qundef, val);
 }
 
@@ -1486,8 +1388,8 @@ rb_obj_transient_heap_evacuate(VALUE obj, int promote)
 }
 #endif
 
-static void
-init_iv_list(VALUE obj, uint32_t len, uint32_t newsize, st_table *index_tbl)
+void
+rb_ensure_iv_list_size(VALUE obj, uint32_t len, uint32_t newsize)
 {
     VALUE *ptr = ROBJECT_IVPTR(obj);
     VALUE *newptr;
@@ -1510,35 +1412,34 @@ init_iv_list(VALUE obj, uint32_t len, uint32_t newsize, st_table *index_tbl)
 #else
     ROBJECT(obj)->as.heap.numiv = newsize;
 #endif
-    ROBJECT(obj)->as.heap.iv_index_tbl = index_tbl;
-}
-
-void
-rb_init_iv_list(VALUE obj)
-{
-    st_table *index_tbl = ROBJECT_IV_INDEX_TBL(obj);
-    uint32_t newsize = (uint32_t)index_tbl->num_entries;
-    uint32_t len = ROBJECT_NUMIV(obj);
-    init_iv_list(obj, len, newsize, index_tbl);
 }
 
-// Retrieve or create the id-to-index mapping for a given object and an
-// instance variable name.
-static struct ivar_update
-obj_ensure_iv_index_mapping(VALUE obj, ID id)
+struct gen_ivtbl *
+rb_ensure_generic_iv_list_size(VALUE obj, uint32_t newsize)
 {
-    VALUE klass = rb_obj_class(obj);
-    struct ivar_update ivup;
-    ivup.iv_extended = 0;
-    ivup.u.iv_index_tbl = iv_index_tbl_make(obj, klass);
+    struct gen_ivtbl * ivtbl = 0;
 
     RB_VM_LOCK_ENTER();
     {
-        iv_index_tbl_extend(&ivup, id, klass);
+        if (UNLIKELY(!gen_ivtbl_get_unlocked(obj, 0, &ivtbl) || newsize > ivtbl->numiv)) {
+            ivtbl = gen_ivtbl_resize(ivtbl, newsize);
+            st_insert(generic_ivtbl_no_ractor_check(obj), (st_data_t)obj, (st_data_t)ivtbl);
+            FL_SET_RAW(obj, FL_EXIVAR);
+        }
     }
     RB_VM_LOCK_LEAVE();
 
-    return ivup;
+    RUBY_ASSERT(ivtbl);
+
+    return ivtbl;
+}
+
+void
+rb_init_iv_list(VALUE obj)
+{
+    uint32_t newsize = rb_shape_get_shape(obj)->iv_count * 2.0;
+    uint32_t len = ROBJECT_NUMIV(obj);
+    rb_ensure_iv_list_size(obj, len, newsize < len ? len : newsize);
 }
 
 // Return the instance variable index for a given name and T_OBJECT object. The
@@ -1552,26 +1453,108 @@ uint32_t
 rb_obj_ensure_iv_index_mapping(VALUE obj, ID id)
 {
     RUBY_ASSERT(RB_TYPE_P(obj, T_OBJECT));
-    // This uint32_t cast shouldn't lose information as it's checked in
-    // iv_index_tbl_extend(). The index is stored as an uint32_t in
-    // struct rb_iv_index_tbl_entry.
-    return (uint32_t)obj_ensure_iv_index_mapping(obj, id).index;
+    attr_index_t index;
+
+    // Ensure there is a transition for IVAR +id+
+    rb_shape_transition_shape(obj, id, rb_shape_get_shape_by_id(ROBJECT_SHAPE_ID(obj)));
+
+    // Get the current shape
+    rb_shape_t * shape = rb_shape_get_shape_by_id(ROBJECT_SHAPE_ID(obj));
+
+    if (!rb_shape_get_iv_index(shape, id, &index)) {
+        rb_bug("unreachable.  Shape was not found for id: %s", rb_id2name(id));
+    }
+
+    uint32_t len = ROBJECT_NUMIV(obj);
+    if (len <= index) {
+        uint32_t newsize = (shape->iv_count + 1) * 1.25;
+        rb_ensure_iv_list_size(obj, len, newsize);
+    }
+    RUBY_ASSERT(index <= ROBJECT_NUMIV(obj));
+    return index;
 }
 
 static VALUE
 obj_ivar_set(VALUE obj, ID id, VALUE val)
 {
-    uint32_t len;
-    struct ivar_update ivup = obj_ensure_iv_index_mapping(obj, id);
+    attr_index_t index = rb_obj_ensure_iv_index_mapping(obj, id);
+    RB_OBJ_WRITE(obj, &ROBJECT_IVPTR(obj)[index], val);
+    return val;
+}
+
+/* Set the instance variable +val+ on object +obj+ at ivar name +id+.
+ * This function only works with T_OBJECT objects, so make sure
+ * +obj+ is of type T_OBJECT before using this function.
+ */
+VALUE
+rb_vm_set_ivar_id(VALUE obj, ID id, VALUE val)
+{
+    rb_check_frozen_internal(obj);
+    obj_ivar_set(obj, id, val);
+    return val;
+}
 
-    len = ROBJECT_NUMIV(obj);
-    if (len <= ivup.index) {
-        uint32_t newsize = iv_index_tbl_newsize(&ivup);
-        init_iv_list(obj, len, newsize, ivup.u.iv_index_tbl);
+bool
+rb_shape_set_shape_id(VALUE obj, shape_id_t shape_id)
+{
+    if (rb_shape_get_shape_id(obj) == shape_id) {
+        return false;
     }
-    RB_OBJ_WRITE(obj, &ROBJECT_IVPTR(obj)[ivup.index], val);
 
-    return val;
+#if SHAPE_IN_BASIC_FLAGS
+    RBASIC_SET_SHAPE_ID(obj, shape_id);
+#else
+    switch (BUILTIN_TYPE(obj)) {
+      case T_OBJECT:
+          ROBJECT_SET_SHAPE_ID(obj, shape_id);
+          break;
+      case T_CLASS:
+      case T_MODULE:
+          {
+              RCLASS_EXT(obj)->shape_id = shape_id;
+              break;
+          }
+      default:
+          {
+              if (shape_id != FROZEN_ROOT_SHAPE_ID) {
+                  struct gen_ivtbl *ivtbl = 0;
+                  RB_VM_LOCK_ENTER();
+                  {
+                      st_table* global_iv_table = generic_ivtbl(obj, 0, false);
+
+                      if (st_lookup(global_iv_table, obj, (st_data_t *)&ivtbl)) {
+                          ivtbl->shape_id = shape_id;
+                      }
+                      else {
+                          rb_bug("Expected shape_id entry in global iv table");
+                      }
+                  }
+                  RB_VM_LOCK_LEAVE();
+              }
+          }
+    }
+#endif
+
+    return true;
+}
+
+/**
+ * Prevents further modifications to the given object.  ::rb_eFrozenError shall
+ * be raised if modification is attempted.
+ *
+ * @param[out]  x  Object in question.
+ */
+void rb_obj_freeze_inline(VALUE x)
+{
+    if (RB_FL_ABLE(x)) {
+        RB_OBJ_FREEZE_RAW(x);
+
+        rb_shape_transition_shape_frozen(x);
+
+        if (RBASIC_CLASS(x) && !(RBASIC(x)->flags & RUBY_FL_SINGLETON)) {
+            rb_freeze_singleton_class(x);
+        }
+    }
 }
 
 static void
@@ -1581,10 +1564,14 @@ ivar_set(VALUE obj, ID id, VALUE val)
 
     switch (BUILTIN_TYPE(obj)) {
       case T_OBJECT:
-        obj_ivar_set(obj, id, val);
-        break;
+      {
+          obj_ivar_set(obj, id, val);
+          break;
+      }
       case T_CLASS:
       case T_MODULE:
+        // TODO: Transition shapes on classes
+        //rb_shape_transition_shape(obj, id, rb_shape_get_shape_by_id(RCLASS_SHAPE_ID(obj)));
         IVAR_ACCESSOR_SHOULD_BE_MAIN_RACTOR(id);
         rb_class_ivar_set(obj, id, val);
         break;
@@ -1614,161 +1601,86 @@ rb_ivar_set_internal(VALUE obj, ID id, VALUE val)
 VALUE
 rb_ivar_defined(VALUE obj, ID id)
 {
-    VALUE val;
-    struct st_table *iv_index_tbl;
-    uint32_t index;
+    attr_index_t index;
 
     if (SPECIAL_CONST_P(obj)) return Qfalse;
     switch (BUILTIN_TYPE(obj)) {
-      case T_OBJECT:
-        iv_index_tbl = ROBJECT_IV_INDEX_TBL(obj);
-        if (iv_index_tbl_lookup(iv_index_tbl, id, &index) &&
-            index < ROBJECT_NUMIV(obj) &&
-            (val = ROBJECT_IVPTR(obj)[index]) != Qundef) {
-            return Qtrue;
-        }
-        break;
       case T_CLASS:
       case T_MODULE:
-        if (RCLASS_IV_TBL(obj) && lock_st_is_member(RCLASS_IV_TBL(obj), (st_data_t)id))
+        if (RCLASS_IV_TBL(obj) && lock_st_is_member(RCLASS_IV_TBL(obj), (st_data_t)id)) {
             return Qtrue;
-        break;
+        }
+        else {
+            return Qfalse;
+        }
       default:
-        if (FL_TEST(obj, FL_EXIVAR))
-            return generic_ivar_defined(obj, id);
-        break;
+        return RBOOL(rb_shape_get_iv_index(rb_shape_get_shape(obj), id, &index));
     }
-    return Qfalse;
 }
 
 typedef int rb_ivar_foreach_callback_func(ID key, VALUE val, st_data_t arg);
 st_data_t rb_st_nth_key(st_table *tab, st_index_t index);
 
-static ID
-iv_index_tbl_nth_id(st_table *iv_index_tbl, uint32_t index)
-{
-    st_data_t key;
-    RB_VM_LOCK_ENTER();
-    {
-        key = rb_st_nth_key(iv_index_tbl, index);
-    }
-    RB_VM_LOCK_LEAVE();
-    return (ID)key;
-}
-
-static inline bool
-ivar_each_i(st_table *iv_index_tbl, VALUE val, uint32_t i, rb_ivar_foreach_callback_func *func, st_data_t arg)
-{
-    if (val != Qundef) {
-        ID id = iv_index_tbl_nth_id(iv_index_tbl, i);
-        switch (func(id, val, arg)) {
-          case ST_CHECK:
-          case ST_CONTINUE:
-            break;
-          case ST_STOP:
-            return true;
-          default:
-            rb_bug("unreachable");
-        }
+static void
+iterate_over_shapes_with_callback(rb_shape_t *shape, VALUE* iv_list, rb_ivar_foreach_callback_func *callback, st_data_t arg) {
+    switch ((enum shape_type)shape->type) {
+        case SHAPE_ROOT:
+            return;
+        case SHAPE_IVAR:
+            iterate_over_shapes_with_callback(shape->parent, iv_list, callback, arg);
+            VALUE val = iv_list[shape->iv_count - 1];
+            if (val != Qundef) {
+                callback(shape->edge_name, val, arg);
+            }
+            return;
+        case SHAPE_IVAR_UNDEF:
+        case SHAPE_FROZEN:
+            iterate_over_shapes_with_callback(shape->parent, iv_list, callback, arg);
+            return;
     }
-    return false;
 }
 
 static void
 obj_ivar_each(VALUE obj, rb_ivar_foreach_callback_func *func, st_data_t arg)
 {
-    st_table *iv_index_tbl = ROBJECT_IV_INDEX_TBL(obj);
-    if (!iv_index_tbl) return;
-    uint32_t i=0;
-
-    for (i=0; i < ROBJECT_NUMIV(obj); i++) {
-        VALUE val = ROBJECT_IVPTR(obj)[i];
-        if (ivar_each_i(iv_index_tbl, val, i, func, arg)) {
-            return;
-        }
-    }
+    rb_shape_t* shape = rb_shape_get_shape(obj);
+    iterate_over_shapes_with_callback(shape, ROBJECT_IVPTR(obj), func, arg);
 }
 
 static void
 gen_ivar_each(VALUE obj, rb_ivar_foreach_callback_func *func, st_data_t arg)
 {
+    rb_shape_t *shape = rb_shape_get_shape(obj);
     struct gen_ivtbl *ivtbl;
-    st_table *iv_index_tbl = RCLASS_IV_INDEX_TBL(rb_obj_class(obj));
-    if (!iv_index_tbl) return;
-    if (!gen_ivtbl_get(obj, 0, &ivtbl)) return;
+    if (!rb_gen_ivtbl_get(obj, 0, &ivtbl)) return;
 
-    for (uint32_t i=0; i<ivtbl->numiv; i++) {
-        VALUE val = ivtbl->ivptr[i];
-        if (ivar_each_i(iv_index_tbl, val, i, func, arg)) {
-            return;
-        }
-    }
-}
-
-struct givar_copy {
-    VALUE obj;
-    VALUE klass;
-    st_table *iv_index_tbl;
-    struct gen_ivtbl *ivtbl;
-};
-
-static int
-gen_ivar_copy(ID id, VALUE val, st_data_t arg)
-{
-    struct givar_copy *c = (struct givar_copy *)arg;
-    struct ivar_update ivup;
-
-    ivup.iv_extended = 0;
-    ivup.u.iv_index_tbl = c->iv_index_tbl;
-
-    RB_VM_LOCK_ENTER();
-    {
-        iv_index_tbl_extend(&ivup, id, c->klass);
-    }
-    RB_VM_LOCK_LEAVE();
-
-    if (ivup.index >= c->ivtbl->numiv) {
-        uint32_t newsize = iv_index_tbl_newsize(&ivup);
-        c->ivtbl = gen_ivtbl_resize(c->ivtbl, newsize);
-    }
-    c->ivtbl->ivptr[ivup.index] = val;
-
-    RB_OBJ_WRITTEN(c->obj, Qundef, val);
-
-    return ST_CONTINUE;
+    iterate_over_shapes_with_callback(shape, ivtbl->ivptr, func, arg);
 }
 
 void
 rb_copy_generic_ivar(VALUE clone, VALUE obj)
 {
-    struct gen_ivtbl *ivtbl;
+    struct gen_ivtbl *obj_ivtbl;
+    struct gen_ivtbl *new_ivtbl;
 
     rb_check_frozen(clone);
 
     if (!FL_TEST(obj, FL_EXIVAR)) {
         goto clear;
     }
-    if (gen_ivtbl_get(obj, 0, &ivtbl)) {
-        struct givar_copy c;
-        uint32_t i;
 
-        if (gen_ivtbl_count(ivtbl) == 0)
+    if (rb_gen_ivtbl_get(obj, 0, &obj_ivtbl)) {
+        if (gen_ivtbl_count(obj_ivtbl) == 0)
             goto clear;
 
-        if (gen_ivtbl_get(clone, 0, &c.ivtbl)) {
-            for (i = 0; i < c.ivtbl->numiv; i++)
-                c.ivtbl->ivptr[i] = Qundef;
-        }
-        else {
-            c.ivtbl = gen_ivtbl_resize(0, ivtbl->numiv);
-            FL_SET(clone, FL_EXIVAR);
+        new_ivtbl = gen_ivtbl_resize(0, obj_ivtbl->numiv);
+        FL_SET(clone, FL_EXIVAR);
+
+        for (uint32_t i=0; i<obj_ivtbl->numiv; i++) {
+            new_ivtbl->ivptr[i] = obj_ivtbl->ivptr[i];
+            RB_OBJ_WRITTEN(clone, Qundef, &new_ivtbl[i]);
         }
 
-        VALUE klass = rb_obj_class(clone);
-        c.iv_index_tbl = iv_index_tbl_make(clone, klass);
-        c.obj = clone;
-        c.klass = klass;
-        gen_ivar_each(obj, gen_ivar_copy, (st_data_t)&c);
         /*
          * c.ivtbl may change in gen_ivar_copy due to realloc,
          * no need to free
@@ -1776,9 +1688,17 @@ rb_copy_generic_ivar(VALUE clone, VALUE obj)
         RB_VM_LOCK_ENTER();
         {
             generic_ivtbl_no_ractor_check(clone);
-            st_insert(generic_ivtbl_no_ractor_check(obj), (st_data_t)clone, (st_data_t)c.ivtbl);
+            st_insert(generic_ivtbl_no_ractor_check(obj), (st_data_t)clone, (st_data_t)new_ivtbl);
         }
         RB_VM_LOCK_LEAVE();
+
+        rb_shape_t * obj_shape = rb_shape_get_shape(obj);
+        if (rb_shape_frozen_shape_p(obj_shape)) {
+            rb_shape_set_shape(clone, obj_shape->parent);
+        }
+        else {
+            rb_shape_set_shape(clone, obj_shape);
+        }
     }
     return;
 
@@ -1846,7 +1766,7 @@ rb_ivar_count(VALUE obj)
 
     switch (BUILTIN_TYPE(obj)) {
       case T_OBJECT:
-        if (ROBJECT_IV_INDEX_TBL(obj) != 0) {
+        if (rb_shape_get_shape(obj)->iv_count > 0) {
             st_index_t i, count, num = ROBJECT_NUMIV(obj);
             const VALUE *const ivptr = ROBJECT_IVPTR(obj);
             for (i = count = 0; i < num; ++i) {
@@ -1867,7 +1787,7 @@ rb_ivar_count(VALUE obj)
         if (FL_TEST(obj, FL_EXIVAR)) {
             struct gen_ivtbl *ivtbl;
 
-            if (gen_ivtbl_get(obj, 0, &ivtbl)) {
+            if (rb_gen_ivtbl_get(obj, 0, &ivtbl)) {
                 return gen_ivtbl_count(ivtbl);
             }
         }
@@ -1965,40 +1885,53 @@ rb_obj_remove_instance_variable(VALUE obj, VALUE name)
 {
     VALUE val = Qnil;
     const ID id = id_for_var(obj, name, an, instance);
-    st_data_t n, v;
-    struct st_table *iv_index_tbl;
-    uint32_t index;
 
+    // Frozen check comes here because it's expected that we raise a
+    // NameError (from the id_for_var check) before we raise a FrozenError
     rb_check_frozen(obj);
+
+    attr_index_t index;
+
     if (!id) {
         goto not_defined;
     }
 
     switch (BUILTIN_TYPE(obj)) {
-      case T_OBJECT:
-        iv_index_tbl = ROBJECT_IV_INDEX_TBL(obj);
-        if (iv_index_tbl_lookup(iv_index_tbl, id, &index) &&
-            index < ROBJECT_NUMIV(obj) &&
-            (val = ROBJECT_IVPTR(obj)[index]) != Qundef) {
-            ROBJECT_IVPTR(obj)[index] = Qundef;
-            return val;
-        }
-        break;
       case T_CLASS:
       case T_MODULE:
         IVAR_ACCESSOR_SHOULD_BE_MAIN_RACTOR(id);
-        n = id;
-        if (RCLASS_IV_TBL(obj) && lock_st_delete(RCLASS_IV_TBL(obj), &n, &v)) {
-            return (VALUE)v;
+        if (RCLASS_IV_TBL(obj)) {
+            st_data_t id_data = (st_data_t)id, val;
+            if (lock_st_delete(RCLASS_IV_TBL(obj), &id_data, &val)) {
+                return (VALUE)val;
+            }
         }
         break;
-      default:
-        if (FL_TEST(obj, FL_EXIVAR)) {
-            if (generic_ivar_remove(obj, id, &val)) {
-                return val;
-            }
+      case T_OBJECT: {
+        rb_shape_t * shape = rb_shape_get_shape(obj);
+        if (rb_shape_get_iv_index(shape, id, &index)) {
+            rb_shape_transition_shape_remove_ivar(obj, id, shape);
+            val = ROBJECT_IVPTR(obj)[index];
+            ROBJECT_IVPTR(obj)[index] = Qundef;
+            return val;
         }
+
+        break;
+      }
+      default: {
+        rb_shape_t * shape = rb_shape_get_shape(obj);
+
+        if (rb_shape_get_iv_index(shape, id, &index)) {
+            rb_shape_transition_shape_remove_ivar(obj, id, shape);
+            struct gen_ivtbl *ivtbl;
+            rb_gen_ivtbl_get(obj, id, &ivtbl);
+            val = ivtbl->ivptr[index];
+            ivtbl->ivptr[index] = Qundef;
+            return val;
+        }
+
         break;
+      }
     }
 
   not_defined: