From 53308013c3f2bad224208805df0f54416067b8be Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 24 Apr 2025 14:38:36 -0700 Subject: Chapter 21: Instruction Encoding and ELF MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: godalming123 <68993177+godalming123@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: tejasae-afk Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Tejas Attarde <201814263+tejasae-afk@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- docs/chapter21/21-grammar.ja.md | 141 ++++++ docs/chapter21/21-grammar.md | 141 ++++++ docs/chapter21/Makefile | 12 + docs/chapter21/README.ja.md | 120 +++++ docs/chapter21/README.md | 170 +++++++ docs/chapter21/encoding-reference.ja.md | 776 +++++++++++++++++++++++++++++++ docs/chapter21/encoding-reference.md | 798 ++++++++++++++++++++++++++++++++ docs/chapter21/font-awesome-4.7.0.zip | Bin 0 -> 669808 bytes docs/chapter21/ifg_trim.pdf | Bin 0 -> 155190 bytes docs/chapter21/lattice.gv | 203 ++++++++ docs/chapter21/lattice.svg | 691 +++++++++++++++++++++++++++ docs/chapter21/lattice2.gv | 85 ++++ docs/chapter21/lattice2.svg | 260 +++++++++++ docs/chapter21/pardoe.docx | Bin 0 -> 22583 bytes docs/chapter21/webtcp.min.js | 65 +++ 15 files changed, 3462 insertions(+) create mode 100644 docs/chapter21/21-grammar.ja.md create mode 100644 docs/chapter21/21-grammar.md create mode 100644 docs/chapter21/Makefile create mode 100644 docs/chapter21/README.ja.md create mode 100644 docs/chapter21/README.md create mode 100644 docs/chapter21/encoding-reference.ja.md create mode 100644 docs/chapter21/encoding-reference.md create mode 100644 docs/chapter21/font-awesome-4.7.0.zip create mode 100644 docs/chapter21/ifg_trim.pdf create mode 100644 docs/chapter21/lattice.gv create mode 100644 docs/chapter21/lattice.svg create mode 100644 docs/chapter21/lattice2.gv create mode 100644 docs/chapter21/lattice2.svg create mode 100644 docs/chapter21/pardoe.docx create mode 100644 docs/chapter21/webtcp.min.js (limited to 'docs') diff --git a/docs/chapter21/21-grammar.ja.md b/docs/chapter21/21-grammar.ja.md new file mode 100644 index 00000000..8cb8f27b --- /dev/null +++ b/docs/chapter21/21-grammar.ja.md @@ -0,0 +1,141 @@ +# 第21章の文法 + +[English](21-grammar.md) | 日本語 + +```antlrv4 +grammar SimpleLanguage; + +// Name lookup, assignable operands, type compatibility, and access permissions +// are checked by the compiler in addition to these syntax rules. +program : statement* EOF ; + +block : '{' statement* '}' ; + +statement + : block + | returnStatement + | ifStatement + | whileStatement + | forStatement + | breakStatement + | continueStatement + | structDeclaration + | declaration ';' + | assignment ';' + | ';' + ; + +returnStatement : 'return' assignment ';' ; +ifStatement : 'if' '(' assignment ')' statement ('else' statement)? ; +whileStatement : 'while' '(' assignment ')' statement ; +breakStatement : 'break' ';' ; +continueStatement : 'continue' ';' ; + +forStatement + : 'for' '(' (declaration | assignment)? ';' assignment? ';' assignment? ')' statement + ; + +structDeclaration : 'struct' IDENTIFIER block ';' ; + +declaration : declarationType binding (',' binding)* ; +declarationType : type | 'var' | 'val' ; +binding : bindingModifier? IDENTIFIER ('=' initializer)? ; +bindingModifier : '!' | '~' ; +initializer : assignment ; + +// The prefix qualifies the named struct reference, not an enclosing array. +// Each [] / [~] suffix qualifies its own array layer. ? requires a reference. +type + : functionType + | primitiveType typeSuffix* + | accessModifier? typeName typeSuffix* + ; +accessModifier : '!' | '~' ; +typeSuffix : '?' | '[]' | '[~]' ; +typeName : IDENTIFIER ; + +primitiveType + : 'int' | 'i8' | 'i16' | 'i32' | 'i64' + | 'u1' | 'u8' | 'u16' | 'u32' | 'byte' | 'bool' + | 'flt' | 'f32' | 'f64' + ; + +assignment : expression (assignmentOperator assignment)? ; +assignmentOperator + : '=' | '+=' | '-=' | '*=' | '/=' | '&=' | '|=' | '^=' + | '<<=' | '>>=' | '>>>=' + ; + +expression : bitwiseExpression ('?' assignment (':' assignment)?)? ; + +bitwiseExpression + : comparisonExpression (('&' | '|' | '^') comparisonExpression)* + ; + +comparisonExpression + : shiftExpression (('==' | '!=' | '<' | '<=' | '>' | '>=') shiftExpression)* + ; + +shiftExpression + : additiveExpression (('<<' | '>>' | '>>>') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-' | '!') unaryExpression + | updateOperator IDENTIFIER + | postfixExpression + ; + +// Prefix updates require a local name; postfix updates also allow fields +// and array elements. All updates require an assignable operand. +updateOperator : '++' | '--' ; +postfixExpression : primaryExpression postfixSuffix* updateOperator? ; +postfixSuffix : '.' IDENTIFIER | '[' assignment ']' | '#' | callSuffix ; + +primaryExpression + : INTEGER_LITERAL + | FLOAT_LITERAL + | 'true' + | 'false' + | 'null' + | IDENTIFIER + | '(' assignment ')' + | newExpression + | functionExpression + ; + +// A function is an expression bound with an ordinary declaration. +// Its last statement supplies the implicit result; return can exit earlier. +functionExpression : '{' parameterList? '->' statement* '}' ; +parameterList : (parameter ','?)+ ; +parameter : type bindingModifier? IDENTIFIER ; + +// Function types have unnamed, space-separated argument types. +// {int} is the zero-argument type; its function expression still uses ->. +functionType + : '{' type+ '->' type '}' '?'? + | '{' type '}' '?'? + ; + +callSuffix : '(' argumentList? ')' ; +argumentList : assignment (',' assignment)* ','? ; + +// Struct initialization uses a block; array allocation supplies a length. +newExpression : 'new' type ('[' assignment ']' | block)? ; + +INTEGER_LITERAL : '0' | [1-9] DIGIT* ; +FLOAT_LITERAL : DIGIT+ ('.' DIGIT* ('e' DIGIT+)? | 'e' '-'? DIGIT+) ; +IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ; +fragment NON_DIGIT : [a-zA-Z_] ; +fragment DIGIT : [0-9] ; +WHITESPACE : [ \t\r\n]+ -> skip ; +LINE_COMMENT : '//' ~[\r\n]* -> skip ; +``` diff --git a/docs/chapter21/21-grammar.md b/docs/chapter21/21-grammar.md new file mode 100644 index 00000000..111957a1 --- /dev/null +++ b/docs/chapter21/21-grammar.md @@ -0,0 +1,141 @@ +# Grammar for Chapter 21 + +English | [日本語](21-grammar.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +// Name lookup, assignable operands, type compatibility, and access permissions +// are checked by the compiler in addition to these syntax rules. +program : statement* EOF ; + +block : '{' statement* '}' ; + +statement + : block + | returnStatement + | ifStatement + | whileStatement + | forStatement + | breakStatement + | continueStatement + | structDeclaration + | declaration ';' + | assignment ';' + | ';' + ; + +returnStatement : 'return' assignment ';' ; +ifStatement : 'if' '(' assignment ')' statement ('else' statement)? ; +whileStatement : 'while' '(' assignment ')' statement ; +breakStatement : 'break' ';' ; +continueStatement : 'continue' ';' ; + +forStatement + : 'for' '(' (declaration | assignment)? ';' assignment? ';' assignment? ')' statement + ; + +structDeclaration : 'struct' IDENTIFIER block ';' ; + +declaration : declarationType binding (',' binding)* ; +declarationType : type | 'var' | 'val' ; +binding : bindingModifier? IDENTIFIER ('=' initializer)? ; +bindingModifier : '!' | '~' ; +initializer : assignment ; + +// The prefix qualifies the named struct reference, not an enclosing array. +// Each [] / [~] suffix qualifies its own array layer. ? requires a reference. +type + : functionType + | primitiveType typeSuffix* + | accessModifier? typeName typeSuffix* + ; +accessModifier : '!' | '~' ; +typeSuffix : '?' | '[]' | '[~]' ; +typeName : IDENTIFIER ; + +primitiveType + : 'int' | 'i8' | 'i16' | 'i32' | 'i64' + | 'u1' | 'u8' | 'u16' | 'u32' | 'byte' | 'bool' + | 'flt' | 'f32' | 'f64' + ; + +assignment : expression (assignmentOperator assignment)? ; +assignmentOperator + : '=' | '+=' | '-=' | '*=' | '/=' | '&=' | '|=' | '^=' + | '<<=' | '>>=' | '>>>=' + ; + +expression : bitwiseExpression ('?' assignment (':' assignment)?)? ; + +bitwiseExpression + : comparisonExpression (('&' | '|' | '^') comparisonExpression)* + ; + +comparisonExpression + : shiftExpression (('==' | '!=' | '<' | '<=' | '>' | '>=') shiftExpression)* + ; + +shiftExpression + : additiveExpression (('<<' | '>>' | '>>>') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-' | '!') unaryExpression + | updateOperator IDENTIFIER + | postfixExpression + ; + +// Prefix updates require a local name; postfix updates also allow fields +// and array elements. All updates require an assignable operand. +updateOperator : '++' | '--' ; +postfixExpression : primaryExpression postfixSuffix* updateOperator? ; +postfixSuffix : '.' IDENTIFIER | '[' assignment ']' | '#' | callSuffix ; + +primaryExpression + : INTEGER_LITERAL + | FLOAT_LITERAL + | 'true' + | 'false' + | 'null' + | IDENTIFIER + | '(' assignment ')' + | newExpression + | functionExpression + ; + +// A function is an expression bound with an ordinary declaration. +// Its last statement supplies the implicit result; return can exit earlier. +functionExpression : '{' parameterList? '->' statement* '}' ; +parameterList : (parameter ','?)+ ; +parameter : type bindingModifier? IDENTIFIER ; + +// Function types have unnamed, space-separated argument types. +// {int} is the zero-argument type; its function expression still uses ->. +functionType + : '{' type+ '->' type '}' '?'? + | '{' type '}' '?'? + ; + +callSuffix : '(' argumentList? ')' ; +argumentList : assignment (',' assignment)* ','? ; + +// Struct initialization uses a block; array allocation supplies a length. +newExpression : 'new' type ('[' assignment ']' | block)? ; + +INTEGER_LITERAL : '0' | [1-9] DIGIT* ; +FLOAT_LITERAL : DIGIT+ ('.' DIGIT* ('e' DIGIT+)? | 'e' '-'? DIGIT+) ; +IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ; +fragment NON_DIGIT : [a-zA-Z_] ; +fragment DIGIT : [0-9] ; +WHITESPACE : [ \t\r\n]+ -> skip ; +LINE_COMMENT : '//' ~[\r\n]* -> skip ; +``` diff --git a/docs/chapter21/Makefile b/docs/chapter21/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter21/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/chapter21/README.ja.md b/docs/chapter21/README.ja.md new file mode 100644 index 00000000..058e7cff --- /dev/null +++ b/docs/chapter21/README.ja.md @@ -0,0 +1,120 @@ +# 第21章: 命令エンコーディングと ELF + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第20章](../chapter20/README.ja.md) | +[次の章: 第22章](../chapter22/README.ja.md) + +この章では、スケジューリングとレジスタ割り当てを終えたグラフを実行可能な命令に変換します。各マシンノードがバイトを書き込み、コンパイラがブロックを配置し、局所参照を解決し、リンカ向けの ELF オブジェクトを出力します。これで生成コードを実行できるため、命令選択、レジスタ割り当て、呼び出し規約も一緒にテストできます。 + +直線的なリビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter21) を読み、[第20章と比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter20...linear-chapter21) することもできます。 + +この章の[完全な言語文法](21-grammar.ja.md)はこちらです。 + +## マシンノードからバイトへ + +命令選択は演算とレジスタ制約を選びます。レジスタ割り当ては物理レジスタとスタックスロットを割り当てます。その後、エンコーディングがオペコード、割り当て済みレジスタ、即値オペランドを命令バイトへ組み合わせます。この時点で命令は別のレジスタを選べません。周囲の命令が、すでに割り当て器の選択に依存しているためです。 + +[Encoding.java](../../src/main/java/com/seaofnodes/simple/codegen/Encoding.java) がバイトストリームを所有し、各ノードのオフセットとエンコード後の長さを記録します。ドライバは次を行います。 + +1. 基本ブロックを配置し、必要に応じて分岐を挿入または反転する。 +2. スケジュール順に `MachNode.encoding(Encoding)` を呼ぶ。 +3. 短い命令形式と長い命令形式を確定する。 +4. このコンパイル内に対象がある参照を修正する。 + +補助関数 `add1`、`add2`、`add4`、`add8` は、リトルエンディアンの値を追加します。エンコーディング関数は `Encoding.reg` で割り当て済みレジスタを得ます。スタックオペランドは、保存レジスタや出力引数の領域も含む、関数のフレーム配置を使います。彩色成功だけでは呼び出し規約の正しさは証明できません。生成プログラムは呼び出し側の値も保存しなければなりません。 + +## 3つの命令セット + +対象はこのドライバを共有します。マシンノードがコンパイラのオペランドを解決し、共有の [ISA エンコーダ](../../isa/README.md) を呼びます。 + +| 対象 | 主なエンコーディング上の課題 | +|---|---| +| RISC-V | 命令語内のレジスタと即値のフィールド。大きい定数とアドレスには複数命令が必要。 | +| AArch64 | レジスタ形式、制限された即値エンコーディング、複数命令による定数構築。 | +| x86-64 | 可変命令長、レジスタ接頭辞、アドレッシング形式、短い分岐と長い分岐。 | + +たとえば小さな整数は命令に直接収まる一方、大きな整数には複数命令や定数プールからのロードが必要なことがあります。その結果、固定幅命令を持つ対象でも、マシンノードによって異なるバイト数を出力できます。 + +[エンコーディングリファレンス](encoding-reference.ja.md) は、詳細なビット配置、具体例、ISA リンクを保持しています。個々の命令実装ではそれらの詳細が重要ですが、ここで説明するコンパイラのパイプラインは変わりません。マシンノードの接続は [node/cpus](../../src/main/java/com/seaofnodes/simple/node/cpus) にあります。共有の [X86 エンコーダ](../../isa/src/main/java/com/seaofnodes/isa/X86.java) が x86 のバイト出力を所有し、[Arm64](../../isa/src/main/java/com/seaofnodes/isa/Arm64.java) と [RiscV](../../isa/src/main/java/com/seaofnodes/isa/RiscV.java) は命令語を詰めます。 + +たとえば `AddX86` はオペコード `0x03` を選びます。その基底 `RegX86` は割り当て済みの2レジスタを読み、`X86.reg(enc,opcode(),dst,src)` を呼びます。共有メソッドは REX.W、オペコード、ModRM を `Encoding` のバイトバッファへ直接書き込みます。`add r9,r10` のバイト列は `4d 03 ca` です。レジスタ制約と2アドレスの要求は、この章のマシンノードに残ります。これによって、ADD を使う判断と、命令の固定されたビット表現を分離します。 + +ロードも同じ境界を使います。この章は、型と割り当て済みオペランドから、幅、符号拡張、レジスタバンクを解決します。`X86.load` はそれらの情報と具体的なアドレスを受け取り、この章のグラフや型の束に依存しません。後の章はコンパイラが進化しても、これらのエンコーディングを再利用します。 + +ARM と RISC-V の実行テストも `isa/src/test-support` の評価器を再利用します。この章のテストハーネスがメモリイメージを準備してリンクし、評価器がそのバイト列を実行します。こうして命令の意味を1か所に保持しつつ、イメージ構築は各章のコンパイラに従います。評価器はテストとともにコンパイルします。Make のリリース jar は、引き続きコンパイラとテストハーネスの両方を同梱します。 + +## 再配置と ELF + +前方分岐は、最初にバイトを書き込む時点では最終的な変位を知りません。対象のオフセットは、間にあるすべてのエンコーディングに依存します。別の分岐を短縮・拡張すると、対象が再び動く場合があります。配置走査が命令サイズを確定してから、局所再配置が最終的な変位を修正します。 + +外部参照には、後での修正が必要です。たとえばコンパイラは、リンカが `malloc` をどこへ配置するか知らなくても、その呼び出しを出力できます。オブジェクトファイルはシンボル、修正位置、再配置種別を記録します。種別は命令と一致しなければなりません。x86 の呼び出し変位と、分割された RISC-V のアドレスは別のフィールドを占めるので、同じ修正演算は使えません。 + +[ElfFile.java](../../src/main/java/com/seaofnodes/simple/codegen/ElfFile.java) は、オブジェクトのコード、データ、シンボル、再配置記録を書き込みます。大きな定数も外部呼び出しと同じ配置問題を生じます。最終的なアドレスを、それらをロードする命令に接続しなければなりません。局所再配置とオブジェクトファイル再配置は、参照を正しくするという同じ責務の2段階です。 + +## 結果の実行 + +第11章の遅延メモリ分割が、エンコーディングまで引き継がれます。パラメータ、呼び出し、戻りはメモリ全体を運び、`BulkMemPhi`、`MemPhi`、`MemMerge` が各関数内の正確なエイリアスを発見します。New は `{ctrl, $mem, size}` を消費し、`{ptr, $mem}` を生成します。そのメモリは割り当てた構造体のエイリアスを覆い、周囲のマージは無関係なエイリアスを保持します。非ゼロ初期化は依然として明示的な Store を使います。メモリノードと順序付け辺はレジスタを必要としません。 + +スケジューリングは集合体を通じてエイリアスをたどり、対応する Store、割り当て、呼び出しの前に読み取りを順序付けます。Call は順序付けオペランドを追加せず、引数リストを保持します。合成されたループ出口は、エイリアスごとに正確なメモリを集めます。 + +実行の回帰テストは、コンストラクタ、インライン化されない呼び出しと再帰呼び出し、インライン化、配列更新を、ネイティブ x86 と両エミュレータで検証します。整数が XMM にある場合もあるため、全幅の x86 ロードはエンコーディング選択時に割り当て済みのレジスタバンクを使います。ARM エミュレーションは、これらの確認で使う大きな定数に対する MOVZ/MOVK の半語構築を処理します。 + +`make tests` は、生成 x86 コードをリンクして実行する C ハーネスと、RISC-V/AArch64 エミュレータの確認を含みます。結果とスピル数の両方を比較します。ネイティブプロセスの失敗は完全な終了ステータスを保持します。エミュレータの確認は、自身の結果メモリを読まなければなりません。別の対象の結果と一致するだけでは不十分です。 + +`make spill-stats` を実行すると、アサーションを有効にして同じテストから割り当てを収集します。各テスト／CPU／ABI を報告してから、群の合計を表示します。スピルの期待値との不一致は、残りの対象や実行確認を省略せず記録します。そのような不一致が1つでもあればコマンドは失敗します。構造的な割り当て器の回帰テストはスピル合計から除外します。 + +## RegAlloc の改良: コピーの除去 + +分割は2つの生存区間間にコピーを挿入します。両方を安全に1区間へまとめられるなら、彩色前にコピーを除去できます。[Coalesce.java](../../src/main/java/com/seaofnodes/simple/codegen/Coalesce.java) は、区間が干渉しないことを確認し、許可レジスタマスクの共通部分を取り、隣接ノードをまとめます。結果の隣接ノード数が利用可能レジスタ数より小さいときだけ併合します。この単純で保守的な規則は、各隣接ノードが異なるレジスタを取っても、色の選択肢を残します。 + +併合は隣接するノードの隣接リストも更新し、削除したコピーへの代表参照を除去します。拒否された併合は元の隣接リストを復元します。マスクの互換性だけでは不十分です。同時に生存する2値は、両方が同じレジスタを許しているだけでは共有できません。 + +彩色後にも、直後の命令に1つだけ使用があるコピーは、そのオペランドがコピー元レジスタを受け入れ、2アドレスのオペランドでなければ除去できます。たとえば `mov rpc=s8; st1 [rpc+4],s1` は `st1 [s8+4],s1` になります。隣接していることで、間にコピー元を上書きするものがないと証明できます。Phi と制御フローの使用側は除外します。この局所整理はスピル選択を変更せず、別の CFG 解析をせずに併合を補完します。 + +互換性のある再実体化や、破壊を考慮するコピー再利用など、第20章の合法性と進捗の修正も引き継ぎます。第21章はネイティブフレームと ABI のサポートを保持します。より強い色バイアスと安いスピルの順位付けは第22章、多数の使用のグループ化は第23章、低頻度側を先にするループ分割は第24章、面積／コストの順位付けは第25章に残します。 + +以下は **この章のコンパイラ** を使い、最適化器の既定シード123で Windows x86-64 上で測定した合計です。分割はレジスタ移動を含む残存 `SplitNode` であり、必ずしもメモリスピルではありません。重み付き数は各分割に `8^loopDepth` を掛けます。 + +| プログラム群 | コンパイル数 | 残存する移動 | ループ重み付き移動 | +|---|---:|---:|---:| +| 第20章 | 39 | 380 | 576 | +| 第21章 | 52 | 467 | 1,076 | +| **合計** | **91** | **847** | **1,652** | + +第20章の行は、BrainFuck と MergeSort を含む元の13入力すべてを、3つの SystemV 対象について固定しています。これらは `Chapter20Test` にあります。以前そのファイルにあった改訂済みソース／ABI ケースは `Chapter21AllocTest` に保持し、`Chapter21Test`、ネイティブ BrainFuck/MergeSort テストと合わせて第21章の行を構成します。その行には ARM/SystemV が17、RISC-V/SystemV が17、x86/SystemV が8、x86/Win64 が10コンパイルあります。ネイティブホスト ABI の変更はこの行に影響するため、同じホストと対象で比較してください。 + +隣接コピー転送の前、メモリ移植によって、群の構成と割り当て器のヒューリスティックを変えずに、以前の合計840／1,456が845／1,559になりました。変化した行は以下のすべてです。各項目は残存／ループ重み付き分割です。 + +| 群／プログラム | 対象／ABI | 変更前 | 遅延メモリ | +|---|---|---:|---:| +| 20 / MergeSort | ARM / SystemV | 44 / 44 | 41 / 41 | +| 20 / BrainFuck | RISC-V / SystemV | 35 / 42 | 37 / 58 | +| 20 / Alloc2 | x86 / SystemV | 3 / 3 | 4 / 4 | +| 20 / Alloc2 | ARM / SystemV | 10 / 10 | 9 / 9 | +| 20 / String | x86 / SystemV | 7 / 14 | 8 / 15 | +| 20 / String | RISC-V / SystemV | 14 / 14 | 10 / 10 | +| 20 / String | ARM / SystemV | 13 / 13 | 10 / 10 | +| 21 / Sieve | x86 / Win64 | 24 / 178 | 24 / 185 | +| 21 / Sieve | RISC-V / SystemV | 19 / 89 | 22 / 92 | +| 21 / Sieve | ARM / SystemV | 23 / 93 | 21 / 91 | +| 21 / BrainFuck | RISC-V / SystemV | 35 / 42 | 46 / 130 | + +重み付き増加の大半は RISC-V BrainFuck によるものです。read-before-New の順序付けだけを省く診断実行では、その2行は35／42と37／58になります。これでコストの大半を説明できますが、コンパイラは順序制約を保持します。メモリ移植にヒューリスティックの調整は含めていません。 + +続く Load 検索の改良は、ループの N 方向メモリマージを通じて BrainFuck の固定プログラム長を畳み込みます。すべての後退辺の枝が畳み込めるか、同じポインタについて変更されていないメモリへ戻る必要があります。RISC-V の Hello World 実行で907回のヒープロードを除去し、スタックアクセスを1,006ロード／572ストアから15／15へ減らします。コピー転送前、その行は144移動／165重み付き移動で、91項目全体は943／1,594でした。隣接コピー転送は、それぞれ35／42と821／1,444へ減らします。RISC-V の Hello World 実行は、ヒープとスタックのアクセス数を変えずに、21,920ではなく21,787命令を実行します。これらはエミュレータの命令数で、ハードウェアの時間測定ではありません。現在のネイティブ BrainFuck テストと、すべての実行時アサーションは有効です。 + +その後 GCM の反依存関係の支配ノード走査を復元したことで、RISC-V BrainFuck の各行は35／42から48／146へ変わり、上の現在の表になりました。条件付き書き手は、後の Load 配置を支配するとは限らないため、書き手の正確なブロックだけを確認すると、必要な順序付けを見逃します。復元した走査は、条件付きストア前の読み取りプログラムが120でなく140を返していた問題を修正します。両方の BrainFuck 実行確認と、91項目全体のスピル監査が成功しています。移動数の増加は、割り当て器のヒューリスティックを変えずに記録しています。 + +次の併合比較は遅延メモリより前のものです。両側はその監査の同じコンパイラを使います。現在のグラフに対する新たな機能無効化比較ではありません。 + +| 以前の制御された比較、同じ91コンパイル | 分割 | ループ重み付き分割 | +|---|---:|---:| +| 併合を無効にした監査コンパイラ | 1,070 | 1,889 | +| 併合を有効にした監査コンパイラ | 840 | 1,456 | + +制御実行は `graphColor` 内の `Coalesce.coalesce` だけを無効にします。両実行で、割り当て、レジスタ制約、実行時確認が成功します。無効化した実行は、スピル期待値の9件の変化を報告し、意図どおり失敗終了します。併合は230移動（21.5%）と433重み付き移動（22.9%）を減らします。局所的な増加は起きる場合があり、1例ではなく集計がトレードオフを判断します。 + +最終監査は x86/RISC-V の狭いストアマスクをバックポートし、ARM のレジスタバンク選択と浮動小数点メモリ演算を修正しました。バイトストアを合法なレジスタに制限すると、RISC-V BrainFuck は2つの群それぞれで211から42重み付き移動となり、以前の表から44の単純移動／338の重み付き移動が減ります。これらの正しさの修正は比較の両側に含まれます。より広いマスクで行った以前の測定は過去の記録で、現在の基準値ではありません。第20章の357重み付き移動も併合の基準値ではありません。第21章は機械命令への変換を変更し、ネイティブ ABI の責務を実装しているためです。 diff --git a/docs/chapter21/README.md b/docs/chapter21/README.md new file mode 100644 index 00000000..03b25759 --- /dev/null +++ b/docs/chapter21/README.md @@ -0,0 +1,170 @@ +# Chapter 21: Instruction Encoding and ELF + +English | [日本語](README.ja.md) + +[Previous: Chapter 20](../chapter20/README.md) | +[Next: Chapter 22](../chapter22/README.md) + +This chapter turns the scheduled, register-allocated graph into executable +instructions. Each machine node writes its bytes; the compiler places blocks, +resolves local references, and exports an ELF object for the linker. We can now +run generated code, which also tests instruction selection, register allocation, +and calling conventions together. + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter21) +in the linear revision history and +[compare it to Chapter 20](https://github.com/SeaOfNodes/Simple/compare/linear-chapter20...linear-chapter21). + +Here is the [complete language grammar](21-grammar.md) for this chapter. + +## From machine nodes to bytes + +Instruction selection chooses the operation and register constraints. Register +allocation assigns physical registers and stack slots. Encoding then combines +the opcode, assigned registers, and immediate operands into instruction bytes. +An instruction cannot choose a different register at this point: the surrounding +instructions already depend on the allocator's choices. + +[Encoding.java](../../src/main/java/com/seaofnodes/simple/codegen/Encoding.java) owns the +byte stream and records each node's offset and encoded length. Its driver: + +1. Lays out basic blocks and inserts or reverses branches as needed. +2. Calls `MachNode.encoding(Encoding)` in scheduled order. +3. Settles short and long instruction forms. +4. Patches references whose targets are inside this compilation. + +The `add1`, `add2`, `add4`, and `add8` helpers append little-endian values. Encoding +functions obtain allocated registers through `Encoding.reg`. Stack operands use +the function's frame layout, including space for saved registers and outgoing +arguments. A successful coloring alone does not establish a correct calling +convention; the generated program must preserve the caller's values too. + +## Three instruction sets + +The targets share this driver. Machine nodes resolve compiler operands, then +call the shared [ISA encoders](../../isa/README.md). + +| Target | Main encoding concerns | +|---|---| +| RISC-V | Register and immediate fields in instruction words; larger constants and addresses need multiple instructions. | +| AArch64 | Register forms, restricted immediate encodings, and multi-instruction constant construction. | +| x86-64 | Variable instruction lengths, register prefixes, addressing forms, and short versus long branches. | + +For example, a small integer can fit directly in an instruction, while a large +one may require several instructions or a load from a constant pool. Consequently, +even a target with fixed-width instructions can emit different numbers of bytes +for different machine nodes. + +The [encoding reference](encoding-reference.md) retains the detailed bit +layouts, worked examples, and ISA links. Those details matter when implementing +a particular instruction, but do not change the compiler pipeline described here. +The machine-node wiring lives under +[node/cpus](../../src/main/java/com/seaofnodes/simple/node/cpus). The shared +[X86 encoder](../../isa/src/main/java/com/seaofnodes/isa/X86.java) owns x86 byte +emission; [Arm64](../../isa/src/main/java/com/seaofnodes/isa/Arm64.java) and +[RiscV](../../isa/src/main/java/com/seaofnodes/isa/RiscV.java) pack instruction words. + +For example, `AddX86` chooses opcode `0x03`. Its `RegX86` base reads the two +allocated registers and calls `X86.reg(enc,opcode(),dst,src)`. The shared method +writes REX.W, the opcode, and ModRM directly into `Encoding`'s byte buffer. +For `add r9,r10`, the bytes are `4d 03 ca`. Register constraints and the +two-address requirement remain on the chapter's machine node. This separates +the decision to use ADD from the fixed bit representation of that instruction. + +Loads use the same boundary: the chapter resolves width, sign extension, and +register bank from its types and allocated operands. `X86.load` receives those +facts and the concrete address; it has no dependency on the chapter's graph or +type lattice. Later chapters reuse these encodings as their compiler evolves. + +ARM and RISC-V execution tests also reuse the evaluators in `isa/src/test-support`. +The chapter's test harness prepares and links a memory image; the evaluator +executes its bytes. This keeps instruction semantics in one place while image +construction follows each chapter's compiler. They compile with the tests; +Make's release jar continues to bundle the test harness as well as the compiler. + +## Relocation and ELF + +A forward branch cannot know its final displacement when its bytes are first +written. Its target's offset depends on all the intervening encodings. Shortening +or expanding another branch can move that target again. The layout pass settles +instruction sizes before local relocations patch the final displacements. + +External references need a later patch. For example, the compiler can emit a +call to `malloc` without knowing where the linker will place it. The object file +records the symbol, patch location, and relocation kind. That kind must agree +with the instruction: an x86 call displacement and a split RISC-V address occupy +different fields and cannot use the same patch operation. + +[ElfFile.java](../../src/main/java/com/seaofnodes/simple/codegen/ElfFile.java) writes the +object's code, data, symbols, and relocation records. Large constants introduce +the same placement problem as external calls: their eventual addresses must be +connected to the instructions that load them. Local relocation and object-file +relocation are two stages of the same obligation to make references correct. + +## Execute the result + +Chapter 11's lazy memory partitioning now carries through encoding. Parameters, +calls, and returns carry whole memory; `BulkMemPhi`, `MemPhi`, and `MemMerge` +discover precise aliases inside each function. New consumes `{ctrl, $mem, size}` +and produces `{ptr, $mem}`. Its memory covers the allocated struct's aliases; +the surrounding merge retains unrelated aliases. Nonzero initialization still +uses explicit Stores. Memory nodes and ordering edges require no registers. + +Scheduling follows aliases through aggregates to order reads before matching +Stores, allocations, and calls. Calls retain their argument lists, with no added +ordering operands. Synthetic loop exits collect precise memory by alias. + +The execution regressions cover constructors, non-inlined and recursive calls, +inlining, and array updates, using native x86 and both emulators. A full-width +x86 load uses the allocated register bank when choosing its encoding, since an +integer may reside in XMM. ARM emulation handles MOVZ/MOVK halfword construction +for the large constants in these checks. + +`make tests` includes C harnesses that link and run generated x86 code, and +RISC-V/AArch64 emulator checks. The tests compare results as well as spill counts. +Native process failures retain their full exit status. Emulator checks must read +their own result memory; matching another target's result is insufficient. + +Run `make spill-stats` to collect allocations from the same tests with assertions +enabled. It reports each test/CPU/ABI, then cohort totals. A spill-golden mismatch +is recorded without skipping the remaining targets or execution checks; any such +mismatch still makes the command fail. Structural allocator regressions are +excluded from the spill totals. + +## RegAlloc improvements: eliminating copies + +A split inserts a copy between two live ranges. If both can safely become one +range, the copy can disappear before coloring. [Coalesce.java](../../src/main/java/com/seaofnodes/simple/codegen/Coalesce.java) +checks that the ranges do not interfere, intersects their allowed-register +masks, and combines their neighbors. It merges only when the resulting +neighbor count is smaller than the number of available registers - meaning it +can always color. + +After coloring, a copy with one use in the immediately following instruction +can also disappear when that operand accepts the source register and is not +its two-address operand. For example, `mov rpc=s8; st1 [rpc+4],s1` becomes +`st1 [s8+4],s1`. Adjacency proves that nothing overwrites the source in between. +Phi and control-flow users are excluded. This local cleanup leaves spill +selection unchanged; it complements coalescing without another CFG analysis. + +For looking at allocator progress, we will keep a table of execution and allocation costs +a chapters' tests - and use the later chapter compiler and register allocator +on them. The later chapters also modify the graph (sometimes adding boiler +plate graph) so its not really a 100% fair comparison of how well this +*heuristic* does, but it does give us some idea that we're not losing ground. + +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. + + +| Test cohort | Cases D / X | Ch 20: Ops / RA / X | Ch 21: Ops / RA / X | +|---|---:|---:|---:| +| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | +| Ch 21 | 20 / 18 | | 6,207 / 261 / 461 | + + diff --git a/docs/chapter21/encoding-reference.ja.md b/docs/chapter21/encoding-reference.ja.md new file mode 100644 index 00000000..c93d2947 --- /dev/null +++ b/docs/chapter21/encoding-reference.ja.md @@ -0,0 +1,776 @@ +# 命令エンコーディングの参考資料 + +[English](encoding-reference.md) | 日本語 + +この文書は [Instruction encoding reference](encoding-reference.md) の日本語訳です。 +元の第21章の README から、詳細な説明を残したものです。 +コンパイラのパイプラインと実験については[章の概要](README.ja.md)を参照してください。 + +# 目次 + +1. [命令エンコーディング](#命令エンコーディング) +2. [基盤](#基盤) +3. [エンディアン](#エンディアン) +4. [RISCV](#riscv) + - [命令形式](#命令形式) + - [浮動小数点数](#浮動小数点数) + - [間接参照](#間接参照memop) + - [分岐](#分岐) + - [即値](#即値) + - [関数内の定数](#関数内の定数) +5. [ARM](#arm) + - [レジスタ形式](#レジスタ形式) + - [即値シフト](#即値シフト) + - [論理演算の即値](#論理演算の即値) + - [浮動小数点数](#浮動小数点数-1) + - [大きな定数](#大きな定数) + - [関数定数](#関数定数) + - [条件フラグ](#条件フラグ) + - [間接参照](#間接参照memop-1) + - [分岐](#分岐-1) +6. [AMD64 X86-64](#amd64-x86-64) + - [REX プレフィックス](#rex-プレフィックス) + - [MODR/M](#modrm) + - [SIB](#sib) + - [変位](#変位) + - [即値](#即値-1) + - [浮動小数点数](#浮動小数点数-2) + - [大きな定数](#大きな定数-1) + - [関数定数](#関数定数-1) + - [条件フラグ](#条件フラグ-1) +7. [再配置](#再配置) + +この章では命令エンコーディングを追加します。命令エンコーディングとは、 +プロセッサの命令セットアーキテクチャ（ISA）が定義する特定のバイナリ形式で機械命令を表すことです。 + +命令選択が完了したら、ELF オブジェクトファイルに書き出す前に、命令をエンコードします。 + +曖昧さを避けるため、命令のエンコードに使う情報の出典を明示します。 +現在、次のアーキテクチャをサポートしています。 + +### RISC-V: + +*riscv* では現在、[RVA23U64](https://msyksphinz-self.github.io/riscv-isadoc/html/) を対象にしています。 + +### ARMV8/AArch64: + +*arm*（aarch64）では、この資料にまとめられた[エンコーディング規則](https://docsmirror.github.io/A64/20a23-06/index.html)を使います。 +*注*：サポートするのは64ビット ARM のエンコーディングだけです。 + +### AMD64: + +*x86-64（amd64）* では、最新の Intel マニュアルの[エンコーディング規則](https://www.felixcloutier.com/x86/)を使います。 + +-------------------------------- + +## 命令エンコーディング + +## 基盤 + +命令選択フェーズは、理想ノードから機械向けのノードを作ります。 +これらの機械向けノードには *encoding* 関数があり、CodeGen 内の Encoding ドライバから呼び出します。 + +```java +for( CFGNode bb : _code._cfg ) + for( Node n : bb._outputs ) + if( n instanceof MachNode mach ) { + int off = _bits.size(); + mach.encoding(this); + _opLen[n._nid] = (byte)(_bits.size()-off); + } +``` + +選んだターゲットに応じて、リトルエンディアンまたはビッグエンディアンのエンコーディングに注意する必要があります。 +これは `add4` が扱い、正しい順序でビットストリームに追加します。 +現時点のビットストリームは、単純な ByteArrayOutputStream です。 + +```java +@Override public void encoding( Encoding enc ) { + enc.add4(0); // adds 4 bytes to the bitstream +} +``` + +資料がビッグエンディアンでエンコーディングを示す *RISC-V* では、 +この関数がリトルエンディアンへの変換も行います。ほかのアーキテクチャでは変換は不要です。 + +## エンディアン + +実際に使う ARM、RISC-V、x86 はすべてリトルエンディアンで、最下位バイトを先に格納します。 +したがって、命令エンコーディングがリトルエンディアン形式で生成されるようにします。 + +```java +// Little endian write of a 32b opcode +public void add4( int op ) { + _bits.write(op ); + _bits.write(op>> 8); + _bits.write(op>>16); + _bits.write(op>>24); +} +``` + +たとえば、固定長命令の32ビットのエンコーディング *10110101100111101011001001101101* を考えます。 + +最下位バイトを最初に追加し、次のバイトを追加していきます。 +``` +_bits.write(op ); +``` + +`_bits.write()` が追加するのは最下位バイトだけです。 +値を右にシフトすると、次のバイトを最下位の位置へ移動でき、各バイトを順番に書き込めます。 + +-------------------------------- + +## RISCV + +RISCV の命令はすべて32ビット幅で、常にリトルエンディアンです。 +RISCV は RISC アーキテクチャなので「レジスタ間」の形式を優先し、エンコーディングは非常に規則的です。 +最も単純なエンコーディングであるため、RISCV から説明します。 + +#### 命令形式 + +##### R-TYPE + +このエンコーディング形式は、`AddRISC`、`MulRISC` などのレジスタ間の演算に使います。 +```java +public static int r_type(int opcode, int rd, int func3, int rs1, int rs2, int func7) { + return (func7 << 25) | (rs2 << 20) | (rs1 << 15) | (func3 << 12) | (rd << 7) | opcode; +} +``` + +##### I-TYPE + +この配置は、`AddIRISC` などの即値形式に使います。 + +```java + public static int i_type(int opcode, int rd, int func3, int rs1, int imm12) { + assert opcode >= 0 && rd >=0 && func3 >=0 && rs1 >=0 && imm12 >= 0; // Zero-extend by caller + return (imm12 << 20) | (rs1 << 15) | (func3 << 12) | (rd << 7) | opcode; + } +``` + +##### S-TYPE + +このエンコーディング形式は `StoreRISC` に使います。 + +```java +public static int s_type(int opcode, int func3, int rs1, int rs2, int imm12) { + assert imm12 >= 0; // Masked to high zero bits by caller + int imm_lo = imm12 & 0x1F; + int imm_hi = imm12 >> 5; + return (imm_hi << 25) | (rs2 << 20) | (rs1 << 15) | (func3 << 12) | (imm_lo << 7) | opcode; +} +``` + +##### B-TYPE + +このエンコーディングの配置は `BranchRISC` が使います。 +```java + // immf = first imm + // immd = second imm + // BRANCH +public static int b_type(int opcode, int immf, int func3, int rs1, int rs2, int immd) { + return (immd << 25 ) | (rs2 << 20) | (rs1 << 15) | (func3 << 12) | (immf << 7) | opcode; + } +``` + +##### U-TYPE + +この配置は `AUIPC` と `LUI` に使います（上位即値は20ビットです）。 + +```java + public static int u_type(int opcode, int rd, int imm20) { + return (imm20 << 12) | (rd << 7) | opcode; + } +``` + +##### J-TYPE + +無条件ジャンプ（`UJmpRISC`）に使います。 +```java + public static int j_type(int opcode, int rd, int imm20) { + return imm20 << 12 | rd << 7 | opcode; + } +``` + +#### 浮動小数点数 + +浮動小数点定数のロードには、間接メモリロード（PC 相対）を使います。 +``` +AUIPC dst,#hi20_constant_pool +Load dst,[dst+#low12_constant_pool] +``` + +#### 間接参照（MemOp） + +[ロード](https://msyksphinz-self.github.io/riscv-isadoc/html/rvi.html#lw)：`lw rd,offset(rs1)` + +[ストア](https://msyksphinz-self.github.io/riscv-isadoc/html/rvi.html#sw)：`sw rs2,offset(rs1)` + +#### 分岐 + +RISC-V は、分岐命令が比較と分岐先を1つの命令に含むという点で特徴的です。 + +#### 即値 + +*ALU* 演算では、即値が符号付き12ビットに収まる場合だけ、即値形式をエンコードします。 +それ以外では Load Upper Immediate（上位20ビット）を使うか、両方を使います。 + +``` +addiw a5,a5,123 +``` + +これに対して、追加のロードを使う場合は次のようになります。 +``` +addw a5,a5,a4 +``` + +### 浮動小数点定数 + +- **定数プール**に格納します。 +- **PC 相対ロード**でアクセスします。 + +### 整数定数 + +- **12ビット定数**：`ADDI` を使います。 +- **20ビット定数**：`LUI` を使います。 +- **32ビット定数**：`LUI` と `ADDI` を組み合わせます。 + +#### 関数内の定数 + +RISC-V のコードで関数内の定数をロードするときは、現在の PC をレジスタに格納し、 +それを基底として定数へアクセスします。ただし、加算のような単純な算術演算のほうが +メモリアクセスより速く効率的なので、通常はロードを避けるようにします。 + +```java +// auipc t0,0 +// addi t1,t0 + #0 +``` + +-------------------------------- + +## ARM + +Arm の命令はすべて32ビット幅で、常にリトルエンディアンです。 +Arm は RISC アーキテクチャなので、「レジスタ間」の形式を優先します。 + +#### レジスタ形式 + +レジスタ形式は、[シフト付きレジスタ](https://docsmirror.github.io/A64/2023-06/orr_log_shift.html)としてエンコードします。 +``` +orr reg1, reg2 +``` +``` +x0 = x0 | (x1 << 0) +``` + +ほかのレジスタ形式にも同じことが当てはまります。 +この共通性によって、レジスタ形式のエンコーディングを共通関数にまとめられます。 + +```java +short self = enc.reg(n); +short reg1 = enc.reg(n.in(1)); +short reg2 = enc.reg(n.in(2)); +int body = r_reg(opcode, 0, reg2, 0, reg1, self); +enc.add4(body); +``` + +レジスタ形式では *imm6* と *shift* は関係しないため、両方を0に設定します。 + +### 即値シフト + +*asri、lsli、lsri* を指します。シフト量が0以上63以下なら、即値シフトとしてエンコードします。 + +#### ASR（即値） + +即値の算術右シフトでは、*immr* をエンコードしたい即値に、imms を `63` = `111111` に設定します。 +これは [asri のエンコーディング](https://docsmirror.github.io/A64/2023-06/asr_sbfm.html)の規則に従っています。 + +`sf` ビットはオペコードに含まれ、`N` は `imm_shift` 関数の実行後、暗黙にビットストリームへ追加されます。 +```java +enc.add4(arm.imm_shift(0b100100110,_imm, 0b111111, rn, rd)); +``` + +#### LSL（即値） + +```java +// UBFM , , #(- MOD 64), #(63-) +// immr must be (- MOD 64) = 64 - shift +enc.add4(arm.imm_shift(0b110100110, 64 - _imm, (64 - _imm) - 1, rn, rd)); +``` + +`_imm` は負にならず、0〜63の間にあるので、`64 - _imm` を `immr` の値として安全に使えます。 +この形式の即値を64から引いて、ビットを反転します。 + +*imms* については、条件 *imms + 1 = immr* が成り立たなければなりません。 +値を代入すると、次のようになります。 + +> imms + 1 = 64 - _imm; + +> imms = (64 - _imm) - 1; + +したがって、`imms` の値は `(64 - _imm) - 1` です。 + +#### LSR（即値） + +*ASR* と同じです。 + +#### 論理演算の即値 + +論理演算の即値は *andi、xori、orri* を指します。 + +```java +// Can we encode this in ARM's 12-bit LOGICAL immediate form? +// Some combination of shifted bit-masks. +private static int imm12Logical(TypeInteger ti) { + if( !ti.isConstant() ) return -1; + if( !ti.isConstant() ) return -1; + long val = ti.value(); + if (val == 0 || val == -1) return -1; // Special cases are not allowed + int immr = 0; + // Rotate until we have 0[...]1 + while (val < 0 || (val & 1)==0) { + val = (val >>> 63) | (val << 1); + immr++; + } + int size = 32; + long pattern = val; + // Is upper half of pattern the same as the lower? + while ((pattern & ((1L<> size)) { + // Then only take one half + pattern >>= size; + size >>= 1; + } + size <<= 1; + int imms = Long.bitCount(pattern); + // Pattern should now be zeros followed by ones 0000011111 + if (pattern != (1L< cond は標準的な条件のいずれかです。 + +-------------------------------- + +## AMD64 X86-64 + +命令幅が固定の riscv アーキテクチャとは異なり、*x86-64* の命令は可変長です。 +これは *CISC（Complex Instruction Set Computer）* アーキテクチャで一般的であり、 +命令幅は1〜15バイトまで変わります。AMD64 は多くの間接アドレッシングモードをサポートするため、 +*CISC* の一般的な目標は、できるだけ少ないアセンブリの行数で処理を完了することです。 + +### REX プレフィックス + +64ビット版の x86 を対象にしているため、このプレフィックスを扱う必要があります。 +一方、32ビットモードでは通常は不要です。 + +一般に、次の場合は *REX* プレフィックスをエンコードしなければなりません。 + +- 拡張レジスタ（R8〜R15、XMM8〜XMM15、YMM8〜YMM15、CR8〜CR15、DR8〜DR15）を使う。 +- オペランドサイズが64ビットで、命令の既定のオペランドサイズが64ビットではない（大部分の ALU 演算）。 +- RSI、RDI、RBP で8ビットのオペランドを使う。 + +次の場合は *REX* プレフィックスをエンコードしてはなりません。 + +- 上位バイトのレジスタ AH、CH、BH、DH を使う（現在の Simple では使っていません）。 + +*注*：SSE 命令のエンコーディングでは、*REX* プレフィックス（0x40）を `SSE` プレフィックスの後に置く必要があります。 +それ以外の場合は無視されます。 + +Simple では、REX プレフィックスをビットストリームの先頭に追加するだけです +（SSE の浮動小数点命令を除く）。配置は次のとおりです。 + +| **フィールド** | **長さ** | **説明** | +|:---------:|:----------:|---------------------------------------------------------------------------------| +| `0100` | 4ビット | 固定のビットパターン | +| `W` | 1ビット | 1なら64ビット、それ以外なら32ビットのオペランドサイズを使う | +| `R` | 1ビット | **MODRM.reg** フィールドの拡張 | +| `X` | 1ビット | **SIB.index** フィールドの拡張 | +| `B` | 1ビット | **MODRM.rm** または **SIB.base** フィールドの拡張 | + +```java + public static int REX_W = 0x48; +``` + +```java +public static int rex(int reg, int ptr, int idx, boolean wide) { + // assuming 64 bit by default so: 0100 1000 + int rex = wide ? REX_W : REX; + if( 8 <= reg && reg <= 15 ) rex |= 0b00000100; // REX.R + if( 8 <= ptr && ptr <= 15 ) rex |= 0b00000001; // REX.B + if( 8 <= idx && idx <= 15 ) rex |= 0b00000010; // REX.X + return rex; +} + + ... + enc.add1(x86_64_v2.rex(dst, src, 0)); +``` + +`W` ビットを設定すると、`0b01001000 = 0x48;` になります。 + +#### オペコード + +この場合、オペコードは実行する操作を指定する1バイトのフィールドです。 +``` +enc.add1(opcode()); // opcode +``` + +#### MODR/M + +| **フィールド** | **長さ** | **説明** | +|:-------------:|:----------:|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| +| **MODRM.mod** | 2ビット | 一般に、このフィールドが `b11` ならレジスタ直接アドレッシングモード、それ以外ならレジスタ間接アドレッシングモードを使う | +| **MODRM.reg** | 3ビット | 2種類の値を取れる。

