Chapter 21: Instruction Encoding and ELF

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 <tejasae-afk@users.noreply.github.com>
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 <jun784@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

1 files changed, 170 insertions, 0 deletions

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.
+
+<!-- spill-matrix:start -->
+| 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 |
+<!-- spill-matrix:end -->
+