# Chapter 23: Methods and Revisiting Types English | [日本語](README.ja.md) [Previous: Chapter 22](../chapter22/README.md) | [Next: Chapter 24a](../chapter24a/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= b > c` are allowed; `a < b > c` is rejected. Equality has lower precedence and does not join a chain. Parentheses can still make the result of one comparison an operand of another. ## 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 { *List 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). ## Finalizing field layouts `FinalizeIR` now also settles field sizes and layouts, replaces symbolic field offsets by constants, and runs peepholes exposed by those constants. Recursive type construction must finish before layout is queried. The phase follows `Iter` and precedes `TypeCheck`; the driver includes it when compiling through any later stage. ## 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 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](../docs/regalloc-spills.md) for coverage. | 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 |