diff options
Diffstat (limited to 'docs')
29 files changed, 2595 insertions, 0 deletions
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章で取り除きます。 + + + +グラフは局所的な畳み込み前の依存関係を示しています。メモリに注目するため、制御エッジの大部分を省略し、合流が重要な箇所に最小限の 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; +``` + + + +ループには第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; +``` + + + +すべての Return は現在のメモリ全体の値を消費します。返されるスカラーがストアに依存しない場合や、プログラムが変更したオブジェクト自体を返す場合でも、これによってストアが生き残ります。 + +## 拡張された型の束 + +この章では、Simple の型の束を大きく改訂します。 + + + +図では **トップ** に `⊤`、**ボトム** に `⊥` を使います。接尾辞は領域を表します。`⊤:struct` は*構造体トップ*で、単独の `⊤` は全体のトップです。本文ではこれらの言葉を使い、コード例では実際の Java 定数を使います。実装の `$TOP` と `$BOT` という名前を図に表示する必要はありません。 + +| 図 | 本文 | Java 定数 | 内部の構造体名 | +|---|---|---|---| +| `⊤:struct` | 構造体トップ | `TypeStruct.TOP` | `$TOP` | +| `⊥:struct` | 構造体ボトム | `TypeStruct.BOT` | `$BOT` | + +図のエッジは束の順序を示し、トップはボトムの上にあります。省略記号を含む箱は、さらに並列の選択肢があることを省略して示すもので、追加の共用体型ではありません。フィールドとタプル要素の型の束は省略しています。フィールドの型には任意のスカラー型（Integer または Pointer）を使え、Tuple の型には Control や Memory を含む*任意の*束の型を使えます。 + +型の束には、以下の領域があります。 + +*  は制御フローを表します。制御トップは到達不能な制御、制御ボトムは到達可能な制御です。 +*  には整数トップ、整数ボトムと、その間に並列に配置された定数があります。省略記号はほかの整数定数を表します。 +* （新規）は構造体の型と 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` 型ではありません。 + +* （新規）は、ユーザー定義の名前付き構造体を表します。この章のフィールドは整数型です。 + * 構造体トップはすべての名前付き構造体の上に、構造体ボトムはすべての名前付き構造体の下にあります。トップは高位の空の構造体の選択肢で、ボトムは保守的に任意の構造体名を含みます。 + * `Person`、`s1`、`s2`、さらにほかの名前は、並列の選択肢です。継承はないため、異なる名前の構造体は、同じフィールドを持っていても互いの下に入りません。 + * プログラムが宣言できる名前に固定の上限はありません。図の省略記号は、特別な無名構造体ではなく、さらに名前付きの選択肢があることを示します。各名前付きの箱は、それぞれのフィールド型の束を省略して表しています。 +* （新規）はメモリ全体のトークンを表します。メモリトップとメモリボトムは `TypeMem.TOP` と `TypeMem.BOT` です。どちらも個別のフィールドに格納された値を記録しません。 +*  は、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 の結果入力は 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 を先に実行しなければなりません。両者の間に通常のデータエッジはありません。 + + + +このスケジューラは本章の実行には十分です。第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. + + + +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; +``` + + + +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; +``` + + + +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. + + + +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: + +*  represents control flow: unreachable control + at control top, and reachable control at control bottom. +*  has integer top, integer bottom, and parallel + constants between them. The ellipses stand for the other integer constants. +*  (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. + +*  (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. +*  (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. +*  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 | +|---|---| +|  |  | + +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. + + + +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 @@ +<svg aria-label="Compiler graph" width="621" height="766" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 621 766" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge ASSOC" id="e6i0" d="M419,46 C419,70 84,41 84,65" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#6[0] → #1 · ASSOC</title></path><path class="edge MEM" id="e7i1" d="M236,118 L236,166" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#7[1] → #3 · MEM</title></path><path class="edge DATA" id="e7i2" d="M514,118 L514,123 Q514,128 509,128 L268,128 Q260,128 260,136 L260,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[2] → #5 · DATA</title></path><path class="edge DATA" id="e7i3" d="M84,118 L84,130 Q84,138 92,138 L276,138 Q284,138 284,146 L284,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[3] → #6 · DATA</title></path><path class="edge MEM" id="e8i1" d="M248,222 L248,227 Q248,232 253,232 L273,232 Q281,232 281,240 L281,270" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#8[1] → #7 · MEM</title></path><path class="edge DATA" id="e8i2" d="M514,118 L514,123 Q514,128 509,128 L326,128 Q318,128 318,136 L318,225.5 Q318,232 311.5,232 L311.5,232 Q305,232 305,238.5 L305,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #5 · DATA</title></path><path class="edge DATA" id="e8i3" d="M84,118 L84,130 Q84,138 92,138 L321,138 Q329,138 329,146 L329,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[3] → #6 · DATA</title></path><path class="edge ASSOC" id="e9i0" d="M419,46 C419,70 434,249 434,273" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#9[0] → #1 · ASSOC</title></path><path class="edge MEM" id="e10i1" d="M293,326 L293,331 Q293,336 298,336 L331,336 Q339,336 339,344 L339,374" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#10[1] → #8 · MEM</title></path><path class="edge DATA" id="e10i2" d="M514,118 L514,123 Q514,128 509,128 L509,128 Q504,128 504,133 L504,224 Q504,232 496,232 L371,232 Q363,232 363,240 L363,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#10[2] → #5 · DATA</title></path><path class="edge DATA" id="e10i3" d="M434,326 L434,331 Q434,336 429,336 L395,336 Q387,336 387,344 L387,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#10[3] → #9 · DATA</title></path><path class="edge MEM" id="e11i1" d="M351,430 L351,435 Q351,440 356,440 L459,440 Q467,440 467,448 L467,478" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#11[1] → #10 · MEM</title></path><path class="edge DATA" id="e11i2" d="M514,118 L514,123 Q514,128 509,128 L509,128 Q504,128 504,133 L504,433.5 Q504,440 497.5,440 L497.5,440 Q491,440 491,446.5 L491,478" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#11[2] → #5 · DATA</title></path><path class="edge DATA" id="e11i3" d="M356,118 L356,130 Q356,138 364,138 L507,138 Q515,138 515,146 L515,478" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#11[3] → #4 · DATA</title></path><path class="edge MEM" id="e12i1" d="M479,534 L479,539 Q479,544 484,544 L517,544 Q525,544 525,552 L525,582" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#12[1] → #11 · MEM</title></path><path class="edge DATA" id="e12i2" d="M514,118 L514,123 Q514,128 519,128 L541,128 Q549,128 549,136 L549,582" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#12[2] → #5 · DATA</title></path><path class="edge MEM" id="e13i1" d="M479,534 L479,539 Q479,544 474,544 L472.5,544 Q466,544 466,550.5 L466,686" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#13[1] → #11 · MEM</title></path><path class="edge DATA" id="e13i2" d="M537,638 L537,643 Q537,648 532,648 L504,648 Q496,648 496,656 L496,686" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#13[2] → #12 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(176,24)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>Start</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#1 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" transform="translate(176,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$mem</tspan><tspan class="node-id"> #3/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEM</title></g><g class="node" id="n4" data-id="4" transform="translate(296,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>arg</tspan><tspan class="node-id"> #4/2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATA</title></g><g class="node" id="n5" data-id="5" transform="translate(454,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>new Point</tspan><tspan class="node-id"> #5</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 new Point +Type not computed + +[0] → — CTRL</title><circle class="port" cx="60" cy="-3" r="3" fill="white"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n6" data-id="6" transform="translate(24,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#0</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 #0 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n7" data-id="7" transform="translate(188,172)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.x</tspan><tspan class="node-id"> #7</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n8" data-id="8" transform="translate(233,276)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.y</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 Store p.y +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #6 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n9" data-id="9" transform="translate(374,276)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#3</tspan><tspan class="node-id"> #9</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#9 #3 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n10" data-id="10" transform="translate(291,380)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.x</tspan><tspan class="node-id"> #10</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#10 Store p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #9 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n11" data-id="11" transform="translate(419,484)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.y</tspan><tspan class="node-id"> #11</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#11 Store p.y +Type not computed + +[0] → — CTRL +[1] → #10 MEM +[2] → #5 DATA +[3] → #4 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n12" data-id="12" transform="translate(477,588)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Load p.x</tspan><tspan class="node-id"> #12</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#12 Load p.x +Type not computed + +[0] → — CTRL +[1] → #11 MEM +[2] → #5 DATA +[3] → — DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="white"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n13" data-id="13" transform="translate(406,692)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #13</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#13 Return +Type not computed + +[0] → — CTRL +[1] → #11 MEM +[2] → #12 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> 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 @@ +<svg aria-label="Compiler graph" width="740" height="766" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 740 766" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge ASSOC" id="e6i0" d="M162,46 C162,70 409,41 409,65" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#6[0] → #1 · ASSOC</title></path><path class="edge MEM" id="e7i1" d="M99,118 L99,130 Q99,138 107,138 L167,138 Q175,138 175,146 L175,166" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#7[1] → #3 · MEM</title></path><path class="edge DATA" id="e7i2" d="M257,118 L257,123 Q257,128 252,128 L207,128 Q199,128 199,136 L199,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[2] → #5 · DATA</title></path><path class="edge DATA" id="e7i3" d="M409,118 L409,130 Q409,138 401,138 L231,138 Q223,138 223,146 L223,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[3] → #6 · DATA</title></path><path class="edge MEM" id="e8i1" d="M187,222 L187,227 Q187,232 182,232 L181,232 Q175,232 175,238 L175,270" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#8[1] → #7 · MEM</title></path><path class="edge DATA" id="e8i2" d="M257,118 L257,224 Q257,232 249,232 L207,232 Q199,232 199,240 L199,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #5 · DATA</title></path><path class="edge DATA" id="e8i3" d="M409,118 L409,234 Q409,242 401,242 L231,242 Q223,242 223,250 L223,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[3] → #6 · DATA</title></path><path class="edge ASSOC" id="e12i0" d="M162,46 C162,70 339,249 339,273" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#12[0] → #1 · ASSOC</title></path><path class="edge CTRL" id="e13i0" d="M65,326 L65,374" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#13[0] → #10 · CTRL</title></path><path class="edge MEM" id="e13i1" d="M187,326 L187,331 Q187,336 182,336 L97,336 Q89,336 89,344 L89,374" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#13[1] → #8 · MEM</title></path><path class="edge DATA" id="e13i2" d="M257,118 L257,123 Q257,128 252,128 L124,128 Q116,128 116,136 L116,344.5 Q116,346 114.5,346 L114.5,346 Q113,346 113,347.5 L113,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#13[2] → #5 · DATA</title></path><path class="edge DATA" id="e13i3" d="M339,326 L339,338 Q339,346 331,346 L145,346 Q137,346 137,354 L137,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#13[3] → #12 · DATA</title></path><path class="edge ASSOC" id="e14i0" d="M162,46 C162,70 598,249 598,273" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#14[0] → #1 · ASSOC</title></path><path class="edge CTRL" id="e15i0" d="M474,326 L474,374" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#15[0] → #11 · CTRL</title></path><path class="edge MEM" id="e15i1" d="M187,326 L187,331 Q187,336 192,336 L490,336 Q498,336 498,344 L498,374" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#15[1] → #8 · MEM</title></path><path class="edge DATA" id="e15i2" d="M257,118 L257,123 Q257,128 262,128 L519,128 Q527,128 527,136 L527,333.5 Q527,336 524.5,336 L524.5,336 Q522,336 522,338.5 L522,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#15[2] → #5 · DATA</title></path><path class="edge DATA" id="e15i3" d="M598,326 L598,331 Q598,336 593,336 L554,336 Q546,336 546,344 L546,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#15[3] → #14 · DATA</title></path><path class="edge MEM" id="e17i1" d="M101,430 L101,442 Q101,450 109,450 L557,450 Q565,450 565,458 L565,478" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#17[1] → #13 · MEM</title></path><path class="edge MEM" id="e17i2" d="M510,430 L510,435 Q510,440 515,440 L597,440 Q605,440 605,448 L605,478" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#17[2] → #15 · MEM</title></path><path class="edge MEM" id="e18i1" d="M585,534 L585,539 Q585,544 590,544 L636,544 Q644,544 644,552 L644,582" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#18[1] → #17 · MEM</title></path><path class="edge DATA" id="e18i2" d="M257,118 L257,123 Q257,128 262,128 L519,128 Q527,128 527,136 L527,224 Q527,232 535,232 L660,232 Q668,232 668,240 L668,582" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[2] → #5 · DATA</title></path><path class="edge MEM" id="e19i1" d="M585,534 L585,686" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#19[1] → #17 · MEM</title></path><path class="edge DATA" id="e19i2" d="M656,638 L656,643 Q656,648 651,648 L623,648 Q615,648 615,656 L615,686" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#19[2] → #18 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(39,24)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Start</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" transform="translate(39,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$mem</tspan><tspan class="node-id"> #3/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEM</title></g><g class="node" id="n5" data-id="5" transform="translate(197,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>new Point</tspan><tspan class="node-id"> #5</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 new Point +Type not computed + +[0] → — CTRL</title><circle class="port" cx="60" cy="-3" r="3" fill="white"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n6" data-id="6" transform="translate(349,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#0</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 #0 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n7" data-id="7" transform="translate(127,172)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.x</tspan><tspan class="node-id"> #7</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n8" data-id="8" transform="translate(127,276)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.y</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 Store p.y +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #6 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n10" data-id="10" transform="translate(24,294)" style="opacity: 1;"><path class="box" d="M0,0H82V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="41" y="17"><tspan>True</tspan><tspan class="node-id"> #10/0</tspan></text><text class="type" text-anchor="middle" y="35" x="41"/><title>#10 True +Projection 0 of #0 +Type not computed + +</title></g><g class="node" id="n11" data-id="11" transform="translate(431,294)" style="opacity: 1;"><path class="box" d="M0,0H86V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="43" y="17"><tspan>False</tspan><tspan class="node-id"> #11/1</tspan></text><text class="type" text-anchor="middle" y="35" x="43"/><title>#11 False +Projection 1 of #0 +Type not computed + +</title></g><g class="node" id="n12" data-id="12" transform="translate(279,276)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#3</tspan><tspan class="node-id"> #12</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#12 #3 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n13" data-id="13" transform="translate(41,380)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.x</tspan><tspan class="node-id"> #13</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#13 Store p.x +Type not computed + +[0] → #10 CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #12 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="#536477"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n14" data-id="14" transform="translate(538,276)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#4</tspan><tspan class="node-id"> #14</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#14 #4 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n15" data-id="15" transform="translate(450,380)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.x</tspan><tspan class="node-id"> #15</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#15 Store p.x +Type not computed + +[0] → #11 CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #14 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="#536477"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n17" data-id="17" transform="translate(525,484)" style="opacity: 1;"><path class="box" d="M12,0H108L120,22L108,44H12L0,22Z" fill="#f5e4fa"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Phi $mem</tspan><tspan class="node-id"> #17</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#17 Phi $mem +Type not computed + +[0] → — ASSOC +[1] → #13 MEM +[2] → #15 MEM</title><circle class="port" cx="0" cy="-3" r="3" fill="white"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="0" y="-10" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n18" data-id="18" transform="translate(596,588)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Load p.x</tspan><tspan class="node-id"> #18</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#18 Load p.x +Type not computed + +[0] → — CTRL +[1] → #17 MEM +[2] → #5 DATA +[3] → — DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="white"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n19" data-id="19" transform="translate(525,692)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #19</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#19 Return +Type not computed + +[0] → — CTRL +[1] → #17 MEM +[2] → #18 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> 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 @@ +<svg aria-label="Compiler graph" width="647" height="664" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 647 664" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge ASSOC" id="e6i0" d="M316,46 C316,70 563,41 563,65" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#6[0] → #1 · ASSOC</title></path><path class="edge MEM" id="e7i1" d="M133,118 L133,140 Q133,148 141,148 L462,148 Q470,148 470,156 L470,168" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#7[1] → #3 · MEM</title></path><path class="edge DATA" id="e7i2" d="M411,118 L411,130 Q411,138 419,138 L486,138 Q494,138 494,146 L494,168" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[2] → #5 · DATA</title></path><path class="edge DATA" id="e7i3" d="M563,118 L563,140 Q563,148 555,148 L526,148 Q518,148 518,156 L518,168" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[3] → #6 · DATA</title></path><path class="edge MEM" id="e8i1" d="M482,224 L482,229 Q482,234 487,234 L487,234 Q492,234 492,239 L492,272" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#8[1] → #7 · MEM</title></path><path class="edge DATA" id="e8i2" d="M411,118 L411,130 Q411,138 419,138 L544,138 Q552,138 552,146 L552,226 Q552,234 544,234 L524,234 Q516,234 516,242 L516,272" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #5 · DATA</title></path><path class="edge DATA" id="e8i3" d="M563,118 L563,236 Q563,244 555,244 L548,244 Q540,244 540,252 L540,272" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[3] → #6 · DATA</title></path><path class="edge MEM" id="e10i1" d="M504,328 L504,340 Q504,348 496,348 L385,348 Q377,348 377,356 L377,376" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#10[1] → #8 · MEM</title></path><path class="edge MEM" id="e10i2" d="M101,536 L101,541 Q101,546 106,546 L459,546 Q467,546 467,538 L467,366 Q467,358 459,358 L425,358 Q417,358 417,366 L417,376" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#10[2] → #15 · MEM</title></path><path class="edge DATA" id="e11i1" d="M253,118 L253,123 Q253,128 248,128 L178,128 Q170,128 170,136 L170,168" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#11[1] → #4 · DATA</title></path><path class="edge DATA" id="e11i2" d="M312,328 L312,333 Q312,338 317,338 L404,338 Q412,338 412,330 L412,166 Q412,158 404,158 L215,158 Q210,158 210,163 L210,168" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#11[2] → #17 · DATA</title></path><path class="edge CTRL" id="e15i0" d="M65,432 L65,480" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#15[0] → #13 · CTRL</title></path><path class="edge MEM" id="e15i1" d="M397,432 L397,437 Q397,442 392,442 L97,442 Q89,442 89,450 L89,480" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#15[1] → #10 · MEM</title></path><path class="edge DATA" id="e15i2" d="M411,118 L411,130 Q411,138 403,138 L124,138 Q116,138 116,146 L116,450.5 Q116,452 114.5,452 L114.5,452 Q113,452 113,453.5 L113,480" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#15[2] → #5 · DATA</title></path><path class="edge DATA" id="e15i3" d="M190,224 L190,229 Q190,234 185,234 L145,234 Q137,234 137,242 L137,480" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#15[3] → #11 · DATA</title></path><path class="edge ASSOC" id="e16i0" d="M316,46 C316,70 342,147 342,171" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#16[0] → #1 · ASSOC</title></path><path class="edge DATA" id="e17i1" d="M190,224 L190,229 Q190,234 195,234 L304,234 Q312,234 312,242 L312,272" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#17[1] → #11 · DATA</title></path><path class="edge DATA" id="e17i2" d="M342,224 L342,272" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#17[2] → #16 · DATA</title></path><path class="edge CTRL" id="e18i0" d="M521,432 L521,480" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#18[0] → #14 · CTRL</title></path><path class="edge MEM" id="e18i1" d="M397,432 L397,437 Q397,442 402,442 L537,442 Q545,442 545,450 L545,480" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#18[1] → #10 · MEM</title></path><path class="edge DATA" id="e18i2" d="M411,118 L411,130 Q411,138 419,138 L566,138 Q574,138 574,146 L574,439.5 Q574,442 571.5,442 L571.5,442 Q569,442 569,444.5 L569,480" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[2] → #5 · DATA</title></path><path class="edge MEM" id="e19i1" d="M397,432 L397,437 Q397,442 402,442 L469,442 Q477,442 477,450 L477,584" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#19[1] → #10 · MEM</title></path><path class="edge DATA" id="e19i2" d="M557,536 L557,541 Q557,546 552,546 L515,546 Q507,546 507,554 L507,584" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#19[2] → #18 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(73,24)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>Start</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#1 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" transform="translate(73,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$mem</tspan><tspan class="node-id"> #3/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEM</title></g><g class="node" id="n4" data-id="4" transform="translate(193,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>arg</tspan><tspan class="node-id"> #4/2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATA</title></g><g class="node" id="n5" data-id="5" transform="translate(351,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>new Point</tspan><tspan class="node-id"> #5</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 new Point +Type not computed + +[0] → — CTRL</title><circle class="port" cx="60" cy="-3" r="3" fill="white"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n6" data-id="6" transform="translate(503,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#0</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 #0 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n7" data-id="7" transform="translate(422,174)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.x</tspan><tspan class="node-id"> #7</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n8" data-id="8" transform="translate(444,278)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.y</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 Store p.y +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #6 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n10" data-id="10" transform="translate(337,382)" style="opacity: 1;"><path class="box" d="M12,0H108L120,22L108,44H12L0,22Z" fill="#f5e4fa"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Phi $mem</tspan><tspan class="node-id"> #10</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#10 Phi $mem +Type not computed + +[0] → — ASSOC +[1] → #8 MEM +[2] → #15 MEM</title><circle class="port" cx="0" cy="-3" r="3" fill="white"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="0" y="-10" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n11" data-id="11" transform="translate(130,174)" style="opacity: 1;"><path class="box" d="M12,0H108L120,22L108,44H12L0,22Z" fill="#f5e4fa"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Phi arg</tspan><tspan class="node-id"> #11</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#11 Phi arg +Type not computed + +[0] → — ASSOC +[1] → #4 DATA +[2] → #17 DATA</title><circle class="port" cx="0" cy="-3" r="3" fill="white"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="0" y="-10" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n13" data-id="13" transform="translate(24,400)" style="opacity: 1;"><path class="box" d="M0,0H82V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="41" y="17"><tspan>True</tspan><tspan class="node-id"> #13/0</tspan></text><text class="type" text-anchor="middle" y="35" x="41"/><title>#13 True +Projection 0 of #0 +Type not computed + +</title></g><g class="node" id="n14" data-id="14" transform="translate(477,400)" style="opacity: 1;"><path class="box" d="M0,0H87V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="43.5" y="17"><tspan>False</tspan><tspan class="node-id"> #14/1</tspan></text><text class="type" text-anchor="middle" y="35" x="43.5"/><title>#14 False +Projection 1 of #0 +Type not computed + +</title></g><g class="node" id="n15" data-id="15" transform="translate(41,486)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.x</tspan><tspan class="node-id"> #15</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#15 Store p.x +Type not computed + +[0] → #13 CTRL +[1] → #10 MEM +[2] → #5 DATA +[3] → #11 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="#536477"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n16" data-id="16" transform="translate(282,174)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#1</tspan><tspan class="node-id"> #16</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#16 #1 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n17" data-id="17" transform="translate(252,278)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>-</tspan><tspan class="node-id"> #17</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#17 - +Type not computed + +[0] → — CTRL +[1] → #11 DATA +[2] → #16 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n18" data-id="18" transform="translate(497,486)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Load p.x</tspan><tspan class="node-id"> #18</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#18 Load p.x +Type not computed + +[0] → #14 CTRL +[1] → #10 MEM +[2] → #5 DATA +[3] → — DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="#536477"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="white"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n19" data-id="19" transform="translate(417,590)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #19</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#19 Return +Type not computed + +[0] → — CTRL +[1] → #10 MEM +[2] → #18 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> 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 @@ +<svg aria-label="Compiler graph" width="598" height="560" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 598 560" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge ASSOC" id="e6i0" d="M419,46 C419,70 514,41 514,65" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#6[0] → #1 · ASSOC</title></path><path class="edge MEM" id="e7i1" d="M236,118 L236,123 Q236,128 231,128 L151,128 Q143,128 143,136 L143,168" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#7[1] → #3 · MEM</title></path><path class="edge DATA" id="e7i2" d="M84,118 L84,150 Q84,158 92,158 L162,158 Q167,158 167,163 L167,168" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[2] → #5 · DATA</title></path><path class="edge DATA" id="e7i3" d="M514,118 L514,130 Q514,138 506,138 L199,138 Q191,138 191,146 L191,168" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[3] → #6 · DATA</title></path><path class="edge MEM" id="e8i1" d="M155,224 L155,229 Q155,234 160,234 L193,234 Q201,234 201,242 L201,272" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#8[1] → #7 · MEM</title></path><path class="edge DATA" id="e8i2" d="M84,118 L84,150 Q84,158 92,158 L217,158 Q225,158 225,166 L225,272" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #5 · DATA</title></path><path class="edge DATA" id="e8i3" d="M514,118 L514,130 Q514,138 506,138 L257,138 Q249,138 249,146 L249,272" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[3] → #6 · DATA</title></path><path class="edge MEM" id="e9i1" d="M213,328 L213,333 Q213,338 218,338 L262,338 Q270,338 270,346 L270,376" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#9[1] → #8 · MEM</title></path><path class="edge DATA" id="e9i2" d="M84,118 L84,150 Q84,158 92,158 L286,158 Q294,158 294,166 L294,376" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[2] → #5 · DATA</title></path><path class="edge MEM" id="e10i1" d="M213,328 L213,333 Q213,338 208,338 L126,338 Q118,338 118,346 L118,376" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#10[1] → #8 · MEM</title></path><path class="edge DATA" id="e10i2" d="M84,118 L84,340 Q84,348 92,348 L134,348 Q142,348 142,356 L142,376" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#10[2] → #5 · DATA</title></path><path class="edge DATA" id="e10i3" d="M356,118 L356,140 Q356,148 348,148 L291,148 Q283,148 283,156 L283,340 Q283,348 275,348 L174,348 Q166,348 166,356 L166,376" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#10[3] → #4 · DATA</title></path><path class="edge MEM" id="e11i1" d="M130,432 L130,480" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#11[1] → #10 · MEM</title></path><path class="edge DATA" id="e11i2" d="M282,432 L282,437 Q282,442 277,442 L168,442 Q160,442 160,450 L160,480" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#11[2] → #9 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(176,24)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>Start</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#1 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" transform="translate(176,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$mem</tspan><tspan class="node-id"> #3/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEM</title></g><g class="node" id="n4" data-id="4" transform="translate(296,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>arg</tspan><tspan class="node-id"> #4/2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATA</title></g><g class="node" id="n5" data-id="5" transform="translate(24,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>new Point</tspan><tspan class="node-id"> #5</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 new Point +Type not computed + +[0] → — CTRL</title><circle class="port" cx="60" cy="-3" r="3" fill="white"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n6" data-id="6" transform="translate(454,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#0</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 #0 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n7" data-id="7" transform="translate(95,174)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.x</tspan><tspan class="node-id"> #7</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n8" data-id="8" transform="translate(153,278)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.y</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 Store p.y +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #6 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n9" data-id="9" transform="translate(222,382)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Load p.x</tspan><tspan class="node-id"> #9</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#9 Load p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → — DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="white"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n10" data-id="10" transform="translate(70,382)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.x</tspan><tspan class="node-id"> #10</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#10 Store p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #4 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n11" data-id="11" transform="translate(70,486)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #11</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#11 Return +Type not computed + +[0] → — CTRL +[1] → #10 MEM +[2] → #9 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> 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=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="#ffc0cb">tuple</TD></TR> + <TR><TD BGCOLOR="black"><FONT COLOR="white">type</FONT></TD></TR> + </TABLE> + >]; + TUPLE2 [shape=plain, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="#ffc0cb">tuple</TD></TR> + <TR><TD BGCOLOR="black"><FONT COLOR="white">type</FONT></TD></TR> + <TR><TD BGCOLOR="black"><FONT COLOR="white">type</FONT></TD></TR> + </TABLE> + >]; + TUPLEN [shape=plain, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="#ffc0cb">tuple</TD></TR> + <TR><TD BGCOLOR="black"><FONT COLOR="white">type</FONT></TD></TR> + <TR><TD BGCOLOR="black"><FONT COLOR="white">…</FONT></TD></TR> + <TR><TD BGCOLOR="black"><FONT COLOR="white">type</FONT></TD></TR> + </TABLE> + >]; + {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 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 12.2.0 (20241103.1931) + --> +<!-- Title: Lattice Pages: 1 --> +<svg width="1551pt" height="603pt" + viewBox="0.00 0.00 1551.00 603.45" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 599.45)"> +<title>Lattice</title> +<polygon fill="white" stroke="none" points="-4,4 -4,-599.45 1547,-599.45 1547,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_control</title> +<polygon fill="none" stroke="#cccccc" points="8,-85.99 8,-524.71 98,-524.71 98,-85.99 8,-85.99"/> +<text text-anchor="middle" x="53" y="-507.41" font-family="Arial" font-size="14.00">Control</text> +</g> +<g id="clust2" class="cluster"> +<title>cluster_integer</title> +<polygon fill="none" stroke="#cccccc" points="106,-85.99 106,-524.71 404,-524.71 404,-85.99 106,-85.99"/> +<text text-anchor="middle" x="255" y="-507.41" font-family="Arial" font-size="14.00">Integer</text> +</g> +<g id="clust6" class="cluster"> +<title>cluster_pointer</title> +<polygon fill="none" stroke="#cccccc" points="412,-75 412,-535.7 893,-535.7 893,-75 412,-75"/> +<text text-anchor="middle" x="652.5" y="-518.4" font-family="Arial" font-size="14.00">Pointer = nullability × struct type</text> +</g> +<g id="clust13" class="cluster"> +<title>cluster_struct</title> +<polygon fill="none" stroke="#cccccc" points="901,-75 901,-551.45 1233,-551.45 1233,-75 901,-75"/> +<text text-anchor="middle" x="1067" y="-534.15" font-family="Arial" font-size="14.00">Struct</text> +<text text-anchor="middle" x="1067" y="-518.4" font-family="Arial" font-size="14.00">named collection of named scalar types</text> +</g> +<g id="clust17" class="cluster"> +<title>cluster_memory</title> +<polygon fill="none" stroke="#cccccc" points="1241,-85.99 1241,-524.71 1347,-524.71 1347,-85.99 1241,-85.99"/> +<text text-anchor="middle" x="1294" y="-507.41" font-family="Arial" font-size="14.00">Memory</text> +</g> +<g id="clust18" class="cluster"> +<title>cluster_tuple</title> +<polygon fill="none" stroke="#cccccc" points="1355,-85.99 1355,-540.46 1535,-540.46 1535,-85.99 1355,-85.99"/> +<text text-anchor="middle" x="1445" y="-523.16" font-family="Arial" font-size="14.00">Tuple</text> +<text text-anchor="middle" x="1445" y="-507.41" font-family="Arial" font-size="14.00">collection of types</text> +</g> +<!-- TOP --> +<g id="node1" class="node"> +<title>TOP</title> +<ellipse fill="black" stroke="black" cx="875" cy="-577.45" rx="27" ry="18"/> +<text text-anchor="middle" x="875" y="-573.35" font-family="DejaVu Sans" font-size="13.00" fill="white">⊤</text> +</g> +<!-- XCTRL --> +<g id="node3" class="node"> +<title>XCTRL</title> +<ellipse fill="#ffff00" stroke="black" cx="53" cy="-474.96" rx="36.51" ry="18"/> +<text text-anchor="middle" x="53" y="-470.86" font-family="DejaVu Sans" font-size="13.00">⊤:ctrl</text> +</g> +<!-- TOP->XCTRL --> +<g id="edge53" class="edge"> +<title>TOP->XCTRL</title> +<path fill="none" stroke="#555555" d="M847.89,-576.27C714.74,-575.32 135.11,-570.13 102,-551.45 82.18,-540.26 69.05,-517.37 61.41,-499.71"/> +<polygon fill="#555555" stroke="#555555" points="63.45,-499.15 59.24,-494.39 59.57,-500.74 63.45,-499.15"/> +</g> +<!-- INT_TOP --> +<g id="node5" class="node"> +<title>INT_TOP</title> +<ellipse fill="#add8e6" stroke="black" cx="353" cy="-474.96" rx="33.44" ry="18"/> +<text text-anchor="middle" x="353" y="-470.86" font-family="DejaVu Sans" font-size="13.00">⊤:int</text> +</g> +<!-- TOP->INT_TOP --> +<g id="edge54" class="edge"> +<title>TOP->INT_TOP</title> +<path fill="none" stroke="#555555" d="M847.84,-576.34C753.92,-575.8 446.62,-572.41 408,-551.45 387.24,-540.18 372.3,-517.29 363.27,-499.66"/> +<polygon fill="#555555" stroke="#555555" points="365.18,-498.78 360.66,-494.31 361.41,-500.63 365.18,-498.78"/> +</g> +<!-- PTR_TOP --> +<g id="node10" class="node"> +<title>PTR_TOP</title> +<ellipse fill="#008000" stroke="black" cx="715" cy="-474.96" rx="61.7" ry="28.99"/> +<text text-anchor="middle" x="715" y="-479.11" font-family="DejaVu Sans" font-size="13.00" fill="white">⊤:ptr</text> +<text text-anchor="middle" x="715" y="-462.61" font-family="DejaVu Sans" font-size="13.00" fill="white">[*⊤:struct]</text> +</g> +<!-- TOP->PTR_TOP --> +<g id="edge55" class="edge"> +<title>TOP->PTR_TOP</title> +<path fill="none" stroke="#555555" d="M855.7,-564.33C831.54,-549.16 789.48,-522.73 757.62,-502.72"/> +<polygon fill="#555555" stroke="#555555" points="758.87,-501.03 752.67,-499.62 756.64,-504.59 758.87,-501.03"/> +</g> +<!-- STRUCT_TOP --> +<g id="node20" class="node"> +<title>STRUCT_TOP</title> +<ellipse fill="#90ee90" stroke="black" cx="996" cy="-474.96" rx="64.35" ry="28.99"/> +<text text-anchor="middle" x="996" y="-479.11" font-family="DejaVu Sans" font-size="13.00">⊤:struct</text> +<text text-anchor="middle" x="996" y="-462.61" font-family="DejaVu Sans" font-size="13.00">[struct top]</text> +</g> +<!-- TOP->STRUCT_TOP --> +<g id="edge56" class="edge"> +<title>TOP->STRUCT_TOP</title> +<path fill="none" stroke="#555555" d="M891.32,-562.9C908.92,-548.28 937.5,-524.55 960.35,-505.57"/> +<polygon fill="#555555" stroke="#555555" points="961.58,-507.27 964.86,-501.82 958.9,-504.04 961.58,-507.27"/> +</g> +<!-- MEM_TOP --> +<g id="node26" class="node"> +<title>MEM_TOP</title> +<ellipse fill="#00008b" stroke="black" cx="1294" cy="-474.96" rx="44.7" ry="18"/> +<text text-anchor="middle" x="1294" y="-470.86" font-family="DejaVu Sans" font-size="13.00" fill="white">⊤:mem</text> +</g> +<!-- TOP->MEM_TOP --> +<g id="edge57" class="edge"> +<title>TOP->MEM_TOP</title> +<path fill="none" stroke="#555555" d="M902.2,-575.86C981.35,-573.98 1207.82,-567.26 1237,-551.45 1258.22,-539.95 1273.86,-516.78 1283.33,-499.12"/> +<polygon fill="#555555" stroke="#555555" points="1284.97,-500.54 1285.85,-494.24 1281.23,-498.61 1284.97,-500.54"/> +</g> +<!-- TUPLE_TOP --> +<g id="node28" class="node"> +<title>TUPLE_TOP</title> +<ellipse fill="#ffc0cb" stroke="black" cx="1408" cy="-474.96" rx="44.7" ry="18"/> +<text text-anchor="middle" x="1408" y="-470.86" font-family="DejaVu Sans" font-size="13.00">⊤:tuple</text> +</g> +<!-- TOP->TUPLE_TOP --> +<g id="edge58" class="edge"> +<title>TOP->TUPLE_TOP</title> +<path fill="none" stroke="#555555" d="M902.34,-576.35C997.63,-575.82 1311.4,-572.48 1351,-551.45 1372.31,-540.13 1387.94,-516.93 1397.39,-499.22"/> +<polygon fill="#555555" stroke="#555555" points="1399.03,-500.62 1399.89,-494.32 1395.29,-498.7 1399.03,-500.62"/> +</g> +<!-- BOT --> +<g id="node2" class="node"> +<title>BOT</title> +<ellipse fill="black" stroke="black" cx="884" cy="-18" rx="27" ry="18"/> +<text text-anchor="middle" x="884" y="-13.9" font-family="DejaVu Sans" font-size="13.00" fill="white">⊥</text> +</g> +<!-- CTRL --> +<g id="node4" class="node"> +<title>CTRL</title> +<ellipse fill="#ffff00" stroke="black" cx="53" cy="-111.99" rx="36.51" ry="18"/> +<text text-anchor="middle" x="53" y="-107.89" font-family="DejaVu Sans" font-size="13.00">⊥:ctrl</text> +</g> +<!-- XCTRL->CTRL --> +<g id="edge1" class="edge"> +<title>XCTRL->CTRL</title> +<path fill="none" stroke="#555555" d="M53,-456.55C53,-397.7 53,-206.04 53,-137.58"/> +<polygon fill="#555555" stroke="#555555" points="55.1,-137.74 53,-131.74 50.9,-137.74 55.1,-137.74"/> +</g> +<!-- XCTRL->INT_TOP --> +<!-- CTRL->BOT --> +<g id="edge59" class="edge"> +<title>CTRL->BOT</title> +<path fill="none" stroke="#555555" d="M69.29,-95.39C78.22,-87.83 89.91,-79.45 102,-75 242.26,-23.4 717.31,-19.12 849.57,-18.95"/> +<polygon fill="#555555" stroke="#555555" points="849.19,-21.05 855.19,-18.94 849.18,-16.85 849.19,-21.05"/> +</g> +<!-- INT_NEG --> +<g id="node7" class="node"> +<title>INT_NEG</title> +<ellipse fill="#add8e6" stroke="black" cx="169" cy="-216.97" rx="55.45" ry="18"/> +<text text-anchor="middle" x="169" y="-212.87" font-family="DejaVu Sans" font-size="13.00">… −2, −1</text> +</g> +<!-- INT_TOP->INT_NEG --> +<g id="edge4" class="edge"> +<title>INT_TOP->INT_NEG</title> +<path fill="none" stroke="#555555" d="M338.42,-458.38C324.81,-443.56 304.22,-420.4 288,-398.97 246.77,-344.48 204.12,-276.17 182.84,-241.1"/> +<polygon fill="#555555" stroke="#555555" points="184.8,-240.29 179.9,-236.24 181.21,-242.46 184.8,-240.29"/> +</g> +<!-- INT_ZERO --> +<g id="node8" class="node"> +<title>INT_ZERO</title> +<ellipse fill="#add8e6" stroke="black" cx="267" cy="-216.97" rx="27" ry="18"/> +<text text-anchor="middle" x="267" y="-212.87" font-family="DejaVu Sans" font-size="13.00">0</text> +</g> +<!-- INT_TOP->INT_ZERO --> +<g id="edge5" class="edge"> +<title>INT_TOP->INT_ZERO</title> +<path fill="none" stroke="#555555" d="M347.22,-456.76C332.26,-412.21 292.18,-292.93 275,-241.79"/> +<polygon fill="#555555" stroke="#555555" points="277.02,-241.21 273.12,-236.19 273.04,-242.55 277.02,-241.21"/> +</g> +<!-- INT_POS --> +<g id="node9" class="node"> +<title>INT_POS</title> +<ellipse fill="#add8e6" stroke="black" cx="353" cy="-216.97" rx="43.16" ry="18"/> +<text text-anchor="middle" x="353" y="-212.87" font-family="DejaVu Sans" font-size="13.00">1, 2, …</text> +</g> +<!-- INT_TOP->INT_POS --> +<g id="edge6" class="edge"> +<title>INT_TOP->INT_POS</title> +<path fill="none" stroke="#555555" d="M353,-456.76C353,-412.51 353,-294.56 353,-242.85"/> +<polygon fill="#555555" stroke="#555555" points="355.1,-242.94 353,-236.94 350.9,-242.94 355.1,-242.94"/> +</g> +<!-- INT_TOP->PTR_TOP --> +<!-- INT_BOT --> +<g id="node6" class="node"> +<title>INT_BOT</title> +<ellipse fill="#add8e6" stroke="black" cx="310" cy="-111.99" rx="33.44" ry="18"/> +<text text-anchor="middle" x="310" y="-107.89" font-family="DejaVu Sans" font-size="13.00">⊥:int</text> +</g> +<!-- INT_BOT->BOT --> +<g id="edge60" class="edge"> +<title>INT_BOT->BOT</title> +<path fill="none" stroke="#555555" d="M335.28,-99.84C354.78,-91.7 382.61,-81.07 408,-75 570.29,-36.22 770.4,-23.83 849.5,-20.29"/> +<polygon fill="#555555" stroke="#555555" points="849.36,-22.39 855.26,-20.04 849.17,-18.2 849.36,-22.39"/> +</g> +<!-- INT_NEG->INT_BOT --> +<g id="edge7" class="edge"> +<title>INT_NEG->INT_BOT</title> +<path fill="none" stroke="#555555" d="M190.72,-200.11C216.15,-181.54 258.17,-150.85 284.95,-131.29"/> +<polygon fill="#555555" stroke="#555555" points="285.92,-133.18 289.52,-127.95 283.44,-129.79 285.92,-133.18"/> +</g> +<!-- INT_NEG->INT_ZERO --> +<!-- INT_ZERO->INT_BOT --> +<g id="edge8" class="edge"> +<title>INT_ZERO->INT_BOT</title> +<path fill="none" stroke="#555555" d="M273.91,-199.43C281.01,-182.41 292.14,-155.76 300.16,-136.55"/> +<polygon fill="#555555" stroke="#555555" points="302.01,-137.58 302.38,-131.24 298.13,-135.96 302.01,-137.58"/> +</g> +<!-- INT_ZERO->INT_POS --> +<!-- INT_POS->INT_BOT --> +<g id="edge9" class="edge"> +<title>INT_POS->INT_BOT</title> +<path fill="none" stroke="#555555" d="M345.9,-198.97C338.83,-182.05 327.93,-155.94 319.99,-136.93"/> +<polygon fill="#555555" stroke="#555555" points="321.94,-136.15 317.69,-131.42 318.07,-137.76 321.94,-136.15"/> +</g> +<!-- PTR_NULL --> +<g id="node12" class="node"> +<title>PTR_NULL</title> +<ellipse fill="#008000" stroke="black" cx="799" cy="-345.97" rx="27.3" ry="18"/> +<text text-anchor="middle" x="799" y="-341.87" font-family="DejaVu Sans" font-size="13.00" fill="white">null</text> +</g> +<!-- PTR_TOP->PTR_NULL --> +<g id="edge16" class="edge"> +<title>PTR_TOP->PTR_NULL</title> +<path fill="none" stroke="#555555" d="M732.81,-447.03C748.16,-423.83 770.03,-390.77 784.37,-369.09"/> +<polygon fill="#555555" stroke="#555555" points="785.98,-370.45 787.54,-364.29 782.48,-368.13 785.98,-370.45"/> +</g> +<!-- PTR_PERSON --> +<g id="node14" class="node"> +<title>PTR_PERSON</title> +<ellipse fill="#008000" stroke="black" cx="542" cy="-345.97" rx="45.72" ry="18"/> +<text text-anchor="middle" x="542" y="-341.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*Person</text> +</g> +<!-- PTR_TOP->PTR_PERSON --> +<g id="edge17" class="edge"> +<title>PTR_TOP->PTR_PERSON</title> +<path fill="none" stroke="#555555" d="M675.88,-452.05C651.99,-438.01 621.28,-418.77 596,-398.97 584.24,-389.76 572.18,-378.36 562.44,-368.58"/> +<polygon fill="#555555" stroke="#555555" points="564.05,-367.22 558.35,-364.42 561.06,-370.17 564.05,-367.22"/> +</g> +<!-- PTR_S1 --> +<g id="node15" class="node"> +<title>PTR_S1</title> +<ellipse fill="#008000" stroke="black" cx="631" cy="-345.97" rx="27" ry="18"/> +<text text-anchor="middle" x="631" y="-341.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*s1</text> +</g> +<!-- PTR_TOP->PTR_S1 --> +<g id="edge18" class="edge"> +<title>PTR_TOP->PTR_S1</title> +<path fill="none" stroke="#555555" d="M697.19,-447.03C681.84,-423.83 659.97,-390.77 645.63,-369.09"/> +<polygon fill="#555555" stroke="#555555" points="647.52,-368.13 642.46,-364.29 644.02,-370.45 647.52,-368.13"/> +</g> +<!-- PTR_MORE --> +<g id="node16" class="node"> +<title>PTR_MORE</title> +<ellipse fill="#008000" stroke="black" cx="715" cy="-345.97" rx="40.6" ry="18"/> +<text text-anchor="middle" x="715" y="-341.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*s2, …</text> +</g> +<!-- PTR_TOP->PTR_MORE --> +<g id="edge19" class="edge"> +<title>PTR_TOP->PTR_MORE</title> +<path fill="none" stroke="#555555" d="M715,-445.77C715,-423.52 715,-392.77 715,-371.51"/> +<polygon fill="#555555" stroke="#555555" points="717.1,-371.66 715,-365.66 712.9,-371.66 717.1,-371.66"/> +</g> +<!-- PTR_TOP->STRUCT_TOP --> +<!-- PTR_BOT --> +<g id="node11" class="node"> +<title>PTR_BOT</title> +<ellipse fill="#008000" stroke="black" cx="748" cy="-111.99" rx="66.47" ry="28.99"/> +<text text-anchor="middle" x="748" y="-116.14" font-family="DejaVu Sans" font-size="13.00" fill="white">⊥:ptr</text> +<text text-anchor="middle" x="748" y="-99.64" font-family="DejaVu Sans" font-size="13.00" fill="white">[*⊥:struct?]</text> +</g> +<!-- PTR_BOT->BOT --> +<g id="edge61" class="edge"> +<title>PTR_BOT->BOT</title> +<path fill="none" stroke="#555555" d="M783.38,-87.06C807.3,-70.88 838.29,-49.92 859.52,-35.56"/> +<polygon fill="#555555" stroke="#555555" points="860.46,-37.46 864.25,-32.36 858.1,-33.98 860.46,-37.46"/> +</g> +<!-- PTR_PERSON_NIL --> +<g id="node17" class="node"> +<title>PTR_PERSON_NIL</title> +<ellipse fill="#008000" stroke="black" cx="651" cy="-216.97" rx="50.33" ry="18"/> +<text text-anchor="middle" x="651" y="-212.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*Person?</text> +</g> +<!-- PTR_NULL->PTR_PERSON_NIL --> +<g id="edge26" class="edge"> +<title>PTR_NULL->PTR_PERSON_NIL</title> +<path fill="none" stroke="#555555" d="M790.34,-328.75C783.99,-317.83 774.65,-303.55 764,-292.97 740.64,-269.76 709.08,-249.53 685.25,-235.95"/> +<polygon fill="#555555" stroke="#555555" points="686.33,-234.14 680.07,-233.04 684.27,-237.8 686.33,-234.14"/> +</g> +<!-- PTR_S1_NIL --> +<g id="node18" class="node"> +<title>PTR_S1_NIL</title> +<ellipse fill="#008000" stroke="black" cx="748" cy="-216.97" rx="30.37" ry="18"/> +<text text-anchor="middle" x="748" y="-212.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*s1?</text> +</g> +<!-- PTR_NULL->PTR_S1_NIL --> +<g id="edge27" class="edge"> +<title>PTR_NULL->PTR_S1_NIL</title> +<path fill="none" stroke="#555555" d="M792.23,-328.1C783.31,-305.9 767.59,-266.75 757.49,-241.6"/> +<polygon fill="#555555" stroke="#555555" points="759.55,-241.1 755.36,-236.31 755.65,-242.66 759.55,-241.1"/> +</g> +<!-- PTR_MORE_NIL --> +<g id="node19" class="node"> +<title>PTR_MORE_NIL</title> +<ellipse fill="#008000" stroke="black" cx="840" cy="-216.97" rx="45.21" ry="18"/> +<text text-anchor="middle" x="840" y="-212.87" font-family="DejaVu Sans" font-size="13.00" fill="white">*s2?, …</text> +</g> +<!-- PTR_NULL->PTR_MORE_NIL --> +<g id="edge28" class="edge"> +<title>PTR_NULL->PTR_MORE_NIL</title> +<path fill="none" stroke="#555555" d="M804.53,-327.84C811.65,-305.78 824.07,-267.3 832.17,-242.24"/> +<polygon fill="#555555" stroke="#555555" points="834.12,-243.03 833.96,-236.68 830.12,-241.74 834.12,-243.03"/> +</g> +<!-- PTR_ANY --> +<g id="node13" class="node"> +<title>PTR_ANY</title> +<ellipse fill="#008000" stroke="black" cx="502" cy="-216.97" rx="82.38" ry="28.99"/> +<text text-anchor="middle" x="502" y="-221.12" font-family="DejaVu Sans" font-size="13.00" fill="white">*⊥:struct</text> +<text text-anchor="middle" x="502" y="-204.62" font-family="DejaVu Sans" font-size="13.00" fill="white">[ptr any struct]</text> +</g> +<!-- PTR_ANY->PTR_BOT --> +<g id="edge29" class="edge"> +<title>PTR_ANY->PTR_BOT</title> +<path fill="none" stroke="#555555" d="M554.17,-194.13C595.32,-176.91 652.51,-152.97 694.1,-135.56"/> +<polygon fill="#555555" stroke="#555555" points="694.78,-137.55 699.5,-133.29 693.15,-133.67 694.78,-137.55"/> +</g> +<!-- PTR_ANY->PTR_PERSON_NIL --> +<!-- PTR_PERSON->PTR_ANY --> +<g id="edge20" class="edge"> +<title>PTR_PERSON->PTR_ANY</title> +<path fill="none" stroke="#555555" d="M536.61,-327.84C530.59,-308.74 520.69,-277.32 513.02,-252.97"/> +<polygon fill="#555555" stroke="#555555" points="515.08,-252.52 511.28,-247.43 511.08,-253.78 515.08,-252.52"/> +</g> +<!-- PTR_PERSON->PTR_S1 --> +<!-- PTR_PERSON->PTR_PERSON_NIL --> +<g id="edge23" class="edge"> +<title>PTR_PERSON->PTR_PERSON_NIL</title> +<path fill="none" stroke="#555555" d="M556.03,-328.62C575.38,-306.08 610.32,-265.36 632,-240.11"/> +<polygon fill="#555555" stroke="#555555" points="633.38,-241.73 635.7,-235.81 630.19,-238.99 633.38,-241.73"/> +</g> +<!-- PTR_S1->PTR_ANY --> +<g id="edge21" class="edge"> +<title>PTR_S1->PTR_ANY</title> +<path fill="none" stroke="#555555" d="M621.75,-328.57C615.28,-317.84 606.03,-303.85 596,-292.97 580.61,-276.28 561.35,-260.24 544.26,-247.31"/> +<polygon fill="#555555" stroke="#555555" points="545.84,-245.87 539.78,-243.96 543.32,-249.23 545.84,-245.87"/> +</g> +<!-- PTR_S1->PTR_MORE --> +<!-- PTR_S1->PTR_S1_NIL --> +<g id="edge24" class="edge"> +<title>PTR_S1->PTR_S1_NIL</title> +<path fill="none" stroke="#555555" d="M640.49,-328.79C647.07,-318.15 656.34,-304.18 666,-292.97 684.1,-271.96 707.73,-250.9 724.97,-236.47"/> +<polygon fill="#555555" stroke="#555555" points="726.11,-238.25 729.39,-232.8 723.43,-235.02 726.11,-238.25"/> +</g> +<!-- PTR_MORE->PTR_NULL --> +<!-- PTR_MORE->PTR_ANY --> +<g id="edge22" class="edge"> +<title>PTR_MORE->PTR_ANY</title> +<path fill="none" stroke="#555555" d="M702.63,-328.84C693.45,-317.69 680.11,-303.08 666,-292.97 635.59,-271.17 597.84,-253.38 566.22,-240.61"/> +<polygon fill="#555555" stroke="#555555" points="567.33,-238.79 560.98,-238.52 565.78,-242.69 567.33,-238.79"/> +</g> +<!-- PTR_MORE->PTR_MORE_NIL --> +<g id="edge25" class="edge"> +<title>PTR_MORE->PTR_MORE_NIL</title> +<path fill="none" stroke="#555555" d="M729.86,-328.89C739.5,-318.54 752.38,-304.85 764,-292.97 782,-274.55 802.85,-254.03 818.15,-239.12"/> +<polygon fill="#555555" stroke="#555555" points="819.6,-240.64 822.44,-234.95 816.67,-237.63 819.6,-240.64"/> +</g> +<!-- PTR_PERSON_NIL->PTR_BOT --> +<g id="edge30" class="edge"> +<title>PTR_PERSON_NIL->PTR_BOT</title> +<path fill="none" stroke="#555555" d="M666.58,-199.43C680.58,-184.56 701.51,-162.35 718.65,-144.16"/> +<polygon fill="#555555" stroke="#555555" points="719.75,-146.05 722.33,-140.24 716.69,-143.17 719.75,-146.05"/> +</g> +<!-- PTR_PERSON_NIL->PTR_S1_NIL --> +<!-- PTR_S1_NIL->PTR_BOT --> +<g id="edge31" class="edge"> +<title>PTR_S1_NIL->PTR_BOT</title> +<path fill="none" stroke="#555555" d="M748,-198.5C748,-184.97 748,-165.76 748,-148.97"/> +<polygon fill="#555555" stroke="#555555" points="750.1,-148.97 748,-142.97 745.9,-148.97 750.1,-148.97"/> +</g> +<!-- PTR_S1_NIL->PTR_MORE_NIL --> +<!-- PTR_MORE_NIL->PTR_BOT --> +<g id="edge32" class="edge"> +<title>PTR_MORE_NIL->PTR_BOT</title> +<path fill="none" stroke="#555555" d="M825.62,-199.88C812.53,-185.22 792.8,-163.14 776.51,-144.9"/> +<polygon fill="#555555" stroke="#555555" points="778.14,-143.58 772.58,-140.51 775.01,-146.38 778.14,-143.58"/> +</g> +<!-- STRUCT_PERSON --> +<g id="node22" class="node"> +<title>STRUCT_PERSON</title> +<polygon fill="#90ee90" stroke="black" points="976.5,-237.47 909.5,-237.47 909.5,-196.47 976.5,-196.47 976.5,-237.47"/> +<text text-anchor="middle" x="943" y="-221.12" font-family="DejaVu Sans" font-size="13.00">Person</text> +<text text-anchor="middle" x="943" y="-204.62" font-family="DejaVu Sans" font-size="13.00">age: int</text> +</g> +<!-- STRUCT_TOP->STRUCT_PERSON --> +<g id="edge36" class="edge"> +<title>STRUCT_TOP->STRUCT_PERSON</title> +<path fill="none" stroke="#555555" d="M990.23,-446.07C979.97,-396.53 958.69,-293.77 948.58,-244.91"/> +<polygon fill="#555555" stroke="#555555" points="950.69,-244.75 947.42,-239.3 946.58,-245.61 950.69,-244.75"/> +</g> +<!-- STRUCT_S1 --> +<g id="node23" class="node"> +<title>STRUCT_S1</title> +<polygon fill="#90ee90" stroke="black" points="1047,-237.47 993,-237.47 993,-196.47 1047,-196.47 1047,-237.47"/> +<text text-anchor="middle" x="1020" y="-221.12" font-family="DejaVu Sans" font-size="13.00">s1</text> +<text text-anchor="middle" x="1020" y="-204.62" font-family="DejaVu Sans" font-size="13.00">x: int</text> +</g> +<!-- STRUCT_TOP->STRUCT_S1 --> +<g id="edge37" class="edge"> +<title>STRUCT_TOP->STRUCT_S1</title> +<path fill="none" stroke="#555555" d="M998.66,-445.58C1003.32,-395.91 1012.89,-293.85 1017.46,-245.08"/> +<polygon fill="#555555" stroke="#555555" points="1019.54,-245.41 1018.01,-239.24 1015.36,-245.02 1019.54,-245.41"/> +</g> +<!-- STRUCT_S2 --> +<g id="node24" class="node"> +<title>STRUCT_S2</title> +<polygon fill="#90ee90" stroke="black" points="1154.88,-237.47 1063.12,-237.47 1063.12,-196.47 1154.88,-196.47 1154.88,-237.47"/> +<text text-anchor="middle" x="1109" y="-221.12" font-family="DejaVu Sans" font-size="13.00">s2</text> +<text text-anchor="middle" x="1109" y="-204.62" font-family="DejaVu Sans" font-size="13.00">x: int, y: int</text> +</g> +<!-- STRUCT_TOP->STRUCT_S2 --> +<g id="edge38" class="edge"> +<title>STRUCT_TOP->STRUCT_S2</title> +<path fill="none" stroke="#555555" d="M1008.31,-446.07C1030.23,-396.43 1075.73,-293.34 1097.24,-244.61"/> +<polygon fill="#555555" stroke="#555555" points="1099.12,-245.54 1099.63,-239.21 1095.28,-243.85 1099.12,-245.54"/> +</g> +<!-- STRUCT_MORE --> +<g id="node25" class="node"> +<title>STRUCT_MORE</title> +<polygon fill="#90ee90" stroke="black" points="1225,-234.97 1171,-234.97 1171,-198.97 1225,-198.97 1225,-234.97"/> +<text text-anchor="middle" x="1198" y="-212.87" font-family="DejaVu Sans" font-size="13.00">…</text> +</g> +<!-- STRUCT_TOP->STRUCT_MORE --> +<g id="edge39" class="edge"> +<title>STRUCT_TOP->STRUCT_MORE</title> +<path fill="none" stroke="#555555" d="M1018.31,-447.4C1030.2,-433.14 1045.02,-415.19 1058,-398.97 1102.92,-342.8 1154.32,-275.57 1180.57,-241"/> +<polygon fill="#555555" stroke="#555555" points="1182,-242.59 1183.95,-236.54 1178.65,-240.05 1182,-242.59"/> +</g> +<!-- STRUCT_TOP->MEM_TOP --> +<!-- STRUCT_BOT --> +<g id="node21" class="node"> +<title>STRUCT_BOT</title> +<ellipse fill="#90ee90" stroke="black" cx="1020" cy="-111.99" rx="82.91" ry="28.99"/> +<text text-anchor="middle" x="1020" y="-116.14" font-family="DejaVu Sans" font-size="13.00">⊥:struct</text> +<text text-anchor="middle" x="1020" y="-99.64" font-family="DejaVu Sans" font-size="13.00">[struct bottom]</text> +</g> +<!-- STRUCT_BOT->BOT --> +<g id="edge62" class="edge"> +<title>STRUCT_BOT->BOT</title> +<path fill="none" stroke="#555555" d="M982.84,-85.85C959.17,-69.85 929.19,-49.57 908.49,-35.56"/> +<polygon fill="#555555" stroke="#555555" points="909.78,-33.9 903.63,-32.28 907.42,-37.38 909.78,-33.9"/> +</g> +<!-- STRUCT_PERSON->STRUCT_BOT --> +<g id="edge40" class="edge"> +<title>STRUCT_PERSON->STRUCT_BOT</title> +<path fill="none" stroke="#555555" d="M957.85,-196.12C968.43,-181.96 982.92,-162.59 995.24,-146.11"/> +<polygon fill="#555555" stroke="#555555" points="996.85,-147.46 998.76,-141.4 993.49,-144.94 996.85,-147.46"/> +</g> +<!-- STRUCT_PERSON->STRUCT_S1 --> +<!-- STRUCT_S1->STRUCT_BOT --> +<g id="edge41" class="edge"> +<title>STRUCT_S1->STRUCT_BOT</title> +<path fill="none" stroke="#555555" d="M1020,-196.12C1020,-182.64 1020,-164.43 1020,-148.49"/> +<polygon fill="#555555" stroke="#555555" points="1022.1,-148.87 1020,-142.87 1017.9,-148.87 1022.1,-148.87"/> +</g> +<!-- STRUCT_S1->STRUCT_S2 --> +<!-- STRUCT_S2->STRUCT_BOT --> +<g id="edge42" class="edge"> +<title>STRUCT_S2->STRUCT_BOT</title> +<path fill="none" stroke="#555555" d="M1091.84,-196.12C1079.5,-181.83 1062.57,-162.25 1048.25,-145.68"/> +<polygon fill="#555555" stroke="#555555" points="1050,-144.5 1044.49,-141.33 1046.82,-147.24 1050,-144.5"/> +</g> +<!-- STRUCT_S2->STRUCT_MORE --> +<!-- STRUCT_MORE->STRUCT_BOT --> +<g id="edge43" class="edge"> +<title>STRUCT_MORE->STRUCT_BOT</title> +<path fill="none" stroke="#555555" d="M1177.76,-198.72C1173.05,-195 1167.95,-191.22 1163,-187.98 1135.19,-169.81 1102.49,-152.39 1075.38,-138.93"/> +<polygon fill="#555555" stroke="#555555" points="1076.64,-137.21 1070.33,-136.44 1074.78,-140.97 1076.64,-137.21"/> +</g> +<!-- MEM_BOT --> +<g id="node27" class="node"> +<title>MEM_BOT</title> +<ellipse fill="#00008b" stroke="black" cx="1294" cy="-111.99" rx="44.7" ry="18"/> +<text text-anchor="middle" x="1294" y="-107.89" font-family="DejaVu Sans" font-size="13.00" fill="white">⊥:mem</text> +</g> +<!-- MEM_TOP->MEM_BOT --> +<g id="edge44" class="edge"> +<title>MEM_TOP->MEM_BOT</title> +<path fill="none" stroke="#555555" d="M1294,-456.55C1294,-397.7 1294,-206.04 1294,-137.58"/> +<polygon fill="#555555" stroke="#555555" points="1296.1,-137.74 1294,-131.74 1291.9,-137.74 1296.1,-137.74"/> +</g> +<!-- MEM_TOP->TUPLE_TOP --> +<!-- MEM_BOT->BOT --> +<g id="edge63" class="edge"> +<title>MEM_BOT->BOT</title> +<path fill="none" stroke="#555555" d="M1273.96,-95.5C1263.49,-88.17 1250.14,-79.95 1237,-75 1125.68,-33.06 983.13,-22.53 918.55,-19.89"/> +<polygon fill="#555555" stroke="#555555" points="918.65,-17.79 912.58,-19.66 918.49,-21.99 918.65,-17.79"/> +</g> +<!-- TUPLE1 --> +<g id="node30" class="node"> +<title>TUPLE1</title> +<polygon fill="#ffc0cb" stroke="none" points="1406.88,-372.47 1363.12,-372.47 1363.12,-319.47 1406.88,-319.47 1406.88,-372.47"/> +<polygon fill="#ffc0cb" stroke="none" points="1363.12,-345.97 1363.12,-372.47 1406.88,-372.47 1406.88,-345.97 1363.12,-345.97"/> +<polygon fill="none" stroke="black" points="1363.12,-345.97 1363.12,-372.47 1406.88,-372.47 1406.88,-345.97 1363.12,-345.97"/> +<text text-anchor="start" x="1368.12" y="-355.12" font-family="DejaVu Sans" font-size="13.00">tuple</text> +<polygon fill="black" stroke="none" points="1363.12,-319.47 1363.12,-345.97 1406.88,-345.97 1406.88,-319.47 1363.12,-319.47"/> +<polygon fill="none" stroke="black" points="1363.12,-319.47 1363.12,-345.97 1406.88,-345.97 1406.88,-319.47 1363.12,-319.47"/> +<text text-anchor="start" x="1370.38" y="-328.62" font-family="DejaVu Sans" font-size="13.00" fill="white">type</text> +</g> +<!-- TUPLE_TOP->TUPLE1 --> +<g id="edge47" class="edge"> +<title>TUPLE_TOP->TUPLE1</title> +<path fill="none" stroke="#555555" d="M1404.85,-456.57C1401.26,-436.74 1395.31,-403.91 1390.86,-379.34"/> +<polygon fill="#555555" stroke="#555555" points="1392.94,-379.03 1389.81,-373.5 1388.81,-379.77 1392.94,-379.03"/> +</g> +<!-- TUPLE2 --> +<g id="node31" class="node"> +<title>TUPLE2</title> +<polygon fill="#ffc0cb" stroke="none" points="1466.88,-385.72 1423.12,-385.72 1423.12,-306.22 1466.88,-306.22 1466.88,-385.72"/> +<polygon fill="#ffc0cb" stroke="none" points="1423.12,-359.22 1423.12,-385.72 1466.88,-385.72 1466.88,-359.22 1423.12,-359.22"/> +<polygon fill="none" stroke="black" points="1423.12,-359.22 1423.12,-385.72 1466.88,-385.72 1466.88,-359.22 1423.12,-359.22"/> +<text text-anchor="start" x="1428.12" y="-368.37" font-family="DejaVu Sans" font-size="13.00">tuple</text> +<polygon fill="black" stroke="none" points="1423.12,-332.72 1423.12,-359.22 1466.88,-359.22 1466.88,-332.72 1423.12,-332.72"/> +<polygon fill="none" stroke="black" points="1423.12,-332.72 1423.12,-359.22 1466.88,-359.22 1466.88,-332.72 1423.12,-332.72"/> +<text text-anchor="start" x="1430.38" y="-341.87" font-family="DejaVu Sans" font-size="13.00" fill="white">type</text> +<polygon fill="black" stroke="none" points="1423.12,-306.22 1423.12,-332.72 1466.88,-332.72 1466.88,-306.22 1423.12,-306.22"/> +<polygon fill="none" stroke="black" points="1423.12,-306.22 1423.12,-332.72 1466.88,-332.72 1466.88,-306.22 1423.12,-306.22"/> +<text text-anchor="start" x="1430.38" y="-315.37" font-family="DejaVu Sans" font-size="13.00" fill="white">type</text> +</g> +<!-- TUPLE_TOP->TUPLE2 --> +<g id="edge48" class="edge"> +<title>TUPLE_TOP->TUPLE2</title> +<path fill="none" stroke="#555555" d="M1412.99,-456.83C1417.76,-440.46 1425.17,-415.04 1431.65,-392.78"/> +<polygon fill="#555555" stroke="#555555" points="1433.64,-393.48 1433.3,-387.13 1429.6,-392.3 1433.64,-393.48"/> +</g> +<!-- TUPLEN --> +<g id="node32" class="node"> +<title>TUPLEN</title> +<polygon fill="#ffc0cb" stroke="none" points="1526.88,-398.97 1483.12,-398.97 1483.12,-292.97 1526.88,-292.97 1526.88,-398.97"/> +<polygon fill="#ffc0cb" stroke="none" points="1483.12,-372.47 1483.12,-398.97 1526.88,-398.97 1526.88,-372.47 1483.12,-372.47"/> +<polygon fill="none" stroke="black" points="1483.12,-372.47 1483.12,-398.97 1526.88,-398.97 1526.88,-372.47 1483.12,-372.47"/> +<text text-anchor="start" x="1488.12" y="-381.62" font-family="DejaVu Sans" font-size="13.00">tuple</text> +<polygon fill="black" stroke="none" points="1483.12,-345.97 1483.12,-372.47 1526.88,-372.47 1526.88,-345.97 1483.12,-345.97"/> +<polygon fill="none" stroke="black" points="1483.12,-345.97 1483.12,-372.47 1526.88,-372.47 1526.88,-345.97 1483.12,-345.97"/> +<text text-anchor="start" x="1490.38" y="-355.12" font-family="DejaVu Sans" font-size="13.00" fill="white">type</text> +<polygon fill="black" stroke="none" points="1483.12,-319.47 1483.12,-345.97 1526.88,-345.97 1526.88,-319.47 1483.12,-319.47"/> +<polygon fill="none" stroke="black" points="1483.12,-319.47 1483.12,-345.97 1526.88,-345.97 1526.88,-319.47 1483.12,-319.47"/> +<text text-anchor="start" x="1498.62" y="-328.62" font-family="DejaVu Sans" font-size="13.00" fill="white">…</text> +<polygon fill="black" stroke="none" points="1483.12,-292.97 1483.12,-319.47 1526.88,-319.47 1526.88,-292.97 1483.12,-292.97"/> +<polygon fill="none" stroke="black" points="1483.12,-292.97 1483.12,-319.47 1526.88,-319.47 1526.88,-292.97 1483.12,-292.97"/> +<text text-anchor="start" x="1490.38" y="-302.12" font-family="DejaVu Sans" font-size="13.00" fill="white">type</text> +</g> +<!-- TUPLE_TOP->TUPLEN --> +<g id="edge49" class="edge"> +<title>TUPLE_TOP->TUPLEN</title> +<path fill="none" stroke="#555555" d="M1424.21,-457.82C1438.47,-443.17 1459.34,-420.61 1475,-398.97 1476.4,-397.02 1477.8,-395.01 1479.17,-392.95"/> +<polygon fill="#555555" stroke="#555555" points="1480.91,-394.14 1482.41,-387.96 1477.38,-391.86 1480.91,-394.14"/> +</g> +<!-- TUPLE_BOT --> +<g id="node29" class="node"> +<title>TUPLE_BOT</title> +<ellipse fill="#ffc0cb" stroke="black" cx="1426" cy="-111.99" rx="44.7" ry="18"/> +<text text-anchor="middle" x="1426" y="-107.89" font-family="DejaVu Sans" font-size="13.00">⊥:tuple</text> +</g> +<!-- TUPLE_BOT->BOT --> +<g id="edge64" class="edge"> +<title>TUPLE_BOT->BOT</title> +<path fill="none" stroke="#555555" d="M1401.48,-96.69C1387.21,-89.03 1368.61,-80.13 1351,-75 1193.97,-29.27 996.8,-20.82 918.41,-19.3"/> +<polygon fill="#555555" stroke="#555555" points="918.75,-17.21 912.72,-19.21 918.68,-21.41 918.75,-17.21"/> +</g> +<!-- TUPLE1->TUPLE_BOT --> +<g id="edge50" class="edge"> +<title>TUPLE1->TUPLE_BOT</title> +<path fill="none" stroke="#555555" d="M1389.47,-319.7C1397.39,-274.85 1413.82,-181.9 1421.66,-137.56"/> +<polygon fill="#555555" stroke="#555555" points="1423.69,-138.14 1422.66,-131.86 1419.55,-137.4 1423.69,-138.14"/> +</g> +<!-- TUPLE1->TUPLE2 --> +<!-- TUPLE2->TUPLE_BOT --> +<g id="edge51" class="edge"> +<title>TUPLE2->TUPLE_BOT</title> +<path fill="none" stroke="#555555" d="M1441.84,-306.4C1437.91,-258.37 1431.3,-177.75 1428,-137.46"/> +<polygon fill="#555555" stroke="#555555" points="1430.13,-137.74 1427.55,-131.93 1425.95,-138.08 1430.13,-137.74"/> +</g> +<!-- TUPLE2->TUPLEN --> +<!-- TUPLEN->TUPLE_BOT --> +<g id="edge52" class="edge"> +<title>TUPLEN->TUPLE_BOT</title> +<path fill="none" stroke="#555555" d="M1487.37,-293.19C1470.79,-244.5 1446.69,-173.75 1434.2,-137.07"/> +<polygon fill="#555555" stroke="#555555" points="1436.27,-136.64 1432.35,-131.63 1432.3,-137.99 1436.27,-136.64"/> +</g> +</g> +</svg> 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 @@ +<svg aria-label="Compiler graph" width="598" height="454" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 598 454" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge ASSOC" id="e6i0" d="M571,46 C571,70 236,41 236,65" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#6[0] → #1 · ASSOC</title></path><path class="edge MEM" id="e7i1" d="M388,118 L388,130 Q388,138 380,138 L376,138 Q368,138 368,146 L368,166" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#7[1] → #3 · MEM</title></path><path class="edge DATA" id="e7i2" d="M84,118 L84,140 Q84,148 92,148 L384,148 Q392,148 392,156 L392,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[2] → #5 · DATA</title></path><path class="edge DATA" id="e7i3" d="M236,118 L236,123 Q236,128 241,128 L408,128 Q416,128 416,136 L416,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[3] → #6 · DATA</title></path><path class="edge MEM" id="e8i1" d="M380,222 L380,227 Q380,232 385,232 L418,232 Q426,232 426,240 L426,270" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#8[1] → #7 · MEM</title></path><path class="edge DATA" id="e8i2" d="M84,118 L84,140 Q84,148 92,148 L442,148 Q450,148 450,156 L450,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #5 · DATA</title></path><path class="edge DATA" id="e8i3" d="M508,118 L508,224 Q508,232 500,232 L482,232 Q474,232 474,240 L474,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[3] → #4 · DATA</title></path><path class="edge MEM" id="e10i1" d="M438,326 L438,331 Q438,336 443,336 L470,336 Q478,336 478,344 L478,374" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#10[1] → #8 · MEM</title></path><path class="edge DATA" id="e10i2" d="M508,118 L508,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#10[2] → #4 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(328,24)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>Start</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#1 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" transform="translate(328,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$mem</tspan><tspan class="node-id"> #3/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEM</title></g><g class="node" id="n4" data-id="4" transform="translate(448,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>arg</tspan><tspan class="node-id"> #4/2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATA</title></g><g class="node" id="n5" data-id="5" transform="translate(24,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>new Box</tspan><tspan class="node-id"> #5</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 new Box +Type not computed + +[0] → — CTRL</title><circle class="port" cx="60" cy="-3" r="3" fill="white"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n6" data-id="6" transform="translate(176,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#0</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 #0 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n7" data-id="7" transform="translate(320,172)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.x</tspan><tspan class="node-id"> #7</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n8" data-id="8" transform="translate(378,276)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.x</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 Store p.x +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #4 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n10" data-id="10" transform="translate(418,380)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #10</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#10 Return +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #4 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> 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 @@ +<svg aria-label="Compiler graph" width="598" height="558" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 598 558" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge ASSOC" id="e6i0" d="M267,46 C267,70 514,41 514,65" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#6[0] → #1 · ASSOC</title></path><path class="edge MEM" id="e7i1" d="M84,118 L84,130 Q84,138 92,138 L272,138 Q280,138 280,146 L280,166" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#7[1] → #3 · MEM</title></path><path class="edge DATA" id="e7i2" d="M362,118 L362,123 Q362,128 357,128 L312,128 Q304,128 304,136 L304,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[2] → #5 · DATA</title></path><path class="edge DATA" id="e7i3" d="M514,118 L514,130 Q514,138 506,138 L336,138 Q328,138 328,146 L328,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[3] → #6 · DATA</title></path><path class="edge MEM" id="e8i1" d="M292,222 L292,227 Q292,232 287,232 L275,232 Q267,232 267,240 L267,270" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#8[1] → #7 · MEM</title></path><path class="edge DATA" id="e8i2" d="M362,118 L362,234 Q362,242 354,242 L299,242 Q291,242 291,250 L291,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #5 · DATA</title></path><path class="edge DATA" id="e8i3" d="M204,118 L204,123 Q204,128 209,128 L213,128 Q221,128 221,136 L221,244 Q221,252 229,252 L307,252 Q315,252 315,260 L315,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[3] → #4 · DATA</title></path><path class="edge MEM" id="e9i1" d="M279,326 L279,331 Q279,336 284,336 L330,336 Q338,336 338,344 L338,374" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#9[1] → #8 · MEM</title></path><path class="edge DATA" id="e9i2" d="M362,118 L362,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[2] → #5 · DATA</title></path><path class="edge MEM" id="e10i1" d="M279,326 L279,478" stroke="#2867b2" marker-start="url(#arrow-MEM)" style="opacity: 1;"><title>#10[1] → #8 · MEM</title></path><path class="edge DATA" id="e10i2" d="M350,430 L350,435 Q350,440 345,440 L317,440 Q309,440 309,448 L309,478" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#10[2] → #9 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(24,24)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>Start</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#1 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" transform="translate(24,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$mem</tspan><tspan class="node-id"> #3/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEM</title></g><g class="node" id="n4" data-id="4" transform="translate(144,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>arg</tspan><tspan class="node-id"> #4/2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATA</title></g><g class="node" id="n5" data-id="5" transform="translate(302,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>new Box</tspan><tspan class="node-id"> #5</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 new Box +Type not computed + +[0] → — CTRL</title><circle class="port" cx="60" cy="-3" r="3" fill="white"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n6" data-id="6" transform="translate(454,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#0</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 #0 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n7" data-id="7" transform="translate(232,172)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.x</tspan><tspan class="node-id"> #7</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 Store p.x +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n8" data-id="8" transform="translate(219,276)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#dcecff"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Store p.x</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 Store p.x +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #4 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n9" data-id="9" transform="translate(290,380)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Load p.x</tspan><tspan class="node-id"> #9</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#9 Load p.x +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → — DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="#536477"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="white"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n10" data-id="10" transform="translate(219,484)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #10</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#10 Return +Type not computed + +[0] → — CTRL +[1] → #8 MEM +[2] → #9 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> 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 @@ +<svg xmlns="http://www.w3.org/2000/svg" width="61" height="20" viewBox="0 0 61 20" role="img" aria-labelledby="title"> + <title id="title">Control</title> + <rect width="61" height="20" rx="2" fill="#ffff00"/> + <text x="30.5" y="14" text-anchor="middle" font-family="Arial, sans-serif" font-size="13" fill="#000000">Control</text> +</svg> 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 @@ +<svg xmlns="http://www.w3.org/2000/svg" width="60" height="20" viewBox="0 0 60 20" role="img" aria-labelledby="title"> + <title id="title">Integer</title> + <rect width="60" height="20" rx="2" fill="#add8e6"/> + <text x="30.0" y="14" text-anchor="middle" font-family="Arial, sans-serif" font-size="13" fill="#000000">Integer</text> +</svg> 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 @@ +<svg xmlns="http://www.w3.org/2000/svg" width="67" height="20" viewBox="0 0 67 20" role="img" aria-labelledby="title"> + <title id="title">Memory</title> + <rect width="67" height="20" rx="2" fill="#00008b"/> + <text x="33.5" y="14" text-anchor="middle" font-family="Arial, sans-serif" font-size="13" fill="#ffffff">Memory</text> +</svg> 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 @@ +<svg xmlns="http://www.w3.org/2000/svg" width="62" height="20" viewBox="0 0 62 20" role="img" aria-labelledby="title"> + <title id="title">Pointer</title> + <rect width="62" height="20" rx="2" fill="#008000"/> + <text x="31.0" y="14" text-anchor="middle" font-family="Arial, sans-serif" font-size="13" fill="#ffffff">Pointer</text> +</svg> 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 @@ +<svg xmlns="http://www.w3.org/2000/svg" width="52" height="20" viewBox="0 0 52 20" role="img" aria-labelledby="title"> + <title id="title">Struct</title> + <rect width="52" height="20" rx="2" fill="#90ee90"/> + <text x="26.0" y="14" text-anchor="middle" font-family="Arial, sans-serif" font-size="13" fill="#000000">Struct</text> +</svg> 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 @@ +<svg xmlns="http://www.w3.org/2000/svg" width="47" height="20" viewBox="0 0 47 20" role="img" aria-labelledby="title"> + <title id="title">Tuple</title> + <rect width="47" height="20" rx="2" fill="#ffc0cb"/> + <text x="23.5" y="14" text-anchor="middle" font-family="Arial, sans-serif" font-size="13" fill="#000000">Tuple</text> +</svg> |