• 一部の命令が使う3ビットのオペコード拡張。ほかの命令と区別する以上の意味は持たない。

• 命令によってソースまたは宛先として使う3ビットのレジスタ参照。参照するレジスタは、命令のオペランドサイズと命令自体に依存する。`REX.R`、`VEX.~R`、`XOP.~R` フィールドによって最上位ビットを1つ追加し、合計4ビットに拡張できる | +| **MODRM.rm** | 3ビット | 直接または間接のレジスタオペランドを指定し、任意で変位を伴う。`REX.B`、`VEX.~B`、`XOP.~B` フィールドによって最上位ビットを1つ追加し、合計4ビットに拡張できる | + +MODR/M バイトも同じように扱います。 + +modrm バイトに最初に必要なのは、2ビットの mod です。 + +##### mod + +mod の配置は次のとおりです。 +``` +public enum MOD { + INDIRECT, // [mem] + INDIRECT_disp8, // [mem + 0x12] + INDIRECT_disp32,// [mem + 0x12345678] + DIRECT, // mem +}; +``` + +##### reg + +reg フィールドは3ビットで、8個のレジスタから1個を選びます。レジスタを指定する場合、 +REX.R によって4ビットに拡張され、16個のレジスタから1個を選べます。 + +##### r/m + +r/m フィールドは3ビットです。レジスタ直接指定モードでは、REX.B によって拡張され、 +16個のレジスタから1個を選べます。メモリ指定モードでは、アドレッシング形式または +ベースレジスタを選びます。一部の値は SIB バイトや RIP 相対アドレッシングを指定します。 + +```java +public static int modrm(MOD mod, int reg, int m_r) { + // combine all the bits + return (mod.ordinal() << 6) | ((reg & 0x07) << 3) | m_r & 0x07; +} +``` + +`modrm` 関数を使って `ModR/M` バイトを構築します。通常、これはオペコードの後に続きます。 + +``` +enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, src)); +``` + +レジスタ形式のエンコーディングは、次のようになります。 +``` +short dst = enc.reg(this ); // src1 +short src = enc.reg(in(2)); // src2 +enc.add1(x86_64_v2.rex(dst, src, 0)); +enc.add1(opcode()); // opcode +enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, src)); +``` + +#### SIB + +SIB バイトには次のフィールドがあります。 + +| **フィールド** | **長さ** | **説明** | +|:-------------:|:----------:|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| +| **SIB.scale** | 2ビット | `SIB.index` のスケーリング係数を示す。表で使う **s** は 2^SIB.scale^ に等しい | +| **SIB.index** | 3ビット | 使用するインデックスレジスタ。各レジスタの値は Registers を参照。`REX.X`、`VEX.~X`、`XOP.~X` フィールドによって最上位ビットを1つ追加し、合計4ビットに拡張できる | +| **SIB.base** | 3ビット | 使用するベースレジスタ。各レジスタの値は Registers を参照。`REX.B`、`VEX.~B`、`XOP.~B` フィールドによって最上位ビットを1つ追加し、合計4ビットに拡張できる | + +MODR/M バイトと同じ配置です。 +```java +public static int sib(int scale, int index, int base) { + return (scale << 6) | ((index & 0x07) << 3) | base & 0x07; +} +``` + +```java +enc.add1(x86_64_v2.sib(_scale, idx, x86_64_v2.RBP)); +``` + +#### 変位 + +変位には2つの形式があります。 +```java +public enum MOD { +INDIRECT, // [mem] +INDIRECT_disp8, // [mem + 0x12] +INDIRECT_disp32,// [mem + 0x12345678] +DIRECT, // mem +}; +``` + +```java +if( mod == MOD.INDIRECT_disp8 ) { + enc.add1(offset); +} else if( mod == MOD.INDIRECT_disp32 ) { + enc.add4(offset); +} +``` + +変位は即値の前に置きます。たとえば、次のようになります。 +``` +sub [eax + 2], 4 +``` +``` +bytes.write(0x83); +bytes.write(modrm(INDIRECT8, 5, 0 /* eax */)); +bytes.write(2); // displcement goes first +bytes.write(4); +``` + +#### 即値 + +即値のバイト列は `ModR/M` バイトの後に置きます。必要に応じて4バイトの即値をエンコードできます。 +```java +// immediate(4 bytes) 32 bits or (1 byte)8 bits +if( x86_64_v2.imm8(_imm) ) enc.add1(_imm); +else enc.add4(_imm); +``` + +#### 間接参照（MemOp） + +X86-64 は複数の間接アドレッシングモードをサポートします。 + +#### 浮動小数点数 + +浮動小数点演算には、XMM レジスタまたはメモリにあるスカラーの単精度浮動小数点値を操作する +`SSE SIMD` 命令を使います。 +*注*：ALU 演算で XMM レジスタを使う場合、エンコーディングは非常に似ていますが、 +レジスタ番号から `XMM_OFFSET` を引く必要がある点が異なります。 +レジスタを連続した番号で数えているため、XMM レジスタに対応する GPR のペアを得るには、 +オフセットを引く必要があります。 + +```java +short dst = (short)(enc.reg(this ) - x86_64_v2.XMM_OFFSET); +``` + +```java +public static int XMM_OFFSET = 16; +``` + +| **X.Reg** | **8ビット GP** | **16ビット GP** | **32ビット GP** | **64ビット GP** | **80ビット x87** | **64ビット MMX** | **128ビット XMM** | **256ビット YMM** | **16ビット Segment** | **32ビット Control** | **32ビット Debug** | +|:--------:|:------------:|:-------------:|:-------------:|:-------------:|:-------------:|:-------------:|:--------------:|:--------------:|:-----------------:|:-----------------:|:---------------:| +| `0.000 (0)` | AL | AX | EAX | RAX | ST0 | MMX0 | XMM0 | YMM0 | ES | CR0 | DR0 | + +`XMM0` が `RAX` に対応し、以降も同様であることがわかります。 + +#### 大きな定数 + +##### 整数：`MOV r64, imm64` 命令形式を使うだけです。 + +##### 浮動小数点数：再配置を使い、メモリ内の定数を使います。 + +#### 関数定数 + +関数定数をロードするには lea を使います。これは、命令ポインタからの相対アドレスを指定したレジスタにロードします。 +`lea rax, [rip+disp32]` + +#### 条件フラグ + +FLAGS レジスタは、x86 CPU の現在の状態を保持するステータスレジスタです。 + +条件付きコードのためにエンコードする必要のあるすべての命令を示す、単純な例を考えます。 + +``` +int square(int a) { + // cmp DWORD PTR [rbp-0x8],0x1 + // `sete al` + bool da = a == 1; + + // cmp eax,0x1 + if(da == 1) { + return 1; + } + return 2; +} +``` + +まず、`a` と1を比較する比較命令が必要です。 +``` +cmp DWORD PTR [rbp-0x8],0x1 +``` + +この比較命令が条件フラグを設定します。 + +> 結果に従って CF、OF、SF、ZF、AF、PF フラグを設定します。 + +続いて `sete` 命令を使い、比較の結果をレジスタへ保存します。 + +`sete al` + +if 条件のために、最初の真偽値の結果に基づく追加の比較を行います。 +``` + cmp eax,0x1 +``` + +そして、比較（`a == 1`）が設定したフラグに依存する条件付き分岐を行います。 +``` +jne 1159 +``` + +-------------------------------- + +## 再配置 + +再配置によって、コードを新しいコードオフセットへ*移動*できます。 +コードは、ほかのコードやデータを参照することがよくあります。 +`call` 命令はサブルーチンを、`branches` はほかの命令を対象とし、 +大きな定数は多くの場合*定数プール*からロードします。 + +### 局所的な再配置 + +局所的な再配置は、局所的または自己参照的なコードを修正します。最も一般的なのは分岐先です。 +`BAOS`（Byte Array Output Stream）に命令を書き込む際、後に続く命令へ向かう前方分岐のオフセットは未知です。 +そのオフセットは、分岐と分岐先の間にあるエンコーディングのサイズに依存します。 +`riscv` と `arm` のターゲットでは簡単に見えます（命令は4バイトなので数えればよい）……。 +しかし、複数の命令を使うエンコーディングもあるため、実際には4バイトとは限りません。 +X86 では命令長が擬似的に不規則に見えるほど多様なので、オペコードの長さを求めること自体が、 +オペコードを書き出すのと同じくらい難しくなります。 + +X86 には、短形式と長形式の分岐という追加の複雑さもあります。 +分岐先が符号付きバイトの範囲（+/-127）にあるなら2バイトの分岐エンコーディングを、 +それ以外では6バイトのエンコーディングを使います。 +Simple には、分岐を縮め、できるだけ2バイト形式を使うパスがあります。 +ただし、このパスはコードをずらす必要があり、その結果、ほかの分岐オフセットもすべて変わります。 +この「圧縮」パスは実際には、すべての分岐が2バイト形式を使えると楽観的に仮定して始め、 +必要に応じて分岐を拡張します（したがって、実際にはコードを*拡張*します）。 + +コードの「形」が最終的に決まったら、局所的な再配置パスを実行して自己参照をすべて更新します。 +基本的には、バイト配列内の分岐オフセットを実際の値で上書きします。 + +このパスの終了時点で、コードはあるオフセット（通常は0）で局所的に正しくなります。 +しかし、これで終わりではありません。別のコンパイルで生成されたコードと*リンク*することが多く、 +その際にもさまざまなオフセットを調整する必要があります。 + +### 大域的な再配置 + +あるコンパイル単位のコードから、別のコンパイル単位のコードを呼びたい場合、*大域的な再配置*が必要です。 +よくある例は、*ローダー*が *ELF* ファイルをロードすることです。 +通常は新しいプログラムの実行ごとに起こり、再配置情報をディスク（たとえば ELF ファイル内）に保存しておく必要があります。 +JIT システムでも、異なるコンパイルをまたいで同じことが必要ですが、再配置情報はメモリに保持できます。 + +#### 再配置の整合性を保つ + +再配置をディスクに書き込めるので、ディスク形式、ローダー、「コードの形」がすべて一致しなければなりません。 +あるコンパイル単位から別の単位を呼ぶ場合、たとえばプログラムが `libc` の `malloc` を呼ぶ場合を考えます。 +呼び出し元は Simple の汎用 `CallNode` の機械固有版を使い、呼び出し先は C でコンパイルされたコードです。 +ロード中に、ローダーが `call` と `libc` の配置を決めます。 +2つの異なるコードブロックを何らかの順序で（通常は多くのほかのブロックとともに）メモリに書き込みます。 +そこで、`call` の呼び出し先を、`libc` のコードブロック内の `malloc` に修正する必要があります。 + +X86 の外部呼び出しは、1バイトのオペコードと4バイトの PC 相対宛先アドレスからなる5バイト命令です。 +必要な修正値は、X86 固有の `call` 命令の*末尾*から `malloc` の先頭までの差であり、 +`call` の最後の4バイトに直接書き込みます。ELF ファイル内のエンコーディングの種類は、これを記述しなければなりません。 + +RISCV の外部呼び出しは、ビットを分担する2つの4バイト命令でエンコードします。 +`LUI` が宛先の上位20ビットをロードし、`JALR` が下位12ビットを加算します（32ビットの絶対宛先範囲）。 +`LUI` を `AUIPC` に置き換えると、32ビットの PC 相対範囲を得られます。 +修正では、一方の命令の20ビットと、もう一方の命令の12ビットを更新します。 +ここでも ELF ファイルのエンコーディングの種類が、この方法を記述する必要があります。 +X86 式の修正をここに使うと、誤ったビットを壊し、プログラムが動かなくなります。 + +#### 大きな定数 + +大きな定数とは、レジスタへ簡単に直接ロードできず、代わりにメモリからロードする定数です。 +セキュリティ上の理由で、*実行*権限ではなく*読み取り専用*権限などを付けた別のアドレス空間に置くことがよくあります。 +そのため、コードに対する最終的な相対アドレスは、配置によって変わります。 +これは、コンパイル単位をまたぐ呼び出しと同じです。 + +大きな定数は、コンパイル単位間で共有することもできます（HPC コードで `pi` を繰り返し使う場合など）。 +共有すると、キャッシュの占有量を減らせます。 +いずれにせよ、コードと定数の配置が決まったら、正しいオフセットからロードするようにコードを修正する必要があります。 +上の `call` の例のように、ロード命令の種類と修正方法の種類が一致しなければなりません。 +X86 では、その種類によって4バイトまたは8バイトのアドレスを使います。 +RISCV では、おそらく `LUI` と `Load` の何らかの組み合わせで、即値を20/12ビットに分けます。 +また、RISCV では同じ `LUI` で定数プールの上位20ビットを「共有」し、 +同じプールの異なる定数には異なるロードを使いたいでしょう。ARM には、さらに別の方法があります。 diff --git a/docs/chapter21/encoding-reference.md b/docs/chapter21/encoding-reference.md new file mode 100644 index 00000000..22702004 --- /dev/null +++ b/docs/chapter21/encoding-reference.md @@ -0,0 +1,798 @@ +# Instruction encoding reference + +English | [日本語](encoding-reference.ja.md) + +Detailed notes retained from the original Chapter 21 README. +See the [chapter overview](README.md) for the compiler pipeline and experiments. + +# Table of Contents + +1. [Instruction Encodings](#instruction-encodings) +2. [Infrastructure](#infrastructure) +3. [Endianness](#endianness) +4. [RISCV](#riscv) + - [Instruction formats](#instruction-formats) + - [Float](#float) + - [Indirect](#indirectmemop) + - [Branch](#branch) + - [Immediates](#immediates) + - [Float Constants](#float-constants) + - [Int Constants](#int-constants) + - [Function Constants](#function-constants) +5. [ARM](#arm) + - [Reg-form](#reg-form) + - [Shift immediates](#shift-immediates) + - [Logical Immediates](#logical-immediates) + - [Float](#float-1) + - [Large constants](#large-constants) + - [Function constant](#function-constant) + - [Conditional flags](#conditional-flags) + - [Indirect](#indirectmemop-1) + - [Branching](#branching) +6. [AMD64 X86-64](#amd64-x86-64) + - [REX PREFIX](#rex-prefix) + - [Opcode](#opcode) + - [MODR/M](#modrm) + - [SIB](#sib) + - [Displacement](#displacement) + - [Immediate](#immediate) + - [Indirect](#indirectmemop-2) + - [Float](#float-2) + - [Large constants](#large-constants-1) + - [Function constant](#function-constant-1) + - [Conditional flags](#conditional-flags-1) +7. [Relocation](#relocation) + - [Local Relocation](#local-relocation) + - [Global Relocation](#global-relocation) + - [Getting Relocations to All Agree](#getting-relocations-to-all-agree) + - [Large Constants](#large-constants-2) + + +This chapter will add instruction encodings. Instruction encoding refers to +the representation of machine instructions in a specific binary format defined +by the processor's instruction set architecture (ISA). + + +After completing instruction selection, the next step is to encode the +instructions before writing them into an ELF object file. + +To avoid ambiguity, we define the sources of the information we use to encode the instructions: + +Currently, we support these architectures: + +### RISC-V: + +For *riscv* we currently target [RVA23U64](https://msyksphinz-self.github.io/riscv-isadoc/html/). + +### ARMV8/AArch64 : +For *arm*(aarch64) we use this collection for the [encoding rules](https://docsmirror.github.io/A64/20a23-06/index.html). +*Note*: We only support 64 bits ARM encodings. + +### AMD64: +For *x86-64(amd64):*, we use the latest Intel manual for the [encoding rules](https://www.felixcloutier.com/x86/). + +-------------------------------- + +## Instruction Encodings + + +## Infrastructure + +The instruction selection phase creates the machine friendly nodes from ideal +nodes. These machine friendly nodes define an *encoding* function that is +called from the Encoding driver found in CodeGen. + +```java +for( CFGNode bb : _code._cfg ) + for( Node n : bb._outputs ) + if( n instanceof MachNode mach ) { + int off = _bits.size(); + mach.encoding(this); + _opLen[n._nid] = (byte)(_bits.size()-off); + } +``` + +Based on the selected target, we either need to look out for little endian or +big endian encodings. These are being handled by `add4` which adds to the bit +stream in the correct order. As of now the bitstream is a simple +ByteArrayOutputStream structure. + +```java +@Override public void encoding( Encoding enc ) { + enc.add4(0); // adds 4 bytes to the bitstream +} +``` + +On *RISC-V*, where the documentation provides big-endian encodings, this +function also converts them to little-endian. For other architectures, no +conversion is necessary. + +## Endianness + +ARM, RISC-V, and x86 are all little-endian architectures in practice, meaning +the least significant byte is stored first. We ensure that instruction +encodings are generated in little-endian format accordingly. + +```java +// Little endian write of a 32b opcode +public void add4( int op ) { + _bits.write(op ); + _bits.write(op>> 8); + _bits.write(op>>16); + _bits.write(op>>24); +} +``` +For example, consider a 32-bit encoding for fixed-width instructions: +*10110101100111101011001001101101*. + +We append the least significant byte first, then the next byte, and so on. +``` +_bits.write(op ); +``` + +`_bits.write()` only appends the least significant byte. By shifting the value +to the right, we can bring the next byte into the least significant position, +allowing us to write each byte in sequence. + + +-------------------------------- + +## RISCV + +RISCV instructions are all 32 bits wide, and are always little-endian. RISCV +is a RISC architecture, it prioritizes "register-to-register" forms, and has +very regular encodings. We present RISCV first because it is the simplest +encoding. + + +#### Instruction formats + +##### R-TYPE +This encoding format is used for reg-to-reg operations. +Such as `AddRISC`, `MulRISC` etc. +```java +public static int r_type(int opcode, int rd, int func3, int rs1, int rs2, int func7) { + return (func7 << 25) | (rs2 << 20) | (rs1 << 15) | (func3 << 12) | (rd << 7) | opcode; +} +``` + +##### I-TYPE +This layout is used for immediate formats. Such as `AddIRISC` + +```java + public static int i_type(int opcode, int rd, int func3, int rs1, int imm12) { + assert opcode >= 0 && rd >=0 && func3 >=0 && rs1 >=0 && imm12 >= 0; // Zero-extend by caller + return (imm12 << 20) | (rs1 << 15) | (func3 << 12) | (rd << 7) | opcode; + } +``` + +##### S-TYPE + +This encoding format is used for `StoreRISC`. + +```java +public static int s_type(int opcode, int func3, int rs1, int rs2, int imm12) { + assert imm12 >= 0; // Masked to high zero bits by caller + int imm_lo = imm12 & 0x1F; + int imm_hi = imm12 >> 5; + return (imm_hi << 25) | (rs2 << 20) | (rs1 << 15) | (func3 << 12) | (imm_lo << 7) | opcode; +} +``` + +##### B-TYPE + +This encoding layout is used by `BranchRISC`. +```java + // immf = first imm + // immd = second imm + // BRANCH +public static int b_type(int opcode, int immf, int func3, int rs1, int rs2, int immd) { + return (immd << 25 ) | (rs2 << 20) | (rs1 << 15) | (func3 << 12) | (immf << 7) | opcode; + } +``` + +##### U-TYPE +This layout is used for `AUIPC` and `LUI`(upper immediate is 20-bits). + +```java + public static int u_type(int opcode, int rd, int imm20) { + return (imm20 << 12) | (rd << 7) | opcode; + } +``` + +##### J-TYPE +Used for unconditional jumps. (`UJmpRISC`) +```java + public static int j_type(int opcode, int rd, int imm20) { + return imm20 << 12 | rd << 7 | opcode; + } +``` + +#### FLOAT +For loading float constants, we use indirect memory load(PC-relative). +``` +AUIPC dst,#hi20_constant_pool +Load dst,[dst+#low12_constant_pool] +``` + +#### INDIRECT(MemOp) + +[Load](https://msyksphinz-self.github.io/riscv-isadoc/html/rvi.html#lw): `lw rd,offset(rs1)` + +[Store](https://msyksphinz-self.github.io/riscv-isadoc/html/rvi.html#sw): `sw rs2,offset(rs1)` + +#### BRANCH +RISC-V is unusual because branch instructions include the comparison and branch target in one instruction. + +#### Immediates +We only encode the imm form for the *ALU* operations if they fit into 12 bits (signed). +Otherwise we do a Load Upper Immediate (high 20 bits) or both. + +``` +addiw a5,a5,123 +``` +vs +(do it with extra load): +``` +addw a5,a5,a4 +``` + +### FLOAT Constants +- Stored in the **constant pool**. +- Accessed via **PC-relative loads**. + +### INT Constants +- **12-bit constants** + - Use `ADDI` +- **20-bit constants** + - Use `LUI` +- **32-bit constants** + - Use `LUI` + `ADDI` combo + - + +#### Function Constants +In our RISC-V code, when we need to load a function-local constant, we store +the current PC into a register and use that as a base to access the +constant. However, we usually try to avoid loads, since simple arithmetic like +addition is faster and more efficient than accessing memory. + +```java +// auipc t0,0 +// addi t1,t0 + #0 +``` + + +-------------------------------- + +## ARM +Arm instructions are all 32 bits wide, and are always little-endian. +Arm is a RISC architecture, it prioritizes "register-to-register" forms. + +#### Reg-form +We encode the regs forms as [shifted registers](https://docsmirror.github.io/A64/2023-06/orr_log_shift.html). +``` +orr reg1, reg2 +``` +``` +x0 = x0 | (x1 << 0) +``` +The same thing applies for all the other reg forms. +Because of this similarity, we can lift the encoding of the reg form to a common function. + +```java +short self = enc.reg(n); +short reg1 = enc.reg(n.in(1)); +short reg2 = enc.reg(n.in(2)); +int body = r_reg(opcode, 0, reg2, 0, reg1, self); +enc.add4(body); +``` +*imm6* and +*shift* +are irelevant for the reg form, so we just set them to 0. + +### Shift immediates +This refers to: *asri, lsli, lsri* +Encode to shift immediates if the shift amount is between [0, 63] inclusive. + +#### ASR(immediate) +For arithmetic Shift Right immediates, we set *immr* to the immediate we wish to encode, and imms to `63` = `111111`. +This is following the rules of [asri encoding](https://docsmirror.github.io/A64/2023-06/asr_sbfm.html). + +The `sf` bit is included in the opcode, `N` is implicitly added to the bitstream after the execution of the +`imm_shift` function. +```java +enc.add4(arm.imm_shift(0b100100110,_imm, 0b111111, rn, rd)); +``` + +#### LSL(immediate) + +```java +// UBFM , , #(- MOD 64), #(63-) +// immr must be (- MOD 64) = 64 - shift +enc.add4(arm.imm_shift(0b110100110, 64 - _imm, (64 - _imm) - 1, rn, rd)); +``` + +We know that `_imm` is never a negative number and is between 0 and 63, so we can safely use `64 - _imm` as the `immr` value. +We take away this form of the immediate from 64 to invert the bits. + +For *imms* - the following condition must hold *imms + 1 = immr*; +After subbing in the values we get: + +> imms + 1 = 64 - _imm; + +> imms = (64 - _imm) - 1; + +Hence, the `imms` value is `(64 - _imm) - 1`. + +#### LSR(immediate) +Same as *ASR*. + + +#### Logical Immediates +Logical immediates refer to *andi, xori, orri*. + +```java +// Can we encode this in ARM's 12-bit LOGICAL immediate form? +// Some combination of shifted bit-masks. +private static int imm12Logical(TypeInteger ti) { + if( !ti.isConstant() ) return -1; + if( !ti.isConstant() ) return -1; + long val = ti.value(); + if (val == 0 || val == -1) return -1; // Special cases are not allowed + int immr = 0; + // Rotate until we have 0[...]1 + while (val < 0 || (val & 1)==0) { + val = (val >>> 63) | (val << 1); + immr++; + } + int size = 32; + long pattern = val; + // Is upper half of pattern the same as the lower? + while ((pattern & ((1L<> size)) { + // Then only take one half + pattern >>= size; + size >>= 1; + } + size <<= 1; + int imms = Long.bitCount(pattern); + // Pattern should now be zeros followed by ones 0000011111 + if (pattern != (1L< cond = is one of the standard conditions. + + +-------------------------------- + +## AMD64 X86-64 + +As opposed to riscv arhitectures, where the instruction width is fixed, +*x86-64* has variable width instructions. This is common with *CISC (Complex +Instruction Set Computer)* architectures, where the instruction width can vary +from 1 to 15 bytes. Since AMD64 supports many indirect addressing modes, the +goal with *CISC* in general is to complete a task in as few lines of assembly +as possible. + +### REX PREFIX + +Since we are targeting the 64-bit version of x86, we need to handle this +prefix. In 32-bit mode, however, it is typically unnecessary. + +Generally speaking the *REX* prefix must be encoded when: + - using one of the extended registers (R8 to R15, XMM8 to XMM15, YMM8 to YMM15, CR8 to CR15 and DR8 to DR15); + - using 64-bit operand size and the instruction does not default to 64-bit operand size(most ALU ops) + - using a 8-bit operand with RSI, RDI, RBP + +A *REX* prefix must not be encoded when: + - using one of the high byte registers AH, CH, BH or DH (not done currently in Simple) + +*Note:* When encoding SSE instruction, the *REX* prefix (0x40) must come after +the `SSE` prefix. In all other cases, it is ignored. + +In Simple, the REX prefix is just appended to the beginning of the bit stream +(except SSE float instructions). The layout is the following: + +| **Field** | **Length** | **Description** | +|:---------:|:----------:|---------------------------------------------------------------------------------| +| `0100` | 4 bits | Fixed bit pattern | +| `W` | 1 bit | When 1, a 64-bit operand size is used. Otherwise, 32-bit operand size is used. | +| `R` | 1 bit | Extension to the **MODRM.reg** field. | +| `X` | 1 bit | Extension to the **SIB.index** field. | +| `B` | 1 bit | Extension to the **MODRM.rm** or **SIB.base** field. | + + +```java + public static int REX_W = 0x48; +``` + +```java +public static int rex(int reg, int ptr, int idx, boolean wide) { + // assuming 64 bit by default so: 0100 1000 + int rex = wide ? REX_W : REX; + if( 8 <= reg && reg <= 15 ) rex |= 0b00000100; // REX.R + if( 8 <= ptr && ptr <= 15 ) rex |= 0b00000001; // REX.B + if( 8 <= idx && idx <= 15 ) rex |= 0b00000010; // REX.X + return rex; +} + + ... + enc.add1(x86_64_v2.rex(dst, src, 0)); +``` + +Setting THE `W` bit gives us: +`0b01001000 = 0x48;` + +#### Opcode +In our case, the opcode is a 1 byte field that specifies the operation to be performed. +``` +enc.add1(opcode()); // opcode +``` + +#### MODR/M + +| **Field** | **Length** | **Description** | +|:-------------:|:----------:|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| +| **MODRM.mod** | 2 bits | In general, when this field is `b11`, then register-direct addressing mode is used; otherwise register-indirect addressing mode is used. +| **MODRM.reg** | 3 bits | This field can have one of two values:

