diff options
Diffstat (limited to 'chapter21/README.md')
| -rw-r--r-- | chapter21/README.md | 954 |
1 files changed, 146 insertions, 808 deletions
diff --git a/chapter21/README.md b/chapter21/README.md index c5b41bc7..cd3a46ae 100644 --- a/chapter21/README.md +++ b/chapter21/README.md @@ -1,810 +1,148 @@ # Chapter 21: Instruction Encoding and ELF -## Meta-Issues / Code-Dev Issues of Instruction Selection, Register Allocation and Encodings - -The output of Encodings - conversion of machine Nodes to instruction bits - is -difficult to test in bulk without an execution strategy. We won't have an -execution strategy until all three of Instruction Selection, Register Allocation -and Encodings are done. Hence in and around the completion of Encoding we -expect to find lots of bugs in Instruction Selection and Register Allocation. -We certainly hand-inspect the output and fix obvious problems, but still lots -bugs linger until we can actually run the code. - -This means that other chapters have updates and bug-fixes to the work being -described here. - -Encodings are an entirely bit-picky nit-picky affair. There's no real rocket -science here, but instead there's an boundless opportunity for off-by-1 errors. -If you find a bug here, do not be surprised! Its almost surely a "shallow" -bug... and there's bound to be a few until Simple gets more programmer hours -under its belt. - - - -You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter21) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter20...linear-chapter21) it to the previous chapter. - -# 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-2) - - [Branch](#branch) - - [Function Constant](#function-constant) - - [LUI](#lui) - - [Large constants](#large-constants) -5. [ARM](#arm) - - [Reg-form](#reg-form) - - [Shift immediates](#shift-immediates) - - [asri](#asrimmediate) - - [LSL(immediate)](#lslimmediate) - - [LSR(immediate)](#lsrimmediate) - - - [Logical Immediates](#logical-immediates) - - [Float](#float) - - [Function constant](#function-constant) - - [Immediate](#immediate) - - [Conditional flags](#conditional-flags) - - [Indirect](#indirectmemop-1) - - [Branching](#branching-) - - [Rip relative](#rip-relative) - - [Compare](#compare) -6. [AMD64](#amd64) - - [REX PREFIX](#rex-prefix) - - [Large constants](#large-constants) - - [MODR/M](#modrm) - - [SIB](#sib) - - [Displacement](#displacement) - - [Immediate](#immediate) - - [Float](#float) - - [Indirect](#indirectmemop) - - [Conditional flags](#conditional-flags) - - -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 <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)); -``` - -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)-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 returns the 12-bit immediate encoding for logical operations if it is possible to encode it, otherwise -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); -``` - -#### Float -Similarly to x86, we have to subtract the offset to get the GPR register pair that corresponds to the *D* register. -``` -short dst = (short)(enc.reg(this ) - arm.D_OFFSET); -``` -For loading float constants we use the `ldr(literal)` instruction. -The offset is added to the PC register to get the address of the literal. - -```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); -``` - -#### Large constants - -##### INT: We can use different combinations of movs(movz, movk, movn) - this allows us to avoid PC relative loading. - -##### FLOAT: We use the *LDR (immediate, SIMD&FP)* instruction relative to the PC - - -#### Function constant -To load a function constant we store the current PC into x0 and use that to access the constant. -Generally, we try to avoid load as adding is faster. -``` -adrp x0, 0 -add x0, x0, 0 -``` - -#### Conditional flags -In arm we set the conditional flags after a comparison - -this works similarly to x86. - -``` -int square(int a) { -// subs -// cset w8, eq // eq = none -bool da = a == 1; - // bne - if(da == 1) { - return 1; - } - return 2; -} -``` -In arm comparisons are done with `subss` which does a subtraction between the two -operands and also sets the flags. -`CSET` is used to look up the flags and save it out to a register. - -Later on `b.ne` relies on this flag again when it attempts to conditionally execute a branch. - -#### INDIRECT(MemOp) -Arm supports the following indirect forms: - -[Load](https://docsmirror.github.io/A64/2023-06/ldr_reg_gen.html): `ldr dst, [base + index]` where both, base and index are registers. - -[Load](https://docsmirror.github.io/A64/2023-06/ldr_imm_gen.html): `ldr dst, [base + #offset]` where base is a register and the offset is an immediate. - -[Store](https://docsmirror.github.io/A64/2023-06/str_reg_gen.html): `str dst, [base + index]` - -[Store](https://docsmirror.github.io/A64/2023-06/strb_imm.html): `str dst, [base + #offset]` - -If the offset is not a con -#### Branching -`B.cond` - branch [conditionally](https://developer.arm.com/documentation/dui0802/b/A32-and-T32-Instructions/Condition-codes?lang=en) to a label at a PC-relative offset. - -> 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 SEE 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:<br><br>• A 3-bit opcode extension, which is used by some instructions but has no further meaning other than distinguishing the instruction from other instructions.<br><br>• 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 is a 3 bit field capable of encoding 15 different registers. - -##### r/m - -The rm field specifies a direct or indirect register operand and is capable of encoding 15 different registers. - - -```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 `SEE SIMD` instructions that operate on scalar single precision floating0-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 <square(int)+0x29> -``` - - --------------------------------- - - -## 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. - +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). + +## 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, but their machine nodes own the bit details. + +| 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](docs/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 implementations live under +[node/cpus](src/main/java/com/seaofnodes/simple/node/cpus). + +## 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 + +`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: conservative copy coalescing + +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. This simple conservative rule +preserves a color choice even if every neighbor takes a different register. + +Merging also updates neighboring adjacency lists and removes sample references +to the deleted copy. A rejected merge restores the original adjacency list. +Mask compatibility alone is insufficient: two values that are simultaneously +live cannot share a register merely because both permit it. + +Chapter 20's legality and progress fixes carry forward, including compatible +rematerialization and clobber-aware copy reuse. Chapter 21 retains its native +frame and ABI support. Stronger color bias and cheap-spill ranking are reserved +for Chapter 22, popular-use grouping for 23, cold-first loop splitting for 24, +and area/cost ranking for 25. + +These are measured sums with **this chapter's compiler**, default optimizer seed +123, on Windows x86-64. A split is a retained `SplitNode`, including register +moves; it is not necessarily a memory spill. Weighted counts multiply each split +by `8^loopDepth`. + +| Test cohort | Allocations | Splits | Loop-weighted splits | +|---|---:|---:|---:| +| Chapter 20 | 39 | 401 | 653 | +| Chapter 21 | 52 | 483 | 1,141 | +| Total | 91 | 884 | 1,794 | + +The Chapter 20 row freezes all 13 original inputs, including BrainFuck and +MergeSort, on three SystemV targets. They live in `Chapter20Test`. The revised +sources/ABI cases previously in that file are retained in `Chapter21AllocTest`; +together with `Chapter21Test` and the native BrainFuck/MergeSort tests they form +the Chapter 21 row. That row includes 17 ARM/SystemV, 17 RISC-V/SystemV, eight +x86/SystemV, and ten x86/Win64 compilations. Native host ABI changes affect this +row; compare the same host and targets. + +| Controlled comparison, same 91 compilations | Splits | Loop-weighted splits | +|---|---:|---:| +| Current compiler with coalescing disabled | 1,074 | 1,921 | +| Current compiler with coalescing | 884 | 1,794 | +| Original Chapter 21 snapshot, including later heuristics | 794 | 1,620 | + +The controlled run disables only the `Coalesce.coalesce` call in `graphColor`; +allocation, register-constraint, and runtime checks still pass. Its different +spill goldens are reported as failures, as intended for this experiment. + +Coalescing saves 190 moves (17.7%) and 127 weighted moves (6.6%) against the same +corrected compiler without coalescing. It is not uniformly beneficial; use the +summed measurements to judge the change. + +Deferring the later heuristics has a visible cost against the old snapshot: +weighted totals rise by 174 (10.7%). RISC-V BrainFuck rises from 28 to 211 in the +native case, while sieve improves from 257 to 178 on x86/Win64, 160 to 89 on +RISC-V, and 160 to 93 on ARM. These are reported costs of the staged tutorial, +not evidence that the simplified allocator beats the original combined one. +Chapter 20's 355 weighted splits also cannot be read as a coalescing baseline: +Chapter 21 changes machine lowering and implements native ABI obligations. +The controlled comparison above holds those changes fixed. |