diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/chapter20/Makefile | 12 | ||||
| -rw-r--r-- | docs/chapter20/README.ja.md | 264 | ||||
| -rw-r--r-- | docs/chapter20/README.md | 529 | ||||
| -rw-r--r-- | docs/chapter20/font-awesome-4.7.0.zip | bin | 0 -> 669808 bytes | |||
| -rw-r--r-- | docs/chapter20/ifg_trim.pdf | bin | 0 -> 155190 bytes | |||
| -rw-r--r-- | docs/chapter20/lattice.gv | 203 | ||||
| -rw-r--r-- | docs/chapter20/lattice.svg | 691 | ||||
| -rw-r--r-- | docs/chapter20/lattice2.gv | 85 | ||||
| -rw-r--r-- | docs/chapter20/lattice2.svg | 260 | ||||
| -rw-r--r-- | docs/chapter20/pardoe.docx | bin | 0 -> 22583 bytes | |||
| -rw-r--r-- | docs/chapter20/webtcp.min.js | 65 |
11 files changed, 2109 insertions, 0 deletions
diff --git a/docs/chapter20/Makefile b/docs/chapter20/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter20/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/docs/chapter20/README.ja.md b/docs/chapter20/README.ja.md new file mode 100644 index 00000000..34fc25b7 --- /dev/null +++ b/docs/chapter20/README.ja.md @@ -0,0 +1,264 @@ +# 第20章: グラフ彩色によるレジスタ割り当て + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第19章](../chapter19/README.ja.md) | +[次の章: 第21章](../chapter21/README.ja.md) + +文法は[第18章](../chapter18/18-grammar.ja.md)から変わりません。 + +## 参考資料 + +これは Briggs-Chaitin-Click 型の割り当て器であり、過去25年間にわたり大きな成功を収めてきた HotSpot の C2 割り当て器に非常によく似ています。 + +Wikipedia にはレジスタ割り当て全般のよい概説があります: https://en.wikipedia.org/wiki/Register_allocation + +Chaitin の原論文: https://en.wikipedia.org/wiki/Register_allocation#CITEREFChaitin1982 + +Briggs による追加: https://dl.acm.org/doi/10.1145/177492.177575 + +Briggs/Chaitin のよい講義スライド PDF: https://aktemur.github.io/cs544/lectures/chapter%2013%20registerAllocation.pdf + +Briggs や Chaitin を組み合わせて検索すると、ほかにも役立つリンクがいくつか見つかります。基本的に、この時代にはレジスタ割り当ての改良が相次ぎ、その多くが高性能な主流コンパイラに取り込まれました。 + +グラフ彩色割り当て器の高速化に関する非常に古い未発表論文 [Interference Graph Trimming](ifg_trim.pdf) を同梱しました。 + +## 命令選択、レジスタ割り当て、命令エンコーディングにまつわる全体的な問題と開発上の問題 + +レジスタ割り当ての出力、すなわち演算に対するレジスタの割り当ては、実行方法がないと大量にテストするのが困難です。命令選択、レジスタ割り当て、命令エンコーディングの3つすべてが完成するまでは、実行方法が得られません。そのため、エンコーディングの完成前後には、命令選択とレジスタ割り当てで多くのバグが見つかると予想しています。もちろん出力を手作業で調べて明らかな問題は修正しますが、実際にコードを動かせるようになるまで、多くのバグが残ります。 + +つまり、この章で説明する作業に対する更新やバグ修正が、ほかの章に含まれています。 + +特にレジスタ割り当て器については、これからかなりの数の章にわたり、章ごとに徐々に改良を追加します。割り当て器は一般に最終的には多数のヒューリスティックを持ちますが、それらを少しずつ追加します。 + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチ上の直線的な Git リビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter20) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter19...linear-chapter20) することもできます。 + +## 基本理論 + +参考資料には基本概念の説明がいくつかありますが、重複を承知で、ここでも短く説明します。 + +読者はレジスタ割り当てが *なぜ* 必要かを知っていると仮定します。マシンレジスタは価値の高い有限資源であり、あらゆる有限資源と同様、適切に割り当てる必要があります。 + +グラフ彩色はそのような割り当て方法の1つです。マシンレジスタを色として扱い、各 *生存区間* が自身のレジスタ／色を必要とする *生存区間の干渉グラフ* を構築します。グラフを彩色することで、各生存区間が、特に別の生存区間と重なる、つまり *干渉する* 場合に、一意のレジスタを得ることを保証します。 + +彩色が成功すれば割り当ては終了し、いくらかの管理処理を経て、プログラムはたとえばコード出力の準備が整います。彩色が失敗したら、衝突する生存区間をスピルするか分割する必要があります。この割り当て器では、生存区間の *分割* を行います。分割により区間は短くなり、干渉するほかの区間が減るため、彩色しやすくなります。一般に、大きな関数は彩色可能になるまで数回の分割を必要とすることがあります。この問題は NP 完全なので保証はなく、最終的な割り当て品質は分割と彩色のヒューリスティックに大きく依存します。 + +したがって、彩色の中核アルゴリズムには多くの「高度な理論」を使いますが、実際の成功の多くは、多数のヒューリスティックに依存します。 + +### 彩色ラウンド + +彩色が得られるまで、次のラウンドを繰り返します。 + +- 生存区間を構築します。区間内のすべての命令は同じレジスタを必要とします。Phi 関数は無関係な定義／使用の辺を同じ生存区間に組み込み、衝突の多い大規模な相互接続区間を生み出すことがあります。一部のハードウェア演算は入力と出力に同じレジスタを要求し（X86 はこの点で悪名高い）、これも区間の数を減らして大きくします。互いに素な集合の Union-Find アルゴリズムを使い、プログラムを前向きに1回走査して高速に区間を構築します。 +- 干渉グラフを構築します。同時に生存する区間どうしは *干渉*、つまり衝突します。CFG を後ろ向きに走査する生存性解析で構築し、ループの入れ子深さに応じて複数回の走査が必要な場合があります。データ構造は通常2次元ビット集合で、三角形の部分だけを保持してサイズを半分にします。生存性解析の一部として、ブロックごとの到達定義集合も持ちます。 +- 干渉グラフを彩色します。グラフのノード（生存区間）のうち、次数が厳密に低いもの（隣接ノードより利用可能レジスタが多いもの）は、必ず色を得られます。衝突する隣接ノードが少ないのでレジスタ（色）を必ず得られるため、グラフから除去できます。この自明なノードの除去により、さらに多くのノードが自明になります。ノードが尽きて彩色が保証されるか、高次数のクリーク、すなわち相互に干渉し、どれも色を保証されない区間集合が見つかるまで繰り返します。後者では、彩色できないかもしれない「危険な」区間を1つ取り出します。グラフが空になったら、逆順に区間を戻しながら彩色します。自明な区間はすべて彩色できますが、危険な区間はできる場合もできない場合もあります。 +- すべての区間が色を得たら、レジスタ割り当ては終了です。そうでなければ分割ラウンドに入ります。彩色できなかった区間を、いくつかのヒューリスティックで多数の小さな区間に分割します。分割には相反する要求があります。多すぎるとスピルが増え、一般に割り当てが悪くなります。少なすぎると彩色不能のまま、割り当てに向けて前進しません。分割が終わったら、生存区間構築、干渉グラフ構築、彩色という新たなラウンドを始めます。 + +## レジスタとレジスタマスク + +レジスタこそ、レジスタ割り当ての対象です。0から始まる小さな密な整数で表し、番号は一般にハードウェアのエンコーディングに従います。X86_64 では RAX が0、RCX が1となり、16個の GPR まで続きます。XMM レジスタ番号は16から31です。番号は一意でなければなりません。割り当て器はこれによってレジスタを追跡します。 + +#### 単純な `long` ではなく RegMask クラスを使う理由 + +レジスタ集合はレジスタマスクに格納します。小さく単純なマシンなら i64 や i128（64または128ビット整数）で十分であり、すべての割り当てがこのビット数に収まるなら、この表現がはるかに優れています。割り当て器は、スタック経由のパラメータと、レジスタを得られない分割にもビットを必要とします。X86 のような32レジスタのマシンでは、フラグ用の1つを加えて33レジスタです。Java の `long` は64ビットなので、スピルとスタック渡しに31ビットが残ります。これはほぼすべての割り当てに十分で、最大級のものだけが使い切ります。しかし64レジスタのチップへ移ると、すぐに不足し、少なくとも128ビットのマスクが必要です。Java では128ビット値を直接 *返せない* ため、Simple は `RegMask` クラスのオブジェクトを使います。 + +#### スタックスロット + +Click による拡張の1つは「スタックスロット」を単なる別のレジスタとして扱う考え方です。ほかのレジスタと同様に彩色することで、スタックを非常に効率よく使えます。C2 は非常に小さいスタックフレームで知られています。もう1つの利点は、callee-save レジスタが優先して分割されることです。生存期間が非常に長く、入口での定義と出口での使用が1つずつしかないためです。その分割は最終的にスタックに彩色され、自然に呼び出しのプロローグとエピローグを構築します。この割り当て器は、それ以外にスタックフレーム管理のための特別な処理を行いません。結果として自然に得られます。 + +多くのレジスタマスクは不変です。たとえば特定のオペコードで許されるレジスタや、呼び出し規約を表すものです。一方、制約集合を蓄積する際に割り当て器が日常的にビットを落とす、可変のビット集合を表すマスクもあります。使い方を区別しやすくするため、`RegMask` クラスには可変版と不変版があります。 + +#### メモリ + +メモリ辺は順序を強制するために存在しますが、レジスタは得ません。割り当て器は基本的にそれらを無視します。 + +### Callee-save / Caller-save レジスタ + +この割り当て器は callee-save と caller-save のレジスタをほぼ特別扱いせず、保存・復元専用のプロローグやエピローグも構築しません。割り当て開始時に、各 `Return` と、各 `Fun` に由来する `CalleeSave` との間に SoN グラフ辺を追加します。通常の ABI が定義する callee-save 集合に固定するレジスタマスクを、これらの辺に与えます。 + +callee-save の生存区間は、関数先頭の `CalleeSave` という単一定義と、`Return` という単一使用を持ちます。安くスピルでき、広い範囲にわたってレジスタを解放するので、理想的なスピル候補です。レジスタを増やすために何かをスピルする必要があると、これらが最初にスピルされます。通常の生存区間分割の結果として、プロローグとエピローグが構築されます。 + +`Calls` は caller-save レジスタを破壊します（callee-save マスクを反転したものです）。これはレジスタを破壊するほかの演算と同様、通常の干渉グラフ構築で計算します。呼び出しで多数のレジスタを破壊すると、その時点で生存しているものから利用可能なレジスタがすべてなくなることが多く、スピルが強制されます。その結果、すぐに理想的な候補である callee-save レジスタがスピルされます。 + +## 生存区間 + +生存区間は、同じレジスタを得なければならないノードと辺の集合です。形状にほとんど制限のない、相互接続された網を形成します。また、すべての構成部分のレジスタ制約を集約します。 + +生存区間は `LRG` クラスのインスタンスとして保持します。そのフィールドの大半はスピルのヒューリスティック用ですが、LRG を定義する重要なフィールドもいくつかあります。`RegAlloc` には、Node から LRG への参照表、すなわち `Node` から `LRG` への対応を含む、LRG を扱う関数がいくつもあります。これは各 Node に専用の LRG フィールドを持つのと非常によく似ていますが、LRG は RegAlloc 中だけ使うので、それ以外ではフィールドが無駄な重荷になります。 + +LRG は自身の名前となる、一意で密な整数 `_lrg` 番号を持ちます。新しい番号は `RegAlloc._lrg_num` カウンタから得ます。LRG は結合できます。これが [Union-Find アルゴリズム](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) です。結合時には、小さい `_lrg` 番号が代表になります。結合は `BuildLRG` 中だけ行い、`Phi` がすべての入出力を同じレジスタに強制するか、2アドレス命令のために発生します。LRG には対応する `union`、`find` 呼び出しと、設定された `_leader` フィールドがあります。 + +割り当て後、`LRG._reg` は選択されたレジスタを保持します。割り当て中、`LRG._mask` は利用可能なレジスタ集合を保持します。通常はすべての既定値から各種の衝突を除いたものです。 + +`LRG._adj` は干渉グラフ全体の一部として隣接ノードのリストを保持し、彩色フェーズでだけ使います。[グラフについての詳細はこちらです。](https://en.wikipedia.org/wiki/Graph_(abstract_data_type)) これはグラフの「隣接リスト」表現で、IFG の2次元ビット集合（それ自体は `BitSet` の1次元リスト）から構築します。グラフ彩色によるレジスタ割り当ては、アルゴリズムの途中でデータ構造のレイアウトを変えることが有効な、数少ない場面の1つです。 + +残りのフィールドは、各種スピルのヒューリスティック専用です。 + +- `_machDef` `_machUse` `_uidx`: 代表となる定義と使用。 +- `_splitDef` `_splitUse`: この LRG に関係する代表的な分割。バイアス付き彩色はレジスタ選択を合わせて、これらを除去しようとします。 +- `_selfConflicts`: *自己衝突* ノードの部分集合。干渉グラフ構築時に検出し、積極的な分割を必要とします。 +- `_1regDefCnt` `_1regUseCnt`: 単一レジスタに固定された定義と使用の数。通常、レジスタ選択の自由を取り戻すため、使用の直前または定義の直後で強制分割を必要とします。 + +## 生存区間と衝突 + +生存区間の `_mask` が空になると、*ハード衝突* か *破壊* が起きた可能性があります。区間は自分自身とも干渉し、*自己衝突* を起こします。彩色中に、干渉区間の彩色不能なクリークが見つかり、*容量不足のスピル* に至ることもあります。このため区間内にはいくつかの衝突レベルがあり、それぞれに異なる対処のヒューリスティックを使います。 + +### ハード衝突 + +生存区間は、レジスタ要求が衝突し、有効な選択肢がなくなる *ハード衝突* を起こすことがあります。明らかな例は、入口のパラメータが `rdx` に固定されながら、出口の値として `rax` にも必要になる場合です。両方を同時に選べないので分割が必要です。生存区間構築フェーズでは、すべての定義と使用のレジスタ制約を AND します。`RegMask` は有効レジスタをすべて失うか、わずかな選択肢だけを残すことがあります。 + +ハード衝突は通常、生存区間構築時に見つかり、干渉グラフ構築や彩色の前に分割ラウンドを引き起こします。干渉グラフ構築中にも見つかる場合があり、一般に1レジスタの破壊が原因です。 + +### 干渉の回避 + +Briggs-Chaitin 割り当て器に対する Click の拡張の1つは、レジスタ制約を利用して干渉グラフの次数を下げることです。そうでなければ辺集合は O(n^2) になります。LR1 が、`rdx` を必要とする呼び出し引数などによって単一レジスタに制限され、より多くの選択肢を持つ LR2 と本来衝突する場合、LR2 の選択肢から `rdx` を除きます。`rdx` がなければ両者に共通レジスタがなくなり、衝突しません。その間の干渉グラフ辺を単に追加しないのです。呼び出し引数の制限は非常に一般的で、この辺除去は O(n^2) の辺集合を大きく縮小し、割り当てを大きな定数倍だけ高速化できます。 + +### 自己衝突 + +生存区間は、異なる2つの値が同時に生存しながら同じレジスタを要求する、*自己衝突* を起こせます。この区間は *必ず* 分割し、その結果としてコピーを得ます。単純な `fib` プログラムなどの、ループをまたぐ依存関係で起きます。 + +```java + int x=1, y=1; + while( true ) { + tmp = x + y; + y = x; + x = tmp; + }; + +``` + +SoN の SSA 形式では: + +```java + int x0 = 1, y0 = 1; + while( true ) { + x1 = phi(x0,x2); + y1 = phi(y0,x1); + x2 = x1 + y1; + } +``` + +変数 `x0,x1,x2,y0,y1` はすべて `Phi` で結合されるので、同じ生存区間の一部です。しかし `x1` と `y1` は `fib` の異なる反復に由来する別々の値を保持します。SSA 形式にはコピーがありませんが、レジスタ割り当て後の形式は、元のコードと同様にコピーを必要とします。 + +自己衝突は干渉グラフ構築中に見つかり、彩色フェーズを試す前に分割ラウンドを引き起こします。 + +## 彩色のヒューリスティック + +レジスタの彩色も分割もヒューリスティックが多数あり、その質が最終的な割り当て品質を大きく左右します。グラフ彩色は NP 完全であり、効率的な彩色アルゴリズムはありません。いずれにせよ、多くのプログラムは分割しなければ彩色できません。 + +### バイアス付き彩色 + +バイアス付き彩色は、Split を除去できるように「よりよい色を選ぶ」、あるいは「色の選択に偏りを付ける」ヒューリスティックです。Split は1つの生存区間を2つに分けますが、必要のない分割が挿入されることもあります。つまり、すでに過剰な分割が起きています。片側の区間が彩色済みで、もう片側も同じ色にできれば、その分割は除去できます。どちらも未彩色でも、片側が再帰的に彩色済み区間に接続されていれば、分割の連鎖がすべて同じ色になって除去されることを期待して、色に偏りを付けられます。 + +彩色処理が逆順に戻り、区間の色を選ぶとき、多くのレジスタ選択肢があることがよくあります。まず任意に、番号が最小のレジスタを選び、それからよりよい色を探します。バイアス付き彩色は代表的な定義を先に調べ（1つしかなければその唯一定義）、次に代表的な使用を調べます。分割の「反対側」が彩色済みかを確認し、そうであり、その色を使えれば採用します。分割があっても未彩色なら、その反対側で再帰的に繰り返します。2アドレス演算のもう1つの入力や、Phi ノードの入力の1つについても行います。 + +どの場合も、現在利用でき、将来この Split の反対側にも選べるかもしれない有効な色を選ぶのが目標です。それによって両側が同じ色になり、分割を除去できます。 + +### 危険な区間の選択 + +ここでは、大きなクリークを作る複数の *生存区間* から1つを選ばざるを得ません。相互の隣接ノードが多すぎて、どれも色を保証されません。ここには相反する要求があります。 + +「面積」が大きく、つまりプログラムの広い範囲を覆い、スピルの「コスト」が低い、つまり定義と使用が少なく、ループ外にある区間を選べば、大きな効果があります。プログラムの広い範囲でレジスタが空き、ほかの場所で彩色が成功できます。通常の ABI の callee-save レジスタは理想的です。入口で定義し出口でだけ使うため、プログラム全体を覆います。スピルも入口と出口で1回ずつ分割するだけです。このような区間のスピルは、基本的に古典的な関数のプロローグ／エピローグ列を構築します。ただし、この割り当て器は、たとえば高速経路の出口より外側でスピルすることも許されます。 + +``` + // No registers saved if the initial RDI is null + test rdi + jne BIG_AND_SLOW + xor rax,rax + ret // Fast path exit: null argument means null result +BIG_AND_SLOW: + add rsp,#12 + mov [rsp+0],rbx // begin spilling callee-save registers + mov [rsp+4],r12 // + // lots of code needing callee-save registers +``` + +もう一方の要求は、偶然によって彩色できそうな区間を選ぶことです。「ほとんど彩色可能」、たとえば利用可能なレジスタ／色より隣接ノードが1つだけ多い区間なら、偶然やバイアス付き彩色によって隣接ノードのいくつかが同じ色を使い、色が空いて、この危険な区間も結局彩色できるかもしれません。 + +## 分割 + +ここでは彩色に失敗したので、分割が必要です。特定の区間が彩色できず、分割方法を決めなければなりません。ここにも相反する要求があります。分割が多すぎると割り当てが悪くなり、少なすぎると進捗しないバグになり、任意の上限を超えるほど多くの分割ラウンドとして現れます。 + +まずスピルをソートして決定的にします。そうしないと HashMap の巡回順になります。それから各スピル対象の区間を順に調べ、分割戦略を決めます。 + +### 自己衝突の分割 + +自己衝突区間は「干渉グラフ構築」段階で発見します。この場合、自己衝突がある状態での彩色には意味がないので、彩色を試さず直接分割へ進みます。IFG 構築中に、この区間の衝突する定義の部分集合を収集しました。それらの定義位置を巡回し、スピルを挿入します。 + +- Phi のスロット #1 の前（ループ入口の Phi をループ本体から切り離す）と、Phi の後。 +- 2アドレス命令の前。演算の前後で区間を分断します。 +- 生存区間を延長する使用の前。 + +この分割集合はかなり積極的ですが、列挙した各位置で分割を必要とするテストを第20章に含めています。自己衝突がある間は彩色を試すことさえできないため、素早く区間を切り分けることが重要です。過剰分割になりがちなので、割り当て器はバイアス付き彩色と最終コピー整理に頼って余分なものを除去します。保守的な併合は後の章で導入します。 + +### ハード衝突の分割 + +直接の定義／使用の衝突（たとえば `rdi` で定義され、`rax` で使われる）は「生存区間構築」走査で発見します。「干渉グラフ構築」走査でも発見できます。たとえば、`rdi` で入る引数が後で使われるものの、`Call` に破壊される場合です。 + +単一定義と単一使用の単純なハード衝突では、正確な定義と使用を生存区間自身に保持しています。定義の後と使用の前で1回ずつ、レジスタが制限された側にだけ分割を行います。 + +より複雑な場合は、容量不足のスピル／ループ入れ子の手法を使います。複製可能な値は使用の近くで再生成できますが、その複製の出力レジスタクラスが使用を満たせる場合だけです。そうでなければ移動が必要です。固定レジスタの定数に柔軟な使用がある場合も、使用で分割しなければなりません。定義で何もしないと、同じハード衝突を永遠に繰り返します。 + +よく使われる定数（たとえば0）は、異なるレジスタを要求する多くの使用を持ちます。使用をレジスタクラスごとにまとめれば移動を減らせますが、このヒューリスティックは後の章まで延期します。 + +### ループの入れ子に沿った分割 + +ここでは通常、容量不足のスピルが起きています。単にもっとレジスタが必要です。`Call` が一時レジスタをすべて破壊し、値を呼び出しの先へ運ぶ必要があるときに起きやすいですが、大きな関数で多くのことが同時に起きる場合にも発生します。 + +ヒューリスティックは、頻繁に実行されるループ本体がスピルしないよう、利用可能レジスタを残すためにループの *周囲* で分割します。分割ラウンドが進むにつれ、区間をより深い入れ子へ分割します。最後には、最内周ループであっても各定義の後と各使用の前で分割します。 + +まず、すべての定義と使用の最小・最大ループ深さを求めます。それらが異なれば最外周ループの *周囲*、すなわち境界で分割し、外側からの制約を持たない内側の区間はそのまま保持します。それでも彩色できなければ、次のラウンドでは最外周ループが1段内側へ移り、次の内側の入れ子の周囲で分割します。最内周ループ内で分割するまで、この処理を繰り返します。 + +### 補助関数 + +RA は、比較的自己完結した一連の補助関数を使います。 + +- **findAllLRG**: 区間のすべての定義と使用を、O(N) ではなく O(|LRG|) 時間で見つけます。 +- **insertBefore** と **insertAfter**: 使用の前か定義の後に分割を挿入します。基本ブロック内の正しい順序に置く処理と、すべての辺の保守を含みます。 +- **makeSplit**: 分割を作ります。複製可能な定数を複製するか、`Machine` に移植先固有の `SplitNode` を要求します。 +- **ldepth**: `long` に詰めた最小・最大ループ深さを受け取り、指定ノード `n` に対する深さ範囲を拡張します。定義や使用がループ「内」にあるかを判定し、ループ周囲の分割に使います。 + +## 割り当て後 + +彩色成功後、両側が同じレジスタの分割を取り除きます。分割を素早く走査し、レジスタを確認して不要なものを除去します。残ったものは割り当ての「採点」用に追跡します。また、分割の後の分割の一部を迂回し、冗長なコピーを除去できることもあります。 + +レジスタは `RegAlloc` オブジェクトの `alloc.regnum( Node n )` から引き続き利用でき、次の命令エンコーディング走査で使います。 + +## RegAlloc の改良: 正しさと測定された基準値 + +この章は小さな割り当て器から始まります。ハード衝突は実際に断ち切らなければなりません。同じブロックに別のコピーがあるだけで分割を省略したり、衝突を復活させるような除去をしたりしてはいけません。ループの後退辺も、特に Phi が並列代入を表す場合には同じ注意が必要です。出力値のない命令にもレジスタ破壊は適用されます。最後に、冗長なコピーの除去には、間にある定義やレジスタ破壊を探す後ろ向き走査が必要です。これらはスピル品質とは独立した、正しさの規則です。 + +分割前に失敗した区間をソートし、同一性マップの順序の変化が割り当てを決めないようにします。割り当て器には null に安全な分割表示と、任意の関数内辺の診断もあります。テストはレジスタマスク、2アドレスのオペランド、Phi のレジスタ一致を確認します。小さなマシングラフが、最適化器の選択とは独立にハード衝突を検証します。ネイティブ実行は、第21章のエンコーディングとともに導入します。 + +### テスト全体で合計したスピル数 + +`make spill-stats` を実行すると、テストを実行し、各コンパイルの数、CPU/ABI ごとの小計、以下の合計を表示します。アサーションは有効なままで、テストが失敗すればコマンドも失敗します。最適化器の既定シードは123です。 + +第20章のプログラム群は `Chapter20Test` の11のソース例すべてと、`BrainFuckTest.testBrainfuck`、`MergeSortTest.testMergeSort` を、x86-64、RISC-V、ARM の SystemV でコンパイルしたものです。スピル0のケースを含む13プログラム、39コンパイルです。人工的な割り当て器の回帰グラフは正しさの確認であり、追加のプログラムベンチマークではありません。 + +| プログラムテスト群 | 割り当て器の章 | コンパイル数 | 分割による移動 | ループ重み付き移動 | +|---|---:|---:|---:|---:| +| 第20章 | 20 | 39 | 234 | 360 | + +`_spills` はレジスタ間コピーも含む、残存した分割移動を数えます。スタックへのストアだけではありません。`_spillScaled` は各移動を `8^loopDepth` で重み付けします。これは粗いコスト推定で、測定された実行頻度ではありません。重み付き小計は x86-64 が161、RISC-V が100、ARM が99です。 + +### 測定についてのコメント + +正しさの修正前、この群は235移動／354重み付き移動でした。遅延メモリ導入前の修正済み基準値は、両方が3増えました。そのうち2移動は、最終的な x86 ストアマスク制限のバックポートによるものです。整数のバイト／short ストアは XMM レジスタを消費できません。これは正しさのためのコストで、品質の向上ではありません。固定隣接ノードへの色バイアスの修正は、この群の数を変えません。 + +遅延メモリと選択済み読み取りの順序付けにより、同じ39コンパイルは導入前の238／357から、234移動／360重み付き移動になりました。すべての対象でレジスタの合法性が確認でき、割り当て器のヒューリスティックは変更していません。変化したプログラムは次のとおりです。 + +| プログラム | 対象 | 移動の前／後 | 重み付きの前／後 | +|---|---|---:|---:| +| 配列アクセス（`testAlloc2`） | x86-64 | 1 / 2 | 1 / 2 | +| 配列の累積和（`testArray1`） | x86-64 | 5 / 6 | 5 / 13 | +| 文字列ハッシュ | x86-64 | 7 / 5 | 21 / 19 | +| 文字列ハッシュ | RISC-V | 4 / 3 | 4 / 3 | +| 文字列ハッシュ | ARM | 5 / 3 | 5 / 3 | +| マージソート | ARM | 37 / 36 | 37 / 36 | + +累積和の追加のループ移動は、選択済み読み取りを、それを破壊する書き込みより前にスケジュールすることから生じます。その順序を省く診断ビルドでは5／5に戻りますが、有効な代替スケジュールではありません。これはフロントエンドとスケジューリングのグラフの変化であり、割り当て器のヒューリスティックの比較ではありません。新しいメモリ割り当ての回帰テストは合法性を確認しますが、この測定群に項目を追加しません。 + +後の章では、品質向上の手法を1つずつ追加し、このような表で締めくくります。第21章では自身の割り当て器で第20章と第21章のプログラム群を測定し、第25章では第20〜25章の群の行を持ちます。章をまたいで行を比較するときは、プログラム／対象の構成とシードを固定し、最適化器や命令選択の変化を割り当ての変化から分けてください。全体が改善するなら局所的な悪化に価値がある場合もありますが、割り当ての失敗や違法なレジスタ割り当てに価値はありません。 diff --git a/docs/chapter20/README.md b/docs/chapter20/README.md new file mode 100644 index 00000000..543bbd84 --- /dev/null +++ b/docs/chapter20/README.md @@ -0,0 +1,529 @@ +# Chapter 20: Graph Coloring Register Allocation + +English | [日本語](README.ja.md) + +[Previous: Chapter 19](../chapter19/README.md) | +[Next: Chapter 21](../chapter21/README.md) + +The grammar is unchanged from [Chapter 18](../chapter18/18-grammar.md). + +## Some Reading Material + +This is a Briggs-Chaitin-Click allocator, and is very similar to the one used +in HotSpot's C2 allocator for the past 25 years with great success. + +Wikipedia has a nice overview of register allocation in general: https://en.wikipedia.org/wiki/Register_allocation + +Chaitin's original: https://en.wikipedia.org/wiki/Register_allocation#CITEREFChaitin1982 + +Briggs additions: https://dl.acm.org/doi/10.1145/177492.177575 + +Nice lecture slides pdf of Briggs/Chaitin: https://aktemur.github.io/cs544/lectures/chapter%2013%20registerAllocation.pdf + +There are several other useful links that can be found by searching for Briggs +or Chaitin in combination. Basically there was a spate of register allocation +improvements in this era that made it into many high-end mainstream compilers. + +I've included a very old unpublished paper on speeding up graph coloring +allocators: [Interference Graph Trimming](ifg_trim.pdf). + + +## Meta-Issues / Code-Dev Issues of Instruction Selection, Register Allocation and Encodings + +The output of Register Allocation - an allocation of registers to ops - is +difficult to test in bulk without an execution strategy. We won't have an +execution strategy until all three of Instruction Selection, Register Allocation +and Encodings are done. Hence in and around the completion of Encoding we +expect to find lots of bugs in Instruction Selection and Register Allocation. +We certainly hand-inspect the output and fix obvious problems, but still lots of +bugs linger until we can actually run the code. + +This means that other chapters have updates and bug-fixes to the work being +described here. + +Specific to the register allocator, we will be gradually adding improvements to +it, chapter by chapter for quite a few chapters. Register allocators generally +end with a large number of heuristics which we will add slowly. + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter20) 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-chapter19...linear-chapter20) it to the previous chapter. + + +## The Basic Theory + +The reading material includes several explanations of the basic concepts, but +at the risk of being redundant I'll present a short version again here. + +I assume you (the reader) know *why* register allocation is required: machine +registers are a high value finite resource, and as with all finite resources +they need to be allocated well. + +Graph Coloring is one such allocation method; machine registers are treated as +colors; a *live range interference graph* is built, with each *live range* +requiring its own register/color. Coloring the graph ensures every live range +gets a unique register, specifically when it overlaps or *interferes* with +another live range. + +A successful coloring ends the allocation and after some bookkeeping the +program is ready for e.g. code emission. A failed coloring requires spilling +or splitting conflicting live ranges; in this allocator we will be doing live +range *splitting*. Splitting live ranges makes them more colorable; they +become shorter with fewer interfering other live ranges. Generally large +functions might require a few rounds of splitting before becoming colorable. +Since the problem is NP-complete there are no guarantees here, the final +allocation quality becomes heavily dependent on splitting and coloring +heuristics. + +Hence, much of the "high theory" will be used to drive the core coloring +algorithm, but much of the actual success will depend on a large collection +of heuristics. + +### Coloring Rounds + +Coloring proceeds in rounds until we get a coloring: + +- Build the Live Ranges; live ranges require the same register for all + instructions in the live range. Phi functions will force unrelated def/use + edges to become part of the same live range and this can drive large + interconnected live ranges with a lot of conflicts. Some hardware ops + require the same register for both inputs and outputs (X86 is notorious here) + which also makes fewer larger live ranges. We'll be using the disjoint + Union-Find algorithm to rapidly build up live ranges in one forward pass over + the program. + +- Build the Interference Graph: every live range which is alive at the same time + as any other, now *interferes* or conflicts. This is built using a LIVE-ness + pass, which is a backwards pass over the CFG, and can require more than one + pass according to loop nesting depth. The data structure here is generally a + 2-D bitset, triangulated to cut its size in half. As part of LIVE, we'll + also have a set of reaching defs per-block. + +- Color the interference graph. Nodes (live ranges) in the graph which are + strictly low degree (more available registers than neighbors) are guaranteed + to get a color. These can be removed from the graph - since they will + guaranteed get a register (color) because they have so few conflicting + neighbors. Removing these trivial nodes makes more nodes go trivial, and + this process repeats until either we run out (and are guaranteed a coloring) + or we find a high-degree clique: a set of mutually interfering live ranges + where none of them are guaranteed a color. In this case we pull an "at risk" + live range out; this one might not color. Once the graph is emptied, we + reverse and re-insert the live ranges, coloring as we go. All the trivial + live ranges will color; the at-risk ones may or may not. + +- If every live range gets a color, then Register Allocation is done. If not, + we enter a round of splitting. Live ranges which did not color are now split + via a series of heuristics into lots of small live ranges. Splitting has a + tension: too much and you got a lot of spills (and a generally poor + allocation). Too little, and you remain uncolorable - and do not make + progress towards an allocation. Once we're done splitting, we start a new + round of coloring (Building the Live Ranges, then the Interference Graph, + then Coloring). + + +## Registers and Register Masks + +Registers are the thing that Register Allocation is all about! They are +represented as a small dense integer, starting up from 0, and the numbering +generally follows from the hardware encodings. So for an X86_64, RAX will be +register 0, RCX register 1 and so on up to the 16 GPRs. The XMM register numbers start at +16 and go through 31. Register numbers must be unique; this is how the register +allocator tracks them. + +#### Why a RegMask class and not a simple `long`? + +A collection of registers live in a Register Mask. For smaller and simpler +machines it suffices to make such masks an i64 or i128 (64 or 128 bit +integers), and this presentation is by far the better way to go... if all +register allocations can fit in this bit limitation. The allocator will need +bits for stack-based parameters and for splits which cannot get a register. +For a 32-register machine like the X86, add 1 for flags - gives 33 registers. +Using a Java `long` has 64 bits, leaving 31 for spills and stack passing. This +is adequate for nearly all allocations; only the largest allocations will run +this out. However, if we move to a chip with 64 registers we'll immediately +run out, and need at least a 128 bit mask. Since you cannot *return* a 128 +bit value directly in Java, Simple will pick up a `RegMask` class object. + +#### Stack Slots + +One of the Click extensions is this notion of treating "stack slots" as Just +Another Register. They get colored like other registers, which in turn leads +to very efficient use of the stack; C2 is known for having very small stack +frames. Another benefit is callee save registers will get split preferentially +(they have very long lifetime and only one def on entry and one use on +exit)... which the splits then end up coloring to the stack, building the call +prolog and epilog naturally. This allocator will not otherwise dedicate any +effort to stack frame management; it will "fall out in the wash". + +Many of the register masks are immutable; e.g. allowed registers for particular +opcodes, or describing registers for calling conventions. Other masks +represent mutable bitsets with the allocator routinely masking off bits when +accumulating a set of constraints. To help keep these uses apart, the +`RegMask` class includes mutable and immutable variants. + +#### Memory + +Memory edges exist to enforce ordering, but do not get any registers. +The allocator basically ignores them. + + +### Callee/Caller Save Registers + +In this allocator, callee- and caller-save registers get almost no special +treatment and no special prolog nor epilog is built to save and restore them. +At the start of the allocator, SoN graph edges are added between each `Return` +and a `CalleeSave` from each `Fun`. These edges are given register masks +pinning them to the callee-save set as defined by the normal ABI. + +Callee-save live ranges thus have a single def (a `CalleeSave` at function +start) and a single use (the `Return`), are cheap to spill and free a register +over a large area - they make ideal spill candidates. When the allocator needs +to spill something to get some more registers, these will be the first to +spill. A prolog and epilog will get built as a consequence of the normal live +range splitting process. + +`Calls` kill the caller-save registers (just the inverted callee-save mask), +and this is computed during the normal interference graph building process just +like any other operation that kills registers. Killing a bunch of registers at +a call typically removes all the free registers from whatever is currently +alive - and will thus force spilling... which will quickly end up spilling +callee-save registers as ideal candidates. + + +## Live Ranges + +A live range is a set of nodes and edges which must get the same register. +Live ranges form an interconnected web with almost no limits on their shape. +Live ranges also gather the set of register constraints from all their parts. + +Live ranges are held in `LRG` class instances. Most of the fields in this +class are for spill heuristics, but there are a few key ones that define what a +LRG is. `RegAlloc` has several functions dealing with LRGs, including a lookup +table from Nodes i.e., a mapping from `Node` to `LRG` (which is very similar to +having a dedicated LRG field in each Node... except that LRGs are only used +during RegAlloc and the field would be dead weight otherwise). + +LRGs have a unique dense integer `_lrg` number which names the LRG. New `_lrg` +numbers come from the `RegAlloc._lrg_num` counter. LRGs can be unioned +together - +[this is the Union-Find algorithm](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) +- and when this happens the lower numbered `_lrg` wins. Unioning only happens +during `BuildLRG` and happens because either a `Phi` is forcing all its inputs +and outputs into the same register, or because of a 2-address instruction. +LRGs have matching `union` and `find` calls, and a set `_leader` field. + +Post-allocation the `LRG._reg` field holds the chosen register. During +allocation the `LRG._mask` field holds the set of available registers, +typically all the defaults, minus various conflicts. + +The `LRG._adj` holds a list of adjacent neighbors as part of the larger +Interference Graph, and is only used during the Coloring phase. +[See more about graphs here.](https://en.wikipedia.org/wiki/Graph_(abstract_data_type)) +This is an "adjacency list" form of a Graph description, and is built from the +IFG's 2-D collection of bits (itself a 1-D list of `BitSet`s). Graph coloring +register allocation is one of the few places where changing the layout of a +data structure mid-algorithm pays out. + +The rest of the fields are dedicated to various spilling heuristics: + +- `_machDef` `_machUse` `_uidx` - A sample def and use. +- `_splitDef` `_splitUse` - Sample splits involved with this LRG; biased + coloring attempts to align register choices to remove these. +- `_selfConflicts` - A partial set of *self-conflicting* nodes. These are + detected during the Interference Graph build phase, and require aggressive + splitting. +- `_1regDefCnt` `_1regUseCnt` - Count of defs and uses which are pinned to a + single register. These typically require a hard-split just before (use) or + after (def) to free up the register choices. + + +## Live Ranges and Conflicts + +If the live range `_mask` field goes empty, you might have a *hard conflict* or +have gotten *killed*. Live ranges can self-interfere, making a +*self-conflict*. During coloring you might discover an uncolorable clique of +interfering live ranges, leading to a *capacity spill*. This leads to a set of +levels of conflicts within a live range (and different heuristics for handling +them). + +### Hard-Conflicts + +A live range can have a *hard conflict*: conflicting register requirements, +leading to no valid register choices. The obvious case is an incoming +parameter fixed in e.g. `rdx` but also required as an exit value in `rax`. You +can't pick both registers at once, so a split is required. During the build +live ranges phase, every register constraint from every def and use are AND'd +together; the `RegMask` might lose all valid registers, or remain with just a +handful of register choices. + +Hard-conflicts are usually found while building live ranges, and will trigger a +round of splitting before building the interference graph or coloring. They +can also be found during interference graph building, generally caused by a +1-register kill. + +### Avoiding interferences + +One of the Click extensions to the Briggs-Chaitin allocator is to take +advantage of register constraints to lower the interference graph degree (which +otherwise becomes an O(n^2) edge collection). If a live range LR1 is reduced +to a single register (such as a call argument requiring `rdx`) and would +otherwise conflict with another live range LR2 which has more choices - we +remove `rdx` from the LR2's choices. Without having `rdx`, LR1 and LR2 have no +registers in common - and hence do not conflict. We just don't add the +interference graph edge between them. Call argument restrictions are very +common and this kind of edge-removal can dramatically shrink the O(n^2) edge +collection - and hence speedup allocation by a large constant factor. + +### Self-Conflicts + +A live-range can *self-conflict*: be alive twice with 2 different values but +require the same register. This live range *must* split and thus picks up a +copy from the split. This happens with loop-carried dependencies as seen in +e.g. a simple `fib` program: + +```java + int x=1, y=1; + while( true ) { + tmp = x + y; + y = x; + x = tmp; + }; + +``` + +In SoN SSA form: +```java + int x0 = 1, y0 = 1; + while( true ) { + x1 = phi(x0,x2); + y1 = phi(y0,x1); + x2 = x1 + y1; + } +``` + +The variables `x0,x1,x2,y0,y1` all form part of the same live range, since they +are all joined by `Phis`. However, `x1` and `y1` hold different values from +different iterations of `fib`. The SSA form does not have a copy, but the +register-allocated form - just like the original code - DOES require a copy. + +Self-conflicts are found during building the interference graph, and will +trigger a round of splits before attempting the coloring phase. + + +## Coloring Heuristics + +Both register coloring and register splitting are full of heuristics, and the +quality of these heuristics goes a long way to deciding the quality of the +final allocation. Graph coloring is NP-complete; there is no efficient +algorithm for coloring and many programs are simply not colorable without +splitting in any case. + + +### Biased Coloring + +Biased coloring is a heuristic that attempts to "pick a better color" or "bias +the color choice", such that a Split is removed. A Split splits one live range +into two; sometimes some are inserted that are not required (i.e., over- +splitting has already happened). If one side (live range) of a split is +already colored and we can color the other side (live range) the same color - +then this split can be removed. If neither side is colored, but one or the +other side is recursively connected to a colored live range, we can still bias +the color in the hopes that a chain of splits will all get the same color and +thus all get removed. + +When the coloring process is reversing, and colors are being picked for live +ranges, we often have many register choices. A first choice is made +arbitrarily (lowest numbered register), and then we go looking for a better +color. Biased coloring inspects first a sample def (if there is only one, then +the One Def is inspected), and then a sample use. Inspection looks to see if +"the other side" of a split is already colored; if so, and that color is +available it is chosen. If there is a split, but it is not colored - we +recursively repeat the process on that split's other side. This is also done +for the other input of two-address ops and one of a Phi node inputs. + +In all cases, the goal is to pick a valid available color - that might also +eventually be pick-able for this Split's other side - and lead to this split +having the same color for both sides, and then being removed. + + +### Pick Risky + +Here we are forced to pick one of several *live ranges* that form a large +clique: they have too many mutual neighbors so that no one of them is +guaranteed a color. There is a conflicting tension here: + +Picking a live range with a large "area" (i.e. covering much of the program), +and low "cost" to spill (i.e. fewer defs and uses, and outside of loops) will +give a large win. A register will become free over a large part of the program +and allow coloring to succeed elsewhere. The normal ABI callee-save registers +are ideal in this case, defined on entry and used only on exit they cover the +entire program. Also, spilling means only a single split on entry and another +at exit. Spilling such live ranges basically builds a classic function +prolog/epilog sequence. Here though, the allocator is allowed to e.g. spill +outside a fast-path exit. + +``` + // No registers saved if the initial RDI is null + test rdi + jne BIG_AND_SLOW + xor rax,rax + ret // Fast path exit: null argument means null result +BIG_AND_SLOW: + add rsp,#12 + mov [rsp+0],rbx // begin spilling callee-save registers + mov [rsp+4],r12 // + // lots of code needing callee-save registers +``` + +The other side of the tension is to pick live ranges that are likely to color +more by chance. If a live range is "very nearly colorable" - say only one more +neighbor than available registers/colors then by chance (and Biased Coloring) +some neighbors might use the same color... freeing up a color and allowing this +risky live range to color after all. + + +## Splitting + +Here we failed to get a coloring - and need to split. Some specific live +ranges did not color and we will need to decide how to split. Again there are +tensions here: too much splitting leads to a bad allocation, too little leads to +no-progress bugs (manifested as too many rounds of splitting past some +arbitrary cutoff). + +We start by sorting the spills to be deterministic (else they are sorted by +HashMap visitation order), then looking at each spilling live range in turn +and deciding on a splitting strategy. + + +### Split Self Conflict + +Self-conflict live ranges are discovered during the "Build the Interference +Graph" stage. If this happens we don't attempt a coloring (it's nonsensical +with self conflicts), but go straight to splitting. During the IFG building we +gathered a subset of the conflicting definitions for this live range. Now +we visit all those definition points and insert spills: + +- Before slot #1 on a Phi (which breaks loop-entry Phis from the loop-body) and + also after the Phi. +- Before a two-address instruction, breaking the live range before the op from + afterwards. +- Before any use that extends a live range. + +This set of splits is fairly aggressive... but test cases requiring a split in +each of the listed locations are included in Chapter 20's test cases. We +cannot even attempt a color while we have self conflicts, so it's important to +break up these live ranges quickly. This tends to over-split and the allocator +leans on Biased Coloring and the final copy cleanup to remove some of the +extras. Conservative coalescing will be introduced in a later chapter. + + +### Split Hard Conflict + +Hard conflicts are discovered during the "Build the Live Ranges" pass for +direct def/use conflicts (e.g. defined in `rdi` and used in `rax`). They also +can be discovered during the "Build the Interference Graph" pass (e.g. incoming +argument in `rdi` used later in the program and killed by a `Call`). + +For simple hard-conflicts (a single def and single use), we have the exact def +and use kept in the Live Range itself. We split once after the def and once +before the use (and only on sides with restricted registers). + +For more complex cases we use the capacity spilling/loop-nest technique. +Cloneable values can be recreated near their uses, but only when the clone's +output register class can satisfy that use. Otherwise we need a move. A fixed +register constant with flexible uses must also split at its uses; doing nothing +at its definition would repeat the same hard conflict forever. + +Popular constants (e.g. 0) often have many uses requiring different registers. +Grouping these uses into register classes can save moves, but we defer that +heuristic to a later chapter. + + +### Split By Loop Nest + +Here we typically see capacity spills: we just need more registers. This +easily happens when a `Call` crushes all the temporary registers and we need to +carry some values past the call - but it can also happen any time we have a +larger function with lots of things going on at once. + +The heuristic here is to split *around* loops, attempting to keep some free +registers available so the hot loop body does not spill. Live ranges are split +into successively deeper loop nests in progressive rounds of splitting, and in +the final case will split once after each def and before each use, even in the +innermost loop. + +The heuristic starts by discovering the min and max loop depth for all defs and +uses. If these vary, we will split *around* the outermost loop, putting in +splits at the loop border and keeping an inner untouched live range that has no +constraints from outside. If this fails to color, on the next round of +splitting the outermost loop will have moved in one layer, and we will be +splitting around the next inner loop nest. This process repeats until we end +up splitting in the inner-most loops. + + +### Helpers + +RA uses a series of helper functions, each is fairly self-contained. + +- **findAllLRG** - find all the defs and uses of a live range in time O(|LRG|) + instead of time O(N). +- **insertBefore** and **insertAfter** - insert a split either before a use or + after a def. Includes the work to put the split in its proper ordering in + a Basic Block and do all edge maintenance. +- **makeSplit** - Make a split (either clone a clonable constant, or ask the + `Machine` for a port-specific `SplitNode`). +- **ldepth** - Given a min&max loop depth (compacted in a `long`), expand the + loop depth range for a given node `n`. Used to decide when a def or use is + "inside" a loop, which in turn is used to split around loops. + + +## Post Allocation + +After a successful coloring, we want to pull out any same-same register splits. +A quick pass over the splits and after checking registers, we pull out the +useless splits (and track the rest for "scoring" our allocation). We'll also +bypass some split-after-splits, which can remove some redundant copying. + +The registers remain available in the `RegAlloc` object via `alloc.regnum( Node n )` +and will be used by a following instruction encoding pass. + + +## RegAlloc improvements: correctness and a measured baseline + +This chapter starts with a small allocator. Hard conflicts must actually be +broken: a split cannot be skipped just because another copy is in the same +block, nor folded away when that would restore the conflict. Loop backedges +need the same care, especially when Phis represent parallel assignments. +Register kills apply even to instructions with no output value. Finally, +removing a redundant copy requires a backward scan for intervening definitions +and register kills. These are correctness rules, independent of spill quality. + +We sort failed live ranges before splitting so changes in identity-map order do +not decide the allocation. The allocator also has null-safe split printing and +an optional function-local-edge diagnostic. The tests check register masks, +two-address operands, and Phi register agreement; tiny machine graphs exercise +hard conflicts independently of optimizer choices. Native execution comes with +encoding in Chapter 21. + +Rows are fixed test cohorts; columns are compiler chapters. Each cell gives +**Ops / RA / X**: executed ARM+RISC-V instructions, the subset emitted for +allocator copies/rematerializations, and x86's loop-weighted split-move estimate. +**Cases D / X** counts measured dynamic program/target cases and x86 compilations; +membership and inputs stay fixed across columns. Native-library work is excluded. +Chapter 20 has no encoder, hence no dynamic counts. Lower is better within each +metric; see the [measurement details](../regalloc-spills.md) for coverage. + +<!-- spill-matrix:start --> +| Test cohort | Cases D / X | Ch 20: Ops / RA / X | +|---|---:|---:| +| Ch 20 | 22 / 13 | — / — / 161 | +<!-- spill-matrix:end --> + +These Windows measurements use optimizer seed 123 for cohorts 20-24 and include +x86-64 SystemV/Win64 and ARM/RISC-V SystemV as applicable. Run `make spill-stats` +here for this compiler, or at the repository root to rebuild the full matrix +and check cohort membership. See the [complete comparison](../regalloc-spills.md) +for measurement details and reproduction commands. + +Cohort 20 contains 11 Chapter20Test programs plus BrainFuck and MergeSort, +each on three SystemV targets: 39 compilations. Synthetic allocator graphs +check correctness separately. This is the baseline; later chapters extend the +columns while keeping these programs and targets fixed. diff --git a/docs/chapter20/font-awesome-4.7.0.zip b/docs/chapter20/font-awesome-4.7.0.zip Binary files differnew file mode 100644 index 00000000..b6bdb4bd --- /dev/null +++ b/docs/chapter20/font-awesome-4.7.0.zip diff --git a/docs/chapter20/ifg_trim.pdf b/docs/chapter20/ifg_trim.pdf Binary files differnew file mode 100644 index 00000000..d952fd4f --- /dev/null +++ b/docs/chapter20/ifg_trim.pdf diff --git a/docs/chapter20/lattice.gv b/docs/chapter20/lattice.gv new file mode 100644 index 00000000..8661082d --- /dev/null +++ b/docs/chapter20/lattice.gv @@ -0,0 +1,203 @@ +digraph Lattice { + compound = true; + // Define nodes + splines=false; + node [shape=circle, style=filled]; + nodesep=0.2; + ranksep=0.2; + + TOP [label=<<B>⊤</B >>, fillcolor=black, fontcolor=white]; + BOT [label=<<B>⊥</B>>, fillcolor=black, fontcolor=white]; + + // ---------------------- + // Control + XCTRL [label=<<B>⊤</B >:ctrl>, fillcolor=yellow, shape=oval]; + CTRL [label=<<B>⊥</B>:ctrl>, fillcolor=yellow, shape=oval]; + + TOP -> XCTRL; + XCTRL -> CTRL; + CTRL -> BOT; + + // ---------------------- + // Integers + INT_TOP [label=<<B>⊤</B >:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<<B>⊥</B>:int>, fillcolor=lightblue, shape=oval]; + + INT_HI [label="[min>max]" , fillcolor=lightblue, shape=oval]; + INT_XBOOL [label="[1...0]", fillcolor=lightblue, shape=oval]; + INT_CON [label="constants", fillcolor=lightblue, shape=oval]; + INT_CON0 [label="0", fillcolor=lightblue]; + INT_CON1 [label="1", fillcolor=lightblue]; + INT_BOOL [label="[0...1]", fillcolor=lightblue,shape=oval]; + INT_LO [label="[min<max]" , fillcolor=lightblue, shape=oval]; + + TOP -> INT_TOP; + INT_TOP -> INT_HI; + INT_HI -> INT_XBOOL; + INT_XBOOL -> INT_CON0; + INT_XBOOL -> INT_CON1; + INT_HI -> INT_CON; + INT_CON0 -> INT_BOOL; + INT_CON1 -> INT_BOOL; + INT_BOOL -> INT_LO; + INT_CON -> INT_LO; + INT_LO -> INT_BOT; + INT_BOT -> BOT; + + INT_CON0 -> INT_CON1 -> INT_CON [style=invis]; + + // ---------------------- + // Floats + FLT_TOP [label=<<B>⊤</B >:flt>, fillcolor=aqua, shape=oval]; + FLT_BOT [label=<<B>⊥</B>:flt>, fillcolor=aqua, shape=oval]; + + FLT_CON64 [label="64b consts\n[excludes\n32b consts]" , fillcolor=aqua, shape=oval]; + FLT_CON32 [label="32b consts", fillcolor=aqua, shape=oval]; + FLT_CONPI [label="3.14159...", fillcolor=aqua, shape=oval]; + FLT_X32 [label="~f32", fillcolor=aqua]; + FLT_CON0 [label="0." , fillcolor=aqua]; + FLT_32 [label="f32" , fillcolor=aqua]; + + TOP -> FLT_TOP; + FLT_TOP -> FLT_CON64 + FLT_TOP -> FLT_CONPI + FLT_CON64 -> FLT_BOT + FLT_CONPI -> FLT_BOT + + FLT_TOP -> FLT_X32; + FLT_X32 -> FLT_CON0; + FLT_X32 -> FLT_CON32; + FLT_CON0 -> FLT_32; + FLT_CON32 -> FLT_32; + FLT_32 -> FLT_BOT + + FLT_BOT -> BOT; + + FLT_CON0 -> FLT_CON32 -> FLT_CONPI -> FLT_CON64 [style=invis]; + + + // ---------------------- + // Pointers, just a boolean nil/not and a struct + PTR [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="green"><FONT color="white">*ptr</FONT></TD></TR> + <TR><TD BGCOLOR="lightgreen">struct</TD></TR> + </TABLE> + >]; + PTR0 [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="green"><FONT color="white">*ptr?</FONT></TD></TR> + <TR><TD BGCOLOR="lightgreen">struct</TD></TR> + </TABLE> + >]; + + TOP -> PTR; + PTR -> PTR0; + PTR0 -> BOT; + + // ---------------------- + // Structs + STRUCT_TOP [label=<<B>⊤</B >:struct>, fillcolor=lightgreen, shape=oval]; + STRUCT_BOT [label=<<B>⊥</B>:struct>, fillcolor=lightgreen, shape=oval]; + + STRUCT_S1 [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR> + </TABLE> + >]; + STRUCT_S2 [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR> + <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR> + </TABLE> + >]; + STRUCT_SN [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR> + <TR><TD BGCOLOR="lightgreen">... </TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR> + <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR> + </TABLE> + >]; + + + TOP -> STRUCT_TOP; + STRUCT_TOP -> STRUCT_S1; + STRUCT_TOP -> STRUCT_S2; + STRUCT_TOP -> STRUCT_SN; + STRUCT_S1 -> STRUCT_BOT; + STRUCT_S2 -> STRUCT_BOT; + STRUCT_SN -> STRUCT_BOT; + STRUCT_BOT -> BOT; + + STRUCT_S1 -> STRUCT_S2 -> STRUCT_SN [style=invis]; + + // ---------------------- + // Memory + MEM_TOP [label=<<B>⊤</B >:mem>, fillcolor=blue, fontcolor=white, shape=oval]; + MEM_BOT [label=<<B>⊥</B>:mem>, fillcolor=blue, fontcolor=white, shape=oval]; + MEM_ALIAS1 [label="#1" , fillcolor=blue, fontcolor=white]; + MEM_ALIASDOTS [label="..." , fillcolor=blue, fontcolor=white, shape=oval]; + MEM_ALIASN [label="#n" , fillcolor=blue, fontcolor=white]; + + TOP -> MEM_TOP; + MEM_TOP -> MEM_ALIAS1; + MEM_TOP -> MEM_ALIASDOTS; + MEM_TOP -> MEM_ALIASN; + MEM_ALIAS1 -> MEM_BOT; + MEM_ALIASDOTS -> MEM_BOT; + MEM_ALIASN -> MEM_BOT; + MEM_BOT -> BOT; + + MEM_ALIAS1 -> MEM_ALIASDOTS -> MEM_ALIASN [style=invis]; + + // ---------------------- + // Tuples + + TUPLE_TOP [label=<<B>⊤</B >:tuple>, fillcolor=pink, shape=oval]; + TUPLE_BOT [label=<<B>⊥</B>:tuple>, fillcolor=pink, shape=oval]; + + TUPLE1 [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TH><TD BGCOLOR="pink">Tuple</TD></TH> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + </TABLE> + >]; + TUPLE2 [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TH><TD BGCOLOR="pink">Tuple</TD></TH> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + </TABLE> + >]; + TUPLEN [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TH><TD BGCOLOR="pink">Tuple</TD></TH> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + <TR><TD BGCOLOR="black" ><FONT color="white">...</FONT></TD></TR> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + </TABLE> + >]; + + + TOP -> TUPLE_TOP; + TUPLE_TOP -> TUPLE1; + TUPLE_TOP -> TUPLE2; + TUPLE_TOP -> TUPLEN; + TUPLE1 -> TUPLE_BOT; + TUPLE2 -> TUPLE_BOT; + TUPLEN -> TUPLE_BOT; + TUPLE_BOT -> BOT; + + // ---------------------- + // Additional customization + {rank=same; TOP;} + {rank=same; INT_TOP; FLT_TOP; XCTRL; PTR; STRUCT_TOP; MEM_TOP; TUPLE_TOP} + {rank=same; INT_CON; INT_CON0; INT_CON1; + FLT_CON32; FLT_CON64; FLT_CON0; FLT_CONPI; + STRUCT_S1; STRUCT_S2; STRUCT_SN; + MEM_ALIAS1; MEM_ALIASDOTS; MEM_ALIASN; + TUPLE1; TUPLE2; TUPLEN; + } + {rank=same; INT_BOT; FLT_BOT; CTRL; PTR0; STRUCT_BOT; MEM_BOT; TUPLE_BOT} + {rank=same; BOT;} +} diff --git a/docs/chapter20/lattice.svg b/docs/chapter20/lattice.svg new file mode 100644 index 00000000..030f4826 --- /dev/null +++ b/docs/chapter20/lattice.svg @@ -0,0 +1,691 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+ "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 12.2.0 (20241103.1931)
+ -->
+<!-- Title: Lattice Pages: 1 -->
+<svg width="1330pt" height="584pt"
+ viewBox="0.00 0.00 1329.51 583.54" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 579.54)">
+<title>Lattice</title>
+<polygon fill="white" stroke="none" points="-4,4 -4,-579.54 1325.51,-579.54 1325.51,4 -4,4"/>
+<!-- TOP -->
+<g id="node1" class="node">
+<title>TOP</title>
+<ellipse fill="black" stroke="black" cx="641.51" cy="-554.42" rx="21.12" ry="21.12"/>
+<text text-anchor="start" x="633.63" y="-549.99" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊤</text>
+</g>
+<!-- XCTRL -->
+<g id="node3" class="node">
+<title>XCTRL</title>
+<ellipse fill="yellow" stroke="black" cx="36.51" cy="-492.79" rx="36.51" ry="18"/>
+<text text-anchor="start" x="17.76" y="-488.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="33.51" y="-488.74" font-family="Times New Roman,serif" font-size="14.00">:ctrl</text>
+</g>
+<!-- TOP->XCTRL -->
+<g id="edge1" class="edge">
+<title>TOP->XCTRL</title>
+<path fill="none" stroke="black" d="M620.33,-551.33C533.82,-542.8 206.01,-510.5 83.28,-498.4"/>
+<polygon fill="black" stroke="black" points="83.86,-494.94 73.56,-497.44 83.17,-501.91 83.86,-494.94"/>
+</g>
+<!-- INT_TOP -->
+<g id="node5" class="node">
+<title>INT_TOP</title>
+<ellipse fill="lightblue" stroke="black" cx="316.51" cy="-492.79" rx="33.95" ry="18"/>
+<text text-anchor="start" x="299.63" y="-488.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="315.38" y="-488.74" font-family="Times New Roman,serif" font-size="14.00">:int</text>
+</g>
+<!-- TOP->INT_TOP -->
+<g id="edge4" class="edge">
+<title>TOP->INT_TOP</title>
+<path fill="none" stroke="black" d="M620.68,-549.6C568.33,-539.99 430.36,-514.68 359.64,-501.71"/>
+<polygon fill="black" stroke="black" points="360.44,-498.29 349.97,-499.93 359.18,-505.18 360.44,-498.29"/>
+</g>
+<!-- FLT_TOP -->
+<g id="node14" class="node">
+<title>FLT_TOP</title>
+<ellipse fill="aqua" stroke="black" cx="494.51" cy="-492.79" rx="32.41" ry="18"/>
+<text text-anchor="start" x="478.76" y="-488.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="494.51" y="-488.74" font-family="Times New Roman,serif" font-size="14.00">:flt</text>
+</g>
+<!-- TOP->FLT_TOP -->
+<g id="edge18" class="edge">
+<title>TOP->FLT_TOP</title>
+<path fill="none" stroke="black" d="M621.99,-545.5C598.79,-536.09 559.6,-520.19 530.78,-508.5"/>
+<polygon fill="black" stroke="black" points="532.29,-505.34 521.7,-504.82 529.65,-511.82 532.29,-505.34"/>
+</g>
+<!-- PTR -->
+<g id="node22" class="node">
+<title>PTR</title>
+<polygon fill="none" stroke="none" points="668.51,-519.29 614.51,-519.29 614.51,-466.29 668.51,-466.29 668.51,-519.29"/>
+<polygon fill="green" stroke="none" points="623.51,-492.79 623.51,-515.29 659.51,-515.29 659.51,-492.79 623.51,-492.79"/>
+<polygon fill="none" stroke="black" points="623.51,-492.79 623.51,-515.29 659.51,-515.29 659.51,-492.79 623.51,-492.79"/>
+<text text-anchor="start" x="630.63" y="-498.99" font-family="Times New Roman,serif" font-size="14.00" fill="white">*ptr</text>
+<polygon fill="lightgreen" stroke="none" points="623.51,-470.29 623.51,-492.79 659.51,-492.79 659.51,-470.29 623.51,-470.29"/>
+<polygon fill="none" stroke="black" points="623.51,-470.29 623.51,-492.79 659.51,-492.79 659.51,-470.29 623.51,-470.29"/>
+<text text-anchor="start" x="626.51" y="-476.49" font-family="Times New Roman,serif" font-size="14.00">struct</text>
+</g>
+<!-- TOP->PTR -->
+<g id="edge33" class="edge">
+<title>TOP->PTR</title>
+<path fill="none" stroke="black" d="M641.51,-532.9C641.51,-532.06 641.51,-531.22 641.51,-530.37"/>
+<polygon fill="black" stroke="black" points="645.01,-530.61 641.51,-520.61 638.01,-530.61 645.01,-530.61"/>
+</g>
+<!-- STRUCT_TOP -->
+<g id="node24" class="node">
+<title>STRUCT_TOP</title>
+<ellipse fill="lightgreen" stroke="black" cx="746.51" cy="-492.79" rx="44.7" ry="18"/>
+<text text-anchor="start" x="721.76" y="-488.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="737.51" y="-488.74" font-family="Times New Roman,serif" font-size="14.00">:struct</text>
+</g>
+<!-- TOP->STRUCT_TOP -->
+<g id="edge36" class="edge">
+<title>TOP->STRUCT_TOP</title>
+<path fill="none" stroke="black" d="M659.8,-543.03C674.04,-534.94 694.24,-523.47 711.55,-513.64"/>
+<polygon fill="black" stroke="black" points="713.07,-516.81 720.03,-508.83 709.61,-510.72 713.07,-516.81"/>
+</g>
+<!-- MEM_TOP -->
+<g id="node29" class="node">
+<title>MEM_TOP</title>
+<ellipse fill="blue" stroke="black" cx="998.51" cy="-492.79" rx="43.67" ry="18"/>
+<text text-anchor="start" x="974.51" y="-488.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊤</text>
+<text text-anchor="start" x="990.26" y="-488.74" font-family="Times New Roman,serif" font-size="14.00" fill="white">:mem</text>
+</g>
+<!-- TOP->MEM_TOP -->
+<g id="edge46" class="edge">
+<title>TOP->MEM_TOP</title>
+<path fill="none" stroke="black" d="M662.51,-549.91C717.64,-540.7 867.72,-515.64 947.33,-502.34"/>
+<polygon fill="black" stroke="black" points="947.77,-505.82 957.06,-500.72 946.62,-498.91 947.77,-505.82"/>
+</g>
+<!-- TUPLE_TOP -->
+<g id="node34" class="node">
+<title>TUPLE_TOP</title>
+<ellipse fill="pink" stroke="black" cx="1182.51" cy="-492.79" rx="42.65" ry="18"/>
+<text text-anchor="start" x="1159.26" y="-488.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="1175.01" y="-488.74" font-family="Times New Roman,serif" font-size="14.00">:tuple</text>
+</g>
+<!-- TOP->TUPLE_TOP -->
+<g id="edge56" class="edge">
+<title>TOP->TUPLE_TOP</title>
+<path fill="none" stroke="black" d="M662.72,-551.08C740.91,-542.46 1014.51,-512.31 1130.21,-499.56"/>
+<polygon fill="black" stroke="black" points="1130.5,-503.05 1140.05,-498.47 1129.73,-496.09 1130.5,-503.05"/>
+</g>
+<!-- BOT -->
+<g id="node2" class="node">
+<title>BOT</title>
+<ellipse fill="black" stroke="black" cx="641.51" cy="-21.12" rx="21.12" ry="21.12"/>
+<text text-anchor="start" x="633.63" y="-16.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊥</text>
+</g>
+<!-- CTRL -->
+<g id="node4" class="node">
+<title>CTRL</title>
+<ellipse fill="yellow" stroke="black" cx="49.51" cy="-82.75" rx="36.51" ry="18"/>
+<text text-anchor="start" x="30.76" y="-78.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="46.51" y="-78.7" font-family="Times New Roman,serif" font-size="14.00">:ctrl</text>
+</g>
+<!-- XCTRL->CTRL -->
+<g id="edge2" class="edge">
+<title>XCTRL->CTRL</title>
+<path fill="none" stroke="black" d="M37.09,-474.38C39.15,-409.6 46.05,-191.88 48.57,-112.25"/>
+<polygon fill="black" stroke="black" points="52.06,-112.73 48.88,-102.63 45.06,-112.51 52.06,-112.73"/>
+</g>
+<!-- CTRL->BOT -->
+<g id="edge3" class="edge">
+<title>CTRL->BOT</title>
+<path fill="none" stroke="black" d="M85.21,-78.15C191.74,-67.42 506.36,-35.74 608.84,-25.41"/>
+<polygon fill="black" stroke="black" points="609.15,-28.9 618.75,-24.42 608.45,-21.94 609.15,-28.9"/>
+</g>
+<!-- INT_HI -->
+<g id="node7" class="node">
+<title>INT_HI</title>
+<ellipse fill="lightblue" stroke="black" cx="174.51" cy="-434.29" rx="53.91" ry="18"/>
+<text text-anchor="middle" x="174.51" y="-429.24" font-family="Times New Roman,serif" font-size="14.00">[min>max]</text>
+</g>
+<!-- INT_TOP->INT_HI -->
+<g id="edge5" class="edge">
+<title>INT_TOP->INT_HI</title>
+<path fill="none" stroke="black" d="M289.8,-481.17C269.89,-473.25 242.26,-462.25 219.03,-453.01"/>
+<polygon fill="black" stroke="black" points="220.37,-449.77 209.78,-449.33 217.78,-456.28 220.37,-449.77"/>
+</g>
+<!-- INT_BOT -->
+<g id="node6" class="node">
+<title>INT_BOT</title>
+<ellipse fill="lightblue" stroke="black" cx="329.51" cy="-82.75" rx="33.95" ry="18"/>
+<text text-anchor="start" x="312.63" y="-78.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="328.38" y="-78.7" font-family="Times New Roman,serif" font-size="14.00">:int</text>
+</g>
+<!-- INT_BOT->BOT -->
+<g id="edge15" class="edge">
+<title>INT_BOT->BOT</title>
+<path fill="none" stroke="black" d="M361.14,-75.7C420.84,-64.3 549.47,-39.71 609.47,-28.25"/>
+<polygon fill="black" stroke="black" points="609.86,-31.73 619.03,-26.42 608.55,-24.86 609.86,-31.73"/>
+</g>
+<!-- INT_XBOOL -->
+<g id="node8" class="node">
+<title>INT_XBOOL</title>
+<ellipse fill="lightblue" stroke="black" cx="97.51" cy="-373.97" rx="33.95" ry="18"/>
+<text text-anchor="middle" x="97.51" y="-368.92" font-family="Times New Roman,serif" font-size="14.00">[1...0]</text>
+</g>
+<!-- INT_HI->INT_XBOOL -->
+<g id="edge6" class="edge">
+<title>INT_HI->INT_XBOOL</title>
+<path fill="none" stroke="black" d="M153.47,-417.36C144.79,-410.78 134.6,-403.06 125.31,-396.03"/>
+<polygon fill="black" stroke="black" points="127.71,-393.46 117.63,-390.21 123.48,-399.04 127.71,-393.46"/>
+</g>
+<!-- INT_CON -->
+<g id="node9" class="node">
+<title>INT_CON</title>
+<ellipse fill="lightblue" stroke="black" cx="174.51" cy="-282.65" rx="45.21" ry="18"/>
+<text text-anchor="middle" x="174.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">constants</text>
+</g>
+<!-- INT_HI->INT_CON -->
+<g id="edge9" class="edge">
+<title>INT_HI->INT_CON</title>
+<path fill="none" stroke="black" d="M174.51,-416C174.51,-390.27 174.51,-343.1 174.51,-312.31"/>
+<polygon fill="black" stroke="black" points="178.01,-312.52 174.51,-302.52 171.01,-312.52 178.01,-312.52"/>
+</g>
+<!-- INT_CON0 -->
+<g id="node10" class="node">
+<title>INT_CON0</title>
+<ellipse fill="lightblue" stroke="black" cx="47.51" cy="-282.65" rx="18" ry="18"/>
+<text text-anchor="middle" x="47.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">0</text>
+</g>
+<!-- INT_XBOOL->INT_CON0 -->
+<g id="edge7" class="edge">
+<title>INT_XBOOL->INT_CON0</title>
+<path fill="none" stroke="black" d="M88.34,-356.59C80.82,-343.17 70.07,-323.96 61.49,-308.62"/>
+<polygon fill="black" stroke="black" points="64.63,-307.08 56.69,-300.06 58.53,-310.5 64.63,-307.08"/>
+</g>
+<!-- INT_CON1 -->
+<g id="node11" class="node">
+<title>INT_CON1</title>
+<ellipse fill="lightblue" stroke="black" cx="97.51" cy="-282.65" rx="18" ry="18"/>
+<text text-anchor="middle" x="97.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">1</text>
+</g>
+<!-- INT_XBOOL->INT_CON1 -->
+<g id="edge8" class="edge">
+<title>INT_XBOOL->INT_CON1</title>
+<path fill="none" stroke="black" d="M97.51,-355.75C97.51,-343.47 97.51,-326.68 97.51,-312.39"/>
+<polygon fill="black" stroke="black" points="101.01,-312.64 97.51,-302.64 94.01,-312.64 101.01,-312.64"/>
+</g>
+<!-- INT_LO -->
+<g id="node13" class="node">
+<title>INT_LO</title>
+<ellipse fill="lightblue" stroke="black" cx="174.51" cy="-141.25" rx="53.91" ry="18"/>
+<text text-anchor="middle" x="174.51" y="-136.2" font-family="Times New Roman,serif" font-size="14.00">[min<max]</text>
+</g>
+<!-- INT_CON->INT_LO -->
+<g id="edge13" class="edge">
+<title>INT_CON->INT_LO</title>
+<path fill="none" stroke="black" d="M174.51,-264.17C174.51,-240.45 174.51,-199.04 174.51,-170.9"/>
+<polygon fill="black" stroke="black" points="178.01,-171.25 174.51,-161.25 171.01,-171.25 178.01,-171.25"/>
+</g>
+<!-- INT_CON0->INT_CON1 -->
+<!-- INT_BOOL -->
+<g id="node12" class="node">
+<title>INT_BOOL</title>
+<ellipse fill="lightblue" stroke="black" cx="97.51" cy="-196.45" rx="33.95" ry="18"/>
+<text text-anchor="middle" x="97.51" y="-191.4" font-family="Times New Roman,serif" font-size="14.00">[0...1]</text>
+</g>
+<!-- INT_CON0->INT_BOOL -->
+<g id="edge10" class="edge">
+<title>INT_CON0->INT_BOOL</title>
+<path fill="none" stroke="black" d="M56.45,-266.6C63.5,-254.72 73.51,-237.87 81.88,-223.77"/>
+<polygon fill="black" stroke="black" points="84.75,-225.79 86.85,-215.41 78.73,-222.22 84.75,-225.79"/>
+</g>
+<!-- INT_CON1->INT_CON -->
+<!-- INT_CON1->INT_BOOL -->
+<g id="edge11" class="edge">
+<title>INT_CON1->INT_BOOL</title>
+<path fill="none" stroke="black" d="M97.51,-264.21C97.51,-253.25 97.51,-238.87 97.51,-226.25"/>
+<polygon fill="black" stroke="black" points="101.01,-226.39 97.51,-216.39 94.01,-226.39 101.01,-226.39"/>
+</g>
+<!-- INT_BOOL->INT_LO -->
+<g id="edge12" class="edge">
+<title>INT_BOOL->INT_LO</title>
+<path fill="none" stroke="black" d="M117.34,-181.75C124.98,-176.47 133.91,-170.3 142.42,-164.42"/>
+<polygon fill="black" stroke="black" points="144.27,-167.4 150.5,-158.83 140.29,-161.64 144.27,-167.4"/>
+</g>
+<!-- INT_LO->INT_BOT -->
+<g id="edge14" class="edge">
+<title>INT_LO->INT_BOT</title>
+<path fill="none" stroke="black" d="M210.07,-127.29C234.52,-118.37 266.93,-106.56 291.82,-97.49"/>
+<polygon fill="black" stroke="black" points="292.71,-100.89 300.91,-94.17 290.31,-94.31 292.71,-100.89"/>
+</g>
+<!-- FLT_CON64 -->
+<g id="node16" class="node">
+<title>FLT_CON64</title>
+<ellipse fill="aqua" stroke="black" cx="564.51" cy="-282.65" rx="55.33" ry="40.66"/>
+<text text-anchor="middle" x="564.51" y="-294.1" font-family="Times New Roman,serif" font-size="14.00">64b consts</text>
+<text text-anchor="middle" x="564.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">[excludes</text>
+<text text-anchor="middle" x="564.51" y="-261.1" font-family="Times New Roman,serif" font-size="14.00">32b consts]</text>
+</g>
+<!-- FLT_TOP->FLT_CON64 -->
+<g id="edge19" class="edge">
+<title>FLT_TOP->FLT_CON64</title>
+<path fill="none" stroke="black" d="M500.48,-474.88C510.8,-443.88 532.35,-379.2 547.59,-333.44"/>
+<polygon fill="black" stroke="black" points="550.9,-334.57 550.74,-323.98 544.26,-332.36 550.9,-334.57"/>
+</g>
+<!-- FLT_CONPI -->
+<g id="node18" class="node">
+<title>FLT_CONPI</title>
+<ellipse fill="aqua" stroke="black" cx="446.51" cy="-282.65" rx="48.79" ry="18"/>
+<text text-anchor="middle" x="446.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">3.14159...</text>
+</g>
+<!-- FLT_TOP->FLT_CONPI -->
+<g id="edge20" class="edge">
+<title>FLT_TOP->FLT_CONPI</title>
+<path fill="none" stroke="black" d="M490.33,-474.51C482.02,-438.11 463.32,-356.27 453.25,-312.16"/>
+<polygon fill="black" stroke="black" points="456.69,-311.49 451.05,-302.52 449.86,-313.04 456.69,-311.49"/>
+</g>
+<!-- FLT_X32 -->
+<g id="node19" class="node">
+<title>FLT_X32</title>
+<ellipse fill="aqua" stroke="black" cx="333.51" cy="-373.97" rx="28.32" ry="28.32"/>
+<text text-anchor="middle" x="333.51" y="-368.92" font-family="Times New Roman,serif" font-size="14.00">~f32</text>
+</g>
+<!-- FLT_TOP->FLT_X32 -->
+<g id="edge23" class="edge">
+<title>FLT_TOP->FLT_X32</title>
+<path fill="none" stroke="black" d="M474.77,-478.22C447.56,-458.14 398.22,-421.73 365.65,-397.69"/>
+<polygon fill="black" stroke="black" points="367.88,-394.99 357.75,-391.86 363.72,-400.62 367.88,-394.99"/>
+</g>
+<!-- FLT_BOT -->
+<g id="node15" class="node">
+<title>FLT_BOT</title>
+<ellipse fill="aqua" stroke="black" cx="507.51" cy="-82.75" rx="32.41" ry="18"/>
+<text text-anchor="start" x="491.76" y="-78.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="507.51" y="-78.7" font-family="Times New Roman,serif" font-size="14.00">:flt</text>
+</g>
+<!-- FLT_BOT->BOT -->
+<g id="edge29" class="edge">
+<title>FLT_BOT->BOT</title>
+<path fill="none" stroke="black" d="M532.4,-70.67C554.98,-60.63 588.29,-45.81 612.16,-35.19"/>
+<polygon fill="black" stroke="black" points="613.29,-38.51 621,-31.25 610.44,-32.12 613.29,-38.51"/>
+</g>
+<!-- FLT_CON64->FLT_BOT -->
+<g id="edge21" class="edge">
+<title>FLT_CON64->FLT_BOT</title>
+<path fill="none" stroke="black" d="M553.11,-242.68C542.05,-203.88 525.53,-145.95 515.71,-111.5"/>
+<polygon fill="black" stroke="black" points="519.17,-110.89 513.06,-102.23 512.44,-112.81 519.17,-110.89"/>
+</g>
+<!-- FLT_CON32 -->
+<g id="node17" class="node">
+<title>FLT_CON32</title>
+<ellipse fill="aqua" stroke="black" cx="333.51" cy="-282.65" rx="50.33" ry="18"/>
+<text text-anchor="middle" x="333.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">32b consts</text>
+</g>
+<!-- FLT_CON32->FLT_CONPI -->
+<!-- FLT_32 -->
+<g id="node21" class="node">
+<title>FLT_32</title>
+<ellipse fill="aqua" stroke="black" cx="333.51" cy="-196.45" rx="23.2" ry="23.2"/>
+<text text-anchor="middle" x="333.51" y="-191.4" font-family="Times New Roman,serif" font-size="14.00">f32</text>
+</g>
+<!-- FLT_CON32->FLT_32 -->
+<g id="edge27" class="edge">
+<title>FLT_CON32->FLT_32</title>
+<path fill="none" stroke="black" d="M333.51,-264.21C333.51,-254.7 333.51,-242.59 333.51,-231.31"/>
+<polygon fill="black" stroke="black" points="337.01,-231.51 333.51,-221.51 330.01,-231.51 337.01,-231.51"/>
+</g>
+<!-- FLT_CONPI->FLT_BOT -->
+<g id="edge22" class="edge">
+<title>FLT_CONPI->FLT_BOT</title>
+<path fill="none" stroke="black" d="M452.03,-264.56C462.62,-229.86 485.86,-153.69 498.65,-111.79"/>
+<polygon fill="black" stroke="black" points="501.94,-112.98 501.51,-102.39 495.25,-110.93 501.94,-112.98"/>
+</g>
+<!-- FLT_CONPI->FLT_CON64 -->
+<!-- FLT_X32->FLT_CON32 -->
+<g id="edge25" class="edge">
+<title>FLT_X32->FLT_CON32</title>
+<path fill="none" stroke="black" d="M333.51,-345.2C333.51,-334.71 333.51,-322.76 333.51,-312.19"/>
+<polygon fill="black" stroke="black" points="337.01,-312.52 333.51,-302.52 330.01,-312.53 337.01,-312.52"/>
+</g>
+<!-- FLT_CON0 -->
+<g id="node20" class="node">
+<title>FLT_CON0</title>
+<ellipse fill="aqua" stroke="black" cx="251.51" cy="-282.65" rx="18.08" ry="18.08"/>
+<text text-anchor="middle" x="251.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">0.</text>
+</g>
+<!-- FLT_X32->FLT_CON0 -->
+<g id="edge24" class="edge">
+<title>FLT_X32->FLT_CON0</title>
+<path fill="none" stroke="black" d="M314.9,-352.7C301.83,-338.47 284.38,-319.46 271.1,-304.99"/>
+<polygon fill="black" stroke="black" points="273.81,-302.77 264.47,-297.77 268.65,-307.5 273.81,-302.77"/>
+</g>
+<!-- FLT_CON0->FLT_CON32 -->
+<!-- FLT_CON0->FLT_32 -->
+<g id="edge26" class="edge">
+<title>FLT_CON0->FLT_32</title>
+<path fill="none" stroke="black" d="M263.96,-268.86C276.06,-256.44 294.74,-237.26 309.69,-221.91"/>
+<polygon fill="black" stroke="black" points="312.03,-224.53 316.5,-214.92 307.01,-219.64 312.03,-224.53"/>
+</g>
+<!-- FLT_32->FLT_BOT -->
+<g id="edge28" class="edge">
+<title>FLT_32->FLT_BOT</title>
+<path fill="none" stroke="black" d="M353.13,-183.63C383.19,-163.99 440.9,-126.28 476.61,-102.94"/>
+<polygon fill="black" stroke="black" points="478.34,-105.99 484.79,-97.59 474.51,-100.13 478.34,-105.99"/>
+</g>
+<!-- PTR0 -->
+<g id="node23" class="node">
+<title>PTR0</title>
+<polygon fill="none" stroke="none" points="668.51,-109.25 614.51,-109.25 614.51,-56.25 668.51,-56.25 668.51,-109.25"/>
+<polygon fill="green" stroke="none" points="623.51,-82.75 623.51,-105.25 659.51,-105.25 659.51,-82.75 623.51,-82.75"/>
+<polygon fill="none" stroke="black" points="623.51,-82.75 623.51,-105.25 659.51,-105.25 659.51,-82.75 623.51,-82.75"/>
+<text text-anchor="start" x="627.63" y="-88.95" font-family="Times New Roman,serif" font-size="14.00" fill="white">*ptr?</text>
+<polygon fill="lightgreen" stroke="none" points="623.51,-60.25 623.51,-82.75 659.51,-82.75 659.51,-60.25 623.51,-60.25"/>
+<polygon fill="none" stroke="black" points="623.51,-60.25 623.51,-82.75 659.51,-82.75 659.51,-60.25 623.51,-60.25"/>
+<text text-anchor="start" x="626.51" y="-66.45" font-family="Times New Roman,serif" font-size="14.00">struct</text>
+</g>
+<!-- PTR->PTR0 -->
+<g id="edge34" class="edge">
+<title>PTR->PTR0</title>
+<path fill="none" stroke="black" d="M641.51,-466.52C641.51,-396.01 641.51,-202.44 641.51,-120.34"/>
+<polygon fill="black" stroke="black" points="645.01,-120.58 641.51,-110.58 638.01,-120.58 645.01,-120.58"/>
+</g>
+<!-- PTR0->BOT -->
+<g id="edge35" class="edge">
+<title>PTR0->BOT</title>
+<path fill="none" stroke="black" d="M641.51,-56.46C641.51,-55.58 641.51,-54.7 641.51,-53.81"/>
+<polygon fill="black" stroke="black" points="645.01,-53.9 641.51,-43.9 638.01,-53.9 645.01,-53.9"/>
+</g>
+<!-- STRUCT_S1 -->
+<g id="node26" class="node">
+<title>STRUCT_S1</title>
+<polygon fill="none" stroke="none" points="741.38,-300.65 663.63,-300.65 663.63,-264.65 741.38,-264.65 741.38,-300.65"/>
+<polygon fill="lightgreen" stroke="none" points="671.63,-273.4 671.63,-291.9 698.38,-291.9 698.38,-273.4 671.63,-273.4"/>
+<polygon fill="none" stroke="black" points="671.63,-273.4 671.63,-291.9 698.38,-291.9 698.38,-273.4 671.63,-273.4"/>
+<text text-anchor="start" x="672.63" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">field</text>
+<defs>
+<linearGradient id="l_0" gradientUnits="userSpaceOnUse" x1="703.51" y1="-289.19" x2="728.26" y2="-276.11" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_0)" stroke="none" points="698.38,-273.4 698.38,-291.9 733.38,-291.9 733.38,-273.4 698.38,-273.4"/>
+<polygon fill="none" stroke="black" points="698.38,-273.4 698.38,-291.9 733.38,-291.9 733.38,-273.4 698.38,-273.4"/>
+<text text-anchor="start" x="699.38" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+</g>
+<!-- STRUCT_TOP->STRUCT_S1 -->
+<g id="edge37" class="edge">
+<title>STRUCT_TOP->STRUCT_S1</title>
+<path fill="none" stroke="black" d="M742.68,-474.51C735.02,-437.92 717.75,-355.45 708.55,-311.5"/>
+<polygon fill="black" stroke="black" points="712.02,-311 706.54,-301.93 705.17,-312.43 712.02,-311"/>
+</g>
+<!-- STRUCT_S2 -->
+<g id="node27" class="node">
+<title>STRUCT_S2</title>
+<polygon fill="none" stroke="none" points="841.38,-309.15 755.63,-309.15 755.63,-256.15 841.38,-256.15 841.38,-309.15"/>
+<polygon fill="lightgreen" stroke="none" points="763.63,-282.65 763.63,-305.15 794.38,-305.15 794.38,-282.65 763.63,-282.65"/>
+<polygon fill="none" stroke="black" points="763.63,-282.65 763.63,-305.15 794.38,-305.15 794.38,-282.65 763.63,-282.65"/>
+<text text-anchor="start" x="766.63" y="-288.85" font-family="Times New Roman,serif" font-size="14.00">field</text>
+<defs>
+<linearGradient id="l_1" gradientUnits="userSpaceOnUse" x1="800.1" y1="-301.86" x2="827.67" y2="-285.95" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_1)" stroke="none" points="794.38,-282.65 794.38,-305.15 833.38,-305.15 833.38,-282.65 794.38,-282.65"/>
+<polygon fill="none" stroke="black" points="794.38,-282.65 794.38,-305.15 833.38,-305.15 833.38,-282.65 794.38,-282.65"/>
+<text text-anchor="start" x="797.38" y="-288.85" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+<polygon fill="lightgreen" stroke="none" points="763.63,-260.15 763.63,-282.65 794.38,-282.65 794.38,-260.15 763.63,-260.15"/>
+<polygon fill="none" stroke="black" points="763.63,-260.15 763.63,-282.65 794.38,-282.65 794.38,-260.15 763.63,-260.15"/>
+<text text-anchor="start" x="766.63" y="-266.35" font-family="Times New Roman,serif" font-size="14.00">field</text>
+<defs>
+<linearGradient id="l_2" gradientUnits="userSpaceOnUse" x1="800.1" y1="-279.36" x2="827.67" y2="-263.45" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_2)" stroke="none" points="794.38,-260.15 794.38,-282.65 833.38,-282.65 833.38,-260.15 794.38,-260.15"/>
+<polygon fill="none" stroke="black" points="794.38,-260.15 794.38,-282.65 833.38,-282.65 833.38,-260.15 794.38,-260.15"/>
+<text text-anchor="start" x="797.38" y="-266.35" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+</g>
+<!-- STRUCT_TOP->STRUCT_S2 -->
+<g id="edge38" class="edge">
+<title>STRUCT_TOP->STRUCT_S2</title>
+<path fill="none" stroke="black" d="M751.03,-474.51C759.53,-440.16 778.05,-365.34 789.28,-319.95"/>
+<polygon fill="black" stroke="black" points="792.67,-320.83 791.67,-310.28 785.87,-319.15 792.67,-320.83"/>
+</g>
+<!-- STRUCT_SN -->
+<g id="node28" class="node">
+<title>STRUCT_SN</title>
+<polygon fill="none" stroke="none" points="941.38,-320.4 855.63,-320.4 855.63,-244.9 941.38,-244.9 941.38,-320.4"/>
+<polygon fill="lightgreen" stroke="none" points="863.63,-293.9 863.63,-316.4 894.38,-316.4 894.38,-293.9 863.63,-293.9"/>
+<polygon fill="none" stroke="black" points="863.63,-293.9 863.63,-316.4 894.38,-316.4 894.38,-293.9 863.63,-293.9"/>
+<text text-anchor="start" x="866.63" y="-300.1" font-family="Times New Roman,serif" font-size="14.00">field</text>
+<defs>
+<linearGradient id="l_3" gradientUnits="userSpaceOnUse" x1="900.1" y1="-313.11" x2="927.67" y2="-297.2" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_3)" stroke="none" points="894.38,-293.9 894.38,-316.4 933.38,-316.4 933.38,-293.9 894.38,-293.9"/>
+<polygon fill="none" stroke="black" points="894.38,-293.9 894.38,-316.4 933.38,-316.4 933.38,-293.9 894.38,-293.9"/>
+<text text-anchor="start" x="897.38" y="-300.1" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+<polygon fill="lightgreen" stroke="none" points="863.63,-271.4 863.63,-293.9 894.38,-293.9 894.38,-271.4 863.63,-271.4"/>
+<polygon fill="none" stroke="black" points="863.63,-271.4 863.63,-293.9 894.38,-293.9 894.38,-271.4 863.63,-271.4"/>
+<text text-anchor="start" x="869.63" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">...  </text>
+<defs>
+<linearGradient id="l_4" gradientUnits="userSpaceOnUse" x1="900.1" y1="-290.61" x2="927.67" y2="-274.7" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_4)" stroke="none" points="894.38,-271.4 894.38,-293.9 933.38,-293.9 933.38,-271.4 894.38,-271.4"/>
+<polygon fill="none" stroke="black" points="894.38,-271.4 894.38,-293.9 933.38,-293.9 933.38,-271.4 894.38,-271.4"/>
+<text text-anchor="start" x="897.38" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+<polygon fill="lightgreen" stroke="none" points="863.63,-248.9 863.63,-271.4 894.38,-271.4 894.38,-248.9 863.63,-248.9"/>
+<polygon fill="none" stroke="black" points="863.63,-248.9 863.63,-271.4 894.38,-271.4 894.38,-248.9 863.63,-248.9"/>
+<text text-anchor="start" x="866.63" y="-255.1" font-family="Times New Roman,serif" font-size="14.00">field</text>
+<defs>
+<linearGradient id="l_5" gradientUnits="userSpaceOnUse" x1="900.1" y1="-268.11" x2="927.67" y2="-252.2" >
+<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/>
+<stop offset="1" style="stop-color:green;stop-opacity:1.;"/>
+</linearGradient>
+</defs>
+<polygon fill="url(#l_5)" stroke="none" points="894.38,-248.9 894.38,-271.4 933.38,-271.4 933.38,-248.9 894.38,-248.9"/>
+<polygon fill="none" stroke="black" points="894.38,-248.9 894.38,-271.4 933.38,-271.4 933.38,-248.9 894.38,-248.9"/>
+<text text-anchor="start" x="897.38" y="-255.1" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text>
+</g>
+<!-- STRUCT_TOP->STRUCT_SN -->
+<g id="edge39" class="edge">
+<title>STRUCT_TOP->STRUCT_SN</title>
+<path fill="none" stroke="black" d="M759.21,-475.24C782.17,-443.49 831.3,-375.56 864.63,-329.48"/>
+<polygon fill="black" stroke="black" points="867.37,-331.67 870.4,-321.52 861.7,-327.57 867.37,-331.67"/>
+</g>
+<!-- STRUCT_BOT -->
+<g id="node25" class="node">
+<title>STRUCT_BOT</title>
+<ellipse fill="lightgreen" stroke="black" cx="751.51" cy="-82.75" rx="44.7" ry="18"/>
+<text text-anchor="start" x="726.76" y="-78.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="742.51" y="-78.7" font-family="Times New Roman,serif" font-size="14.00">:struct</text>
+</g>
+<!-- STRUCT_BOT->BOT -->
+<g id="edge43" class="edge">
+<title>STRUCT_BOT->BOT</title>
+<path fill="none" stroke="black" d="M725.72,-67.77C709,-58.7 687.2,-46.89 669.97,-37.55"/>
+<polygon fill="black" stroke="black" points="671.71,-34.51 661.25,-32.82 668.37,-40.67 671.71,-34.51"/>
+</g>
+<!-- STRUCT_S1->STRUCT_BOT -->
+<g id="edge40" class="edge">
+<title>STRUCT_S1->STRUCT_BOT</title>
+<path fill="none" stroke="black" d="M706.86,-264.91C715.3,-230.49 733.97,-154.31 744.29,-112.19"/>
+<polygon fill="black" stroke="black" points="747.69,-113.04 746.67,-102.5 740.89,-111.37 747.69,-113.04"/>
+</g>
+<!-- STRUCT_S1->STRUCT_S2 -->
+<!-- STRUCT_S2->STRUCT_BOT -->
+<g id="edge41" class="edge">
+<title>STRUCT_S2->STRUCT_BOT</title>
+<path fill="none" stroke="black" d="M792.36,-256.52C783.62,-219.3 767.61,-151.25 758.45,-112.26"/>
+<polygon fill="black" stroke="black" points="761.88,-111.57 756.18,-102.64 755.07,-113.17 761.88,-111.57"/>
+</g>
+<!-- STRUCT_S2->STRUCT_SN -->
+<!-- STRUCT_SN->STRUCT_BOT -->
+<g id="edge42" class="edge">
+<title>STRUCT_SN->STRUCT_BOT</title>
+<path fill="none" stroke="black" d="M870.86,-245.05C841.74,-205.46 796.64,-144.13 771.03,-109.3"/>
+<polygon fill="black" stroke="black" points="773.99,-107.42 765.25,-101.44 768.36,-111.57 773.99,-107.42"/>
+</g>
+<!-- MEM_ALIAS1 -->
+<g id="node31" class="node">
+<title>MEM_ALIAS1</title>
+<ellipse fill="blue" stroke="black" cx="975.51" cy="-282.65" rx="20.13" ry="20.13"/>
+<text text-anchor="middle" x="975.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00" fill="white">#1</text>
+</g>
+<!-- MEM_TOP->MEM_ALIAS1 -->
+<g id="edge47" class="edge">
+<title>MEM_TOP->MEM_ALIAS1</title>
+<path fill="none" stroke="black" d="M996.51,-474.51C992.58,-438.66 983.84,-358.73 978.96,-314.18"/>
+<polygon fill="black" stroke="black" points="982.45,-313.94 977.89,-304.38 975.5,-314.7 982.45,-313.94"/>
+</g>
+<!-- MEM_ALIASDOTS -->
+<g id="node32" class="node">
+<title>MEM_ALIASDOTS</title>
+<ellipse fill="blue" stroke="black" cx="1036.51" cy="-282.65" rx="27" ry="18"/>
+<text text-anchor="middle" x="1036.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00" fill="white">...</text>
+</g>
+<!-- MEM_TOP->MEM_ALIASDOTS -->
+<g id="edge48" class="edge">
+<title>MEM_TOP->MEM_ALIASDOTS</title>
+<path fill="none" stroke="black" d="M1001.81,-474.51C1008.41,-438.02 1023.27,-355.86 1031.23,-311.83"/>
+<polygon fill="black" stroke="black" points="1034.63,-312.69 1032.97,-302.23 1027.74,-311.45 1034.63,-312.69"/>
+</g>
+<!-- MEM_ALIASN -->
+<g id="node33" class="node">
+<title>MEM_ALIASN</title>
+<ellipse fill="blue" stroke="black" cx="1097.51" cy="-282.65" rx="20.13" ry="20.13"/>
+<text text-anchor="middle" x="1097.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00" fill="white">#n</text>
+</g>
+<!-- MEM_TOP->MEM_ALIASN -->
+<g id="edge49" class="edge">
+<title>MEM_TOP->MEM_ALIASN</title>
+<path fill="none" stroke="black" d="M1006.95,-474.88C1024.11,-438.46 1063.18,-355.52 1083.95,-311.44"/>
+<polygon fill="black" stroke="black" points="1087.07,-313.03 1088.16,-302.49 1080.73,-310.05 1087.07,-313.03"/>
+</g>
+<!-- MEM_BOT -->
+<g id="node30" class="node">
+<title>MEM_BOT</title>
+<ellipse fill="blue" stroke="black" cx="998.51" cy="-82.75" rx="43.67" ry="18"/>
+<text text-anchor="start" x="974.51" y="-78.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊥</text>
+<text text-anchor="start" x="990.26" y="-78.7" font-family="Times New Roman,serif" font-size="14.00" fill="white">:mem</text>
+</g>
+<!-- MEM_BOT->BOT -->
+<g id="edge53" class="edge">
+<title>MEM_BOT->BOT</title>
+<path fill="none" stroke="black" d="M958.6,-75.08C887.17,-63.15 738.86,-38.38 673.56,-27.48"/>
+<polygon fill="black" stroke="black" points="674.3,-24.05 663.86,-25.86 673.15,-30.96 674.3,-24.05"/>
+</g>
+<!-- MEM_ALIAS1->MEM_BOT -->
+<g id="edge50" class="edge">
+<title>MEM_ALIAS1->MEM_BOT</title>
+<path fill="none" stroke="black" d="M977.84,-262.38C981.92,-226.96 990.35,-153.62 995.09,-112.45"/>
+<polygon fill="black" stroke="black" points="998.57,-112.87 996.23,-102.53 991.61,-112.07 998.57,-112.87"/>
+</g>
+<!-- MEM_ALIAS1->MEM_ALIASDOTS -->
+<!-- MEM_ALIASDOTS->MEM_BOT -->
+<g id="edge51" class="edge">
+<title>MEM_ALIASDOTS->MEM_BOT</title>
+<path fill="none" stroke="black" d="M1033.07,-264.56C1026.49,-229.93 1012.06,-154.01 1004.08,-112.06"/>
+<polygon fill="black" stroke="black" points="1007.56,-111.6 1002.25,-102.43 1000.68,-112.91 1007.56,-111.6"/>
+</g>
+<!-- MEM_ALIASDOTS->MEM_ALIASN -->
+<!-- MEM_ALIASN->MEM_BOT -->
+<g id="edge52" class="edge">
+<title>MEM_ALIASN->MEM_BOT</title>
+<path fill="none" stroke="black" d="M1088.37,-264.2C1070.97,-229.07 1032.98,-152.35 1012.41,-110.82"/>
+<polygon fill="black" stroke="black" points="1015.58,-109.34 1008.01,-101.93 1009.31,-112.45 1015.58,-109.34"/>
+</g>
+<!-- TUPLE1 -->
+<g id="node36" class="node">
+<title>TUPLE1</title>
+<polygon fill="none" stroke="none" points="1185.51,-309.15 1131.51,-309.15 1131.51,-256.15 1185.51,-256.15 1185.51,-309.15"/>
+<polygon fill="pink" stroke="none" points="1139.76,-282.65 1139.76,-305.15 1177.26,-305.15 1177.26,-282.65 1139.76,-282.65"/>
+<polygon fill="none" stroke="black" points="1139.76,-282.65 1139.76,-305.15 1177.26,-305.15 1177.26,-282.65 1139.76,-282.65"/>
+<text text-anchor="start" x="1142.76" y="-288.85" font-family="Times New Roman,serif" font-size="14.00">Tuple</text>
+<polygon fill="black" stroke="none" points="1139.76,-260.15 1139.76,-282.65 1177.26,-282.65 1177.26,-260.15 1139.76,-260.15"/>
+<polygon fill="none" stroke="black" points="1139.76,-260.15 1139.76,-282.65 1177.26,-282.65 1177.26,-260.15 1139.76,-260.15"/>
+<text text-anchor="start" x="1146.88" y="-266.35" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+</g>
+<!-- TUPLE_TOP->TUPLE1 -->
+<g id="edge57" class="edge">
+<title>TUPLE_TOP->TUPLE1</title>
+<path fill="none" stroke="black" d="M1180.42,-474.51C1176.51,-440.23 1167.99,-365.66 1162.8,-320.24"/>
+<polygon fill="black" stroke="black" points="1166.28,-319.86 1161.67,-310.32 1159.33,-320.65 1166.28,-319.86"/>
+</g>
+<!-- TUPLE2 -->
+<g id="node37" class="node">
+<title>TUPLE2</title>
+<polygon fill="none" stroke="none" points="1253.51,-320.4 1199.51,-320.4 1199.51,-244.9 1253.51,-244.9 1253.51,-320.4"/>
+<polygon fill="pink" stroke="none" points="1207.76,-293.9 1207.76,-316.4 1245.26,-316.4 1245.26,-293.9 1207.76,-293.9"/>
+<polygon fill="none" stroke="black" points="1207.76,-293.9 1207.76,-316.4 1245.26,-316.4 1245.26,-293.9 1207.76,-293.9"/>
+<text text-anchor="start" x="1210.76" y="-300.1" font-family="Times New Roman,serif" font-size="14.00">Tuple</text>
+<polygon fill="black" stroke="none" points="1207.76,-271.4 1207.76,-293.9 1245.26,-293.9 1245.26,-271.4 1207.76,-271.4"/>
+<polygon fill="none" stroke="black" points="1207.76,-271.4 1207.76,-293.9 1245.26,-293.9 1245.26,-271.4 1207.76,-271.4"/>
+<text text-anchor="start" x="1214.88" y="-277.6" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+<polygon fill="black" stroke="none" points="1207.76,-248.9 1207.76,-271.4 1245.26,-271.4 1245.26,-248.9 1207.76,-248.9"/>
+<polygon fill="none" stroke="black" points="1207.76,-248.9 1207.76,-271.4 1245.26,-271.4 1245.26,-248.9 1207.76,-248.9"/>
+<text text-anchor="start" x="1214.88" y="-255.1" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+</g>
+<!-- TUPLE_TOP->TUPLE2 -->
+<g id="edge58" class="edge">
+<title>TUPLE_TOP->TUPLE2</title>
+<path fill="none" stroke="black" d="M1186.34,-474.51C1192.95,-442.94 1206.72,-377.19 1216.28,-331.51"/>
+<polygon fill="black" stroke="black" points="1219.68,-332.35 1218.3,-321.85 1212.83,-330.92 1219.68,-332.35"/>
+</g>
+<!-- TUPLEN -->
+<g id="node38" class="node">
+<title>TUPLEN</title>
+<polygon fill="none" stroke="none" points="1321.51,-331.65 1267.51,-331.65 1267.51,-233.65 1321.51,-233.65 1321.51,-331.65"/>
+<polygon fill="pink" stroke="none" points="1275.76,-305.15 1275.76,-327.65 1313.26,-327.65 1313.26,-305.15 1275.76,-305.15"/>
+<polygon fill="none" stroke="black" points="1275.76,-305.15 1275.76,-327.65 1313.26,-327.65 1313.26,-305.15 1275.76,-305.15"/>
+<text text-anchor="start" x="1278.76" y="-311.35" font-family="Times New Roman,serif" font-size="14.00">Tuple</text>
+<polygon fill="black" stroke="none" points="1275.76,-282.65 1275.76,-305.15 1313.26,-305.15 1313.26,-282.65 1275.76,-282.65"/>
+<polygon fill="none" stroke="black" points="1275.76,-282.65 1275.76,-305.15 1313.26,-305.15 1313.26,-282.65 1275.76,-282.65"/>
+<text text-anchor="start" x="1282.88" y="-288.85" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+<polygon fill="black" stroke="none" points="1275.76,-260.15 1275.76,-282.65 1313.26,-282.65 1313.26,-260.15 1275.76,-260.15"/>
+<polygon fill="none" stroke="black" points="1275.76,-260.15 1275.76,-282.65 1313.26,-282.65 1313.26,-260.15 1275.76,-260.15"/>
+<text text-anchor="start" x="1288.88" y="-266.35" font-family="Times New Roman,serif" font-size="14.00" fill="white">...</text>
+<polygon fill="black" stroke="none" points="1275.76,-237.65 1275.76,-260.15 1313.26,-260.15 1313.26,-237.65 1275.76,-237.65"/>
+<polygon fill="none" stroke="black" points="1275.76,-237.65 1275.76,-260.15 1313.26,-260.15 1313.26,-237.65 1275.76,-237.65"/>
+<text text-anchor="start" x="1282.88" y="-243.85" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+</g>
+<!-- TUPLE_TOP->TUPLEN -->
+<g id="edge59" class="edge">
+<title>TUPLE_TOP->TUPLEN</title>
+<path fill="none" stroke="black" d="M1192.06,-474.88C1207.65,-445.62 1239.24,-386.36 1263.24,-341.32"/>
+<polygon fill="black" stroke="black" points="1266.22,-343.18 1267.83,-332.71 1260.04,-339.88 1266.22,-343.18"/>
+</g>
+<!-- TUPLE_BOT -->
+<g id="node35" class="node">
+<title>TUPLE_BOT</title>
+<ellipse fill="pink" stroke="black" cx="1192.51" cy="-82.75" rx="42.65" ry="18"/>
+<text text-anchor="start" x="1169.26" y="-78.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="1185.01" y="-78.7" font-family="Times New Roman,serif" font-size="14.00">:tuple</text>
+</g>
+<!-- TUPLE_BOT->BOT -->
+<g id="edge63" class="edge">
+<title>TUPLE_BOT->BOT</title>
+<path fill="none" stroke="black" d="M1151.54,-77.32C1046.53,-65.95 769.32,-35.95 674.14,-25.65"/>
+<polygon fill="black" stroke="black" points="674.52,-22.18 664.2,-24.58 673.77,-29.14 674.52,-22.18"/>
+</g>
+<!-- TUPLE1->TUPLE_BOT -->
+<g id="edge60" class="edge">
+<title>TUPLE1->TUPLE_BOT</title>
+<path fill="none" stroke="black" d="M1162.95,-256.52C1169.28,-219.3 1180.86,-151.25 1187.49,-112.26"/>
+<polygon fill="black" stroke="black" points="1190.9,-113.1 1189.12,-102.66 1184,-111.93 1190.9,-113.1"/>
+</g>
+<!-- TUPLE2->TUPLE_BOT -->
+<g id="edge61" class="edge">
+<title>TUPLE2->TUPLE_BOT</title>
+<path fill="none" stroke="black" d="M1220.11,-245.05C1213.55,-206.44 1203.46,-147.16 1197.47,-111.94"/>
+<polygon fill="black" stroke="black" points="1200.99,-111.74 1195.86,-102.47 1194.09,-112.92 1200.99,-111.74"/>
+</g>
+<!-- TUPLEN->TUPLE_BOT -->
+<g id="edge62" class="edge">
+<title>TUPLEN->TUPLE_BOT</title>
+<path fill="none" stroke="black" d="M1269.56,-233.75C1249.85,-195.12 1223.04,-142.58 1206.8,-110.75"/>
+<polygon fill="black" stroke="black" points="1210.07,-109.46 1202.41,-102.15 1203.83,-112.65 1210.07,-109.46"/>
+</g>
+</g>
+</svg>
diff --git a/docs/chapter20/lattice2.gv b/docs/chapter20/lattice2.gv new file mode 100644 index 00000000..6aa37fa0 --- /dev/null +++ b/docs/chapter20/lattice2.gv @@ -0,0 +1,85 @@ +digraph Lattice { + compound = true; + // Define nodes + splines=false; + node [shape=oval, style=filled]; + nodesep=0.2; + ranksep=0.4; + + TOP [label="~scalar\n+int+tmp+0", fillcolor=black, fontcolor=white, group=center]; + + // ------------------------ + PTRHQ [label="~tmp\n+tmp+0", fillcolor=green, fontcolor=white, group=left]; + TOP -> PTRHQ + + VALH_ [label="~nscalar\n+int+tmp", fillcolor=white, group=center]; + TOP -> VALH_ + + INTHQ [label="~int\n+int+0", fillcolor=lightblue, group=right]; + TOP -> INTHQ + + LEFTHI [label="junk", style=invis, group=junkleft] + + + PTRHQ -> LEFTHI-> VALH_ -> INTHQ [style=invis]; + { rank=same; PTRHQ; LEFTHI; VALH_; INTHQ } + + // ------------------------ + PTRH_ [label="~ntmp\n+tmp", fillcolor=green, fontcolor=white, group=left]; + VALH_ -> PTRH_ + PTRHQ -> PTRH_ + + INTH_ [label="~nint\n+int", fillcolor=lightblue, group=right]; + VALH_ -> INTH_ + INTHQ -> INTH_ + { rank=same; PTRH_; INTH_ } + + // ------------------------ + NILX_ [label="~nil\n[int,tmp]+0", fillcolor=aqua, group=junkleft]; + INTHQ -> NILX_ + PTRHQ -> NILX_ + + NIL__ [label="nil\n[+int+tmp],0", fillcolor=pink]; + VALH_ -> NIL__; + + NILX_ -> NIL__ [style=invis]; + { rank=same; NIL__; NILX_ } + + // ------------------------ + PTRL_ [label="ntmp\ntmp", fillcolor=green, fontcolor=white, group=left]; + PTRH_ -> PTRL_ + + INTL_ [label="nint\nint", fillcolor=lightblue, group=right]; + INTH_ -> INTL_ + { rank=same; PTRL_; INTL_ } + + // ------------------------ + PTRL0 [label="tmp\ntmp,0", fillcolor=green, fontcolor=white, group=left]; + PTRL_ -> PTRL0 + NIL__ -> PTRL0 + + VALL_ [label="nscalar\nint,tmp", fillcolor=white, group=center]; + PTRL_ -> VALL_ + INTL_ -> VALL_ + NILX_ -> VALL_ + + INTL0 [label="int\nint,0", fillcolor=lightblue, group=right]; + INTL_ -> INTL0 + NIL__ -> INTL0 + + PTRL0 -> VALL_ -> INTL0 [style=invis]; + { rank=same; PTRL0; VALL_; INTL0 } + + // ------------------------ + BOT [label="scalar\nint,tmp,0", fillcolor=black, fontcolor=white, group=center]; + PTRL0 -> BOT + INTL0 -> BOT + VALL_ -> BOT + + // ------------------------ + // Verticle alignment + TOP -> VALH_ -> VALL_ -> BOT [style=invis]; + PTRHQ -> PTRH_ -> PTRL_ -> PTRL0 [style=invis]; + INTHQ -> INTH_ -> INTL_ -> INTL0 [style=invis]; + LEFTHI -> NILX_ [style=invis] +} diff --git a/docs/chapter20/lattice2.svg b/docs/chapter20/lattice2.svg new file mode 100644 index 00000000..857bca2d --- /dev/null +++ b/docs/chapter20/lattice2.svg @@ -0,0 +1,260 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+ "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 12.2.0 (20241103.1931)
+ -->
+<!-- Title: Lattice Pages: 1 -->
+<svg width="478pt" height="501pt"
+ viewBox="0.00 0.00 477.96 500.90" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 496.9)">
+<title>Lattice</title>
+<polygon fill="white" stroke="none" points="-4,4 -4,-496.9 473.96,-496.9 473.96,4 -4,4"/>
+<!-- TOP -->
+<g id="node1" class="node">
+<title>TOP</title>
+<ellipse fill="black" stroke="black" cx="240.13" cy="-463.91" rx="59.04" ry="28.99"/>
+<text text-anchor="middle" x="240.13" y="-467.11" font-family="Times New Roman,serif" font-size="14.00" fill="white">~scalar</text>
+<text text-anchor="middle" x="240.13" y="-450.61" font-family="Times New Roman,serif" font-size="14.00" fill="white">+int+tmp+0</text>
+</g>
+<!-- PTRHQ -->
+<g id="node2" class="node">
+<title>PTRHQ</title>
+<ellipse fill="green" stroke="black" cx="43.13" cy="-376.92" rx="43.13" ry="28.99"/>
+<text text-anchor="middle" x="43.13" y="-380.12" font-family="Times New Roman,serif" font-size="14.00" fill="white">~tmp</text>
+<text text-anchor="middle" x="43.13" y="-363.62" font-family="Times New Roman,serif" font-size="14.00" fill="white">+tmp+0</text>
+</g>
+<!-- TOP->PTRHQ -->
+<g id="edge1" class="edge">
+<title>TOP->PTRHQ</title>
+<path fill="none" stroke="black" d="M196.41,-444.04C164.74,-430.38 121.99,-411.94 89.68,-398"/>
+<polygon fill="black" stroke="black" points="91.11,-394.81 80.55,-394.06 88.34,-401.24 91.11,-394.81"/>
+</g>
+<!-- VALH_ -->
+<g id="node3" class="node">
+<title>VALH_</title>
+<ellipse fill="white" stroke="black" cx="240.13" cy="-376.92" rx="48.44" ry="28.99"/>
+<text text-anchor="middle" x="240.13" y="-380.12" font-family="Times New Roman,serif" font-size="14.00">~nscalar</text>
+<text text-anchor="middle" x="240.13" y="-363.62" font-family="Times New Roman,serif" font-size="14.00">+int+tmp</text>
+</g>
+<!-- TOP->VALH_ -->
+<g id="edge2" class="edge">
+<title>TOP->VALH_</title>
+<path fill="none" stroke="black" d="M235.15,-434.61C234.93,-429.02 234.85,-423.06 234.9,-417.18"/>
+<polygon fill="black" stroke="black" points="238.39,-417.69 235.12,-407.61 231.39,-417.52 238.39,-417.69"/>
+</g>
+<!-- TOP->VALH_ -->
+<!-- INTHQ -->
+<g id="node4" class="node">
+<title>INTHQ</title>
+<ellipse fill="lightblue" stroke="black" cx="432.13" cy="-376.92" rx="37.83" ry="28.99"/>
+<text text-anchor="middle" x="432.13" y="-380.12" font-family="Times New Roman,serif" font-size="14.00">~int</text>
+<text text-anchor="middle" x="432.13" y="-363.62" font-family="Times New Roman,serif" font-size="14.00">+int+0</text>
+</g>
+<!-- TOP->INTHQ -->
+<g id="edge3" class="edge">
+<title>TOP->INTHQ</title>
+<path fill="none" stroke="black" d="M283.22,-443.83C314.91,-429.81 357.78,-410.83 389.39,-396.84"/>
+<polygon fill="black" stroke="black" points="390.53,-400.16 398.26,-392.92 387.7,-393.76 390.53,-400.16"/>
+</g>
+<!-- LEFTHI -->
+<!-- PTRHQ->LEFTHI -->
+<!-- PTRH_ -->
+<g id="node6" class="node">
+<title>PTRH_</title>
+<ellipse fill="green" stroke="black" cx="43.13" cy="-289.94" rx="36.77" ry="28.99"/>
+<text text-anchor="middle" x="43.13" y="-293.14" font-family="Times New Roman,serif" font-size="14.00" fill="white">~ntmp</text>
+<text text-anchor="middle" x="43.13" y="-276.64" font-family="Times New Roman,serif" font-size="14.00" fill="white">+tmp</text>
+</g>
+<!-- PTRHQ->PTRH_ -->
+<g id="edge8" class="edge">
+<title>PTRHQ->PTRH_</title>
+<path fill="none" stroke="black" d="M38.15,-347.62C37.93,-342.03 37.85,-336.07 37.9,-330.2"/>
+<polygon fill="black" stroke="black" points="41.39,-330.71 38.12,-320.63 34.39,-330.54 41.39,-330.71"/>
+</g>
+<!-- PTRHQ->PTRH_ -->
+<!-- NILX_ -->
+<g id="node8" class="node">
+<title>NILX_</title>
+<ellipse fill="aqua" stroke="black" cx="150.13" cy="-289.94" rx="56.39" ry="28.99"/>
+<text text-anchor="middle" x="150.13" y="-293.14" font-family="Times New Roman,serif" font-size="14.00">~nil</text>
+<text text-anchor="middle" x="150.13" y="-276.64" font-family="Times New Roman,serif" font-size="14.00">[int,tmp]+0</text>
+</g>
+<!-- PTRHQ->NILX_ -->
+<g id="edge12" class="edge">
+<title>PTRHQ->NILX_</title>
+<path fill="none" stroke="black" d="M70.41,-354.26C82.91,-344.33 97.94,-332.4 111.56,-321.58"/>
+<polygon fill="black" stroke="black" points="113.43,-324.56 119.09,-315.6 109.08,-319.08 113.43,-324.56"/>
+</g>
+<!-- VALH_->INTHQ -->
+<!-- VALH_->PTRH_ -->
+<g id="edge7" class="edge">
+<title>VALH_->PTRH_</title>
+<path fill="none" stroke="black" d="M201.21,-359.13C167.78,-344.71 119.68,-323.96 85.33,-309.14"/>
+<polygon fill="black" stroke="black" points="87.1,-306.09 76.53,-305.35 84.33,-312.52 87.1,-306.09"/>
+</g>
+<!-- INTH_ -->
+<g id="node7" class="node">
+<title>INTH_</title>
+<ellipse fill="lightblue" stroke="black" cx="432.13" cy="-289.94" rx="31.47" ry="28.99"/>
+<text text-anchor="middle" x="432.13" y="-293.14" font-family="Times New Roman,serif" font-size="14.00">~nint</text>
+<text text-anchor="middle" x="432.13" y="-276.64" font-family="Times New Roman,serif" font-size="14.00">+int</text>
+</g>
+<!-- VALH_->INTH_ -->
+<g id="edge9" class="edge">
+<title>VALH_->INTH_</title>
+<path fill="none" stroke="black" d="M278.53,-358.93C311.9,-344.16 360.02,-322.86 393.48,-308.05"/>
+<polygon fill="black" stroke="black" points="394.67,-311.35 402.4,-304.1 391.84,-304.95 394.67,-311.35"/>
+</g>
+<!-- NIL__ -->
+<g id="node9" class="node">
+<title>NIL__</title>
+<ellipse fill="pink" stroke="black" cx="324.13" cy="-289.94" rx="62.23" ry="28.99"/>
+<text text-anchor="middle" x="324.13" y="-293.14" font-family="Times New Roman,serif" font-size="14.00">nil</text>
+<text text-anchor="middle" x="324.13" y="-276.64" font-family="Times New Roman,serif" font-size="14.00">[+int+tmp],0</text>
+</g>
+<!-- VALH_->NIL__ -->
+<g id="edge13" class="edge">
+<title>VALH_->NIL__</title>
+<path fill="none" stroke="black" d="M264.43,-351.34C272.67,-343.01 282.01,-333.55 290.83,-324.64"/>
+<polygon fill="black" stroke="black" points="293.12,-327.3 297.66,-317.72 288.14,-322.38 293.12,-327.3"/>
+</g>
+<!-- VALL_ -->
+<g id="node13" class="node">
+<title>VALL_</title>
+<ellipse fill="white" stroke="black" cx="240.13" cy="-115.97" rx="39.42" ry="28.99"/>
+<text text-anchor="middle" x="240.13" y="-119.17" font-family="Times New Roman,serif" font-size="14.00">nscalar</text>
+<text text-anchor="middle" x="240.13" y="-102.67" font-family="Times New Roman,serif" font-size="14.00">int,tmp</text>
+</g>
+<!-- VALH_->VALL_ -->
+<!-- INTHQ->INTH_ -->
+<g id="edge10" class="edge">
+<title>INTHQ->INTH_</title>
+<path fill="none" stroke="black" d="M427.17,-348.1C426.94,-342.37 426.85,-336.25 426.9,-330.21"/>
+<polygon fill="black" stroke="black" points="430.39,-330.42 427.13,-320.34 423.39,-330.26 430.39,-330.42"/>
+</g>
+<!-- INTHQ->INTH_ -->
+<!-- INTHQ->NILX_ -->
+<g id="edge11" class="edge">
+<title>INTHQ->NILX_</title>
+<path fill="none" stroke="black" d="M396.99,-365.33C350,-351.17 266.03,-325.87 209.23,-308.75"/>
+<polygon fill="black" stroke="black" points="210.28,-305.41 199.69,-305.88 208.26,-312.11 210.28,-305.41"/>
+</g>
+<!-- LEFTHI->VALH_ -->
+<!-- LEFTHI->NILX_ -->
+<!-- PTRL_ -->
+<g id="node10" class="node">
+<title>PTRL_</title>
+<ellipse fill="green" stroke="black" cx="43.13" cy="-202.96" rx="31.47" ry="28.99"/>
+<text text-anchor="middle" x="43.13" y="-206.16" font-family="Times New Roman,serif" font-size="14.00" fill="white">ntmp</text>
+<text text-anchor="middle" x="43.13" y="-189.66" font-family="Times New Roman,serif" font-size="14.00" fill="white">tmp</text>
+</g>
+<!-- PTRH_->PTRL_ -->
+<g id="edge15" class="edge">
+<title>PTRH_->PTRL_</title>
+<path fill="none" stroke="black" d="M38.17,-261.11C37.94,-255.39 37.85,-249.26 37.9,-243.22"/>
+<polygon fill="black" stroke="black" points="41.39,-243.44 38.13,-233.36 34.39,-243.27 41.39,-243.44"/>
+</g>
+<!-- PTRH_->PTRL_ -->
+<!-- INTL_ -->
+<g id="node11" class="node">
+<title>INTL_</title>
+<ellipse fill="lightblue" stroke="black" cx="432.13" cy="-202.96" rx="27" ry="28.99"/>
+<text text-anchor="middle" x="432.13" y="-206.16" font-family="Times New Roman,serif" font-size="14.00">nint</text>
+<text text-anchor="middle" x="432.13" y="-189.66" font-family="Times New Roman,serif" font-size="14.00">int</text>
+</g>
+<!-- INTH_->INTL_ -->
+<g id="edge16" class="edge">
+<title>INTH_->INTL_</title>
+<path fill="none" stroke="black" d="M427.17,-261.11C426.94,-255.39 426.85,-249.26 426.9,-243.22"/>
+<polygon fill="black" stroke="black" points="430.39,-243.44 427.13,-233.36 423.39,-243.27 430.39,-243.44"/>
+</g>
+<!-- INTH_->INTL_ -->
+<!-- NILX_->NIL__ -->
+<!-- NILX_->VALL_ -->
+<g id="edge21" class="edge">
+<title>NILX_->VALL_</title>
+<path fill="none" stroke="black" d="M164.79,-261.6C180.03,-232.15 203.95,-185.91 220.74,-153.45"/>
+<polygon fill="black" stroke="black" points="223.74,-155.27 225.23,-144.78 217.53,-152.06 223.74,-155.27"/>
+</g>
+<!-- PTRL0 -->
+<g id="node12" class="node">
+<title>PTRL0</title>
+<ellipse fill="green" stroke="black" cx="43.13" cy="-115.97" rx="34.12" ry="28.99"/>
+<text text-anchor="middle" x="43.13" y="-119.17" font-family="Times New Roman,serif" font-size="14.00" fill="white">tmp</text>
+<text text-anchor="middle" x="43.13" y="-102.67" font-family="Times New Roman,serif" font-size="14.00" fill="white">tmp,0</text>
+</g>
+<!-- NIL__->PTRL0 -->
+<g id="edge18" class="edge">
+<title>NIL__->PTRL0</title>
+<path fill="none" stroke="black" d="M286.24,-266.48C232.36,-233.13 134.24,-172.38 80.6,-139.17"/>
+<polygon fill="black" stroke="black" points="82.76,-136.39 72.41,-134.1 79.07,-142.34 82.76,-136.39"/>
+</g>
+<!-- INTL0 -->
+<g id="node14" class="node">
+<title>INTL0</title>
+<ellipse fill="lightblue" stroke="black" cx="432.13" cy="-115.97" rx="28.81" ry="28.99"/>
+<text text-anchor="middle" x="432.13" y="-119.17" font-family="Times New Roman,serif" font-size="14.00">int</text>
+<text text-anchor="middle" x="432.13" y="-102.67" font-family="Times New Roman,serif" font-size="14.00">int,0</text>
+</g>
+<!-- NIL__->INTL0 -->
+<g id="edge23" class="edge">
+<title>NIL__->INTL0</title>
+<path fill="none" stroke="black" d="M341.49,-261.99C360.34,-231.61 390.49,-183.05 410.79,-150.35"/>
+<polygon fill="black" stroke="black" points="413.65,-152.38 415.95,-142.04 407.7,-148.69 413.65,-152.38"/>
+</g>
+<!-- PTRL_->PTRL0 -->
+<g id="edge17" class="edge">
+<title>PTRL_->PTRL0</title>
+<path fill="none" stroke="black" d="M38.17,-174.13C37.94,-168.47 37.85,-162.41 37.9,-156.43"/>
+<polygon fill="black" stroke="black" points="41.39,-156.75 38.12,-146.67 34.39,-156.58 41.39,-156.75"/>
+</g>
+<!-- PTRL_->PTRL0 -->
+<!-- PTRL_->VALL_ -->
+<g id="edge19" class="edge">
+<title>PTRL_->VALL_</title>
+<path fill="none" stroke="black" d="M71.36,-189.78C103.94,-175.73 157.92,-152.44 196.04,-135.99"/>
+<polygon fill="black" stroke="black" points="197.16,-139.32 204.96,-132.15 194.39,-132.9 197.16,-139.32"/>
+</g>
+<!-- INTL_->VALL_ -->
+<g id="edge20" class="edge">
+<title>INTL_->VALL_</title>
+<path fill="none" stroke="black" d="M407.43,-191.02C376.23,-177.21 322.01,-153.22 283.77,-136.29"/>
+<polygon fill="black" stroke="black" points="285.39,-133.18 274.83,-132.33 282.55,-139.58 285.39,-133.18"/>
+</g>
+<!-- INTL_->INTL0 -->
+<g id="edge22" class="edge">
+<title>INTL_->INTL0</title>
+<path fill="none" stroke="black" d="M427.17,-174.13C426.94,-168.41 426.85,-162.28 426.9,-156.24"/>
+<polygon fill="black" stroke="black" points="430.39,-156.46 427.13,-146.38 423.39,-156.29 430.39,-156.46"/>
+</g>
+<!-- INTL_->INTL0 -->
+<!-- PTRL0->VALL_ -->
+<!-- BOT -->
+<g id="node15" class="node">
+<title>BOT</title>
+<ellipse fill="black" stroke="black" cx="240.13" cy="-28.99" rx="46.85" ry="28.99"/>
+<text text-anchor="middle" x="240.13" y="-32.19" font-family="Times New Roman,serif" font-size="14.00" fill="white">scalar</text>
+<text text-anchor="middle" x="240.13" y="-15.69" font-family="Times New Roman,serif" font-size="14.00" fill="white">int,tmp,0</text>
+</g>
+<!-- PTRL0->BOT -->
+<g id="edge26" class="edge">
+<title>PTRL0->BOT</title>
+<path fill="none" stroke="black" d="M73.48,-101.88C105.02,-88.28 154.83,-66.79 191.79,-50.85"/>
+<polygon fill="black" stroke="black" points="193.14,-54.08 200.94,-46.9 190.37,-47.65 193.14,-54.08"/>
+</g>
+<!-- VALL_->INTL0 -->
+<!-- VALL_->BOT -->
+<g id="edge28" class="edge">
+<title>VALL_->BOT</title>
+<path fill="none" stroke="black" d="M235.17,-87.15C234.94,-81.48 234.85,-75.42 234.9,-69.44"/>
+<polygon fill="black" stroke="black" points="238.39,-69.76 235.12,-59.68 231.39,-69.6 238.39,-69.76"/>
+</g>
+<!-- VALL_->BOT -->
+<!-- INTL0->BOT -->
+<g id="edge27" class="edge">
+<title>INTL0->BOT</title>
+<path fill="none" stroke="black" d="M405.84,-103.34C375.52,-89.91 325.06,-67.58 287.78,-51.08"/>
+<polygon fill="black" stroke="black" points="289.59,-48.05 279.03,-47.21 286.75,-54.45 289.59,-48.05"/>
+</g>
+</g>
+</svg>
diff --git a/docs/chapter20/pardoe.docx b/docs/chapter20/pardoe.docx Binary files differnew file mode 100644 index 00000000..24fde921 --- /dev/null +++ b/docs/chapter20/pardoe.docx diff --git a/docs/chapter20/webtcp.min.js b/docs/chapter20/webtcp.min.js new file mode 100644 index 00000000..bf23ee5a --- /dev/null +++ b/docs/chapter20/webtcp.min.js @@ -0,0 +1,65 @@ +function Http(j){this.cID=Math.random().toString(36).substr(2);this.webtcp=j;this.webtcp.httpClients[this.cID]=this;this.createPacket=function(){return{cID:this.cID,type:"http",host:this.remoteAddress,port:this.remotePort,method:null,data:null}};this.ondata=function(){};this.get=function(g,c){this.on("data",c);this.rpc("httpGet",[g])};this.post=function(g,c,j){this.on("data",j);this.rpc("httpPost",[g,c])}}Http.prototype=new WebTCPIO;function Socket(j,g,c,p){this.sID=Math.random().toString(36).substr(2);this.webtcp=j;this.closed=this.ready=!1;this.options=p;this.sockOpts={_updating:!1};this.remoteAddress=g;this.remotePort=c;this.webtcp.sockets[this.sID]=this;this.createPacket=function(){return{id:Math.random().toString(36).substr(2),sID:this.sID,type:"tcp",options:this.options,host:this.remoteAddress,port:this.remotePort,data:null}};this.onconnect=function(){this.webtcp.sockets[sID].ready=!0;this.webtcp.sockets[sID].closed=!1}; +this.ondata=function(){};this.onend=function(){};this.ontimeout=function(){};this.ondrain=function(){};this.onclose=function(){this.webtcp.sockets[sID].ready=!1;this.webtcp.sockets[sID].closed=!0};this.getSockOpts=function(){this.sockOpts._updating=!0;this.rpc("getSockOpts")};this.onSockOptsRcv=function(c){this.sockOpts=c;this.sockOpts._updating=!1}}Socket.prototype=new WebTCPIO;var JSON;JSON||(JSON={}); +(function(){function j(c,p){var q,t,n,x,i=k,e,l=p[c];l&&"object"==typeof l&&"function"==typeof l.toJSON&&(l=l.toJSON(c));"function"==typeof r&&(l=r.call(p,c,l));switch(typeof l){case "string":return g(l);case "number":return isFinite(l)?String(l):"null";case "boolean":case "null":return String(l);case "object":if(!l)return"null";k+=v;e=[];if("[object Array]"===Object.prototype.toString.apply(l)){x=l.length;for(q=0;q<x;q+=1)e[q]=j(q,l)||"null";n=0===e.length?"[]":k?"[\n"+k+e.join(",\n"+k)+"\n"+i+"]": +"["+e.join(",")+"]";k=i;return n}if(r&&"object"==typeof r){x=r.length;for(q=0;q<x;q+=1)"string"==typeof r[q]&&(t=r[q],n=j(t,l),n&&e.push(g(t)+(k?": ":":")+n))}else for(t in l)Object.prototype.hasOwnProperty.call(l,t)&&(n=j(t,l),n&&e.push(g(t)+(k?": ":":")+n));n=0===e.length?"{}":k?"{\n"+k+e.join(",\n"+k)+"\n"+i+"}":"{"+e.join(",")+"}";k=i;return n}}function g(c){n.lastIndex=0;return n.test(c)?'"'+c.replace(n,function(c){var g=D[c];return"string"==typeof g?g:"\\u"+("0000"+c.charCodeAt(0).toString(16)).slice(-4)})+ +'"':'"'+c+'"'}function c(c){return 10>c?"0"+c:c}"use strict";"function"!=typeof Date.prototype.toJSON&&(Date.prototype.toJSON=function(){return isFinite(this.valueOf())?this.getUTCFullYear()+"-"+c(this.getUTCMonth()+1)+"-"+c(this.getUTCDate())+"T"+c(this.getUTCHours())+":"+c(this.getUTCMinutes())+":"+c(this.getUTCSeconds())+"Z":null},String.prototype.toJSON=Number.prototype.toJSON=Boolean.prototype.toJSON=function(){return this.valueOf()});var p=/[\u0000\u00ad\u0600-\u0604\u070f\u17b4\u17b5\u200c-\u200f\u2028-\u202f\u2060-\u206f\ufeff\ufff0-\uffff]/g, +n=/[\\\"\x00-\x1f\x7f-\x9f\u00ad\u0600-\u0604\u070f\u17b4\u17b5\u200c-\u200f\u2028-\u202f\u2060-\u206f\ufeff\ufff0-\uffff]/g,k,v,D={"\b":"\\b","\t":"\\t","\n":"\\n","\f":"\\f","\r":"\\r",'"':'\\"',"\\":"\\\\"},r;"function"!=typeof JSON.stringify&&(JSON.stringify=function(c,g,p){var n;v=k="";if("number"==typeof p)for(n=0;n<p;n+=1)v+=" ";else"string"==typeof p&&(v=p);r=g;if(!g||"function"==typeof g||"object"==typeof g&&"number"==typeof g.length)return j("",{"":c});throw Error("JSON.stringify");});"function"!= +typeof JSON.parse&&(JSON.parse=function(c,g){function j(c,k){var i,e,l=c[k];if(l&&"object"==typeof l)for(i in l)Object.prototype.hasOwnProperty.call(l,i)&&(e=j(l,i),void 0!==e?l[i]=e:delete l[i]);return g.call(c,k,l)}var k,c=String(c);p.lastIndex=0;p.test(c)&&(c=c.replace(p,function(c){return"\\u"+("0000"+c.charCodeAt(0).toString(16)).slice(-4)}));if(/^[\],:{}\s]*$/.test(c.replace(/\\(?:["\\\/bfnrt]|u[0-9a-fA-F]{4})/g,"@").replace(/"[^"\\\n\r]*"|true|false|null|-?\d+(?:\.\d*)?(?:[eE][+\-]?\d+)?/g, +"]").replace(/(?:^|:|,)(?:\s*\[)+/g,"")))return k=eval("("+c+")"),"function"==typeof g?j({"":k},""):k;throw new SyntaxError("JSON.parse");})})(); +SockJS=function(){var j=document,g=window,c={},p=function(){};p.prototype.addEventListener=function(a,b){this._listeners||(this._listeners={});a in this._listeners||(this._listeners[a]=[]);var f=this._listeners[a];-1===c.arrIndexOf(f,b)&&f.push(b)};p.prototype.removeEventListener=function(a,b){if(this._listeners&&a in this._listeners){var f=this._listeners[a],d=c.arrIndexOf(f,b);-1!==d&&(1<f.length?this._listeners[a]=f.slice(0,d).concat(f.slice(d+1)):delete this._listeners[a])}};p.prototype.dispatchEvent= +function(a){var b=a.type,c=Array.prototype.slice.call(arguments,0);this["on"+b]&&this["on"+b].apply(this,c);if(this._listeners&&b in this._listeners)for(var d=0;d<this._listeners[b].length;d++)this._listeners[b][d].apply(this,c)};var n=function(a,b){this.type=a;if("undefined"!=typeof b)for(var c in b)b.hasOwnProperty(c)&&(this[c]=b[c])};n.prototype.toString=function(){var a=[],b;for(b in this)if(this.hasOwnProperty(b)){var c=this[b];"function"==typeof c&&(c="[function]");a.push(b+"="+c)}return"SimpleEvent("+ +a.join(", ")+")"};var k=function(a){this.events=a||[]};k.prototype.emit=function(a){var b=Array.prototype.slice.call(arguments,1);!this.nuked&&this["on"+a]&&this["on"+a].apply(this,b);-1===c.arrIndexOf(this.events,a)&&c.log("Event "+JSON.stringify(a)+" not listed "+JSON.stringify(this.events)+" in "+this)};k.prototype.nuke=function(){this.nuked=!0;for(var a=0;a<this.events.length;a++)delete this[this.events[a]]};c.random_string=function(a,b){var b=b||37,c,d=[];for(c=0;c<a;c++)d.push("abcdefghijklmnopqrstuvwxyz0123456789_".substr(Math.floor(Math.random()* +b),1));return d.join("")};c.random_number=function(a){return Math.floor(Math.random()*a)};c.random_number_string=function(a){var b=(""+(a-1)).length;return(Array(b+1).join("0")+c.random_number(a)).slice(-b)};c.getOrigin=function(a){return(a+"/").split("/").slice(0,3).join("/")};c.isSameOriginUrl=function(a,b){return b||(b=g.location.href),a.split("/").slice(0,3).join("/")===b.split("/").slice(0,3).join("/")};c.getParentDomain=function(a){return/^[0-9.]*$/.test(a)||/^\[/.test(a)||!/[.]/.test(a)?a: +a.split(".").slice(1).join(".")};c.objectExtend=function(a,b){for(var c in b)b.hasOwnProperty(c)&&(a[c]=b[c]);return a};c.polluteGlobalNamespace=function(){"_jp"in g||(g._jp={})};c.closeFrame=function(a,b){return"c"+JSON.stringify([a,b])};c.userSetCode=function(a){return 1E3===a||3E3<=a&&4999>=a};c.countRTO=function(a){var b;return 100<a?b=3*a:b=a+200,b};c.log=function(){g.console&&console.log&&console.log.apply&&console.log.apply(console,arguments)};c.bind=function(a,b){return a.bind?a.bind(b):function(){return a.apply(b, +arguments)}};c.flatUrl=function(a){return-1===a.indexOf("?")&&-1===a.indexOf("#")};c.amendUrl=function(a){var b=j.location;if(!a)throw Error("Wrong url for SockJS");if(!c.flatUrl(a))throw Error("Only basic urls are supported in SockJS");return 0===a.indexOf("//")&&(a=b.protocol+a),0===a.indexOf("/")&&(a=b.protocol+"//"+b.host+a),a=a.replace(/[/]+$/,""),a};c.arrIndexOf=function(a,b){for(var c=0;c<a.length;c++)if(a[c]===b)return c;return-1};c.arrSkip=function(a,b){var f=c.arrIndexOf(a,b);return-1=== +f?a.slice():a.slice(0,f).concat(a.slice(f+1))};c.isArray=Array.isArray||function(a){return 0<={}.toString.call(a).indexOf("Array")};c.delay=function(a,b){return"function"==typeof a&&(b=a,a=0),setTimeout(b,a)};var v=/[\\\"\x00-\x1f\x7f-\x9f\u00ad\u0600-\u0604\u070f\u17b4\u17b5\u200c-\u200f\u2028-\u202f\u2060-\u206f\ufeff\ufff0-\uffff]/g,D={"\x00":"\\u0000","\u0001":"\\u0001","\u0002":"\\u0002","\u0003":"\\u0003","\u0004":"\\u0004","\u0005":"\\u0005","\u0006":"\\u0006","\u0007":"\\u0007","\b":"\\b", +"\t":"\\t","\n":"\\n","\x0B":"\\u000b","\f":"\\f","\r":"\\r","\u000e":"\\u000e","\u000f":"\\u000f","\u0010":"\\u0010","\u0011":"\\u0011","\u0012":"\\u0012","\u0013":"\\u0013","\u0014":"\\u0014","\u0015":"\\u0015","\u0016":"\\u0016","\u0017":"\\u0017","\u0018":"\\u0018","\u0019":"\\u0019","\u001a":"\\u001a","\u001b":"\\u001b","\u001c":"\\u001c","\u001d":"\\u001d","\u001e":"\\u001e","\u001f":"\\u001f",'"':'\\"',"\\":"\\\\","\u007f":"\\u007f","\u0080":"\\u0080","\u0081":"\\u0081","\u0082":"\\u0082", +"\u0083":"\\u0083","\u0084":"\\u0084","\u0085":"\\u0085","\u0086":"\\u0086","\u0087":"\\u0087","\u0088":"\\u0088","\u0089":"\\u0089","\u008a":"\\u008a","\u008b":"\\u008b","\u008c":"\\u008c","\u008d":"\\u008d","\u008e":"\\u008e","\u008f":"\\u008f","\u0090":"\\u0090","\u0091":"\\u0091","\u0092":"\\u0092","\u0093":"\\u0093","\u0094":"\\u0094","\u0095":"\\u0095","\u0096":"\\u0096","\u0097":"\\u0097","\u0098":"\\u0098","\u0099":"\\u0099","\u009a":"\\u009a","\u009b":"\\u009b","\u009c":"\\u009c","\u009d":"\\u009d", +"\u009e":"\\u009e","\u009f":"\\u009f","\u00ad":"\\u00ad","\u0600":"\\u0600","\u0601":"\\u0601","\u0602":"\\u0602","\u0603":"\\u0603","\u0604":"\\u0604","\u070f":"\\u070f","\u17b4":"\\u17b4","\u17b5":"\\u17b5","\u200c":"\\u200c","\u200d":"\\u200d","\u200e":"\\u200e","\u200f":"\\u200f","\u2028":"\\u2028","\u2029":"\\u2029","\u202a":"\\u202a","\u202b":"\\u202b","\u202c":"\\u202c","\u202d":"\\u202d","\u202e":"\\u202e","\u202f":"\\u202f","\u2060":"\\u2060","\u2061":"\\u2061","\u2062":"\\u2062","\u2063":"\\u2063", +"\u2064":"\\u2064","\u2065":"\\u2065","\u2066":"\\u2066","\u2067":"\\u2067","\u2068":"\\u2068","\u2069":"\\u2069","\u206a":"\\u206a","\u206b":"\\u206b","\u206c":"\\u206c","\u206d":"\\u206d","\u206e":"\\u206e","\u206f":"\\u206f","\ufeff":"\\ufeff","\ufff0":"\\ufff0","\ufff1":"\\ufff1","\ufff2":"\\ufff2","\ufff3":"\\ufff3","\ufff4":"\\ufff4","\ufff5":"\\ufff5","\ufff6":"\\ufff6","\ufff7":"\\ufff7","\ufff8":"\\ufff8","\ufff9":"\\ufff9","\ufffa":"\\ufffa","\ufffb":"\\ufffb","\ufffc":"\\ufffc","\ufffd":"\\ufffd", +"\ufffe":"\\ufffe","\uffff":"\\uffff"},r=/[\x00-\x1f\ud800-\udfff\ufffe\uffff\u0300-\u0333\u033d-\u0346\u034a-\u034c\u0350-\u0352\u0357-\u0358\u035c-\u0362\u0374\u037e\u0387\u0591-\u05af\u05c4\u0610-\u0617\u0653-\u0654\u0657-\u065b\u065d-\u065e\u06df-\u06e2\u06eb-\u06ec\u0730\u0732-\u0733\u0735-\u0736\u073a\u073d\u073f-\u0741\u0743\u0745\u0747\u07eb-\u07f1\u0951\u0958-\u095f\u09dc-\u09dd\u09df\u0a33\u0a36\u0a59-\u0a5b\u0a5e\u0b5c-\u0b5d\u0e38-\u0e39\u0f43\u0f4d\u0f52\u0f57\u0f5c\u0f69\u0f72-\u0f76\u0f78\u0f80-\u0f83\u0f93\u0f9d\u0fa2\u0fa7\u0fac\u0fb9\u1939-\u193a\u1a17\u1b6b\u1cda-\u1cdb\u1dc0-\u1dcf\u1dfc\u1dfe\u1f71\u1f73\u1f75\u1f77\u1f79\u1f7b\u1f7d\u1fbb\u1fbe\u1fc9\u1fcb\u1fd3\u1fdb\u1fe3\u1feb\u1fee-\u1fef\u1ff9\u1ffb\u1ffd\u2000-\u2001\u20d0-\u20d1\u20d4-\u20d7\u20e7-\u20e9\u2126\u212a-\u212b\u2329-\u232a\u2adc\u302b-\u302c\uaab2-\uaab3\uf900-\ufa0d\ufa10\ufa12\ufa15-\ufa1e\ufa20\ufa22\ufa25-\ufa26\ufa2a-\ufa2d\ufa30-\ufa6d\ufa70-\ufad9\ufb1d\ufb1f\ufb2a-\ufb36\ufb38-\ufb3c\ufb3e\ufb40-\ufb41\ufb43-\ufb44\ufb46-\ufb4e\ufff0-\uffff]/g, +B,M=JSON&&JSON.stringify||function(a){return v.lastIndex=0,v.test(a)&&(a=a.replace(v,function(a){return D[a]})),'"'+a+'"'};c.quote=function(a){a=M(a);r.lastIndex=0;if(r.test(a)){if(!B){var b,c={},d=[];for(b=0;65536>b;b++)d.push(String.fromCharCode(b));B=(r.lastIndex=0,d.join("").replace(r,function(a){return c[a]="\\u"+("0000"+a.charCodeAt(0).toString(16)).slice(-4),""}),r.lastIndex=0,c)}a=a.replace(r,function(a){return B[a]})}return a};var q="websocket xdr-streaming xhr-streaming iframe-eventsource iframe-htmlfile xdr-polling xhr-polling iframe-xhr-polling jsonp-polling".split(" "); +c.probeProtocols=function(){for(var a={},b=0;b<q.length;b++){var c=q[b];a[c]=e[c]&&e[c].enabled()}return a};c.detectProtocols=function(a,b,c){var d={},h=[];b||(b=q);for(var m=0;m<b.length;m++){var g=b[m];d[g]=a[g]}var e=function(a){var b=a.shift();d[b]?h.push(b):0<a.length&&e(a)};return!1!==c.websocket&&e(["websocket"]),d["xhr-streaming"]&&!c.null_origin?h.push("xhr-streaming"):d["xdr-streaming"]&&!c.cookie_needed&&!c.null_origin?h.push("xdr-streaming"):e(["iframe-eventsource","iframe-htmlfile"]), +d["xhr-polling"]&&!c.null_origin?h.push("xhr-polling"):d["xdr-polling"]&&!c.cookie_needed&&!c.null_origin?h.push("xdr-polling"):e(["iframe-xhr-polling","jsonp-polling"]),h};c.createHook=function(){var a="a"+c.random_string(8);if(!("_sockjs_global"in g)){var b={};g._sockjs_global=function(a){return a in b||(b[a]={id:a,del:function(){delete b[a]}}),b[a]}}return g._sockjs_global(a)};c.attachMessage=function(a){c.attachEvent("message",a)};c.attachEvent=function(a,b){"undefined"!=typeof g.addEventListener? +g.addEventListener(a,b,!1):(j.attachEvent("on"+a,b),g.attachEvent("on"+a,b))};c.detachMessage=function(a){c.detachEvent("message",a)};c.detachEvent=function(a,b){"undefined"!=typeof g.addEventListener?g.removeEventListener(a,b,!1):(j.detachEvent("on"+a,b),g.detachEvent("on"+a,b))};var t={},C=!1,x=function(){for(var a in t)t[a](),delete t[a]},i=function(){C||(C=!0,x())};c.attachEvent("beforeunload",i);c.attachEvent("unload",i);c.unload_add=function(a){var b=c.random_string(8);return t[b]=a,C&&c.delay(x), +b};c.unload_del=function(a){a in t&&delete t[a]};c.createIframe=function(a,b){var f=j.createElement("iframe"),d,h,m=function(){clearTimeout(d);try{f.onload=null}catch(a){}f.onerror=null},g=function(){f&&(m(),setTimeout(function(){f&&f.parentNode.removeChild(f);f=null},0),c.unload_del(h))};return f.src=a,f.style.display="none",f.style.position="absolute",f.onerror=function(){f&&(g(),b("onerror"))},f.onload=function(){clearTimeout(d);d=setTimeout(function(){f&&(g(),b("onload timeout"))},2E3)},j.body.appendChild(f), +d=setTimeout(function(){f&&(g(),b("timeout"))},15E3),h=c.unload_add(g),{post:function(a,b){try{f&&f.contentWindow&&f.contentWindow.postMessage(a,b)}catch(c){}},cleanup:g,loaded:m}};c.createHtmlfile=function(a,b){var f=new ActiveXObject("htmlfile"),d,h,m,e=function(){clearTimeout(d)},j=function(){f&&(e(),c.unload_del(h),m.parentNode.removeChild(m),m=f=null,CollectGarbage())};f.open();f.write('<html><script>document.domain="'+document.domain+'";<\/script></html>');f.close();f.parentWindow._jp=g._jp; +var i=f.createElement("div");return f.body.appendChild(i),m=f.createElement("iframe"),i.appendChild(m),m.src=a,d=setTimeout(function(){f&&(j(),b("timeout"))},15E3),h=c.unload_add(j),{post:function(a,b){try{m&&m.contentWindow&&m.contentWindow.postMessage(a,b)}catch(c){}},cleanup:j,loaded:e}};i=function(){};i.prototype=new k(["chunk","finish"]);i.prototype._start=function(a,b,f,d){var h=this;try{h.xhr=new XMLHttpRequest}catch(m){}if(!h.xhr)try{h.xhr=new g.ActiveXObject("Microsoft.XMLHTTP")}catch(e){}if(g.ActiveXObject|| +g.XDomainRequest)b+=(-1===b.indexOf("?")?"?":"&")+"t="+ +new Date;h.unload_ref=c.unload_add(function(){h._cleanup(!0)});try{h.xhr.open(a,b,!0)}catch(j){h.emit("finish",0,"");h._cleanup();return}if(!d||!d.no_credentials)h.xhr.withCredentials="true";if(d&&d.headers)for(var i in d.headers)h.xhr.setRequestHeader(i,d.headers[i]);h.xhr.onreadystatechange=function(){if(h.xhr){var a=h.xhr;switch(a.readyState){case 3:try{var b=a.status,c=a.responseText}catch(d){}c&&0<c.length&&h.emit("chunk",b,c);break;case 4:h.emit("finish", +a.status,a.responseText),h._cleanup(!1)}}};h.xhr.send(f)};i.prototype._cleanup=function(a){if(this.xhr){c.unload_del(this.unload_ref);this.xhr.onreadystatechange=function(){};if(a)try{this.xhr.abort()}catch(b){}this.unload_ref=this.xhr=null}};i.prototype.close=function(){this.nuke();this._cleanup(!0)};(c.XHRCorsObject=function(){var a=this,b=arguments;c.delay(function(){a._start.apply(a,b)})}).prototype=new i;(c.XHRLocalObject=function(a,b,f){var d=this;c.delay(function(){d._start(a,b,f,{no_credentials:!0})})}).prototype= +new i;i=c.XDRObject=function(a,b,f){var d=this;c.delay(function(){d._start(a,b,f)})};i.prototype=new k(["chunk","finish"]);i.prototype._start=function(a,b,f){var d=this,h=new XDomainRequest,b=b+((-1===b.indexOf("?")?"?":"&")+"t="+ +new Date),g=h.ontimeout=h.onerror=function(){d.emit("finish",0,"");d._cleanup(!1)};h.onprogress=function(){d.emit("chunk",200,h.responseText)};h.onload=function(){d.emit("finish",200,h.responseText);d._cleanup(!1)};d.xdr=h;d.unload_ref=c.unload_add(function(){d._cleanup(!0)}); +try{d.xdr.open(a,b),d.xdr.send(f)}catch(e){g()}};i.prototype._cleanup=function(a){if(this.xdr){c.unload_del(this.unload_ref);this.xdr.ontimeout=this.xdr.onerror=this.xdr.onprogress=this.xdr.onload=null;if(a)try{this.xdr.abort()}catch(b){}this.unload_ref=this.xdr=null}};i.prototype.close=function(){this.nuke();this._cleanup(!0)};c.isXHRCorsCapable=function(){return g.XMLHttpRequest&&"withCredentials"in new XMLHttpRequest?1:g.XDomainRequest&&j.domain?2:s.enabled()?3:4};var e=function(a,b,f){var d=this, +h;d._options={devel:!1,debug:!1,protocols_whitelist:[],info:void 0,rtt:void 0};f&&c.objectExtend(d._options,f);d._base_url=c.amendUrl(a);d._server=d._options.server||c.random_number_string(1E3);d._options.protocols_whitelist&&d._options.protocols_whitelist.length?h=d._options.protocols_whitelist:("string"==typeof b&&0<b.length?h=[b]:c.isArray(b)?h=b:h=null,h&&d._debug('Deprecated API: Use "protocols_whitelist" option instead of supplying protocol list as a second parameter to SockJS constructor.')); +d._protocols=[];d.protocol=null;d.readyState=e.CONNECTING;d._ir=N(d._base_url);d._ir.onfinish=function(a,b){d._ir=null;a?(d._options.info&&(a=c.objectExtend(a,d._options.info)),d._options.rtt&&(b=d._options.rtt),d._applyInfo(a,b,h),d._didClose()):d._didClose(1002,"Can't connect to server",!0)}};e.prototype=new p;e.version="0.3.2";e.CONNECTING=0;e.OPEN=1;e.CLOSING=2;e.CLOSED=3;e.prototype._debug=function(){this._options.debug&&c.log.apply(c,arguments)};e.prototype._dispatchOpen=function(){this.readyState=== +e.CONNECTING?(this._transport_tref&&(clearTimeout(this._transport_tref),this._transport_tref=null),this.readyState=e.OPEN,this.dispatchEvent(new n("open"))):this._didClose(1006,"Server lost session")};e.prototype._dispatchMessage=function(a){this.readyState===e.OPEN&&this.dispatchEvent(new n("message",{data:a}))};e.prototype._dispatchHeartbeat=function(){this.readyState===e.OPEN&&this.dispatchEvent(new n("heartbeat",{}))};e.prototype._didClose=function(a,b,f){var d=this;if(d.readyState!==e.CONNECTING&& +d.readyState!==e.OPEN&&d.readyState!==e.CLOSING)throw Error("INVALID_STATE_ERR");d._ir&&(d._ir.nuke(),d._ir=null);d._transport&&(d._transport.doCleanup(),d._transport=null);var h=new n("close",{code:a,reason:b,wasClean:c.userSetCode(a)});if(!c.userSetCode(a)&&d.readyState===e.CONNECTING&&!f){if(d._try_next_protocol(h))return;h=new n("close",{code:2E3,reason:"All transports failed",wasClean:!1,last_event:h})}d.readyState=e.CLOSED;c.delay(function(){d.dispatchEvent(h)})};e.prototype._didMessage=function(a){switch(a.slice(0, +1)){case "o":this._dispatchOpen();break;case "a":for(var a=JSON.parse(a.slice(1)||"[]"),b=0;b<a.length;b++)this._dispatchMessage(a[b]);break;case "m":a=JSON.parse(a.slice(1)||"null");this._dispatchMessage(a);break;case "c":a=JSON.parse(a.slice(1)||"[]");this._didClose(a[0],a[1]);break;case "h":this._dispatchHeartbeat()}};e.prototype._try_next_protocol=function(a){var b=this;b.protocol&&(b._debug("Closed transport:",b.protocol,""+a),b.protocol=null);for(b._transport_tref&&(clearTimeout(b._transport_tref), +b._transport_tref=null);;){a=b.protocol=b._protocols.shift();if(!a)return!1;if(e[a]&&!0===e[a].need_body&&(!j.body||"undefined"!=typeof j.readyState&&"complete"!==j.readyState))return b._protocols.unshift(a),b.protocol="waiting-for-load",c.attachEvent("load",function(){b._try_next_protocol()}),!0;if(e[a]&&e[a].enabled(b._options)){b._transport_tref=c.delay((b._options.rto||0)*(e[a].roundTrips||1)||5E3,function(){b.readyState===e.CONNECTING&&b._didClose(2007,"Transport timeouted")});var f=c.random_string(8), +f=b._base_url+"/"+b._server+"/"+f;return b._debug("Opening transport:",a," url:"+f," RTO:"+b._options.rto),b._transport=new e[a](b,f,b._base_url),!0}b._debug("Skipping transport:",a)}};e.prototype.close=function(a,b){if(a&&!c.userSetCode(a))throw Error("INVALID_ACCESS_ERR");return this.readyState!==e.CONNECTING&&this.readyState!==e.OPEN?!1:(this.readyState=e.CLOSING,this._didClose(a||1E3,b||"Normal closure"),!0)};e.prototype.send=function(a){if(this.readyState===e.CONNECTING)throw Error("INVALID_STATE_ERR"); +return this.readyState===e.OPEN&&this._transport.doSend(c.quote(""+a)),!0};e.prototype._applyInfo=function(a,b,f){this._options.info=a;this._options.rtt=b;this._options.rto=c.countRTO(b);this._options.info.null_origin=!j.domain;b=c.probeProtocols();this._protocols=c.detectProtocols(b,f,a)};i=e.websocket=function(a,b){var f=this,d=b+"/websocket";"https"===d.slice(0,5)?d="wss"+d.slice(5):d="ws"+d.slice(4);f.ri=a;f.url=d;f.ws=new (g.WebSocket||g.MozWebSocket)(f.url);f.ws.onmessage=function(a){f.ri._didMessage(a.data)}; +f.unload_ref=c.unload_add(function(){f.ws.close()});f.ws.onclose=function(){f.ri._didMessage(c.closeFrame(1006,"WebSocket connection broken"))}};i.prototype.doSend=function(a){this.ws.send("["+a+"]")};i.prototype.doCleanup=function(){var a=this.ws;a&&(a.onmessage=a.onclose=null,a.close(),c.unload_del(this.unload_ref),this.unload_ref=this.ri=this.ws=null)};i.enabled=function(){return!!g.WebSocket||!!g.MozWebSocket};i.roundTrips=2;var l=function(){};l.prototype.send_constructor=function(a){this.send_buffer= +[];this.sender=a};l.prototype.doSend=function(a){this.send_buffer.push(a);this.send_stop||this.send_schedule()};l.prototype.send_schedule_wait=function(){var a=this,b;a.send_stop=function(){a.send_stop=null;clearTimeout(b)};b=c.delay(25,function(){a.send_stop=null;a.send_schedule()})};l.prototype.send_schedule=function(){var a=this;if(0<a.send_buffer.length){var b="["+a.send_buffer.join(",")+"]";a.send_stop=a.sender(a.trans_url,b,function(){a.send_stop=null;a.send_schedule_wait()});a.send_buffer= +[]}};l.prototype.send_destructor=function(){this._send_stop&&this._send_stop();this._send_stop=null};var O=function(a,b,f){if(!("_send_form"in this)){var d=this._send_form=j.createElement("form"),h=this._send_area=j.createElement("textarea");h.name="d";d.style.display="none";d.style.position="absolute";d.method="POST";d.enctype="application/x-www-form-urlencoded";d.acceptCharset="UTF-8";d.appendChild(h);j.body.appendChild(d)}var d=this._send_form,h=this._send_area,g="a"+c.random_string(8);d.target= +g;d.action=a+"/jsonp_send?i="+g;var e;try{e=j.createElement('<iframe name="'+g+'">')}catch(i){e=j.createElement("iframe"),e.name=g}e.id=g;d.appendChild(e);e.style.display="none";try{h.value=b}catch(k){c.log("Your browser is seriously broken. Go home! "+k.message)}d.submit();var l=function(){e.onerror&&(e.onreadystatechange=e.onerror=e.onload=null,c.delay(500,function(){e.parentNode.removeChild(e);e=null}),h.value="",f())};return e.onerror=e.onload=l,e.onreadystatechange=function(){"complete"==e.readyState&& +l()},l},P=function(a){return function(b,c,d){return(new a("POST",b+"/xhr_send",c)).onfinish=function(a){d(a)},function(a){d(0,a)}}},i=e["jsonp-polling"]=function(a,b){c.polluteGlobalNamespace();this.ri=a;this.trans_url=b;this.send_constructor(O);this._schedule_recv()};i.prototype=new l;i.prototype._schedule_recv=function(){var a=this,b=a.trans_url+"/jsonp",f="a"+c.random_string(6),b=b+"?c="+escape("_jp."+f),d=function(b){delete g._jp[f];a._recv_stop=null;b&&(a._is_closing||a.ri._didMessage(b));a._is_closing|| +a._schedule_recv()},e,m=j.createElement("script"),i,k=function(a){i&&(i.parentNode.removeChild(i),i=null);m&&(clearTimeout(e),m.parentNode.removeChild(m),m.onreadystatechange=m.onerror=m.onload=m.onclick=null,m=null,d(a),d=null)},l=!1,p=null;m.id="a"+c.random_string(8);m.src=b;m.type="text/javascript";m.charset="UTF-8";m.onerror=function(){p||(p=setTimeout(function(){l||k(c.closeFrame(1006,"JSONP script loaded abnormally (onerror)"))},1E3))};m.onload=function(){k(c.closeFrame(1006,"JSONP script loaded abnormally (onload)"))}; +m.onreadystatechange=function(){if(/loaded|closed/.test(m.readyState)){if(m&&m.htmlFor&&m.onclick){l=!0;try{m.onclick()}catch(a){}}m&&k(c.closeFrame(1006,"JSONP script loaded abnormally (onreadystatechange)"))}};if("undefined"==typeof m.async&&j.attachEvent)if(/opera/i.test(navigator.userAgent))i=j.createElement("script"),i.text="try{var a = document.getElementById('"+m.id+"'); if(a)a.onerror();}catch(x){};",m.async=i.async=!1;else{try{m.htmlFor=m.id,m.event="onclick"}catch(n){}m.async=!0}"undefined"!= +typeof m.async&&(m.async=!0);e=setTimeout(function(){k(c.closeFrame(1006,"JSONP script loaded abnormally (timeout)"))},35E3);b=j.getElementsByTagName("head")[0];b=(b.insertBefore(m,b.firstChild),i&&b.insertBefore(i,b.firstChild),k);g._jp[f]=b;a._recv_stop=function(){g._jp[f]&&g._jp[f](c.closeFrame(1E3,"JSONP user aborted read"))}};i.enabled=function(){return!0};i.need_body=!0;i.prototype.doCleanup=function(){this._is_closing=!0;this._recv_stop&&this._recv_stop();this.ri=this._recv_stop=null;this.send_destructor()}; +i=function(){};i.prototype=new l;i.prototype.run=function(a,b,c,d,e){this.ri=a;this.trans_url=b;this.send_constructor(P(e));this.poll=new E(a,d,b+c,e)};i.prototype.doCleanup=function(){this.poll&&(this.poll.abort(),this.poll=null)};var w=e["xhr-streaming"]=function(a,b){this.run(a,b,"/xhr_streaming",y,c.XHRCorsObject)};w.prototype=new i;w.enabled=function(){return g.XMLHttpRequest&&"withCredentials"in new XMLHttpRequest&&!/opera/i.test(navigator.userAgent)};w.roundTrips=2;w.need_body=!0;l=e["xdr-streaming"]= +function(a,b){this.run(a,b,"/xhr_streaming",y,c.XDRObject)};l.prototype=new i;l.enabled=function(){return!!g.XDomainRequest};l.roundTrips=2;var F=e["xhr-polling"]=function(a,b){this.run(a,b,"/xhr",y,c.XHRCorsObject)};F.prototype=new i;F.enabled=w.enabled;F.roundTrips=2;w=e["xdr-polling"]=function(a,b){this.run(a,b,"/xhr",y,c.XDRObject)};w.prototype=new i;w.enabled=l.enabled;w.roundTrips=2;var s=function(){};s.prototype.i_constructor=function(a,b,f){var d=this;d.ri=a;d.origin=c.getOrigin(f);d.base_url= +f;d.trans_url=b;a=f+"/iframe.html";d.ri._options.devel&&(a+="?t="+ +new Date);d.window_id=c.random_string(8);a+="#"+d.window_id;d.iframeObj=c.createIframe(a,function(a){d.ri._didClose(1006,"Unable to load an iframe ("+a+")")});d.onmessage_cb=c.bind(d.onmessage,d);c.attachMessage(d.onmessage_cb)};s.prototype.doCleanup=function(){if(this.iframeObj){c.detachMessage(this.onmessage_cb);try{this.iframeObj.iframe.contentWindow&&this.postMessage("c")}catch(a){}this.iframeObj.cleanup();this.onmessage_cb=this.iframeObj= +this.iframeObj=null}};s.prototype.onmessage=function(a){if(a.origin===this.origin){var b=a.data.slice(0,8),c=a.data.slice(8,9),a=a.data.slice(9);if(b===this.window_id)switch(c){case "s":this.iframeObj.loaded();this.postMessage("s",JSON.stringify([e.version,this.protocol,this.trans_url,this.base_url]));break;case "t":this.ri._didMessage(a)}}};s.prototype.postMessage=function(a,b){this.iframeObj.post(this.window_id+a+(b||""),this.origin)};s.prototype.doSend=function(a){this.postMessage("m",a)};s.enabled= +function(){var a=navigator&&navigator.userAgent&&-1!==navigator.userAgent.indexOf("Konqueror");return("function"==typeof g.postMessage||"object"==typeof g.postMessage)&&!a};var G,H=function(a,b){parent!==g?parent.postMessage(G+a+(b||""),"*"):c.log("Can't postMessage, no parent window.",a,b)},u=function(){};u.prototype._didClose=function(a,b){H("t",c.closeFrame(a,b))};u.prototype._didMessage=function(a){H("t",a)};u.prototype._doSend=function(a){this._transport.doSend(a)};u.prototype._doCleanup=function(){this._transport.doCleanup()}; +c.parent_origin=void 0;e.bootstrap_iframe=function(){var a;G=j.location.hash.slice(1);c.attachMessage(function(b){if(b.source===parent&&("undefined"==typeof c.parent_origin&&(c.parent_origin=b.origin),b.origin===c.parent_origin)){var f=b.data.slice(0,8),d=b.data.slice(8,9),b=b.data.slice(9);if(f===G)switch(d){case "s":var h=JSON.parse(b),f=h[0],d=h[1],b=h[2],h=h[3];f!==e.version&&c.log('Incompatibile SockJS! Main site uses: "'+f+'", the iframe: "'+e.version+'".');if(!c.flatUrl(b)||!c.flatUrl(h)){c.log("Only basic urls are supported in SockJS"); +break}if(!c.isSameOriginUrl(b)||!c.isSameOriginUrl(h)){c.log("Can't connect to different domain from within an iframe. ("+JSON.stringify([g.location.href,b,h])+")");break}a=new u;a._transport=new u[d](a,b,h);break;case "m":a._doSend(b);break;case "c":a&&a._doCleanup(),a=null}}});H("s")};var z=function(a,b){var f=this;c.delay(function(){f.doXhr(a,b)})};z.prototype=new k(["finish"]);z.prototype.doXhr=function(a,b){var f=this,d=(new Date).getTime(),e=new b("GET",a+"/info"),g=c.delay(8E3,function(){e.ontimeout()}); +e.onfinish=function(a,b){clearTimeout(g);g=null;if(200===a){var c=(new Date).getTime()-d,e=JSON.parse(b);"object"!=typeof e&&(e={});f.emit("finish",e,c)}else f.emit("finish")};e.ontimeout=function(){e.close();f.emit("finish")}};var K=function(a){var b=this,f=function(){var c=new s;c.protocol="w-iframe-info-receiver";var f=function(a){"string"==typeof a&&"m"===a.substr(0,1)?(a=JSON.parse(a.substr(1)),b.emit("finish",a[0],a[1])):b.emit("finish");c.doCleanup();c=null};c.i_constructor({_options:{},_didClose:f, +_didMessage:f},a,a)};j.body?f():c.attachEvent("load",f)};K.prototype=new k(["finish"]);var L=function(){var a=this;c.delay(function(){a.emit("finish",{},2E3)})};L.prototype=new k(["finish"]);var N=function(a){if(c.isSameOriginUrl(a))return new z(a,c.XHRLocalObject);switch(c.isXHRCorsCapable()){case 1:return new z(a,c.XHRLocalObject);case 2:return new z(a,c.XDRObject);case 3:return new K(a);default:return new L}};(u["w-iframe-info-receiver"]=function(a,b,f){(new z(f,c.XHRLocalObject)).onfinish=function(b, +c){a._didMessage("m"+JSON.stringify([b,c]));a._didClose()}}).prototype.doCleanup=function(){};k=e["iframe-eventsource"]=function(){this.protocol="w-iframe-eventsource";this.i_constructor.apply(this,arguments)};k.prototype=new s;k.enabled=function(){return"EventSource"in g&&s.enabled()};k.need_body=!0;k.roundTrips=3;(u["w-iframe-eventsource"]=function(a,b){this.run(a,b,"/eventsource",I,c.XHRLocalObject)}).prototype=new i;k=e["iframe-xhr-polling"]=function(){this.protocol="w-iframe-xhr-polling";this.i_constructor.apply(this, +arguments)};k.prototype=new s;k.enabled=function(){return g.XMLHttpRequest&&s.enabled()};k.need_body=!0;k.roundTrips=3;(u["w-iframe-xhr-polling"]=function(a,b){this.run(a,b,"/xhr",y,c.XHRLocalObject)}).prototype=new i;k=e["iframe-htmlfile"]=function(){this.protocol="w-iframe-htmlfile";this.i_constructor.apply(this,arguments)};k.prototype=new s;k.enabled=function(){return s.enabled()};k.need_body=!0;k.roundTrips=3;(u["w-iframe-htmlfile"]=function(a,b){this.run(a,b,"/htmlfile",J,c.XHRLocalObject)}).prototype= +new i;var E=function(a,b,c,d){this.ri=a;this.Receiver=b;this.recv_url=c;this.AjaxObject=d;this._scheduleRecv()};E.prototype._scheduleRecv=function(){var a=this,b=a.poll=new a.Receiver(a.recv_url,a.AjaxObject);b.onmessage=function(b){a.ri._didMessage(b.data)};b.onclose=function(c){a.poll=b=b.onmessage=b.onclose=null;a.poll_is_closing||("permanent"===c.reason?a.ri._didClose(1006,"Polling error ("+c.reason+")"):a._scheduleRecv())}};E.prototype.abort=function(){this.poll_is_closing=!0;this.poll&&this.poll.abort()}; +var I=function(a){var b=this,f=new EventSource(a);f.onmessage=function(a){b.dispatchEvent(new n("message",{data:unescape(a.data)}))};b.es_close=f.onerror=function(a,e){var g=e?"user":2!==f.readyState?"network":"permanent";b.es_close=f.onmessage=f.onerror=null;f.close();f=null;c.delay(200,function(){b.dispatchEvent(new n("close",{reason:g}))})}};I.prototype=new p;I.prototype.abort=function(){this.es_close&&this.es_close({},!0)};var A,J=function(a){var b=this;c.polluteGlobalNamespace();b.id="a"+c.random_string(6, +26);a+=(-1===a.indexOf("?")?"?":"&")+"c="+escape("_jp."+b.id);if(void 0===A)if("ActiveXObject"in g)try{A=!!new ActiveXObject("htmlfile")}catch(f){}else A=!1;var d=A?c.createHtmlfile:c.createIframe,e;g._jp[b.id]={start:function(){e.loaded()},message:function(a){b.dispatchEvent(new n("message",{data:a}))},stop:function(){b.iframe_close({},"network")}};b.iframe_close=function(a,c){e.cleanup();b.iframe_close=e=null;delete g._jp[b.id];b.dispatchEvent(new n("close",{reason:c}))};e=d(a,function(){b.iframe_close({}, +"permanent")})};J.prototype=new p;J.prototype.abort=function(){this.iframe_close&&this.iframe_close({},"user")};var y=function(a,b){var c=this,d=0;c.xo=new b("POST",a,null);c.xo.onchunk=function(a,b){if(200===a)for(;;){var e=b.slice(d),g=e.indexOf("\n");if(-1===g)break;d+=g+1;e=e.slice(0,g);c.dispatchEvent(new n("message",{data:e}))}};c.xo.onfinish=function(a,b){c.xo.onchunk(a,b);c.xo=null;c.dispatchEvent(new n("close",{reason:200===a?"network":"permanent"}))}};return y.prototype=new p,y.prototype.abort= +function(){this.xo&&(this.xo.close(),this.dispatchEvent(new n("close",{reason:"user"})),this.xo=null)},e.getUtils=function(){return c},e.getIframeTransport=function(){return s},e}();"_sockjs_onload"in window&&setTimeout(_sockjs_onload,1);"function"==typeof define&&define.amd&&define("sockjs",[],function(){return SockJS});function WebTCP(j,g){this.sockets={};this.httpClients={};this.sock=new SockJS("http://"+j+":"+g+"/bridge");this.ready=!1;this.outputBuffer=[];var c=this;this.sock.onopen=function(){c.ready=!0;c.processBuffer()};this.processBuffer=function(){if(0<this.outputBuffer.length&&this.ready)for(var c in this.outputBuffer)this.sock.send(this.outputBuffer[c])};this.sock.onmessage=function(g){g.data=JSON.parse(g.data);g.data.sID?(sID=g.data.sID,c.sockets[sID].onEvent(g.data.eventName,g.data.data)):g.data.cID&& +(cID=g.data.cID,c.httpClients[cID].onEvent(g.data.eventName,g.data.data))};this.sock.onclose=function(){console.log("close")};this.createSocket=function(c,g,j){return new Socket(this,c,g,j)};this.createHTTPClient=function(){return new Http(this)}};function WebTCPIO(){this.onEvent=function(j,g){this["on"+j](g);if(this["on"+j+"Custom"])this["on"+j+"Custom"](g)};this.on=function(j,g){this["on"+j+"Custom"]=g};this.rpc=function(j,g){var c=this.createPacket();c.command=j;c.args=g;this.send(JSON.stringify(c));return c.id};this.write=function(j){var g=this.createPacket();g.data=j;this.send(JSON.stringify(g));return g.id};this.send=function(j){if(this.webtcp.ready)this.webtcp.sock.send(j);else{if(this.webtcp.outputBuffer>this.webtcp.BUFF_SIZE)throw"Output buffer is already full, but sockJS connection is not ready yet"; +this.webtcp.outputBuffer.push(j)}};this.onerror=function(j){throw j;}};
\ No newline at end of file |
