From fc06aa2bebec45aa93df5450ebf4c327f9f51496 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 5 Aug 2024 16:15:27 -0700 Subject: Chapter 13: Global Code Motion MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Thalia Archibald Co-authored-by: Dibyendu Majumdar Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- docs/chapter13/Makefile | 1 + docs/chapter13/README.ja.md | 258 +++++++++++++++++++++++++++ docs/chapter13/README.md | 375 ++++++++++++++++++++++++++++++++++++++++ docs/chapter13/graph1.gv | 79 +++++++++ docs/chapter13/graph1.json | 25 +++ docs/chapter13/graph1.svg | 123 +++++++++++++ docs/chapter13/graph2.gv | 84 +++++++++ docs/chapter13/graph2.json | 25 +++ docs/chapter13/graph2.svg | 123 +++++++++++++ docs/chapter13/graph3-snip.jpg | Bin 0 -> 19681 bytes docs/chapter13/graph3-snip.json | 17 ++ docs/chapter13/graph3-snip.svg | 91 ++++++++++ docs/chapter13/graph3.gv | 85 +++++++++ docs/chapter13/graph3.json | 26 +++ docs/chapter13/graph3.svg | 128 ++++++++++++++ docs/chapter13/graph4.gv | 110 ++++++++++++ docs/chapter13/graph4.json | 24 +++ docs/chapter13/graph4.svg | 120 +++++++++++++ docs/chapter13/graph5.gv | 117 +++++++++++++ docs/chapter13/graph5.json | 24 +++ docs/chapter13/graph5.svg | 120 +++++++++++++ docs/chapter13/graph6.gv | 117 +++++++++++++ docs/chapter13/graph6.json | 25 +++ docs/chapter13/graph6.svg | 124 +++++++++++++ docs/chapter13/graph7.gv | 23 +++ docs/chapter13/graph7.json | 16 ++ docs/chapter13/graph7.svg | 78 +++++++++ docs/chapter13/graph8.gv | 45 +++++ docs/chapter13/graph8.json | 21 +++ docs/chapter13/graph8.svg | 98 +++++++++++ 30 files changed, 2502 insertions(+) create mode 100644 docs/chapter13/Makefile create mode 100644 docs/chapter13/README.ja.md create mode 100644 docs/chapter13/README.md create mode 100644 docs/chapter13/graph1.gv create mode 100644 docs/chapter13/graph1.json create mode 100644 docs/chapter13/graph1.svg create mode 100644 docs/chapter13/graph2.gv create mode 100644 docs/chapter13/graph2.json create mode 100644 docs/chapter13/graph2.svg create mode 100644 docs/chapter13/graph3-snip.jpg create mode 100644 docs/chapter13/graph3-snip.json create mode 100644 docs/chapter13/graph3-snip.svg create mode 100644 docs/chapter13/graph3.gv create mode 100644 docs/chapter13/graph3.json create mode 100644 docs/chapter13/graph3.svg create mode 100644 docs/chapter13/graph4.gv create mode 100644 docs/chapter13/graph4.json create mode 100644 docs/chapter13/graph4.svg create mode 100644 docs/chapter13/graph5.gv create mode 100644 docs/chapter13/graph5.json create mode 100644 docs/chapter13/graph5.svg create mode 100644 docs/chapter13/graph6.gv create mode 100644 docs/chapter13/graph6.json create mode 100644 docs/chapter13/graph6.svg create mode 100644 docs/chapter13/graph7.gv create mode 100644 docs/chapter13/graph7.json create mode 100644 docs/chapter13/graph7.svg create mode 100644 docs/chapter13/graph8.gv create mode 100644 docs/chapter13/graph8.json create mode 100644 docs/chapter13/graph8.svg (limited to 'docs') diff --git a/docs/chapter13/Makefile b/docs/chapter13/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter13/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter13/README.ja.md b/docs/chapter13/README.ja.md new file mode 100644 index 00000000..27f78e4b --- /dev/null +++ b/docs/chapter13/README.ja.md @@ -0,0 +1,258 @@ +# 第13章: 大域的コード移動 + +[English](README.md) | 日本語 + +[前: 第12章](../chapter12/README.ja.md) | +[次: 第14章](../chapter14/README.ja.md) + +この文書は [原文](README.md) の日本語訳です。 + +この章では、第10〜12章で構築した、参照フィールドと遅延的なメモリ分割を含むグラフをスケジュールします。移動可能な演算のスロット 0 の制御入力を選び、エイリアスする可能性がある Load と Store の順序を維持します。 + +また、この章ではかなり詳しいグラフアルゴリズムをいくつか紹介します。グラフ理論を復習しておくとよいでしょう。 + +文法は[第12章](../chapter12/12-grammar.ja.md)から変わりません。 + +# 目次 + +1. [概要](#概要) +2. [スケジューリングの例を追う](#スケジューリングの例を追う) +3. [ループのスケジューリング](#ループのスケジューリング) +4. [大域的コード移動アルゴリズムの構成要素](#大域的コード移動アルゴリズムの構成要素) +5. [SoN グラフ内の基本ブロックの識別](#son-グラフ内の基本ブロックの識別) +6. [無限ループの処理](#無限ループの処理) +7. [支配ノード](#支配ノード) +8. [ループ深度](#ループ深度) +9. [早期スケジュール](#早期スケジュール) +10. [遅延スケジュール](#遅延スケジュール) +11. [反依存の挿入](#反依存の挿入) +12. [動画での解説](#動画での解説) + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの線形な Git リビジョン履歴で[この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter13)を読み、前章との[差分](https://github.com/SeaOfNodes/Simple/compare/linear-chapter12...linear-chapter13)を見ることもできます。 + +元の入力ソースプログラムは、物事が起こる順序を定義します。プログラムを Sea of Nodes 表現にパースし、さまざまな最適化を行うと、その順序は完全には維持されません。最適化された Sea of Nodes グラフを動かすのは、元のソースプログラムの命令列ではなく、ノード間の依存関係です。 + +この章の目標は、最適化された Sea of Nodes グラフから、命令を実行するスケジュールをどう復元するかを見ることです。このスケジュールは、元のソースプログラムの意味論を保持する必要がありますが、それ以外は命令の実行を並べ替えてかまいません。 + +スケジューリングアルゴリズムは SoN グラフ内の暗黙の基本ブロックをまたいで働くため、大域的コード移動アルゴリズムと呼びます。スケジューラは基本ブロックの境界を越えて命令を移動できます。 + +このアルゴリズムの主な参考文献は GCM GVN 論文 [^1] です。ただし Simple の実装には、論文で説明された版と異なる点があります。 + +複雑な話題なので、まず概要を示してから詳しく見ていきます。 + +## 概要 + +Sea of Nodes グラフには、2つの仮想的なグラフが含まれています。 + +* Start、If、Region など、特定のノード型が表す制御フローグラフがあります。 +* 主として、値やメモリを生成・消費するノード間の定義と使用のエッジ（Def-Use）によって成り立つデータグラフがあります。 + +スケジューリングの観点では、制御フローグラフは固定され、動かせません。一方、データ値やメモリを消費・生成するノードには、実行する時点にある程度の自由があります。スケジューリングアルゴリズムの目標は、これらのノードについて、最適かつ正しい配置を見つけることです。 + +中心となるスケジューリングアルゴリズムは2段階で働きます。 + +* 早期スケジュール: この段階では末端（Stop）から始めて、各 Node の「入力」を上向きに DFS でたどります。各データノードを、その入力に支配される最初の制御ブロックに配置します。 +* 遅延スケジュール: この段階では Stop から逆向きに、定義より先に使用をスケジュールします。そしてデータノードを、上で計算した最初のブロックと、すべての使用を支配する最後の制御ブロックの間に移動します。配置は、可能な限り浅いループの入れ子に置き、かつできるだけ制御に依存させるという条件に従います。さらに Load 命令の配置では、同じメモリ位置に対する Load と Store の順序を正しくする必要があります。 + +## スケジューリングの例を追う + +各手順を詳しく説明する前に、例を追ってスケジューリング中に SoN グラフがどう変わるかを見ると理解の助けになります。 + +説明のために、次のプログラムを使います。 + +```java +struct S { int f; } +S v=new S; +v.f = 2; +int i=new S.f; +i=v.f; +if (arg) v.f=1; +return i; +``` + +まずスケジューリング前のグラフを見ましょう。 + +この説明用の図は、精密な `S.f` の鎖と、Return が消費する最後の MemMerge を示します。変更されないデフォルトのメモリは Start から来ており、冗長なひとまとめの Phi は畳み込まれて消えています。第10章・第11章と同じく、Region とその Phi 束縛を含む制御フローの文脈は省略しています。Load や Store を制御する箇所には、小さく切り離された True/False 射影が残っています。第10章の模式的なソース上の制御とは異なり、これらの図は各段階の実際のスケジューリング入力を示します。入口ブロックと Loop の束縛は省略しています。 + +![グラフ1](./graph1.svg) + +次の点に注目してください。 + +* 制御ノードは動かせません。ここでは大部分を省略しています。 +* New ノードにはすでに制御入力があり、Phi は Region に束縛されています。これらの束縛は図示していなくても固定のままです。 +* ロード `.f` とストア `.f=` のノードはまだ「浮いて」います。この段階では制御入力がないため、スケジューリングでそのブロックを選ぶ必要があります。 + +次に、早期スケジュール実行後のグラフを見ましょう。 + +![グラフ2](./graph2.svg) + +早期スケジュールは、入力がそこで利用できるため、ロード `.f` とストア `.f=` を最初の基本ブロックに置きます。この入口ブロックへの制御束縛は省略しているので、メモリの図は変わっていないように見えます。 + +以下のグラフは、遅延スケジューリング後のメモリとデータの依存関係に注目しています。Region を含む制御フローの骨組みは省略しています。Store #22 の制御入力は、独立した True 射影 #8 への赤いエッジとして見えます。Store から Load への反依存とメモリ Phi は残しています。 + +![グラフ3](./graph3.svg) + +以下の抜粋は、グラフの主な変更を示します。 + +![先行するロードの後に順序付けられたストア](./graph3-snip.svg) + +* ストア `.f=` は、ロード `.f` に対する反依存を持つようになりました。これにより、プログラムの意味論が要求する通り、ストアがロードより後にスケジュールされます。反依存は後で詳しく扱います。 +* ストア `.f=` が If ノードの True 分岐に束縛されたことにも注目してください。 + +## ループのスケジューリング + +今度はループを含む別の例を示します。 + +```java +struct S { int f; } +S v = new S; +int i = arg; +while (arg > 0) { + int j = i/3; + if (arg == 5) + v.f = j; + arg = arg - 1; +} +return v; +``` + +スケジューリング前の SoN グラフは次のようになります。 + +![グラフ4](./graph4.svg) + +早期スケジュールを生成すると、次を得ます。 + +![グラフ5](./graph5.svg) + +早期スケジュールは Store #31 をループ先頭に配置します（制御束縛は省略）。遅延スケジューリングは、それを `if (arg == 5)` の True 分岐 #15 に移します。赤い制御エッジがそれを示します。 + +![グラフ6](./graph6.svg) + +最終的な実行スケジュールでは、式 `i/3` はループの外で実行できます。`arg` の元の値だけに依存するため、ループ不変だからです。 + +## 大域的コード移動アルゴリズムの構成要素 + +上では GCM アルゴリズムの構成要素のいくつかに触れました。ここで、まだ触れていないものも含めて列挙します。 + +* SoN グラフの制御フローノードには、暗黙の基本ブロックがあります。GCM アルゴリズムでは、これらのノードをもっと明示的に認識する必要があります。 +* プログラムに無限ループがあると、Stop ノードから到達できないノードが生じ、アルゴリズムに問題をもたらします。対処するため、無限ループを発見し、ループから Stop ノードへのダミーエッジを作る必要があります。 +* Simple の SoN グラフではループをすでに識別しているため、ループ発見の手順は不要です。ただし、各 CFG ノードに関連するループ深度を計算する必要があります。 +* [第6章](../chapter06/README.ja.md)で支配ノードの概念を説明しました。支配ノードは GCM アルゴリズムの要なので、段階的な支配ノード発見アルゴリズムを、その要件を満たすように拡張します。 +* アルゴリズムの2段階、早期スケジューリングと遅延スケジューリングはすでに述べました。 +* さらに、特定の場面では、正しい実行順序を強制するため Load と Store の間に反依存エッジを追加する必要があります。 +* GCM アルゴリズムの実装を容易にするため、Node 階層にいくつか変更を加えます。これらは、前の章から引き継いだ Node 階層を概念的に変えるものではありません。 + +## SoN グラフ内の基本ブロックの識別 + +Sea of Nodes グラフは、プログラムの制御フローグラフをすでに捉えています。この情報は、制御ノードと、制御ノードからほかの型のノードへのエッジに暗黙に含まれます。 + +復習すると、制御は Start ノードで、`$ctrl` という名前に束縛された射影を介して始まります。プログラム中を制御が流れるにつれて、この名前の束縛は更新され、制御が受け渡され、最終的に Stop ノードに到達します。 + +ある制御ノードは基本ブロックを開始し、別のものは基本ブロック（BB）を終了すると認識すれば、CFG の基本ブロック構造を簡単に構築できます。 + +すべての制御ノードを列挙します。 + +| ノード | BB を開始する | BB を終了する | +|---|---|---| +| Start | はい。ただし `$ctrl` 射影を介してのみ | いいえ | +| CProj | 入力制御が If ノードなら、はい | いいえ | +| Region | はい | いいえ | +| If | いいえ | はい | +| Return | いいえ | はい | +| Stop | はい | はい | + +この章における Node 階層の変更は次の通りです。 + +* 上のすべての制御ノードは、基底クラス CFG Node を継承するようになります。これによって、制御フローノードの共通機能を基底クラスに置けます。 +* CProj ノードは通常の Proj ノードを継承し、次の場合に使います。 + * Start からの `$ctrl` 射影 + * If からの True と False の射影 +* Never ノードは If の特別なサブクラスで、後述するように無限ループの処理に使います。 +* XCtrl ノードは死んだ制御を表します。 + +## 無限ループの処理 + +無限ループを含むコードの例です。 + +```java +while (1) {} +return 0; +``` + +まず、その結果のグラフを見ましょう。 + +![グラフ7](./graph7.svg) + +次に、無限ループから Stop ノードへのエッジを挿入した後の、変更されたグラフを見てください。 + +![グラフ8](./graph8.svg) + +実装は [`LoopNode.forceExit()`](../../src/main/java/com/seaofnodes/simple/node/LoopNode.java#L57) にあります。後退エッジの支配ノードの鎖をたどり、出口を探します。出口がなければ Never ノードと、決して通らない return 経路を挿入し、スケジューラの逆向きの探索でループに到達できるようにします。 + +## 支配ノード + +Simple では支配ノードを段階的に計算します。ピープホール最適化でグラフの一部を削除することはあっても、新しい制御構造を導入することはないという性質を利用します。これにより、以下の単純な方法を使えます。 + +CFG ノードはすべての制御ノードの基底クラスです。`_idepth` を通して、支配深度の保守的な近似を保持します。このフィールドは直近の支配ノードの深度を表すキャッシュ値です。初期値 `0` は未計算を意味し、要求時に深度を計算します。 + +デフォルトの計算とキャッシュは [`CFGNode.idepth()`](../../src/main/java/com/seaofnodes/simple/node/CFGNode.java#L51) を参照してください。[`RegionNode`](../../src/main/java/com/seaofnodes/simple/node/RegionNode.java#L94)、[`LoopNode`](../../src/main/java/com/seaofnodes/simple/node/LoopNode.java#L31)、[`StartNode`](../../src/main/java/com/seaofnodes/simple/node/StartNode.java#L36)、[`StopNode`](../../src/main/java/com/seaofnodes/simple/node/StopNode.java#L58) のオーバーライドは、合流、ループ入口、グラフの端点を扱います。 + +制御フローグラフの一部を削除すると、`_idepth` に飛びが生じますが、支配木を下るにつれて `_idepth` の値が増えるという不変条件は依然として正しく反映されます。 + +最初の計算時にキャッシュする支配深度とともに、直近の支配ノードを得るメソッドを提供します。この値は、ある時点でのみ有効であり、グラフが変わると無効になるためキャッシュしません。 + +[`CFGNode.idom()` と `domLCA()`](../../src/main/java/com/seaofnodes/simple/node/CFGNode.java#L60) は、デフォルトの直近の支配ノードと、2つの支配ノードの最小共通祖先を見つける探索を提供します。[`RegionNode.idom()`](../../src/main/java/com/seaofnodes/simple/node/RegionNode.java#L103) は流入する経路を組み合わせ、[`LoopNode.idom()`](../../src/main/java/com/seaofnodes/simple/node/LoopNode.java#L33) はループ入口を使います。Start と Stop に直近の支配ノードはありません。 + +## ループ深度 + +Simple の Sea of Nodes グラフは、Loop ノードによってループを明示的に識別します。言語が提供するループの作り方は `while` 文だけなので、汎用的なループ発見処理を実装する必要はありません。 + +ただし、ループ深度を計算する必要はあります。支配深度の計算と似た方法で行います。 + +[`CFGNode.loopDepth()`](../../src/main/java/com/seaofnodes/simple/node/CFGNode.java#L78) は制御入力の深度を継承し、[`RegionNode.loopDepth()`](../../src/main/java/com/seaofnodes/simple/node/RegionNode.java#L116) は流入する経路を使います。[`LoopNode.loopDepth()`](../../src/main/java/com/seaofnodes/simple/node/LoopNode.java#L35) は入れ子を1段増やし、後退エッジの支配ノードの鎖をたどってループ出口に印を付けます。[`StartNode`](../../src/main/java/com/seaofnodes/simple/node/StartNode.java#L41) と [`StopNode`](../../src/main/java/com/seaofnodes/simple/node/StopNode.java#L68) は最も外側の深度を 1 にします。 + +## 早期スケジュール + +GCM アルゴリズム本体は、早期スケジュールの計算から始まります。末端（Stop）から各 Node の「入力」を上向きに DFS でたどり、各データノードを、その入力に支配される最初の制御ブロックに配置します。 + +前提として、前述した方法で無限ループを修正しておく必要があります。 + +実装は [`GlobalCodeMotion.schedEarly()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L62) から始まります。[`_rpo_cfg()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L85) は CFG の走査順序を構築し、[`_schedEarly()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L94) はデータ入力を再帰的にスケジュールします。制御をスケジュールする前にデータのサイクルへ入ることを避けるため、Phi 入力を通る再帰は飛ばします。 + +既存の制御および Phi/Proj の束縛は維持します。浮いているノードには、最も深い入力ブロックを最も早い配置として与えます。MemMerge も、疎なエイリアステーブル内の存在しないエントリを無視して、同じ規則に従います。 + +## 遅延スケジュール + +遅延スケジューリングは Stop から始め、ワークリストを使って定義より先に使用を配置します。CFG ノード、Phi、射影、割り当ては固定の配置を与えます。ほかのノードは、自分の使用がスケジュールされるまで待ちます。Load は、自分のエイリアスを上書きしたり合流したりできるメモリユーザーも待ちます。選ぶブロックは、早期配置とすべての使用の共通支配ノードとの間にあり、浅いループを優先し、その次に深い制御フローを優先します。 + +実装は次の手順に分かれます。 + +* [`schedLate()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L114) は配置テーブルを管理し、最終的な制御入力を設定します。[`breadth()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L129) はワークリストを駆動し、使用が完了すると定義と待機中のロードを起こします。 +* [`_doSchedLate()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L175) は使用の共通支配ノードを見つけ、ロードの反依存を考慮して、早期配置に向かってたどります。[`better()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L215) を呼び出し、候補ブロックを比較します。 +* [`use_block()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L202) は Phi の使用を、合流そのものではなく、対応する流入制御経路で扱います。 + +## 反依存の挿入 + +同じメモリ位置への Load と Store を正しく順序付けるため、以下のように Store から Load へのエッジを挿入します。Store は、先行する Load を待たなければなりません。これらのエッジは、通常 SoN で捉える Def-Use の依存関係を表さず、純粋にスケジューリングの制約として存在するため、反依存と呼びます。 + +反依存は、遅延スケジュールの実行**中**に計算します。早期スケジュールと、Load をスケジュールする前に得られる Load の使用の遅延スケジュールに依存するためです。 + +Load から後ろを見て、そのメモリ入力を Start のメモリ射影、メモリ Phi、または Store までたどります。最適化によって、MemMerge を通る Load の精密なスライスはすでに選択されています。そのメモリ定義のユーザーを調べ、Load のエイリアスを覆う Store とメモリ Phi だけを残します。Start の1つのメモリ射影は多数のエイリアスを供給する可能性があるので、メモリ入力を共有するだけで反依存があるとは限りません。 + +MemMerge はスライスを包むだけで、どれも上書きしません。これを書き込みとして扱うと、Load 自身の結果に依存する集約を Load が待つことになり得ます。Load をスケジュールする準備ができたかどうかの判断と、反依存の計算には、同じエイリアスのフィルタを使います。完了したメモリユーザーは、共有するメモリ定義がすでにスケジュールされていても、待機中のロードを起こします。 + +`schedLate` の途中なので、Load のすべてのユーザーの遅延スケジュールはすでに計算済みで、Load の使用の*最小共通祖先*、すなわち LCA または遅い位置を持っています。Load に影響し得るメモリ定義の集合を調べ、Store から Load への反依存を追加するか、Load の実効的な LCA を上げます。Phi のメモリ定義では Phi の入力を調べ、そのブロックに実効的な使用を置きます。これを Load の LCA を上げるために使います。ストアでも同じことを行いますが、Load の LCA と**同じ**ブロックのストアが見つかったら、同一ブロック内の順序を強制する反依存エッジを追加します。 + +エイリアスのフィルタは [`antiUse()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L224)、Load の候補ブロックへの印付けと競合するメモリユーザーの調査は [`find_anti_dep()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L233) を参照してください。[`anti_dep()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L260) は、競合する演算の支配区間をたどり、Load の LCA を上げ、必要なら Store から Load へのエッジを追加します。評価器のスケジューラは GCM と独立してその Store を配置する可能性があるため、Store の区間全体をチェックします。 + +## 動画での解説 + +実装を詳しくたどるには、以下の動画をご覧ください。 + +* [Coffee Compiler Club - 2024年6月21日](https://youtu.be/5Po0gxfE7LA?feature=shared) +* [Coffee Compiler Club - 2024年6月26日](https://www.youtube.com/watch?v=HnN2YzmFb-8&t=0s) + +[^1]: Cliff Click. (1995). + Global Code Motion Global Value Numbering. + +次の[第14章](../chapter14/README.ja.md)では、このスケジュール済みコンパイラに浮動小数点演算と狭い数値型を追加します。 diff --git a/docs/chapter13/README.md b/docs/chapter13/README.md new file mode 100644 index 00000000..9e3a1d69 --- /dev/null +++ b/docs/chapter13/README.md @@ -0,0 +1,375 @@ +# Chapter 13: Global Code Motion + +English | [日本語](README.ja.md) + +[Previous: Chapter 12](../chapter12/README.md) | +[Next: Chapter 14](../chapter14/README.md) + +This chapter schedules the graphs built in Chapters 10-12, including +reference fields and lazy memory partitions. It chooses a slot-0 control input +for movable operations and preserves the ordering of potentially aliasing +Loads and Stores. + +Also in this chapter, we'll be presenting several fairly detailed graph +algorithms. You might want to brush up on your graph theory! + +The grammar is unchanged from [Chapter 12](../chapter12/12-grammar.md). + +# Table of Contents + +1. [High Level Overview](#high-level-overview) +2. [Scheduling Walk Through](#scheduling-walk-through) +3. [Scheduling a Loop](#scheduling-a-loop) +4. [Components of the Global Code Motion Algorithm](#components-of-the-global-code-motion-algorithm) +5. [Identification of Basic Blocks in SoN graph](#identification-of-basic-blocks-in-son-graph) +6. [Handling Infinite Loops](#handling-infinite-loops) +7. [Dominators](#dominators) +8. [Loop depth](#loop-depth) +9. [Early Schedule](#early-schedule) +10. [Late Schedule](#late-schedule) +11. [Inserting Anti Dependencies](#inserting-anti-dependencies) +12. [Video Walk Through](#video-walk-through) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter13) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter12...linear-chapter13) it to the previous chapter. + + +The original input source program defines a sequence in which things happen. As +we parse the program into Sea of Nodes representation and perform various +optimizations, this sequence is not fully maintained. The optimized Sea of +Nodes graph is driven by the dependencies between nodes rather than the +sequence of instructions in the original source program. + +Our goal in this chapter is to look at how we can recover a schedule for executing instructions from an +optimized Sea of Nodes graph. This schedule needs to preserve the semantics of the original source program, +but is otherwise allowed to reorder the execution of instructions. + +Since the scheduling algorithm works across the implicit Basic Blocks in the SoN Graph, +we call this a Global Code Motion algorithm; the scheduler can move instructions across Basic Block boundaries. + +The primary reference for this algorithm is the GCM GVN paper [^1]. However, the implementation in Simple has some +differences compared to the version described in the paper. + +Since this is a complex topic, we will present a high level summary first and then delve into the details. + +## High Level Overview + +The Sea of Nodes graph has two virtual graphs within it. + +* There is a control flow graph, represented by certain node types, such as Start, If, Region, etc. +* There is a data graph, primarily driven by Def-Use edges between nodes that produce or consume values or memory. + +From a scheduling point of view, the control flow graph is fixed, and immovable. +However, the nodes that consume or produce data values/memory have some flexibility in terms of when they are executed. The goal of the +scheduling algorithm is to find the best placement of these nodes so that they are both optimum and correct. + +At its core, the scheduling algorithm works in two phases: + +* Schedule Early - in this phase, we do an upward DFS walk on the "inputs" of each Node, starting from the bottom (Stop). We schedule each data node to the + first control block where they are dominated by their inputs. +* Schedule Late - in this phase we work backwards from Stop, scheduling uses before definitions, and move data nodes to a block between the first block calculated above, + and the last control block where they dominate all their uses. The placement is subject to the condition that it is in the shallowest loop nest possible, and is as control dependent as possible. + Additionally, the placement of Load instructions must ensure correct ordering between Loads and Stores of the same memory location. + +## Scheduling Walk Through + +Before we describe the steps in detail, it is instructive to walk through an example and see the changes that occur to the SoN graph during scheduling. + +To motivate the discussion, we will use this example program. + +```java +struct S { int f; } +S v=new S; +v.f = 2; +int i=new S.f; +i=v.f; +if (arg) v.f=1; +return i; +``` + +First let's look at the graph before scheduling. + +These walkthrough diagrams show the precise `S.f` chain and the final +MemMerge consumed by Return. The unchanged default memory comes from Start; +any redundant bulk Phis have folded away. As in Chapters 10 and 11, the diagrams omit +control-flow context, including Regions and their Phi bindings. Small, +detached True/False projections remain where they gate a Load or Store. +Unlike Chapter 10's schematic source gates, these figures show the actual +scheduling inputs at each stage. Entry-block and Loop bindings are omitted. + +![Graph1](./graph1.svg) + +Observe that + +* Control nodes are immovable. Most are omitted here. +* New nodes already have control inputs, and Phis are bound to Regions; + these bindings remain fixed even though they are not drawn. +* The load `.f` and store `.f=` nodes are still "floating": they have no + control input at this stage, so scheduling must choose their blocks. + +Now, let's look at the graph after we run the early schedule. + +![Graph2](./graph2.svg) + + +The early schedule puts the load `.f` and stores `.f=` in the first basic +block, since their inputs are available there. These entry-block control +bindings are omitted, so the memory view looks unchanged. + +The graph below focuses on memory and data dependencies after late scheduling. +The control-flow scaffold, including the Region, is omitted. Store #22's +control input remains visible as the red edge to the standalone True +projection #8; the Store-to-Load anti-dependency and memory Phis are retained. + +![Graph3](./graph3.svg) + +The snip below shows the main changes in the graph: + +![Store ordered after the earlier load](./graph3-snip.svg) + +* The store `.f=` now has an anti-dependency on the load `.f`; this ensures that the store is scheduled after the load, as required by program semantics. We discuss anti-dependencies in detail later. +* Observe also that the store `.f=` is now bound to the True branch of the If node. + +## Scheduling a Loop + +We show another example, this time involving a loop. + +```java +struct S { int f; } +S v = new S; +int i = arg; +while (arg > 0) { + int j = i/3; + if (arg == 5) + v.f = j; + arg = arg - 1; +} +return v; +``` + +The SoN graph prior to scheduling looks like this: + +![Graph4](./graph4.svg) + +Following early schedule generation, we get: + +![Graph5](./graph5.svg) + +The early schedule places Store #31 at the loop header (its control binding +is omitted). Late scheduling moves it to the True branch #15 of +`if (arg == 5)`, shown by the red control edge: + +![Graph6](./graph6.svg) + +The final execution schedule shows that the expression `i/3` can be performed outside the loop because it only depends on the +original value of `arg`, and hence is loop invariant. + +## Components of the Global Code Motion Algorithm + +We have already alluded to several components of the GCM algorithm in passing above. Here we list them out as well as others we did not mention: + +* The SoN graph has implicit basic blocks in the control flow nodes. For the GCM algo, we need to recognize these nodes more explicitly. +* When a program has an infinite loop, it poses a problem for the algo, as nodes can be unreachable from the Stop node. To work around this issue, we need to discover + infinite loops and create a dummy edge connecting the loop to the Stop node. +* Loops are already identified in the Simple SoN graph, so we do not need a loop discovery step. However, we need to compute the loop depth associated with each CFG node. +* In [Chapter 6](../chapter06/README.md) we explained the concept of Dominators. Dominators are key to the GCM algo, and we extend our incremental dominator discovery algo to + ensure that it meets the requirements of the algo. +* We already mentioned the two phases of the algo - the Early Scheduling and the Late Scheduling. +* In addition, we need to add anti-dependency edges between Loads and Stores in certain scenarios to enforce correct execution order. +* There are a few changes to our Node hierarchy to help us implement the GCM algo more conveniently. These changes do not conceptually alter the Node hierarchy we inherited from the previous chapters. + +## Identification of Basic Blocks in SoN graph + +The Sea of Nodes graph already captures the program's control flow graph. This information is implicit in the control nodes and edges from control nodes to other types of nodes. + +To recap, Control starts at the Start node, via a projection that is bound to the name `$ctrl`. As the control flows in the program, this name binding gets updated, and control is +passed around, until it reaches the Stop node. + +The Basic Block structure of the CFG can be easily constructed by recognizing that certain control nodes start a Basic Block, whereas certain others end a BB. + +Here is the list of all control nodes: + +| Node | Starts a BB | Ends a BB | +|--------|-----------------------------------------|-----------| +| Start | Yes but only via the `$ctrl` projection | No | +| CProj | Yes if input control is an If node | No | +| Region | Yes | No | +| If | No | Yes | +| Return | No | Yes | +| Stop | Yes | Yes | + +Changes to Node hierarchy in this chapter: + +* All control nodes above now extend a base class CFG Node. This allows us to place common functionality of control flow nodes in the base class. +* The CProj node extends the regular Proj node and is used in following cases: + * The `$ctrl` projection off Start + * The True and False projections off If. +* The Never node is a special sub class of If that is used to handle infinite loops as explained later. +* The XCtrl node represents a dead control. + +## Handling Infinite Loops + +Here is an example of code that contains an infinite loop: + +```java +while (1) {} +return 0; +``` + +First let's look at the graph resulting from this: + +![Graph7](./graph7.svg) + +Now, look at the modified graph after we insert an edge from the infinite loop to Stop node. + +![Graph8](./graph8.svg) + +The implementation is in +[`LoopNode.forceExit()`](../../src/main/java/com/seaofnodes/simple/node/LoopNode.java#L57). +It walks the backedge's dominator chain to look for an exit. If none exists, +it inserts a Never node and a never-taken return path, making the loop +reachable to the scheduler's backward walk. + +## Dominators + +In Simple, we compute Dominators incrementally. Our approach relies on the fact that we may delete parts of the graph during peepholes, +but we never introduce new control structure via peepholes. This allows us to use a simple approach described below. + +The CFG node is the base class for all control nodes. It maintains a conservative approximation of dominator depth via `_idepth`. This field is a cached value representing +the immediate dominator depth. Its initial value is `0`, which signifies that it has not yet been computed. The depth is computed on request. + +See [`CFGNode.idepth()`](../../src/main/java/com/seaofnodes/simple/node/CFGNode.java#L51) +for the default computation and cache. The overrides in +[`RegionNode`](../../src/main/java/com/seaofnodes/simple/node/RegionNode.java#L94), +[`LoopNode`](../../src/main/java/com/seaofnodes/simple/node/LoopNode.java#L31), +[`StartNode`](../../src/main/java/com/seaofnodes/simple/node/StartNode.java#L36), and +[`StopNode`](../../src/main/java/com/seaofnodes/simple/node/StopNode.java#L58) +handle merges, loop entries, and the graph's endpoints. + +If portions of the control flow graph are deleted, then there will be gaps in the `_idepth`, but it still correctly reflects the +invariant that the value of `_idepth` increases as we go down the dominator tree. + +Alongside the dominator depth, which is cached on first compute, a method is provided to get the immediate Dominator node. This +value is not cached as it is only valid at a point in time, and is invalidated as the graph changes. + +[`CFGNode.idom()` and `domLCA()`](../../src/main/java/com/seaofnodes/simple/node/CFGNode.java#L60) +provide the default immediate dominator and the walk that finds the least +common ancestor of two dominators. +[`RegionNode.idom()`](../../src/main/java/com/seaofnodes/simple/node/RegionNode.java#L103) +combines the incoming paths; [`LoopNode.idom()`](../../src/main/java/com/seaofnodes/simple/node/LoopNode.java#L33) +uses the loop entry. Start and Stop have no immediate dominator. + +## Loop Depth + +Simple's Sea of Nodes graph identifies loops explicitly via Loop nodes. Since the language provides a single way to create a loop, using the `while` statement, +it is not necessary to implement a generic loop discovery process. + +We do however need to compute a loop depth. This is done similarly to how we compute the dominator depth. + +[`CFGNode.loopDepth()`](../../src/main/java/com/seaofnodes/simple/node/CFGNode.java#L78) +inherits depth from its control input, while +[`RegionNode.loopDepth()`](../../src/main/java/com/seaofnodes/simple/node/RegionNode.java#L116) +uses an incoming path. +[`LoopNode.loopDepth()`](../../src/main/java/com/seaofnodes/simple/node/LoopNode.java#L35) +adds a nesting level and walks the backedge's dominator chain to mark loop exits. +[`StartNode`](../../src/main/java/com/seaofnodes/simple/node/StartNode.java#L41) and +[`StopNode`](../../src/main/java/com/seaofnodes/simple/node/StopNode.java#L68) +establish the outermost depth of 1. + +## Early Schedule + +The GCM algorithm proper starts with the computation of the early schedule, during which we do an upward DFS walk on the "inputs" of each Node, starting from the bottom (Stop). We schedule each data node to the +first control block where they are dominated by their inputs. + +A pre-condition of this is to ensure that infinite loops have been fixed as described earlier. + +The implementation starts in +[`GlobalCodeMotion.schedEarly()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L62). +[`_rpo_cfg()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L85) +builds the CFG traversal order, and +[`_schedEarly()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L94) +recursively schedules data inputs. It skips recursion through Phi inputs to +avoid entering a data cycle before its control has been scheduled. + +Existing control and Phi/Proj bindings are preserved. Floating nodes receive +the deepest input block as their earliest placement. MemMerge follows this +same rule, ignoring absent entries in its sparse alias table. + +## Late Schedule + +Late scheduling starts at Stop and uses a worklist to place uses before their +definitions. CFG nodes, Phis, projections, and allocations provide fixed +placements. Other nodes wait until their uses have been scheduled; a Load also +waits for memory users that can overwrite or merge its alias. The chosen block +lies between the early placement and the common dominator of all uses, favoring +shallower loops and then deeper control flow. + +The implementation is divided into these steps: + +* [`schedLate()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L114) + manages the placement tables and installs the final control inputs; + [`breadth()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L129) + drives the worklist and wakes definitions and waiting loads as uses finish. +* [`_doSchedLate()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L175) + finds the common dominator of uses, accounts for load anti-dependencies, and + walks toward the early placement. It calls + [`better()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L215) + to compare candidate blocks. +* [`use_block()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L202) + handles Phi uses at their matching incoming control paths, rather than at + the merge itself. + +## Inserting Anti Dependencies + +To ensure that Loads and Stores to the same memory location are correctly +ordered, we insert an edge from the Store to the Load as described below: the +Store must wait for the earlier Load. We call these edges anti-dependencies +because they do not represent the Def-Use dependency that we normally capture +in SoN, and are purely present as scheduling constraints. + +We compute anti-dependencies DURING running schedule late. This is because we rely on the early-schedule, and the late-schedule of the Load's uses (before scheduling the Load). + +Looking backwards from the Load, we follow its memory input to Start's memory +projection, a memory Phi, or a Store. Optimization has already selected the +Load's precise slice through any MemMerge. We inspect users of that memory +definition, keeping only Stores and memory Phis that cover the Load's alias. +Start's single memory projection may supply many aliases, so sharing a memory +input alone does not imply an anti-dependency. + +MemMerge only packages slices; it does not overwrite any of them. Treating it +as a write could make a Load wait for an aggregate which itself depends on the +Load's result. The same alias filter is used both when deciding whether a Load +is ready to schedule and when computing its anti-dependencies. A completed +memory user wakes waiting loads even if their shared memory definition has +already been scheduled. + +Since we're in the middle of `schedLate`, we have already computed all the late +schedules of a Load's users, and we have the Loads *Least Common Ancestor* of +uses, the LCA or late position. We inspect the set of mem-defs that might +impact the Load, and either add an anti-dependency from Store to Load, or raise +the Loads effective LCA. For Phi mem-defs, we look at the Phi inputs and place +an effective use on that block; this will be used to raise the Load's LCA. For +stores, we do the same - until/unless we find stores with the SAME block as the +Load's LCA. Then we add the anti-dependency edge to force ordering within the +same block. + +See [`antiUse()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L224) +for the alias filter, and +[`find_anti_dep()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L233) +for marking the Load's candidate blocks and inspecting competing memory users. +[`anti_dep()`](../../src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java#L260) +walks the competing operation's dominator interval, raises the Load's LCA, +and adds a Store-to-Load edge when required. It checks the Store's full interval +because the evaluator's scheduler may place that Store independently of GCM. + +## Video Walk Through + +Please watch the following video for a detailed walk through of the implementation. + +* [Coffee Compiler Club - 21 June 2024](https://youtu.be/5Po0gxfE7LA?feature=shared). +* [Coffee Compiler Club - 26 June 2024](https://www.youtube.com/watch?v=HnN2YzmFb-8&t=0s) + +[^1]: Cliff Click. (1995). + Global Code Motion Global Value Numbering. + +Next, [Chapter 14](../chapter14/README.md) adds floating-point arithmetic and +narrow numeric types to this scheduled compiler. diff --git a/docs/chapter13/graph1.gv b/docs/chapter13/graph1.gv new file mode 100644 index 00000000..4d6ee1fe --- /dev/null +++ b/docs/chapter13/graph1.gv @@ -0,0 +1,79 @@ +digraph chapter13 { +/* +struct S { int f; } +S v=new S; +v.f = 2; +int i=new S.f; +i=v.f; +if (arg) v.f=1; +return i; + +*/ + rankdir=BT; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl$memarg
+
> + ]; + MemMerge [ shape=box label="MemMerge" ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_4 [ label="#0" ]; + new9 [ label="new S" ]; + Con_11 [ label="#2" ]; + Store12 [ label=".f =" ]; + new13 [ label="new S" ]; + Store14 [ label=".f =" ]; + Load16 [ label=".f" ]; + If17 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_21 [ label="#1" ]; + Store22 [ label=".f =" ]; + Region23 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_224 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; + Return25 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region23;Phi_224;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return25[taillabel=0 color=red]; + new9 -> Start2:p0[taillabel=0 color=green]; + Store12 -> Start2:p1[taillabel=1 color=blue]; + Store12 -> new9[taillabel=2]; + Store12 -> Con_11[taillabel=3]; + new13 -> Start2:p0[taillabel=0 color=green]; + Store14 -> Store12[taillabel=1 color=blue]; + Store14 -> new13[taillabel=2]; + Store14 -> Con_4[taillabel=3]; + Load16 -> Store14[taillabel=1 color=blue]; + Load16 -> new9[taillabel=2]; + If17 -> Start2:p0[taillabel=0 color=red]; + If17 -> Start2:p2[taillabel=1]; + Store22 -> Store14[taillabel=1 color=blue]; + Store22 -> new9[taillabel=2]; + Store22 -> Con_21[taillabel=3]; + Region23 -> If17:p0[taillabel=1 color=red]; + Region23 -> If17:p1[taillabel=2 color=red]; + Phi_224 -> Region23 [style=dotted taillabel=0]; + Phi_224 -> Store22[taillabel=1 color=blue]; + Phi_224 -> Store14[taillabel=2 color=blue constraint=false]; + Return25 -> Region23[taillabel=0 color=red]; + Return25 -> Load16[taillabel=2]; + Return25 -> MemMerge[taillabel=1 color=blue]; + MemMerge -> Start2:p1[taillabel=1 color=blue]; + MemMerge -> Phi_224[taillabel=2 color=blue]; +} diff --git a/docs/chapter13/graph1.json b/docs/chapter13/graph1.json new file mode 100644 index 00000000..aac69ce2 --- /dev/null +++ b/docs/chapter13/graph1.json @@ -0,0 +1,25 @@ +{ + "ver": 1, + "comp": "chapter13/docs/graph1.svg", + "step": 1, + "roots": [25], + "scope": 0, + "nodes": [ + {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 224, "role": "MEM", "label": null}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 11, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 12, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 14, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 12, "role": "MEM", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": ".f", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 22, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}], "proj": null}, + {"id": 25, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 224, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 22, "role": "MEM", "label": null}, {"idx": 2, "def": 14, "role": "MEM", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter13/graph1.svg b/docs/chapter13/graph1.svg new file mode 100644 index 00000000..93a2a03f --- /dev/null +++ b/docs/chapter13/graph1.svg @@ -0,0 +1,123 @@ +#1[1] → #6 · MEM#1[2] → #224 · MEM#12[1] → #6 · MEM#12[2] → #9 · DATA#12[3] → #11 · DATA#14[1] → #12 · MEM#14[2] → #13 · DATA#14[3] → #4 · DATA#16[1] → #14 · MEM#16[2] → #9 · DATA#22[1] → #14 · MEM#22[2] → #9 · DATA#22[3] → #21 · DATA#25[1] → #1 · MEM#25[2] → #16 · DATA#224[1] → #22 · MEM#224[2] → #14 · MEMMemMerge  #1#1 MemMerge +Type not computed + +[0] → — DATA +[1] → #6 MEM +[2] → #224 MEM012Start  #2#2 Start +Type not computed + +#0  #4#4 #0 +Type not computed + +$mem  #6/1#6 $mem +Projection 1 of #2 +Type not computed + +[0] → #2 MEMnew S  #9#9 new S +Type not computed + +[0] → — CTRL0#2  #11#11 #2 +Type not computed + +.f =  #12#12 .f = +Type not computed + +[0] → — DATA +[1] → #6 MEM +[2] → #9 DATA +[3] → #11 DATA0123new S  #13#13 new S +Type not computed + +[0] → — CTRL0.f =  #14#14 .f = +Type not computed + +[0] → — DATA +[1] → #12 MEM +[2] → #13 DATA +[3] → #4 DATA0123.f  #16#16 .f +Type not computed + +[0] → — DATA +[1] → #14 MEM +[2] → #9 DATA012#1  #21#21 #1 +Type not computed + +.f =  #22#22 .f = +Type not computed + +[0] → — DATA +[1] → #14 MEM +[2] → #9 DATA +[3] → #21 DATA0123Return  #25#25 Return +Type not computed + +[0] → — CTRL +[1] → #1 MEM +[2] → #16 DATA012MemPhi_2  #224#224 MemPhi_2 +Type not computed + +[0] → — ASSOC +[1] → #22 MEM +[2] → #14 MEM012 diff --git a/docs/chapter13/graph2.gv b/docs/chapter13/graph2.gv new file mode 100644 index 00000000..94d94dae --- /dev/null +++ b/docs/chapter13/graph2.gv @@ -0,0 +1,84 @@ +digraph chapter13 { +/* +struct S { int f; } +S v=new S; +v.f = 2; +int i=new S.f; +i=v.f; +if (arg) v.f=1; +return i; + +*/ + rankdir=BT; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl$memarg
+
> + ]; + MemMerge [ shape=box label="MemMerge" ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_4 [ label="#0" ]; + new9 [ label="new S" ]; + Con_11 [ label="#2" ]; + Store12 [ label=".f =" ]; + new13 [ label="new S" ]; + Store14 [ label=".f =" ]; + Load16 [ label=".f" ]; + If17 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_21 [ label="#1" ]; + Store22 [ label=".f =" ]; + Region23 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_224 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; + Return25 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region23;Phi_224;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return25[taillabel=0 color=red]; + new9 -> Start2:p0[taillabel=0 color=green]; + Store12 -> Start2:p0[taillabel=0 color=red]; + Store12 -> Start2:p1[taillabel=1 color=blue]; + Store12 -> new9[taillabel=2]; + Store12 -> Con_11[taillabel=3]; + new13 -> Start2:p0[taillabel=0 color=green]; + Store14 -> Start2:p0[taillabel=0 color=red]; + Store14 -> Store12[taillabel=1 color=blue]; + Store14 -> new13[taillabel=2]; + Store14 -> Con_4[taillabel=3]; + Load16 -> Start2:p0[taillabel=0 color=red]; + Load16 -> Store14[taillabel=1 color=blue]; + Load16 -> new9[taillabel=2]; + If17 -> Start2:p0[taillabel=0 color=red]; + If17 -> Start2:p2[taillabel=1]; + Store22 -> Start2:p0[taillabel=0 color=red]; + Store22 -> Store14[taillabel=1 color=blue]; + Store22 -> new9[taillabel=2]; + Store22 -> Con_21[taillabel=3]; + Region23 -> If17:p0[taillabel=1 color=red]; + Region23 -> If17:p1[taillabel=2 color=red]; + Phi_224 -> Region23 [style=dotted taillabel=0]; + Phi_224 -> Store22[taillabel=1 color=blue]; + Phi_224 -> Store14[taillabel=2 color=blue constraint=false]; + Return25 -> Region23[taillabel=0 color=red]; + Return25 -> Load16[taillabel=2]; + Return25 -> MemMerge[taillabel=1 color=blue]; + MemMerge -> Start2:p1[taillabel=1 color=blue]; + MemMerge -> Phi_224[taillabel=2 color=blue]; + MemMerge -> Region23[taillabel=0 color=green]; +} diff --git a/docs/chapter13/graph2.json b/docs/chapter13/graph2.json new file mode 100644 index 00000000..47689c72 --- /dev/null +++ b/docs/chapter13/graph2.json @@ -0,0 +1,25 @@ +{ + "ver": 1, + "comp": "chapter13/docs/graph2.svg", + "step": 1, + "roots": [25], + "scope": 0, + "nodes": [ + {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 224, "role": "MEM", "label": null}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 11, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 12, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 14, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 12, "role": "MEM", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": ".f", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 22, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}], "proj": null}, + {"id": 25, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 224, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 22, "role": "MEM", "label": null}, {"idx": 2, "def": 14, "role": "MEM", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter13/graph2.svg b/docs/chapter13/graph2.svg new file mode 100644 index 00000000..05210749 --- /dev/null +++ b/docs/chapter13/graph2.svg @@ -0,0 +1,123 @@ +#1[1] → #6 · MEM#1[2] → #224 · MEM#12[1] → #6 · MEM#12[2] → #9 · DATA#12[3] → #11 · DATA#14[1] → #12 · MEM#14[2] → #13 · DATA#14[3] → #4 · DATA#16[1] → #14 · MEM#16[2] → #9 · DATA#22[1] → #14 · MEM#22[2] → #9 · DATA#22[3] → #21 · DATA#25[1] → #1 · MEM#25[2] → #16 · DATA#224[1] → #22 · MEM#224[2] → #14 · MEMMemMerge  #1#1 MemMerge +Type not computed + +[0] → — CTRL +[1] → #6 MEM +[2] → #224 MEM012Start  #2#2 Start +Type not computed + +#0  #4#4 #0 +Type not computed + +$mem  #6/1#6 $mem +Projection 1 of #2 +Type not computed + +[0] → #2 MEMnew S  #9#9 new S +Type not computed + +[0] → — CTRL0#2  #11#11 #2 +Type not computed + +.f =  #12#12 .f = +Type not computed + +[0] → — CTRL +[1] → #6 MEM +[2] → #9 DATA +[3] → #11 DATA0123new S  #13#13 new S +Type not computed + +[0] → — CTRL0.f =  #14#14 .f = +Type not computed + +[0] → — CTRL +[1] → #12 MEM +[2] → #13 DATA +[3] → #4 DATA0123.f  #16#16 .f +Type not computed + +[0] → — CTRL +[1] → #14 MEM +[2] → #9 DATA012#1  #21#21 #1 +Type not computed + +.f =  #22#22 .f = +Type not computed + +[0] → — CTRL +[1] → #14 MEM +[2] → #9 DATA +[3] → #21 DATA0123Return  #25#25 Return +Type not computed + +[0] → — CTRL +[1] → #1 MEM +[2] → #16 DATA012MemPhi_2  #224#224 MemPhi_2 +Type not computed + +[0] → — ASSOC +[1] → #22 MEM +[2] → #14 MEM012 diff --git a/docs/chapter13/graph3-snip.jpg b/docs/chapter13/graph3-snip.jpg new file mode 100644 index 00000000..804a32c4 Binary files /dev/null and b/docs/chapter13/graph3-snip.jpg differ diff --git a/docs/chapter13/graph3-snip.json b/docs/chapter13/graph3-snip.json new file mode 100644 index 00000000..548dbdf3 --- /dev/null +++ b/docs/chapter13/graph3-snip.json @@ -0,0 +1,17 @@ +{ + "ver": 1, + "comp": "chapter13/docs/graph3-snip.svg", + "step": 1, + "roots": [22], + "scope": 0, + "nodes": [ + {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 0}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 14, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 0, "role": "MEM", "label": null}, {"idx": 2, "def": 0, "role": "DATA", "label": null}, {"idx": 3, "def": 0, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": ".f", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 22, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}, {"idx": 4, "def": 16, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter13/graph3-snip.svg b/docs/chapter13/graph3-snip.svg new file mode 100644 index 00000000..9f5218af --- /dev/null +++ b/docs/chapter13/graph3-snip.svg @@ -0,0 +1,91 @@ +#16[1] → #14 · MEM#16[2] → #9 · DATA#22[0] → #8 · CTRL#22[1] → #14 · MEM#22[2] → #9 · DATA#22[3] → #21 · DATA#22[4] → #16 · DATATrue  #8/0#8 True +Projection 0 of #0 +Type not computed + +new S  #9#9 new S +Type not computed + +[0] → — CTRL0.f =  #14#14 .f = +Type not computed + +[0] → — CTRL +[1] → — MEM +[2] → — DATA +[3] → — DATA0123.f  #16#16 .f +Type not computed + +[0] → — CTRL +[1] → #14 MEM +[2] → #9 DATA012#1  #21#21 #1 +Type not computed + +.f =  #22#22 .f = +Type not computed + +[0] → #8 CTRL +[1] → #14 MEM +[2] → #9 DATA +[3] → #21 DATA +[4] → #16 DATA01234 diff --git a/docs/chapter13/graph3.gv b/docs/chapter13/graph3.gv new file mode 100644 index 00000000..53c9aafe --- /dev/null +++ b/docs/chapter13/graph3.gv @@ -0,0 +1,85 @@ +digraph chapter13 { +/* +struct S { int f; } +S v=new S; +v.f = 2; +int i=new S.f; +i=v.f; +if (arg) v.f=1; +return i; + +*/ + rankdir=BT; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl$memarg
+
> + ]; + MemMerge [ shape=box label="MemMerge" ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_4 [ label="#0" ]; + new9 [ label="new S" ]; + Con_11 [ label="#2" ]; + Store12 [ label=".f =" ]; + new13 [ label="new S" ]; + Store14 [ label=".f =" ]; + Load16 [ label=".f" ]; + If17 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_21 [ label="#1" ]; + Store22 [ label=".f =" ]; + Region23 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_224 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; + Return25 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region23;Phi_224;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return25[taillabel=0 color=red]; + new9 -> Start2:p0[taillabel=0 color=green]; + Store12 -> Start2:p0[taillabel=0 color=red]; + Store12 -> Start2:p1[taillabel=1 color=blue]; + Store12 -> new9[taillabel=2]; + Store12 -> Con_11[taillabel=3]; + new13 -> Start2:p0[taillabel=0 color=green]; + Store14 -> Start2:p0[taillabel=0 color=red]; + Store14 -> Store12[taillabel=1 color=blue]; + Store14 -> new13[taillabel=2]; + Store14 -> Con_4[taillabel=3]; + Load16 -> Start2:p0[taillabel=0 color=red]; + Load16 -> Store14[taillabel=1 color=blue]; + Load16 -> new9[taillabel=2]; + If17 -> Start2:p0[taillabel=0 color=red]; + If17 -> Start2:p2[taillabel=1]; + Store22 -> If17:p0[taillabel=0 color=red]; + Store22 -> Store14[taillabel=1 color=blue]; + Store22 -> new9[taillabel=2]; + Store22 -> Con_21[taillabel=3]; + Store22 -> Load16[taillabel=4]; + Region23 -> If17:p0[taillabel=1 color=red]; + Region23 -> If17:p1[taillabel=2 color=red]; + Phi_224 -> Region23 [style=dotted taillabel=0]; + Phi_224 -> Store22[taillabel=1 color=blue]; + Phi_224 -> Store14[taillabel=2 color=blue constraint=false]; + Return25 -> Region23[taillabel=0 color=red]; + Return25 -> Load16[taillabel=2]; + Return25 -> MemMerge[taillabel=1 color=blue]; + MemMerge -> Start2:p1[taillabel=1 color=blue]; + MemMerge -> Phi_224[taillabel=2 color=blue]; + MemMerge -> Region23[taillabel=0 color=green]; +} diff --git a/docs/chapter13/graph3.json b/docs/chapter13/graph3.json new file mode 100644 index 00000000..e44eb1b1 --- /dev/null +++ b/docs/chapter13/graph3.json @@ -0,0 +1,26 @@ +{ + "ver": 1, + "comp": "chapter13/docs/graph3.svg", + "step": 1, + "roots": [25], + "scope": 0, + "nodes": [ + {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 224, "role": "MEM", "label": null}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 8, "label": "True", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 0}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 11, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 12, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 14, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 12, "role": "MEM", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": ".f", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 22, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}, {"idx": 4, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 25, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 224, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 22, "role": "MEM", "label": null}, {"idx": 2, "def": 14, "role": "MEM", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter13/graph3.svg b/docs/chapter13/graph3.svg new file mode 100644 index 00000000..0247b5c6 --- /dev/null +++ b/docs/chapter13/graph3.svg @@ -0,0 +1,128 @@ +#1[1] → #6 · MEM#1[2] → #224 · MEM#12[1] → #6 · MEM#12[2] → #9 · DATA#12[3] → #11 · DATA#14[1] → #12 · MEM#14[2] → #13 · DATA#14[3] → #4 · DATA#16[1] → #14 · MEM#16[2] → #9 · DATA#22[0] → #8 · CTRL#22[1] → #14 · MEM#22[2] → #9 · DATA#22[3] → #21 · DATA#22[4] → #16 · DATA#25[1] → #1 · MEM#25[2] → #16 · DATA#224[1] → #22 · MEM#224[2] → #14 · MEMMemMerge  #1#1 MemMerge +Type not computed + +[0] → — CTRL +[1] → #6 MEM +[2] → #224 MEM012Start  #2#2 Start +Type not computed + +#0  #4#4 #0 +Type not computed + +$mem  #6/1#6 $mem +Projection 1 of #2 +Type not computed + +[0] → #2 MEMTrue  #8/0#8 True +Projection 0 of #0 +Type not computed + +new S  #9#9 new S +Type not computed + +[0] → — CTRL0#2  #11#11 #2 +Type not computed + +.f =  #12#12 .f = +Type not computed + +[0] → — CTRL +[1] → #6 MEM +[2] → #9 DATA +[3] → #11 DATA0123new S  #13#13 new S +Type not computed + +[0] → — CTRL0.f =  #14#14 .f = +Type not computed + +[0] → — CTRL +[1] → #12 MEM +[2] → #13 DATA +[3] → #4 DATA0123.f  #16#16 .f +Type not computed + +[0] → — CTRL +[1] → #14 MEM +[2] → #9 DATA012#1  #21#21 #1 +Type not computed + +.f =  #22#22 .f = +Type not computed + +[0] → #8 CTRL +[1] → #14 MEM +[2] → #9 DATA +[3] → #21 DATA +[4] → #16 DATA01234Return  #25#25 Return +Type not computed + +[0] → — CTRL +[1] → #1 MEM +[2] → #16 DATA012MemPhi_2  #224#224 MemPhi_2 +Type not computed + +[0] → — ASSOC +[1] → #22 MEM +[2] → #14 MEM012 diff --git a/docs/chapter13/graph4.gv b/docs/chapter13/graph4.gv new file mode 100644 index 00000000..d7082072 --- /dev/null +++ b/docs/chapter13/graph4.gv @@ -0,0 +1,110 @@ +digraph chapter13 { +/* +struct S { int f; } +S v = new S; +int i = arg; +while (arg > 0) { + int j = i/3; + if (arg == 5) + v.f = j; + arg = arg - 1; +} +return v; + +*/ + rankdir=BT; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl$memarg
+
> + ]; + MemMerge [ shape=box label="MemMerge" ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_4 [ label="#0" ]; + new9 [ label="new S" ]; + Store10 [ label=".f =" ]; + Loop11 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg13 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + LT14 [ label="<" ]; + If16 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Div21 [ label="//" ]; + Con_22 [ label="#3" ]; + EQ23 [ label="==" ]; + Con_24 [ label="#5" ]; + If25 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Phi_230 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; + Store31 [ label=".f =" ]; + Region32 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_233 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; + Sub35 [ label="-" ]; + Con_36 [ label="#1" ]; + Return37 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop11;Phi_230;Phi_arg13;} + { rank=same; Region32;Phi_233;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return37[taillabel=0 color=red]; + new9 -> Start2:p0[taillabel=0 color=green]; + Store10 -> Start2:p1[taillabel=1 color=blue]; + Store10 -> new9[taillabel=2]; + Store10 -> Con_4[taillabel=3]; + Loop11 -> Start2:p0[taillabel=1 color=red]; + Loop11 -> Region32[taillabel=2 color=red constraint=false]; + Phi_arg13 -> Loop11 [style=dotted taillabel=0]; + Phi_arg13 -> Start2:p2[taillabel=1]; + Phi_arg13 -> Sub35[taillabel=2 constraint=false]; + LT14 -> Con_4[taillabel=1]; + LT14 -> Phi_arg13[taillabel=2]; + If16 -> Loop11[taillabel=0 color=red]; + If16 -> LT14[taillabel=1]; + Div21 -> Start2:p2[taillabel=1]; + Div21 -> Con_22[taillabel=2]; + EQ23 -> Phi_arg13[taillabel=1]; + EQ23 -> Con_24[taillabel=2]; + If25 -> If16:p0[taillabel=0 color=red]; + If25 -> EQ23[taillabel=1]; + Phi_230 -> Loop11 [style=dotted taillabel=0]; + Phi_230 -> Store10[taillabel=1 color=blue]; + Phi_230 -> Phi_233[taillabel=2 color=blue constraint=false]; + Store31 -> Phi_230[taillabel=1 color=blue]; + Store31 -> new9[taillabel=2]; + Store31 -> Div21[taillabel=3]; + Region32 -> If25:p0[taillabel=1 color=red]; + Region32 -> If25:p1[taillabel=2 color=red]; + Phi_233 -> Region32 [style=dotted taillabel=0]; + Phi_233 -> Store31[taillabel=1 color=blue]; + Phi_233 -> Phi_230[taillabel=2 color=blue constraint=false]; + Sub35 -> Phi_arg13[taillabel=1]; + Sub35 -> Con_36[taillabel=2]; + Return37 -> If16:p1[taillabel=0 color=red]; + Return37 -> new9[taillabel=2]; + Return37 -> MemMerge[taillabel=1 color=blue]; + MemMerge -> Start2:p1[taillabel=1 color=blue]; + MemMerge -> Phi_230[taillabel=2 color=blue]; +} diff --git a/docs/chapter13/graph4.json b/docs/chapter13/graph4.json new file mode 100644 index 00000000..add08b6b --- /dev/null +++ b/docs/chapter13/graph4.json @@ -0,0 +1,24 @@ +{ + "ver": 1, + "comp": "chapter13/docs/graph4.svg", + "step": 1, + "roots": [37], + "scope": 0, + "nodes": [ + {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 7, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 2}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 10, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "//", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 22, "role": "DATA", "label": null}], "proj": null}, + {"id": 22, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 31, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 230, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}], "proj": null}, + {"id": 37, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 230, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 233, "role": "MEM", "label": null}], "proj": null}, + {"id": 233, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 31, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter13/graph4.svg b/docs/chapter13/graph4.svg new file mode 100644 index 00000000..9ca92879 --- /dev/null +++ b/docs/chapter13/graph4.svg @@ -0,0 +1,120 @@ +#1[1] → #6 · MEM#1[2] → #230 · MEM#10[1] → #6 · MEM#10[2] → #9 · DATA#10[3] → #4 · DATA#21[1] → #7 · DATA#21[2] → #22 · DATA#31[1] → #230 · MEM#31[2] → #9 · DATA#31[3] → #21 · DATA#37[1] → #1 · MEM#37[2] → #9 · DATA#230[1] → #10 · MEM#230[2] → #233 · MEM#233[1] → #31 · MEM#233[2] → #230 · MEMMemMerge  #1#1 MemMerge +Type not computed + +[0] → — DATA +[1] → #6 MEM +[2] → #230 MEM012Start  #2#2 Start +Type not computed + +#0  #4#4 #0 +Type not computed + +$mem  #6/1#6 $mem +Projection 1 of #2 +Type not computed + +[0] → #2 MEMarg  #7/2#7 arg +Projection 2 of #2 +Type not computed + +[0] → #2 DATAnew S  #9#9 new S +Type not computed + +[0] → — CTRL0.f =  #10#10 .f = +Type not computed + +[0] → — DATA +[1] → #6 MEM +[2] → #9 DATA +[3] → #4 DATA0123//  #21#21 // +Type not computed + +[0] → — DATA +[1] → #7 DATA +[2] → #22 DATA012#3  #22#22 #3 +Type not computed + +.f =  #31#31 .f = +Type not computed + +[0] → — DATA +[1] → #230 MEM +[2] → #9 DATA +[3] → #21 DATA0123Return  #37#37 Return +Type not computed + +[0] → — CTRL +[1] → #1 MEM +[2] → #9 DATA012MemPhi_2  #230#230 MemPhi_2 +Type not computed + +[0] → — ASSOC +[1] → #10 MEM +[2] → #233 MEM012MemPhi_2  #233#233 MemPhi_2 +Type not computed + +[0] → — ASSOC +[1] → #31 MEM +[2] → #230 MEM012 diff --git a/docs/chapter13/graph5.gv b/docs/chapter13/graph5.gv new file mode 100644 index 00000000..8189f6dd --- /dev/null +++ b/docs/chapter13/graph5.gv @@ -0,0 +1,117 @@ +digraph chapter13 { +/* +struct S { int f; } +S v = new S; +int i = arg; +while (arg > 0) { + int j = i/3; + if (arg == 5) + v.f = j; + arg = arg - 1; +} +return v; + +*/ + rankdir=BT; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl$memarg
+
> + ]; + MemMerge [ shape=box label="MemMerge" ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_4 [ label="#0" ]; + new9 [ label="new S" ]; + Store10 [ label=".f =" ]; + Loop11 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg13 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + LT14 [ label="<" ]; + If16 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Div21 [ label="//" ]; + Con_22 [ label="#3" ]; + EQ23 [ label="==" ]; + Con_24 [ label="#5" ]; + If25 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Phi_230 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; + Store31 [ label=".f =" ]; + Region32 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_233 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; + Sub35 [ label="-" ]; + Con_36 [ label="#1" ]; + Return37 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop11;Phi_230;Phi_arg13;} + { rank=same; Region32;Phi_233;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return37[taillabel=0 color=red]; + new9 -> Start2:p0[taillabel=0 color=green]; + Store10 -> Start2:p0[taillabel=0 color=red]; + Store10 -> Start2:p1[taillabel=1 color=blue]; + Store10 -> new9[taillabel=2]; + Store10 -> Con_4[taillabel=3]; + Loop11 -> Start2:p0[taillabel=1 color=red]; + Loop11 -> Region32[taillabel=2 color=red constraint=false]; + Phi_arg13 -> Loop11 [style=dotted taillabel=0]; + Phi_arg13 -> Start2:p2[taillabel=1]; + Phi_arg13 -> Sub35[taillabel=2 constraint=false]; + LT14 -> Loop11[taillabel=0 color=red]; + LT14 -> Con_4[taillabel=1]; + LT14 -> Phi_arg13[taillabel=2]; + If16 -> Loop11[taillabel=0 color=red]; + If16 -> LT14[taillabel=1]; + Div21 -> Start2[taillabel=0 color=red]; + Div21 -> Start2:p2[taillabel=1]; + Div21 -> Con_22[taillabel=2]; + EQ23 -> Loop11[taillabel=0 color=red]; + EQ23 -> Phi_arg13[taillabel=1]; + EQ23 -> Con_24[taillabel=2]; + If25 -> If16:p0[taillabel=0 color=red]; + If25 -> EQ23[taillabel=1]; + Phi_230 -> Loop11 [style=dotted taillabel=0]; + Phi_230 -> Store10[taillabel=1 color=blue]; + Phi_230 -> Phi_233[taillabel=2 color=blue constraint=false]; + Store31 -> Loop11[taillabel=0 color=red]; + Store31 -> Phi_230[taillabel=1 color=blue]; + Store31 -> new9[taillabel=2]; + Store31 -> Div21[taillabel=3]; + Region32 -> If25:p0[taillabel=1 color=red]; + Region32 -> If25:p1[taillabel=2 color=red]; + Phi_233 -> Region32 [style=dotted taillabel=0]; + Phi_233 -> Store31[taillabel=1 color=blue]; + Phi_233 -> Phi_230[taillabel=2 color=blue constraint=false]; + Sub35 -> Loop11[taillabel=0 color=red]; + Sub35 -> Phi_arg13[taillabel=1]; + Sub35 -> Con_36[taillabel=2]; + Return37 -> If16:p1[taillabel=0 color=red]; + Return37 -> new9[taillabel=2]; + Return37 -> MemMerge[taillabel=1 color=blue]; + MemMerge -> Start2:p1[taillabel=1 color=blue]; + MemMerge -> Phi_230[taillabel=2 color=blue]; + MemMerge -> Loop11[taillabel=0 color=green]; +} diff --git a/docs/chapter13/graph5.json b/docs/chapter13/graph5.json new file mode 100644 index 00000000..6b1722f6 --- /dev/null +++ b/docs/chapter13/graph5.json @@ -0,0 +1,24 @@ +{ + "ver": 1, + "comp": "chapter13/docs/graph5.svg", + "step": 1, + "roots": [37], + "scope": 0, + "nodes": [ + {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 7, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 2}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 10, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "//", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 22, "role": "DATA", "label": null}], "proj": null}, + {"id": 22, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 31, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 230, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}], "proj": null}, + {"id": 37, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 230, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 233, "role": "MEM", "label": null}], "proj": null}, + {"id": 233, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 31, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter13/graph5.svg b/docs/chapter13/graph5.svg new file mode 100644 index 00000000..c120550f --- /dev/null +++ b/docs/chapter13/graph5.svg @@ -0,0 +1,120 @@ +#1[1] → #6 · MEM#1[2] → #230 · MEM#10[1] → #6 · MEM#10[2] → #9 · DATA#10[3] → #4 · DATA#21[1] → #7 · DATA#21[2] → #22 · DATA#31[1] → #230 · MEM#31[2] → #9 · DATA#31[3] → #21 · DATA#37[1] → #1 · MEM#37[2] → #9 · DATA#230[1] → #10 · MEM#230[2] → #233 · MEM#233[1] → #31 · MEM#233[2] → #230 · MEMMemMerge  #1#1 MemMerge +Type not computed + +[0] → — CTRL +[1] → #6 MEM +[2] → #230 MEM012Start  #2#2 Start +Type not computed + +#0  #4#4 #0 +Type not computed + +$mem  #6/1#6 $mem +Projection 1 of #2 +Type not computed + +[0] → #2 MEMarg  #7/2#7 arg +Projection 2 of #2 +Type not computed + +[0] → #2 DATAnew S  #9#9 new S +Type not computed + +[0] → — CTRL0.f =  #10#10 .f = +Type not computed + +[0] → — CTRL +[1] → #6 MEM +[2] → #9 DATA +[3] → #4 DATA0123//  #21#21 // +Type not computed + +[0] → — CTRL +[1] → #7 DATA +[2] → #22 DATA012#3  #22#22 #3 +Type not computed + +.f =  #31#31 .f = +Type not computed + +[0] → — CTRL +[1] → #230 MEM +[2] → #9 DATA +[3] → #21 DATA0123Return  #37#37 Return +Type not computed + +[0] → — CTRL +[1] → #1 MEM +[2] → #9 DATA012MemPhi_2  #230#230 MemPhi_2 +Type not computed + +[0] → — ASSOC +[1] → #10 MEM +[2] → #233 MEM012MemPhi_2  #233#233 MemPhi_2 +Type not computed + +[0] → — ASSOC +[1] → #31 MEM +[2] → #230 MEM012 diff --git a/docs/chapter13/graph6.gv b/docs/chapter13/graph6.gv new file mode 100644 index 00000000..47165fdb --- /dev/null +++ b/docs/chapter13/graph6.gv @@ -0,0 +1,117 @@ +digraph chapter13 { +/* +struct S { int f; } +S v = new S; +int i = arg; +while (arg > 0) { + int j = i/3; + if (arg == 5) + v.f = j; + arg = arg - 1; +} +return v; + +*/ + rankdir=BT; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl$memarg
+
> + ]; + MemMerge [ shape=box label="MemMerge" ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_4 [ label="#0" ]; + new9 [ label="new S" ]; + Store10 [ label=".f =" ]; + Loop11 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg13 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + LT14 [ label="<" ]; + If16 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Div21 [ label="//" ]; + Con_22 [ label="#3" ]; + EQ23 [ label="==" ]; + Con_24 [ label="#5" ]; + If25 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Phi_230 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; + Store31 [ label=".f =" ]; + Region32 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_233 [ style=filled fillcolor=lightyellow label="MemPhi_2" ]; + Sub35 [ label="-" ]; + Con_36 [ label="#1" ]; + Return37 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop11;Phi_230;Phi_arg13;} + { rank=same; Region32;Phi_233;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return37[taillabel=0 color=red]; + new9 -> Start2:p0[taillabel=0 color=green]; + Store10 -> Start2:p0[taillabel=0 color=red]; + Store10 -> Start2:p1[taillabel=1 color=blue]; + Store10 -> new9[taillabel=2]; + Store10 -> Con_4[taillabel=3]; + Loop11 -> Start2:p0[taillabel=1 color=red]; + Loop11 -> Region32[taillabel=2 color=red constraint=false]; + Phi_arg13 -> Loop11 [style=dotted taillabel=0]; + Phi_arg13 -> Start2:p2[taillabel=1]; + Phi_arg13 -> Sub35[taillabel=2 constraint=false]; + LT14 -> Loop11[taillabel=0 color=red]; + LT14 -> Con_4[taillabel=1]; + LT14 -> Phi_arg13[taillabel=2]; + If16 -> Loop11[taillabel=0 color=red]; + If16 -> LT14[taillabel=1]; + Div21 -> Start2:p0[taillabel=0 color=red]; + Div21 -> Start2:p2[taillabel=1]; + Div21 -> Con_22[taillabel=2]; + EQ23 -> If16:p0[taillabel=0 color=red]; + EQ23 -> Phi_arg13[taillabel=1]; + EQ23 -> Con_24[taillabel=2]; + If25 -> If16:p0[taillabel=0 color=red]; + If25 -> EQ23[taillabel=1]; + Phi_230 -> Loop11 [style=dotted taillabel=0]; + Phi_230 -> Store10[taillabel=1 color=blue]; + Phi_230 -> Phi_233[taillabel=2 color=blue constraint=false]; + Store31 -> If25:p0[taillabel=0 color=red]; + Store31 -> Phi_230[taillabel=1 color=blue]; + Store31 -> new9[taillabel=2]; + Store31 -> Div21[taillabel=3]; + Region32 -> If25:p0[taillabel=1 color=red]; + Region32 -> If25:p1[taillabel=2 color=red]; + Phi_233 -> Region32 [style=dotted taillabel=0]; + Phi_233 -> Store31[taillabel=1 color=blue]; + Phi_233 -> Phi_230[taillabel=2 color=blue constraint=false]; + Sub35 -> Region32[taillabel=0 color=red]; + Sub35 -> Phi_arg13[taillabel=1]; + Sub35 -> Con_36[taillabel=2]; + Return37 -> If16:p1[taillabel=0 color=red]; + Return37 -> new9[taillabel=2]; + Return37 -> MemMerge[taillabel=1 color=blue]; + MemMerge -> Start2:p1[taillabel=1 color=blue]; + MemMerge -> Phi_230[taillabel=2 color=blue]; + MemMerge -> If16:p1[taillabel=0 color=green]; +} diff --git a/docs/chapter13/graph6.json b/docs/chapter13/graph6.json new file mode 100644 index 00000000..c63c717f --- /dev/null +++ b/docs/chapter13/graph6.json @@ -0,0 +1,25 @@ +{ + "ver": 1, + "comp": "chapter13/docs/graph6.svg", + "step": 1, + "roots": [37], + "scope": 0, + "nodes": [ + {"id": 1, "label": "MemMerge", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 6, "label": "$mem", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 2, "role": "MEM", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 7, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 2}}, + {"id": 9, "label": "new S", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}], "proj": null}, + {"id": 10, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "True", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 0}}, + {"id": 21, "label": "//", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 22, "role": "DATA", "label": null}], "proj": null}, + {"id": 22, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 31, "label": ".f =", "type": null, "kind": "MEM", "edges": [{"idx": 0, "def": 15, "role": "CTRL", "label": null}, {"idx": 1, "def": 230, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}, {"idx": 3, "def": 21, "role": "DATA", "label": null}], "proj": null}, + {"id": 37, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 1, "role": "MEM", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 230, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 10, "role": "MEM", "label": null}, {"idx": 2, "def": 233, "role": "MEM", "label": null}], "proj": null}, + {"id": 233, "label": "MemPhi_2", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 31, "role": "MEM", "label": null}, {"idx": 2, "def": 230, "role": "MEM", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter13/graph6.svg b/docs/chapter13/graph6.svg new file mode 100644 index 00000000..d6dec88f --- /dev/null +++ b/docs/chapter13/graph6.svg @@ -0,0 +1,124 @@ +#1[1] → #6 · MEM#1[2] → #230 · MEM#10[1] → #6 · MEM#10[2] → #9 · DATA#10[3] → #4 · DATA#21[1] → #7 · DATA#21[2] → #22 · DATA#31[0] → #15 · CTRL#31[1] → #230 · MEM#31[2] → #9 · DATA#31[3] → #21 · DATA#37[1] → #1 · MEM#37[2] → #9 · DATA#230[1] → #10 · MEM#230[2] → #233 · MEM#233[1] → #31 · MEM#233[2] → #230 · MEMMemMerge  #1#1 MemMerge +Type not computed + +[0] → — CTRL +[1] → #6 MEM +[2] → #230 MEM012Start  #2#2 Start +Type not computed + +#0  #4#4 #0 +Type not computed + +$mem  #6/1#6 $mem +Projection 1 of #2 +Type not computed + +[0] → #2 MEMarg  #7/2#7 arg +Projection 2 of #2 +Type not computed + +[0] → #2 DATAnew S  #9#9 new S +Type not computed + +[0] → — CTRL0.f =  #10#10 .f = +Type not computed + +[0] → — CTRL +[1] → #6 MEM +[2] → #9 DATA +[3] → #4 DATA0123True  #15/0#15 True +Projection 0 of #0 +Type not computed + +//  #21#21 // +Type not computed + +[0] → — CTRL +[1] → #7 DATA +[2] → #22 DATA012#3  #22#22 #3 +Type not computed + +.f =  #31#31 .f = +Type not computed + +[0] → #15 CTRL +[1] → #230 MEM +[2] → #9 DATA +[3] → #21 DATA0123Return  #37#37 Return +Type not computed + +[0] → — CTRL +[1] → #1 MEM +[2] → #9 DATA012MemPhi_2  #230#230 MemPhi_2 +Type not computed + +[0] → — ASSOC +[1] → #10 MEM +[2] → #233 MEM012MemPhi_2  #233#233 MemPhi_2 +Type not computed + +[0] → — ASSOC +[1] → #31 MEM +[2] → #230 MEM012 diff --git a/docs/chapter13/graph7.gv b/docs/chapter13/graph7.gv new file mode 100644 index 00000000..b6507e53 --- /dev/null +++ b/docs/chapter13/graph7.gv @@ -0,0 +1,23 @@ +digraph chapter13 { + rankdir=BT; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Con_4 [ label="#0" ]; + Loop8 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + { rank=same; Loop8;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Loop8 -> Start2:p0[taillabel=1 color=red]; + Loop8 -> Loop8[taillabel=2 color=red constraint=false]; +} diff --git a/docs/chapter13/graph7.json b/docs/chapter13/graph7.json new file mode 100644 index 00000000..0e3efb9f --- /dev/null +++ b/docs/chapter13/graph7.json @@ -0,0 +1,16 @@ +{ + "ver": 1, + "comp": "chapter13/docs/graph7.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 8, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 1, "role": "CTRL", "label": null}, {"idx": 2, "def": 8, "role": "CTRL", "label": null}], "proj": null} + ], + "groups": [ + {"id": 8, "par": 0, "nodes": [8]} + ] +} diff --git a/docs/chapter13/graph7.svg b/docs/chapter13/graph7.svg new file mode 100644 index 00000000..15d886dc --- /dev/null +++ b/docs/chapter13/graph7.svg @@ -0,0 +1,78 @@ +#8[1] → #1 · CTRL#8[2] → #8 · CTRL$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +#0  #4#4 #0 +Type not computed + +Loop  #8#8 Loop +Type not computed + +[0] → — DATA +[1] → #1 CTRL +[2] → #8 CTRL012Loop  #8Loop · 1 nodes−Fold region diff --git a/docs/chapter13/graph8.gv b/docs/chapter13/graph8.gv new file mode 100644 index 00000000..442b6843 --- /dev/null +++ b/docs/chapter13/graph8.gv @@ -0,0 +1,45 @@ +digraph chapter13 { +/* +while (1) {} +return 0; + +*/ + rankdir=BT; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Never18 [ shape=plaintext label=< + + + +
Never
+ + +
TrueFalse
+
> + ]; + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_4 [ label="#0" ]; + Return21 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Loop8 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + { rank=same; Loop8;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Never18 -> Loop8[taillabel=0 color=red]; + Never18 -> Con_4[taillabel=1]; + Stop3 -> Return21[taillabel=0 color=red]; + Return21 -> Never18:p0[taillabel=0 color=red]; + Return21 -> Con_4[taillabel=2]; + Loop8 -> Start2:p0[taillabel=1 color=red]; + Loop8 -> Never18:p1[taillabel=2 color=red constraint=false]; +} diff --git a/docs/chapter13/graph8.json b/docs/chapter13/graph8.json new file mode 100644 index 00000000..b7d4f41c --- /dev/null +++ b/docs/chapter13/graph8.json @@ -0,0 +1,21 @@ +{ + "ver": 1, + "comp": "chapter13/docs/graph8.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 18, "role": "CTRL", "label": null}], "proj": {"par": 18, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 21, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 5, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 18, "role": "CTRL", "label": null}], "proj": {"par": 18, "idx": 1}}, + {"id": 6, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 8, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "CTRL", "label": null}, {"idx": 2, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 18, "label": "Never", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 0, "role": "DATA", "label": null}, {"idx": 2, "def": 4, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 8, "par": 0, "nodes": [1, 5, 8, 18]} + ] +} diff --git a/docs/chapter13/graph8.svg b/docs/chapter13/graph8.svg new file mode 100644 index 00000000..d96a9a7d --- /dev/null +++ b/docs/chapter13/graph8.svg @@ -0,0 +1,98 @@ +#3[0] → #21 · CTRL#8[1] → #6 · CTRL#8[2] → #5 · CTRL#18[0] → #8 · CTRL#18[1] → #4 · DATA#21[0] → #1 · CTRL#21[2] → #4 · DATATrue  #1/0#1 True +Projection 0 of #18 +Type not computed + +[0] → #18 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #21 CTRL0#0  #4#4 #0 +Type not computed + +False  #5/1#5 False +Projection 1 of #18 +Type not computed + +[0] → #18 CTRL$ctrl  #6/0#6 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLLoop  #8#8 Loop +Type not computed + +[0] → — DATA +[1] → #6 CTRL +[2] → #5 CTRL012Never  #18#18 Never +Type not computed + +[0] → #8 CTRL +[1] → #4 DATA01Return  #21#21 Return +Type not computed + +[0] → #1 CTRL +[1] → — DATA +[2] → #4 DATA012Loop  #8Loop · 4 nodes−Fold region -- cgit v1.2.3