diff options
| -rw-r--r-- | chapter19/README.md | 14 | ||||
| -rw-r--r-- | chapter20/README.md | 56 | ||||
| -rw-r--r-- | chapter21/README.md | 88 |
3 files changed, 117 insertions, 41 deletions
diff --git a/chapter19/README.md b/chapter19/README.md index a866876d..752e139f 100644 --- a/chapter19/README.md +++ b/chapter19/README.md @@ -3,6 +3,20 @@ You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter19) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter18...linear-chapter19) it to the previous chapter. +## Meta-Issues / Code-Dev Issues of Instruction Selection, Register Allocation and Encodings + +The output of Instruction Selection - the mapping from idealized Simple Nodes +to machine-specific ones - is difficult to test in bulk without an execution +strategy. We won't have an execution stratgy 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. + + ## Portable Compilation A new abstract `Machine` class is added, one per unique CPU port. `Machine` diff --git a/chapter20/README.md b/chapter20/README.md index b06e1f7a..06bc481f 100644 --- a/chapter20/README.md +++ b/chapter20/README.md @@ -21,6 +21,20 @@ I've included a very old unpublished paper on speeding up graph coloring allocators: [Interference Graph Triming](docs/ifg_trim.pdf). +## Meta-Issues / Code-Dev Issues of Instruction Selection, Register Allocation and Encodings + +The output of Register Allocation - an allocation of registers to ops - is +difficult to test in bulk without an execution strategy. We won't have an +execution stratgy 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. + + You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter20) 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-chapter19...linear-chapter20) it to the previous chapter. @@ -216,8 +230,8 @@ If the live range `_mask` field goes empty, you might have a *hard conflict* or have gotten *killed*. Live ranges can self-interfere, making a *self-conflict*. During coloring you might discover an uncolorable clique of interfering live ranges, leading to a *capacity spill*. This leads to a set of -levels of conflicts within a live range (and thus a different heuristics for -handling them). +levels of conflicts within a live range (and different heuristics for handling +them). ### Hard-Conflicts @@ -249,7 +263,7 @@ collection - and hence speedup allocation by a large constant factor. ### Self-Conflicts -A live-range can *self-conflict* be alive twice with 2 different values but +A live-range can *self-conflict*: be alive twice with 2 different values but require the same register. This live range *must* split and thus picks up a copy from the split. This happens with loop-carried dependencies as seen in e.g. a simple `fib` program: @@ -359,12 +373,13 @@ risky live range to color after all. Here we failed to get a coloring - and need to split. Some specific live ranges did not color and we will need to decide how to split. Again there are -tensions here: too much splitting leads to a bad allocation, to little leads to +tensions here: too much splitting leads to a bad allocation, too little leads to no-progress bugs (manifested as too many rounds of splitting past some arbitrary cutoff). -We start by looking at each spilling live range in turn, and deciding -on a splitting strategy. +We start by sorting the spills to be deterministic (else they are sorted by +HashMap visitation order), then looking at each spilling live range in turn +and deciding on a splitting strategy. ### Split Self Conflict @@ -385,7 +400,7 @@ This set of splits is fairly aggressive... but test cases requiring a split in each of the listed locations are including in Chapter 20's test cases. We cannot even attempt a color while we have self conflicts, so its important to break up these live ranges quickly. This tends to over-split and the allocator -leans on Biased Coloring to remove some of the extras. +leans on Biased Coloring and Coalescing to remove some of the extras. ### Split Hard Conflict @@ -395,9 +410,14 @@ direct def/use conflicts (e.g. defined in `rdi` and used in `rax`). They also can be discovered during the "Build the Interference Graph" pass (e.g. incoming argument in `rdi` used later in the program and killed by a `Call`). -For simple hard-conflicts, we have the exact def and use kept in the Live Range -itself. We split once after the def and once before the use (and only on sides -with restricted registers). +For simple hard-conflicts (a single def and single use), we have the exact def +and use kept in the Live Range itself. We split once after the def and once +before the use (and only on sides with restricted registers). + +Another common case is popular constants (e.g. 0): a single def with many uses, +and some of the uses require certain registers. Instead of splitting the +popular constant everywhere, we first split it into "register classes" and see +if we can remove the hard conflict with fewer spills. For more complex cases we use the capacity spilling/loop-nest technique. @@ -424,6 +444,22 @@ splitting around the next inner loop nest. This process repeats until we end up splitting in the inner-most loops. +### Helpers + +RA uses a series of helper functions, each is fairly self-contained. + +- **findAllLRG** - find all the defs and uses of a live range in time O(|LRG|) + instead of time O(N). +- **insertBefore** and **insertAfter** - insert a split either before a use or + after a def. Includes the work to put the split in its proper ordering in + a Basic Block and do all edge maintenance. +- **makeSplit** - Make a split (either clone a clonable constant, or ask the + `Machine` for a port-specific `SplitNode`. +- **ldepth** - Given a min&max loop depth (compacted in a `long`), expand the + loop depth range for a given node `n`. Used to decide when a def or use is + "inside" a loop, which in turn is used to split around loops. + + ## Post Allocation After a successful coloring, we want to pull out any same-same register splits. diff --git a/chapter21/README.md b/chapter21/README.md index 7d08036c..58969581 100644 --- a/chapter21/README.md +++ b/chapter21/README.md @@ -1,5 +1,18 @@ # 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 stratgy 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. + # Table of Contents @@ -41,10 +54,9 @@ - [LUI](#lui) - [Large constants](#large-constants) -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). +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 @@ -53,6 +65,7 @@ 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: + ### AMD64: For *x86-64(amd64):*, we use the latest Intel manual for the [encoding rules](https://www.felixcloutier.com/x86/). @@ -60,8 +73,6 @@ For *x86-64(amd64):*, we use the latest Intel manual for the [encoding rules](ht 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/2023-06/index.html). *Note*: We only support 64 bits ARM encodings. @@ -73,8 +84,9 @@ For *arm*(aarch64) we use this collection for the [encoding rules](https://docsm ## 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. +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 ) @@ -85,9 +97,11 @@ for( CFGNode bb : _code._cfg ) _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 BAOS stucture. + +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 BAOS +stucture. ```java @Override public void encoding( Encoding enc ) { @@ -98,7 +112,9 @@ 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. +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 @@ -117,28 +133,37 @@ 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. +`_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. + ## AMD64 -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. + +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. + +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) A *REX* prefix must not be encoded when: - - using one of the high byte registers AH, CH, BH or DH. + - 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. +*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: +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** | |:---------:|:----------:|---------------------------------------------------------------------------------| @@ -151,9 +176,8 @@ The layout is the following: ```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 @@ -166,7 +190,6 @@ public static int rex(int reg, int ptr, int idx, boolean wide) { ... enc.add1(x86_64_v2.rex(dst, src, 0)); -} ``` Setting THE `W` bit gives us: @@ -181,7 +204,7 @@ enc.add1(opcode()); // opcode | **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.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. | @@ -194,10 +217,10 @@ The first thing we need for the modrm byte is the 2 bits mod. The layout for mod is the following: ``` public enum MOD { -INDIRECT, // [mem] -INDIRECT_disp8, // [mem + 0x12] -INDIRECT_disp32,// [mem + 0x12345678] -DIRECT, // mem + INDIRECT, // [mem] + INDIRECT_disp8, // [mem + 0x12] + INDIRECT_disp32,// [mem + 0x12345678] + DIRECT, // mem }; ``` @@ -492,7 +515,7 @@ int body = arm.load_pc(0b01011100, 0, dst); ##### 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 +##### FLOAT: We use the *LDR (immediate, SIMD&FP)* instruction relative to the PC #### Function constant @@ -661,6 +684,9 @@ we store the current PC into a register and use that as a base to access the con // auipc t0,0 // addi t1,t0 + #0 ``` + + + ## Relocation ## Local paches: TBD |