From 4369fd94247acf5fef5ebff0ac644671bf165e42 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 12 Sep 2024 11:13:31 -0700 Subject: Chapter 15: Arrays MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: XmiliaH Co-authored-by: Thalia Archibald 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 Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- README.ja.md | 2 +- README.md | 2 +- chapter14.iml | 28 -- docs/chapter15/15-grammar.ja.md | 135 +++++++ docs/chapter15/15-grammar.md | 131 +++++++ docs/chapter15/Makefile | 12 + docs/chapter15/README.ja.md | 188 ++++++++++ docs/chapter15/README.md | 262 +++++++++++++ .../com/seaofnodes/simple/GlobalCodeMotion.java | 46 +-- src/main/java/com/seaofnodes/simple/Parser.java | 241 ++++++++---- src/main/java/com/seaofnodes/simple/Utils.java | 11 +- .../java/com/seaofnodes/simple/node/AddNode.java | 5 +- .../java/com/seaofnodes/simple/node/AndNode.java | 1 - .../java/com/seaofnodes/simple/node/BoolNode.java | 22 +- .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 16 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 2 - .../java/com/seaofnodes/simple/node/CProjNode.java | 17 +- .../com/seaofnodes/simple/node/ConstantNode.java | 1 - .../java/com/seaofnodes/simple/node/DivNode.java | 2 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 127 +++++-- .../com/seaofnodes/simple/node/MemMergeNode.java | 36 +- .../java/com/seaofnodes/simple/node/MemOpNode.java | 23 +- .../com/seaofnodes/simple/node/MemPhiNode.java | 12 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 4 +- .../java/com/seaofnodes/simple/node/NewNode.java | 37 +- src/main/java/com/seaofnodes/simple/node/Node.java | 16 +- .../java/com/seaofnodes/simple/node/OrNode.java | 1 - .../java/com/seaofnodes/simple/node/PhiNode.java | 10 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 5 +- .../com/seaofnodes/simple/node/RegionNode.java | 59 ++- .../java/com/seaofnodes/simple/node/SarNode.java | 16 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 82 ++-- .../java/com/seaofnodes/simple/node/ShlNode.java | 18 +- .../java/com/seaofnodes/simple/node/ShrNode.java | 17 +- .../java/com/seaofnodes/simple/node/StartNode.java | 4 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 26 +- .../java/com/seaofnodes/simple/node/SubNode.java | 7 +- .../java/com/seaofnodes/simple/node/XorNode.java | 1 - .../simple/print/SimpleGraphAdapter.java | 9 +- .../simple/print/SimpleGraphObserver.java | 2 +- .../java/com/seaofnodes/simple/type/Field.java | 24 +- src/main/java/com/seaofnodes/simple/type/Type.java | 10 + .../java/com/seaofnodes/simple/type/TypeFloat.java | 6 + .../com/seaofnodes/simple/type/TypeInteger.java | 17 +- .../java/com/seaofnodes/simple/type/TypeMem.java | 36 +- .../com/seaofnodes/simple/type/TypeMemPtr.java | 15 +- .../com/seaofnodes/simple/type/TypeStruct.java | 114 ++++-- .../java/com/seaofnodes/simple/type/TypeTuple.java | 9 +- .../java/com/seaofnodes/simple/BrainFuckTest.java | 80 ++++ .../java/com/seaofnodes/simple/Chapter06Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 28 +- .../java/com/seaofnodes/simple/Chapter12Test.java | 29 +- .../java/com/seaofnodes/simple/Chapter13Test.java | 37 +- .../com/seaofnodes/simple/Chapter14FloatTest.java | 11 - .../java/com/seaofnodes/simple/Chapter14Test.java | 127 +------ .../java/com/seaofnodes/simple/Chapter15Test.java | 416 +++++++++++++++++++++ src/test/java/com/seaofnodes/simple/TypeTest.java | 30 +- .../com/seaofnodes/simple/evaluator/Evaluator.java | 184 ++++++++- .../com/seaofnodes/simple/evaluator/Scheduler.java | 71 ++-- .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 6 +- 60 files changed, 2236 insertions(+), 652 deletions(-) delete mode 100644 chapter14.iml create mode 100644 docs/chapter15/15-grammar.ja.md create mode 100644 docs/chapter15/15-grammar.md create mode 100644 docs/chapter15/Makefile create mode 100644 docs/chapter15/README.ja.md create mode 100644 docs/chapter15/README.md create mode 100644 src/test/java/com/seaofnodes/simple/BrainFuckTest.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter15Test.java diff --git a/README.ja.md b/README.ja.md index d4ad30b1..3347ece3 100644 --- a/README.ja.md +++ b/README.ja.md @@ -51,7 +51,7 @@ Simple 言語のスタイルは、C または Java のサブセットに倣っ * [第12章](docs/chapter12/README.ja.md)：参照フィールド、前方参照、再帰的な構造体。 * [第13章](docs/chapter13/README.ja.md)：大域的コード移動とスケジューリング。 * [第14章](docs/chapter14/README.ja.md)：数値型。浮動小数点数、狭い整数型、範囲、`f32` への丸め。 -* 第15章：静的な長さを持つ一次元配列型。配列のロードとストア。 +* [第15章](docs/chapter15/README.ja.md)：静的な長さを持つ一次元配列型。配列のロードとストア。 * 第16章：コンストラクタ。 * 第17a章：束縛の可変性、参照の権限、深い読み取り専用ビュー。 * 第17b章：糖衣構文。`var`、`val`、`x+=y`、`for(init; test; next) body`。 diff --git a/README.md b/README.md index 88954ae2..2fc93835 100644 --- a/README.md +++ b/README.md @@ -60,7 +60,7 @@ The Simple language is styled after a subset of C or Java. * [Chapter 12](docs/chapter12/README.md): Reference fields, forward references and recursive structs. * [Chapter 13](docs/chapter13/README.md): Global Code Motion - Scheduling. * [Chapter 14](docs/chapter14/README.md): Numeric types: floats, narrow integers, ranges and rounding to `f32`. -* Chapter 15: One dimensional static length array type, with array loads and stores. +* [Chapter 15](docs/chapter15/README.md): One dimensional static length array type, with array loads and stores. * Chapter 16: Constructors * Chapter 17a: Binding mutability, reference permissions, and deep read-only views. * Chapter 17b: Syntax sugar: `var`, `val`, `x+=y`, `for(init; test; next) body` diff --git a/chapter14.iml b/chapter14.iml deleted file mode 100644 index 4c719b6d..00000000 --- a/chapter14.iml +++ /dev/null @@ -1,28 +0,0 @@ - - - - - - - - - - - - - - - - - - - - - - - - - - - - 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! diff --git a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 78a0dcde..d17ec3b6 100644 --- a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -93,11 +93,12 @@ public abstract class GlobalCodeMotion { private static void _schedEarly(Node n, BitSet visit) { if( n==null || visit.get(n._nid) ) return; // Been there, done that + assert !(n instanceof CFGNode); visit.set(n._nid); // Schedule inputs first, except Phis: following their backedges would // enter a data cycle before its control has been scheduled. for( Node def : n._inputs ) - if( def!=null && !(def instanceof PhiNode) ) + if( def!=null ) _schedEarly(def,visit); // An existing edge 0 already supplies control (or a Phi/Proj binding). if( n.in(0)==null ) { @@ -122,7 +123,7 @@ public abstract class GlobalCodeMotion { // Copy the best placement choice into the control slot for( int i=0; i st._alias==load._alias; - case MemPhiNode phi -> phi._alias==load._alias; - case BulkMemPhiNode phi -> !phi.isSplit(load._alias); - default -> false; - }; + // An allocation may consume a load's memory through a partial aggregate. + private static void wakeLoads(Node def, CFGNode[] late, WorkList work, BitSet visit) { + if( visit.get(def._nid) ) return; + visit.set(def._nid); + for( Node out : def._outputs ) + if( out instanceof LoadNode ld && late[ld._nid]==null ) work.push(ld); + if( def instanceof MemMergeNode ) + for( int i=1; imem uses, looking for Stores causing an anti-dep - for( Node mem : load.mem()._outputs ) { - if( !antiUse(load,mem) ) continue; + for( Node mem : load.antiDeps() ) { switch( mem ) { case StoreNode st: assert late[st._nid]!=null; lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); break; + case NewNode st: + assert late[st._nid]!=null; + lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); + break; case PhiNode phi: // Repeat anti-dep for matching Phi inputs. // No anti-dep edges but may raise the LCA. diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 0602d290..81291326 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -31,14 +31,13 @@ public class Parser { */ public static StartNode START; - public static ConstantNode ZERO; - public static XCtrlNode XCTRL; + public static ConstantNode ZERO; // Very common node, cached here + public static XCtrlNode XCTRL; // Very common node, cached here - public StopNode STOP; + // Next available memory alias number + static int ALIAS; - // Field identities are independent of the memory graph and Start's tuple. - private final HashMap _aliases = new HashMap<>(); - private int _alias = 2; + public StopNode STOP; // Debugger Printing. public static boolean SCHEDULED; // True if debug printer can use schedule info @@ -101,7 +100,9 @@ public class Parser { ScopeNode _continueScope; ScopeNode _breakScope; - // Mapping from a type name to a Type. + // Mapping from a type name to a Type. The string name matches + // `type.str()` call. No TypeMemPtrs are in here, because Simple does not + // have C-style '*ptr' references. public static HashMap TYPES = new HashMap<>(); public Parser(String source, TypeInteger arg) { @@ -129,8 +130,9 @@ public class Parser { _continueScope = _breakScope = null; START = new StartNode(new Type[]{ Type.CONTROL, TypeMem.BOT, arg }); STOP = new StopNode(source); - ZERO = new ConstantNode(TypeInteger.constant(0)).peephole().keep(); + ZERO = con(0).keep(); XCTRL= new XCtrlNode().peephole().keep(); + ALIAS = 2; // alias 0 for the control, 1 for memory } public Parser(String source) { @@ -157,8 +159,9 @@ public class Parser { _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 2, ScopeNode.ARG0).peephole()); _scope.define("$mem", TypeMem.BOT, new ProjNode(START, 1, "$mem").peephole()); parseBlock(); + if( ctrl()._type==Type.CONTROL ) - STOP.addReturn(new ReturnNode(ctrl(), new ConstantNode(TypeInteger.constant(0)).peephole(), _scope).peephole()); + STOP.addReturn(new ReturnNode(ctrl(), ZERO, _scope).peephole()); _scope.pop(); _xScopes.pop(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); @@ -218,7 +221,7 @@ public class Parser { Type t = type(); if( t==null ) throw errorSyntax("Requires a field type, found '"+_lexer.getAnyNextToken()+"'"); - return require(Field.make(requireId().intern(),t),";"); + return require(Field.make(requireId().intern(),ALIAS++,t),";"); } /** @@ -232,7 +235,9 @@ public class Parser { if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope"); String typeName = requireId(); Type t = TYPES.get(typeName); - if( t!=null && !(t instanceof TypeStruct ts && ts._fields==null) ) throw errorSyntax("struct '" + typeName + "' cannot be redefined"); + if( t!=null && !(t instanceof TypeMemPtr tmp && tmp._obj._fields==null) ) + throw errorSyntax("struct '" + typeName + "' cannot be redefined"); + // Parse a collection of fields ArrayList fields = new ArrayList<>(); require("{"); while (!peek('}') && !_lexer.isEOF()) { @@ -242,10 +247,8 @@ public class Parser { } require("}"); // Build and install the TypeStruct - TypeStruct ts = TypeStruct.make(typeName, fields); - TYPES.put(typeName, ts); // Insert the struct name in the collection of all struct names - _aliases.put(typeName,_alias); - _alias += ts._fields.length; + TypeStruct ts = TypeStruct.make(typeName, fields.toArray(new Field[fields.size()])); + TYPES.put(typeName, TypeMemPtr.make(ts)); return parseStatement(); } @@ -337,7 +340,7 @@ public class Parser { ctrl(XCTRL); // Kill current scope // Prune nested lexical scopes that have depth > than the loop head // We use _breakScope as a proxy for the loop head scope to obtain the depth - while( cur._scopes.size() > _breakScope._scopes.size() ) + while( cur._idxs.size() > _breakScope._idxs.size() ) cur.pop(); // If this is a continue then first time the target is null // So we just use the pruned current scope as the base for the @@ -345,7 +348,7 @@ public class Parser { if (toScope == null) return cur; // toScope is either the break scope, or a scope that was created here - assert toScope._scopes.size() <= _breakScope._scopes.size(); + assert toScope._idxs.size() <= _breakScope._idxs.size(); toScope.ctrl(toScope.mergeScopes(cur)); return toScope; } @@ -469,33 +472,69 @@ public class Parser { // Auto-deepen forward ref types Type e = expr._type; if( e instanceof TypeMemPtr tmp && tmp._obj._fields==null ) - e = tmp.make_from((TypeStruct)TYPES.get(tmp._obj._name)); + e = TYPES.get(tmp._obj._name); // Type is sane if( !e.isa(t) ) throw error("Type " + e.str() + " is not of declared type " + t.str()); return _scope.update(name,expr); } - // Parse a "type id" and return "type" (and re-parse "id" in caller) or - // return null. + // Parse and return a type or null. Valid types always are followed by an + // 'id' which the caller must parse. This lets us distinguish forward ref + // types (which ARE valid here) from local vars in an (optional) forward + // ref type position. private Type type() { - int old = _lexer._position; + int old1 = _lexer._position; String tname = _lexer.matchId(); if( tname==null ) return null; - boolean nullable = match("?"); - Type t = TYPES.get(tname); - // Assume a forward-reference type - if( t == null ) { - int old2 = _lexer._position; - String id = _lexer.matchId(); - if( id==null ) { - _lexer._position = old; - return null; + // Convert the type name to a type. + Type t0 = TYPES.get(tname); + Type t1 = t0 == null ? TypeMemPtr.make(TypeStruct.make(tname)) : t0; // Null: assume a forward ref type + // Nest arrays and '?' as needed + while( true ) { + assert !(t1 instanceof TypeStruct); + if( match("?") ) { + if( !(t1 instanceof TypeMemPtr tmp) ) + throw error("Type "+t0+" cannot be null"); + if( tmp._nil ) throw error("Type "+t1+" already allows null"); + t1 = TypeMemPtr.make(tmp._obj,true); + continue; + } + if( match("[]") ) { + t1 = typeAry(t1); + continue; } - TYPES.put(tname,t = TypeStruct.make(tname)); - _lexer._position = old2; // Reparse ID in caller + break; } - return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,nullable) : t; + + // Check no forward ref + if( t0 != null ) return t1; + // Check valid forward ref, after parsing all the type extra bits. + // Cannot check earlier, because cannot find required 'id' until after "[]?" syntax + int old2 = _lexer._position; + String id = _lexer.matchId(); + _lexer._position = old2; // Reset lexer to reparse + if( id==null ) { + _lexer._position = old1; // Reset lexer to reparse + return null; // Not a type + } + // Yes a forward ref, so declare it + TYPES.put(tname,t1); + return t1; + } + + // Make an array type of t + private TypeMemPtr typeAry( Type t ) { + if( t instanceof TypeMemPtr tmp && !tmp._nil ) + throw error("Arrays of reference types must always be nullable"); + String tname = t.str()+"[]"; + Type ta = TYPES.get(tname); + if( ta != null ) return (TypeMemPtr)ta; + // Need make an array type. + TypeStruct ts = TypeStruct.makeAry(TypeInteger.BOT,ALIAS++,t,ALIAS++); + TypeMemPtr tary = TypeMemPtr.make(ts); + TYPES.put(tname,tary); + return tary; } @@ -643,22 +682,36 @@ public class Parser { * Parse a primary expression: * * 
-     *     primaryExpr : integerLiteral | Identifier | true | false | null | new Identifier | '(' expression ')'
+     *     primaryExpr : integerLiteral | Identifier | true | false | null | new Type | '(' expression ')'
      *
* @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral(); if( match("(") ) return require(parseExpression(), ")"); - if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole(); + if( matchx("true" ) ) return con(1); if( matchx("false") ) return ZERO; if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole(); if( matchx("new") ) { - String structName = requireId(); - Type t = TYPES.get(structName); - if( !(t instanceof TypeStruct obj) || obj._fields==null ) - throw error("Unknown struct type '" + structName + "'"); - return newStruct(obj); + Type t = type(); + if( t==null ) throw error("Expected a type"); + if( match("[") ) { + Node len = parseExpression().keep(); + if( !(len._type instanceof TypeInteger) ) + throw error("Cannot allocate an array with length "+len._type); + require("]"); + TypeMemPtr tmp = typeAry(t); + return newArray(tmp._obj,len); + } + if( t instanceof TypeMemPtr tmp ) { + TypeStruct obj = tmp._obj; + if( obj._fields==null ) + throw error("Unknown struct type '" + obj._name + "'"); + if( obj.isAry() ) + throw Utils.TODO(); // Missing array length + return newStruct(obj,con(obj.offset(obj._fields.length))); + } + throw error("Cannot allocate a "+t.str()); } String name = _lexer.matchId(); if( name == null) throw errorSyntax("an identifier or expression"); @@ -668,25 +721,46 @@ public class Parser { } /** - * Return a NewNode but also generate instructions to initialize it. + * Return a NewNode with pre-zeroed memory */ - private Node newStruct(TypeStruct obj) { - Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep(); - int alias = _aliases.get(obj._name); - for( Field field : obj._fields ) { - store(field._fname,alias,field._type,n,new ConstantNode(field._type.makeInit()).peephole(),true); - alias++; - } - return n.unkeep(); + private Node newStruct(TypeStruct obj, Node size) { + Node prior = mem().keep(); + // No default: only the aliases initialized by this allocation. + MemMergeNode input = new MemMergeNode(null); + for( Field f : obj._fields ) + input.alias(f._alias,prior); + Node nnn = new NewNode(TypeMemPtr.make(obj),ctrl(),input.peephole(),size).peephole().keep(); + Node ptr = new ProjNode(nnn,0,obj._name).peephole().keep(); + Node out = new ProjNode(nnn,1,"$mem").peephole().keep(); + MemMergeNode after = new MemMergeNode(prior); + for( Field f : obj._fields ) + after.alias(f._alias,out); + mem(after.peephole()); + out.unkeep(); + nnn.unkeep(); + if( prior.unkeep().isUnused() ) prior.kill(); + return ptr.unkeep(); + } + + private Node newArray(TypeStruct ary, Node len) { + int base = ary.aryBase (); + int scale= ary.aryScale(); + Node size = new AddNode(con(base),new ShlNode(len,con(scale)).peephole()).peephole(); + Node ptr = newStruct(ary,size); + int alias = ary._fields[0]._alias; // Length alias + store("#",alias,TypeInteger.BOT,ptr,con(ary.offset(0)),len.unkeep(),true,null); + return ptr; } // Memory is one hidden SSA variable, including across branches and loops. private Node mem() { return _scope.lookup("$mem"); } private Node mem(Node n) { return _scope.update("$mem",n); } - private void store(String name, int alias, Type glb, Node ptr, Node val, boolean init) { + private void store(String name, int alias, Type glb, Node ptr, Node off, Node val, boolean init, Node ctrl) { Node prior = mem().keep(); - Node st = new StoreNode(name,alias,glb,ctrl(),prior,ptr,val,init).peephole(); + Node st = new StoreNode(name,alias,glb,prior,ptr,off,val,init); + st.setDef(0,ctrl); + st = st.peephole(); mem(new MemMergeNode(prior,alias,st).peephole()); if( prior.unkeep().isUnused() ) prior.kill(); } @@ -697,39 +771,66 @@ public class Parser { * * 
      *     expr ('.' IDENTIFIER)* [ = expr ]
+     *     expr #
+     *     expr ('[' expr ']')* = [ = expr ]
      *
*/ private Node parsePostfix(Node expr) { - if( !match(".") ) return expr; + String name = null; + if( match(".") ) name = requireId().intern(); + else if( match("#") ) name = "#"; + else if( match("[") ) name = "[]"; + else return expr; // No postfix + // Sanity check expr for being a reference if( !(expr._type instanceof TypeMemPtr ptr) ) - throw error("Expected struct reference but got " + expr._type.str()); - - String name = requireId().intern(); - if( expr._type == TypeMemPtr.TOP ) throw error("Accessing field '" + name + "' from null"); + throw error("Expected reference but got " + expr._type.str()); + if( ptr == TypeMemPtr.TOP ) throw error("Accessing field '" + name + "' from null"); if( ptr._obj == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); - TypeStruct base = (TypeStruct)TYPES.get(ptr._obj._name); - int idx = base==null ? -1 : base.find(name); - if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); - int alias = _aliases.get(ptr._obj._name)+idx; + // Sanity check field name for existing + TypeMemPtr tmp = (TypeMemPtr)TYPES.get(ptr._obj._name); + if( tmp == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + TypeStruct base = tmp._obj; + int fidx = base.find(name); + if( fidx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + expr.keep(); + + // 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(),"]"); + Node shl = new ShlNode(idx,con(base.aryScale())).peephole(); + off = new AddNode(con(base.aryBase()),shl).peephole(); + } else { // Else normal struct field + // Hardwired field offset + off = con(base.offset(fidx)); + } if( match("=") ) { // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment if( peek('=') ) _lexer._position--; else { + off.keep(); Node val = parseExpression(); - Type glb = base._fields[idx]._type; // Auto-truncate when storing to narrow fields - val = zsMask(val,glb); - store(name,alias,glb,expr,val,false); - return expr; // "obj.a = expr" returns the expression while updating memory + val = zsMask(val,f._type).keep(); + // Array control stands in for the future bounds check. + store(name,f._alias,f._type,expr.unkeep(),off.unkeep(),val,false,base.isAry() ? ctrl() : null); + return val.unkeep(); // "obj.a = expr" returns the expression while updating memory } } - Type declaredType = base._fields[idx]._type; - return parsePostfix(new LoadNode(name, alias, declaredType.glb(), mem(), expr).peephole()); + Node load = new LoadNode(name, f._alias, f._type.glb(), mem(), expr.unkeep(), off); + // Arrays include control, as a proxy for a safety range check + // Structs don't need this; they only need a NPE check which is + // done via the type system. + if( base.isAry() ) load.setDef(0,ctrl()); + return parsePostfix(load.peephole()); } + // zero/sign extend. "i" is limited to either classic unsigned (min==0) or // classic signed (min=minus-power-of-2); max=power-of-2-minus-1. private Node zsMask(Node val, Type t ) { @@ -742,10 +843,10 @@ public class Parser { return new RoundF32Node(val).peephole(); } if( t0._min==0 ) // Unsigned - return new AndNode(val,new ConstantNode(TypeInteger.constant(t0._max)).peephole()).peephole(); + return new AndNode(val,con(t0._max)).peephole(); // Signed extension int shift = Long.numberOfLeadingZeros(t0._max)-1; - Node shf = new ConstantNode(TypeInteger.constant(shift)).peephole(); + Node shf = con(shift); if( shf._type==TypeInteger.ZERO ) return val; return new SarNode(new ShlNode(val,shf.keep()).peephole(),shf.unkeep()).peephole(); @@ -764,6 +865,10 @@ public class Parser { return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole(); } + public static Node con( long con ) { + return new ConstantNode(TypeInteger.constant(con)).peephole(); + } + ////////////////////////////////// // Utilities for lexical analysis diff --git a/src/main/java/com/seaofnodes/simple/Utils.java b/src/main/java/com/seaofnodes/simple/Utils.java index f3ac25b1..1346c3ea 100644 --- a/src/main/java/com/seaofnodes/simple/Utils.java +++ b/src/main/java/com/seaofnodes/simple/Utils.java @@ -13,14 +13,9 @@ public class Utils { * @param i element to be removed * @return element removed */ - public static E del(ArrayList array, int i) { - if ( i >= 0 && i < array.size() ) { - E tmp = array.get(i); - E last = array.removeLast(); - if (i < array.size()) array.set(i, last); - return tmp; - } - return null; + public static void del(ArrayList array, int i) { + E last = array.removeLast(); + if (i < array.size()) array.set(i, last); } /** diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 0046bd03..5875a73d 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -15,7 +15,8 @@ public class AddNode extends Node { @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; - if( t1.isHigh() || t2.isHigh() ) return TypeInteger.TOP; + if( t1.isHigh() || t2.isHigh() ) + return TypeInteger.TOP; if( t1 instanceof TypeInteger i1 && t2 instanceof TypeInteger i2 ) { if (i1.isConstant() && i2.isConstant()) @@ -29,7 +30,7 @@ public class AddNode extends Node { } private static boolean overflow( long x, long y ) { - if( (x ^ y ) < 0 ) return false; // unequal signs, never overflow + if( (x ^ y ) < 0 ) return false; // unequal signs, never overflow return (x ^ (x + y)) < 0; // sum has unequal signs, so overflow } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/AndNode.java b/src/main/java/com/seaofnodes/simple/node/AndNode.java index e2729e60..0844f2ea 100644 --- a/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -14,7 +14,6 @@ public class AndNode extends Node { @Override public Type compute() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; if( in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 8a25e8d9..6efde623 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -32,9 +32,6 @@ abstract public class BoolNode extends Node { Type t2 = in(2)._type; if( t1.isHigh() || t2.isHigh() ) return BOOL.dual(); - // Compare of same - if( in(1)==in(2) ) - return doOp(ZERO,ZERO); if( t1 instanceof TypeInteger i1 && t2 instanceof TypeInteger i2 ) return doOp(i1,i2); @@ -50,6 +47,10 @@ abstract public class BoolNode extends Node { @Override public Node idealize() { + // Compare of same + if( in(1)==in(2) ) + return new ConstantNode(doOp(ZERO,ZERO)); + // Equals pushes constant to the right; 5==X becomes X==5. if( this instanceof EQ ) { if( !(in(2) instanceof ConstantNode) ) { @@ -61,11 +62,14 @@ abstract public class BoolNode extends Node { // Equals X==0 becomes a !X if( (in(2)._type == ZERO || in(2)._type == TypeMemPtr.NULLPTR) ) return new NotNode(in(1)); - // Equals bool == 1 becomes bool - if( in(2)._type == TRUE && in(1)._type == BOOL ) - return in(1); } + // Do we have ((phi cons) cmp con) ? + // Do we have ((phi cons) cmp (phi cons)) ? + // Push the compare up through the phi: (phi con0 cmp con, con1 cmp con...) + Node phicon = AddNode.phiCon(this,this instanceof EQ); + if( phicon!=null ) return phicon; + return null; } @@ -103,8 +107,8 @@ abstract public class BoolNode extends Node { Node copyF() { return new LEF(null,null); } } - public static class EQF extends EQ { public EQF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQF(lhs,rhs); } } - public static class LTF extends LT { public LTF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs < rhs; } Node copy(Node lhs, Node rhs) { return new LTF(lhs,rhs); } } - public static class LEF extends LE { public LEF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LEF(lhs,rhs); } } + public static class EQF extends EQ { public EQF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs == rhs; } } + public static class LTF extends LT { public LTF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs < rhs; } } + public static class LEF extends LE { public LEF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs <= rhs; } } } diff --git a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java index 8d512f21..84f97189 100644 --- a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -87,7 +87,7 @@ public class BulkMemPhiNode extends PhiNode { // True if the MemMerge has no precise slice still covered by this Phi. private boolean canPeek(MemMergeNode mmm) { - return missingAlias(mmm,false)==0; + return mmm.in(1)!=null && missingAlias(mmm)==0; } // Return an alias required by an input but still covered by this Phi, or 0. @@ -95,7 +95,7 @@ public class BulkMemPhiNode extends PhiNode { return switch(n) { case ProjNode proj -> 0; case ConstantNode con -> 0; - case MemMergeNode mmm -> missingAlias(mmm,false); + case MemMergeNode mmm -> missingAlias(mmm); case MemOpNode mem -> unsplit(mem._alias); case BulkMemPhiNode bulk -> missingAlias(bulk); default -> throw new AssertionError("Unexpected memory input "+n); @@ -111,7 +111,7 @@ public class BulkMemPhiNode extends PhiNode { use.addDepForwards(this); return switch(use) { case ScopeNode scope -> 0; - case MemMergeNode mmm -> missingAlias(mmm,true); + case MemMergeNode mmm -> missingAlias(mmm); case BulkMemPhiNode bulk -> missingAlias(bulk); case MemOpNode mem -> unsplit(mem._alias); case MemPhiNode phi -> unsplit(phi._alias); @@ -139,14 +139,14 @@ public class BulkMemPhiNode extends PhiNode { return 0; } - // First precise MemMerge slice still covered by this Phi. When inspecting - // a user, ignore slots which point back to this Phi. - private int missingAlias(MemMergeNode mmm, boolean user) { + // Every explicit slot requests that alias, including a partial allocation + // input whose slot still points to this bulk Phi. + private int missingAlias(MemMergeNode mmm) { for( int alias=2; alias _print1(ExprPrinter p) { return p.p(".").p(_name); } @Override public Type compute() { - return _declaredType; + Type t = MemMergeNode.contents(mem(),_alias,this); + // No constant folding if the pointer still needs a null check. + return err()==null ? _declaredType.join(t) : _declaredType; } @Override @@ -57,15 +63,57 @@ public class LoadNode extends MemOpNode { setDef(1,IterPeeps.add(merge.alias(_alias))); return this; } - + Node ptr = ptr(); // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && - ptr() == st.ptr() && _alias==st._alias ) { // Must check same object + _alias==st._alias && ptr == st.ptr() && off() == st.off() ) { // Must check same object assert _name.equals(st._name); // Equiv class aliasing is perfect return st.val(); } + // Simple Load-after-New on same address. + if( mem() instanceof ProjNode p && p.in(0) instanceof NewNode nnn && + ptr == nnn.proj(0) ) // Must check same object + return new ConstantNode(_declaredType.makeInit()); + + // Load-after-Store on same address, but bypassing provably unrelated + // stores. This is a more complex superset of the above two peeps. + // "Provably unrelated" is really weak. + Node mem = mem(); + outer: + while( true ) { + mem.addDep(this); + switch( mem ) { + case MemMergeNode merge: + mem = merge.alias(_alias); + break; + case StoreNode st: + if( _alias==st._alias && ptr == st.ptr() && off() == st.off() ) + return st.val(); // Proved equal + // Can we prove unequal? Offsets do not overlap? + if( _alias==st._alias && !off()._type.join(st.off()._type).isHigh() && // Offsets overlap + !neverAlias(ptr,st.ptr()) ) // And might alias + break outer; // Cannot tell, stop trying + // Pointers cannot overlap + mem = st.mem(); // Proved never equal + break; + case PhiNode phi: + break outer; // Assume related + case ProjNode mproj: + if( mproj.in(0) instanceof NewNode nnn1 ) { + if( ptr instanceof ProjNode pproj && pproj.in(0) == mproj.in(0) ) + return new ConstantNode(_declaredType.makeInit()); // Load from a New + if( !(ptr instanceof ProjNode pproj && pproj.in(0) instanceof NewNode nnn2) ) + break outer; // Cannot tell, ptr not related to New + mem = nnn1.mem();// Bypass unrelated New + break; + } else break outer; + default: + break outer; + } + } + // Push a Load up through a Phi, as long as it collapses on at least // one arm. If at a Loop, the backedge MUST collapse - else we risk // spinning the same transform around the loop indefinitely. @@ -73,31 +121,66 @@ public class LoadNode extends MemOpNode { // if( pred ) ptr.x = e0; val = pred ? e0 // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; - if( mem() instanceof MemPhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 ) { + if( mem() instanceof MemPhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 && + off() instanceof ConstantNode ) { // Profit on RHS/Loop backedge if( profit(memphi,2) || // Else must not be a loop to count profit on LHS. (!(memphi.region() instanceof LoopNode) && profit(memphi,1)) ) { - if( ptr() instanceof NewNode || !(ptr() instanceof CastNode) ) { - if( !(ptr() instanceof NewNode) ) throw Utils.TODO(); // Validate - - Node ld1 = new LoadNode(_name,_alias,_declaredType,memphi.in(1),ptr()).peephole(); - Node ld2 = new LoadNode(_name,_alias,_declaredType,memphi.in(2),ptr()).peephole(); - return new PhiNode(_name,_type,memphi.region(),ld1,ld2); - } + Node ld1 = ld(1); + Node ld2 = ld(2); + return new PhiNode(_name,_declaredType,memphi.region(),ld1,ld2); } } return null; } + private Node ld( int idx ) { + Node mem = mem(), ptr = ptr(); + LoadNode ld = new LoadNode(_name,_alias,_declaredType,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr,off()); + ld.setDef(0,in(0)); + return ld.peephole(); + } + private static boolean neverAlias( Node ptr1, Node ptr2 ) { + return ptr1.in(0) != ptr2.in(0) && + // Unrelated allocations + ptr1 instanceof ProjNode && ptr1.in(0) instanceof NewNode && + ptr2 instanceof ProjNode && ptr2.in(0) instanceof NewNode; + } + // Profitable if we find a matching Store on this Phi arm. private boolean profit(PhiNode phi, int idx) { Node px = phi.in(idx); - return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr() && _alias==st1._alias; + if( px==null ) return false; + px.addDep(this); + if( px._type instanceof TypeMem mem && mem._t.isHighOrConst() ) return true; + if( px instanceof StoreNode st1 && _alias==st1._alias && ptr()==st1.ptr() && off()==st1.off() ) return true; + return false; + } + + // Memory writers which must follow this read. A packaging node is not a + // write, but can hide New's input, so follow this alias through aggregates. + public ArrayList antiDeps() { + ArrayList deps = new ArrayList<>(); + antiDeps(mem(),deps,new BitSet()); + return deps; } - Node copy(Node mem, Node ptr) { - return new LoadNode(_name,_alias,_declaredType,mem,ptr); + private void antiDeps(Node mem, ArrayList deps, BitSet visit) { + if( visit.get(mem._nid) ) return; + visit.set(mem._nid); + for( Node use : mem._outputs ) { + if( use instanceof MemMergeNode merge ) { + Node slice = _alias 1; _alias = alias; } @@ -18,8 +18,14 @@ public class MemPhiNode extends PhiNode { @Override public Type compute() { assert BulkMemPhiNode.checkMem(this,_alias); - Type t = super.compute(); - return t==Type.TOP || t==TypeMem.TOP ? TypeMem.TOP : TypeMem.make(_alias); + if( !(region() instanceof RegionNode r) ) + return region()._type==Type.XCONTROL ? TypeMem.TOP : _type; + if( r.inProgress() ) return _declaredType; + Type t = Type.TOP; + for( int i=1; i _print1(ExprPrinter p) { return p.p("new ").p(_ptr._obj.str()); } - @Override - public Type compute() { return _ptr; } + public TypeTuple compute() { + return TypeTuple.make(_ptr,TypeMem.BOT); + } @Override public Node idealize() { return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 4ee82187..541c8eb1 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -92,7 +92,7 @@ public abstract class Node extends BaseNode implements OutNode, Cloneable public boolean isUnused() { return nOuts() == 0; } - public CFGNode cfg0() { return (CFGNode)in(0); } + public CFGNode cfg0() { return (CFGNode)in(0); } /** * Change a def into a Node. Keeps the edges correct, by removing @@ -136,11 +136,10 @@ public abstract class Node extends BaseNode implements OutNode, Cloneable Node delDef(int idx) { unlock(); Node old_def = in(idx); - if( old_def != null && // If the old def exists, remove a def->use edge - old_def.delUse(this) ) // If we removed the last use, the old def is now dead + Utils.del(_inputs, idx); + if( old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def old_def.moveDepsToWorklist(); - Utils.del(_inputs, idx); return this; } @@ -489,8 +488,6 @@ public abstract class Node extends BaseNode implements OutNode, Cloneable // ------------------------------------------------------------------------ // - /** Is this Node control-flow-graph related */ - /** Is this Node Memory related */ public boolean isMem() { return false; } @@ -593,12 +590,7 @@ public abstract class Node extends BaseNode implements OutNode, Cloneable E x = pred.apply(this); if( x != null ) return x; for( Node def : _inputs ) if( def != null && (x = def._walk(pred)) != null ) return x; - // Unroll iterator to survive junk CME - for( int i=0; i<_outputs.size(); i++ ) { - Node use = _outputs.get(i); - if( use != null && (x = use._walk(pred)) != null ) - return x; - } + for( Node use : _outputs ) if( use != null && (x = use._walk(pred)) != null ) return x; return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/OrNode.java b/src/main/java/com/seaofnodes/simple/node/OrNode.java index 67585423..1f312d10 100644 --- a/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -14,7 +14,6 @@ public class OrNode extends Node { @Override public Type compute() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; if( in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 309cd8b5..ea5eeb89 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -12,7 +12,7 @@ public class PhiNode extends Node { final String _label; // The Phi type we compute must stay within the domain of the Phi. - // Example Int stays Int, Ptr stays Ptr, Mem stays Mem. + // Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. final Type _declaredType; public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; } @@ -21,7 +21,7 @@ public class PhiNode extends Node { return type instanceof TypeMem ? new BulkMemPhiNode(label,inputs) : new PhiNode(label,type,inputs); } - @Override public String label() { return "Phi_"+_label; } + @Override public String label() { return "Phi_"+MemOpNode.mlabel(_label); } @Override protected ExprPrinter _print1(ExprPrinter p) { @@ -82,9 +82,9 @@ public class PhiNode extends Node { if( in(2)._type == in(2)._type.makeInit() ) nullx = 2; if( nullx != -1 ) { Node val = in(3-nullx); - if( region().idom(this) instanceof IfNode iff && iff.pred().addDep(this)==val ) { + if( r.idom(this) instanceof IfNode iff && iff.pred().addDep(this)==val ) { // Must walk the idom on the null side to make sure we hit False. - CFGNode idom = (CFGNode)region().in(nullx); + CFGNode idom = (CFGNode)r.in(nullx); while( idom.nIns() > 0 && idom.in(0) != iff ) idom = idom.idom(); if( idom instanceof CProjNode proj && proj._idx==1 ) return val; @@ -97,7 +97,7 @@ public class PhiNode extends Node { private boolean same_op() { Node op = in(1); - if( op.isCFG() || op instanceof ConstantNode || op instanceof PhiNode || + if( op instanceof CFGNode || op instanceof ConstantNode || op instanceof PhiNode || op instanceof ProjNode || op instanceof NewNode || op instanceof ScopeNode || op instanceof MemMergeNode ) return false; // A bulk Phi must split its aliases before factoring precise Stores. if( this instanceof BulkMemPhiNode ) return false; diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index e82c69b3..668e20ad 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -21,12 +21,13 @@ public class ProjNode extends Node { _label = label; } - @Override - public String label() { return _label; } + @Override public String label() { return _label; } @Override protected ExprPrinter _print1(ExprPrinter p) { return p.p(_label); } + @Override public CFGNode cfg0() { return in(0).cfg0(); } + @Override public boolean isMultiTail() { return in(0).isMultiHead(); } @Override public boolean isMem() { return _type instanceof TypeMem; } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index cdfd10ad..d4f73ddf 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -67,15 +67,70 @@ public class RegionNode extends CFGNode { // If a CFG diamond with no merging, delete: "if( pred ) {} else {};" if( !hasPhi() && // No Phi users, just a control user - in(1) instanceof ProjNode p1 && - in(2) instanceof ProjNode p2 && + in(1) instanceof CProjNode p1 && + in(2) instanceof CProjNode p2 && p1.addDepForwards(this).in(0)==p2.addDepForwards(this).in(0) && p1.in(0) instanceof IfNode iff ) return iff.ctrl(); + + // Look for direct uses of a guarded expression, and replace with the guard result. + if( !(idom() instanceof StartNode) && // Dead or dying + !(this instanceof LoopNode) ) { + VISIT.clear(); + boolean progress = false; + outer: + for( int i=1; i>i2.value()); - if( i2._min < 0 || i2._max >= 64 ) - return TypeInteger.BOT; - return TypeInteger.make(i1._min>>i2._min,i1._max>>i2._min); + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if( i0.isConstant() && i1.isConstant() ) + return TypeInteger.constant(i0.value()>>i1.value()); + if( i1.isConstant() ) { + int log = (int)i1.value(); + return TypeInteger.make(-1L<<(63-log),(1L<<(63-log))-1); + } } return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index b408eb2f..36a5060b 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -3,10 +3,9 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; -import com.seaofnodes.simple.type.TypeMemPtr; - +import com.seaofnodes.simple.type.*; import java.util.*; /** @@ -23,24 +22,22 @@ public class ScopeNode extends Node { public static final String ARG0 = "arg"; /** - * Names for every input edge + * Map variable names to Scope input edge */ - public final Stack> _scopes; + public final Stack> _idxs; /** - * Tracks declared types for every name + * Map variable names to declared Type */ - public Stack> _types; - + final Stack> _decls; // A new ScopeNode public ScopeNode() { - _scopes = new Stack<>(); - _types = new Stack<>(); + _idxs = new Stack<>(); + _decls= new Stack<>(); _type = Type.BOTTOM; } - @Override public String label() { return "Scope"; } @Override @@ -59,6 +56,20 @@ public class ScopeNode extends Node { return p.unchar(' ').p("]"); } + public Node ctrl() { return in(0); } + + /** + * The ctrl of a ScopeNode is always bound to the currently active + * control node in the graph, via a special name '$ctrl' that is not + * a valid identifier in the language grammar and hence cannot be + * referenced in Simple code. + * + * @param n The node to be bound to '$ctrl' + * + * @return Node that was bound + */ + public Node ctrl(Node n) { return setDef(0,n); } + /** * Recover the names for all variable bindings. * The result is an array of names that is aligned with the @@ -68,7 +79,7 @@ public class ScopeNode extends Node { */ public String[] reverseNames() { String[] names = new String[nIns()]; - for( HashMap syms : _scopes ) + for( HashMap syms : _idxs ) for( String name : syms.keySet() ) names[syms.get(name)] = name; return names; @@ -78,33 +89,34 @@ public class ScopeNode extends Node { @Override public Node idealize() { return null; } - public void push() { _scopes.push(new HashMap<>()); _types.push(new HashMap<>()); } - public void pop() { popN(_scopes.pop().size()); _types.pop(); } + public void push() { _idxs.push(new HashMap<>()); _decls.push(new HashMap<>()); } + public void pop() { popN(_idxs.pop().size()); _decls.pop(); } /** - * Create a new name in the current scope + * Create a new variable name in the current scope */ public Node define( String name, Type declaredType, Node n ) { - HashMap syms = _scopes.lastElement(); - _types.lastElement().put(name,declaredType); + HashMap syms = _idxs.lastElement(); + _decls.lastElement().put(name,declaredType); if( syms.put(name,nIns()) != null ) return null; // Double define return addDef(n); } + /** * Lookup a name in all scopes starting from most deeply nested. * * @param name Name to be looked up * @see #update(String, Node, int) */ - public Node lookup( String name ) { return update(name,null,_scopes.size()-1); } + public Node lookup( String name ) { return update(name,null,_idxs.size()-1); } /** * If the name is present in any scope, then redefine else null * * @param name Name being redefined * @param n The node to bind to the name */ - public Node update( String name, Node n ) { return update(name,n,_scopes.size()-1); } + public Node update( String name, Node n ) { return update(name,n,_idxs.size()-1); } /** * Both recursive lookup and update. *

@@ -118,7 +130,7 @@ public class ScopeNode extends Node { */ private Node update( String name, Node n, int nestingLevel ) { if( nestingLevel<0 ) return null; // Missed in all scopes, not found - var syms = _scopes.get(nestingLevel); // Get the symbol table for nesting level + var syms = _idxs.get(nestingLevel); // Get the symbol table for nesting level var idx = syms.get(name); if( idx == null ) return update(name,n,nestingLevel-1); // Not found in this scope, recursively look in parent scope Node old = in(idx); @@ -136,29 +148,15 @@ public class ScopeNode extends Node { return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer } - // Return declared type + // Return declared type for a variable public Type lookupDeclaredType( String name ) { - for( int i=_types.size(); i>0; i-- ) { - Type t = _types.get(i-1).get(name); + for( int i=_decls.size(); i>0; i-- ) { + Type t = _decls.get(i-1).get(name); if( t != null ) return t; } return null; } - public Node ctrl() { return in(0); } - - /** - * The ctrl of a ScopeNode is always bound to the currently active - * control node in the graph, via a special name '$ctrl' that is not - * a valid identifier in the language grammar and hence cannot be - * referenced in Simple code. - * - * @param n The node to be bound to '$ctrl' - * - * @return Node that was bound - */ - public Node ctrl(Node n) { return setDef(0,n); } - /** * Duplicate a ScopeNode; including all levels, up to Nodes. So this is * neither shallow (would dup the Scope but not the internal HashMap @@ -166,7 +164,7 @@ public class ScopeNode extends Node { * also the program Nodes). *

* If the {@code loop} flag is set, the edges are filled in as the original - * Scope, as a indication of Lazy Phis at loop heads. The goal here is to + * Scope, as an indication of Lazy Phis at loop heads. The goal here is to * not make Phis at loop heads for variables which are never touched in the * loop body. *

@@ -179,10 +177,10 @@ public class ScopeNode extends Node { // 1) duplicate the name bindings of the ScopeNode across all stack levels // 2) Make the new ScopeNode a user of all the nodes bound // 3) Ensure that the order of defs is the same to allow easy merging - for( HashMap syms : _scopes ) - dup._scopes.push(new HashMap<>(syms)); - for( HashMap ts : _types ) - dup._types.push(ts); // Types don't change, just keep stacks aligned + for( HashMap syms : _idxs ) + dup._idxs.push(new HashMap<>(syms)); + for( HashMap ts : _decls ) + dup._decls.push(ts); // Types don't change, just keep stacks aligned dup.addDef(ctrl()); // Control input is just copied for( int i=1; i (x << i) + (c << i) + if( lhs instanceof AddNode add && add.in(2)._type instanceof TypeInteger c && c.isConstant() ) { + long sum = c.value() << shl.value(); + if( Integer.MIN_VALUE <= sum && sum <= Integer.MAX_VALUE ) + return new AddNode( new ShlNode(add.in(1),rhs).peephole(), Parser.con(sum) ); + } + } // TODO: x << 3 << (y ? 1 : 2) ==> x << (y ? 4 : 5) diff --git a/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/src/main/java/com/seaofnodes/simple/node/ShrNode.java index b89f5191..2193965b 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -14,19 +14,10 @@ public class ShrNode extends Node { @Override public Type compute() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; - if (in(1)._type instanceof TypeInteger i1 && - in(2)._type instanceof TypeInteger i2) { - if( i1.isConstant() && i2.isConstant() ) - return TypeInteger.constant(i1.value()>>>i2.value()); - if( i2._min < 0 || i2._max >= 64 ) - return TypeInteger.BOT; - // Zero shifting a negative makes a larger positive - // so get the endpoints correct. - long s1 = i1._min>>>i2._min; - long s2 = i1._max>>>i2._min; - boolean wrap = i1._min < 0 && i1._max >=0; - return TypeInteger.make(wrap ? 0 : Math.min(s1,s2),Math.max(s1,s2)); + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if( i0.isConstant() && i1.isConstant() ) + return TypeInteger.constant(i0.value()>>>i1.value()); } return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index a5d4923f..812305d5 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -16,8 +16,7 @@ public class StartNode extends CFGNode implements MultiNode { _type = _args = TypeTuple.make(args); } - @Override - public String label() { return "Start"; } + @Override public String label() { return "Start"; } @Override protected ExprPrinter _print1(ExprPrinter p) { return p.p(label()); @@ -25,6 +24,7 @@ public class StartNode extends CFGNode implements MultiNode { @Override public boolean isMultiHead() { return true; } @Override public boolean blockHead() { return true; } + @Override public CFGNode cfg0() { return this; } @Override public TypeTuple compute() { return _args; } diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index e9eaaf2e..485491c0 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -16,24 +16,26 @@ public class StoreNode extends MemOpNode { private final boolean _init; // Initializing writes are allowed to write null /** - * @param name The struct field we are assigning to - * @param memSlice The memory alias node - this is updated after a Store - * @param memPtr The ptr to the struct where we will store a value + * @param name The struct field we are assigning to + * @param mem The memory alias node - this is updated after a Store + * @param ptr The ptr to the struct base where we will store a value + * @param off The offset inside the struct base * @param value Value to be stored */ - public StoreNode(String name, int alias, Type glb, Node ctrl, Node memSlice, Node memPtr, Node value, boolean init) { - super(name, alias, glb, ctrl, memSlice, memPtr, value); + public StoreNode(String name, int alias, Type glb, Node mem, Node ptr, Node off, Node value, boolean init) { + super(name, alias, glb, mem, ptr, off, value); _init = init; } + // Debugger label @Override boolean canDrop(MemOpNode other, Node dep) { return super.canDrop(other,dep) && _init==((StoreNode)other)._init; } - @Override public String label() { return "." +_name+"="; } + @Override public String label() { return "st_"+mlabel(); } @Override public boolean isMem() { return true; } - public Node val() { return in(3); } + public Node val() { return in(4); } @Override protected ExprPrinter _print1(ExprPrinter p) { @@ -41,7 +43,10 @@ public class StoreNode extends MemOpNode { } @Override - public Type compute() { return TypeMem.make(_alias); } + public Type compute() { + Type t = val()._type.meet(MemMergeNode.contents(mem(),_alias,this)); + return TypeMem.make(_alias,t); + } @Override public Node idealize() { @@ -55,6 +60,7 @@ public class StoreNode extends MemOpNode { // required init-store being stomped by a first user store. if( mem() instanceof StoreNode st && ptr()==st.ptr() && _alias==st._alias && // Must check same object + off()==st.off() && // And same offset ptr()._type instanceof TypeMemPtr && // No bother if weird dead pointers // Must have exactly one use of "this" or you get weird // non-serializable memory effects in the worse case. @@ -82,7 +88,7 @@ public class StoreNode extends MemOpNode { String err() { String err = super.err(); if( err != null ) return err; - Type ptr = val()._type; - return _init || ptr.isa(_declaredType) ? null : "Cannot store "+ptr+" into field "+_declaredType+" "+_name; + Type t = val()._type; + return _init || t.isa(_declaredType) ? null : "Cannot store "+t+" into field "+_declaredType+" "+_name; } } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index d5e54e73..134f7cd6 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -15,10 +15,6 @@ public class SubNode extends Node { @Override public Type compute() { - // Sub of same is 0 - if( in(1)==in(2) ) - return TypeInteger.ZERO; - Type t1 = in(1)._type, t2 = in(2)._type; if( t1.isHigh() || t2.isHigh() ) return TypeInteger.TOP; @@ -27,6 +23,9 @@ public class SubNode extends Node { if (i1.isConstant() && i2.isConstant()) return TypeInteger.constant(i1.value()-i2.value()); } + // Sub of same is 0 + if( in(1)==in(2) ) + return TypeInteger.ZERO; return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/XorNode.java b/src/main/java/com/seaofnodes/simple/node/XorNode.java index 720fb8e4..dbff90cf 100644 --- a/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -14,7 +14,6 @@ public class XorNode extends Node { @Override public Type compute() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; if( in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index 26897a7c..e2bf366d 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.type.TypeMem; -/** Chapter 14's view of the IR; browser, transport and layout are shared. */ +/** Chapter 15's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter { @Override protected String[] edgeNames(Node n) { @@ -21,16 +21,17 @@ public class SimpleGraphAdapter extends GraphAdapter { if( n instanceof LoopNode ) return Kind.LOOP; if( n instanceof RegionNode ) return Kind.REGION; if( n instanceof PhiNode ) return Kind.PHI; - return n.isCFG() ? Kind.CTRL : isMem(n) ? Kind.MEM : Kind.DATA; + return n instanceof CFGNode ? Kind.CTRL : isMem(n) ? Kind.MEM : Kind.DATA; } @Override protected Role role(Node n, int i) { if( n instanceof ScopeNode || n instanceof ConstantNode || n instanceof XCtrlNode ) return Role.ASSOC; if( n instanceof PhiNode ) return i == 0 ? Role.ASSOC : isMem(n) ? Role.MEM : Role.DATA; - if( n instanceof ProjNode || n instanceof CProjNode ) return n.isCFG() ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA; + if( n instanceof ProjNode || n instanceof CProjNode ) + return n instanceof CFGNode ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA; if( n instanceof RegionNode && i == 0 ) return Role.ASSOC; if( i == 0 || n instanceof RegionNode || n instanceof StopNode ) return Role.CTRL; - if( i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode) ) return Role.MEM; + if( i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode || n instanceof NewNode) ) return Role.MEM; Node def = n.in(i); if( def != null && isMem(def) ) return Role.MEM; return Role.DATA; diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index 202aa9d9..450922d7 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 14's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 15's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture { private Parser _parser; private Node _ret; diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java index b2c006dd..5e674132 100644 --- a/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/src/main/java/com/seaofnodes/simple/type/Field.java @@ -12,48 +12,52 @@ public class Field extends Type { // Field name public final String _fname; + // Unique memory alias + public final int _alias; // Type of the field public final Type _type; - private Field(String fname, Type type ) { + private Field(String fname, int alias, Type type ) { super(TFLD); _fname = fname; + _alias = alias; _type = type; } // Make with existing alias - public static Field make( String fname, Type type ) { - return new Field(fname,type).intern(); + public static Field make( String fname, int alias, Type type ) { + return new Field(fname,alias,type).intern(); } - public static final Field TEST = make("test",TypeInteger.ZERO); + public static final Field TEST = make("test",-2,TypeInteger.ZERO); public static void gather(ArrayList ts) { ts.add(TEST); } @Override Field xmeet( Type that ) { Field fld = (Field)that; // Invariant assert _fname.equals(fld._fname); - return make(_fname,_type.meet(fld._type)); + assert _alias==fld._alias; + return make(_fname,_alias,_type.meet(fld._type)); } @Override - public Field dual() { return make(_fname,_type.dual()); } + public Field dual() { return make(_fname,_alias,_type.dual()); } @Override public Field glb() { - return make(_fname,_type.glb()); + return make(_fname,_alias,_type.glb()); } // Override in subclasses - int hash() { return _fname.hashCode() ^ _type.hashCode(); } + int hash() { return _fname.hashCode() ^ _type.hashCode() ^ _alias; } boolean eq(Type t) { Field f = (Field)t; - return _fname.equals(f._fname) && _type==f._type; + return _fname.equals(f._fname) && _alias==f._alias && _type==f._type; } @Override public StringBuilder print( StringBuilder sb ) { - return _type.print(sb.append(_fname).append(" :")); + return _type.print(sb.append(_fname).append(":").append(_alias).append(" : ")); } @Override public String str() { return _fname; } diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 49dc090a..989eff9e 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -39,6 +39,7 @@ public class Type { static final byte TMEMPTR = 9; // Memory pointer type static final byte TSTRUCT =10; // Structs; tuples with named fields static final byte TFLD =11; // Fields into struct + static final byte TARRAY =12; // Array public final byte _type; @@ -81,6 +82,7 @@ public class Type { public StringBuilder typeName( StringBuilder sb) { return print(sb); } public Type makeInit() { return null; } + public Type nonZero() { return glb(); } // ---------------------------------------------------------- @@ -177,6 +179,14 @@ public class Type { */ public Type glb() { return _type==TCTRL ? XCONTROL : BOTTOM; } + // ---------------------------------------------------------- + + // Size in bits to hold an instance of this type. + // Sizes are expected to be between 1 and 64 bits. + // Size 0 means this either takes no space (such as a known-zero field) + // or isn't a scalar to be stored in memory. + public int log_size() { throw Utils.TODO(); } + // ---------------------------------------------------------- // Useful in the debugger, which calls toString everywhere. // This is a more verbose dev-friendly print. diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java index 975c1a9e..dc36c082 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -70,6 +70,11 @@ public class TypeFloat extends Type { @Override public boolean isHighOrConst() { return _sz<=0; } @Override public boolean isConstant() { return _sz==0; } + @Override public int log_size() { + int sz = _sz==0 ? (isF32() ? 32 : 64) : Math.abs(_sz); + return _sz==32 ? 2 : 3; + } + public double value() { return _con; } @Override @@ -111,4 +116,5 @@ public class TypeFloat extends Type { TypeFloat i = (TypeFloat)t; // Contract return _con==i._con && _sz==i._sz; } + } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index aca3e06b..042b4ba8 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.type; +import com.seaofnodes.simple.Utils; import java.util.ArrayList; /** @@ -75,6 +76,14 @@ public class TypeInteger extends Type { @Override public boolean isHighOrConst() { return _min >= _max; } @Override public boolean isConstant () { return _min == _max; } + @Override public int log_size() { + if( this==I8 || this==U8 || this==BOOL ) return 0; // 1<<0 == 1 bytes + if( this==I16 || this==U16 ) return 1; // 1<<1 == 2 bytes + if( this==I32 || this==U32 ) return 2; // 1<<2 == 4 bytes + if( this==BOT ) return 3; // 1<<3 == 8 bytes + throw Utils.TODO(); + } + public long value() { assert isConstant(); return _min; } // AND-mask of forced zeros. e.g. unsigned types will return their mask; @@ -104,8 +113,14 @@ public class TypeInteger extends Type { } @Override public TypeInteger dual() { return make(_max,_min); } - @Override public Type glb() { return BOT; } + @Override public TypeInteger glb() { return BOT; } @Override public TypeInteger makeInit() { return ZERO; } + @Override public TypeInteger nonZero() { + if( isHigh() ) return this; + if( _min==0 ) return make(1,_max); // specifically good on BOOL + if( _max==0 ) return make(_min,-1); + return this; + } @Override int hash() { return (int)((_min ^ (_min>>32)) *(_max ^ (_max>>32))); } @Override public boolean eq( Type t ) { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 38b3635a..76288d3e 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -16,49 +16,55 @@ public class TypeMem extends Type { // -1 means BOT, all memory. // N means slice#N. public final int _alias; + public final Type _t; // Memory contents, some scalar type - private TypeMem(int alias) { super(TMEM); _alias = alias; } + private TypeMem(int alias, Type t) { super(TMEM); _alias = alias; _t = t; } - public static TypeMem make(int alias) { return new TypeMem(alias).intern(); } - public static final TypeMem TOP = make( 0); - public static final TypeMem BOT = make(-1); + public static TypeMem make(int alias, Type t) { return new TypeMem(alias,t).intern(); } + public static final TypeMem TOP = make( 0, Type.TOP); + public static final TypeMem BOT = make(-1, Type.BOTTOM); - public static void gather(ArrayList ts) { ts.add(make(1)); ts.add(BOT); } + public static void gather(ArrayList ts) { ts.add(make(1,TypeInteger.ZERO)); ts.add(BOT); } @Override TypeMem xmeet(Type t) { TypeMem that = (TypeMem) t; // Invariant: TypeMem and unequal - return _alias==0 ? that : (that._alias==0 ? this : BOT); + if( this==TOP ) return that; + if( that==TOP ) return this; + if( this==BOT ) return BOT; + if( that==BOT ) return BOT; + int alias = _alias==that._alias ? _alias : -1; + Type mt = _t.meet(that._t); + return make(alias,mt); } @Override public Type dual() { if( _alias== 0 ) return BOT; if( _alias==-1 ) return TOP; - return this; + return make(_alias,_t.dual()); } @Override - public Type glb() { return make(_alias); } + public Type glb() { return make(_alias,_t.glb()); } @Override - int hash() { return 9876543 + _alias; } + int hash() { return 9876543 + _alias + _t.hashCode(); } @Override boolean eq(Type t) { TypeMem that = (TypeMem) t; // Invariant - return _alias == that._alias; + return _alias == that._alias && _t == that._t; } @Override public StringBuilder print(StringBuilder sb) { if( this==BOT ) return sb.append("MemBot"); if( this==TOP ) return sb.append("MemTop"); - return sb.append("MEM#").append( switch(_alias) { - case 0 -> "TOP"; - case -1 -> "BOT"; - default -> ""+_alias; - }); + sb.append("MEM#"); + if( _alias== 0 ) return sb.append("TOP"); + if( _alias==-1 ) return sb.append("BOT"); + return _t.print(sb.append(_alias).append(":")); } @Override public String str() { return toString(); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index e6e40fe2..ceba733d 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -6,8 +6,8 @@ import java.util.ArrayList; * Represents a Pointer to memory. * * Null is generic pointer to non-existent memory. - * *void is a non-Null pointer to all possible structs. - * Pointers can be to specific struct types, or a union with Null. + * *void is a non-Null pointer to all possible refs, both structs and arrays. + * Pointers can be to specific struct and array types, or a union with Null. * The distinguished *$BOT ptr represents union of *void and Null. * The distinguished *$TOP ptr represents the dual of *$BOT. */ @@ -33,12 +33,16 @@ public class TypeMemPtr extends Type { } public static TypeMemPtr make(TypeStruct obj, boolean nil) { return new TypeMemPtr(obj, nil).intern(); } public static TypeMemPtr make(TypeStruct obj) { return make(obj, false); } - public TypeMemPtr make_from(TypeStruct obj) { return make(obj, _nil); } + public TypeMemPtr makeFrom(TypeStruct obj) { return make(obj, _nil); } + // An abstract pointer, pointing to either a Struct or an Array. + // Can also be null or not. public static final TypeMemPtr BOT = make(TypeStruct.BOT,true); public static final TypeMemPtr TOP = BOT.dual(); + // An abstract null (can be Struct or Array) or not-null C void* public static final TypeMemPtr NULLPTR = make(TypeStruct.TOP,true); public static final TypeMemPtr VOIDPTR = NULLPTR.dual(); // A bottom mix of not-null ptrs, like C's void* but not null + public static final TypeMemPtr TEST= make(TypeStruct.TEST,false); public static void gather(ArrayList ts) { ts.add(NULLPTR); ts.add(BOT); ts.add(TEST); } @@ -52,11 +56,14 @@ public class TypeMemPtr extends Type { public TypeMemPtr dual() { return TypeMemPtr.make(_obj.dual(), !_nil); } @Override - public Type glb() { return make(_obj.glb(),true); } + public TypeMemPtr glb() { return make(_obj.glb(),true); } @Override public TypeMemPtr makeInit() { return NULLPTR; } + @Override public Type nonZero() { return VOIDPTR; } @Override public boolean isHigh() { return this==TOP; } + @Override public int log_size() { return 2; } // (1<<2)==4-byte pointers + @Override int hash() { return _obj.hashCode() ^ (_nil ? 1024 : 0); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 8ad59a39..922b7914 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -8,38 +8,53 @@ import java.util.ArrayList; */ public class TypeStruct extends Type { - // Immutable shallow references, resolved by name in Parser.TYPES when needed. - // A name-only struct has _fields == null, even after its definition is known. - // For LLI { LLI? next; int i; }, L0 is name-only and L1.next points to L0; - // TYPES["LLI"] holds L1. We deliberately stop recursive type expansion here, - // keeping interning and lattice operations finite and acyclic. Never patch - // L0 into L1: field access looks up the complete declaration by name instead. + // A Struct has a name and a set of fields; the fields themselves have + // names, types and aliases. The name has no semantic meaning, but is + // useful for debugging. Briefly during parsing a Struct can be a + // forward-ref; in this case the _fields array is null. + + // Its illegal to attempt to load a field from a forward-ref struct. + + // Example: "int rez = new S.x; struct S { int x; } return rez;" // Error, S not defined + // Rewrite: "struct S { int x; } int rez = new S.x; return rez;" // Ok, no forward ref + // + // During the normal optimization run, struct types "bottom out" at further + // struct references, so we don't have to handle e.g. cyclic types. The + // "bottom out" is again the forward-ref struct. public final String _name; public final Field[] _fields; - private TypeStruct(String name, Field[] fields) { - super(Type.TSTRUCT); + TypeStruct(String name, Field[] fields) { + super(TSTRUCT); _name = name; _fields = fields; } - // Forward-ref version - public static TypeStruct make(String name) { return new TypeStruct(name, null).intern(); } // All fields directly listed - public static TypeStruct make(String name, Field[] fields) { return new TypeStruct(name, fields).intern(); } - // Parser uses an ArrayList to gather the fields - public static TypeStruct make(String name, ArrayList fields) { return make(name,fields.toArray(new Field[fields.size()])); } - - public static final TypeStruct TOP = make("$TOP",new Field [0]); - public static final TypeStruct BOT = make("$BOT",new Field [0]); + public static TypeStruct make(String name, Field... fields) { return new TypeStruct(name, fields).intern(); } + public static final TypeStruct TOP = make("$TOP",new Field[0]); + public static final TypeStruct BOT = make("$BOT",new Field[0]); public static final TypeStruct TEST = make("test",new Field[]{Field.TEST}); + // Forward-ref version + public static TypeStruct make(String name) { return make(name, (Field[])null); } + + // Array + public static TypeStruct makeAry(TypeInteger len, int lenAlias, Type body, int bodyAlias) { + assert !(body instanceof TypeMemPtr tmp && !tmp._nil); + return make(body.str() + "[]", + Field.make("#" , lenAlias,len ), + Field.make("[]",bodyAlias,body)); + } // A pair of self-cyclic types private static final TypeStruct S1F = make("S1"); private static final TypeStruct S2F = make("S2"); - public static final TypeStruct S1 = make("S1", new Field[]{ Field.make("a", TypeInteger.BOT), Field.make("s2",TypeMemPtr.make(S2F,false)) }); - private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", TypeFloat .BOT), Field.make("s1",TypeMemPtr.make(S1F,false)) }); - public static void gather(ArrayList ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); } + public static final TypeStruct S1 = make("S1", new Field[]{ Field.make("a", -1, TypeInteger.BOT), Field.make("s2",-2,TypeMemPtr.make(S2F,false)) }); + private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", -3, TypeFloat .BOT), Field.make("s1",-4,TypeMemPtr.make(S1F,false)) }); + + private static final TypeStruct ARY = makeAry(TypeInteger.BOT,-1,TypeFloat.BOT,-2); + + public static void gather(ArrayList ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); ts.add(ARY); } public int find(String fname) { for( int i=0; i<_fields.length; i++ ) @@ -66,11 +81,15 @@ public class TypeStruct extends Type { return BOT; // It's a struct; that's about all we know if( this._fields==null ) return this; if( that._fields==null ) return that; - // Now all fields should be the same, so just do field meets - assert _fields.length == that._fields.length; + if( _fields.length != that._fields.length ) return BOT; + // Just do field meets Field[] flds = new Field[_fields.length]; - for( int i=0; i<_fields.length; i++ ) - flds[i] = (Field)_fields[i].meet(that._fields[i]); + for( int i=0; i<_fields.length; i++ ) { + Field f0 = _fields[i], f1 = that._fields[i]; + if( !f0._fname.equals(f1._fname) || f0._alias != f1._alias ) + return BOT; + flds[i] = (Field)f0.meet(f1); + } return make(_name,flds); } @@ -109,6 +128,7 @@ public class TypeStruct extends Type { if( !_name.equals(ts._name) ) return false; if( _fields == ts._fields ) return true; + if( _fields==null || ts._fields==null ) return false; if( _fields.length!=ts._fields.length ) return false; for( int i = 0; i < _fields.length; i++ ) @@ -145,4 +165,52 @@ public class TypeStruct extends Type { if( this==TOP ) return "StructTop"; return _name; } + + + public boolean isAry() { return _fields.length==2 && _fields[1]._fname.equals("[]"); } + + public int aryBase() { + assert isAry(); + if( _offs==null ) _offs = offsets(); + return _offs[1]; + } + public int aryScale() { + assert isAry(); + return _fields[1]._type.log_size(); + } + + + // Field offsets as packed byte offsets + private int[] _offs; // Lazily computed and not part of the type semantics + public int offset(int idx) { + if( _offs==null ) _offs = offsets(); + return _offs[idx]; + } + private int[] offsets() { // Field byte offsets + // Compute a layout for a collection of fields + assert _fields != null; // No forward refs + // Compute a layout + int[] cnts = new int[4]; // Count of fields at log field size + for( Field f : _fields ) + cnts[f._type.log_size()]++; // Log size is 0(byte), 1(i16/u16), 2(i32/f32), 3(i64/dbl) + int off = 0, idx = 0; // Base common struct fields go here, e.g. Mark/Klass + // Compute offsets to the start of each power-of-2 aligned fields. + int[] offs = new int[4]; + for( int i=3; i>=0; i-- ) { + offs[i] = off; + off += cnts[i]<