Chapter 15: Arrays

Co-authored-by: XmiliaH <xmilia.hermit@gmail.com>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

1 files changed, 260 insertions, 0 deletions

diff --git a/docs/chapter15/README.md b/docs/chapter15/README.md
new file mode 100644
index 00000000..db0f2f1c
--- /dev/null
+++ b/docs/chapter15/README.md
@@ -0,0 +1,260 @@
+# Chapter 15: Arrays
+
+[Previous: Chapter 14](../chapter14/README.md) |
+[Next: Chapter 16](../chapter16/README.md)
+
+# Table of Contents
+
+1. [Parser changes](#parser)
+2. [TypeArray is TypeStruct](#type-array-is-typestruct)
+3. [Allocation and partial memory](#allocation-and-partial-memory)
+4. [New Address Math](#new-address-math)
+5. [Struct Layout](#struct-layout)
+6. [Some Simple Address Math Peeps](#some-simple-address-math-peeps)
+7. [Discussion](#discussion)
+
+
+At long last we introduce arrays!  These require more complex addressing math,
+which in turn means we need to change how Loads and Stores do addressing -
+with true field *offsets* instead of field *names*.  This means we also
+will do a struct field *layout* in this chapter.
+
+Arrays are created with the standard `new int[len]` syntax, and can be any base
+type and any integer expression length.  Arrays are read and written in the usual
+style: `Person p = persons[idx];` and `persons[idx] = new Person;`. The length
+is accessed with post-fix `#`; e.g. `persons#`.
+
+Like Java, arrays are always safety checked, and failing a runtime check
+will panic the Evaluator.
+
+- Indexing out of bounds:
+- `ary[-1]`
+- `ary[ary#]`
+- Creating an array with a bad length:
+- `new int[-1];    // Negative length`
+- `new int[1<<63]; // Too large`
+- `new int[3.14];  // Not an integer`
+
+
+You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter15) 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-chapter14...linear-chapter15) it to the previous chapter.
+
+
+## Parser
+
+The Parser changes to support arrays are fairly minimal.  The main change is
+when parsing a `type()` we look for array syntax: `int[]` is now a valid type.
+Any dimension of arrays are allowed, and the base type can be any type so
+e.g. `Person[][]?` is a two-dimensional array of `Person`s which might be null.
+
+Arrays are always created with zero/null bodies, so implicitly always allow
+`null` values.
+
+We make a new array with much the same syntax as making a new object: `new
+int[99]`.  The length is required and is any integer expression, so
+e.g. `new int[arg]` is an integer array of length `arg`.  Multi-dimensional arrays
+only make the outer dimension; the elements themselves are all null and typed
+as the next lower dimension array.
+
+Arrays implicitly have two fields: the length and the body.  The length is a
+read-only field set when the array is allocated; it is referenced with the
+post-fix `#` operator; e.g. `ary#`.  Example to sum an array:
+
+```java
+int[] ary = new int[arg];
+int sum = 0;
+int i = 0;
+while( i < ary# ) {
+    sum = sum + ary[i];
+    i = i + 1;
+}
+```
+
+Because arrays have two implicit fields, they get 2 unique alias numbers per
+base array type.  This means that `int[]` and `flt[]` types never alias, but
+all `int[]` types all alias - and all references into an array body all alias
+with each other.  This can lead to some conservative code (no optimization)
+with mixing loads and stores in an array in a loop.  Some of this can be
+addressed in a later chapter - simple 1-d stencil calculations can be heavily
+optimized - but Simple the compiler is not targeting complex vectorization.
+
+
+## Type Array is TypeStruct
+
+Arrays have a unique type, which is actually just a `TypeStruct` with fields
+named `#` and `[]`.  Since these are not available as field names from within
+the Parser, users cannot write their own structs which get confused as arrays.
+
+These `TypeStruct` arrays otherwise behave exactly as a `TypeStruct`.
+
+
+## Allocation and partial memory
+
+This chapter keeps Chapter 11's single hidden `$mem` variable and lazy
+`BulkMemPhi`/`MemPhi` partitioning. Start produces `{ctrl, $mem, arg}` and
+Return consumes `{ctrl, $mem, value}`. Array initialization changes New:
+instead of separate initializing Stores, New allocates and zeros the object.
+
+New consumes `{ctrl, $mem, size}` and produces just `{ptr, $mem}`. The pointer
+is result 0 because New has no control result. Its memory input and result
+cover only the field aliases in New's internal `TypeStruct`, also available
+through its `TypeMemPtr`. Alias numbers are identities, not projection indices.
+
+For an allocation affecting aliases `A`, the parser builds:
+
+```text
+input = MemMerge(default: absent, each a in A: before[a])
+new   = New(ctrl, input, size)
+ptr   = Proj(new, 0)
+after = MemMerge(default: before, each a in A: Proj(new, 1))
+```
+
+All affected entries share the same memory projection. The input MemMerge is
+partial: a null default means an unlisted alias is **not covered**. The output
+aggregate retains the previous memory for unrelated aliases. An empty struct
+has an empty partial input and leaves whole memory unchanged.
+
+Memory types now pair an alias with the type of values stored in that slice.
+An alias query through New combines the incoming contents with the field's
+initializer: integer zero, floating zero, or null. The query follows aggregates
+and allocations, stops at cached Phi types, and records optimizer dependencies.
+MemPhi merges these value types for its one alias. No per-alias New projections
+or new lattice domain are needed.
+
+A Load using New's own pointer can fold to the initialized value. A pointer
+from a distinct New can bypass the allocation to its memory input. Mere node
+inequality is insufficient: a Phi or cast can still denote the allocated object.
+Array length is set by a subsequent Store; the array body is zeroed by New.
+Array accesses retain their existing control input as the bounds-check proxy.
+
+Both schedulers follow an alias through MemMerge to find New's memory effect.
+MemMerge itself does not overwrite memory, but must not hide the ordering of
+a read before allocation and a later write to an existing object.
+
+## New Address Math
+
+Since arrays need addressing math to index into them, Loads and Stores need a
+way to compute an offset.  Previously Loads and Stores only worked on structs,
+and included the field name within them - thus the implicit addressing was field
+name (e.g. a string lookup!).  New in this chapter we create a struct *layout*
+and compute field offsets to all structs.
+
+Loads and Stores now take an `off` instead of a field name, and the field
+name is included for debugging only.
+
+```java
+public MemOpNode(String name, int alias, Type glb, Node mem, Node ptr, Node off) {
+    super(null, mem, ptr, off);
+    _name  = name;
+    _alias = alias;
+    _declaredType = glb;
+}
+```
+
+For arrays, the `off` is computed via the normal array math sequence:
+
+  `off = base + (idx << scale)`
+
+The base and index are computed for arrays from the element type, and used
+by the parser to build the offset.  For structs, the layout is used.
+
+```java
+// Get field type and layout offset from base type and field index fidx
+Field f = base._fields[fidx];  // Field from field index
+Node off;
+if( name.equals("[]") ) {      // If field is an array body
+    // Array index math
+    Node idx = require(parseExpression(),"]");
+    off = new AddNode(con(base.aryBase()),new ShlNode(idx,con(base.aryScale())).peephole()).peephole();
+} else {                       // Else normal struct field
+    // Hardwired field offset
+    off = con(base.offset(fidx));
+}
+```
+
+
+## Struct Layout
+
+New in this chapter is struct *layouts*: a fixed offset inside a block of
+memory where a particular field is stored.  The offset is computed and cached
+in `TypeStruct`.  Every field type now has a `log_size`.  These fields are
+packed by size, with alignment padding and the whole struct is padded out to
+mod 8.  This means the actual field offset and the field declaration order are
+*unrelated*: large fields pack low, and smaller fields pack next.
+
+```java
+struct s {
+  i8 b;        // log_size=0
+  u16 char;   // log_size=1
+  Person p;      // log_size=2
+  flt pi;        // log_size=3
+}
+// Layout will be:
+struct s {
+  flt pi;        // offset= 0, log_size=3
+  Person p;      // offset= 8, log_size=2
+  u16 char;   // offset=12, log_size=1
+  i8 b;          // offset=14, log_size=0
+  void pad;      // offset=15, size = 1
+}                // size  =16
+```
+
+Field size is mostly obvious except perhaps for `TypeInteger`.  Floats are
+either 32 bits or 64 bits.  Pointers are set at 4 bytes in `TypeMemPtr` and
+this could be changed at a later date to support a larger range of pointers.
+`TypeInteger` only has valid `log_size` fields for a fixed set of user-visible
+integer ranges.  Other ranges are possible in Simple via `compute` calls, but
+these will never show up as base field types:
+
+   `struct S { i16 x; }`
+
+Here `x` will have offset 0 and size 2 bytes, and `S` will be padded to size 8.
+
+   `S s = new S; s.x = 3;`
+
+The same `x` field now holds either a 0 or a 3, so the `TypeInteger` for `x`
+will be a range `[0-3]` which could be represented in just 2 bits ... but this is not used to compute the field size.
+
+
+## Some Simple Address Math Peeps
+
+Shift-left by 0 is an identity: `(x<<0)` becomes `x`.
+
+Shift-left with a constant add distributes, to allow more constant folding:
+`(x + c) << i` becomes `(x << i) + (c << i)`.
+
+This means the IR for:
+
+  `x[i]`  becomes  `16/*base*/ + (i << 3/*scale*/)`
+  becomes `Load(mem,x,Add(Shl(i,3),16))`
+
+
+  `x[i+1]` becomes `16/*base*/ + ((i+1) << 3/*scale*/)` becomes
+  `Load(mem,x,Add(Shl(i,3),24))`
+
+Notice the `idx+1` folds the `+1` into the base math.
+
+Also notice this form is perfect for the X86 addressing modes.
+
+## Discussion
+
+Included in the test cases is a simple rolling sum, and a Sieve of Eratosthenes.
+
+```java
+int i=0;
+while( i < ary# ) {
+    ary[i] = i;
+    i = i+1;
+}
+```
+
+Here we really see the lack of an `i++` operator and a `for` loop.  You can
+imagine another syntax:
+
+```java
+for( int i=0; i < ary#; i++ )
+    ary[i] = i;
+```
+
+that would be entirely syntactic-sugar over the existing parser, but would
+really help make array looping syntax clearer.  There are lots of options
+here, which should really be the focus of another chapter!