summaryrefslogtreecommitdiff
path: root/docs/chapter15
diff options
context:
space:
mode:
Diffstat (limited to 'docs/chapter15')
-rw-r--r--docs/chapter15/15-grammar.ja.md135
-rw-r--r--docs/chapter15/15-grammar.md131
-rw-r--r--docs/chapter15/Makefile12
-rw-r--r--docs/chapter15/README.ja.md188
-rw-r--r--docs/chapter15/README.md262
5 files changed, 728 insertions, 0 deletions
diff --git a/docs/chapter15/15-grammar.ja.md b/docs/chapter15/15-grammar.ja.md
new file mode 100644
index 00000000..09438f64
--- /dev/null
+++ b/docs/chapter15/15-grammar.ja.md
@@ -0,0 +1,135 @@
+# 第15章の文法
+
+[English](15-grammar.md) | 日本語
+
+この文書は [原文](15-grammar.md) の日本語訳です。
+
+[第15章に戻る](README.ja.md)
+
+```antlrv4
+grammar SimpleLanguage;
+
+program : block EOF ;
+
+block : statement+ ;
+
+
+statement
+ : '{' block '}'
+ | returnStatement
+ | ifStatement
+ | whileStatement
+ | breakStatement
+ | continueStatement
+ | structDeclaration
+ | expressionStatement
+ ;
+
+
+returnStatement : 'return' expression ';' ;
+
+ifStatement : 'if' '(' expression ')' statement ('else' statement)? ;
+
+whileStatement : 'while' '(' expression ')' statement ;
+
+breakStatement : 'break' ';' ;
+
+continueStatement : 'continue' ';' ;
+
+
+structDeclaration : 'struct' IDENTIFIER '{' fields '}' ;
+
+fields : field+ ;
+
+field : type IDENTIFIER ';' ;
+
+
+expressionStatement
+ : type IDENTIFIER ';'
+ | type IDENTIFIER '=' expression ';'
+ | IDENTIFIER '=' expression ';'
+ | expression
+ ;
+
+PRIMTYPE
+ : 'int'
+ | 'i8'
+ | 'i16'
+ | 'i32'
+ | 'i64'
+ | 'u8'
+ | 'u16'
+ | 'u32'
+ | 'flt'
+ | 'f32'
+ | 'f64'
+ | 'bool'
+ ;
+
+type
+ : PRIMTYPE
+ | typeName '?'?
+ | typeName nestedArray+
+ ;
+
+nestedArray : '?'? '[]'* ;
+
+typeName : IDENTIFIER ;
+
+
+expression : bitWiseExpression ;
+
+bitWiseExpression
+ : comparisonExpression ( '&' | '|' | '^' ) comparisonExpression)*
+ ;
+
+comparisonExpression
+ : shiftExpression (('==' | '!='| '>'| '<'| '>='| '<=') shiftExpression)*
+ ;
+
+shiftExpression
+ : additiveExpression ( '<<' | '>>>' | '>>' ) additiveExpression)*
+ ;
+
+additiveExpression
+ : multiplicativeExpression (('+' | '-') multiplicativeExpression)*
+ ;
+
+multiplicativeExpression
+ : unaryExpression (('*' | '/') unaryExpression)*
+ ;
+
+unaryExpression
+ : ('-') unaryExpression
+ | '!' unaryExpression
+ | primaryExpression postFix*
+ ;
+
+primaryExpression
+ : INTEGER_LITERAL
+ | '(' expression ')'
+ | 'true'
+ | 'false'
+ | 'null'
+ | newExpression
+ | IDENTIFIER
+ ;
+
+newExpression : 'new' IDENTIFIER [ '[' expression ']' ] ;
+
+postFix
+ : '.' IDENTIFIER [ '=' expression ]
+ | '[' expression ']' [ '=' expression ]
+ | '#'
+ ;
+
+INTEGER_LITERAL
+ : [1-9]DIGIT*
+ | [0]
+ ;
+
+IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ;
+
+NON_DIGIT: [a-zA-Z_];
+DIGIT: [0-9];
+```
diff --git a/docs/chapter15/15-grammar.md b/docs/chapter15/15-grammar.md
new file mode 100644
index 00000000..d524c560
--- /dev/null
+++ b/docs/chapter15/15-grammar.md
@@ -0,0 +1,131 @@
+# Grammar for Chapter 15
+
+English | [日本語](15-grammar.ja.md)
+
+```antlrv4
+grammar SimpleLanguage;
+
+program : block EOF ;
+
+block : statement+ ;
+
+
+statement
+ : '{' block '}'
+ | returnStatement
+ | ifStatement
+ | whileStatement
+ | breakStatement
+ | continueStatement
+ | structDeclaration
+ | expressionStatement
+ ;
+
+
+returnStatement : 'return' expression ';' ;
+
+ifStatement : 'if' '(' expression ')' statement ('else' statement)? ;
+
+whileStatement : 'while' '(' expression ')' statement ;
+
+breakStatement : 'break' ';' ;
+
+continueStatement : 'continue' ';' ;
+
+
+structDeclaration : 'struct' IDENTIFIER '{' fields '}' ;
+
+fields : field+ ;
+
+field : type IDENTIFIER ';' ;
+
+
+expressionStatement
+ : type IDENTIFIER ';'
+ | type IDENTIFIER '=' expression ';'
+ | IDENTIFIER '=' expression ';'
+ | expression
+ ;
+
+PRIMTYPE
+ : 'int'
+ | 'i8'
+ | 'i16'
+ | 'i32'
+ | 'i64'
+ | 'u8'
+ | 'u16'
+ | 'u32'
+ | 'flt'
+ | 'f32'
+ | 'f64'
+ | 'bool'
+ ;
+
+type
+ : PRIMTYPE
+ | typeName '?'?
+ | typeName nestedArray+
+ ;
+
+nestedArray : '?'? '[]'* ;
+
+typeName : IDENTIFIER ;
+
+
+expression : bitWiseExpression ;
+
+bitWiseExpression
+ : comparisonExpression ( '&' | '|' | '^' ) comparisonExpression)*
+ ;
+
+comparisonExpression
+ : shiftExpression (('==' | '!='| '>'| '<'| '>='| '<=') shiftExpression)*
+ ;
+
+shiftExpression
+ : additiveExpression ( '<<' | '>>>' | '>>' ) additiveExpression)*
+ ;
+
+additiveExpression
+ : multiplicativeExpression (('+' | '-') multiplicativeExpression)*
+ ;
+
+multiplicativeExpression
+ : unaryExpression (('*' | '/') unaryExpression)*
+ ;
+
+unaryExpression
+ : ('-') unaryExpression
+ | '!' unaryExpression
+ | primaryExpression postFix*
+ ;
+
+primaryExpression
+ : INTEGER_LITERAL
+ | '(' expression ')'
+ | 'true'
+ | 'false'
+ | 'null'
+ | newExpression
+ | IDENTIFIER
+ ;
+
+newExpression : 'new' IDENTIFIER [ '[' expression ']' ] ;
+
+postFix
+ : '.' IDENTIFIER [ '=' expression ]
+ | '[' expression ']' [ '=' expression ]
+ | '#'
+ ;
+
+INTEGER_LITERAL
+ : [1-9]DIGIT*
+ | [0]
+ ;
+
+IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ;
+
+NON_DIGIT: [a-zA-Z_];
+DIGIT: [0-9];
+```
diff --git a/docs/chapter15/Makefile b/docs/chapter15/Makefile
new file mode 100644
index 00000000..12659b8f
--- /dev/null
+++ b/docs/chapter15/Makefile
@@ -0,0 +1,12 @@
+GV := $(wildcard *.gv)
+SVG := $(patsubst %.gv,%.svg,$(GV))
+
+.PHONY: all
+all: $(SVG)
+
+%.svg: %.gv
+ dot -Tsvg $< > $@
+
+.PHONY: clean
+clean:
+ @rm -f $(SVG)
diff --git a/docs/chapter15/README.ja.md b/docs/chapter15/README.ja.md
new file mode 100644
index 00000000..b1ff339b
--- /dev/null
+++ b/docs/chapter15/README.ja.md
@@ -0,0 +1,188 @@
+# 第15章: 配列
+
+[English](README.md) | 日本語
+
+[前: 第14章](../chapter14/README.ja.md) |
+[次: 第16章](../chapter16/README.ja.md)
+
+この文書は [原文](README.md) の日本語訳です。
+
+# 目次
+
+1. [パーサーの変更](#パーサー)
+2. [配列型は TypeStruct](#配列型は-typestruct)
+3. [割り当てと部分メモリ](#割り当てと部分メモリ)
+4. [新しいアドレス計算](#新しいアドレス計算)
+5. [構造体の配置](#構造体の配置)
+6. [単純なアドレス計算のピープホール最適化](#単純なアドレス計算のピープホール最適化)
+7. [考察](#考察)
+
+ついに配列を導入します。配列にはもっと複雑なアドレス計算が必要なので、Load と Store のアドレス指定を、フィールドの*名前*から実際の*オフセット*へ変更しなければなりません。そのため、この章では構造体フィールドの*配置*も行います。
+
+配列は標準的な `new int[len]` 構文で作り、任意の基本型と、長さを表す任意の整数式を使えます。読み書きも通常の形式で、`Person p = persons[idx];` や `persons[idx] = new Person;` とします。長さには後置の `#`、たとえば `persons#` でアクセスします。
+
+Java と同じく、配列には常に安全性のチェックがあり、実行時チェックに失敗すると評価器はパニックになります。
+
+- 範囲外の添字:
+- `ary[-1]`
+- `ary[ary#]`
+- 不正な長さの配列の作成:
+- `new int[-1]; // Negative length`（負の長さ）
+- `new int[1<<63]; // Too large`（大きすぎる）
+- `new int[3.14]; // Not an integer`（整数ではない）
+
+[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの線形の Git リビジョン履歴で[この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter15)を読むことや、前章との[差分](https://github.com/SeaOfNodes/Simple/compare/linear-chapter14...linear-chapter15)を見ることもできます。
+
+## パーサー
+
+配列をサポートするパーサーの変更は、ごく小さなものです。主な変更は、`type()` のパース時に配列構文を探すことです。`int[]` が有効な型になります。配列は任意の次元を許し、基本型も任意なので、たとえば `Person[][]?` は null である可能性がある `Person` の2次元配列です。
+
+配列は常にゼロ/null の本体で作られるので、暗黙に常に `null` 値を許容します。
+
+新しい配列は、新しいオブジェクトとほぼ同じ構文、`new int[99]` で作ります。長さは必須で、任意の整数式を使えます。たとえば `new int[arg]` は長さ `arg` の整数配列です。多次元配列では最も外側の次元だけを作ります。要素自体はすべて null で、次に低い次元の配列として型付けされます。
+
+配列は暗黙に2つのフィールド、長さと本体を持ちます。長さは割り当て時に設定される読み取り専用フィールドで、後置 `#` 演算子、たとえば `ary#` で参照します。配列の合計を求める例です。
+
+```java
+int[] ary = new int[arg];
+int sum = 0;
+int i = 0;
+while( i < ary# ) {
+ sum = sum + ary[i];
+ i = i + 1;
+}
+```
+
+配列には2つの暗黙のフィールドがあるので、基本配列型ごとに2つの一意なエイリアス番号を得ます。したがって `int[]` と `flt[]` の型は決してエイリアスしませんが、すべての `int[]` 型はエイリアスします。また、配列本体へのすべての参照も互いにエイリアスします。このため、ループ内で配列へのロードとストアを混在させると、保守的なコード（最適化なし）になることがあります。一部は後の章で対処できます。単純な1次元ステンシル計算は大幅に最適化できますが、Simple コンパイラは複雑なベクトル化を目標にしていません。
+
+## 配列型は TypeStruct
+
+配列は固有の型を持ちますが、実際には `#` と `[]` という名前のフィールドを持つ `TypeStruct` にすぎません。これらはパーサーでフィールド名として使えないので、ユーザーが配列と混同される独自の構造体を書くことはできません。
+
+これらの `TypeStruct` 配列は、ほかの点では `TypeStruct` とまったく同じように振る舞います。
+
+## 割り当てと部分メモリ
+
+この章でも、第11章の1つの隠れた `$mem` 変数と、遅延的な `BulkMemPhi`/`MemPhi` 分割を維持します。Start は `{ctrl, $mem, arg}` を生成し、Return は `{ctrl, $mem, value}` を消費します。配列の初期化によって New が変わります。別々の初期化 Store の代わりに、New がオブジェクトを割り当ててゼロ化します。
+
+New は `{ctrl, $mem, size}` を消費し、`{ptr, $mem}` だけを生成します。New に制御の結果がないため、ポインタは結果 0 です。メモリ入力と結果は、New 内部の `TypeStruct` のフィールドのエイリアスだけを覆います。これらは `TypeMemPtr` からも得られます。エイリアス番号は識別子であり、射影の添字ではありません。
+
+エイリアス `A` に作用する割り当てについて、パーサーは次を構築します。
+
+```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))
+```
+
+影響を受けるすべてのエントリは、同じメモリ射影を共有します。入力の MemMerge は部分的です。null のデフォルトは、列挙されていないエイリアスを**覆わない**ことを意味します。出力の集約は、関係のないエイリアスについて前のメモリを保持します。空の構造体は空の部分入力を持ち、メモリ全体を変更しません。
+
+メモリ型は、エイリアスと、そのスライスに格納される値の型を対にするようになります。New を通るエイリアス問い合わせは、流入する内容とフィールドの初期値（整数ゼロ、浮動小数点ゼロ、null）を組み合わせます。問い合わせは集約と割り当てをたどり、キャッシュされた Phi の型で止まり、最適化器の依存関係を記録します。MemPhi は、自分の1つのエイリアスについてこれらの値の型を合流します。エイリアスごとの New 射影も、新しい束の領域も不要です。
+
+New 自身のポインタを使う Load は、初期化された値に畳み込めます。別の New から来たポインタは、割り当てを迂回してそのメモリ入力へ進めます。単にノードが異なるだけでは不十分です。Phi やキャストが、依然として割り当てられたオブジェクトを表す可能性があるためです。配列の長さは後続の Store で設定し、本体は New がゼロ化します。配列アクセスは境界チェックの代理として、既存の制御入力を保持します。
+
+両スケジューラは、MemMerge を通してエイリアスをたどり、New のメモリへの作用を見つけます。MemMerge 自体はメモリを上書きしませんが、割り当て前の読み出しと、既存オブジェクトへの後続の書き込みの順序を隠してはいけません。
+
+## 新しいアドレス計算
+
+配列では添字でアクセスするためのアドレス計算が必要なので、Load と Store にオフセットを計算する方法が必要です。以前の Load と Store は構造体だけを対象にし、内部にフィールド名を持っていました。つまり暗黙のアドレス指定はフィールド名によるもの（文字列検索のようなもの）でした。この章で新たに構造体の*配置*を作り、すべての構造体のフィールドのオフセットを計算します。
+
+Load と Store はフィールド名の代わりに `off` を取るようになり、フィールド名はデバッグ用にだけ含めます。
+
+```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;
+}
+```
+
+配列の `off` は、通常の配列計算の手順で計算します。
+
+`off = base + (idx << scale)`
+
+配列については要素型からベースと添字を計算し、パーサーがオフセットを構築するのに使います。構造体については配置を使います。
+
+```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));
+}
+```
+
+## 構造体の配置
+
+この章で新しく導入する構造体の*配置*は、特定のフィールドを格納するメモリブロック内の固定オフセットです。`TypeStruct` でオフセットを計算し、キャッシュします。すべてのフィールド型は `log_size` を持つようになります。フィールドはサイズ順に詰め込み、アラインメント用のパディングを入れ、構造体全体も8の倍数までパディングします。したがって実際のフィールドオフセットとフィールドの宣言順序は*無関係*です。大きなフィールドを低い位置に詰め、小さなフィールドをその次に詰めます。
+
+```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
+```
+
+フィールドのサイズは、おそらく `TypeInteger` を除けばほぼ明らかです。浮動小数点は32ビットか64ビットです。ポインタは `TypeMemPtr` で4バイトに設定しており、後により広いポインタ範囲をサポートするため変更できます。`TypeInteger` は、ユーザーに見える固定された整数範囲の集合についてだけ、有効な `log_size` フィールドを持ちます。Simple では `compute` の呼び出しでほかの範囲も可能ですが、フィールドの基本型には決して現れません。
+
+`struct S { i16 x; }`
+
+ここでは `x` のオフセットは 0、サイズは2バイトで、`S` はサイズ 8 までパディングされます。
+
+`S s = new S; s.x = 3;`
+
+同じ `x` フィールドが今度は 0 または 3 を保持するため、`x` の `TypeInteger` は範囲 `[0-3]` になります。これはたった2ビットで表せますが、フィールドサイズの計算には使いません。
+
+## 単純なアドレス計算のピープホール最適化
+
+0 だけの左シフトは恒等操作です。`(x<<0)` は `x` になります。
+
+定数加算に対する左シフトは分配して、さらに定数畳み込みを可能にします。`(x + c) << i` は `(x << i) + (c << i)` になります。
+
+つまり IR は次のようになります。
+
+`x[i]` は `16/*base*/ + (i << 3/*scale*/)` となり、`Load(mem,x,Add(Shl(i,3),16))` になります。
+
+`x[i+1]` は `16/*base*/ + ((i+1) << 3/*scale*/)` となり、`Load(mem,x,Add(Shl(i,3),24))` になります。
+
+`idx+1` の `+1` がベースの計算に畳み込まれる点に注目してください。
+
+また、この形は X86 のアドレッシングモードにぴったりです。
+
+## 考察
+
+テストケースには、単純な移動和とエラトステネスの篩が含まれます。
+
+```java
+int i=0;
+while( i < ary# ) {
+ ary[i] = i;
+ i = i+1;
+}
+```
+
+ここでは `i++` 演算子と `for` ループがないことが、はっきり見えます。別の構文を想像できます。
+
+```java
+for( int i=0; i < ary#; i++ )
+ ary[i] = i;
+```
+
+これは既存のパーサーの上の糖衣構文だけで実現でき、配列をループする構文をずっと明快にできます。ここには多くの選択肢があり、別の章で集中的に扱うべき話題です。
diff --git a/docs/chapter15/README.md b/docs/chapter15/README.md
new file mode 100644
index 00000000..1ce5badf
--- /dev/null
+++ b/docs/chapter15/README.md
@@ -0,0 +1,262 @@
+# Chapter 15: Arrays
+
+English | [日本語](README.ja.md)
+
+[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!
generated by cgit v1.2.3 (git 2.25.1) at 2026-10-15 12:35:26 +0000