• A 3-bit opcode extension, which is used by some instructions but has no further meaning other than distinguishing the instruction from other instructions.

• A 3-bit register reference, which can be used as the source or the destination of an instruction (depending on the instruction). The referenced register depends on the operand-size of the instruction and the instruction itself. The `REX.R`, `VEX.~R` or `XOP.~R` field can extend this field with 1 most-significant bit to 4 bits total. | +| **MODRM.rm** | 3 bits | Specifies a direct or indirect register operand, optionally with a displacement. The `REX.B`, `VEX.~B` or `XOP.~B` field can extend this field with 1 most-significant bit to 4 bits total. | + + +We deal with the MODR/M byte in a similar way: + +The first thing we need for the modrm byte is the 2 bits mod. + +##### mod + +The layout for mod is the following: +``` +public enum MOD { + INDIRECT, // [mem] + INDIRECT_disp8, // [mem + 0x12] + INDIRECT_disp32,// [mem + 0x12345678] + DIRECT, // mem +}; +``` + +##### reg +The reg field has 3 bits, selecting one of 8 registers. When it names a +register, REX.R extends it to 4 bits, selecting one of 16 registers. + +##### r/m + +The r/m field has 3 bits. In register-direct mode, REX.B extends it to +select one of 16 registers. In memory modes, r/m selects the addressing form +or base register; some values select a SIB byte or RIP-relative addressing. + + +```java +public static int modrm(MOD mod, int reg, int m_r) { + // combine all the bits + return (mod.ordinal() << 6) | ((reg & 0x07) << 3) | m_r & 0x07; +} +``` + +The `modrm` function is then used to build up the `ModR/M` byte. +Usually this follows after the opcode. + +``` +enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, src)); +``` + +Encoding a reg form might look like this: +``` +short dst = enc.reg(this ); // src1 +short src = enc.reg(in(2)); // src2 +enc.add1(x86_64_v2.rex(dst, src, 0)); +enc.add1(opcode()); // opcode +enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, src)); +``` + +#### SIB +The SIB byte has the following fields: + +| **Field** | **Length** | **Description** | +|:-------------:|:----------:|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| +| **SIB.scale** | 2 bits | This field indicates the scaling factor of `SIB.index`, where **s** (as used in the tables) equals 2^SIB.scale^. | +| **SIB.index** | 3 bits | The index register to use. See Registers for the values to use for each of the registers. The `REX.X`, `VEX.~X` or `XOP.~X` field can extend this field with 1 most-significant bit to 4 bits total. | +| **SIB.base** | 3 bits | The base register to use. See Registers for the values to use for each of the registers. The `REX.B`, `VEX.~B` or `XOP.~B` field can extend this field with 1 most-significant bit to 4 bits total. | + +It has the same layout as the MODR/M byte. +```java +public static int sib(int scale, int index, int base) { + return (scale << 6) | ((index & 0x07) << 3) | base & 0x07; +} +``` + +```java +enc.add1(x86_64_v2.sib(_scale, idx, x86_64_v2.RBP)); +``` + +#### Displacement +Displacement can happen in 2 forms: +```java +public enum MOD { +INDIRECT, // [mem] +INDIRECT_disp8, // [mem + 0x12] +INDIRECT_disp32,// [mem + 0x12345678] +DIRECT, // mem +}; +``` + +```java +if( mod == MOD.INDIRECT_disp8 ) { + enc.add1(offset); +} else if( mod == MOD.INDIRECT_disp32 ) { + enc.add4(offset); +} +``` +The displacement goes before the immediate, so for example: +``` +sub [eax + 2], 4 +``` +``` +bytes.write(0x83); +bytes.write(modrm(INDIRECT8, 5, 0 /* eax */)); +bytes.write(2); // displcement goes first +bytes.write(4); +``` + +#### Immediate +The immediate byte/bytes go after the `ModR/M` byte, we are capable of encoding 4 bytes of immediates depending on the need. +```java +// immediate(4 bytes) 32 bits or (1 byte)8 bits +if( x86_64_v2.imm8(_imm) ) enc.add1(_imm); +else enc.add4(_imm); +``` + +#### INDIRECT(MemOp) +X86-64 support multiple indirect addressing modes: + + +#### Float +For float operations we use `SSE SIMD` instructions that operate on scalar single precision floating-point values located in the +XMM registers or memory. +*Note*: When using XMM registers for ALU operations, the encoding is really similar with the exception that we need +to subtract the `XMM_OFFSET` from the register number. +We count the registers continuously, so we need to subtract the offset to get the GPR register pair that corresponds to the XMM register. + +```java +short dst = (short)(enc.reg(this ) - x86_64_v2.XMM_OFFSET); +``` + +```java +public static int XMM_OFFSET = 16; +``` + +| **X.Reg** | **8-bit GP** | **16-bit GP** | **32-bit GP** | **64-bit GP** | **80-bit x87** | **64-bit MMX** | **128-bit XMM** | **256-bit YMM** | **16-bit Segment** | **32-bit Control** | **32-bit Debug** | +|:--------:|:------------:|:-------------:|:-------------:|:-------------:|:-------------:|:-------------:|:--------------:|:--------------:|:-----------------:|:-----------------:|:---------------:| +| `0.000 (0)` | AL | AX | EAX | RAX | ST0 | MMX0 | XMM0 | YMM0 | ES | CR0 | DR0 | + +We see that `XMM0` corresponds to `RAX` and so on. + +#### Large constants + +##### INT: We just use `MOV r64, imm64` instruction form. + +##### FLOAT: We use relocation and use constant from memory. + +#### Function constant +To load a function constant we use lea which will load the address into the specified reg +relative to the instruction pointer. +`lea rax, [rip+disp32]` + +#### Conditional flags: +The FLAGS register is the status register that contains the current state of an x86 CPU. + +Let's consider a simple example that presents all the instructions that we need to encode for +conditional code. + +``` +int square(int a) { + // cmp DWORD PTR [rbp-0x8],0x1 + // `sete al` + bool da = a == 1; + + // cmp eax,0x1 + if(da == 1) { + return 1; + } + return 2; +} +``` + +First we need a compare instruction comparing `a` with 1. +``` +cmp DWORD PTR [rbp-0x8],0x1 +``` + +This compare instruction then sets the conditional flags: +> The CF, OF, SF, ZF, AF, and PF flags are set according to the result. + +We then use the `sete` instruction to save out the result of the comparison to a register: + +`sete al` + +For the if condition we do an extra comparison based on the result of the first bool. +``` + cmp eax,0x1 +``` + +And then a conditional branch that is relying on the flags set by the comparison(`a == 1`). +``` +jne 1159 +``` + + +-------------------------------- + + +## Relocation + +Relocation allows code to be *relocated* to a new code offset. Code often +refers to other code and data; `call` instructions target subroutines, +`branches` target other instructions, large constants are often loaded from a +*constant pool*. + +### Local Relocation + +Local relocation patches up local, or self-referential, code; the most common +form is branch targets. When writing instructions into the `BAOS` (Byte Array +Output Stream) forwards branches towards future instructions have an unknown +offset - the offset depends on the size of the encodings in between the branch +and target. For `riscv` and `arm` targets this sounds easy (and instructions +are 4 bytes, so just count instructions)... except that some encodings use +multiple instructions so are not actually 4 bytes long. For X86's wild +psuedo-random instruction lengths the act of figuring out the opcode length is +just as hard as writing the opcode in the first place. + +X86 adds another wrinkle: short and long form branches. If a branch target +lies within a signed byte range (+/-127) X86 will use a 2 byte branch encoding, +otherwise a 6 byte encoding. Simple includes a pass to compact these branches +and use 2 bytes wherever possible - but this pass has to slide code around +which changes all the other branch offsets. The "compact" pass actually starts +optimistically assuming all branches can use the 2 byte form, and then expands +branches as needed (so really *expands* the code). + +Once the code is finally settled into "shape", a local relocation pass is made +to update all the self-references. Basically, the branch offsets in the byte +array get overwritten with the actual values. + +At the end of this pass, the code is locally correct at some offset (generally +0), but this is not the end - code is often *linked* against other code +generated in other compilations, and again various offsets will need to be +adjusted. + +### Global Relocation + +Code in one compilation unit wants to call code in another... this requires a +*global relocation*. A common example is a *loader* loading an *ELF* file, +which mostly happens every time a new program is run, and requires the +relocation information to be stored to disk (in e.g. the ELF file). JIT +systems will neeed to do this as well across different compilations, although +the relocation information can stay in memory. + +#### Getting Relocations to All Agree + +Since the relocations can be written to disk, the disk format, loader and "code +shape" all have to agree. Suppose we want to call from one compilation unit to +another - e.g. the program is calling `malloc` from `libc`. The caller is a +Simple using a machine-specific version of generic `CallNode` with the target +being C-compiled code. During loading, the placement of the `call` and `libc` +is determined by the loader; the two different blocks of code are written into +memory in some order (generally with lots of other blocks of code). Now we +need to patch the `call`'s target to be `malloc` in the `libc` block of code. + +For an X86 external call, the encoding is a 5-byte instruction, one byte of +opcode and 4 bytes of PC-relative target address. The needed patch is the +delta between the X86-specific `call` instruction *end* and the start of +`malloc`, and is written directly on the last 4 bytes of the `call`. The +encoding type in the ELF file has to describe this. + +For a RISCV external call, the encoding is 2 4-byte instructions each carrying +some of the bits. The `LUI` loads the target upper 20 bits, and then the +`JALR` adds in the lower 12 bits (32-bit absolute target range). The `LUI` +might be replaced with a `AUIPC` to get a 32-bit pc-relative range. Patching +here updates 20bits in one instruction and 12bits in another. Again the ELF +file encoding type has to describe this; using a X86-style patch here will just +crush the wrong bits and make a broken program. + +#### Large Constants + +Large constants are those which cannot be easily directly loaded into a +register, and instead are loaded from memory. For security reasons they are +often kept in a seperate address space with e.g. *read-only* permissions instead +of *execute* permissions. This means their final address, relative to the code, +varies according to placement - same as for calls crossing compilation units. + +Also large constants can be shared across compilation units (one can imagine +repeated uses of `pi` in HPC codes); sharing reduces cache footprint. In any +case, once the locations of the code and constants are known, the code needs to +be patched to load at the correct offset. Like the `call` example above, the +load instruction variant and patch variant all need to agree. An X86 might use +either a 4-byte address or an 8-byte address depending on X86 variant; the +RISCV probably uses some variant of an `LUI` and a `Load`, with the immediate +split into 20/12 bits. Also the RISCV probably wants to "share" the constant +pool 20 bits in the same `LUI`, but have different loads for different +constants coming out of the same pool. ARM will have yet another variant. + diff --git a/docs/chapter21/font-awesome-4.7.0.zip b/docs/chapter21/font-awesome-4.7.0.zip new file mode 100644 index 00000000..b6bdb4bd Binary files /dev/null and b/docs/chapter21/font-awesome-4.7.0.zip differ diff --git a/docs/chapter21/ifg_trim.pdf b/docs/chapter21/ifg_trim.pdf new file mode 100644 index 00000000..d952fd4f Binary files /dev/null and b/docs/chapter21/ifg_trim.pdf differ diff --git a/docs/chapter21/lattice.gv b/docs/chapter21/lattice.gv new file mode 100644 index 00000000..8661082d --- /dev/null +++ b/docs/chapter21/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/chapter21/lattice.svg b/docs/chapter21/lattice.svg new file mode 100644 index 00000000..e72b473b --- /dev/null +++ b/docs/chapter21/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/chapter21/lattice2.gv b/docs/chapter21/lattice2.gv new file mode 100644 index 00000000..6aa37fa0 --- /dev/null +++ b/docs/chapter21/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/chapter21/lattice2.svg b/docs/chapter21/lattice2.svg new file mode 100644 index 00000000..8b682aa7 --- /dev/null +++ b/docs/chapter21/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/chapter21/pardoe.docx b/docs/chapter21/pardoe.docx new file mode 100644 index 00000000..24fde921 Binary files /dev/null and b/docs/chapter21/pardoe.docx differ diff --git a/docs/chapter21/webtcp.min.js b/docs/chapter21/webtcp.min.js new file mode 100644 index 00000000..bf23ee5a --- /dev/null +++ b/docs/chapter21/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