summaryrefslogtreecommitdiff
path: root/chapter21
diff options
context:
space:
mode:
Diffstat (limited to 'chapter21')
-rw-r--r--chapter21/README.ja.md118
-rw-r--r--chapter21/README.md2
-rw-r--r--chapter21/docs/18-grammar.ja.md138
-rw-r--r--chapter21/docs/18-grammar.md2
-rw-r--r--chapter21/docs/encoding-reference.ja.md777
-rw-r--r--chapter21/docs/encoding-reference.md2
6 files changed, 1039 insertions, 0 deletions
diff --git a/chapter21/README.ja.md b/chapter21/README.ja.md
new file mode 100644
index 00000000..dbf11374
--- /dev/null
+++ b/chapter21/README.ja.md
@@ -0,0 +1,118 @@
+# 第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) することもできます。
+
+## マシンノードからバイトへ
+
+命令選択は演算とレジスタ制約を選びます。レジスタ割り当ては物理レジスタとスタックスロットを割り当てます。その後、エンコーディングがオペコード、割り当て済みレジスタ、即値オペランドを命令バイトへ組み合わせます。この時点で命令は別のレジスタを選べません。周囲の命令が、すでに割り当て器の選択に依存しているためです。
+
+[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 | 可変命令長、レジスタ接頭辞、アドレッシング形式、短い分岐と長い分岐。 |
+
+たとえば小さな整数は命令に直接収まる一方、大きな整数には複数命令や定数プールからのロードが必要なことがあります。その結果、固定幅命令を持つ対象でも、マシンノードによって異なるバイト数を出力できます。
+
+[エンコーディングリファレンス](docs/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/chapter21/README.md b/chapter21/README.md
index 5e7baaa1..57705fa7 100644
--- a/chapter21/README.md
+++ b/chapter21/README.md
@@ -1,5 +1,7 @@
# Chapter 21: Instruction Encoding and ELF
+English | [日本語](README.ja.md)
+
[Previous: Chapter 20](../chapter20/README.md) |
[Next: Chapter 22](../chapter22/README.md)
diff --git a/chapter21/docs/18-grammar.ja.md b/chapter21/docs/18-grammar.ja.md
new file mode 100644
index 00000000..dbd7f0fd
--- /dev/null
+++ b/chapter21/docs/18-grammar.ja.md
@@ -0,0 +1,138 @@
+# 第21章の文法
+
+[English](18-grammar.md) | 日本語
+
+この文書は [原文](18-grammar.md) の日本語訳です。
+
+> 訳注: 原文の見出しは「Grammar for Chapter 16」です。この日本語版では、配置されている第21章に合わせた見出しにしています。
+
+[第21章に戻る](../README.ja.md)
+
+```antlrv4
+grammar SimpleLanguage;
+
+program : block EOF ;
+
+block : statement+ ;
+
+
+statement
+ : '{' block '}'
+ | returnStatement
+ | ifStatement
+ | whileStatement
+ | breakStatement
+ | continueStatement
+ | structDeclaration
+ | expressionStatement
+ ;
+
+
+returnStatement : 'return' expression ';' ;
+
+ifStatement : 'if' '(' expression ')' statement ('else' statement)? ;
+
+whileStatement : 'while' '(' expression ')' statement ;
+
+breakStatement : 'break' ';' ;
+
+continueStatement : 'continue' ';' ;
+
+
+structDeclaration : 'struct' IDENTIFIER '{' block '}' ;
+
+expressionStatement
+ : type IDENTIFIER ';'
+ | type IDENTIFIER '=' expression ';'
+ | IDENTIFIER '=' expression ';'
+ | expression
+ ;
+
+PRIMTYPE
+ : 'int'
+ | 'i8'
+ | 'i16'
+ | 'i32'
+ | 'i64'
+ | 'u8'
+ | 'u16'
+ | 'u32'
+ | 'flt'
+ | 'f32'
+ | 'f64'
+ | 'bool'
+ ;
+
+type
+ : PRIMTYPE
+ | typeName '?'?
+ | typeName nestedArray+
+ ;
+
+nestedArray : '?'? '[]'* ;
+
+typeName : IDENTIFIER ;
+
+
+expression : bitWiseExpression ;
+
+bitWiseExpression
+ : comparisonExpression ( '&' | '|' | '^' ) comparisonExpression)*
+ ;
+
+comparisonExpression
+ : shiftExpression (('==' | '!='| '>'| '<'| '>='| '<=') shiftExpression)*
+ ;
+
+shiftExpression
+ : additiveExpression ( '<<' | '>>>' | '>>' ) additiveExpression)*
+ ;
+
+additiveExpression
+ : multiplicativeExpression (('+' | '-') multiplicativeExpression)*
+ ;
+
+multiplicativeExpression
+ : unaryExpression (('*' | '/') unaryExpression)*
+ ;
+
+unaryExpression
+ : ('-') unaryExpression
+ | '!' unaryExpression
+ | primaryExpression postAssign
+ ;
+
+primaryExpression
+ : INTEGER_LITERAL
+ | FLOAT_LITERAL
+ | '(' expression ')'
+ | 'true'
+ | 'false'
+ | 'null'
+ | newExpression
+ | IDENTIFIER
+ ;
+
+newExpression
+ : 'new' IDENTIFIER [ '{' block '}' ]
+ | 'new' IDENTIFIER '[' expression ']'
+ ;
+
+postAssign : postFix [ '=' expression ] | [ '#' ];
+
+postFix
+ : '.' IDENTIFIER postFix
+ | '[' expression ']' postFix
+ ;
+
+
+IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ;
+
+INTEGER_LITERAL
+ : [1-9]DIGIT*
+ | [0]
+ ;
+
+NON_DIGIT: [a-zA-Z_];
+DIGIT: [0-9];
+```
diff --git a/chapter21/docs/18-grammar.md b/chapter21/docs/18-grammar.md
index 7da725e9..51539d0b 100644
--- a/chapter21/docs/18-grammar.md
+++ b/chapter21/docs/18-grammar.md
@@ -1,5 +1,7 @@
# Grammar for Chapter 16
+English | [日本語](18-grammar.ja.md)
+
```antlrv4
grammar SimpleLanguage;
diff --git a/chapter21/docs/encoding-reference.ja.md b/chapter21/docs/encoding-reference.ja.md
new file mode 100644
index 00000000..8ccdc728
--- /dev/null
+++ b/chapter21/docs/encoding-reference.ja.md
@@ -0,0 +1,777 @@
+# 命令エンコーディングの参考資料
+
+[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 <Xd>, <Xn>, #(-<shift> MOD 64), #(63-<shift>)
+// immr must be (-<shift> 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)-1)) == (pattern >> 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<<imms)-1) return -1;
+ imms--;
+ if (size == 64) return 0x1000 | immr << 6 | imms;
+ return (32-size)<<1 | immr << 6 | imms;
+}
+```
+
+imm12Logical は、エンコードできる場合は論理演算の12ビットの即値エンコーディングを返し、
+できない場合は -1 を返します。
+```java
+int imm12;
+return and.in(2) instanceof ConstantNode off &&
+off._con instanceof TypeInteger ti && (imm12 = imm12Logical(ti)) != -1
+? new AndIARM(and, imm12)
+```
+```java
+arm.imm_inst(enc,this,0b100100100,_imm);
+```
+
+#### 浮動小数点数
+
+x86 と同じように、*D* レジスタに対応する汎用レジスタ（GPR）のペアを得るために、オフセットを引く必要があります。
+```
+short dst = (short)(enc.reg(this ) - arm.D_OFFSET);
+```
+
+浮動小数点定数をロードするには、`ldr(literal)` 命令を使います。
+オフセットを PC レジスタに加算して、リテラルのアドレスを求めます。
+
+```java
+// Any number that can be expressed as +/-n * 2-r,where n and r are integers, 16 <= n <= 31, 0 <= r <= 7.
+int body = arm.load_pc(0b01011100, 0, dst);
+```
+
+#### 大きな定数
+
+##### 整数：mov（movz、movk、movn）をさまざまに組み合わせて、PC 相対ロードを避けられます。
+
+##### 浮動小数点数：PC 相対の *LDR（immediate, SIMD&FP）* 命令を使います。
+
+#### 関数定数
+
+関数定数をロードするには、現在の PC を x0 に格納し、それを使って定数へアクセスします。
+一般に、加算のほうが速いためロードを避けるようにします。
+```
+adrp x0, 0
+add x0, x0, 0
+```
+
+#### 条件フラグ
+
+arm では比較後に条件フラグを設定します。これは x86 と同じように動作します。
+
+```
+int square(int a) {
+// subs
+// cset w8, eq // eq = none
+bool da = a == 1;
+ // bne
+ if(da == 1) {
+ return 1;
+ }
+ return 2;
+}
+```
+
+arm の比較は `subss` で行い、2つのオペランドの減算とフラグの設定を同時に行います。
+`CSET` はフラグを調べ、その結果をレジスタに保存します。
+
+後で `b.ne` が条件付き分岐を実行しようとするときにも、このフラグに依存します。
+
+#### 間接参照（MemOp）
+
+Arm は次の間接参照形式をサポートします。
+
+[ロード](https://docsmirror.github.io/A64/2023-06/ldr_reg_gen.html)：`ldr dst, [base + index]`。base と index はどちらもレジスタです。
+
+[ロード](https://docsmirror.github.io/A64/2023-06/ldr_imm_gen.html)：`ldr dst, [base + #offset]`。base はレジスタ、offset は即値です。
+
+[ストア](https://docsmirror.github.io/A64/2023-06/str_reg_gen.html)：`str dst, [base + index]`
+
+[ストア](https://docsmirror.github.io/A64/2023-06/strb_imm.html)：`str dst, [base + #offset]`
+
+オフセットが定数でなければ……（訳注：原文のこの文は途中で途切れています）。
+
+#### 分岐
+
+`B.cond` は、PC 相対オフセットのラベルへ[条件付き](https://developer.arm.com/documentation/dui0802/b/A32-and-T32-Instructions/Condition-codes?lang=en)で分岐します。
+
+> 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 プレフィックスをビットストリームの先頭に追加するだけです
+（SEE の浮動小数点命令を除く。訳注：「SEE」は原文の表記です）。配置は次のとおりです。
+
+| **フィールド** | **長さ** | **説明** |
+|:---------:|:----------:|---------------------------------------------------------------------------------|
+| `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種類の値を取れる。<br><br>• 一部の命令が使う3ビットのオペコード拡張。ほかの命令と区別する以上の意味は持たない。<br><br>• 命令によってソースまたは宛先として使う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ビットのフィールドで、15種類のレジスタをエンコードできます。
+（訳注：ビット数とレジスタ数について、ここでは原文の記述を保持しています。）
+
+##### r/m
+
+rm フィールドは直接または間接のレジスタオペランドを指定し、15種類のレジスタをエンコードできます。
+
+```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 レジスタまたはメモリにあるスカラーの単精度浮動小数点値を操作する
+`SEE 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 <square(int)+0x29>
+```
+
+--------------------------------
+
+## 再配置
+
+再配置によって、コードを新しいコードオフセットへ*移動*できます。
+コードは、ほかのコードやデータを参照することがよくあります。
+`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/chapter21/docs/encoding-reference.md b/chapter21/docs/encoding-reference.md
index e273caec..5853b380 100644
--- a/chapter21/docs/encoding-reference.md
+++ b/chapter21/docs/encoding-reference.md
@@ -1,5 +1,7 @@
# 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.
generated by cgit v1.2.3 (git 2.25.1) at 2026-10-15 13:41:43 +0000