From 2a643205cc0b4adff394c6bed272e4b9f158f89f Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 23 Apr 2024 17:23:16 +0100 Subject: Chapter 10: Structs and Memory MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Thalia Archibald Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Dibyendu Majumdar Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: XmiliaH Co-authored-by: Tamás Hadházy <85063808+Hels15@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 --- docs/chapter10/10-grammar.ja.md | 131 ++++++ docs/chapter10/10-grammar.md | 127 ++++++ docs/chapter10/Makefile | 1 + docs/chapter10/README.ja.md | 270 +++++++++++++ docs/chapter10/README.md | 422 ++++++++++++++++++++ docs/chapter10/example1.gv | 16 + docs/chapter10/example1.json | 23 ++ docs/chapter10/example1.svg | 118 ++++++ docs/chapter10/example2a.gv | 17 + docs/chapter10/example2a.json | 26 ++ docs/chapter10/example2a.svg | 130 ++++++ docs/chapter10/example2b.gv | 19 + docs/chapter10/example2b.json | 27 ++ docs/chapter10/example2b.svg | 135 +++++++ docs/chapter10/example2c.gv | 14 + docs/chapter10/example2c.json | 21 + docs/chapter10/example2c.svg | 109 +++++ docs/chapter10/lattice.gv | 127 ++++++ docs/chapter10/lattice.svg | 593 ++++++++++++++++++++++++++++ docs/chapter10/load-after-store-after.json | 19 + docs/chapter10/load-after-store-after.svg | 97 +++++ docs/chapter10/load-after-store-before.json | 20 + docs/chapter10/load-after-store-before.svg | 103 +++++ docs/chapter10/type-control.svg | 5 + docs/chapter10/type-integer.svg | 5 + docs/chapter10/type-memory.svg | 5 + docs/chapter10/type-pointer.svg | 5 + docs/chapter10/type-struct.svg | 5 + docs/chapter10/type-tuple.svg | 5 + 29 files changed, 2595 insertions(+) create mode 100644 docs/chapter10/10-grammar.ja.md create mode 100644 docs/chapter10/10-grammar.md create mode 100644 docs/chapter10/Makefile create mode 100644 docs/chapter10/README.ja.md create mode 100644 docs/chapter10/README.md create mode 100644 docs/chapter10/example1.gv create mode 100644 docs/chapter10/example1.json create mode 100644 docs/chapter10/example1.svg create mode 100644 docs/chapter10/example2a.gv create mode 100644 docs/chapter10/example2a.json create mode 100644 docs/chapter10/example2a.svg create mode 100644 docs/chapter10/example2b.gv create mode 100644 docs/chapter10/example2b.json create mode 100644 docs/chapter10/example2b.svg create mode 100644 docs/chapter10/example2c.gv create mode 100644 docs/chapter10/example2c.json create mode 100644 docs/chapter10/example2c.svg create mode 100644 docs/chapter10/lattice.gv create mode 100644 docs/chapter10/lattice.svg create mode 100644 docs/chapter10/load-after-store-after.json create mode 100644 docs/chapter10/load-after-store-after.svg create mode 100644 docs/chapter10/load-after-store-before.json create mode 100644 docs/chapter10/load-after-store-before.svg create mode 100644 docs/chapter10/type-control.svg create mode 100644 docs/chapter10/type-integer.svg create mode 100644 docs/chapter10/type-memory.svg create mode 100644 docs/chapter10/type-pointer.svg create mode 100644 docs/chapter10/type-struct.svg create mode 100644 docs/chapter10/type-tuple.svg (limited to 'docs/chapter10') diff --git a/docs/chapter10/10-grammar.ja.md b/docs/chapter10/10-grammar.ja.md new file mode 100644 index 00000000..62e20597 --- /dev/null +++ b/docs/chapter10/10-grammar.ja.md @@ -0,0 +1,131 @@ +# 第10章の文法 + +[English](10-grammar.md) | 日本語 + +この文書は [原文](10-grammar.md) の日本語訳です。 + +[第10章に戻る](README.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | structDeclaration + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatment + ; + +field + : 'int' IDENTIFIER ';' + ; + +fields + : field+ + ; + +structDeclaration + : 'struct' IDENTIFIER '{' fields '}' + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + | fieldExpression '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +structName + : IDENTIFIER + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + | structName ('?')? IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | '!' unaryExpression + | primaryExpression + ; + +newExpression + : 'new' IDENTIFIER + ; + +fieldExpression + : primaryExpresson '.' IDENTIFIER + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | 'null' + | newExpression + | '(' expression ')' + | fieldExpression + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter10/10-grammar.md b/docs/chapter10/10-grammar.md new file mode 100644 index 00000000..0c6fe7e0 --- /dev/null +++ b/docs/chapter10/10-grammar.md @@ -0,0 +1,127 @@ +# Grammar for Chapter 10 + +English | [日本語](10-grammar.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | structDeclaration + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatment + ; + +field + : 'int' IDENTIFIER ';' + ; + +fields + : field+ + ; + +structDeclaration + : 'struct' IDENTIFIER '{' fields '}' + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + | fieldExpression '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +structName + : IDENTIFIER + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + | structName ('?')? IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | '!' unaryExpression + | primaryExpression + ; + +newExpression + : 'new' IDENTIFIER + ; + +fieldExpression + : primaryExpresson '.' IDENTIFIER + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | 'null' + | newExpression + | '(' expression ')' + | fieldExpression + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter10/Makefile b/docs/chapter10/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter10/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter10/README.ja.md b/docs/chapter10/README.ja.md new file mode 100644 index 00000000..19ee75eb --- /dev/null +++ b/docs/chapter10/README.ja.md @@ -0,0 +1,270 @@ +# 第10章: 構造体とメモリ + +[English](README.md) | 日本語 + +[前: 第9章](../chapter09/README.ja.md) | +[次: 第11章](../chapter11/README.ja.md) + +この文書は [原文](README.md) の日本語訳です。 + +この章では、ユーザー定義の構造体、ポインタ、割り当て、フィールドのロードとストア、null チェックを追加します。また、メモリへの作用も含めてグラフを実行する評価器を導入します。[文法](10-grammar.ja.md)は第10章と第11章で共通です。次の章ではメモリの表現を改善します。 + +## 参照 + +構造体は、名前と型を持つフィールドの集まりです。C や Java とよく似た、ごく伝統的なものです。新しい構造体は `new` キーワードで作ります。これはメモリを割り当て、参照を生成します。メモリの解放は後の章で扱います。フィールドへのアクセスには `.` 記法を使います。フィールドには、ほかの構造体への参照も含め、任意のスカラー値を格納でき、相互再帰も可能です。参照フィールドは通常の変数と同じように、null を許容することも禁止することもできます。 + +```java +struct Person { + String last; // Last name, must exist + String? middle; // Optional middle name + int age; +}; +``` + +ここには、null にならない final な String の `last`、null を許容する final な String の `middle`、そして `int age` があります。`int` として宣言されたすべてのフィールドと同じく、`age` は変更可能です。後の章では、変更可能な参照フィールドと不変の整数フィールドの両方を扱えるようにします。当面はこの選択で、よくある用途の大部分をカバーします。 + +フィールドにアクセスするには参照が必要です。静的フィールドは後の章で追加します。 + +フィールドへの参照には、必ず null でないポインタを使わなければなりません。これは型システムが直接チェックします。つまり Simple は、設計によって null ポインタ例外を禁止します。使用前に null をチェックする例を示します。 + +```java +print(ptr.age); // ERROR! ptr might be null + +if( ptr ) print(ptr.age); // Test before use + +// Field use can be far removed, as long as the check dominates +if( ptr ) { + S1; // Other statements + while( other ) { ...ptr.age... } +}; +``` + +割り当てとストアが加わるため、メモリへの作用を扱う必要が生じます。 + +## 1つのメモリ値 + +算術ノードは使用する値に依存します。同じように、ロードはメモリを観測する時点にも依存します。この章では、各ストアは直前のメモリ状態を消費し、次の状態を生成します。ロードはメモリを消費しますが、変更しません。これによって、ソースプログラムのメモリ順序がグラフに明示されます。 + +```java +struct Point { int x; int y; } +Point p = new Point; +p.x = 3; +p.y = arg; +return p.x; +``` + +`NewNode` はポインタを生成します。パーサーはまず両フィールドにゼロを書き込むストアを出力し、次に `x` に 3、`y` に `arg` を格納します。最後のロードは、`y` へのストア後のメモリを観測します。異なるフィールドは独立ですが、この章では意図的にこの依存関係を残します。第11章で取り除きます。 + +![1本の鎖がストアとロードを順序付ける](example1.svg) + +グラフは局所的な畳み込み前の依存関係を示しています。メモリに注目するため、制御エッジの大部分を省略し、合流が重要な箇所に最小限の True/False ノードだけを残しています。また、この配置は実行スケジュールではなく、依存関係を示します。 + +| ノード | 入力 | 結果 | +|---|---|---| +| `New` | 制御と構造体の型 | 新しい、null でないオブジェクトポインタ | +| `Store` | メモリ、ポインタ、フィールド名、値 | 更新されたメモリ全体の状態 | +| `Load` | メモリ、ポインタ、フィールド名 | フィールドの値 | +| `Start` | 外部からの入口 | 制御、初期メモリ、`arg` | +| `Return` | 制御、メモリ、結果 | それまでの作用をすべて保持した完了 | + +制御とメモリをともに消費または生成するノードでは、制御がスロット 0、メモリがスロット 1 を占めます。Start の出力は `{ctrl, $mem, arg}`、Return の入力は `{ctrl, $mem, result}` です。 + +メモリエッジは依存関係であり、ヒープのコピーではありません。グラフは合法な実行順序を決めます。ハードウェアでは Store が物理メモリを直接更新します。評価器では、Store がオブジェクトに付随するメモリ配列を更新します。 + +## メモリは SSA 変数 + +パーサーは `$mem` という名前の隠れた束縛を1つ保持します。ソースの識別子に `$` は含められないため、ユーザーコードからこの名前は使えません。メモリの読み出しと更新には、局所変数と同じ `ScopeNode` の検索・更新操作を使います。 + +`if` の2つの分岐は、異なるメモリ値で終了する可能性があります。通常の Phi が、実行された分岐のメモリを選択します。 + +```java +struct Point { int x; int y; } +Point p = new Point; +if( arg ) p.x = 3; else p.x = 4; +return p.x; +``` + +![分岐をまたぐメモリ全体](example2a.svg) + +ループには第8章の遅延 Phi 構築を再利用します。ループ内で `$mem` を読み出すか更新すると、最初は未完成のメモリ Phi を作ります。ループを閉じると、その後退エッジが与えられます。`break`、`continue`、入れ子のループ、早期 return でも、スカラー変数と同じスコープの仕組みを使います。 + +```java +struct Point { int x; int y; } +Point p = new Point; +while( arg ) { + p.x = arg; + arg = arg-1; +}; +return p.x; +``` + +![ループを巡るメモリ全体](example2b.svg) + +すべての Return は現在のメモリ全体の値を消費します。返されるスカラーがストアに依存しない場合や、プログラムが変更したオブジェクト自体を返す場合でも、これによってストアが生き残ります。 + +## 拡張された型の束 + +この章では、Simple の型の束を大きく改訂します。 + +![6つの領域と並列な名前付き構造体の選択肢を持つ型の束](./lattice.svg) + +図では **トップ** に `⊤`、**ボトム** に `⊥` を使います。接尾辞は領域を表します。`⊤:struct` は*構造体トップ*で、単独の `⊤` は全体のトップです。本文ではこれらの言葉を使い、コード例では実際の Java 定数を使います。実装の `$TOP` と `$BOT` という名前を図に表示する必要はありません。 + +| 図 | 本文 | Java 定数 | 内部の構造体名 | +|---|---|---|---| +| `⊤:struct` | 構造体トップ | `TypeStruct.TOP` | `$TOP` | +| `⊥:struct` | 構造体ボトム | `TypeStruct.BOT` | `$BOT` | + +図のエッジは束の順序を示し、トップはボトムの上にあります。省略記号を含む箱は、さらに並列の選択肢があることを省略して示すもので、追加の共用体型ではありません。フィールドとタプル要素の型の束は省略しています。フィールドの型には任意のスカラー型（Integer または Pointer）を使え、Tuple の型には Control や Memory を含む*任意の*束の型を使えます。 + +型の束には、以下の領域があります。 + +* ![制御](type-control.svg) は制御フローを表します。制御トップは到達不能な制御、制御ボトムは到達可能な制御です。 +* ![整数](type-integer.svg) には整数トップ、整数ボトムと、その間に並列に配置された定数があります。省略記号はほかの整数定数を表します。 +* ![ポインタ](type-pointer.svg)（新規）は構造体の型と null 許容性を組み合わせます。 + * 接頭辞 `*` は、その型へのポインタを意味します。`*Person` は Person への null でないポインタです。接尾辞 `?` は null を含むため、`*Person?` は Person ポインタまたは null を許容します。 + * ポインタ領域には構造体の束全体が2つ含まれます。1つは null を含まず、もう1つは null を含みます。図は両方について名前付きの選択肢を展開しています。単に2つのポインタ型があるわけではありません。 + * `null` は構造体トップと null 許容フラグを組み合わせたもので、null でないオブジェクトの選択肢を持ちません。図では `null` とともに `*⊤:struct?` と表記しています。 + * 構造体ボトムへのポインタは任意の構造体を指せます。図では null でない形式を `*⊥:struct`、null を許容する形式を `*⊥:struct?` と示します。後者がポインタボトムで、ポインタトップは `*⊤:struct` です。 + * null は false、null でないポインタは true と評価されます。 + + > C との類推: 構造体ボトムへの null でないポインタは `void *` に似ています。ただし C の `void *` は null にもなれます。Simple はこの定数を `TypeMemPtr.VOIDPTR` と名付け、`*void` と表示します。構造体ボトム自体は、構造体の型に共通する下界であって、C の `void` 型ではありません。 + +* ![構造体](type-struct.svg)（新規）は、ユーザー定義の名前付き構造体を表します。この章のフィールドは整数型です。 + * 構造体トップはすべての名前付き構造体の上に、構造体ボトムはすべての名前付き構造体の下にあります。トップは高位の空の構造体の選択肢で、ボトムは保守的に任意の構造体名を含みます。 + * `Person`、`s1`、`s2`、さらにほかの名前は、並列の選択肢です。継承はないため、異なる名前の構造体は、同じフィールドを持っていても互いの下に入りません。 + * プログラムが宣言できる名前に固定の上限はありません。図の省略記号は、特別な無名構造体ではなく、さらに名前付きの選択肢があることを示します。各名前付きの箱は、それぞれのフィールド型の束を省略して表しています。 +* ![メモリ](type-memory.svg)（新規）はメモリ全体のトークンを表します。メモリトップとメモリボトムは `TypeMem.TOP` と `TypeMem.BOT` です。どちらも個別のフィールドに格納された値を記録しません。 +* ![タプル](type-tuple.svg) は、Start の制御、メモリ、引数のように、1つのノードから出る結果の集まりを表します。ピンク色の見出しは長さの異なるタプルを区別します。縦に積まれた黒い `type` の各セルは、別のタプルを含む可能性も含め、型の束全体を再び表しています。 + +束には以下の操作を使います。 + +* **Meet（交わり）** は最大下界を計算します。これらの例では、入力が表す選択肢を組み合わせるものと考えてください。 + * `Person` と `s1` の meet は構造体ボトムです。この2つの名前だけを表す別の型はありません。 + * `*Person` と `*s1` の meet は、構造体ボトムへの null でないポインタです。 + * `*Person` と `null` の meet は `*Person?` です。 + * 構造体ボトムへの null でないポインタと `null` の meet はポインタボトムです。 + * `1` と `2` の meet は整数ボトムです。 +* **Dual（双対）** は束を中心線に対して反転します。トップとボトムが入れ替わり、dual を2回適用すると元の型に戻ります。 + * 構造体トップと構造体ボトムは双対です。 + * `null` と、構造体ボトムへの null でないポインタは双対です。 + * ポインタの dual は、その構造体のフィールドにも dual を適用し、null 許容性を反転します。したがって `*Person` の dual は、一般には元の `*Person?` ではありません。フィールドの型も双対にする必要があります。図ではフィールドの詳細を省略しています。 +* **Join（結び）** は最小上界を計算します。meet と dual を通して `JOIN(x,y) = MEET(x.dual(),y.dual()).dual()` と定義されます。 + * `Person` と `s1` の join は構造体トップです。 + * `*Person` と `*s1` の join はポインタトップです。 + * 構造体ボトムへの null でないポインタと `null` の join はポインタトップです。 + * `1` と `2` の join は整数トップです。 + +Sea of Nodes グラフの構築中には、値が生成された領域の中に留まることを保証します。つまり、ポインタフィールドに整数が入ることは（当然ながら）なく、汎用の `TOP` や `BOT` さえ入りません。強調しておきたい細かい点がいくつかあります。 + +* Phi を作るとき、その初期型は最初の入力の宣言型に基づきます。ほかにどんな型との meet を取るかはまだわからないため、これは悲観的な型の割り当てです。 +* Phi の入力がすべてわかったら、宣言型の局所的なトップから始め、すべての入力型の meet を計算します。この計算により、Phi の型をより精密にします。 + +## パーサーの拡張 + +これまでの章で使える型は Integer だけでした。今では変数を Integer 型にも、Struct 型へのポインタにもできます。このため、パーサーは変数の宣言型を追跡するようになりました（以前は Integer だけでした）。変数の宣言型は、その変数に合法的に代入できる値の集合を定義します。Sea of Nodes グラフは、変数に代入された値の実際の型も追跡します。これらの型の遷移は前節で説明した型の束によって定義されます。 + +## null ポインタ解析 + +Simple 言語の構文では、ポインタ変数が null を許容すると指定できます。そのうえで、null ポインタ例外が発生することを防ぎます。コンパイラは null チェックが必要かどうかを判定し、必要なのに存在しなければプログラムを拒否します（ユーザーに null チェックの挿入を求めます）。 + +パーサーは、ポインタ変数の真偽を調べる条件に遭遇すると、その知識を使って以降の分岐で型情報を絞り込みます。 + +動機となる例を2つ示します。 + +```java +struct Bar { int a; } +Bar? bar = new Bar; +if (arg) bar = null; +if( bar ) bar.a = 1; +``` + +上で `bar` が `null` でなければ、`bar.a` への代入を許可したいところです。最後の行に null チェックがなく、たとえば単に `bar.a = 1;` だった場合、`Java` はこのプログラムをコンパイルしますが NPE を投げます。Simple は null チェックが必要だと指摘して、プログラムを拒否します。 + +```java +struct Bar { int a; } +Bar? bar = new Bar; +if (arg) bar = null; +int rez = 3; +if( !bar ) rez=4; +else bar.a = 1; +``` + +`bar` が `null` なら、`!bar` を `true` と評価したいところです。else 分岐では `bar` が null でないとわかるため、`bar.a` への代入は許可されるべきです。 + +この動作を可能にするため、以下の拡張を行います。 + +* 型システムでポインタが null かどうかを追跡します。したがって、ptr 型が流れるすべての Node でも追跡します。 +* `If` ノードの述語が ptr 値なら、その述語をアップキャストで「包みます」。アップキャストは true 分岐で null の可能性を取り除き、ポインタを使えるようにします。 +* アップキャストには、構造体ボトムへの null でないポインタ（`TypeMemPtr.VOIDPTR`）への `Cast` を使います。元のポインタ型とこの型の join を取ります。これは図の `*⊥:struct` に対応します。この JOIN 操作は、ptr についてすでにわかっていることをすべて保持し、ptr が null でないという新しい知識を追加します。 +* アップキャストは `CastNode` 演算で表し、適用可能であれば現在のスコープで元の述語のすべての出現をアップキャストに置き換えます。変更は `If` の各分岐に局所的で、true 分岐と false 分岐で別々に行います（false 分岐では述語を反転します）。 +* アップキャストにも通常のピープホール最適化を適用します。入力の型がアップキャストのスーパータイプなら `CastNode` を除去できます。`ScopeNode.upcast()` メソッドと `CastNode` を参照してください。 +* Not の型を計算するとき、入力が ptr なら Integer 型を生成します。入力が `null` なら `1`、null でない ptr 値なら `0` に変換します。`NotNode.compute()` を参照してください。 + +## 局所的なメモリ最適化 + +**同じポインタとフィールド**へのストアの直後にあるロードは、格納した値を使えます。`p.x` に `arg` を書き込んだばかりなので、その読み戻しにメモリアクセスは不要です。 + +```java +struct Box { int x; } +Box p = new Box; +p.x = arg; +return p.x; // Can return arg directly. +``` + +| 変換前: 格納した値を読み戻す | 変換後: 値を直接使う | +|---|---| +| ![変換前: Return は Store p.x の後の Load p.x を読む](load-after-store-before.svg) | ![変換後: Return は arg を使い、Store のメモリも引き続き消費する](load-after-store-after.svg) | + +Return の結果入力は Load から `arg` に変わり、使われなくなった Load は消えます。Return は引き続き Store のメモリを消費するので、書き込みは保持されます。 + +同じアドレスへの別のストアの直後にあるストアは、先行するストアを必要とするほかのユーザーがなければ、その先行ストアを破棄できます。この別の書き換えにより、上の図に残っているゼロ初期化のストアも除去できます。ここでも、ポインタとフィールドの両方のチェックが重要です。 + +ロードはメモリ Phi を通って上に移動することもできます。これは[第5章の Phi を通って上に押し上げる最適化](../chapter05/README.ja.md#phi-を通して加算を押し上げる)を拡張したものです。そこでは流入経路上で算術を畳み込みましたが、ここでは対応するストアに対してロードを畳み込めます。「Phi の Load は、Load の Phi になる」。グラフの記法では次のようになります。 + +```text +Load(Phi(r, m0, m1), p.x) + -> Phi(r, Load(m0, p.x), Load(m1, p.x)) +``` + +メモリの Phi が、ロードされた値の Phi になります。このピープホール変換は Node の総数を増やすので、利益のヒューリスティックは、少なくとも1つの Load が畳み込まれることを要求します。ループの場合、この Load は**後退エッジ**でなければなりません。入口だけで畳み込むと、サイクルに沿って無限に押し上げ続けられるロードが残るためです。算術の書き換えと同じく、畳み込みを露出させることは、変換後の後片付けに期待するものではなく、グラフを変換する判断の一部です。[`LoadNode.idealize()`](../../src/main/java/com/seaofnodes/simple/node/LoadNode.java) を参照してください。 + +逆方向は[第5章の共通演算の引き下げ](../chapter05/README.ja.md#例3)を拡張します。「Load の Phi は、Phi の Load になる」。対応する Load や Store の Phi は、合流後の1つの演算にできます。たとえば、次の2つの書き込みは、 + +```java +if (arg) s.x = arg+1; +else s.x = arg+2; +``` + +`s.x = Phi(arg+1,arg+2)` になり、最終的には `s.x = arg+Phi(1,2)` にできます。一般的な書き換えでは、メモリやポインタも含め、異なる各オペランドについて正しく型付けされた別々の Phi を作ります。メモリ演算にはさらに注意が必要です。型の精度が失われる可能性があるので、それも利益判定の一部としてチェックします。 + +また、Store を移動したときに元の作用が消えるように、Store にほかのユーザーがあってはいけません。Load については、そのメモリのユーザーに、競合する書き込みやメモリの合流が生じる可能性があってはいけません。そうでなければ、読み出しを遅らせると値が変わり得ます。ずっと後に反依存を追加しますが、今は保守的にチェックします。 + +### 簡単な最適化を見逃す + +1本のメモリ鎖は正しいものの保守的です。オブジェクトが同一でも、`y` へのストアが、先行する `x` へのストアからの値の転送を妨げることがあります。これは最適化の取りこぼしであり、次の章の動機となります。 + +## グラフの実行 + +評価器には、小さな遅延スケジューラがあります。ロードは、同じメモリ定義を消費する後続のストアより先に実行しなければなりません。ロードからストアへの通常のデータエッジがなくてもそうです。これらのロード/ストアの反依存が、明示的なグラフエッジを補います。 + +たとえば `p` の割り当て後の `int old = p.x; p.x = arg; return old;` は、最後のストアの前の値を読みます。以下のグラフでは Load と Store が同じメモリ状態を消費します。スケジューラは Load を先に実行しなければなりません。両者の間に通常のデータエッジはありません。 + +![ロードは値を上書きするストアより前でなければならない](example2c.svg) + +このスケジューラは本章の実行には十分です。第13章では、大域的コード移動とスケジューリングを独立した話題として扱います。 + +## ビルドとテスト + +このディレクトリで、JDK 21 以降、Make、シェルを使って実行します。 + +```sh +make lib +make tests +make release +make view +``` + +Make は Maven を使わずにこのスナップショットを直接ビルドします。`make release` は `build/release/simple.jar` を生成し、`make view` は共通の対話的グラフビューアを起動します。Maven と IDEA のモジュール記述も提供されています。テストには、これまでのすべての章、メモリ順序、返されたオブジェクトの内容、入れ子のループが含まれます。 + +次の[第11章](../chapter11/README.ja.md)では、パーサーのこの1つの束縛を維持しつつ、グラフを独立したメモリスライスに分割します。 diff --git a/docs/chapter10/README.md b/docs/chapter10/README.md new file mode 100644 index 00000000..a07a175f --- /dev/null +++ b/docs/chapter10/README.md @@ -0,0 +1,422 @@ +# Chapter 10: Structs and Memory + +English | [日本語](README.ja.md) + +[Previous: Chapter 9](../chapter09/README.md) | +[Next: Chapter 11](../chapter11/README.md) + +This chapter adds user-defined structs, pointers, allocation, field loads and +stores, and null checking. It also introduces an evaluator that executes the +graph, including its memory effects. The [grammar](10-grammar.md) is the +same in Chapters 10 and 11; the next chapter improves the memory representation. + +## References + +Structs are a collection of named and typed fields; very classically similar to +C or Java. New structs are made with the `new` keyword; this allocates memory +and produces a reference. Freeing memory awaits a later chapter. Fields are +accessed with the `.` notation. The fields can hold any scalar value, +including reference to other structs and be mutually recursive. Any reference +field can allow null or not, same as a normal variable. + +```java +struct Person { + String last; // Last name, must exist + String? middle; // Optional middle name + int age; +}; +``` + +Here we have fields `last`, a not-null final String, and `middle` a nullable +and final String, and an `int age`. Like all `int` declared fields, it is +mutable. Later chapters will allow both mutable reference fields and immutable +integer fields; for now this choice covers most of the common ground. + +You have to have a reference to get at the fields, static fields are added in a later chapter. + +All field references have to be against not-null pointers, and this is directly +checked in the type system. I.e., Simple disallows null-pointer-exceptions by +design. Some examples of null checking before using: + +```java +print(ptr.age); // ERROR! ptr might be null + +if( ptr ) print(ptr.age); // Test before use + +// Field use can be far removed, as long as the check dominates +if( ptr ) { + S1; // Other statements + while( other ) { ...ptr.age... } +}; +``` + +Allocation, as well as Stores, means we now have memory effects to deal with. + + +## One memory value + +Arithmetic nodes depend on the values they use, similarly a load also depends +on when it observes memory. In this chapter every store consumes the preceding +memory state and produces the next one, and a load consumes memory without +changing it. This makes the source program's memory ordering explicit in the +graph. + +```java +struct Point { int x; int y; } +Point p = new Point; +p.x = 3; +p.y = arg; +return p.x; +``` + +`NewNode` produces the pointer. The parser emits stores of zero for both fields, +then stores 3 into `x` and `arg` into `y`. The final load observes the memory +after the `y` store. We deliberately keep that dependency here, even though +different fields are independent. Chapter 11 will remove it. + +![One chain orders stores and loads](example1.svg) + +The graphs show dependencies before local folding. To focus on memory, remove +most control edges leaving behind minimal True/False nodes when merges are +important. Also, the layout shows dependencies, not an execution schedule. + +| Node | Inputs | Result | +|----------|---|---| +| `New` | Control and a struct type | A fresh, non-null object pointer | +| `Store` | Memory, pointer, field name, value | The updated whole-memory state | +| `Load` | Memory, pointer, field name | The value of the field | +| `Start` | External entry | Control, initial memory, and `arg` | +| `Return` | Control, memory, result | Completion with all preceding effects retained | + +For nodes consuming or producing both control and memory, control occupies slot +0 and memory slot 1. Start's outputs are `{ctrl, $mem, arg}`; Return's inputs +are `{ctrl, $mem, result}`. + +The memory edge is a dependency, not a copy of the heap. The graph determines +the legal execution order. In hardware, a Store updates physical memory +directly. In the evaluator, a Store updates an object's attached memory array. + +## Memory is an SSA variable + +The parser keeps one hidden binding named `$mem`. Source identifiers cannot +contain `$`, so user code cannot name it. Reading and updating memory uses the +same `ScopeNode` lookup and update operations as a local variable. + +For an `if`, the two branches can finish with different memory values. An +ordinary Phi selects the memory from the branch that executed: + +```java +struct Point { int x; int y; } +Point p = new Point; +if( arg ) p.x = 3; else p.x = 4; +return p.x; +``` + +![Whole memory across a branch](example2a.svg) + +Loops reuse Chapter 8's lazy Phi construction. Reading or updating `$mem` in a +loop creates an initially incomplete memory Phi. Closing the loop supplies its +backedge. `break`, `continue`, nested loops, and early returns use the same scope +mechanics as scalar variables. + +```java +struct Point { int x; int y; } +Point p = new Point; +while( arg ) { + p.x = arg; + arg = arg-1; +}; +return p.x; +``` + +![Whole memory around a loop](example2b.svg) + +Every Return consumes the current whole-memory value. This keeps stores alive +even when the returned scalar does not depend on them, or when the program +returns the modified object itself. + +## Enhanced Type Lattice + +The Type Lattice for Simple has a major revision in this chapter. + +![Type lattice with six domains and parallel named struct alternatives](./lattice.svg) + +The diagram uses `⊤` for **top** and `⊥` for **bottom**. A suffix names the +domain: `⊤:struct` is *struct top*, while the bare `⊤` is global top. In the +prose we use those words; in code examples we use the actual Java constants. +The implementation's `$TOP` and `$BOT` names need not appear in the diagram: + +| Diagram | Prose | Java constant | Internal struct name | +|---|---|---|---| +| `⊤:struct` | struct top | `TypeStruct.TOP` | `$TOP` | +| `⊥:struct` | struct bottom | `TypeStruct.BOT` | `$BOT` | + +Edges in this diagram show lattice order, with top above bottom. Boxes +containing an ellipsis abbreviate further parallel alternatives; they are not +extra union types. Field and tuple-element type lattices are elided in the +diagram. Field types can be any scalar type (Integer or Pointer), Tuple types +can be *any* lattice type, including Control and Memory. + +Within the type lattice, we now have the following domains: + +* ![Control](type-control.svg) represents control flow: unreachable control + at control top, and reachable control at control bottom. +* ![Integer](type-integer.svg) has integer top, integer bottom, and parallel + constants between them. The ellipses stand for the other integer constants. +* ![Pointer](type-pointer.svg) (new) combines a struct type with nullability. + * The prefix `*` means pointer-to: `*Person` is a non-null pointer to a Person. + The suffix `?` includes null, so `*Person?` permits a Person pointer or null. + * The pointer domain contains the whole struct lattice twice, once without + null and once with it. The diagram expands named alternatives in both + copies. It is not just two individual pointer types. + * `null` combines struct top with the nullable flag: it has no non-null + object alternative. The diagram labels it `*⊤:struct?` as well as `null`. + * A pointer to struct bottom can point to any struct. The diagram shows the + non-null form as `*⊥:struct` and the nullable form as `*⊥:struct?`. + The latter is pointer bottom; pointer top is `*⊤:struct`. + * Null evaluates to false; non-null pointers evaluate to true. + + > C analogy: the non-null pointer to struct bottom is akin to `void *`, except + > that C's `void *` may also be null. Simple names this constant + > `TypeMemPtr.VOIDPTR` and prints it as `*void`. Struct bottom itself is the + > common lower bound of struct types, not C's `void` type. + +* ![Struct](type-struct.svg) (new) represents user-defined named structs. + Fields have integer types in this chapter. + * Struct top lies above every named struct; struct bottom lies below every + named struct. Top is the high/empty struct alternative, while bottom + conservatively includes any struct name. + * `Person`, `s1`, `s2`, and further names are parallel alternatives. There is + no inheritance, so different named structs do not nest beneath one another, + even if they have identical fields. + * There is no fixed bound on the names a program can declare. The diagram's + ellipsis stands for more named alternatives, not a distinguished unnamed + struct. Each named box abbreviates its own field-type lattice. +* ![Memory](type-memory.svg) (new) represents the whole-memory token. + Memory top and memory bottom are `TypeMem.TOP` and `TypeMem.BOT`. Neither + records the values stored in individual fields. +* ![Tuple](type-tuple.svg) represents a collection of results from one node, + such as Start's control, memory, and argument. The pink headers identify tuples + of different lengths; each vertically stacked black `type` cell stands for + the full type lattice again, including the possibility of another tuple. + +We use the following operations on the lattice: + +* **Meet** computes the greatest lower bound. For these examples, think of + combining the alternatives represented by its inputs. + * The meet of `Person` and `s1` is struct bottom. There is no separate type + representing exactly those two names. + * The meet of `*Person` and `*s1` is the non-null pointer to struct bottom. + * The meet of `*Person` and `null` is `*Person?`. + * The meet of the non-null pointer to struct bottom and `null` is pointer bottom. + * The meet of `1` and `2` is integer bottom. +* **Dual** reflects the lattice about its centerline: top and bottom exchange + places, and applying dual twice returns the original type. + * Struct top and struct bottom are duals. + * `null` and the non-null pointer to struct bottom are duals. + * A pointer's dual also duals its struct's fields and flips nullability. Thus + the dual of `*Person` is not generally the original `*Person?`: the field + types must be dualed too. Those field details are omitted in the diagram. +* **Join** computes the least upper bound. It is defined through meet and dual: + `JOIN(x,y) = MEET(x.dual(),y.dual()).dual()`. + * The join of `Person` and `s1` is struct top. + * The join of `*Person` and `*s1` is pointer top. + * The join of the non-null pointer to struct bottom and `null` is pointer top. + * The join of `1` and `2` is integer top. + +As we construct the Sea of Nodes graph, we ensure that values stay inside the +domain they are created in - that is pointer fields will never contain integers +(obviously)... nor even the generic `TOP` and `BOT`. There are a couple of +nuances worth highlighting. + +* When Phis are created, the initial type of the Phi is based on the declared + type of its first input. This is a pessimistic type assignment because we do + not yet know what other types will be met. + +* When all the inputs of the Phi are known, we start with the local Top of the + declared type, and then compute a meet of all the input types. This + computation results in a more refined type for the Phi. + +## Parser Enhancements + +In previous chapters the only available type was Integer. Now, variables can +be of Integer type or pointer to Struct types. To support this, the Parser now +tracks the declared type of a variable (used to only be Integer!). The +declared type of a variable defines the set of values that can be legitimately +assigned to the variable. The Sea of Nodes graph also tracks the actual type +of values assigned to variables, these type transitions are defined by the Type +lattice described in the previous section. + +## Null Pointer Analysis + +The Simple language syntax allows a pointer variable to be specified as +null-able - and it prevents ever throwing a Null Pointer Exception. The +compiler decides if a null check is needed, and if needed and missing +the compiler rejects the program (asking the user to insert a null check). + +When the Parser encounters conditions that test the truthiness of a pointer variable, it uses this knowledge to refine the type information in the branches that follow. + +Here are two motivating examples: + +```java +struct Bar { int a; } +Bar? bar = new Bar; +if (arg) bar = null; +if( bar ) bar.a = 1; +``` + +If `bar` is not `null` above, then we would like to allow the assignment to +`bar.a`. If the final line lacked the null check, e.g. a plain `bar.a = 1;`, +then `Java` would compile this program but throw a NPE, and Simple rejects the +program pointing out a null check is required. + + +```java +struct Bar { int a; } +Bar? bar = new Bar; +if (arg) bar = null; +int rez = 3; +if( !bar ) rez=4; +else bar.a = 1; +``` + +If `bar` is `null` then we would like `!bar` to evaluate to `true`. In the else +branch we know `bar` is not null, hence the assignment to `bar.a` should be +allowed. + +To enable this behaviour, we make the following enhancements. + +* We track the null-ness of a pointer in the Type system, and hence in every + Node that ptr type flows through. + +* We "wrap" the predicate of an `If` node with an up-cast when we see that the + predicate is a ptr value. The up-cast removes the null possibility on the + true branch making it legal to use the pointer. + +* The up-cast uses a `Cast` with the non-null pointer to struct bottom + (`TypeMemPtr.VOIDPTR`). It joins the original pointer type with that type, + corresponding to `*⊥:struct` in the diagram. This JOIN operation preserves + everything we already know about ptr, and also adds the new knowledge that + the ptr is not-null. + +* The up-cast is represented by the `CastNode` op, and if applicable, we + replace all occurrences of the original predicate with the up-cast in the + current scope. The change is local to each branch of the `If`; occurring + separately for the true and the false branches of the `If` (and the false + branch inverts the predicate). + +* The up-cast peepholes normally; if its input's type is a super type of the + up-cast, then the `CastNode` can be removed. See `ScopeNode.upcast()` method, + and `CastNode`. + +* When computing a type for Not, we produce an Integer type when its input is a + ptr. When the input is a `null` we convert to `1` and when it is a non-null + ptr value, we convert to `0`. See `NotNode.compute()`. + + +## Local memory optimizations + +A load immediately following a store to the **same pointer and field** can use +the stored value. We just wrote `arg` into `p.x`, so reading it back needs no +memory access: + +```java +struct Box { int x; } +Box p = new Box; +p.x = arg; +return p.x; // Can return arg directly. +``` + +| Before: read back the stored value | After: use the value directly | +|---|---| +| ![Before: Return reads Load p.x after Store p.x](load-after-store-before.svg) | ![After: Return uses arg and still consumes the Store's memory](load-after-store-after.svg) | + +Return's result input changes from the Load to `arg`, and the unused Load +disappears. Return still consumes the Store's memory, so the write is retained. + +A store immediately following another store to the same address can also +discard the earlier store when no other user needs it. That separate rewrite +can remove the zero-initialization store still shown above. Again, both the +pointer and field checks matter. + +A load can also move up through a memory Phi. This extends +[Chapter 5's push-through-Phi optimization](../chapter05/README.md#pushing-addition-up-through-a-phi): +there, arithmetic folds on the incoming paths; here, a load can fold against a +matching store. "A Load of a Phi becomes a Phi of Loads". In graph notation: + +```text +Load(Phi(r, m0, m1), p.x) + -> Phi(r, Load(m0, p.x), Load(m1, p.x)) +``` + +The Phi of memory becomes a Phi of loaded values. Since this peep increases +the overall Node count, the profit heurstic requires at least one Load to fold. +On a loop, that Load must be the **backedge**: folding only on entry would +leave a load that could be pushed around the cycle indefinitely. As with the +arithmetic rewrite, exposing a fold is part of deciding to transform the +graph, not just a hoped-for cleanup afterward. See +[`LoadNode.idealize()`](../../src/main/java/com/seaofnodes/simple/node/LoadNode.java). + +The reverse direction extends +[Chapter 5's common-operation pull-down](../chapter05/README.md#example-3): +"A Phis of Loads becomes a Load of a Phi". A Phi of matching Loads or Stores +can become one operation after the join. For example, these two writes: + +```java +if (arg) s.x = arg+1; +else s.x = arg+2; +``` + +can become `s.x = Phi(arg+1,arg+2)` and eventually `s.x = arg+Phi(1,2)`. The +general rewrite creates a separate, correctly typed Phi for each differing +operand, including memory and pointers. We must be more careful here with +memory ops; it is possible to lose some type precision, so we check for that as +part of the profitability. + +Also, a Store must have no other users, so moving it removes the original +effect. A Load must have no possible conflicting writes or memory merges among +its memory's users; otherwise delaying the read could change its value. Much +later, we will be adding anti-dependences, but for now we do a conservative +check. + +### Missing an easy one + +The single memory chain is correct but conservative. A store to `y` can +prevent forwarding an earlier store to `x`, even when the objects are +identical. This is a missed optimization and it motivates the next chapter. + +## Executing the graph + +The evaluator includes a small late scheduler. A load must execute before a +later store that consumes the same memory definition, even though there is no +ordinary data edge from the load to that store. These load/store +anti-dependencies supplement the explicit graph edges. + +For example, after allocating `p`, `int old = p.x; p.x = arg; return old;` +reads the value before the final store. In the graph below, Load and Store +consume the same memory state. The scheduler must execute the Load first; +there is no ordinary data edge between them. + +![A load must precede a clobbering store](example2c.svg) + +The scheduler is sufficient to execute this chapter. Chapter 13 develops +global code motion and scheduling as a separate topic. + +## Build and test + +From this directory, with JDK 21 or newer, Make, and a shell: + +```sh +make lib +make tests +make release +make view +``` + +Make builds this snapshot directly, without Maven. `make release` produces +`build/release/simple.jar`; `make view` launches the shared interactive graph +viewer. Maven and IDEA module descriptions are also supplied. Tests include all +earlier chapters, memory ordering, returned object contents, and nested loops. + +Next, [Chapter 11](../chapter11/README.md) keeps this one parser binding while +splitting the graph into independent memory slices. diff --git a/docs/chapter10/example1.gv b/docs/chapter10/example1.gv new file mode 100644 index 00000000..9585b8e4 --- /dev/null +++ b/docs/chapter10/example1.gv @@ -0,0 +1,16 @@ +digraph Memory { + // IR styles match graph/web/render.js; arrows are use -> definition. + graph [bgcolor="#fafbfc" fontname="Helvetica" nodesep=0.35 ranksep=0.55 splines=ortho]; + node [fontname="Helvetica" fontsize=12 color="#758191" fontcolor="#152330" shape=box style="rounded,filled" fillcolor="#edf3f7"]; + edge [fontname="Helvetica" fontsize=9 color="#536477" fontcolor="#364352" arrowsize=0.7 penwidth=1.5]; + + rankdir=RL; + + M0 [label="Initial memory" shape=octagon style="filled" fillcolor="#dcecff"]; + X [label="Store p.x = 3" shape=octagon style="filled" fillcolor="#dcecff"]; + Y [label="Store p.y = arg" shape=octagon style="filled" fillcolor="#dcecff"]; + L [label="Load p.x" shape=box style="rounded,filled" fillcolor="#edf3f7"]; + L -> Y -> X -> M0 [color="#2867b2"]; + Return -> Y [color="#2867b2"]; Return -> L; + Return [shape=box style="filled" fillcolor="#fff1c4"]; +} diff --git a/docs/chapter10/example1.json b/docs/chapter10/example1.json new file mode 100644 index 00000000..a111ae88 --- /dev/null +++ b/docs/chapter10/example1.json @@ -0,0 +1,23 @@ +{ + "ver": 1, + "comp": "chapter10/docs/example1.svg", + "step": 1, + "roots": [13], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "DATA", "label": null}], "proj": {"par": 1, "idx": 2}}, + {"id": 5, "label": "new Point", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.y", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 10, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "Store p.y", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": "Load p.x", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "MEM", "label": null}, {"idx": 2, "def": 12, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter10/example1.svg b/docs/chapter10/example1.svg new file mode 100644 index 00000000..d98e0ccd --- /dev/null +++ b/docs/chapter10/example1.svg @@ -0,0 +1,118 @@ +#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #7 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#9[0] → #1 · ASSOC#10[1] → #8 · MEM#10[2] → #5 · DATA#10[3] → #9 · DATA#11[1] → #10 · MEM#11[2] → #5 · DATA#11[3] → #4 · DATA#12[1] → #11 · MEM#12[2] → #5 · DATA#13[1] → #11 · MEM#13[2] → #12 · DATAStart  #1#1 Start +Type not computed + +$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Point  #5#5 new Point +Type not computed + +[0] → — CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8#8 Store p.y +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #6 DATA0123#3  #9#9 #3 +Type not computed + +[0] → #1 ASSOC0Store p.x  #10#10 Store p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #9 DATA0123Store p.y  #11#11 Store p.y +Type not computed + +[0] → — CTRL +[1] → #10 MEM +[2] → #5 DATA +[3] → #4 DATA0123Load p.x  #12#12 Load p.x +Type not computed + +[0] → — CTRL +[1] → #11 MEM +[2] → #5 DATA +[3] → — DATA0123Return  #13#13 Return +Type not computed + +[0] → — CTRL +[1] → #11 MEM +[2] → #12 DATA012 diff --git a/docs/chapter10/example2a.gv b/docs/chapter10/example2a.gv new file mode 100644 index 00000000..93a8a904 --- /dev/null +++ b/docs/chapter10/example2a.gv @@ -0,0 +1,17 @@ +digraph Memory { + // IR styles match graph/web/render.js; arrows are use -> definition. + graph [bgcolor="#fafbfc" fontname="Helvetica" nodesep=0.35 ranksep=0.55 splines=ortho]; + node [fontname="Helvetica" fontsize=12 color="#758191" fontcolor="#152330" shape=box style="rounded,filled" fillcolor="#edf3f7"]; + edge [fontname="Helvetica" fontsize=9 color="#536477" fontcolor="#364352" arrowsize=0.7 penwidth=1.5]; + + rankdir=RL; + + M [label="Incoming memory" shape=octagon style="filled" fillcolor="#dcecff"]; + A [label="True: Store x" shape=octagon style="filled" fillcolor="#dcecff"]; + B [label="False: Store x" shape=octagon style="filled" fillcolor="#dcecff"]; + P [label="Phi(memory)" shape=hexagon style="filled" fillcolor="#f5e4fa"]; + P -> A -> M [color="#2867b2"]; P -> B -> M [color="#2867b2"]; + P -> Region [style=dashed,color="#9396a3"]; Return -> P [color="#2867b2"]; + Return [shape=box style="filled" fillcolor="#fff1c4"]; + Region [shape=trapezium style="filled" fillcolor="#fff1c4"]; +} diff --git a/docs/chapter10/example2a.json b/docs/chapter10/example2a.json new file mode 100644 index 00000000..660c72e8 --- /dev/null +++ b/docs/chapter10/example2a.json @@ -0,0 +1,26 @@ +{ + "ver": 1, + "comp": "chapter10/docs/example2a.svg", + "step": 1, + "roots": [19], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 5, "label": "new Point", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.y", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "True", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 0}}, + {"id": 11, "label": "False", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 1}}, + {"id": 12, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 13, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 10, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 12, "role": "DATA", "label": null}], "proj": null}, + {"id": 14, "label": "#4", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 15, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 14, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "Phi $mem", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 13, "role": "MEM", "label": null}, {"idx": 2, "def": 15, "role": "MEM", "label": null}], "proj": null}, + {"id": 18, "label": "Load p.x", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 17, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 17, "role": "MEM", "label": null}, {"idx": 2, "def": 18, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter10/example2a.svg b/docs/chapter10/example2a.svg new file mode 100644 index 00000000..b7664907 --- /dev/null +++ b/docs/chapter10/example2a.svg @@ -0,0 +1,130 @@ +#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #7 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#12[0] → #1 · ASSOC#13[0] → #10 · CTRL#13[1] → #8 · MEM#13[2] → #5 · DATA#13[3] → #12 · DATA#14[0] → #1 · ASSOC#15[0] → #11 · CTRL#15[1] → #8 · MEM#15[2] → #5 · DATA#15[3] → #14 · DATA#17[1] → #13 · MEM#17[2] → #15 · MEM#18[1] → #17 · MEM#18[2] → #5 · DATA#19[1] → #17 · MEM#19[2] → #18 · DATAStart  #1#1 Start +Type not computed + +$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMnew Point  #5#5 new Point +Type not computed + +[0] → — CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8#8 Store p.y +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #6 DATA0123True  #10/0#10 True +Projection 0 of #0 +Type not computed + +False  #11/1#11 False +Projection 1 of #0 +Type not computed + +#3  #12#12 #3 +Type not computed + +[0] → #1 ASSOC0Store p.x  #13#13 Store p.x +Type not computed + +[0] → #10 CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #12 DATA0123#4  #14#14 #4 +Type not computed + +[0] → #1 ASSOC0Store p.x  #15#15 Store p.x +Type not computed + +[0] → #11 CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #14 DATA0123Phi $mem  #17#17 Phi $mem +Type not computed + +[0] → — ASSOC +[1] → #13 MEM +[2] → #15 MEM012Load p.x  #18#18 Load p.x +Type not computed + +[0] → — CTRL +[1] → #17 MEM +[2] → #5 DATA +[3] → — DATA0123Return  #19#19 Return +Type not computed + +[0] → — CTRL +[1] → #17 MEM +[2] → #18 DATA012 diff --git a/docs/chapter10/example2b.gv b/docs/chapter10/example2b.gv new file mode 100644 index 00000000..c7d64509 --- /dev/null +++ b/docs/chapter10/example2b.gv @@ -0,0 +1,19 @@ +digraph Memory { + // IR styles match graph/web/render.js; arrows are use -> definition. + graph [bgcolor="#fafbfc" fontname="Helvetica" nodesep=0.35 ranksep=0.55 splines=ortho]; + node [fontname="Helvetica" fontsize=12 color="#758191" fontcolor="#152330" shape=box style="rounded,filled" fillcolor="#edf3f7"]; + edge [fontname="Helvetica" fontsize=9 color="#536477" fontcolor="#364352" arrowsize=0.7 penwidth=1.5]; + + rankdir=RL; + + P [label="Phi(memory)" shape=hexagon style="filled" fillcolor="#f5e4fa"]; + S [label="Loop-body Store" shape=octagon style="filled" fillcolor="#dcecff"]; + P -> Entry [color="#2867b2"]; + P -> S [color="#2867b2",constraint=false]; // Backedge must not place Store before Phi. + S -> P [color="#2867b2"]; + P -> Loop [style=dashed,color="#9396a3"]; Return -> P [color="#2867b2"]; + Return -> S [style=invis]; // Layout only: Phi, Store, Return from left to right. + Return [shape=box style="filled" fillcolor="#fff1c4"]; + Entry [shape=octagon style="filled" fillcolor="#dcecff"]; + Loop [shape=box style="rounded,filled" fillcolor="#ffe0ab"]; +} diff --git a/docs/chapter10/example2b.json b/docs/chapter10/example2b.json new file mode 100644 index 00000000..da2fc557 --- /dev/null +++ b/docs/chapter10/example2b.json @@ -0,0 +1,27 @@ +{ + "ver": 1, + "comp": "chapter10/docs/example2b.svg", + "step": 1, + "roots": [19], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "DATA", "label": null}], "proj": {"par": 1, "idx": 2}}, + {"id": 5, "label": "new Point", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.y", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "Phi $mem", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 15, "role": "MEM", "label": null}], "proj": null}, + {"id": 11, "label": "Phi arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 17, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "True", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 0}}, + {"id": 14, "label": "False", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 1}}, + {"id": 15, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 13, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 17, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 18, "label": "Load p.x", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 14, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 18, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter10/example2b.svg b/docs/chapter10/example2b.svg new file mode 100644 index 00000000..1feb91a3 --- /dev/null +++ b/docs/chapter10/example2b.svg @@ -0,0 +1,135 @@ +#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #7 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#10[1] → #8 · MEM#10[2] → #15 · MEM#11[1] → #4 · DATA#11[2] → #17 · DATA#15[0] → #13 · CTRL#15[1] → #10 · MEM#15[2] → #5 · DATA#15[3] → #11 · DATA#16[0] → #1 · ASSOC#17[1] → #11 · DATA#17[2] → #16 · DATA#18[0] → #14 · CTRL#18[1] → #10 · MEM#18[2] → #5 · DATA#19[1] → #10 · MEM#19[2] → #18 · DATAStart  #1#1 Start +Type not computed + +$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Point  #5#5 new Point +Type not computed + +[0] → — CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8#8 Store p.y +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #6 DATA0123Phi $mem  #10#10 Phi $mem +Type not computed + +[0] → — ASSOC +[1] → #8 MEM +[2] → #15 MEM012Phi arg  #11#11 Phi arg +Type not computed + +[0] → — ASSOC +[1] → #4 DATA +[2] → #17 DATA012True  #13/0#13 True +Projection 0 of #0 +Type not computed + +False  #14/1#14 False +Projection 1 of #0 +Type not computed + +Store p.x  #15#15 Store p.x +Type not computed + +[0] → #13 CTRL +[1] → #10 MEM +[2] → #5 DATA +[3] → #11 DATA0123#1  #16#16 #1 +Type not computed + +[0] → #1 ASSOC0-  #17#17 - +Type not computed + +[0] → — CTRL +[1] → #11 DATA +[2] → #16 DATA012Load p.x  #18#18 Load p.x +Type not computed + +[0] → #14 CTRL +[1] → #10 MEM +[2] → #5 DATA +[3] → — DATA0123Return  #19#19 Return +Type not computed + +[0] → — CTRL +[1] → #10 MEM +[2] → #18 DATA012 diff --git a/docs/chapter10/example2c.gv b/docs/chapter10/example2c.gv new file mode 100644 index 00000000..f3a52b4d --- /dev/null +++ b/docs/chapter10/example2c.gv @@ -0,0 +1,14 @@ +digraph Memory { + // IR styles match graph/web/render.js; arrows are use -> definition. + graph [bgcolor="#fafbfc" fontname="Helvetica" nodesep=0.35 ranksep=0.55 splines=ortho]; + node [fontname="Helvetica" fontsize=12 color="#758191" fontcolor="#152330" shape=box style="rounded,filled" fillcolor="#edf3f7"]; + edge [fontname="Helvetica" fontsize=9 color="#536477" fontcolor="#364352" arrowsize=0.7 penwidth=1.5]; + + rankdir=RL; + + M [label="Prior memory" shape=octagon style="filled" fillcolor="#dcecff"]; + L [label="Load p.x" shape=box style="rounded,filled" fillcolor="#edf3f7"]; + S [label="Store p.x" shape=octagon style="filled" fillcolor="#dcecff"]; + L -> M [color="#2867b2"]; S -> M [color="#2867b2"]; + S -> L [style=dashed,xlabel="execute load first"]; +} diff --git a/docs/chapter10/example2c.json b/docs/chapter10/example2c.json new file mode 100644 index 00000000..8623ab8d --- /dev/null +++ b/docs/chapter10/example2c.json @@ -0,0 +1,21 @@ +{ + "ver": 1, + "comp": "chapter10/docs/example2c.svg", + "step": 1, + "roots": [11], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "DATA", "label": null}], "proj": {"par": 1, "idx": 2}}, + {"id": 5, "label": "new Point", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.y", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "Load p.x", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter10/example2c.svg b/docs/chapter10/example2c.svg new file mode 100644 index 00000000..f7f7bce3 --- /dev/null +++ b/docs/chapter10/example2c.svg @@ -0,0 +1,109 @@ +#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #7 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#9[1] → #8 · MEM#9[2] → #5 · DATA#10[1] → #8 · MEM#10[2] → #5 · DATA#10[3] → #4 · DATA#11[1] → #10 · MEM#11[2] → #9 · DATAStart  #1#1 Start +Type not computed + +$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Point  #5#5 new Point +Type not computed + +[0] → — CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8#8 Store p.y +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #6 DATA0123Load p.x  #9#9 Load p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → — DATA0123Store p.x  #10#10 Store p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #4 DATA0123Return  #11#11 Return +Type not computed + +[0] → — CTRL +[1] → #10 MEM +[2] → #9 DATA012 diff --git a/docs/chapter10/lattice.gv b/docs/chapter10/lattice.gv new file mode 100644 index 00000000..b56a3073 --- /dev/null +++ b/docs/chapter10/lattice.gv @@ -0,0 +1,127 @@ +digraph Lattice { + rankdir=TB; + newrank=true; + // Preserve the same-rank ordering edges through cluster layout. + remincross=false; + nodesep=0.22; + ranksep=0.65; + node [shape=ellipse, style=filled, fontname="DejaVu Sans", fontsize=13]; + edge [color="#555555", arrowsize=0.6]; + + // These arrows are lattice-order edges, not use/definition edges. + TOP [label="⊤", fillcolor=black, fontcolor=white]; + BOT [label="⊥", fillcolor=black, fontcolor=white]; + + subgraph cluster_control { + label="Control"; fontname="Arial"; color="#cccccc"; + node [fillcolor="#ffff00"]; + XCTRL [label="⊤:ctrl"]; + CTRL [label="⊥:ctrl"]; + XCTRL -> CTRL; + } + + subgraph cluster_integer { + label="Integer"; fontname="Arial"; color="#cccccc"; + node [fillcolor="#add8e6"]; + INT_TOP [label="⊤:int"]; + INT_BOT [label="⊥:int"]; + INT_NEG [label="… −2, −1"]; + INT_ZERO [label="0"]; + INT_POS [label="1, 2, …"]; + {rank=same; INT_NEG; INT_ZERO; INT_POS;} + INT_NEG -> INT_ZERO -> INT_POS [style=invis]; + INT_TOP -> {INT_NEG INT_ZERO INT_POS}; + {INT_NEG INT_ZERO INT_POS} -> INT_BOT; + } + + subgraph cluster_pointer { + label="Pointer = nullability × struct type"; + fontname="Arial"; color="#cccccc"; + node [fillcolor="#008000", fontcolor=white]; + PTR_TOP [label="⊤:ptr\n[*⊤:struct]"]; + PTR_BOT [label="⊥:ptr\n[*⊥:struct?]"]; + PTR_NULL [label="null"]; + PTR_ANY [label="*⊥:struct\n[ptr any struct]"]; + PTR_PERSON [label="*Person"]; + PTR_S1 [label="*s1"]; + PTR_MORE [label="*s2, …"]; + PTR_PERSON_NIL [label="*Person?"]; + PTR_S1_NIL [label="*s1?"]; + PTR_MORE_NIL [label="*s2?, …"]; + {rank=same; PTR_PERSON; PTR_S1; PTR_MORE; PTR_NULL;} + {rank=same; PTR_ANY; PTR_PERSON_NIL; PTR_S1_NIL; PTR_MORE_NIL;} + PTR_PERSON -> PTR_S1 -> PTR_MORE -> PTR_NULL [style=invis]; + PTR_ANY -> PTR_PERSON_NIL -> PTR_S1_NIL -> PTR_MORE_NIL [style=invis]; + PTR_TOP -> {PTR_PERSON PTR_S1 PTR_MORE PTR_NULL}; + {PTR_PERSON PTR_S1 PTR_MORE} -> PTR_ANY; + PTR_PERSON -> PTR_PERSON_NIL; + PTR_S1 -> PTR_S1_NIL; + PTR_MORE -> PTR_MORE_NIL; + PTR_NULL -> {PTR_PERSON_NIL PTR_S1_NIL PTR_MORE_NIL}; + {PTR_ANY PTR_PERSON_NIL PTR_S1_NIL PTR_MORE_NIL} -> PTR_BOT; + } + + subgraph cluster_struct { + label="Struct\nnamed collection of named scalar types"; + fontname="Arial"; color="#cccccc"; + node [fillcolor="#90ee90"]; + STRUCT_TOP [label="⊤:struct\n[struct top]"]; + STRUCT_BOT [label="⊥:struct\n[struct bottom]"]; + STRUCT_PERSON [label="Person\nage: int", shape=box]; + STRUCT_S1 [label="s1\nx: int", shape=box]; + STRUCT_S2 [label="s2\nx: int, y: int", shape=box]; + STRUCT_MORE [label="…", shape=box]; + {rank=same; STRUCT_PERSON; STRUCT_S1; STRUCT_S2; STRUCT_MORE;} + STRUCT_PERSON -> STRUCT_S1 -> STRUCT_S2 -> STRUCT_MORE [style=invis]; + STRUCT_TOP -> {STRUCT_PERSON STRUCT_S1 STRUCT_S2 STRUCT_MORE}; + {STRUCT_PERSON STRUCT_S1 STRUCT_S2 STRUCT_MORE} -> STRUCT_BOT; + } + + subgraph cluster_memory { + label="Memory"; fontname="Arial"; color="#cccccc"; + node [fillcolor="#00008b", fontcolor=white]; + MEM_TOP [label="⊤:mem"]; + MEM_BOT [label="⊥:mem"]; + MEM_TOP -> MEM_BOT; + } + + subgraph cluster_tuple { + label="Tuple\ncollection of types"; + fontname="Arial"; color="#cccccc"; + node [fillcolor="#ffc0cb"]; + TUPLE_TOP [label="⊤:tuple"]; + TUPLE_BOT [label="⊥:tuple"]; + // Each black element stands for a recursively nested type lattice. + TUPLE1 [shape=plain, label=< + + + +
tuple
type
+ >]; + TUPLE2 [shape=plain, label=< + + + + +
tuple
type
type
+ >]; + TUPLEN [shape=plain, label=< + + + + + +
tuple
type
…
type
+ >]; + {rank=same; TUPLE1; TUPLE2; TUPLEN;} + TUPLE1 -> TUPLE2 -> TUPLEN [style=invis]; + TUPLE_TOP -> {TUPLE1 TUPLE2 TUPLEN}; + {TUPLE1 TUPLE2 TUPLEN} -> TUPLE_BOT; + } + + TOP -> {XCTRL INT_TOP PTR_TOP STRUCT_TOP MEM_TOP TUPLE_TOP}; + {CTRL INT_BOT PTR_BOT STRUCT_BOT MEM_BOT TUPLE_BOT} -> BOT; + {rank=same; XCTRL; INT_TOP; PTR_TOP; STRUCT_TOP; MEM_TOP; TUPLE_TOP;} + {rank=same; CTRL; INT_BOT; PTR_BOT; STRUCT_BOT; MEM_BOT; TUPLE_BOT;} + XCTRL -> INT_TOP -> PTR_TOP -> STRUCT_TOP -> MEM_TOP -> TUPLE_TOP [style=invis]; +} diff --git a/docs/chapter10/lattice.svg b/docs/chapter10/lattice.svg new file mode 100644 index 00000000..006ab762 --- /dev/null +++ b/docs/chapter10/lattice.svg @@ -0,0 +1,593 @@ + + + + + + +Lattice + + +cluster_control + +Control + + +cluster_integer + +Integer + + +cluster_pointer + +Pointer = nullability × struct type + + +cluster_struct + +Struct +named collection of named scalar types + + +cluster_memory + +Memory + + +cluster_tuple + +Tuple +collection of types + + + +TOP + +⊤ + + + +XCTRL + +⊤:ctrl + + + +TOP->XCTRL + + + + + +INT_TOP + +⊤:int + + + +TOP->INT_TOP + + + + + +PTR_TOP + +⊤:ptr +[*⊤:struct] + + + +TOP->PTR_TOP + + + + + +STRUCT_TOP + +⊤:struct +[struct top] + + + +TOP->STRUCT_TOP + + + + + +MEM_TOP + +⊤:mem + + + +TOP->MEM_TOP + + + + + +TUPLE_TOP + +⊤:tuple + + + +TOP->TUPLE_TOP + + + + + +BOT + +⊥ + + + +CTRL + +⊥:ctrl + + + +XCTRL->CTRL + + + + + + +CTRL->BOT + + + + + +INT_NEG + +… −2, −1 + + + +INT_TOP->INT_NEG + + + + + +INT_ZERO + +0 + + + +INT_TOP->INT_ZERO + + + + + +INT_POS + +1, 2, … + + + +INT_TOP->INT_POS + + + + + + +INT_BOT + +⊥:int + + + +INT_BOT->BOT + + + + + +INT_NEG->INT_BOT + + + + + + +INT_ZERO->INT_BOT + + + + + + +INT_POS->INT_BOT + + + + + +PTR_NULL + +null + + + +PTR_TOP->PTR_NULL + + + + + +PTR_PERSON + +*Person + + + +PTR_TOP->PTR_PERSON + + + + + +PTR_S1 + +*s1 + + + +PTR_TOP->PTR_S1 + + + + + +PTR_MORE + +*s2, … + + + +PTR_TOP->PTR_MORE + + + + + + +PTR_BOT + +⊥:ptr +[*⊥:struct?] + + + +PTR_BOT->BOT + + + + + +PTR_PERSON_NIL + +*Person? + + + +PTR_NULL->PTR_PERSON_NIL + + + + + +PTR_S1_NIL + +*s1? + + + +PTR_NULL->PTR_S1_NIL + + + + + +PTR_MORE_NIL + +*s2?, … + + + +PTR_NULL->PTR_MORE_NIL + + + + + +PTR_ANY + +*⊥:struct +[ptr any struct] + + + +PTR_ANY->PTR_BOT + + + + + + +PTR_PERSON->PTR_ANY + + + + + + +PTR_PERSON->PTR_PERSON_NIL + + + + + +PTR_S1->PTR_ANY + + + + + + +PTR_S1->PTR_S1_NIL + + + + + + +PTR_MORE->PTR_ANY + + + + + +PTR_MORE->PTR_MORE_NIL + + + + + +PTR_PERSON_NIL->PTR_BOT + + + + + + +PTR_S1_NIL->PTR_BOT + + + + + + +PTR_MORE_NIL->PTR_BOT + + + + + +STRUCT_PERSON + +Person +age: int + + + +STRUCT_TOP->STRUCT_PERSON + + + + + +STRUCT_S1 + +s1 +x: int + + + +STRUCT_TOP->STRUCT_S1 + + + + + +STRUCT_S2 + +s2 +x: int, y: int + + + +STRUCT_TOP->STRUCT_S2 + + + + + +STRUCT_MORE + +… + + + +STRUCT_TOP->STRUCT_MORE + + + + + + +STRUCT_BOT + +⊥:struct +[struct bottom] + + + +STRUCT_BOT->BOT + + + + + +STRUCT_PERSON->STRUCT_BOT + + + + + + +STRUCT_S1->STRUCT_BOT + + + + + + +STRUCT_S2->STRUCT_BOT + + + + + + +STRUCT_MORE->STRUCT_BOT + + + + + +MEM_BOT + +⊥:mem + + + +MEM_TOP->MEM_BOT + + + + + + +MEM_BOT->BOT + + + + + +TUPLE1 + + + +tuple + + +type + + + +TUPLE_TOP->TUPLE1 + + + + + +TUPLE2 + + + +tuple + + +type + + +type + + + +TUPLE_TOP->TUPLE2 + + + + + +TUPLEN + + + +tuple + + +type + + +… + + +type + + + +TUPLE_TOP->TUPLEN + + + + + +TUPLE_BOT + +⊥:tuple + + + +TUPLE_BOT->BOT + + + + + +TUPLE1->TUPLE_BOT + + + + + + +TUPLE2->TUPLE_BOT + + + + + + +TUPLEN->TUPLE_BOT + + + + + diff --git a/docs/chapter10/load-after-store-after.json b/docs/chapter10/load-after-store-after.json new file mode 100644 index 00000000..d27efe5b --- /dev/null +++ b/docs/chapter10/load-after-store-after.json @@ -0,0 +1,19 @@ +{ + "ver": 1, + "comp": "load-after-store-after", + "step": 1, + "roots": [10], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "DATA", "label": null}], "proj": {"par": 1, "idx": 2}}, + {"id": 5, "label": "new Box", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 4, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter10/load-after-store-after.svg b/docs/chapter10/load-after-store-after.svg new file mode 100644 index 00000000..78867d38 --- /dev/null +++ b/docs/chapter10/load-after-store-after.svg @@ -0,0 +1,97 @@ +#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #7 · MEM#8[2] → #5 · DATA#8[3] → #4 · DATA#10[1] → #8 · MEM#10[2] → #4 · DATAStart  #1#1 Start +Type not computed + +$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Box  #5#5 new Box +Type not computed + +[0] → — CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.x  #8#8 Store p.x +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #4 DATA0123Return  #10#10 Return +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #4 DATA012 diff --git a/docs/chapter10/load-after-store-before.json b/docs/chapter10/load-after-store-before.json new file mode 100644 index 00000000..ba4e2e0b --- /dev/null +++ b/docs/chapter10/load-after-store-before.json @@ -0,0 +1,20 @@ +{ + "ver": 1, + "comp": "load-after-store-before", + "step": 1, + "roots": [10], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 1, "role": "MEM", "label": null}], "proj": {"par": 1, "idx": 1}}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "DATA", "label": null}], "proj": {"par": 1, "idx": 2}}, + {"id": 5, "label": "new Box", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.x", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "Load p.x", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter10/load-after-store-before.svg b/docs/chapter10/load-after-store-before.svg new file mode 100644 index 00000000..497c915d --- /dev/null +++ b/docs/chapter10/load-after-store-before.svg @@ -0,0 +1,103 @@ +#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #7 · MEM#8[2] → #5 · DATA#8[3] → #4 · DATA#9[1] → #8 · MEM#9[2] → #5 · DATA#10[1] → #8 · MEM#10[2] → #9 · DATAStart  #1#1 Start +Type not computed + +$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Box  #5#5 new Box +Type not computed + +[0] → — CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.x  #8#8 Store p.x +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #4 DATA0123Load p.x  #9#9 Load p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → — DATA0123Return  #10#10 Return +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #9 DATA012 diff --git a/docs/chapter10/type-control.svg b/docs/chapter10/type-control.svg new file mode 100644 index 00000000..d4b79c53 --- /dev/null +++ b/docs/chapter10/type-control.svg @@ -0,0 +1,5 @@ + + Control + + Control + diff --git a/docs/chapter10/type-integer.svg b/docs/chapter10/type-integer.svg new file mode 100644 index 00000000..97d03372 --- /dev/null +++ b/docs/chapter10/type-integer.svg @@ -0,0 +1,5 @@ + + Integer + + Integer + diff --git a/docs/chapter10/type-memory.svg b/docs/chapter10/type-memory.svg new file mode 100644 index 00000000..16b5121f --- /dev/null +++ b/docs/chapter10/type-memory.svg @@ -0,0 +1,5 @@ + + Memory + + Memory + diff --git a/docs/chapter10/type-pointer.svg b/docs/chapter10/type-pointer.svg new file mode 100644 index 00000000..7604492e --- /dev/null +++ b/docs/chapter10/type-pointer.svg @@ -0,0 +1,5 @@ + + Pointer + + Pointer + diff --git a/docs/chapter10/type-struct.svg b/docs/chapter10/type-struct.svg new file mode 100644 index 00000000..97a16562 --- /dev/null +++ b/docs/chapter10/type-struct.svg @@ -0,0 +1,5 @@ + + Struct + + Struct + diff --git a/docs/chapter10/type-tuple.svg b/docs/chapter10/type-tuple.svg new file mode 100644 index 00000000..691478ac --- /dev/null +++ b/docs/chapter10/type-tuple.svg @@ -0,0 +1,5 @@ + + Tuple + + Tuple + -- cgit v1.2.3