Chapter 23: Methods and Revisiting Types

Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

1 files changed, 463 insertions, 0 deletions

diff --git a/docs/chapter23/README.md b/docs/chapter23/README.md
new file mode 100644
index 00000000..747b37e3
--- /dev/null
+++ b/docs/chapter23/README.md
@@ -0,0 +1,463 @@
+# Chapter 23: Methods and Revisiting Types
+
+English | [日本語](README.ja.md)
+
+[Previous: Chapter 22](../chapter22/README.md) |
+[Next: Chapter 24](../chapter24/README.md)
+
+In this chapter we add *methods*, functions defined in structs which take a
+hidden `self` argument and can access the struct fields.  Here is an
+`indexOf` method in a String-like class:
+
+```java
+// A String-like class, with methods
+struct String {
+    u8[~] buf; // Buffer of read-only characters
+
+    // Return the index of the first character 'c' or -1
+    val indexOf = { u8 c ->           // Hidden 'self' argument
+        for( int i=0; i<buf#; i++ )   // Direct access to `buf` field
+            if( buf[i]==c )
+                return i;
+        return -1;                    // 'c' not in 'self'
+    };
+};
+```
+
+Also in this chapter we revisit our Types and make some major changes:
+- Types are now *cyclic*: a Type can (indirectly) point to itself.
+- Types remain
+  [*interned*](https://en.wikipedia.org/wiki/Interning_(computer_science)) or
+  [*hash-consed*](https://en.wikipedia.org/wiki/Hash_consing).
+- Type objects are managed via an object pool.
+- Newly created types probe the interning table, and if a hit is found, the
+  original is used, and the new type is returned to the object pool.
+- The intern table hit rate is something like 99.9%; nearly all types created
+  have already been created!  This last point turns into an interesting
+  performance win; much of the work in an optimizing compiler deals with
+  manipulating Types, keeping the count of Types small and fitting in the
+  faster levels of cache is a nice payoff.
+- Many of the interning algorithms require cycle-handling via some kind of
+  "visit bit".  One easy way to do this is add a *unique id* UID to every type,
+  a small dense integer that is used in bit-sets to avoid visiting a type more
+  than once.  Smaller UIDs use smaller bit-sets, which again fit in the faster
+  cache levels.
+- As a consequence, our types are cyclic (the goal!), and **faster** and have a
+  more complex implementation.  **Using** the types remains the same; the same
+  Type API is used when creating them, MEETing, making Read-Only, printing,
+  etc; only the implementation details change.
+
+
+You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter23) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter22...linear-chapter23) it to the previous chapter.
+
+
+Here is the [complete language grammar](23-grammar.md) for this chapter.
+
+## Why Cyclic Types?
+
+Cyclic types give us a sharper analysis than the alternative, and thus admit
+more programs or better optimizations or both.  In Simple's case Types are also
+used for type-checking, so sharper types means we allow more valid programs.
+
+**Why Cyclic Types Now**?  Because we hit them as soon as we allow a
+function definition inside of a struct which takes the struct as an argument,
+i.e. *methods* taking a *self* argument.
+
+Let's look at our `String.indexOf` example above.  Here we define a `String`
+with an `indexOf` method; a hidden argument string `self` is passed in
+and searched.  What is the type of `struct String`?
+
+`struct String { u8[~] buf; { !String !self, u8 c -> int } indexOf; }`
+
+It is the type named `String` with a field `u8[~] buf` and a final assigned
+constant field `indexOf`, itself with type `{ !String !self, u8 c -> int }`.
+i.e., the type of `String` has a reference to itself, nested inside the type of
+`indexOf`.... i.e. `String`'s type is *cyclic*.
+
+
+## Less Cyclic Types
+
+This problem of cyclic types has been around for a long time, and there are a
+number of tried and true methods for dealing with them.  One easy one is to
+have a type *definition* and a separate type *reference*.  The reference refers
+to the type by doing some kind of lookup; an easy one is via the type name and
+the parser's symbol table i.e., some kind of hash table lookup.
+
+In this model the cycle is effectively avoided; all "back edges" in the type
+cycle are really done by the reference edge (itself possibly a hash table
+lookup).
+
+So why not go down this route?
+
+Because all type references lead back to the same type definition - which
+means any specialization of type information is lost, because *all* type
+references lead back to the same definition and you end up taking the MEET
+over *all* paths.
+
+Here's an example, a Linked List with a Java `Object` or a C `void*` payload:
+
+```java
+struct List {
+  !List !next;
+  Object payload;  // equivalently for C: void*
+}
+// Then walk a collection of ints and build a List:
+List nums = null;
+for( int x : ary_ints )
+    nums = new List{next=nums; payload=x; }
+
+// Again for strings:
+List strs = null;
+for( String x : ary_strs )
+    strs = new List{next=strs; payload=x; }
+```
+
+What is the type of `nums`?  It's `*List`... which is:
+
+```
+struct List { List *next; Object payload }
+```
+
+No sharpening of `Object` to `int` nor `String` because every List object
+has a payload of `Object` and `Object` MEET `int` is back to `Object`.
+
+If we allow truly cyclic types then in these kinds of places we can discover
+(or infer) a sharper type: `*List<int> { *List<int> next, int payload }`
+basically building up *generics* in the optimizer.  This is not generics in the
+language nor type-variables per-se, but it goes a long way towards them.
+
+
+## Handling cyclic types
+
+In this Chapter Simple handles cyclic types directly.  This means we have
+`Type` objects whose child types can point back to the original - and that
+means
+[*recursive descent*](https://en.wikipedia.org/wiki/Recursive_descent_parser)
+no longer works on Types.
+
+Up till now we've used recursive descent when building up Types: child types
+are built first, then interned, then the interned children are used to build up
+the next layer.  Because each layer is interned and because recursive descent
+stops at interned Types we avoid repeating work at shared Types.  This makes
+operations on the current Types linear in the *delta* between the old and new
+Types, i.e. incremental and fast.
+
+With the new cyclic types we now run into the problem that we cannot intern a
+cycle until we see the whole cycle.  Also hash tables require an equality
+check and we cannot use recursive descent to compare a cycle for equality.
+
+The standard way to deal with cycles in a graph is with some kind of *visited*
+notion, a "I have been here before" indicator.  We will use a hashtable keyed
+from a unique type ID; "visited" just means your unique ID is a key in the
+table.  Every Type thus picks up a unique ID from a global counter.  Since we
+will be interning Types we only need as many unique IDs as we have unique Types
+(plus a few spare to build and intern cycles).  From prior history I know this
+number typically maxes out in the low thousands so a small integer will do.
+
+Another thing - we want to keep as much of our existing infrastructure as
+we can, so we are going to keep all our existing recursive descent visitations
+with some small modifications.
+
+`TypeStructs` exist in every Type cycle (except pure function type cycles,
+where a function takes *itself* as an argument, which are weird and we kinda
+don't care how they get handled).  So in the core part of every `TypeStruct`
+generator we'll set an element in a global `VISIT` hashtable to signal the
+start of a cyclic Type creation - and we'll check for those elements to stop
+cycling.
+
+
+
+
+Time for an example!
+
+Let's go with a linked list, where we might have cycles of unrelated payloads
+(but here only strings).  Mind you, a linked list is almost always the wrong
+structure for any given job (being wildly inefficient compared to easy
+alternatives) but it is a great tutorial data structure.
+
+
+```java
+struct List {
+    !List? !next; // Next pointer or null
+    str !name;    // Payload
+};
+```
+
+And the type of this struct matches its declaration:
+
+`struct List { List*? next, str !name };`
+
+We can use this to build up a list of strings:
+
+```java
+var list = new List{ name="Hello"; };
+list = new List { list, name="World"; };
+```
+
+
+### Checking a cyclic type for Read-Only / Final
+
+Suppose at some point we want to make a read-only immutable version:
+```java
+val hello = list; // Make a read-only version
+print(hello);     // Pass along the read-only version
+```
+
+What is the type of `hello`?  It is the read-only type of `List`... and `List` is
+a cyclic type. Follow the implementation of
+[`Type.makeRO`, `isFinal`, and `_isFinal`](../../src/main/java/com/seaofnodes/simple/type/Type.java).
+
+We call `recurOpen()` to start/open the recursive walk, do the recursion
+calling `_isFinal()` and end/close the recursive walk, and return a boolean
+answer.  `_isFinal()` is NOT Java final, and is overridden in the Type subclasses.
+Subclasses implement the check for their own representation. For example,
+[`TypeMemPtr._isFinal`](../../src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java)
+reads the pointer's access permission, while
+[`TypeStruct._isFinal`](../../src/main/java/com/seaofnodes/simple/type/TypeStruct.java)
+walks the fields and handles cycles.
+
+Here we see a common pattern in dealing with cycles: the **test-and-set**.  We
+check for any hard and fast answers (open structs are never read-only; they are
+only partially defined and as-yet-unparsed non-final fields may appear), then
+we **test** if we have been here before, and if so stop the recursion and
+return some kind of answer.  For "isFinal" the returned answer is "yes final"
+as long as everything else in the cycle is also final.
+
+If we have not already checked this Type, we **set** the "visit" bit indicating
+we've been here before, and then proceed to do normal recursive-descent on the
+fields asking the same question recursively.
+
+For our example, we open the recursion (set a sentinel in `VISIT`), call
+`makeRO` on `struct List`, which then calls `_isFinal` which then checks
+the `_open` flag (not open), checks the `VISIT` (not visited), sets the
+UID in `VISIT` and starts walking the fields.
+[`Field._isFinal`](../../src/main/java/com/seaofnodes/simple/type/Field.java)
+checks both the field's binding and its type.
+
+The first field is `List*? !next`, which is not-final, so immediately returns
+`false`, which stops `_isFinal` on `List` and the whole `isFinal()` call returns
+`false`, and ends/closes the recursion (clears `VISIT`).
+
+
+### Making a cyclic type for Read-Only / Final
+
+To make the build-then-intern more obvious, let's put unique IDs on all our
+Types.  Here is the Type of `List` with sample UIDs following each unique type.
+Fields are also just types so also get UIDs.
+
+```
+struct List#2 {       // struct List has UID#2
+  List#2*?#3 !next#4, // Field  next has UID#3, type ptr-or-null#3 to List#2
+  str#1 !name#5       // Field  name has UID#5, type str#1
+};
+```
+
+You can see from the repeated UIDs that `List#2` happens twice... because List
+is cyclic.
+
+Now we do really need to make a cyclic type, and so our `makeRO()` call falls
+into the recursive path in
+[`Type.makeRO`](../../src/main/java/com/seaofnodes/simple/type/Type.java).
+
+Once again `recurOpen` starts/opens our recursive walk, and then we call
+`_makeRO()` which is overridden in the child Type classes. Follow
+[`TypeStruct._makeRO` and `recurPre`](../../src/main/java/com/seaofnodes/simple/type/TypeStruct.java)
+for the implementation.
+
+First up is the **test-and-set**.  The **test** is by type name; we attempt to
+get a `List` TypeStruct from `VISIT`, and if successful we return early -
+without recursion.  This means we can only have one `List` object in a R/O
+cycle of types.  You can imagine a tangle of multiple nested cyclic types where
+some are "List-of-int" and some are "List-of-Lists-of-", but here in the name
+of simplicity we choose to approximate our types to only a single instance of
+`List`.
+
+In this example on first visit of `List` we will miss in `VISIT`.  The next call
+to `ts = recurPre(_name,_open)` does common shared pre-recursive work: we make
+a new `TypeStruct` and **set** it in the `VISIT` table.  The new `TypeStruct`
+is a blank version of `List` with all !fields !attached; we force these fields to
+be final right away but they are missing their types:
+
+```
+struct List#12 {
+  ____ next#14,
+  ____ name#15
+}
+```
+
+
+Finally, we recursively call `_makeRO` on all the field types and set them in.
+We call `_fields[i]._t._makeRO()` on a `TypeMemPtr` which makes a new
+TMP after calling `_makeRO()` on the recursive `List`.
+
+This recursion comes right back to `TypeStruct._makeRO()`, and hits in the
+`VISIT` table on the same type name.  Unwinding the first field set, we have:
+
+```
+struct List#12 {
+  List#12 *? #13 next#14, // Recursive next field makes a cycle
+  ____  name#15
+}
+```
+
+You should notice all new UIDs for all the Types.  Since we cannot intern yet,
+we cannot end up with prior types.  The second field `str name` does already
+exist, so we end up with:
+
+```
+struct List#12 {
+  List#12 *? #13 next#14, // Recursive next field makes a cycle
+  str#2 name#15           // Reuse the interned type str#2
+}
+```
+
+At this point the recursion unwinds and we head into the complex
+[`Type.recurClose()`](../../src/main/java/com/seaofnodes/simple/type/Type.java).
+You might try single-stepping through
+[`TypeTest.testList`](../../src/test/java/com/seaofnodes/simple/TypeTest.java),
+which builds these types. Here is a high
+level summary:
+
+Copy all the visited types out of `VISIT` for easier management; we might find
+some of these types already interned, and then we'll remove them from further
+processing; this is easier if they are not in a HashMap.
+
+**Pass#1:** look for pre-existing interned parts not in any cycle, and just
+replace them.  We could have a new cycle of Types with pointers off to older
+interned types... that we made copies of.  After this step, we'll still have
+new cycles but the output edges will point to prior types if possible.
+Replaced types hit the delayed `FREES` list.
+
+**Pass#2:** All types have their *duals* pre-computed and directly available.
+Make the recursive cyclic duals now.
+
+**Pass#3:** Install the new types.  It *is* possible to now discover common
+pointers to newly interned types, and so again we need to test and replace as
+we go (and put the unused types on the delayed `FREES` list again).  This step
+requires hash table probe - which requires a cyclic hash and cyclic equals.
+
+**Pass#4:** Free up all the delayed-free Types now, to be recycled in future
+Type productions.
+
+In the end, the new `List` cyclic type is wholly interned - with a R/W version
+of `List#2` pointing back to the R/W `List#2` and the R/O version `List#12`
+pointing back to the same R/O `List#12`.
+
+
+
+### Cyclic HashCode and Equals
+
+Cyclic `hashCodes` and `equals` deserve more discussion.  When comparing two
+cycles for equivalence we want to be equivalent regardless of where the
+comparison starts.  i.e. cycle `A<->B` should be equal to cycle `B<->A`.  This
+means they both need the same hashcode, and this means we cannot use
+order-varying hashes!
+
+E.g. Suppose A has static hash value 1 (plus something recursively from B's
+hash), and vice-versa B has static hash value 3 (and something recursive from
+A), and we compute hashes as `parent.hash*7 + child.hash`.  If we compute A's
+hash as `A.hash * 7 + B.hash` we get `1 * 7 + 3 == 10`, and then later we start
+from B we get: `B.hash * 7 + A.hash` and which then becomes `3 * 7 + 1 ==
+22`... and their hashes differ so the hash table might miss the equivalence.
+Also, if we simply use recursive descent in the cycle we'll
+recurse until stack overflow and crash.
+
+We fix this by having `TypeStruct.hash()` *not* recurse - thus its hash
+function is somewhat weak, depending only on the field names and aliases.
+
+*Cyclic-equals* is triggered by the `VISIT` table being not-empty, and uses
+another unrelated *visit* table, the `CEQUALS` table, to separate concerns from
+`VISIT`.  The cycle-equals check proceeds like the normal `eq` with recursive
+descent on the parts, and some up-front hard-and-fast static checks - and the
+ubiquitous **test-and-set** pattern before the recursion.
+
+If we ever compare the same two types for cycle-equals again, we assume they
+will be cycle-equals (all other things being equals).
+
+
+
+## Methods and Final Fields and Classes
+
+Methods are simply function values (final fields) declared inside a struct that
+take an implicit `self` argument.
+
+Final fields declared in the original struct definition are *values* and cannot
+change; they are the same for all instances.  They get moved out of the
+struct's memory footprint and into a *class* - a collection of values from the
+final fields.  Classes are just plain namespaces and have no concrete
+implementation; they are not reified.
+
+```java
+struct vecInt {
+    u32 !len;   // Actual number of elements
+    int[] !buf; // Array of integers.
+
+    // Since "add" is declared with `val` in the original struct definition,
+    // it is a final field and is moved out of here to the class.
+
+    // Method: Internal: copy buf to a new size
+    val _grow = { int sz ->
+        var buf2 = new int[sz];
+        for( int i=0; i<len; i++ )
+            buf2[i] = buf[i];
+        buf = buf2;
+    };
+
+    // Method: Add an element, growing the backing array when needed.
+    val add = { int e ->
+        if( len >= buf# ) _grow(buf#*2);
+        buf[len++] = e;
+        return self;
+    };
+
+
+};
+
+val primes = new vecInt{buf = new int[4];}.add(2).add(3).add(5).add(7).add(11);
+```
+
+Here the `val add` field is a *value* field, a constant function value.  It is
+moved out of the basic `vecInt` object into `vecInt`'s *class*, and takes no
+storage space in `vecInt` objects.  The same happens for `_grow`.  The size of
+a `vecInt` instance is thus its `u32` length and array pointer, plus alignment
+padding. The array header and elements occupy a separate allocation. Reclaiming
+the old buffer after growth is outside this example. Appending
+`return primes.len*100+primes.buf[4];` produces 511 on both RISC-V and ARM.
+
+## RegAlloc improvements: grouping popular uses
+
+Chapter 22 improved color preferences and cheap-spill ordering.  This chapter
+adds a way to split a popular value whose uses demand incompatible registers.
+For example, several shifts may need the same count register while another use
+needs a different register.  Sharing one copy for each compatible group can
+avoid inserting a separate copy at every use.
+
+The allocator applies this to a single-definition live range with an empty
+register mask and more than two fixed-register uses.  It intersects overlapping
+use masks into groups; narrowing a group keeps it compatible with its earlier
+users, so one pass suffices. Disjoint masks start separate groups.  It snapshots
+distinct users before rewiring their inputs, ignores scheduling-only edges,
+and counts a call once even when the value supplies several arguments.
+
+Grouping declines values used by multiple calls, whose register kills tend to
+undo the benefit of a shared copy.  The usual loop-boundary splitting remains
+the fallback, including splitting an existing copy when all uses have the same
+loop depth.  Cold-first loop splitting is left for Chapter 24; area/cost spill
+ranking remains for Chapter 25.
+
+Rows are fixed test cohorts; columns are compiler chapters. Each cell gives
+**Ops / RA / X**: executed ARM+RISC-V instructions, the subset emitted for
+allocator copies/rematerializations, and x86's loop-weighted split-move estimate.
+**Cases D / X** counts measured dynamic program/target cases and x86 compilations;
+membership and inputs stay fixed across columns. Native-library work is excluded.
+Chapter 20 has no encoder, hence no dynamic counts. Lower is better within each
+metric; see the [measurement details](../regalloc-spills.md) for coverage.
+
+<!-- spill-matrix:start -->
+| Test cohort | Cases D / X | Ch 20: Ops / RA / X | Ch 21: Ops / RA / X | Ch 22: Ops / RA / X | Ch 23: Ops / RA / X |
+|---|---:|---:|---:|---:|---:|
+| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | 58,736 / 9,084 / 184 |
+| Ch 21 | 20 / 18 |  | 6,207 / 261 / 461 | 6,324 / 379 / 475 | 6,326 / 381 / 475 |
+| Ch 22 | 14 / 8 |  |  | 198 / 60 / 7 | 194 / 56 / 7 |
+| Ch 23 | 14 / 8 |  |  |  | 630 / 160 / 36 |
+<!-- spill-matrix:end -->