From 18fd28edce813d36c491e42d9e64c53c7251d26e Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 7 Feb 2025 08:58:36 -0800 Subject: Chapter 19: Instruction Selection and Portable Compilation MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: hadha Co-authored-by: godalming123 <68993177+godalming123@users.noreply.github.com> Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- docs/chapter19/Makefile | 12 + docs/chapter19/README.ja.md | 149 ++++++++ docs/chapter19/README.md | 236 ++++++++++++ docs/chapter19/font-awesome-4.7.0.zip | Bin 0 -> 669808 bytes docs/chapter19/lattice.gv | 203 ++++++++++ docs/chapter19/lattice.svg | 691 ++++++++++++++++++++++++++++++++++ docs/chapter19/lattice2.gv | 85 +++++ docs/chapter19/lattice2.svg | 260 +++++++++++++ docs/chapter19/webtcp.min.js | 65 ++++ 9 files changed, 1701 insertions(+) create mode 100644 docs/chapter19/Makefile create mode 100644 docs/chapter19/README.ja.md create mode 100644 docs/chapter19/README.md create mode 100644 docs/chapter19/font-awesome-4.7.0.zip create mode 100644 docs/chapter19/lattice.gv create mode 100644 docs/chapter19/lattice.svg create mode 100644 docs/chapter19/lattice2.gv create mode 100644 docs/chapter19/lattice2.svg create mode 100644 docs/chapter19/webtcp.min.js (limited to 'docs/chapter19') diff --git a/docs/chapter19/Makefile b/docs/chapter19/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter19/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/chapter19/README.ja.md b/docs/chapter19/README.ja.md new file mode 100644 index 00000000..c52ff522 --- /dev/null +++ b/docs/chapter19/README.ja.md @@ -0,0 +1,149 @@ +# 第19章: 命令選択と移植可能なコンパイル + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第18章](../chapter18/README.ja.md) | +[次の章: 第20章](../chapter20/README.ja.md) + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチ上の直線的な Git リビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter19) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter18...linear-chapter19) することもできます。 + +文法は[第18章](../chapter18/18-grammar.ja.md)から変わりません。 + +## 命令選択、レジスタ割り当て、命令エンコーディングにまつわる全体的な問題と開発上の問題 + +命令選択の出力、すなわち理想化された Simple ノードからマシン固有のノードへの対応付けは、実行方法がないと大量にテストするのが困難です。命令選択、レジスタ割り当て、命令エンコーディングの3つすべてが完成するまでは、実行方法が得られません。そのため、エンコーディングの完成前後には、命令選択とレジスタ割り当てで多くのバグが見つかると予想しています。もちろん出力を手作業で調べて明らかな問題は修正しますが、実際にコードを動かせるようになるまで、多くのバグが残ります。 + +つまり、この章で説明する作業に対する更新やバグ修正が、ほかの章に含まれています。 + +## 移植可能なコンパイル + +CPU の移植先ごとに1つの、新しい抽象 `Machine` クラスを追加します。`Machine` は移植先の名前、すべてのレジスタ名、そして *理想* ノードからマシンノードを生成する方法を定義します。さらに、コード生成時にマシン非依存のコンパイラ部分が使う *split* 演算と *jump* の生成も可能にします。 + +各種呼び出し規約を選択できるように、新しい CallingConv 列挙型を追加します。 + +## 命令選択フェーズ + +*大域的コード移動* の前に、新しい *InstructionSelection* コンパイルフェーズを追加します。これは任意ですが、*理想* ノードをマシン固有の派生形に置き換えます。命令選択には対象 CPU 名を渡し、その時点で移植コードを検索して使用します。これによって、少なくとも Java 実装では CPU 移植先を遅延して追加できます。 + +## マシン固有のノード + +`MachNode` インターフェースを実装する「マシン固有」のノードという概念を追加します。`MachNode` ノードは、各命令の入力・出力レジスタ、ビットエンコーディング、利用者向けの表現を定義します。後ほど、局所スケジュールを改善するための機能ユニット情報を追加します。 + +## CodeGen コンパイルドライバの整理 + +さらに多くの静的なグローバル状態を、すべての最上位ドライバ間で受け渡す CodeGen オブジェクトに移します。Node のコンストラクタには渡さないため、idealize() 呼び出しにも渡しません。静的なグローバル状態が必要なケースの大半は、依然としてこれらです。要するに、コンパイラはずっと関数型に近づき、並行コンパイルやマルチスレッドコンパイルに向けて大きく前進します。 + +## 命令選択を通じたメモリの扱い + +パーサーは1つの `$mem` 束縛を保持します。BulkMemPhi は必要に応じてエイリアスを並列の MemPhi に分割し、MemMerge は既定のメモリと明示的なスライスをまとめます。両方のマシン選択器は、これらのノードクラスとエイリアス情報を保持します。メモリの Phi を通常の値の Phi には変換しません。 + +この章では、コンストラクタの非ゼロ値を明示的な Store に変換し、割り当てそのものはゼロ初期化演算として維持します。New は `{ctrl, $mem, size}` を消費し、`{ptr, $mem}` を生成します。その入力は、割り当てる構造体のエイリアスをカバーする部分的な MemMerge です。単一のメモリ結果も、同じエイリアスをカバーします。パーサーは周囲の集合体に無関係なメモリを保持します。割り当てのサイズレジスタは入力2、ポインタ結果は出力0で、メモリにはレジスタがありません。 + +選択されたメモリ演算は、x86 の算術命令や比較命令が Load を吸収しても、フィールドのエイリアスを保持します。そのため大域的スケジューリングは、共通の MemOpNode を通じ、MemMerge 内の該当スライスをたどって反依存関係を見つけます。メモリを結果とする命令は書き手で、ほかのメモリ演算は読み手です。書き手の末尾にある順序付け辺は、レジスタを要求しません。Phi の因数分解で使用する単純な1段階の Load ガードは変更しません。 + +Call は依然としてメモリ全体を消費し、生成します。Call はブロックを終了するため、スケジューリングは引数リストに入力を追加せず、読み取りを Call の前に引き上げます。直接マシン呼び出しは定数の対象を埋め込み、制御、メモリ、引数の入力だけを保持します。 + +## レジスタとレジスタマスク + +`Machines` はレジスタを小さな密な整数として定義します。レジスタ割り当て器は割り当て時にこれらの番号を使います。小さな整数からマシンレジスタへの対応は移植者に任されますが、通常は明らかな1対1の対応があります。X86 では RAX がレジスタ0、RCX がレジスタ1となり、16個の GPR まで続きます。XMM レジスタ番号は16から31です。レジスタ番号は一意でなければなりません。割り当て器はこれによってレジスタを追跡します。 + +レジスタマスククラス `RegMask` は、許可されたレジスタのビット集合を保持します。大半のマシン演算は全レジスタの部分集合に制限され、許可集合を RegMask で記述します。大半の RegMask は、たとえば `Mul` 演算で許可されるレジスタ集合のように不変ですが、割り当て器は可変のレジスタ集合も広範囲に使います。 + +呼び出し規約は多くの固定レジスタを指定し、実際には許可レジスタ集合をかなり「縛る」傾向があります。 + +## SystemV または Win64 呼び出し規約を持つ X86_64_V2 移植 + +`node/cpus/x86_64_v2` ディレクトリには、X86 64 V2 への移植 `x86_64_v2.java` があります。16個の64ビット GPR、16個の XMM レジスタ、X86 フラグをサポートします。理想化された Simple の Sea-of-Nodes から X86 演算を対応付けるパターンマッチャがあります。アドレッシングモードを除けば、理想ノードから X86 演算へほぼ1対1で対応付けます。 + +### 通常の命令選択 + +instSelect フェーズは理想グラフを走査し、理想演算からマシン演算への対応を保持します。先着順で最初に一致したものを採用する、貪欲なパターンマッチを行います。特別な動作のない演算は局所的な検索だけを行います。たとえば `Mul` は X86 の `MulX86` に直接対応します。大半のマッチの右辺は即値定数にでき、即値版（`MulIX86`）に対応します。 + +### アドレッシングモード + +多くの X86 演算では、入力の1つが `Load` なら、メモリを入力にする派生形を使えます。X86 マッチャの専用の `address()` 呼び出しが各種アドレッシングモードを探し、メモリ専用の派生形を構築します。これらは個別に明示する必要がありますが、単純な1行のマッチと、メモリ版を割り当てる1行で済みます。 + +### Compare と Jmp + +Simple の `BoolNode` は `0/1` の値を生成します。X86 では `Cmp/SetXX` という命令列で行います。X86 の `Jxx` は `0/1` ではなく `FLAGS` を受け取るので、`SetXX` を飛ばして直接 `Cmp` を使います。理想 `Bool` を直接使う場合は `SetXX` が必要です。つまり `return a==3` は `CmpX86 RAX,#3; SetEQ RAX; ret;` に対応し、`if( a==3 )` は `CmpX86 RAX,#3; jeq;` に対応します。 + +## RISC-V 移植 + +`node/cpus/riscv` ディレクトリには RISC-V への移植 `riscv.java` があります。32個の64ビット GPR と32個の浮動小数点レジスタをサポートします。理想化された Simple の Sea-of-Nodes から riscv 演算を対応付けるパターンマッチャがあります。現在の対象は `RVA23U64` です。 + +### 通常の命令選択 + +**X86_64_V2** と同様に動作します。riscv には *複雑な* アドレッシングモードがないため、ほとんどの場合は貪欲なパターンマッチを適用しません。特別な動作のない演算は、単純に検索します。 + +### 制限された ISA + +RISC-V は単純なアドレッシングモードとオーバーロードを備える、制限された ISA です。たとえば `lea` はありません。 + +### 分岐 + +`x86_64_v2` の分岐は、フラグを設定する比較命令と、そのフラグを使うジャンプ命令を必要とします。一方 RISC-V は、必要なオペランドをすべて分岐命令そのものに含め、別の比較ステップを不要にします。 + +例: + +``` +beq x10, x11, some_label +``` + +`CBranchRISC` がこの動作を実装します。 + +### R フラグを持たない + +RISC-V には R フラグがありません。同様の機能を得るには、比較結果に応じてレジスタ値を明示的に設定できます。 + +``` +xor a0, a0, a1 +seqz a0, a0 +``` + +最初の `xor` の後、`a0` と `a1` が等しければ `a0` はゼロになります。`seqz` 命令は、前の演算で `a0` がゼロになっていれば `a0` を1に設定します。これは `nodes/cpus/riscv` 移植の `SetRISC` に対応します。 + +### 固定長命令 + +RISC-V の命令長は（ほとんどの場合）32ビット固定であり、エンコーディング側で変位を活用できます。 + +例: + +``` +flw fa5, 0(a0) +flw fa4, 12(a0) +fadd.s fa0, fa5, fa4 +``` + +（`flw` の前にロードは必要ありません。） + +### ABI 名（レジスタ） + +`RISC-V` の汎用レジスタ（`GPR`）は `x0` から `x31`、浮動小数点レジスタは `f0` から `f31` です。 + +読みやすさを高め、呼び出し規約と整合させるため、RISC-V はレジスタの ABI 名を定義し、生の番号よりも直感的な別名を提供します。 + +| レジスタ | 別名 | 用途 | 保存する側 | +|----------|-------|------------------------------|----------| +| x10 | a0 | 関数の引数／戻り値 | 呼び出し側 | +| x11 | a1 | 関数の引数／戻り値 | 呼び出し側 | +| x12 | a2 | 関数の引数 | 呼び出し側 | +| x13 | a3 | 関数の引数 | 呼び出し側 | +| x14 | a4 | 関数の引数 | 呼び出し側 | +| x15 | a5 | 関数の引数 | 呼び出し側 | +| x16 | a6 | 関数の引数 | 呼び出し側 | +| x17 | a7 | 関数の引数 | 呼び出し側 | + +関数に引数を渡すとき、呼び出し側からの最初の8個の引数はレジスタ `a0` から `a7` で渡します。 + +### 浮動小数点値のロード + +現在、浮動小数点定数は、浮動小数点レジスタに変換する前に、まず `integer GPR` にロードします。この処理は RA フェーズで次のように書き換えます。 + +```` +lui a0, 262144 +fmv.w.x fa0, a0 +```` + +非定数値には、GPR と FPR の両方をサポートする、より広いレジスタマスクを使います。この実装は `nodes/cpus/riscv/LoadRISC` にあります。 diff --git a/docs/chapter19/README.md b/docs/chapter19/README.md new file mode 100644 index 00000000..4d9e0572 --- /dev/null +++ b/docs/chapter19/README.md @@ -0,0 +1,236 @@ +# Chapter 19: Instruction Selection and Portable Compilation + +English | [日本語](README.ja.md) + +[Previous: Chapter 18](../chapter18/README.md) | +[Next: Chapter 20](../chapter20/README.md) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter19) 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-chapter18...linear-chapter19) it to the previous chapter. + + +The grammar is unchanged from [Chapter 18](../chapter18/18-grammar.md). + +## Meta-Issues / Code-Dev Issues of Instruction Selection, Register Allocation and Encodings + +The output of Instruction Selection - the mapping from idealized Simple Nodes +to machine-specific ones - 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. + + +## Portable Compilation + +A new abstract `Machine` class is added, one per unique CPU port. `Machine` +defines a name for the port, names for all registers, and how to generate +machine Nodes from *ideal* Nodes. `Machine` also allows generating *split* ops +and *jumps*, both used by the machine independent compiler parts during +code-gen. + +A new CallingConv enum is added, to allow picking between various calling conventions. + +## The Instruction Selection Phase + +A new *InstructionSelection* compile phase is added before *Global Code +Motion*. It is optional, but will replace the *ideal* Nodes with machine- +specific variants. Instruction selection is called with the target CPU name; +the porting code is looked up and used then. This allows the Java +implementation at least the ability to add CPU ports lazily. + + +## Machine Specific Nodes + +We add a notion of "machine specific" Nodes, which implement the `MachNode` +interface. `MachNode` nodes define incoming and outgoing registers for every +instruction, their bit encodings and user representations. Later we'll add +function unit information for a better local schedule. + + +## Clean up CodeGen compile driver + +More static globals move into the CodeGen object, which is passed around at all +the top level drivers. It's not passed into the Node constructors, hence not +into the idealize() calls, which remains the majority of cases needing a static +global. In short the compiler gets a lot more functional, and a big step +towards concurrent or multi-threaded compilation. + + +## Memory through instruction selection + +The parser carries one `$mem` binding. BulkMemPhi splits aliases on demand into +parallel MemPhis, while MemMerge packages a default memory and explicit slices. +Both machine selectors preserve these node classes and their alias information; +they do not turn memory Phis into ordinary value Phis. + +This chapter lowers nonzero constructor values into explicit Stores, keeping the +allocation itself a zeroing operation. New consumes `{ctrl, $mem, size}` and +produces `{ptr, $mem}`. Its input is a partial MemMerge covering the allocated +struct's aliases; its single memory result covers those same aliases. The parser +preserves unrelated memory in the surrounding aggregate. The allocation's size +register is input 2, its pointer result is output 0, and memory has no register. + +Selected memory operations retain their field alias even when an x86 arithmetic +or comparison instruction absorbs a Load. Global scheduling therefore finds +anti-dependencies through the common MemOpNode, following the relevant slice +through MemMerge. Memory-result instructions are writers; other memory operations +are readers. Trailing ordering edges on writers impose no register requirement. +The simple one-step Load guard used when factoring Phis is unchanged. + +Calls still consume and produce whole memory. They terminate their blocks, so +scheduling raises a read before a Call without adding inputs to its argument +list. Direct machine calls embed their constant target and retain only control, +memory, and argument inputs. + + +## Registers and Register Masks + +`Machines` define registers as small dense integers. The Register Allocator +will use these numbers when allocating. The mappings from small integers to +machine registers is up to the porter, but there's usually an obvious +one-to-one. For the X86, 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. + +A `RegMask` Register Mask class holds onto bitsets of allowed registers. Most +machine ops are limited to some subset of all registers, and the allowed sets +are written as a RegMask. Most RegMasks are immutable, e.g. the set of allowed +registers into a `Mul` operation, but the register allocator will make +extensive use of mutable register sets. + +Calling conventions dictate many fixed registers, and in practice tend to +really "bind up" the set of allowed registers. + + +## An X86_64_V2 port, with SystemV or Win64 calling conventions + +In the `node/cpus/x86_64_v2` directory is a `x86_64_v2.java` port to an X86 64 +V2. This port supports 16 64-bit GPRs, 16 XMM registers and the X86 flags. +There is a pattern matcher for matching X86 ops from idealized Simple +Sea-of-Nodes. Except for the addressing modes pattern matcher matches nearly +one-for-one X86 ops from ideal nodes. + +### Normal instruction selection + +The instSelect phase walks the ideal graph, and maintains a mapping +from ideal-to-machine ops. It does a greedy pattern match, first come first +match. Ops without any special behavior simply do the local lookup e.g. an +`Mul` exactly matches to an X86 `MulX86` directly. The RHS of most matches can +be an immediate constant, matching an immediate-flavored version (`MulIX86`). + +### Addressing Modes + +For many X86 operations, if one of the inputs is a `Load`, the X86 can use an +op-from-memory variant. There's a specific `address()` call in the X86 matcher +that looks for the various kinds of addressing modes and will build memory- +specific variations. These all need to be called out specifically, but with a +simple one-line match and one-line allocation of the memory version. + +### Compare vs Jmp + +In simple, a `BoolNode` produces a `0/1` value. On an X86 this is done with +the `Cmp/SetXX` opcode sequence. The X86 `Jxx` takes in `FLAGS` and not a +`0/1`, so the `Jxx` will skip the `SetXX` and directly use the `Cmp`. Using +the ideal `Bool` directly will require the `SetXX`. i.e. `return a==3` will +match to a `CmpX86 RAX,#3; SetEQ RAX; ret;` whereas a `if( a==3 )` will match +to a `CmpX86 RAX,#3; jeq;` + +## RISC-V port + +In the `node/cpus/riscv` directory is a `riscv.java` port to a RISC-V. +This port supports 32 64-bit GPRs, and 32 floating-point registers. +There is a pattern matcher for matching riscv ops from idealized Simple +Sea-of-Nodes. Currently, we are targeting `RVA23U64`. + +### Normal instruction selection + +Works the same way as **X86_64_V2**, since riscv doesn't have *complex* addressing modes, greedy +pattern matching doesn't apply to most of the cases. Ops without any special behavior simply do the lookup. + +### Restricted ISA +RISC-V is a restricted ISA with simple addressing modes and overloads. +E.g `lea` is not present. + + +### Branching + +In `x86_64_v2`, branching requires a comparison instruction to set flags, +followed by a jump instruction that uses those flags. In contrast, RISC-V +includes all necessary operands within the branch instruction itself, +eliminating the need for a separate comparison step. + +E.g +``` +beq x10, x11, some_label +``` + +`CBranchRISC` implements this behavior. + +### No R-Flags + +No R-flags exist in RISC-V. To obtain similar functionality: +We can set the value of registers based on the result of the comparison this way explicitly. +``` +xor a0, a0, a1 +seqz a0, a0 +``` +After the first `xor` - `a0` will be zero if `a0` and `a1` are equal. +The `seqz` instruction will set `a0` to 1 if `a0` is zero from the previous operation. +This matches `SetRISC` in the `nodes/cpus/riscv` port. + +### Fixed instruction length + +RISC-V instructions have fixed length of 32 bits(in most cases) which means +that we can benefit from displacements in the encoding side. + +E.g +``` +flw fa5, 0(a0) +flw fa4, 12(a0) +fadd.s fa0, fa5, fa4 +``` +(No load is needed prior to `flw`) + +### ABI names(registers) +In `RISC-V`, general-purpose registers (`GPRs`) range from `x0` to `x31`, and floating-point registers range +from `f0` to `f31`. + +To enhance readability and align with calling conventions, RISC-V defines ABI names for registers, providing more intuitive aliases +instead of raw register numbers. + + + +| Register | Alias | Usage | Saved By | +|----------|-------|------------------------------|----------| +| x10 | a0 | Function arguments/return values | Caller | +| x11 | a1 | Function arguments/return values | Caller | +| x12 | a2 | Function arguments | Caller | +| x13 | a3 | Function arguments | Caller | +| x14 | a4 | Function arguments | Caller | +| x15 | a5 | Function arguments | Caller | +| x16 | a6 | Function arguments | Caller | +| x17 | a7 | Function arguments | Caller | + +When passing in arguments to a function, the first 8 arguments from the caller are passed in registers `a0` to `a7`. + +### Load floats +Currently, floating-point constants are first loaded into an `integer GPR` before being converted into a floating-point register. +This process is rewritten in the RA stage as: + + +```` +lui a0, 262144 +fmv.w.x fa0, a0 +```` +For non-constant values, we use a broader register mask that +supports both GPRs and FPRs. This implementation can be found in: +`nodes/cpus/riscv/LoadRISC`. + + + + + diff --git a/docs/chapter19/font-awesome-4.7.0.zip b/docs/chapter19/font-awesome-4.7.0.zip new file mode 100644 index 00000000..b6bdb4bd Binary files /dev/null and b/docs/chapter19/font-awesome-4.7.0.zip differ diff --git a/docs/chapter19/lattice.gv b/docs/chapter19/lattice.gv new file mode 100644 index 00000000..8661082d --- /dev/null +++ b/docs/chapter19/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=<⊤>, fillcolor=black, fontcolor=white]; + BOT [label=<⊥>, fillcolor=black, fontcolor=white]; + + // ---------------------- + // Control + XCTRL [label=<⊤:ctrl>, fillcolor=yellow, shape=oval]; + CTRL [label=<⊥:ctrl>, fillcolor=yellow, shape=oval]; + + TOP -> XCTRL; + XCTRL -> CTRL; + CTRL -> BOT; + + // ---------------------- + // Integers + INT_TOP [label=<⊤:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<⊥: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 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=<⊤:flt>, fillcolor=aqua, shape=oval]; + FLT_BOT [label=<⊥: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=< + + + +
*ptr
struct
+ >]; + PTR0 [shape=none, fillcolor=none, label=< + + + +
*ptr?
struct
+ >]; + + TOP -> PTR; + PTR -> PTR0; + PTR0 -> BOT; + + // ---------------------- + // Structs + STRUCT_TOP [label=<⊤:struct>, fillcolor=lightgreen, shape=oval]; + STRUCT_BOT [label=<⊥:struct>, fillcolor=lightgreen, shape=oval]; + + STRUCT_S1 [shape=none, fillcolor=none, label=< + + +
fieldint/ptr
+ >]; + STRUCT_S2 [shape=none, fillcolor=none, label=< + + + +
fieldint/ptr
fieldint/ptr
+ >]; + STRUCT_SN [shape=none, fillcolor=none, label=< + + + + +
fieldint/ptr
... int/ptr
fieldint/ptr
+ >]; + + + 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=<⊤:mem>, fillcolor=blue, fontcolor=white, shape=oval]; + MEM_BOT [label=<⊥: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=<⊤:tuple>, fillcolor=pink, shape=oval]; + TUPLE_BOT [label=<⊥:tuple>, fillcolor=pink, shape=oval]; + + TUPLE1 [shape=none, fillcolor=none, label=< + + + +
Tuple
type
+ >]; + TUPLE2 [shape=none, fillcolor=none, label=< + + + + +
Tuple
type
type
+ >]; + TUPLEN [shape=none, fillcolor=none, label=< + + + + + +
Tuple
type
...
type
+ >]; + + + 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/chapter19/lattice.svg b/docs/chapter19/lattice.svg new file mode 100644 index 00000000..030f4826 --- /dev/null +++ b/docs/chapter19/lattice.svg @@ -0,0 +1,691 @@ + + + + + + +Lattice + + + +TOP + +⊤ + + + +XCTRL + +⊤ +:ctrl + + + +TOP->XCTRL + + + + + +INT_TOP + +⊤ +:int + + + +TOP->INT_TOP + + + + + +FLT_TOP + +⊤ +:flt + + + +TOP->FLT_TOP + + + + + +PTR + + + +*ptr + + +struct + + + +TOP->PTR + + + + + +STRUCT_TOP + +⊤ +:struct + + + +TOP->STRUCT_TOP + + + + + +MEM_TOP + +⊤ +:mem + + + +TOP->MEM_TOP + + + + + +TUPLE_TOP + +⊤ +:tuple + + + +TOP->TUPLE_TOP + + + + + +BOT + +⊥ + + + +CTRL + +⊥ +:ctrl + + + +XCTRL->CTRL + + + + + +CTRL->BOT + + + + + +INT_HI + +[min>max] + + + +INT_TOP->INT_HI + + + + + +INT_BOT + +⊥ +:int + + + +INT_BOT->BOT + + + + + +INT_XBOOL + +[1...0] + + + +INT_HI->INT_XBOOL + + + + + +INT_CON + +constants + + + +INT_HI->INT_CON + + + + + +INT_CON0 + +0 + + + +INT_XBOOL->INT_CON0 + + + + + +INT_CON1 + +1 + + + +INT_XBOOL->INT_CON1 + + + + + +INT_LO + +[min<max] + + + +INT_CON->INT_LO + + + + + + +INT_BOOL + +[0...1] + + + +INT_CON0->INT_BOOL + + + + + + +INT_CON1->INT_BOOL + + + + + +INT_BOOL->INT_LO + + + + + +INT_LO->INT_BOT + + + + + +FLT_CON64 + +64b consts +[excludes +32b consts] + + + +FLT_TOP->FLT_CON64 + + + + + +FLT_CONPI + +3.14159... + + + +FLT_TOP->FLT_CONPI + + + + + +FLT_X32 + +~f32 + + + +FLT_TOP->FLT_X32 + + + + + +FLT_BOT + +⊥ +:flt + + + +FLT_BOT->BOT + + + + + +FLT_CON64->FLT_BOT + + + + + +FLT_CON32 + +32b consts + + + + +FLT_32 + +f32 + + + +FLT_CON32->FLT_32 + + + + + +FLT_CONPI->FLT_BOT + + + + + + +FLT_X32->FLT_CON32 + + + + + +FLT_CON0 + +0. + + + +FLT_X32->FLT_CON0 + + + + + + +FLT_CON0->FLT_32 + + + + + +FLT_32->FLT_BOT + + + + + +PTR0 + + + +*ptr? + + +struct + + + +PTR->PTR0 + + + + + +PTR0->BOT + + + + + +STRUCT_S1 + + + +field + + + + + + + + +int/ptr + + + +STRUCT_TOP->STRUCT_S1 + + + + + +STRUCT_S2 + + + +field + + + + + + + + +int/ptr + + +field + + + + + + + + +int/ptr + + + +STRUCT_TOP->STRUCT_S2 + + + + + +STRUCT_SN + + + +field + + + + + + + + +int/ptr + + +...   + + + + + + + + +int/ptr + + +field + + + + + + + + +int/ptr + + + +STRUCT_TOP->STRUCT_SN + + + + + +STRUCT_BOT + +⊥ +:struct + + + +STRUCT_BOT->BOT + + + + + +STRUCT_S1->STRUCT_BOT + + + + + + +STRUCT_S2->STRUCT_BOT + + + + + + +STRUCT_SN->STRUCT_BOT + + + + + +MEM_ALIAS1 + +#1 + + + +MEM_TOP->MEM_ALIAS1 + + + + + +MEM_ALIASDOTS + +... + + + +MEM_TOP->MEM_ALIASDOTS + + + + + +MEM_ALIASN + +#n + + + +MEM_TOP->MEM_ALIASN + + + + + +MEM_BOT + +⊥ +:mem + + + +MEM_BOT->BOT + + + + + +MEM_ALIAS1->MEM_BOT + + + + + + +MEM_ALIASDOTS->MEM_BOT + + + + + + +MEM_ALIASN->MEM_BOT + + + + + +TUPLE1 + + + +Tuple + + +type + + + +TUPLE_TOP->TUPLE1 + + + + + +TUPLE2 + + + +Tuple + + +type + + +type + + + +TUPLE_TOP->TUPLE2 + + + + + +TUPLEN + + + +Tuple + + +type + + +... + + +type + + + +TUPLE_TOP->TUPLEN + + + + + +TUPLE_BOT + +⊥ +:tuple + + + +TUPLE_BOT->BOT + + + + + +TUPLE1->TUPLE_BOT + + + + + +TUPLE2->TUPLE_BOT + + + + + +TUPLEN->TUPLE_BOT + + + + + diff --git a/docs/chapter19/lattice2.gv b/docs/chapter19/lattice2.gv new file mode 100644 index 00000000..6aa37fa0 --- /dev/null +++ b/docs/chapter19/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/chapter19/lattice2.svg b/docs/chapter19/lattice2.svg new file mode 100644 index 00000000..857bca2d --- /dev/null +++ b/docs/chapter19/lattice2.svg @@ -0,0 +1,260 @@ + + + + + + +Lattice + + + +TOP + +~scalar ++int+tmp+0 + + + +PTRHQ + +~tmp ++tmp+0 + + + +TOP->PTRHQ + + + + + +VALH_ + +~nscalar ++int+tmp + + + +TOP->VALH_ + + + + + + +INTHQ + +~int ++int+0 + + + +TOP->INTHQ + + + + + + + +PTRH_ + +~ntmp ++tmp + + + +PTRHQ->PTRH_ + + + + + + +NILX_ + +~nil +[int,tmp]+0 + + + +PTRHQ->NILX_ + + + + + + +VALH_->PTRH_ + + + + + +INTH_ + +~nint ++int + + + +VALH_->INTH_ + + + + + +NIL__ + +nil +[+int+tmp],0 + + + +VALH_->NIL__ + + + + + +VALL_ + +nscalar +int,tmp + + + + +INTHQ->INTH_ + + + + + + +INTHQ->NILX_ + + + + + + + +PTRL_ + +ntmp +tmp + + + +PTRH_->PTRL_ + + + + + + +INTL_ + +nint +int + + + +INTH_->INTL_ + + + + + + + +NILX_->VALL_ + + + + + +PTRL0 + +tmp +tmp,0 + + + +NIL__->PTRL0 + + + + + +INTL0 + +int +int,0 + + + +NIL__->INTL0 + + + + + +PTRL_->PTRL0 + + + + + + +PTRL_->VALL_ + + + + + +INTL_->VALL_ + + + + + +INTL_->INTL0 + + + + + + + +BOT + +scalar +int,tmp,0 + + + +PTRL0->BOT + + + + + + +VALL_->BOT + + + + + + +INTL0->BOT + + + + + diff --git a/docs/chapter19/webtcp.min.js b/docs/chapter19/webtcp.min.js new file mode 100644 index 00000000..bf23ee5a --- /dev/null +++ b/docs/chapter19/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;qc?"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=a};c.countRTO=function(a){var b;return 100b;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