From 1659b2591654acd3679c2779fd62281e496fdaf6 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 30 Jun 2024 01:58:08 +0100 Subject: Chapter 11: Splitting Memory MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Dibyendu Majumdar Co-authored-by: Thalia Archibald Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- README.ja.md | 2 +- README.md | 2 +- chapter10.iml | 28 - chapter11.iml | 28 + docs/chapter11/Makefile | 1 + docs/chapter11/README.ja.md | 168 ++++++ docs/chapter11/README.md | 270 +++++++++ docs/chapter11/example1.gv | 20 + docs/chapter11/example1.json | 31 + docs/chapter11/example1.svg | 155 +++++ docs/chapter11/example2a.gv | 17 + docs/chapter11/example2a.json | 20 + docs/chapter11/example2a.svg | 103 ++++ docs/chapter11/example2b-final.json | 251 ++++++++ docs/chapter11/example2b-final.svg | 110 ++++ docs/chapter11/example2b-merged.json | 339 +++++++++++ docs/chapter11/example2b-merged.svg | 130 +++++ docs/chapter11/example2b-split-y.json | 486 ++++++++++++++++ docs/chapter11/example2b-split-y.svg | 157 +++++ docs/chapter11/example2b.gv | 19 + docs/chapter11/example2b.json | 30 + docs/chapter11/example2b.svg | 150 +++++ docs/chapter11/example2c.gv | 15 + docs/chapter11/example2c.json | 23 + docs/chapter11/example2c.svg | 121 ++++ docs/chapter11/lattice.gv | 133 +++++ docs/chapter11/lattice.svg | 644 +++++++++++++++++++++ src/main/java/com/seaofnodes/simple/IRPrinter.java | 1 + src/main/java/com/seaofnodes/simple/Parser.java | 22 +- .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 237 ++++++++ .../java/com/seaofnodes/simple/node/LoadNode.java | 32 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 61 ++ .../java/com/seaofnodes/simple/node/MemOpNode.java | 13 +- .../com/seaofnodes/simple/node/MemPhiNode.java | 36 ++ src/main/java/com/seaofnodes/simple/node/Node.java | 10 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 21 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 4 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 18 +- .../simple/print/SimpleGraphObserver.java | 2 +- src/main/java/com/seaofnodes/simple/type/Type.java | 2 +- .../java/com/seaofnodes/simple/type/TypeMem.java | 72 ++- .../java/com/seaofnodes/simple/Chapter10Test.java | 31 +- .../java/com/seaofnodes/simple/Chapter11Test.java | 64 ++ src/test/java/com/seaofnodes/simple/TypeTest.java | 21 +- .../com/seaofnodes/simple/evaluator/Evaluator.java | 1 + .../com/seaofnodes/simple/evaluator/Scheduler.java | 13 +- 46 files changed, 4017 insertions(+), 97 deletions(-) delete mode 100644 chapter10.iml create mode 100644 chapter11.iml create mode 100644 docs/chapter11/Makefile create mode 100644 docs/chapter11/README.ja.md create mode 100644 docs/chapter11/README.md create mode 100644 docs/chapter11/example1.gv create mode 100644 docs/chapter11/example1.json create mode 100644 docs/chapter11/example1.svg create mode 100644 docs/chapter11/example2a.gv create mode 100644 docs/chapter11/example2a.json create mode 100644 docs/chapter11/example2a.svg create mode 100644 docs/chapter11/example2b-final.json create mode 100644 docs/chapter11/example2b-final.svg create mode 100644 docs/chapter11/example2b-merged.json create mode 100644 docs/chapter11/example2b-merged.svg create mode 100644 docs/chapter11/example2b-split-y.json create mode 100644 docs/chapter11/example2b-split-y.svg create mode 100644 docs/chapter11/example2b.gv create mode 100644 docs/chapter11/example2b.json create mode 100644 docs/chapter11/example2b.svg create mode 100644 docs/chapter11/example2c.gv create mode 100644 docs/chapter11/example2c.json create mode 100644 docs/chapter11/example2c.svg create mode 100644 docs/chapter11/lattice.gv create mode 100644 docs/chapter11/lattice.svg create mode 100644 src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/MemMergeNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/MemPhiNode.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter11Test.java diff --git a/README.ja.md b/README.ja.md index 26698a4a..faa963f4 100644 --- a/README.ja.md +++ b/README.ja.md @@ -47,7 +47,7 @@ Simple 言語のスタイルは、C または Java のサブセットに倣っ * [第8章](docs/chapter08/README.ja.md)：ループ構造の続き。必要時の Phi の生成、`break` 文と `continue` 文。 * [第9章](docs/chapter09/README.ja.md)：大域的値番号付け。不動点に達するまでのピープホール最適化の反復。ワークリスト。 * [第10章](docs/chapter10/README.ja.md)：ユーザー定義の構造体、ポインタ、null 解析。SSA で表す単一のメモリ値。ロード、ストア、実行可能な評価器。 -* 第11章：同値類によるエイリアス解析。`MemMerge`、`MemPhi`、`BulkMemPhi` による必要時のメモリ分割。 +* [第11章](docs/chapter11/README.ja.md)：同値類によるエイリアス解析。`MemMerge`、`MemPhi`、`BulkMemPhi` による必要時のメモリ分割。 * 第12章：参照フィールド、前方参照、再帰的な構造体。 * 第13章：大域的コード移動とスケジューリング。 * 第14章：数値型。浮動小数点数、狭い整数型、範囲、`f32` への丸め。 diff --git a/README.md b/README.md index ce0d3e52..3ca676ee 100644 --- a/README.md +++ b/README.md @@ -55,7 +55,7 @@ The Simple language is styled after a subset of C or Java. * [Chapter 9](docs/chapter09/README.md): Global Value Numbering. Iterative peepholes to fixpoint. Worklists. * [Chapter 10](docs/chapter10/README.md): User defined structs, pointers and null analysis. One memory value in SSA. Loads, stores, and an executable evaluator. -* Chapter 11: Equivalence class aliasing. Lazy memory +* [Chapter 11](docs/chapter11/README.md): Equivalence class aliasing. Lazy memory partitioning with `MemMerge`, `MemPhi`, and `BulkMemPhi`. * Chapter 12: Reference fields, forward references and recursive structs. * Chapter 13: Global Code Motion - Scheduling. diff --git a/chapter10.iml b/chapter10.iml deleted file mode 100644 index a352db38..00000000 --- a/chapter10.iml +++ /dev/null @@ -1,28 +0,0 @@ - - - - - - - - - - - - - - - - - - - - - - - - - - - - diff --git a/chapter11.iml b/chapter11.iml new file mode 100644 index 00000000..92b9e5ca --- /dev/null +++ b/chapter11.iml @@ -0,0 +1,28 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/docs/chapter11/Makefile b/docs/chapter11/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter11/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter11/README.ja.md b/docs/chapter11/README.ja.md new file mode 100644 index 00000000..3ef66442 --- /dev/null +++ b/docs/chapter11/README.ja.md @@ -0,0 +1,168 @@ +# 第11章: メモリの分割 + +[English](README.md) | 日本語 + +[前: 第10章](../chapter10/README.ja.md) | +[次: 第12章](../chapter12/README.ja.md) + +この文書は [原文](README.md) の日本語訳です。 + +第10章では、1つの SSA メモリ値でメモリへの作用を明示しました。この章ではパーサーのモデルをそのまま維持し、グラフの書き換えによって独立したメモリ鎖を復元します。新しい言語構文はありません。[文法](../chapter10/10-grammar.ja.md)、ポインタ型、null チェックは変わりません。 + +## なぜメモリを分割するのか + +```java +struct Point { int x; int y; } +Point p = new Point; +p.x = 42; +while (arg > 0) { + p.y = p.y + arg; + arg = arg - 1; +} +return p.x; +``` + +ループが変更するのは `y` なので、`x` に影響できません。メモリ鎖が1本だと、`x` のロードはループのストアの後に続きます。フィールドを分割すれば、通常のストア後のロードへの値の転送によって、戻り値を 42 にできます。 + +![独立したフィールドの依存関係](example1.svg) + +グラフは、最後の Load を畳み込む前の分割された鎖を示します。そのメモリ入力は、ループの `y` の鎖を迂回して 42 の Store に直接つながります。第10章と同様、小さく切り離された True/False 射影は、Load と Store を制御するソースの分岐を示します。Loop とその Phi 束縛を含む、ほかの制御フローの文脈は省略しています。グラフが示すのは実行順序ではなく依存関係です。 + +## 同値類によるエイリアシング + +各構造体フィールドは整数のエイリアス識別子を持ちます。別のフィールドには、異なる構造体で同じ綴りを持っていても、別の識別子を与えます。*同じ*構造体の2つのインスタンスは、フィールドのエイリアスを共有します。したがって異なるクラス間では決してエイリアスしませんが、同じクラス内のアクセスは**エイリアスする可能性があります**（同じクラスであることは同じアドレスを意味しません）。ポインタの同一性は、依然として確認する必要があります。 + +パーサーは構造体の宣言時に、alias#2 から始めてフィールドの識別子を割り当てます。 + +宣言されたフィールドやエイリアスのそれぞれについて、Start 射影、スコープの束縛、ループ Phi を割り当てることはしません。Start が1つのメモリ値を供給し、Scope が1つの `$mem` 束縛を保持し、Return がメモリ全体を消費します: `{ctrl, $mem, result}`。Start の出力と同様、制御はスロット 0、メモリはスロット 1 にあります。最適化器は、グラフの演算が必要とする箇所にだけスライスを導入します。 + +## 3つのメモリノード + +| ノード | 意味 | +|---|---| +| `MemMerge` | デフォルトと精密なエイリアスごとの上書きからなる完全なメモリ状態 | +| `MemPhi` | 流入する制御経路に従って選択される1つのエイリアス | +| `BulkMemPhi` | 明示した除外集合を除くすべてのエイリアスを、制御によって選択する | + +`MemMerge` は、あるプログラム位置でメモリの独立した部分を組み合わせます。制御フローの合流ではありません。たとえばエイリアス `x` へのストア後は、次のようになります。 + +```text +prior = current memory +store = Store_x(prior, pointer, value) +current memory = MemMerge(default=prior, x=store) +``` + +MemMerge はスロット 1 にデフォルトのメモリを持ち、それと異なる場合にはほかのスロットに精密なエイリアスを持ちます。Load、Store、MemPhi は、入力の MemMerge から精密な入力を選択し、可能なら精密なエイリアス入力を使います。 + +明示的なエイリアスはデフォルトを上書きします。エイリアスのスライスは互いに交わらず、その和集合はすべてのメモリを覆います。積み重なった MemMerge を平坦化するときは、外側の MemMerge が置き換えていないエントリを保持します。 + +以下のグラフは、冗長な初期化ストアを除去した後の `p.x = arg; p.y = 42; return p;` を示します。MemMerge はスロット 1 にデフォルトのメモリを、スロット 2 と 3 に `x` と `y` の上書きを受け取ります。 + +![集約が両方の更新を保持する](example2a.svg) + +## メモリ Phi の分割 + +パーサーは最初に、通常の SSA アルゴリズムでメモリの合流が必要な箇所に BulkMemPhi を作ります。合流点の確定中は、除外集合を空としてすべてのエイリアスを覆うところから始めます。その後、ピープホール最適化によって、必要に応じて遅延的に、ひとまとめのメモリから精密なメモリスライスを分離します。 + +この変換により、ひとまとめのメモリから精密な単一エイリアスを分離できます。 + +```text +BulkPhi(R, left, right) + becomes +MemMerge( + default = BulkPhi_except{x}(R, left, right), + x = MemPhi_x(R, slice(left,x), slice(right,x))) +``` + +「BulkPhi は、（そのエイリアスを除いた）BulkPhi と（そのエイリアスの）MemPhi をまとめる Merge になる」。 + +新しい精密な Phi と残りのひとまとめの Phi は、Region（図では省略）と一致する制御経路の添字を共有します。ループでも同じ変換を使い、入力の中に後退エッジが含まれます。さらに分割しても、すでに抽出したスライスをすべて保持します（積み重なった分割はピープホール最適化で整理します）。 + +ここでは2つの分岐が `p.x` に 3 または 4 を格納してから `p` を返します。グラフは、ひとまとめの Phi とその入力の集約をさらに簡略化する前、`x` を抽出した直後の分割を示します。 + +```java +struct Point { int x; int y; } +Point p = new Point; +if (arg) p.x = 3; +else p.x = 4; +return p; +``` + +![精密な Phi とひとまとめの Phi が制御の合流を共有する](example2b.svg) + +このグラフから先に進めると、たとえば次の順でピープホール最適化が発動します。 + +**入力の MemMerge を平坦化してから、`y` を分割します。** MemMerge #17 と #18 は #9 から `y` のスライスを継承しますが、それぞれ自身の `x` の上書きが優先します。両者のデフォルトは Start のメモリとなり、#9 は使われなくなります。BulkMemPhi #21 は `x` を除外しますが、まだ `y` を覆うので、これらの MemMerge を単に迂回することはできません。`y` の MemPhi #24 を抽出し、両フィールドを除外した BulkMemPhi #25 を作ります。追加の MemMerge #26 がこれらのスライスを組み合わせます。 + +![入力の集約を平坦化し y を抽出した後](example2b-split-y.svg) + +**変更のないメモリを畳み込みます。** MemPhi #24 の両入力は同じ初期化 Store #8 なので、その Store になります。BulkMemPhi #25 は、今度は #17 と #18 を透かして見ることができます。それらの明示的なエイリアスはすべて、その領域から除外されているためです。残る両入力は Start のメモリになり、このひとまとめの Phi も畳み込まれます。出力側の集約を平坦化すると、MemMerge #22 には Start からのデフォルトメモリ、MemPhi #20 からの `x`、Store #8 からの `y` が残ります。 + +![分岐の合流が必要なのは x のメモリ Phi だけ](example2b-merged.svg) + +**Store をくくり出してから、上書きされた初期化を取り除きます。** ひとまとめの Phi と入力の集約がなくなると、Store #14 と #16 を使うのは MemPhi #20 だけになります。これらは同じポインタとエイリアスに格納し、同じ入力メモリを共有します。`PhiNode` は Store を合流の下に引き下げられます。 + +```text +MemPhi_x(Store_x(mem, p, 3), Store_x(mem, p, 4)) + becomes +Store_x(mem, p, Phi(3, 4)) +``` + +一般に Phi の組み替えでは、第10章と同じく、Load や Store を押し上げたり引き下げたりして組み合わせられます。Phi の新しいメモリオペランドには、そのエイリアスの精密な MemPhi を使えます。このピープホール変換は精密なエイリアスを必要とし、BulkMem があると妨げられます。そのため、BulkMem を分割するきっかけにもなります。 + +例の続きを見ると、新しい値の Phi #28 は true 側で 3、false 側で 4 を選びます。Store #27 が両分岐の Store とそのメモリ Phi を置き換えます。初期の `p.x = 0` の Store #7 は、この1つの Store だけをユーザーに持つようになり、連続するストアの除去で迂回されます。`p.y = 0` の Store #8 は残ります。オブジェクトを返すので、その `y` フィールドは引き続き初期化が必要です。 + +![最終グラフ: 値の Phi を格納する1つの x Store と y の初期化](example2b-final.svg) + +したがって最終グラフには、2つの Store、通常の値の Phi が1つ、MemMerge が1つあり、MemPhi も BulkMemPhi も残りません。ワークリストの順序が違えば、たとえば元の入力 MemMerge を平坦化前に迂回し、一時的な `y` の分割を避けられる場合もあります。 + +このメモリ分割変換は大きくグラフに介入するため、再帰的に呼び出すことを禁止します。ループの周囲を分割することはよいのですが、その途中にあるループ先頭を分割しようとすると問題になります。分割で生まれた新しいノードをワークリストに入れ、現在の分割が完了してから訪問します。これによって、ループを巡るメモリを安全に完全分割できます。 + +ひとまとめの Phi は複数のエイリアスを合流するため、MemMerge に対してピープホール最適化をするときに注意が必要です。MemMerge の精密な合流と、ひとまとめの Phi が重複してはいけません。 + +これは第9章のワークリストの教訓も拡張します。ひとまとめの Phi は自分のユーザーを調べるので、ユーザーの分割が変わったら生成側を起こす必要があります。それが `addDep()` の仕事です。MemMerge からスライスを選ぶと、新しいひとまとめの Phi のユーザーが露出することがあります。その選択された定義もキューに入れなければなりません。つまり MemMerge、MemPhi、BulkMemPhi を扱うときには、非局所的な依存関係を想定する必要があります。 + +メモリ分割でノード数が増えることもありますが、Phi（Mem、Bulk、その他）はコードを生成しません。前進は、ひとまとめの Phi からエイリアスを抽出し、一部の Load と Store を除去することで得られます。すべての書き換えにグラフの縮小を求めるのではありません。言い換えれば、MemPhi 数が増えても、Load/Store の総数は減っています。 + +## 型 + +型の束は、第10章の6つの領域、色、記法を維持します。`⊤` はトップ、`⊥` はボトムを意味し、接尾辞は領域を示します。ほかの5領域は変わりませんが、メモリには、メモリトップ（`TypeMem.TOP`）とメモリボトム（`TypeMem.BOT`）の間に、精密なエイリアスごとの平坦な要素 `MEM#N` が加わります。 + +![精密なメモリエイリアスを含む型の領域](lattice.svg) + +並列の `MEM#2`、`MEM#3`、さらにほかのエイリアス要素は、独立したフィールドスライスを表します。上の最初の `Point` 宣言では、この2つのエイリアスは `Point.x` と `Point.y` を識別します。異なるエイリアスの meet はメモリボトム、join はメモリトップです。精密なエイリアスはそれぞれ自分自身の双対です。（省略記号は並列なエイリアスがさらにあることを示し、エイリアスの集合を表す型ではありません。） + +## 評価と順序付け + +MemMerge は依存関係のノードであり、メモリを上書きしません。コードも出力しません。評価器での結果はメモリトークンですが、Store は実際にオブジェクトのフィールドを変更します。スケジューラは、メモリをまとめることと上書きすることを区別しなければなりません。異なるエイリアス類の Store はロード/ストアの反依存を課しませんが、同じ類の Load には反依存が必要です。 + +`int old = p.x; p.x = arg; p.y = arg; return old;` では、Load は後続の `x` の Store より前でなければならず、`y` の Store は独立したメモリ鎖を持ちます。グラフでは、局所的な畳み込み前のこのスケジューリング要件を示すため、Load を残しています。 + +![順序付けは影響を受けるエイリアス内に適用される](example2c.svg) + +この章には多くのテストがあります。独立したフィールドの畳み込み、並列のメモリ Phi、複数のフィールド更新が Return で保持されること、早期 return、break/continue を伴う入れ子のループ、エイリアスする可能性のあるポインタ経由の後続ストアより前の読み出しを扱います。 + +## 後の章に残ること + +第11章では、パース中にすべてのアクセスのエイリアスがわかっています。ここで遅延するのは、メモリ分割の構築です。第25章では（同じ表現を使いながら）既存のアクセスのエイリアスが*後になって*わかることも許し、さらに不完全な型、モジュールのエイリアス、分割コンパイルなど、多くの利点を可能にします。 + +第12〜24章はこの表現を使います。第13章では大域的コード移動とロード/ストアの反依存を追加します。第15章では部分メモリと型付きエイリアス内容を伴う割り当てを追加します。第16章では初期化をコンストラクタの値に拡張し、第18章では関数呼び出しをまたいでメモリ全体を運びます。 + +## ビルドとテスト + +JDK 21 以降を使い、このディレクトリで実行します。 + +```sh +make lib +make tests +make release +make view +``` + +Make は Maven を使わず、この完全なスナップショットをビルドします。`make release` は `build/release/simple.jar` を書き出し、`make view` は共通のグラフビューアを起動します。ルートの Maven reactor と提供される IDEA のモジュール記述の両方に本章が含まれます。リポジトリのルートから、前後両方をテストするには次を実行します。 + +```sh +make tests CHAPTERS="chapter10 chapter11" +``` + +次の[第12章](../chapter12/README.ja.md)では、このメモリ表現を維持したまま参照フィールドと再帰構造体を追加します。 diff --git a/docs/chapter11/README.md b/docs/chapter11/README.md new file mode 100644 index 00000000..804bcb3c --- /dev/null +++ b/docs/chapter11/README.md @@ -0,0 +1,270 @@ +# Chapter 11: Splitting Memory + +English | [日本語](README.ja.md) + +[Previous: Chapter 10](../chapter10/README.md) | +[Next: Chapter 12](../chapter12/README.md) + +Chapter 10 made memory effects explicit with one SSA memory value. This +chapter keeps exactly that parser model and recovers independent memory chains +through graph rewrites. There is no new language syntax; the +[grammar](../chapter10/10-grammar.md), pointer types, and null checks are unchanged. + +## Why split memory? + +```java +struct Point { int x; int y; } +Point p = new Point; +p.x = 42; +while (arg > 0) { + p.y = p.y + arg; + arg = arg - 1; +} +return p.x; +``` + +The loop changes `y`, so it cannot affect `x`. With one memory chain the load +of `x` follows the loop's stores. Splitting the fields lets ordinary +load-after-store forwarding turn the return value into 42. + +![Independent field dependencies](example1.svg) + +The graph shows the split chains before the final Load folds. Its memory input +goes straight to the Store of 42, bypassing the loop's `y` chain. As in +Chapter 10, small, detached True/False projections show the source branches +gating Loads and Stores. Other control-flow context, including Loops and their +Phi bindings, is omitted. The graph shows dependencies, not execution order. + +## Equivalence-class aliasing + +Each struct field has an integer alias identity. Two different fields receive +different identities, even if they have the same spelling in different structs. +Two instances of the *same* struct share their field aliases. Thus different +classes never alias; accesses in the same class **may alias** (same-class does +not mean same-address). You still need to check for pointer identity. + +The parser assigns field identities at struct declarations, beginning at alias#2. + +We do not allocate a Start projection, scope binding, or loop Phi for every +declared field or alias. Start supplies one memory value, Scope holds one +`$mem` binding, and Return consumes all of memory: `{ctrl, $mem, result}`. As +with Start's outputs, control is in slot 0 and memory in slot 1. The optimizer +introduces slices only where graph operations require them. + +## Three memory nodes + +| Node | Meaning | +|---|---| +| `MemMerge` | A complete memory state: a default plus precise alias overrides | +| `MemPhi` | One alias selected according to the incoming control path | +| `BulkMemPhi` | All aliases except an explicit exclusion set, selected by control | + +`MemMerge` combines independent pieces of memory at one program point. It is +not a control-flow merge. For example, after storing to alias `x`: + +```text +prior = current memory +store = Store_x(prior, pointer, value) +current memory = MemMerge(default=prior, x=store) +``` + +MemMerges have a default memory in slot 1, and precise aliases in other slots +if they differ from the default. Loads, Stores and MemPhis select their +precise input from any incoming MemMerge, using a precise alias input if +possible. + +The explicit aliases override the default: the alias slices are disjoint, +and their union covers all memory. Flattening stacked MemMerges preserves +entries that the outer MemMerge has not replaced. + +The graph below shows `p.x = arg; p.y = 42; return p;` after redundant +initialization stores have been removed. MemMerge takes the default memory +in slot 1 and the `x` and `y` overrides in slots 2 and 3. + +![An aggregate preserves both updates](example2a.svg) + + +## Splitting a memory Phi + +The Parser initially creates a BulkMemPhi wherever the ordinary SSA algorithm needs +to merge memory. It starts by covering all aliases and an empty exclusion set +while the merge point is finalized. Later, peeps will split out precise memory +slices from the bulk memory, lazily on demand. + +Precise single aliases can be split out from the bulk by this transformation: + +```text +BulkPhi(R, left, right) + becomes +MemMerge( + default = BulkPhi_except{x}(R, left, right), + x = MemPhi_x(R, slice(left,x), slice(right,x))) +``` + +"A BulkPhi becomes a Merge of a BulkPhi (minus the alias) and MemPhi (of the alias)". + +The new precise Phi and the remaining bulk Phi share a Region (omitted from the +illustrations) and matching control-path indices. A loop uses the same +transformation, with the backedge among those inputs. Each further split +preserves all previously extracted slices (and peephole optimizations tidy up +the stacked splits). + +Here the two branches store 3 or 4 into `p.x`, then return `p`. The graph shows +the partition immediately after extracting `x`, before further simplification +of the bulk Phi and its incoming aggregates. + +```java +struct Point { int x; int y; } +Point p = new Point; +if (arg) p.x = 3; +else p.x = 4; +return p; +``` + +![Precise and bulk Phis share a control merge](example2b.svg) + +Continuing from this graph, here is one order in which the peepholes can fire: + +**Flatten the incoming MemMerges, then split `y`.** MemMerges #17 and #18 +inherit the `y` slice from #9, but their own `x` overrides win. Both now have +Start's memory as their default, and #9 becomes unused. BulkMemPhi #21 excludes +`x`, but still covers `y`, so it cannot simply bypass these MemMerges. It +extracts MemPhi #24 for `y` and creates BulkMemPhi #25, excluding both fields. +The extra MemMerge #26 combines these slices. + +![After flattening the incoming aggregates and extracting y](example2b-split-y.svg) + +**Fold the unchanged memory.** Both inputs of MemPhi #24 are the same +initializing Store #8, so it becomes that Store. BulkMemPhi #25 can now look +through #17 and #18: their explicit aliases are all excluded from its domain. +Both remaining inputs become Start's memory, so this bulk Phi also folds. +Flattening the outgoing aggregates leaves MemMerge #22 with default memory +from Start, `x` from MemPhi #20, and `y` from Store #8. + +![Only the x memory Phi still needs the branch merge](example2b-merged.svg) + +**Factor the Stores, then remove the overwritten initialization.** With the +bulk Phi and the incoming aggregates gone, Stores #14 and #16 are used only +by MemPhi #20. They store to the same pointer and alias, and share the same +incoming memory. `PhiNode` can pull the Store below the merge: + +```text +MemPhi_x(Store_x(mem, p, 3), Store_x(mem, p, 4)) + becomes +Store_x(mem, p, Phi(3, 4)) +``` + +In general, Phi refactoring can combine Loads or Stores as in Chapter 10 (pushing +up or pulling down). The Phi new memory operands can use precise MemPhis for +the alias. This peep requires precise aliases, and is otherwise blocked by +BulkMems - and thus is a trigger for splitting a BulkMem. + + +Continuing with the example, the new value Phi #28 chooses 3 on the true arm +and 4 on the false arm. Store +#27 replaces both branch Stores and their memory Phi. Now the initial +`p.x = 0` Store #7 has only that one Store as a user, so store-after-store +elimination bypasses it. The `p.y = 0` Store #8 remains: we return the object, +and its `y` field still needs initialization. + +![Final graph: one x Store of a value Phi, and the y initialization](example2b-final.svg) + +Thus the final graph has two Stores, one ordinary value Phi, and one MemMerge; +neither a MemPhi nor a BulkMemPhi remains. Other worklists order can, for +instance, bypass the original incoming MemMerges before flattening them, +avoiding the temporary `y` split. + +This memory splitting transform is invasive, and is disallowed from being +called recursively; you can end up splitting around a loop (which is good) but +then trying to split a mid-split loop head (which is bad). The new nodes from +the split are put on the worklist and visited after the current split +completes - safely allowing memory to be completely sliced around loops. + +Since bulk Phis merge a bunch of aliases, they have to take care when +peepholing vs MemMerges: there cannot be any overlap between the MemMerge +precise merges and the bulk Phi. + +This also extends the worklist lesson from Chapter 9: a bulk Phi inspects its +users, so changes to a user's partition must wake the producer - job for +`addDep()`. Selecting a slice from a MemMerge can expose a new bulk-Phi +user; that selected definition must be queued too. In short, any time we're +working with MemMerge, MemPhi or BulkMemPhi we can expect some non-local +dependencies. + +Memory splitting can increase node count - but Phis (Mem, Bulk or otherwise) +make no code. Progress comes from extracting an alias from a bulk Phi and +removing some Loads and Stores, rather than from requiring every rewrite +to shrink the graph. In other words, the total Load/Store count is going down +even if the MemPhi count is going up. + + +## Types + +The type lattice retains Chapter 10's six domains, colors, and notation: +`⊤` means top, `⊥` means bottom, and a suffix names the domain. The other five +domains are unchanged; however memory now adds a flat element `MEM#N` for each precise +alias between memory top (`TypeMem.TOP`) and memory bottom (`TypeMem.BOT`). + +![The type domains, including precise memory aliases](lattice.svg) + +The parallel `MEM#2`, `MEM#3`, and further alias elements describe independent +field slices. For the first `Point` declaration above, these two aliases identify +`Point.x` and `Point.y`. Meeting different aliases gives memory bottom; joining +them gives memory top. Each precise alias is its own dual. (And the ellipsis stands +for more parallel aliases, not a type representing a set of aliases). + + +## Evaluation and ordering + +MemMerge is a dependency node and not a clobber; it emits no code. Its +evaluator result is a memory token, while Store actually mutates the object's +fields. The scheduler must distinguish merging memory from overwriting memory. +Stores in different alias classes do not impose load/store anti-dependencies, +but Loads in the same class require anti-dependencies. + +In `int old = p.x; p.x = arg; p.y = arg; return old;`, the Load must precede +the later `x` Store; the `y` Store has an independent memory chain. The graph +retains the Load to show this scheduling requirement before local folding. + +![Ordering applies within the affected alias](example2c.svg) + +There are a lot of tests in this chapter, to cover independent-field folding, +parallel memory Phis, multiple field updates surviving at Return, early +returns, nested loops with break/continue, and reads before subsequent stores +through potentially aliased pointers. + +## What remains for later chapters? + +Chapter 11 knows every access's alias while parsing. What is lazy here is the +construction of memory partitions. Chapter 25 also allows an existing access's +alias to become known *later* (using the same representation) and will allow +more incomplete types, module aliases, seperate compilation and a host of other +benefits. + +Chapters 12-24 use this representation. Chapter 13 adds global code motion +and load/store anti-dependencies. Chapter 15 adds allocation with partial memory and typed +alias contents. Chapter 16 extends initialization to constructor values, and +Chapter 18 carries whole memory across function calls. + +## Build and test + +With JDK 21 or newer, from this directory: + +```sh +make lib +make tests +make release +make view +``` + +Make builds this complete snapshot without Maven. `make release` writes +`build/release/simple.jar`; `make view` launches the shared graph viewer. +Both the root Maven reactor and the supplied IDEA module descriptor include +the chapter. From the repository root, test both halves with: + +```sh +make tests CHAPTERS="chapter10 chapter11" +``` + +Next, [Chapter 12](../chapter12/README.md) adds reference fields and recursive +structs while retaining this memory representation. diff --git a/docs/chapter11/example1.gv b/docs/chapter11/example1.gv new file mode 100644 index 00000000..5e059d77 --- /dev/null +++ b/docs/chapter11/example1.gv @@ -0,0 +1,20 @@ +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=BT; + + M [label="Initial memory" shape=octagon style="filled" fillcolor="#dcecff"]; + X [label="Store x = 42" shape=octagon style="filled" fillcolor="#dcecff"]; + Y [label="Loop: Store y" shape=octagon style="filled" fillcolor="#dcecff"]; + L [label="Load x (42)" shape=box style="rounded,filled" fillcolor="#edf3f7"]; + L -> X -> M [color="#2867b2"]; Y -> M [color="#2867b2"]; + MemMerge -> X [color="#2867b2"]; MemMerge -> Y [color="#2867b2"]; + Return -> MemMerge [color="#2867b2"]; Return -> L; + { rank=same; MemMerge -> L [style=invis]; } + Y -> X [style=invis]; // Layout only: keep the stores in code order. + Return [shape=box style="filled" fillcolor="#fff1c4"]; + MemMerge [shape=octagon style="filled" fillcolor="#dcecff"]; +} diff --git a/docs/chapter11/example1.json b/docs/chapter11/example1.json new file mode 100644 index 00000000..c0c28450 --- /dev/null +++ b/docs/chapter11/example1.json @@ -0,0 +1,31 @@ +{ + "ver": 1, + "comp": "chapter11/docs/example1.svg", + "step": 1, + "roots": [24], + "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": "#42", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 8, "label": "Store p.x", "type": "MEM#2", "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": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "Store p.y", "type": "MEM#3", "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": 11, "label": "MemPhi y", "type": "MEM#3", "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 9, "role": "MEM", "label": null}, {"idx": 2, "def": 19, "role": "MEM", "label": null}], "proj": null}, + {"id": 12, "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": 21, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "True", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 0}}, + {"id": 16, "label": "False", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 1}}, + {"id": 17, "label": "Load p.y", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 15, "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": 18, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 17, "role": "DATA", "label": null}, {"idx": 2, "def": 12, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "Store p.y", "type": "MEM#3", "kind": "MEM", "edges": [{"idx": 0, "def": 15, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 18, "role": "DATA", "label": null}], "proj": null}, + {"id": 20, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 21, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 12, "role": "DATA", "label": null}, {"idx": 2, "def": 20, "role": "DATA", "label": null}], "proj": null}, + {"id": 22, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 8, "role": "MEM", "label": null}, {"idx": 3, "def": 11, "role": "MEM", "label": null}], "proj": null}, + {"id": 23, "label": "Load p.x", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 16, "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": 24, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 22, "role": "MEM", "label": null}, {"idx": 2, "def": 23, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter11/example1.svg b/docs/chapter11/example1.svg new file mode 100644 index 00000000..46faf818 --- /dev/null +++ b/docs/chapter11/example1.svg @@ -0,0 +1,155 @@ +#6[0] → #1 · ASSOC#7[0] → #1 · ASSOC#8[1] → #3 · MEM#8[2] → #5 · DATA#8[3] → #7 · DATA#9[1] → #3 · MEM#9[2] → #5 · DATA#9[3] → #6 · DATA#11[1] → #9 · MEM#11[2] → #19 · MEM#12[1] → #4 · DATA#12[2] → #21 · DATA#17[0] → #15 · CTRL#17[1] → #11 · MEM#17[2] → #5 · DATA#18[1] → #17 · DATA#18[2] → #12 · DATA#19[0] → #15 · CTRL#19[1] → #11 · MEM#19[2] → #5 · DATA#19[3] → #18 · DATA#20[0] → #1 · ASSOC#21[1] → #12 · DATA#21[2] → #20 · DATA#22[1] → #3 · MEM#22[2] → #8 · MEM#22[3] → #11 · MEM#23[0] → #16 · CTRL#23[1] → #8 · MEM#23[2] → #5 · DATA#24[1] → #22 · MEM#24[2] → #23 · DATAStart  #1#1 Start +Type not computed + +$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Point  #5#5 new Point +Type not computed + +[0] → — CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0#42  #7#7 #42 +Type not computed + +[0] → #1 ASSOC0Store p.x  #8MEM#2#8 Store p.x +MEM#2 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #7 DATA0123Store p.y  #9MEM#3#9 Store p.y +MEM#3 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123MemPhi y  #11MEM#3#11 MemPhi y +MEM#3 + +[0] → — ASSOC +[1] → #9 MEM +[2] → #19 MEM012Phi arg  #12#12 Phi arg +Type not computed + +[0] → — ASSOC +[1] → #4 DATA +[2] → #21 DATA012True  #15/0#15 True +Projection 0 of #0 +Type not computed + +False  #16/1#16 False +Projection 1 of #0 +Type not computed + +Load p.y  #17#17 Load p.y +Type not computed + +[0] → #15 CTRL +[1] → #11 MEM +[2] → #5 DATA +[3] → — DATA0123+  #18#18 + +Type not computed + +[0] → — CTRL +[1] → #17 DATA +[2] → #12 DATA012Store p.y  #19MEM#3#19 Store p.y +MEM#3 + +[0] → #15 CTRL +[1] → #11 MEM +[2] → #5 DATA +[3] → #18 DATA0123#1  #20#20 #1 +Type not computed + +[0] → #1 ASSOC0-  #21#21 - +Type not computed + +[0] → — CTRL +[1] → #12 DATA +[2] → #20 DATA012MemMerge  #22#22 MemMerge +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #8 MEM +[3] → #11 MEM0123Load p.x  #23#23 Load p.x +Type not computed + +[0] → #16 CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → — DATA0123Return  #24#24 Return +Type not computed + +[0] → — CTRL +[1] → #22 MEM +[2] → #23 DATA012 diff --git a/docs/chapter11/example2a.gv b/docs/chapter11/example2a.gv new file mode 100644 index 00000000..187e63b9 --- /dev/null +++ b/docs/chapter11/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="Default memory" shape=octagon style="filled" fillcolor="#dcecff"]; + X [label="Store x" shape=octagon style="filled" fillcolor="#dcecff"]; + Y [label="Store y" shape=octagon style="filled" fillcolor="#dcecff"]; + X -> M [color="#2867b2"]; Y -> M [color="#2867b2"]; + MemMerge -> M [xlabel="default",color="#2867b2"]; MemMerge -> X [xlabel="x",color="#2867b2"]; + MemMerge -> Y [xlabel="y",color="#2867b2"]; Return -> MemMerge [color="#2867b2"]; + Return [shape=box style="filled" fillcolor="#fff1c4"]; + MemMerge [shape=octagon style="filled" fillcolor="#dcecff"]; +} diff --git a/docs/chapter11/example2a.json b/docs/chapter11/example2a.json new file mode 100644 index 00000000..b9e84d5a --- /dev/null +++ b/docs/chapter11/example2a.json @@ -0,0 +1,20 @@ +{ + "ver": 1, + "comp": "chapter11/docs/example2a.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": 7, "label": "Store p.x", "type": "MEM#2", "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": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "#42", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 9, "label": "Store p.y", "type": "MEM#3", "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": 8, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 7, "role": "MEM", "label": null}, {"idx": 3, "def": 9, "role": "MEM", "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": 5, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter11/example2a.svg b/docs/chapter11/example2a.svg new file mode 100644 index 00000000..b43a55b4 --- /dev/null +++ b/docs/chapter11/example2a.svg @@ -0,0 +1,103 @@ +#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #4 · DATA#8[0] → #1 · ASSOC#9[1] → #3 · MEM#9[2] → #5 · DATA#9[3] → #8 · DATA#10[1] → #3 · MEM#10[2] → #7 · MEM#10[3] → #9 · MEM#11[1] → #10 · MEM#11[2] → #5 · DATAStart  #1#1 Start +Type not computed + +$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Point  #5#5 new Point +Type not computed + +[0] → — CTRL0Store p.x  #7MEM#2#7 Store p.x +MEM#2 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #4 DATA0123#42  #8#8 #42 +Type not computed + +[0] → #1 ASSOC0Store p.y  #9MEM#3#9 Store p.y +MEM#3 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #8 DATA0123MemMerge  #10#10 MemMerge +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #7 MEM +[3] → #9 MEM0123Return  #11#11 Return +Type not computed + +[0] → — CTRL +[1] → #10 MEM +[2] → #5 DATA012 diff --git a/docs/chapter11/example2b-final.json b/docs/chapter11/example2b-final.json new file mode 100644 index 00000000..b0a7a2f3 --- /dev/null +++ b/docs/chapter11/example2b-final.json @@ -0,0 +1,251 @@ +{ + "ver": 1, + "comp": "chapter11/docs/example2b-final.svg", + "step": 100, + "roots": [ + 23 + ], + "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": 8, + "label": "Store p.y", + "type": "MEM#3", + "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": 13, + "label": "#3", + "type": null, + "kind": "DATA", + "edges": [ + { + "idx": 0, + "def": 1, + "role": "ASSOC", + "label": null + } + ], + "proj": null + }, + { + "id": 15, + "label": "#4", + "type": null, + "kind": "DATA", + "edges": [ + { + "idx": 0, + "def": 1, + "role": "ASSOC", + "label": null + } + ], + "proj": null + }, + { + "id": 22, + "label": "MemMerge", + "type": null, + "kind": "MEM", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 3, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 27, + "role": "MEM", + "label": null + }, + { + "idx": 3, + "def": 8, + "role": "MEM", + "label": null + } + ], + "proj": null + }, + { + "id": 23, + "label": "Return", + "type": null, + "kind": "CTRL", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 22, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 5, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 27, + "label": "Store p.x", + "type": "MEM#2", + "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": 28, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 28, + "label": "Phi x value", + "type": null, + "kind": "PHI", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "ASSOC", + "label": null + }, + { + "idx": 1, + "def": 13, + "role": "DATA", + "label": null + }, + { + "idx": 2, + "def": 15, + "role": "DATA", + "label": null + } + ], + "proj": null + } + ], + "groups": [] +} diff --git a/docs/chapter11/example2b-final.svg b/docs/chapter11/example2b-final.svg new file mode 100644 index 00000000..163d7fce --- /dev/null +++ b/docs/chapter11/example2b-final.svg @@ -0,0 +1,110 @@ +#6[0] → #1 · ASSOC#8[1] → #3 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#13[0] → #1 · ASSOC#15[0] → #1 · ASSOC#22[1] → #3 · MEM#22[2] → #27 · MEM#22[3] → #8 · MEM#23[1] → #22 · MEM#23[2] → #5 · DATA#27[1] → #3 · MEM#27[2] → #5 · DATA#27[3] → #28 · DATA#28[1] → #13 · DATA#28[2] → #15 · DATAStart  #1#1 Start +Type not computed + +$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMnew Point  #5#5 new Point +Type not computed + +[0] → — CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.y  #8MEM#3#8 Store p.y +MEM#3 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123#3  #13#13 #3 +Type not computed + +[0] → #1 ASSOC0#4  #15#15 #4 +Type not computed + +[0] → #1 ASSOC0MemMerge  #22#22 MemMerge +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #27 MEM +[3] → #8 MEM0123Return  #23#23 Return +Type not computed + +[0] → — CTRL +[1] → #22 MEM +[2] → #5 DATA012Store p.x  #27MEM#2#27 Store p.x +MEM#2 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #28 DATA0123Phi x value  #28#28 Phi x value +Type not computed + +[0] → — ASSOC +[1] → #13 DATA +[2] → #15 DATA012 diff --git a/docs/chapter11/example2b-merged.json b/docs/chapter11/example2b-merged.json new file mode 100644 index 00000000..914b7cfb --- /dev/null +++ b/docs/chapter11/example2b-merged.json @@ -0,0 +1,339 @@ +{ + "ver": 1, + "comp": "chapter11/docs/example2b-merged.svg", + "step": 8, + "roots": [ + 23 + ], + "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": "MEM#2", + "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": "MEM#3", + "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": 11, + "label": "True", + "type": null, + "kind": "CTRL", + "edges": [], + "proj": { + "par": 0, + "idx": 0 + } + }, + { + "id": 12, + "label": "False", + "type": null, + "kind": "CTRL", + "edges": [], + "proj": { + "par": 0, + "idx": 1 + } + }, + { + "id": 13, + "label": "#3", + "type": null, + "kind": "DATA", + "edges": [ + { + "idx": 0, + "def": 1, + "role": "ASSOC", + "label": null + } + ], + "proj": null + }, + { + "id": 14, + "label": "Store p.x", + "type": "MEM#2", + "kind": "MEM", + "edges": [ + { + "idx": 0, + "def": 11, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 7, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 5, + "role": "DATA", + "label": null + }, + { + "idx": 3, + "def": 13, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 15, + "label": "#4", + "type": null, + "kind": "DATA", + "edges": [ + { + "idx": 0, + "def": 1, + "role": "ASSOC", + "label": null + } + ], + "proj": null + }, + { + "id": 16, + "label": "Store p.x", + "type": "MEM#2", + "kind": "MEM", + "edges": [ + { + "idx": 0, + "def": 12, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 7, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 5, + "role": "DATA", + "label": null + }, + { + "idx": 3, + "def": 15, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 20, + "label": "MemPhi x", + "type": "MEM#2", + "kind": "PHI", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "ASSOC", + "label": null + }, + { + "idx": 1, + "def": 14, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 16, + "role": "MEM", + "label": null + } + ], + "proj": null + }, + { + "id": 22, + "label": "MemMerge", + "type": null, + "kind": "MEM", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 3, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 20, + "role": "MEM", + "label": null + }, + { + "idx": 3, + "def": 8, + "role": "MEM", + "label": null + } + ], + "proj": null + }, + { + "id": 23, + "label": "Return", + "type": null, + "kind": "CTRL", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 22, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 5, + "role": "DATA", + "label": null + } + ], + "proj": null + } + ], + "groups": [] +} diff --git a/docs/chapter11/example2b-merged.svg b/docs/chapter11/example2b-merged.svg new file mode 100644 index 00000000..21ae615e --- /dev/null +++ b/docs/chapter11/example2b-merged.svg @@ -0,0 +1,130 @@ +#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #3 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#13[0] → #1 · ASSOC#14[0] → #11 · CTRL#14[1] → #7 · MEM#14[2] → #5 · DATA#14[3] → #13 · DATA#15[0] → #1 · ASSOC#16[0] → #12 · CTRL#16[1] → #7 · MEM#16[2] → #5 · DATA#16[3] → #15 · DATA#20[1] → #14 · MEM#20[2] → #16 · MEM#22[1] → #3 · MEM#22[2] → #20 · MEM#22[3] → #8 · MEM#23[1] → #22 · MEM#23[2] → #5 · DATAStart  #1#1 Start +Type not computed + +$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMnew Point  #5#5 new Point +Type not computed + +[0] → — CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7MEM#2#7 Store p.x +MEM#2 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8MEM#3#8 Store p.y +MEM#3 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123True  #11/0#11 True +Projection 0 of #0 +Type not computed + +False  #12/1#12 False +Projection 1 of #0 +Type not computed + +#3  #13#13 #3 +Type not computed + +[0] → #1 ASSOC0Store p.x  #14MEM#2#14 Store p.x +MEM#2 + +[0] → #11 CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #13 DATA0123#4  #15#15 #4 +Type not computed + +[0] → #1 ASSOC0Store p.x  #16MEM#2#16 Store p.x +MEM#2 + +[0] → #12 CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #15 DATA0123MemPhi x  #20MEM#2#20 MemPhi x +MEM#2 + +[0] → — ASSOC +[1] → #14 MEM +[2] → #16 MEM012MemMerge  #22#22 MemMerge +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #20 MEM +[3] → #8 MEM0123Return  #23#23 Return +Type not computed + +[0] → — CTRL +[1] → #22 MEM +[2] → #5 DATA012 diff --git a/docs/chapter11/example2b-split-y.json b/docs/chapter11/example2b-split-y.json new file mode 100644 index 00000000..fc3c8758 --- /dev/null +++ b/docs/chapter11/example2b-split-y.json @@ -0,0 +1,486 @@ +{ + "ver": 1, + "comp": "chapter11/docs/example2b-split-y.svg", + "step": 3, + "roots": [ + 23 + ], + "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": "MEM#2", + "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": "MEM#3", + "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": 11, + "label": "True", + "type": null, + "kind": "CTRL", + "edges": [], + "proj": { + "par": 0, + "idx": 0 + } + }, + { + "id": 12, + "label": "False", + "type": null, + "kind": "CTRL", + "edges": [], + "proj": { + "par": 0, + "idx": 1 + } + }, + { + "id": 13, + "label": "#3", + "type": null, + "kind": "DATA", + "edges": [ + { + "idx": 0, + "def": 1, + "role": "ASSOC", + "label": null + } + ], + "proj": null + }, + { + "id": 14, + "label": "Store p.x", + "type": "MEM#2", + "kind": "MEM", + "edges": [ + { + "idx": 0, + "def": 11, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 7, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 5, + "role": "DATA", + "label": null + }, + { + "idx": 3, + "def": 13, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 15, + "label": "#4", + "type": null, + "kind": "DATA", + "edges": [ + { + "idx": 0, + "def": 1, + "role": "ASSOC", + "label": null + } + ], + "proj": null + }, + { + "id": 16, + "label": "Store p.x", + "type": "MEM#2", + "kind": "MEM", + "edges": [ + { + "idx": 0, + "def": 12, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 7, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 5, + "role": "DATA", + "label": null + }, + { + "idx": 3, + "def": 15, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 17, + "label": "MemMerge", + "type": null, + "kind": "MEM", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 3, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 14, + "role": "MEM", + "label": null + }, + { + "idx": 3, + "def": 8, + "role": "MEM", + "label": null + } + ], + "proj": null + }, + { + "id": 18, + "label": "MemMerge", + "type": null, + "kind": "MEM", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 3, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 16, + "role": "MEM", + "label": null + }, + { + "idx": 3, + "def": 8, + "role": "MEM", + "label": null + } + ], + "proj": null + }, + { + "id": 20, + "label": "MemPhi x", + "type": "MEM#2", + "kind": "PHI", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "ASSOC", + "label": null + }, + { + "idx": 1, + "def": 14, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 16, + "role": "MEM", + "label": null + } + ], + "proj": null + }, + { + "id": 22, + "label": "MemMerge", + "type": null, + "kind": "MEM", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 26, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 20, + "role": "MEM", + "label": null + } + ], + "proj": null + }, + { + "id": 23, + "label": "Return", + "type": null, + "kind": "CTRL", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 22, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 5, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 24, + "label": "MemPhi y", + "type": "MEM#3", + "kind": "PHI", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "ASSOC", + "label": null + }, + { + "idx": 1, + "def": 8, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 8, + "role": "MEM", + "label": null + } + ], + "proj": null + }, + { + "id": 25, + "label": "BulkMemPhi except x,y", + "type": null, + "kind": "PHI", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "ASSOC", + "label": null + }, + { + "idx": 1, + "def": 17, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 18, + "role": "MEM", + "label": null + } + ], + "proj": null + }, + { + "id": 26, + "label": "MemMerge", + "type": null, + "kind": "MEM", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 25, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 20, + "role": "MEM", + "label": null + }, + { + "idx": 3, + "def": 24, + "role": "MEM", + "label": null + } + ], + "proj": null + } + ], + "groups": [] +} diff --git a/docs/chapter11/example2b-split-y.svg b/docs/chapter11/example2b-split-y.svg new file mode 100644 index 00000000..f4d4b9b6 --- /dev/null +++ b/docs/chapter11/example2b-split-y.svg @@ -0,0 +1,157 @@ +#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #3 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#13[0] → #1 · ASSOC#14[0] → #11 · CTRL#14[1] → #7 · MEM#14[2] → #5 · DATA#14[3] → #13 · DATA#15[0] → #1 · ASSOC#16[0] → #12 · CTRL#16[1] → #7 · MEM#16[2] → #5 · DATA#16[3] → #15 · DATA#17[1] → #3 · MEM#17[2] → #14 · MEM#17[3] → #8 · MEM#18[1] → #3 · MEM#18[2] → #16 · MEM#18[3] → #8 · MEM#20[1] → #14 · MEM#20[2] → #16 · MEM#22[1] → #26 · MEM#22[2] → #20 · MEM#23[1] → #22 · MEM#23[2] → #5 · DATA#24[1] → #8 · MEM#24[2] → #8 · MEM#25[1] → #17 · MEM#25[2] → #18 · MEM#26[1] → #25 · MEM#26[2] → #20 · MEM#26[3] → #24 · MEMStart  #1#1 Start +Type not computed + +$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMnew Point  #5#5 new Point +Type not computed + +[0] → — CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7MEM#2#7 Store p.x +MEM#2 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8MEM#3#8 Store p.y +MEM#3 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123True  #11/0#11 True +Projection 0 of #0 +Type not computed + +False  #12/1#12 False +Projection 1 of #0 +Type not computed + +#3  #13#13 #3 +Type not computed + +[0] → #1 ASSOC0Store p.x  #14MEM#2#14 Store p.x +MEM#2 + +[0] → #11 CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #13 DATA0123#4  #15#15 #4 +Type not computed + +[0] → #1 ASSOC0Store p.x  #16MEM#2#16 Store p.x +MEM#2 + +[0] → #12 CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #15 DATA0123MemMerge  #17#17 MemMerge +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #14 MEM +[3] → #8 MEM0123MemMerge  #18#18 MemMerge +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #16 MEM +[3] → #8 MEM0123MemPhi x  #20MEM#2#20 MemPhi x +MEM#2 + +[0] → — ASSOC +[1] → #14 MEM +[2] → #16 MEM012MemMerge  #22#22 MemMerge +Type not computed + +[0] → — CTRL +[1] → #26 MEM +[2] → #20 MEM012Return  #23#23 Return +Type not computed + +[0] → — CTRL +[1] → #22 MEM +[2] → #5 DATA012MemPhi y  #24MEM#3#24 MemPhi y +MEM#3 + +[0] → — ASSOC +[1] → #8 MEM +[2] → #8 MEM012BulkMemPhi except x,y  #25#25 BulkMemPhi except x,y +Type not computed + +[0] → — ASSOC +[1] → #17 MEM +[2] → #18 MEM012MemMerge  #26#26 MemMerge +Type not computed + +[0] → — CTRL +[1] → #25 MEM +[2] → #20 MEM +[3] → #24 MEM0123 diff --git a/docs/chapter11/example2b.gv b/docs/chapter11/example2b.gv new file mode 100644 index 00000000..39b87a6a --- /dev/null +++ b/docs/chapter11/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="MemPhi(x)" shape=hexagon style="filled" fillcolor="#f5e4fa"]; + B [label="BulkMemPhi(All except x)" shape=hexagon style="filled" fillcolor="#f5e4fa"]; + P -> Left [xlabel="slice x",color="#2867b2"]; P -> Right [xlabel="slice x",color="#2867b2"]; + B -> Left [color="#2867b2"]; B -> Right [color="#2867b2"]; + P -> Region [style=dashed,color="#9396a3"]; B -> Region [style=dashed,color="#9396a3"]; + MemMerge -> P [xlabel="x",color="#2867b2"]; MemMerge -> B [xlabel="default",color="#2867b2"]; + MemMerge [shape=octagon style="filled" fillcolor="#dcecff"]; + Left [shape=octagon style="filled" fillcolor="#dcecff"]; + Right [shape=octagon style="filled" fillcolor="#dcecff"]; + Region [shape=trapezium style="filled" fillcolor="#fff1c4"]; +} diff --git a/docs/chapter11/example2b.json b/docs/chapter11/example2b.json new file mode 100644 index 00000000..702773ea --- /dev/null +++ b/docs/chapter11/example2b.json @@ -0,0 +1,30 @@ +{ + "ver": 1, + "comp": "chapter11/docs/example2b.svg", + "step": 1, + "roots": [23], + "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": "MEM#2", "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": "MEM#3", "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": 9, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 7, "role": "MEM", "label": null}, {"idx": 3, "def": 8, "role": "MEM", "label": null}], "proj": null}, + {"id": 11, "label": "True", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 0}}, + {"id": 12, "label": "False", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 1}}, + {"id": 13, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 14, "label": "Store p.x", "type": "MEM#2", "kind": "MEM", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "#4", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 16, "label": "Store p.x", "type": "MEM#2", "kind": "MEM", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}, {"idx": 3, "def": 15, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 9, "role": "MEM", "label": null}, {"idx": 2, "def": 14, "role": "MEM", "label": null}], "proj": null}, + {"id": 18, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 9, "role": "MEM", "label": null}, {"idx": 2, "def": 16, "role": "MEM", "label": null}], "proj": null}, + {"id": 20, "label": "MemPhi x", "type": "MEM#2", "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 16, "role": "MEM", "label": null}], "proj": null}, + {"id": 21, "label": "BulkMemPhi except x", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 17, "role": "MEM", "label": null}, {"idx": 2, "def": 18, "role": "MEM", "label": null}], "proj": null}, + {"id": 22, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 21, "role": "MEM", "label": null}, {"idx": 2, "def": 20, "role": "MEM", "label": null}], "proj": null}, + {"id": 23, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 22, "role": "MEM", "label": null}, {"idx": 2, "def": 5, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter11/example2b.svg b/docs/chapter11/example2b.svg new file mode 100644 index 00000000..54ddad9d --- /dev/null +++ b/docs/chapter11/example2b.svg @@ -0,0 +1,150 @@ +#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #3 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#9[1] → #3 · MEM#9[2] → #7 · MEM#9[3] → #8 · MEM#13[0] → #1 · ASSOC#14[0] → #11 · CTRL#14[1] → #7 · MEM#14[2] → #5 · DATA#14[3] → #13 · DATA#15[0] → #1 · ASSOC#16[0] → #12 · CTRL#16[1] → #7 · MEM#16[2] → #5 · DATA#16[3] → #15 · DATA#17[1] → #9 · MEM#17[2] → #14 · MEM#18[1] → #9 · MEM#18[2] → #16 · MEM#20[1] → #14 · MEM#20[2] → #16 · MEM#21[1] → #17 · MEM#21[2] → #18 · MEM#22[1] → #21 · MEM#22[2] → #20 · MEM#23[1] → #22 · MEM#23[2] → #5 · DATAStart  #1#1 Start +Type not computed + +$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMnew Point  #5#5 new Point +Type not computed + +[0] → — CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7MEM#2#7 Store p.x +MEM#2 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8MEM#3#8 Store p.y +MEM#3 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123MemMerge  #9#9 MemMerge +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #7 MEM +[3] → #8 MEM0123True  #11/0#11 True +Projection 0 of #0 +Type not computed + +False  #12/1#12 False +Projection 1 of #0 +Type not computed + +#3  #13#13 #3 +Type not computed + +[0] → #1 ASSOC0Store p.x  #14MEM#2#14 Store p.x +MEM#2 + +[0] → #11 CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #13 DATA0123#4  #15#15 #4 +Type not computed + +[0] → #1 ASSOC0Store p.x  #16MEM#2#16 Store p.x +MEM#2 + +[0] → #12 CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #15 DATA0123MemMerge  #17#17 MemMerge +Type not computed + +[0] → — CTRL +[1] → #9 MEM +[2] → #14 MEM012MemMerge  #18#18 MemMerge +Type not computed + +[0] → — CTRL +[1] → #9 MEM +[2] → #16 MEM012MemPhi x  #20MEM#2#20 MemPhi x +MEM#2 + +[0] → — ASSOC +[1] → #14 MEM +[2] → #16 MEM012BulkMemPhi except x  #21#21 BulkMemPhi except x +Type not computed + +[0] → — ASSOC +[1] → #17 MEM +[2] → #18 MEM012MemMerge  #22#22 MemMerge +Type not computed + +[0] → — CTRL +[1] → #21 MEM +[2] → #20 MEM012Return  #23#23 Return +Type not computed + +[0] → — CTRL +[1] → #22 MEM +[2] → #5 DATA012 diff --git a/docs/chapter11/example2c.gv b/docs/chapter11/example2c.gv new file mode 100644 index 00000000..b32d186d --- /dev/null +++ b/docs/chapter11/example2c.gv @@ -0,0 +1,15 @@ +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 x 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"]; + Y [label="Store p.y: independent" shape=octagon style="filled" fillcolor="#dcecff"]; +} diff --git a/docs/chapter11/example2c.json b/docs/chapter11/example2c.json new file mode 100644 index 00000000..c25fa5b8 --- /dev/null +++ b/docs/chapter11/example2c.json @@ -0,0 +1,23 @@ +{ + "ver": 1, + "comp": "chapter11/docs/example2c.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": "MEM#2", "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": "MEM#3", "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": 9, "label": "Load p.x", "type": null, "kind": "DATA", "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": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "Store p.x", "type": "MEM#2", "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": 11, "label": "Store p.y", "type": "MEM#3", "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": 12, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 3, "role": "MEM", "label": null}, {"idx": 2, "def": 10, "role": "MEM", "label": null}, {"idx": 3, "def": 11, "role": "MEM", "label": null}], "proj": null}, + {"id": 13, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 12, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter11/example2c.svg b/docs/chapter11/example2c.svg new file mode 100644 index 00000000..01bbe10a --- /dev/null +++ b/docs/chapter11/example2c.svg @@ -0,0 +1,121 @@ +#6[0] → #1 · ASSOC#7[1] → #3 · MEM#7[2] → #5 · DATA#7[3] → #6 · DATA#8[1] → #3 · MEM#8[2] → #5 · DATA#8[3] → #6 · DATA#9[1] → #7 · MEM#9[2] → #5 · DATA#10[1] → #7 · MEM#10[2] → #5 · DATA#10[3] → #4 · DATA#11[1] → #8 · MEM#11[2] → #5 · DATA#11[3] → #4 · DATA#12[1] → #3 · MEM#12[2] → #10 · MEM#12[3] → #11 · MEM#13[1] → #12 · MEM#13[2] → #9 · DATAStart  #1#1 Start +Type not computed + +$mem  #3/1#3 $mem +Projection 1 of #1 +Type not computed + +[0] → #1 MEMarg  #4/2#4 arg +Projection 2 of #1 +Type not computed + +[0] → #1 DATAnew Point  #5#5 new Point +Type not computed + +[0] → — CTRL0#0  #6#6 #0 +Type not computed + +[0] → #1 ASSOC0Store p.x  #7MEM#2#7 Store p.x +MEM#2 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Store p.y  #8MEM#3#8 Store p.y +MEM#3 + +[0] → — CTRL +[1] → #3 MEM +[2] → #5 DATA +[3] → #6 DATA0123Load p.x  #9#9 Load p.x +Type not computed + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → — DATA0123Store p.x  #10MEM#2#10 Store p.x +MEM#2 + +[0] → — CTRL +[1] → #7 MEM +[2] → #5 DATA +[3] → #4 DATA0123Store p.y  #11MEM#3#11 Store p.y +MEM#3 + +[0] → — CTRL +[1] → #8 MEM +[2] → #5 DATA +[3] → #4 DATA0123MemMerge  #12#12 MemMerge +Type not computed + +[0] → — CTRL +[1] → #3 MEM +[2] → #10 MEM +[3] → #11 MEM0123Return  #13#13 Return +Type not computed + +[0] → — CTRL +[1] → #12 MEM +[2] → #9 DATA012 diff --git a/docs/chapter11/lattice.gv b/docs/chapter11/lattice.gv new file mode 100644 index 00000000..93d99dd8 --- /dev/null +++ b/docs/chapter11/lattice.gv @@ -0,0 +1,133 @@ +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\nprecise alias slices"; fontname="Arial"; color="#cccccc"; + node [fillcolor="#00008b", fontcolor=white]; + MEM_TOP [label="⊤:mem"]; + MEM_BOT [label="⊥:mem"]; + MEM_ALIAS2 [label="MEM#2"]; + MEM_ALIAS3 [label="MEM#3"]; + MEM_MORE [label="…"]; + {rank=same; MEM_ALIAS2; MEM_ALIAS3; MEM_MORE;} + MEM_ALIAS2 -> MEM_ALIAS3 -> MEM_MORE [style=invis]; + MEM_TOP -> {MEM_ALIAS2 MEM_ALIAS3 MEM_MORE}; + {MEM_ALIAS2 MEM_ALIAS3 MEM_MORE} -> MEM_BOT; + } + + subgraph cluster_tuple { + label="Tuple\ncollection of types"; + fontname="Arial"; color="#cccccc"; + node [fillcolor="#ffc0cb"]; + TUPLE_TOP [label="⊤:tuple"]; + TUPLE_BOT [label="⊥:tuple"]; + // Each black element stands for a recursively nested type lattice. + TUPLE1 [shape=plain, label=< + + + +
tuple
type
+ >]; + TUPLE2 [shape=plain, label=< + + + + +
tuple
type
type
+ >]; + TUPLEN [shape=plain, label=< + + + + + +
tuple
type
…
type
+ >]; + {rank=same; TUPLE1; TUPLE2; TUPLEN;} + TUPLE1 -> TUPLE2 -> TUPLEN [style=invis]; + TUPLE_TOP -> {TUPLE1 TUPLE2 TUPLEN}; + {TUPLE1 TUPLE2 TUPLEN} -> TUPLE_BOT; + } + + TOP -> {XCTRL INT_TOP PTR_TOP STRUCT_TOP MEM_TOP TUPLE_TOP}; + {CTRL INT_BOT PTR_BOT STRUCT_BOT MEM_BOT TUPLE_BOT} -> BOT; + {rank=same; XCTRL; INT_TOP; PTR_TOP; STRUCT_TOP; MEM_TOP; TUPLE_TOP;} + {rank=same; CTRL; INT_BOT; PTR_BOT; STRUCT_BOT; MEM_BOT; TUPLE_BOT;} + XCTRL -> INT_TOP -> PTR_TOP -> STRUCT_TOP -> MEM_TOP -> TUPLE_TOP [style=invis]; +} diff --git a/docs/chapter11/lattice.svg b/docs/chapter11/lattice.svg new file mode 100644 index 00000000..8d2e2875 --- /dev/null +++ b/docs/chapter11/lattice.svg @@ -0,0 +1,644 @@ + + + + + + +Lattice + + +cluster_control + +Control + + +cluster_integer + +Integer + + +cluster_pointer + +Pointer = nullability × struct type + + +cluster_struct + +Struct +named collection of named scalar types + + +cluster_memory + +Memory +precise alias slices + + +cluster_tuple + +Tuple +collection of types + + + +TOP + +⊤ + + + +XCTRL + +⊤:ctrl + + + +TOP->XCTRL + + + + + +INT_TOP + +⊤:int + + + +TOP->INT_TOP + + + + + +PTR_TOP + +⊤:ptr +[*⊤:struct] + + + +TOP->PTR_TOP + + + + + +STRUCT_TOP + +⊤:struct +[struct top] + + + +TOP->STRUCT_TOP + + + + + +MEM_TOP + +⊤:mem + + + +TOP->MEM_TOP + + + + + +TUPLE_TOP + +⊤:tuple + + + +TOP->TUPLE_TOP + + + + + +BOT + +⊥ + + + +CTRL + +⊥:ctrl + + + +XCTRL->CTRL + + + + + + +CTRL->BOT + + + + + +INT_NEG + +… −2, −1 + + + +INT_TOP->INT_NEG + + + + + +INT_ZERO + +0 + + + +INT_TOP->INT_ZERO + + + + + +INT_POS + +1, 2, … + + + +INT_TOP->INT_POS + + + + + + +INT_BOT + +⊥:int + + + +INT_BOT->BOT + + + + + +INT_NEG->INT_BOT + + + + + + +INT_ZERO->INT_BOT + + + + + + +INT_POS->INT_BOT + + + + + +PTR_NULL + +null + + + +PTR_TOP->PTR_NULL + + + + + +PTR_PERSON + +*Person + + + +PTR_TOP->PTR_PERSON + + + + + +PTR_S1 + +*s1 + + + +PTR_TOP->PTR_S1 + + + + + +PTR_MORE + +*s2, … + + + +PTR_TOP->PTR_MORE + + + + + + +PTR_BOT + +⊥:ptr +[*⊥:struct?] + + + +PTR_BOT->BOT + + + + + +PTR_PERSON_NIL + +*Person? + + + +PTR_NULL->PTR_PERSON_NIL + + + + + +PTR_S1_NIL + +*s1? + + + +PTR_NULL->PTR_S1_NIL + + + + + +PTR_MORE_NIL + +*s2?, … + + + +PTR_NULL->PTR_MORE_NIL + + + + + +PTR_ANY + +*⊥:struct +[ptr any struct] + + + +PTR_ANY->PTR_BOT + + + + + + +PTR_PERSON->PTR_ANY + + + + + + +PTR_PERSON->PTR_PERSON_NIL + + + + + +PTR_S1->PTR_ANY + + + + + + +PTR_S1->PTR_S1_NIL + + + + + + +PTR_MORE->PTR_ANY + + + + + +PTR_MORE->PTR_MORE_NIL + + + + + +PTR_PERSON_NIL->PTR_BOT + + + + + + +PTR_S1_NIL->PTR_BOT + + + + + + +PTR_MORE_NIL->PTR_BOT + + + + + +STRUCT_PERSON + +Person +age: int + + + +STRUCT_TOP->STRUCT_PERSON + + + + + +STRUCT_S1 + +s1 +x: int + + + +STRUCT_TOP->STRUCT_S1 + + + + + +STRUCT_S2 + +s2 +x: int, y: int + + + +STRUCT_TOP->STRUCT_S2 + + + + + +STRUCT_MORE + +… + + + +STRUCT_TOP->STRUCT_MORE + + + + + + +STRUCT_BOT + +⊥:struct +[struct bottom] + + + +STRUCT_BOT->BOT + + + + + +STRUCT_PERSON->STRUCT_BOT + + + + + + +STRUCT_S1->STRUCT_BOT + + + + + + +STRUCT_S2->STRUCT_BOT + + + + + + +STRUCT_MORE->STRUCT_BOT + + + + + +MEM_ALIAS2 + +MEM#2 + + + +MEM_TOP->MEM_ALIAS2 + + + + + +MEM_ALIAS3 + +MEM#3 + + + +MEM_TOP->MEM_ALIAS3 + + + + + +MEM_MORE + +… + + + +MEM_TOP->MEM_MORE + + + + + + +MEM_BOT + +⊥:mem + + + +MEM_BOT->BOT + + + + + +MEM_ALIAS2->MEM_BOT + + + + + + +MEM_ALIAS3->MEM_BOT + + + + + + +MEM_MORE->MEM_BOT + + + + + +TUPLE1 + + + +tuple + + +type + + + +TUPLE_TOP->TUPLE1 + + + + + +TUPLE2 + + + +tuple + + +type + + +type + + + +TUPLE_TOP->TUPLE2 + + + + + +TUPLEN + + + +tuple + + +type + + +… + + +type + + + +TUPLE_TOP->TUPLEN + + + + + +TUPLE_BOT + +⊥:tuple + + + +TUPLE_BOT->BOT + + + + + +TUPLE1->TUPLE_BOT + + + + + + +TUPLE2->TUPLE_BOT + + + + + + +TUPLEN->TUPLE_BOT + + + + + diff --git a/src/main/java/com/seaofnodes/simple/IRPrinter.java b/src/main/java/com/seaofnodes/simple/IRPrinter.java index 621bc2d6..d5ab15fe 100644 --- a/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -9,6 +9,7 @@ public final class IRPrinter extends IRAdapter { new com.seaofnodes.print.IRPrinter<>(new IRPrinter()); @Override public String type(Node n) { return n._type==null ? "" : n._type.str(); } @Override public int inputColumns() { return 3; } + @Override public String inputMark(Node n, Node def) { return n instanceof MemMergeNode && def instanceof MemMergeNode ? "^" : " "; } @Override public Kind kind(Node n) { if( n instanceof StartNode ) return Kind.START; if( n instanceof StopNode ) return Kind.STOP; diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 7734f4df..df8d0b1c 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -33,6 +33,10 @@ public class Parser { public StopNode STOP; + // Field identities are independent of the memory graph and Start's tuple. + private final HashMap _aliases = new HashMap<>(); + private int _alias = 2; + // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; @@ -200,6 +204,8 @@ public class Parser { require("}"); // Build and install the TypeStruct TypeStruct ts = TypeStruct.make(typeName, fields); + _aliases.put(typeName,_alias); + _alias += ts._fields.length; OBJS.put(typeName, ts); // Insert the struct name in the collection of all struct names return parseStatement(); } @@ -589,8 +595,10 @@ public class Parser { private Node newStruct( TypeStruct obj ) { Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep(); Node initValue = new ConstantNode(TypeInteger.constant(0)).peephole(); + int alias = _aliases.get(obj._name); for( Field field : obj._fields ) { - mem(new StoreNode(field._fname, mem(), n, initValue).peephole()); + store(field._fname,alias,n,initValue); + alias++; } return n.unkeep(); } @@ -599,6 +607,13 @@ public class Parser { private Node mem() { return _scope.lookup("$mem"); } private Node mem(Node n) { return _scope.update("$mem",n); } + private void store(String name, int alias, Node ptr, Node val) { + Node prior = mem().keep(); + Node st = new StoreNode(name,alias,prior,ptr,val).peephole(); + mem(new MemMergeNode(prior,alias,st).peephole()); + if( prior.unkeep().isUnused() ) prior.kill(); + } + /** * Parse postfix expression. For now this is just a field * expression, but in future could be array index too. @@ -616,19 +631,20 @@ public class Parser { String name = requireId().intern(); int idx = ptr._obj==null ? -1 : ptr._obj.find(name); if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + int alias = _aliases.get(ptr._obj._name)+idx; if( match("=") ) { // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment if( peek('=') ) _lexer._position--; else { Node val = parseExpression(); - mem(new StoreNode(name, mem(), expr, val).peephole()); + store(name,alias,expr,val); return expr; // "obj.a = expr" returns the expression while updating memory } } Type declaredType = ptr._obj._fields[idx]._type; - return parsePostfix(new LoadNode(name, declaredType, mem(), expr).peephole()); + return parsePostfix(new LoadNode(name, alias, declaredType, mem(), expr).peephole()); } /** diff --git a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java new file mode 100644 index 00000000..8d512f21 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -0,0 +1,237 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; +import java.util.BitSet; + +/** + * A Phi for bulk memory. It covers all aliases except {@link #_aliases}; + * those aliases must be represented by parallel precise MemPhis at the same + * program slice. + */ +public class BulkMemPhiNode extends PhiNode { + + private static final BitSet EMPTY = new BitSet(); + + // Excluded Aliases; empty means NO exclusions. + // Each split clones the exclusions; published sets are never mutated. + public final BitSet _aliases; + + public BulkMemPhiNode(String label, Node... inputs) { + this(label,EMPTY,inputs); + } + + private BulkMemPhiNode(String label, BitSet aliases, Node... inputs) { + super(label,TypeMem.BOT,inputs); + _aliases = aliases; + } + + public boolean isSplit(int alias) { return _aliases.get(alias); } + + @Override public String label() { return "BulkPhi"+_aliases; } + + @Override + public Type compute() { + Type t = super.compute(); + return t instanceof TypeMem mem ? mem : + t==Type.BOTTOM ? TypeMem.BOT : + TypeMem.TOP; + } + + @Override + public Node idealize() { + Node progress = super.idealize(); + if( progress != null ) return progress; + if( ((RegionNode)region()).inProgress() || region().nIns()<=1 ) + return null; // Input is in-progress + + // "Peek through" a MemMerge that covers this alias set on its default + for( int i=1; i= mmm.nIns() || mmm.in(alias)==null) ) + return false; + return true; + } + + + // True if the MemMerge has no precise slice still covered by this Phi. + private boolean canPeek(MemMergeNode mmm) { + return missingAlias(mmm,false)==0; + } + + // Return an alias required by an input but still covered by this Phi, or 0. + private int inputAlias(Node n) { + return switch(n) { + case ProjNode proj -> 0; + case ConstantNode con -> 0; + case MemMergeNode mmm -> missingAlias(mmm,false); + case MemOpNode mem -> unsplit(mem._alias); + case BulkMemPhiNode bulk -> missingAlias(bulk); + default -> throw new AssertionError("Unexpected memory input "+n); + }; + } + + // Return an alias required by a user but still covered by this Phi, or 0. + private int outputAlias(Node use) { + // This decision depends backwards on an immediate user's alias/set. + // Normal graph-neighbor enqueueing flows from defs to uses, so retain + // an explicit forward dependency to revisit this Phi when the user + // sharpens. + use.addDepForwards(this); + return switch(use) { + case ScopeNode scope -> 0; + case MemMergeNode mmm -> missingAlias(mmm,true); + case BulkMemPhiNode bulk -> missingAlias(bulk); + case MemOpNode mem -> unsplit(mem._alias); + case MemPhiNode phi -> unsplit(phi._alias); + default -> { + assert use instanceof ReturnNode + : "Unexpected bulk-memory user "+use; + yield 0; + } + }; + } + + // Alias zero/one is bulk, and an already excluded precise alias cannot + // trigger another split of this Phi. + private int unsplit(int alias) { + if( alias <= 1 ) return 0; + assert !_aliases.get(alias); + return alias; + } + + // First alias excluded by the neighboring bulk Phi but not by this one. + private int missingAlias(BulkMemPhiNode bulk) { + for( int alias = bulk._aliases.nextSetBit(0); alias >= 0; alias = bulk._aliases.nextSetBit(alias+1) ) + if( !_aliases.get(alias) ) + return alias; + return 0; + } + + // First precise MemMerge slice still covered by this Phi. When inspecting + // a user, ignore slots which point back to this Phi. + private int missingAlias(MemMergeNode mmm, boolean user) { + for( int alias=2; alias= 0; old = _aliases.nextSetBit(old+1) ) + { assert old != alias; mmm.alias(old,precisePhi(old));} + mmm.alias(alias,precise); + assert checkMerge(mmm); + return mmm; + } + + // Find or make the precise Phi parallel to this bulk Phi at the same merge. + private Node precisePhi(int alias) { + MemPhiNode mphi = _findPhi(alias); + if( mphi!=null ) return mphi; + + mphi = new MemPhiNode("$"+alias,alias); + mphi.addDef(region()); + // Due to cycles, must set before calling peephole + mphi.setType(TypeMem.make(alias)); + for( int i=1; i= 0; alias = bulk._aliases.nextSetBit(alias+1) ) + if( alias >= mmm.nIns() || mmm.in(alias)==null ) + return false; + return true; + } + + @Override public boolean eq(Node n) { + return _aliases.equals(((BulkMemPhiNode)n)._aliases) && super.eq(n); + } + + @Override int hash() { return _aliases.hashCode(); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 31c7699c..9bf36459 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -2,7 +2,10 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.Field; /** @@ -16,11 +19,11 @@ public class LoadNode extends MemOpNode { * Load a value from a ptr.field. * * @param name The field we are loading - * @param memSlice The whole-memory node - this is updated after a Store + * @param memSlice The memory alias node - this is updated after a Store * @param memPtr The ptr to the struct from where we load a field */ - public LoadNode(String name, Type glb, Node memSlice, Node memPtr) { - super(name, memSlice, memPtr, null); + public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) { + super(name, alias, memSlice, memPtr, null); _declaredType = glb; } @@ -28,15 +31,16 @@ public class LoadNode extends MemOpNode { return super.canDrop(other,dep) && _declaredType==((LoadNode)other)._declaredType && !clobbered(dep); } - // A Store directly clobbers this memory. A Phi might lead to a clobber - // through a cycle; conservatively stop rather than searching beyond it. + // Check only immediate memory users. Stores clobber memory; Phis and + // aggregates might lead to a clobber, so stop rather than search further. private boolean clobbered(Node dep) { Node mem = mem(); mem.addDepForwards(dep); for( Node use : mem._outputs ) { if( use==null ) continue; use.addDepForwards(dep); - if( use instanceof StoreNode || use instanceof PhiNode ) return true; + if( use instanceof StoreNode || use instanceof PhiNode || + use instanceof MemMergeNode ) return true; } return false; } @@ -54,10 +58,16 @@ public class LoadNode extends MemOpNode { @Override public Node idealize() { + if( mem() instanceof MemMergeNode merge ) { + setDef(1,IterPeeps.add(merge.alias(_alias))); + return this; + } + // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && - ptr() == st.ptr() && _name.equals(st._name) ) { // Must check same object + ptr() == st.ptr() && _alias==st._alias ) { // Must check same object + assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect return st.val(); } @@ -68,13 +78,13 @@ public class LoadNode extends MemOpNode { // if( pred ) ptr.x = e0; val = pred ? e0 // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; - if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 ) { + if( mem() instanceof MemPhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 ) { // Profit on RHS/Loop backedge if( profit(memphi,2) || // Else must not be a loop to count profit on LHS. (!(memphi.region() instanceof LoopNode) && profit(memphi,1)) ) { - Node ld1 = new LoadNode(_name,_declaredType,memphi.in(1),ptr()).peephole(); - Node ld2 = new LoadNode(_name,_declaredType,memphi.in(2),ptr()).peephole(); + Node ld1 = new LoadNode(_name,_alias,_declaredType,memphi.in(1),ptr()).peephole(); + Node ld2 = new LoadNode(_name,_alias,_declaredType,memphi.in(2),ptr()).peephole(); return new PhiNode(_name,_type,memphi.region(),ld1,ld2); } } @@ -85,6 +95,6 @@ public class LoadNode extends MemOpNode { // Profitable if we find a matching Store on this Phi arm. private boolean profit(PhiNode phi, int idx) { Node px = phi.in(idx); - return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr() && _name.equals(st1._name); + return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr() && _alias==st1._alias; } } diff --git a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java new file mode 100644 index 00000000..f3d5b01e --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -0,0 +1,61 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; + +/** All memory: a default slice and explicit overrides for individual aliases. */ +public class MemMergeNode extends Node { + public MemMergeNode(Node bulk) { super(null,bulk); _type = TypeMem.BOT; } + public MemMergeNode(Node bulk, int alias, Node precise) { + this(bulk); + alias(alias,precise); + } + + public Node alias(int alias) { + Node n = alias < nIns() ? in(alias) : null; + assert n!=null || !(in(1) instanceof BulkMemPhiNode bulk) || !bulk.isSplit(alias); + return n==null ? in(1) : n; + } + + public void alias(int alias, Node mem) { + assert alias > 1; + while( nIns()<=alias ) addDef(null); + setDef(alias,mem); + } + + @Override public String label() { return "MemMerge"; } + @Override public boolean isMem() { return true; } + @Override public Type compute() { return TypeMem.BOT; } + @Override protected ExprPrinter _print1(ExprPrinter p) { + p.p("MEM["); + for( int i=1; i=nIns() || in(i)==null) ) + alias(i,mem.in(i)); + IterPeeps.add(mem.in(1)); + setDef(1,mem.in(1)); + return this; + } + assert BulkMemPhiNode.checkMerge(this); + return progress ? this : null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 138f8fa5..44304bcb 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.type.Field; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMemPtr; @@ -9,10 +10,12 @@ import com.seaofnodes.simple.type.TypeMemPtr; public abstract class MemOpNode extends Node { public final String _name; + public final int _alias; - public MemOpNode(String name, Node memSlice, Node memPtr, Node value) { + public MemOpNode(String name, int alias, Node memSlice, Node memPtr, Node value) { super(null, memSlice, memPtr, value); _name = name; + _alias = alias; } public Node mem() { return in(1); } @@ -22,19 +25,17 @@ public abstract class MemOpNode extends Node { // The caller has already checked the opcode, input shape and control. boolean canDrop(MemOpNode other, Node dep) { ptr().addDep(dep); - if( !_name.equals(other._name) || err()!=null ) return false; - return !(ptr()._type instanceof TypeMemPtr p && - other.ptr()._type instanceof TypeMemPtr q && p._obj!=q._obj); + return _alias==other._alias && err()==null; } @Override boolean eq(Node n) { MemOpNode mem = (MemOpNode)n; // Invariant - return _name.equals(mem._name); + return _alias==mem._alias; // When comparing types error to use "equals"; always use "==" } @Override - int hash() { return _name.hashCode(); } + int hash() { return _alias; } @Override String err() { diff --git a/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java new file mode 100644 index 00000000..c806bede --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java @@ -0,0 +1,36 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; + +/** A Phi for one field alias, parallel to a bulk Phi at the same Region. */ +public class MemPhiNode extends PhiNode { + public final int _alias; + + public MemPhiNode(String label, int alias, Node... inputs) { + super(label,TypeMem.make(alias),inputs); + assert alias > 1; + _alias = alias; + } + + @Override public String label() { return "MemPhi_"+_alias; } + + @Override public Type compute() { + assert BulkMemPhiNode.checkMem(this,_alias); + Type t = super.compute(); + return t==Type.TOP || t==TypeMem.TOP ? TypeMem.TOP : TypeMem.make(_alias); + } + + @Override public Node idealize() { + for( int i=1; i implements Cloneable { * or output of this node, that is, it is at least one step away. The node * being added must benefit from this node being peepholed. */ - Node addDep(Node dep) { return addDep(dep,false); } + Node addDep( Node dep ) { + return addDep(dep,false); + } + + // A bulk Phi inspects its users' partitions. Def-to-use propagation does + // not revisit that producer when an immediate user's partition changes. Node addDepForwards(Node dep) { return addDep(dep,true); } + private Node addDep(Node dep, boolean forwards) { // Running peepholes during the big assert cannot have side effects // like adding dependencies. @@ -415,7 +421,7 @@ public abstract class Node extends BaseNode implements Cloneable { if( obs != null ) obs.dep(this, dep); if( _deps==null ) _deps = new ArrayList<>(); if( Utils.find(_deps ,dep) != -1 ) return this; // Already on list - if( !forwards && Utils.find(_inputs,dep) != -1 ) return this; // No need for deps on immediate neighbors + if( !forwards && Utils.find(_inputs,dep) != -1 ) return this; if( !forwards && Utils.find(_outputs,dep)!= -1 ) return this; _deps.add(dep); return this; diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 24a72aa4..6995cc2f 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -17,6 +17,10 @@ public class PhiNode extends Node { public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; } + public static PhiNode make(String label, Type type, Node... inputs) { + return type instanceof TypeMem ? new BulkMemPhiNode(label,inputs) : new PhiNode(label,type,inputs); + } + @Override public String label() { return "Phi_"+_label; } @Override @@ -95,7 +99,18 @@ public class PhiNode extends Node { private boolean same_op() { Node op = in(1); if( op.isCFG() || op instanceof ConstantNode || op instanceof PhiNode || - op instanceof ProjNode || op instanceof NewNode || op instanceof ScopeNode ) return false; + op instanceof ProjNode || op instanceof NewNode || op instanceof ScopeNode || op instanceof MemMergeNode ) return false; + // A bulk Phi must split its aliases before factoring precise Stores. + if( this instanceof BulkMemPhiNode ) return false; + // Bulk splitting currently identifies parallel slices by Region/alias. + // Factoring can introduce another slice at a different memory point; + // wait until that Region's bulk partitioning has finished. + if( op instanceof MemOpNode ) + for( Node use : region()._outputs ) + if( use instanceof BulkMemPhiNode ) { + use.addDepForwards(this); + return false; + } Node busy = null; for( int i=1; i { private Parser _parser; private Node _ret; diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index bd9cf458..93e27c76 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -34,7 +34,7 @@ public class Type { static final byte TSIMPLE = 4; // End of the Simple Types static final byte TINT = 5; // All Integers; see TypeInteger static final byte TTUPLE = 6; // Tuples; finite collections of unrelated Types, kept in parallel - static final byte TMEM = 7; // Whole-memory token + static final byte TMEM = 7; // All memory (alias 0) or A slice of memory - with specific alias static final byte TMEMPTR = 8; // Memory pointer type static final byte TSTRUCT = 9; // Structs; tuples with named fields static final byte TFLD =10; // Fields into struct diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index d921bac3..b6fc8824 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -1,20 +1,66 @@ package com.seaofnodes.simple.type; +import com.seaofnodes.simple.Utils; +import java.lang.Long; +import java.util.BitSet; import java.util.ArrayList; -/** A token for all memory; field values are not tracked in its type. */ + +/** + * Represents a slice of memory corresponding to a set of aliases + */ public class TypeMem extends Type { - private final boolean _high; - private TypeMem(boolean high) { super(TMEM); _high = high; } - public static final TypeMem TOP = new TypeMem(true ).intern(); - public static final TypeMem BOT = new TypeMem(false).intern(); - - public static void gather(ArrayList ts) { ts.add(BOT); } - @Override TypeMem xmeet(Type t) { return BOT; } - @Override public Type dual() { return _high ? BOT : TOP; } - @Override public Type glb() { return BOT; } - @Override int hash() { return _high ? 1 : 2; } - @Override boolean eq(Type t) { return _high==((TypeMem)t)._high; } - @Override public StringBuilder print(StringBuilder sb) { return sb.append(_high ? "MemTop" : "MemBot"); } + + // Which slice of memory? + // 0 means TOP, no slice. + // -1 means BOT, all memory. + // N means slice#N. + private final int _alias; + + private TypeMem(int alias) { super(TMEM); _alias = alias; } + + public static TypeMem make(int alias) { return new TypeMem(alias).intern(); } + public static final TypeMem TOP = make( 0); + public static final TypeMem BOT = make(-1); + + + public static void gather(ArrayList ts) { ts.add(make(1)); ts.add(BOT); } + + @Override + TypeMem xmeet(Type t) { + TypeMem that = (TypeMem) t; // Invariant: TypeMem and unequal + return _alias==0 ? that : (that._alias==0 ? this : BOT); + } + + @Override + public Type dual() { + if( _alias== 0 ) return BOT; + if( _alias==-1 ) return TOP; + return this; + } + + @Override + public Type glb() { return TypeMem.BOT; } + + @Override + int hash() { return 9876543 + _alias; } + + @Override + boolean eq(Type t) { + TypeMem that = (TypeMem) t; // Invariant + return _alias == that._alias; + } + + @Override + public StringBuilder print(StringBuilder sb) { + if( this==BOT ) return sb.append("MemBot"); + if( this==TOP ) return sb.append("MemTop"); + return sb.append("MEM#").append( switch(_alias) { + case 0 -> "TOP"; + case -1 -> "BOT"; + default -> ""+_alias; + }); + } + @Override public String str() { return print(new StringBuilder()).toString(); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java index f39b1e78..9a5e4677 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -169,7 +169,7 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,0,(Phi_$mem+2));", stop.toString()); + assertEquals("return Phi(Loop11,0,(Phi_a+2));", stop.toString()); } @Test @@ -221,7 +221,7 @@ if( bar ) bar.a = 1; return bar; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region15,null,new Bar);", stop.toString()); + assertEquals("return Phi(Region16,null,new Bar);", stop.toString()); } @Test @@ -237,7 +237,7 @@ else bar.a = 1; return rez; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region32,4,3);", stop.toString()); + assertEquals("return Phi(Region34,4,3);", stop.toString()); } @Test @@ -290,9 +290,8 @@ while( i.x < i.len ) { return sum; """); StopNode stop = parser.parse().iterate(); - // The preceding len store keeps the initial x load on the bulk chain. - assertEquals("return Phi(Loop13,0,(Phi(Loop,.x,(Phi_x+1))+Phi_sum));", stop.toString()); - assertEquals(10L, com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,5)); + assertEquals("return Phi(Loop16,0,(Phi(Loop,0,(Phi_$2+1))+Phi_sum));", stop.toString()); + assertEquals(10L,Evaluator.evaluate(stop,5)); } @@ -312,7 +311,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,new s0,Phi(Region31,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop11,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString()); } @Test @@ -329,7 +328,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop13,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop15,new s0,Phi(Region35,new s0,Phi_ret));", stop.toString()); } @@ -346,7 +345,7 @@ while(arg < 10) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,new s0,Phi(Region30,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop11,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString()); } @Test @@ -480,8 +479,7 @@ return 0; assertEquals(2244L, com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,1)); } - @Test public void testMemoryAcrossNestedLoops() { - var stop = new Parser(""" + static final String NESTED_MEMORY = """ struct S { int x; int y; int z; } S s = new S; s.x = 5; s.y = 7; s.z = 11; @@ -498,7 +496,10 @@ return 0; arg = arg - 1; } return s; - """).parse().iterate(); + """; + + @Test public void testMemoryAcrossNestedLoops() { + var stop = new Parser(NESTED_MEMORY).parse().iterate(); for (int arg=0; arg<7; arg++) { var obj = (com.seaofnodes.simple.evaluator.Evaluator.Obj) com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,arg); @@ -524,7 +525,7 @@ return 0; } } - @Test public void testDropLoads() { + @Test public void testKeepLoadsAtMerge() { StopNode stop = new Parser(""" struct S { int x; } S a = new S; S b = new S; @@ -535,7 +536,8 @@ return 0; if (arg>1) v=p.x; else v=q.x; return v; """).parse().iterate(); - assertEquals(1,countMemoryNodes(stop,LoadNode.class,new BitSet())); + // The one-step safety check stops at the memory aggregate. + assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet())); assertEquals(-1L,Evaluator.evaluate(stop,-1)); assertEquals(1L,Evaluator.evaluate(stop,0)); assertEquals(3L,Evaluator.evaluate(stop,3)); @@ -548,6 +550,7 @@ return 0; if (arg) s.x=arg+1; else s.x=arg+2; return s; """).parse().iterate(); + // Releasing the old aggregate exposes the overwritten initializing Store. assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); assertEquals(2L,((Evaluator.Obj)Evaluator.evaluate(stop,0)).fields()[0]); assertEquals(4L,((Evaluator.Obj)Evaluator.evaluate(stop,3)).fields()[0]); diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java new file mode 100644 index 00000000..5f92c9c1 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -0,0 +1,64 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.evaluator.Evaluator; +import org.junit.Test; +import static org.junit.Assert.*; + +public class Chapter11Test { + @Test public void testIndependentField() { + var stop = new Parser(""" + struct S { int x; int y; } + S s = new S; + s.x = 42; + while (arg > 0) { s.y = s.y + arg; arg = arg - 1; } + return s.x; + """).parse().iterate(); + assertEquals("return 42;",stop.toString()); + assertEquals(42L,Evaluator.evaluate(stop,5)); + assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); + } + + @Test public void testParallelMemoryPhis() { + var stop = new Parser(""" + struct S { int x; int y; int z; } + S a = new S; S b = new S; + S p = a; if (arg) p = b; + while (arg > 0) { + a.x = p.x + arg; + a.y = p.y + 2; + a.z = p.z + 3; + arg = arg - 1; + } + return a; + """).parse().iterate(); + int[] phis = {0}; + stop.walk(n -> { + if (n instanceof MemPhiNode) phis[0]++; + if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b) + for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1)) + assertTrue(a=3); + assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); + } + + @Test public void testLateSliceWorklist() throws ReflectiveOperationException { + // Seed 97 exposed a store selecting a bulk predecessor without queuing + // it. Keep both the worklist assertion and the final heap check. + for (int seed : new int[]{0,97,123,456}) { + var parser = new Parser(Chapter10Test.NESTED_MEMORY); + var field = IterPeeps.class.getDeclaredField("WORK"); + field.setAccessible(true); + Object work = field.get(null); + field = work.getClass().getDeclaredField("_R"); + field.setAccessible(true); + ((java.util.Random)field.get(work)).setSeed(seed); + var stop = parser.parse().iterate(); + assertArrayEquals(new Object[]{9L,25L,17L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); + } + } +} diff --git a/src/test/java/com/seaofnodes/simple/TypeTest.java b/src/test/java/com/seaofnodes/simple/TypeTest.java index c9eb2747..f9c580cc 100644 --- a/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -22,10 +22,23 @@ public class TypeTest { Assert.assertNotEquals(s1, s1.dual()); Assert.assertEquals(s1, s1.dual().glb()); - assertEquals(TypeStruct.BOT, s1.meet(s2)); - assertEquals(TypeMem.BOT, TypeMem.TOP.meet(TypeMem.BOT)); - assertEquals(TypeMem.TOP, TypeMem.BOT.dual()); - assertEquals(TypeMem.BOT, TypeMem.TOP.dual()); + TypeMem m1 = TypeMem.make(1); + TypeMem m2 = TypeMem.make(2); + TypeMem m3 = TypeMem.make(3); + TypeMem m4 = TypeMem.make(4); + + Assert.assertNotEquals(m1, m2); + Assert.assertNotEquals(m2, m3); + Assert.assertNotEquals(m3, m4); + + Assert.assertEquals(TypeStruct.BOT, s1.meet(s2)); + Assert.assertEquals(TypeMem .BOT, m1.meet(m2)); + Assert.assertEquals(TypeMem .BOT, m2.meet(m3)); + Assert.assertEquals(TypeMem .BOT, m3.meet(m4)); + + Assert.assertEquals(TypeMem.BOT, m1.glb()); + Assert.assertEquals(m1, m1.dual()); + Assert.assertEquals(TypeMem.TOP, m1.glb().dual()); TypeMemPtr ptr1 = TypeMemPtr.make(s1); Assert.assertEquals(s1, ptr1._obj); diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index bddcc596..ac7c5e09 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -138,6 +138,7 @@ public class Evaluator { case CastNode cast -> val(cast.in(1)); case LoadNode load -> load(load); case StoreNode store -> store(store); + case MemMergeNode merge -> MEMORY; case NewNode alloc -> alloc(alloc); case ProjNode proj -> ((Object[])val(proj.ctrl()))[proj._idx]; default -> throw new AssertionError("Unexpected node " + node); diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index 674d12f5..48ac0562 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -215,7 +215,7 @@ public class Scheduler { private void refinePlacement(NodeData data, BasicBlock block) { assert !isPinnedNode(data); data.block = data.block == null ? block : dom(data.block, block); - assert isValid(data); + assert isValid(data) : data.node.uniqueName()+" at "+data.block.entry.uniqueName(); } /** @@ -250,6 +250,12 @@ public class Scheduler { // so do that now. var mem = l.in(1); for(var out : mem._outputs) { + // Aggregates describe partitions; they do not overwrite + // memory. Only users of this alias constrain the load. + if (out instanceof MemMergeNode || out instanceof ReturnNode) continue; + if (out instanceof StoreNode s && s._alias != l._alias) continue; + if (out instanceof MemPhiNode p && p._alias != l._alias) continue; + if (out instanceof BulkMemPhiNode p && p.isSplit(l._alias)) continue; if (out instanceof PhiNode p) { var r = p.in(0); for (int i = 1; i < p.nIns(); i++) { @@ -271,7 +277,7 @@ public class Scheduler { // Store nodes have anti-deps to load nodes. // So decrease the uses of these loads when the store is placed. for (var out: s.in(1)._outputs) { - if (out instanceof LoadNode) od(out).ifPresent(this::decUsers); + if (out instanceof LoadNode l && l._alias==s._alias) od(out).ifPresent(this::decUsers); } } } @@ -467,7 +473,8 @@ public class Scheduler { var data = mem.pop(); node = data.node; for(var out:node.in(1)._outputs) { - if (out instanceof LoadNode) od(out).ifPresent(d->d.users++); + if (out instanceof LoadNode l && l._alias==((StoreNode)node)._alias) + od(out).ifPresent(d->d.users++); } } } -- cgit v1.2.3