path: root/chapter23/README.md

# 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.


The lazy memory model from Chapter 11 continues through the new type system.
BulkMemPhi/MemPhi discover aliases during optimization. Each New covers only
instance fields; class-wide (`_one`) fields are excluded from its partial memory.
Field offsets stay symbolic until layout, and Loads retain cyclic field types
and deep-final information while querying the contents of a precise alias.

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.


## 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.  Let's look at `Type.makeRO`:

```java
public final Type makeRO() {
    if( isFinal() ) return this; // First check if already read-only
    return recurOpen()._makeRO().recurClose();
}
```

and `isFinal()`:

```java
// Are all reachable struct Fields are final?
public final boolean isFinal() { return recurClose(recurOpen()._isFinal()); }
boolean _isFinal() { assert _type < TCYCLIC; return true; }
```

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.
Most subclasses just forward the problem along:

`@Override boolean _isFinal() { return _obj._isFinal(); }`

until we hit `TypeStruct`:

```java
@Override boolean _isFinal() {
    if( _open ) return false;     // May have more non-final fields
    if( VISIT.containsKey(_uid) ) // Test: been here before?
        return true;              // Cycles assume final
    VISIT.put(_uid,this);         // Set: don't do this again
    for( Field fld : _fields )
        if( !fld._isFinal() )
            return false;
    return true;
}
```

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.  Fields check:

`@Override boolean _isFinal() { return _final && _t._isFinal(); }`

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 next line:

`return recurOpen()._makeRO().recurClose();`.

Once again `recurOpen` starts/opens our recursive walk, and then we call
`_makeRO()` which is overridden in every child Type class.  Let's look at
`TypeStruct`s version:

```java
// Make a read-only version
@Override TypeStruct _makeRO() {
    // Check for already visited
    TypeStruct ts = (TypeStruct)VISIT.get(_name);
    if( ts!=null ) return ts;   // Already visited
    ts = recurPre(_name,_open); // Make a new type with blank fields
    Field[] flds = ts._fields;
    for( Field fld : flds ) fld._final = true;

    // Now start the recursion
    for( int i=0; i<flds.length; i++ )
        flds[i].setType(_fields[i]._t._makeRO());

    return ts;
}
```

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()`.  You might try single-stepping through the code for a few
examples; the `TypeTest.testList` test 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.

Chapter 21's adjacent-copy forwarding also carries forward: after coloring,
a sole use in the next instruction can read the source register when its
operand mask permits it and no two-address tie is broken. The table below
includes this cleanup and the lazy memory forward port. Cohort 22 now also includes the two zero-move C return
ABI checks added since the earlier audit (26 entries instead of 24).

Run `make spill-stats` in this directory. All rows below use **this chapter's
compiler**, seed 123, and frozen source/target combinations from each cohort.
The Windows run combines x86 SystemV/Win64 and RISC-V/ARM SystemV. Diagnostic
machine graphs are checked separately and do not contribute to the counts.

| Program cohort | Compilations | Retained moves | Loop-weighted moves |
|---|---:|---:|---:|
| Chapter 20 | 39 | 323 | 442 |
| Chapter 21 | 52 | 433 | 965 |
| Chapter 22 | 26 | 67 | 67 |
| Chapter 23 | 30 | 78 | 225 |
| **Total** | **147** | **901** | **1,699** |

`_spills` counts retained SplitNodes, including register moves; `_spillScaled`
weights them by `8^loopDepth`. These estimate compiler-generated moves, not
runtime memory traffic. The reporter prints individual compilations and sums
by CPU/ABI, and still reports failure when a spill expectation or execution
check fails.

In the earlier audit, before adjacent-copy forwarding, disabling grouping produced
**the same 933 moves / 1,745 weighted moves**. The original grouping code also
has those totals. This suite therefore shows no spill improvement from grouping;
the reduced machine-graph regression exercises its compatibility and call rules,
including a null-mask crash in the old implementation. A plausible allocator
heuristic needs measurements on workloads that reach it before claiming a win.

For the older cohorts alone, Chapter 22's compiler produced 838 moves / 1,496
weighted moves; this compiler then produced 849 / 1,514. That comparison includes
changes outside allocation. In particular, Chapter 20's frozen String input
survives optimization here and costs 16 weighted moves; Chapter 22 eliminated
it at this seed. It would be misleading to attribute that difference to grouping.

The original 64-bit `person21` and guarded `stringHash21` inputs preserve cohort
21. The revised String input and two encoding tests enabled in this chapter
belong to cohort 23. Keeping these cohorts fixed makes subsequent comparisons
meaningful even as the language and its tests grow.