diff options
Diffstat (limited to 'content')
| -rw-r--r-- | content/machine-code-generation.md | 895 |
1 files changed, 895 insertions, 0 deletions
diff --git a/content/machine-code-generation.md b/content/machine-code-generation.md new file mode 100644 index 0000000..ebf2fe2 --- /dev/null +++ b/content/machine-code-generation.md @@ -0,0 +1,895 @@ +Title: Lessons learned on machine code generation +Date: 2021-06-16 +Category: +Tags: +Slug: machine-code-generation +Lang: en +Summary: + A summary of the lessons I learned about machine code generation during my + work at Lightening, Hex0 and all my recent research on compilers. + + +Machine code generation sounded like a weird magic to me half a year ago, I +swear, but now it doesn't look so disturbingly complicated. *Nothing in +computer science is that complicated, after all*. + + +1. [Basics](#basics) + 1. [Machine code is numbers](#what) + 1. [Demonstration](#demo) + 3. [Calling convention](#talk) + 4. [Memory protections](#protections) + 5. [Just-in-Time Compilation](#jit) + 1. [Example: Lightening: Guile's machine code generation + library](#lightening) +2. [Lessons learned](#problems) + 1. [Problem: Large immediates](#large-imm) + 1. [Solution: multiple instruction expansion](#multi-inst) + 2. [Solution: constant insertion](#constants) + 2. [Problem: Unknown addresses and offsets](#addr-off) + 1. [Solution: relocations](#relocs) + 1. [Example: C compilers](#relocs-c) + 2. [Example: Lightening](#relocs-lightening) + 3. [Problem: Long jumps](#jumps) + 1. [Solution: always insert the largest jump possible](#always-largest) + 1. [Optimization: pointer relaxation](#relaxation) + 2. [Example: relaxed global variable access in C + compilers](#relax-example) + 2. [Solution: Veneers](#veneer) + 1. [Example: Lightening's veneer system](#lightening-veneer) + 4. [Problem: Register Access](#reg-access) + 1. [Solution: use the stack](#stack) + 2. [Solution: controlled register access](#controlled-regs) +3. [Final thoughts](#final) + +### Basics {#basics} + +There are many contexts where you may need to generate machine code. If you are +writing a compiler, an assembler, a jit compiler... In the last months I've +been working on Lightening, a machine code generation library that powers +Guile's JIT Compilation, a RISC-V assembler and interpreter and Hex0, which was +introduced in the [previous post](https://ekaitz.elenq.tech/hex0.html), where I +needed to assemble a file by hand. + +All of those cases result in the same thing, even if they have different +conditions: we are generating machine code. + +In this post I'll try to talk about some issues that are generic and apply to +all the cases and others that are more specific to some of the projects I +mention. + +But first we need to clarify some stuff just in case. + +#### Machine code is numbers {#what} + +> Machine code is what people from the electronics world call "code". + +I know you know it, but let's refresh some things about computing we may have +forgotten thanks to all the efforts that [hide the +complexity](https://ekaitz.elenq.tech/hiding-the-complexity.html) of our +everyday business. + +Machine code instructions are basically blocks of bits your processor is +reading and interpreting. Those bit blocks encode all the information the +processor needs: the identifier of the instruction and its arguments. + +The identifier is normally known as *opcode*. The arguments can have many +different meanings, depending on the instruction so we are not getting into +that. The instructions normally alter the values of registers, so they need to +have identifiers for the source and destination registers, or literal values +that are introduced literally inside of the instruction (they are called +*immediates*). + +Let's put a simple RISC-V example here. Consider this assembly instruction: + + ::asm + addi a0, zero, 56 + +This thing you interpret as some assembly instruction that adds `56` to the +`zero` register and stores the result in the `a0` register, has to be encoded +in a way that the machine is able to understand. Better said, it is encoded in +a way that **you** can understand! The real instruction is a bunch of bits that +represent the same thing. + +RISC-V base ISA has a various instruction formats which depend on the goal of +the instruction. This one is from the `I` format, because it includes an +*immediate*. Read it and compare with the following: + +- First the *opcode*, `addi` for you, has a binary counterpart: `0010011`. 7 + bits for this instruction format. +- Then the destination register, `a0`, has an binary representation: `01010`. + There are 32 registers in RISC-V so each of them are represented by a 5 bit + value. +- There's some extra space for an opcode-like field called `funct3`: `000` +- Then there the source register, `zero`, which is: `00000`. Again 5 bits. +- And the *immediate* you are adding, `56`, which is just the binary + representation of `56`: `000000111000`. It's 12 bits wide for this + instruction format. + +Putting all together: + + ::asm + 000000111000 | 00000 | 000 | 01010 | 0010011 + +So this forms the following binary value: + + ::asm + 00000011100000000000010100010011 + +Or in hex: + + ::asm + 0x3800513 + +> Just for if you didn't realize, you just assembled an instruction by hand. + +That instruction we just created is going to be processed by the machine, +reading each of the fields and activating its circuits as it needs according to +the voltage levels those values represent. + +In this case, it's going to activate the ALU to add the numbers and all +that kind of things, but in other cases it may just change the value of the +program counter or whatever. All this is executed by the circuitry of the +device, right after it loads the instruction. + +That's for the machine, but for us, from the perspective of a programmer, +instructions are just numbers, as we just saw. + + +##### Demonstration {#demo} + +I purposely used *machine* to refer to the device that runs our instructions, +but we have to be more specific about it now. + +I'm going to talk specifically about modern (and common) microprocessors, +because other devices may have peculiarities that can sidetrack us too +hard[^harvard]. + +[^harvard]: One of those peculiarities is the [Harvard + Architecture](https://en.wikipedia.org/wiki/Harvard_architecture) that is not + going to let us make the fantastic trick I'm going to show you now. Harvard + Architecture is popular on microcontrollers. + +In our modern and common microprocessor, [instructions are located in the +memory](https://en.wikipedia.org/wiki/Von_Neumann_architecture). But that's +nothing we didn't know! If we run a binary it's loaded in the memory and +executed from there. We all know that! + +But you can be surprised to certain level if we stretch that a little bit. + +Well, we know from the previous part that instructions are just numbers, and we +know that they loaded from the memory so let's do some C black magic and see +what happens: + + ::clike + #include<stdint.h> + #include<stdio.h> + + typedef int f0(void); + + int main(int argc, char* argv[]){ + uint32_t instructions[2]; + + instructions[0] = 0x03800513; // addi a0, zero, 56 + instructions[1] = 0x00008067; // jalr zero, ra, 0 + + f0 *load_56 = (f0*) instructions; // Reinterpret the array address + // as a function + int a = load_56(); + printf("%d\n", a); + } + +In that example we build an array of two values. The first one corresponds to +the instruction we encoded by had before and the second corresponds to `jalr +zero, ra, 0`, the return instruction, which you can encode yourself. + +After that we convert the address of the array to a function that returns and +integer and... Boom! We execute the array of numbers. + +The code only works on RISC-V, but don't worry, I can tell you that it prints +`56`. + +So it was true that the machine can execute stuff from the memory, but what we +may not know is that for the machine there's no actual distinction between +instructions and data[^lisp]. We just executed an array of numbers! + +[^lisp]: LISPers are always right. + +The machine doesn't care. If it looks like instructions it executes. + +You can try to put random values in the array and try to execute them, too. +An `Illegal instruction` error is going to happen, probably. If you are lucky +you may execute something by accident, who knows. + +But how did this thing work that well? Why did it return the value correctly +and all that? + +#### Calling convention {#talk} + +The code worked because we are following the RISC-V ABI, the same that C is +following in the example. It tells us how do we need to pass arguments to +functions and return and all that. This part of the ABI that defines how to +call and return from functions is called *calling convention*. + +I'm not going to extend a lot talking about this, but I will just say that +RISC-V has some registers to pass arguments on: `a0`, `a1`...`a7`. And those +registers are also used for return values. + +In the example we are not taking any argument so we don't need to read from any +but we return one value, just writing it in `a0`. + +With what you know, you can now create a function that gets an input argument +and adds an *immediate* to it. Why don't you try? + +On the other hand. RISC-V ABI defines there's a register called `ra` that +contains the Return Address, so we need to jump to it if we want to finish our +function execution. + +There are many things more you can read about, but this is enough to begin. + + +#### Memory protections {#protections} + +The C example where we executed an array is correct, it runs and all that, but +the reality is that memory has different kinds of permissions for each part of +it. + +Code in memory is normally read only and executable, and data can be read-only +or not, depending on the goal it has (constant or variable). + +If you think about the example above, once the array is set, we can overwrite +it later, or even write it from the instructions we inserted on it. This could +led to security issues or unexpected results. That's why code is normally read +only and any attempt to write it will raise an exception to the kernel. + +There are several ways to identify a memory block as code: the RISC-V assembly +(and many others) uses the `.text` directive which automatically sets the block +as a read-only block that can be executed; the `mmap` Linux system call needs +some flags to indicate the protections on the memory block (`PROT_EXEC`, +`PROT_READ`, `PROT_WRITE`...); etc. + + +#### Just-in-Time Compilation {#jit} + +Just-in-time (JIT) Compilation is a way to execute programs that involve a +compilation step at runtime. Typically this happens on interpreted programs, +where the interpreter consumes part of the execution time. An interpreter with +a JIT Compilation feature is able to compile parts of the code it's going to +run to machine code and speed up the execution of those parts. + +Clever interpreters are able to predict if the time they need to compile and +execute the JIT Compiled parts is less than the time they need to interpret +them, so they can decide if it's worth the effort. + +Normally, the JIT Compilation is more effective in pieces of code that are +executed many times because the code only needs to be compiled once and the +speed increase is going to be obtained in every execution. But many algorithms +may be defined, and parts of the code may be recompiled looking for different +optimizations while the interpreter collects data about the performance of the +program. + +Explained like this it looks like it's a complex thing to do (and it is) but +with the previously mentioned points we can imagine a simple JIT machine code +generation library. We "just" need to: + +- Know what code to generate (choose a function to compile, this step may need + some code analysis). +- Reserve some space (`malloc`, `mmap`...) +- Fill the space with numbers (the machine code instructions resulting from the + compilation of the function). +- Next time the program wants to call the function we compiled, call the + numbers instead (as we did [in the demonstration](#demo)). + +##### Example: Lightening, Guile's machine code generation library {#lightening} + +The just-in-time compilation process in Guile is simple, but effective[^guile]. +Guile uses a library called Lightening for it. Lightening is a template-like +library that defines a virtual instruction set. That instruction set is +translated by the library to the instruction set of the actual machine. + +Implementing support for another architecture is as simple as implementing all +the translation code for the new architecture. That's [what I've been doing +these days](https://ekaitz.elenq.tech/lightening.html). + +Guile's JIT compiler only needs to call the instructions of the library and +they will generate actual machine code by themselves, packaged in a function +the interpreter will be able to call later. + +Lightening is simple because it doesn't need to compile from source code, or +make code analysis to find which part of the code does it need to compile. It +just exposes an API that looks like an instruction set and that's the thing +that we translate to the machine code. + +The JIT is going to call the API of Lightening, creating more complex +operations by combining Lightening's instructions and Lightening is going to +convert those operations to their machine code by a simple translation, filling +the array of numbers and returning its address as a function pointer we can +call later. + +Of course, it is much more complex than that because it needs to solve many +other problems we are talking about later but that's the idea. And the idea +doesn't sound too difficult, once you have in mind what we talked about +previously. + +[^guile]: You can read more about [how it works here][guile-jit]. + +[guile-jit]: https://www.gnu.org/software/guile/manual/html_node/Just_002dIn_002dTime-Native-Code.html + + +### Lessons learned {#problems} + +There are many problems that a machine code generation library like that can +encounter, but they are not exclusive for those libraries. These kind of +problems can also appear in compilers, assemblers and many other things. + +The lessons I learned come as problems I encountered during these days of +digging and implementing and some possible solutions or thoughts about them. + +#### Problem: Large immediates {#large-imm} + +Large *immediates* are one of the most obvious but boring issues in this world, +and they apply to many cases. + +In the [example above](#what) we encoded an `addi` instruction that added `56`, +an *immediate*, to a register, and we said the *immediate* had a 12 bit space +in the instruction. Registers in RISC-V are 32 bit (in RV32) or 64 bit (in +RV64) wide, so we can work with larger values, but we are limited to use `12` +bit immediates in `addi` and all the other `I`-type instructions. + +Why is that? Well, RISC-V instructions are 32 bit and they need to be able to +pack much more information than the *immediate* they use, so the *immediates* +can't be as large as we want. The fixed instruction size is a design decision +that keeps the processor simple, but other processors have other design +decisions[^x86] around this. + +[^x86]: In x86 all the instructions don't have the same length and some can + encode larger *immediates*. + +##### Solution: multiple instruction expansion {#multi-inst} + +There are several solutions for this, but the most obvious one is to use more +than one instruction to operate in an immediate. + +If we want to load a 64 bit value, we can add, rotate left, add, rotate left, +add... Until we fill a whole register with the value we were looking for. + +This means a simple addition can be expanded to many instructions. In some +cases they are going to be just a few, but as the *immediates* get big we may +need more than eight instructions, very well encoded, to write the immediate to +a register and be able to operate with it. + +##### Solution: constant insertion {#constants} + +This is not a solution we can take everywhere, but we can take in the context +we are right now (code is stored in the memory and all that, remember). +Consider this RV64 code: + + ::clike + auipc t0, 0 // x[t0] = PC + 0 + ld t0, 12(t0) // x[t0] = mem[ x[t0] + 12 ] + jal zero, 3 // PC = PC + 3 + 0xAAAAAAAAAAAAAAAA // This is a 64 bit literal + addi t0, t0, 1 // x[t0] = x[t0] + 1 + // What's the value of t0 here? + +The code has some comments in the right that I'm going to use through the whole +post, so get used to them. The `x` means register access (base registers are +called X registers in RISC-V), and `mem` is memory, `PC` (program counter) is +written in uppercase and not as if it was a register because it's not +accessible by the programmer so we need to treat it as a global variable we can +only set using jumps or get using `auipc`. + +RISC-V instructions are 32 bit long (4 bytes), so you can get what the offset +in the `ld` instruction does, right? + +Basically we are loading a doubleword (`ld`) at the position of the +`0xAAAAAAAAAAAAAAAA` in the `t0` register and adding `1` to it. So the answer +to the question is `0xAAAAAAAAAAAAAAAB`. + +But can you see the trick we are using? + +The `jal` instruction is jumping over the constant so we can't execute it by +accident (which will cause an `Illegal Instruction` error), and using the `ld` +instruction we are able to load a big constant to a register. A constant which +**is mixed with the code**, as any immediate would be, but without being +associated with any instruction. + +If we know the code we are generating is a function, we can always wait until +the return instruction and insert all the constants after it, so they are +perfectly separated and we don't insert jumps to avoid executing the constants +by accident. For that case, we need to change the values of the `auipc` and the +`ld` accordingly, making them point to the correct address, which has some +associated issues we need to talk about now. + + +--- + +<div style=" + text-align: center; + font-size: smaller; + padding-left: 3em; + padding-right: 3em; + padding-top: 1em; + padding-bottom: 1em; + border-top: 1px solid var(--border-color); + border-bottom: 1px solid var(--border-color)"> +Keep in mind you can hire <a href="https://elenq.tech">ElenQ +Technology</a> if you like this kind of material. <br/> +We teach with this mixture of passion and awkward charisma. We also code and +research. +</div> + +--- + + +#### Problem: Unknown addresses and offsets {#addr-off} + +Addresses and offsets are a pain in the ass because you may don't know them +when you expect to. + +Let's consider an unconditional jump like the one of the previous example. The +number we introduce is the amount of instructions to jump from the program +counter: an offset. The *immediate* offset can be positive, for forward jumps, +or negative, for backward jumps. + + ::clike + jal zero, 3 // PC = PC + 3 + +Generating this jump supposes that you know where you need to jump: you want to +jump 3 instructions to *the future*. + +But imagine you are assembling a file, a real assembly file that is not an +oversimplification of the assembly, like what we did in the previous example. A +real assembly file with *labels*: + + ::clike + add a0, a0, t1 // I don't care about this instruction + j end // Unconditional jump to `end` + + // Some code here + + end: // Label `end` + ret // return + +If you are assembling this file line by line, you can actually assemble the +`add` in the first line, because you know *everything* from it, but you are +unable to emit the `j end` because you don't know where `end` is *yet*. + +If this assembly is written in a file you can always preprocess the whole file, +get the labels, associate them with their addresses and then assemble the whole +thing, but you are not always in this situation. + +Lightening, for instance, generates the code as you call the API, so it doesn't +know where does your jump point to until you call the API for the label later. + +Compilers may encounter this issue too, when they are using separate +compilation and linking steps. You must be able to compile one source file by +your own but you may not know where do global variables appear, because they +might be in a different file, and you only know those at link time. + +##### Solution: relocations {#relocs} + +There's one simple way to solve it: introduce a fake offset or address and +patch it later, when we know the position of the symbol. That's what +relocations do. + +###### Example: C compilers {#relocs-c} + +The relocations are a mechanism to pass information between the compiler and +the linker, you can actually see them in the object files generated by your +compiler. Make a simple file with a global variable and compile it. Something +like this: + + ::clike + int global_symbol; + int main(int argc, char* argv[]){ + return global_symbol !=0; + } + +If you compile it with `gcc -c`, you can inspect relocations in the result with +`objdump`, using the `-r` flag alongside with `-d` for disassemble. In RISC-V +you'll find things like `R_RISCV_HI20` or `R_RISCV_LO12` where the relocations +are located. They are ways to encode *immediates* in `U`-type instructions and +`I`-type instructions respectively. In my case I get something like this (it's +not the full result): + + ::clike + 6: 00000797 auipc a5,0x0 + 6: R_RISCV_PCREL_HI20 global_symbol + 6: R_RISCV_RELAX *ABS* + a: 00078793 addi a5,a5,0x0 + a: R_RISCV_PCREL_LO12_I .L0 + a: R_RISCV_RELAX *ABS* + e: 639c ld a5,0(a5) + +There are two types of relocations but we are going to talk about the +`R_RISCV_RELAX` later. You see my relocations have `PCREL` in the middle, but +just to mention they are relative to the program counter. + +If you just inspect the binary with the `-d` you won't see the relocations and +the result will look like nonsense code[^nonsense-code]: + + ::clike + 6: 00000797 auipc a5,0x0 // x[a5] = PC + 0 + a: 00078793 addi a5,a5,0x0 // x[a5] = x[a5] + 0 + e: 639c ld a5,0(a5) // x[a5] = mem[ x[a5] + 0 ] + +This adds `0` to program counter and stores the result in `a5`, then adds `0` +to `a5`, and loads a doubleword to `a5` from the address at `a5`. But the +address at `a5` at the moment of the load is nothing but the program counter at +the `auipc` instruction. Weird. + +The relocation is going to point to the `auipc` and the `addi`, and tell the +linker it has to replace the zeros by other value. Which one? The address of +the global variable. If we replace the zeros by a combination that is able to +load the address of the global variable the code will work. That's what the +relocation does here. + +So, as we don't know where to point, we insert anything (zeros) and we fix the +instructions when we know where do they need to point to. + +[^nonsense-code]: `addi a5,a5, 0x0` is adding 0 to `a5` and storing it in `a5` + so it's just moving it. RISC-V has a pseudoinstruction for that: `mv a5,a5`, + which is expanded to the `addi`. `objdump` is going to write `mv` in its + output, because it tries to be clever, but that is not the goal of the + instruction we have. I changed it to the actual instruction so we can + understand this better. + +###### Example: Lightening {#relocs-lightening} + +Same approach is followed in Lightening, and you can follow in your assembler, +library or anything that has a similar problem. Let's consider some code using +Lightening (obtained from `tests/beqr.c`, comments on my own): + + ::clike + // Make a function that loads two arguments + jit_load_args_2(j, jit_operand_gpr (JIT_OPERAND_ABI_WORD, JIT_R0), + jit_operand_gpr (JIT_OPERAND_ABI_WORD, JIT_R1)); + + jit_reloc_t r = jit_beqr(j, JIT_R0, JIT_R1); // branch if equal registers + jit_leave_jit_abi(j, 0, 0, align); // end ABI context + jit_reti(j, 0); // return 0 + jit_patch_here(j, r); // make the branch jump here + jit_leave_jit_abi(j, 0, 0, align); // end ABI context + jit_reti(j, 1); // return 1 + + // Obtain the function we created + jit_word_t (*f)(jit_word_t, jit_word_t) = jit_end(j, NULL); + + // Test if it works + ASSERT(f(0, 0) == 1); // 0 == 0 so it jumps -> returns 1 + ASSERT(f(0, 1) == 0); // 0 != 1 so it doesn't jump -> returns 0 + +In this example we see how we generate machine code statement by statement, so +there's no way to know where does the `beqr` need to jump until we generated +all the code for it. + +You see the `beqr` function doesn't receive the target address or offset as an +argument, but it returns a `jit_reloc_t`, which other functions like `reti` +don't return. + +That `jit_reloc_t` is what we are patching later with the `jit_patch_here` to +tell where does it need to jump. The `jit_patch_here` function is going to +correct the bits we set to zero because we didn't know the target at that +moment. + +There are different kinds of relocations, as it happened in the previous +example with the compilers, because different instruction formats need to be +patched in different ways. In the case of Lightening, the relocation has a type +associated with it, so we can check and act accordingly. + + +#### Problem: Long jumps {#jumps} + +As we saw, some jumps encode the target as an *immediate*. This has a couple of +implications that we just described in previously: + +- The jump target could be larger than the space we have for the immediate. +- Sometimes we can't know the target until we reach the position where the jump + points to. + +Both issues can be combined together in a killer combo. Consider this code: + + ::clike + j label // jump to label + + // A lot of instructions here + + label: + // this is the target of the jump + +In RISC-V the `j` pseudoinstruction is resolved to `jal`, that has a `21` bit +(signed) space for the jump target. If we had a hella lot of instructions +between the jump and the target we may need more bits for the jump than the +space we actually have. + +Again, in the case were we can preprocess everything there's no problem, but if +we are assembling the instructions as they come we are going to have issues. +We realize we can't jump that far too late, because we already inserted +a 21 bit jump and too many instructions when we reach the label. Patching the +jump is not enough, because we didn't leave enough space to insert the offset +we need. + +##### Solution: always insert the largest jump possible {#always-largest} + +There's an obvious solution: always insert the largest possible jump and patch +the whole jump later. + +In RISC-V `jalr` jumps to the absolute address that is stored on a register +with an optional 12 bit (signed) offset. Combined with the `auipc` (add upper +immediate to program counter) it lets us make 32 bit relative jumps in just 2 +instructions. Let's explain that in code just in case: + + ::clike + auipc t0, offset_hi // x[t0] = PC + (offset_hi<<12) + jalr zero, offset_lo(t0) // PC = x[t0] + offset_lo + +If we consider `offset` as a value we know, we can split it in two blocks: the +highest 20 bits as `offset_hi` and the lowest 12 bits as `offset_low` and use +them to jump to any address in the 32 range from the current position, using +just 2 instructions. + +In 32 bit machines, this jump is the largest jump possible, because the machine +can only address 32 bits, so we will be sure that any relative (or absolute, +using `lui` instead of `auipc`) jump we want to make can fit in place. The only +thing we have to take in account is to patch both instructions when we find the +targets, not only one. + +###### Optimization: pointer relaxation {#relaxation} + +But using the largest possible jumps can led to inefficiencies because we use +two instructions for jumps that can potentially fit in just one. + +We can use something we saw before for that: relocations. More specifically, +in the case of the GCC toolchain, we can use the `R_RISCV_RELAX` that appeared +before. + +The relaxation relocation is going to tell the next step, which can be the +linker or anything else depending on the context we are working on, that the +pointer can be relaxed. In the case of the `auipc` + `jalr`, possibly by +replacing both instructions by a 21 bit jump like `jal`. + +So we start with the longest jump possible, but when we actually know the +target of the jump, we can reduce it to something smaller that needs fewer +instructions. + +###### Example: relaxed global variable access in C compilers {#relax-example} + +Global variables, as we saw before, are some of those points where compilers +need to use relocations and let the linker clean the result. + +Global variables don't necessarily involve jumps but they do involve pointers +for the loads and stores needed to operate with them. In the final executables, +global variables are part of the `.data` segment, because they are known at +compilation time, so we can exploit that fact a little and relax our weird +`auipc` + *load/store* combos. + +RISC-V has many registers, so we can use them for things that may not be the +norm in other platforms where registers are scarce. In this case, we can +exploit the `gp` (global pointer) register on RISC-V to improve the access to +the global variables. We can cache the address of the `.data` segment of the +program in the `gp` register so, as we know most of the global variables are +going to be near (12 bit offset) to the beginning of the `.data` segment, we +are probably going to be able to remove some of the `auipc`s we inserted +before. + +So a simple load of a global 64bit variable to a register: + + ::clike + auipc t0, offset_to_global_hi // x[t0] = PC + offset_to_global_hi << 12 + ld t0, offset_to_global_lo(t0) // x[t0] = mem[ x[t0] + offset_to_global_lo ] + +Is optimized to this: + + ::clike + ld t0, offset_from_data(gp) // x[t0] = mem[ x[gp] + offset_from_data ] + +Of course, the offsets have to be calculated and all that, but it's not that +difficult. + + +##### Solution: Veneers {#veneer} + +There are other solutions that don't involve messing around with the code we +generated earlier in an aggressive way like removing instructions, which can be +pretty bad because you have to shift the array of instructions you generated to +clean the gaps the pointer relaxation leaves. + +Veneers are non destructive, and they involve no instruction reorganization, so +they are interesting for those cases where you need to generate the code as you +go. + +Let's explain them with an example: + + ::clike + beq a0, a1, branch // Jump to `branch` if x[a0] == x[a1] + + // Instructions... + + branch: + // Branch target + +As we saw previously, if we insert too many instructions in between the jump +and the target we screw it. What we didn't mention is that as we go assembling +instructions one by one we can keep a track of the amount of instructions we +are inserting. + +Having that in mind, we can take decisions in time, right before it's too late. +We can combine that knowledge with the [constant insertion](#constants) method +introduced before to insert full-range jumps if needed, right before we exhaust +the possible offset of the original instruction. + +Of course, we need to patch the original instruction to jump to the code we are +just going to insert, and we need to add some protections around the veneer to +make it only accessible to the original jump. + + ::clike + beq a0, a1, veneer // Jump to `veneer` if x[a0] == x[a1] + + // Many instructions, but not too many! + + // Here we realize we are running out of offset range so we insert a helper + // block that lets us jump further. + j avoid // Jump to `avoid` so the normal execution flow + // doesn't fall in the veneer + veneer: + auipc t0,0 // x[t0] = PC + 0 + ld t0,12(t0) // x[t0] = mem[ x[t0] + 12 ] + jalr zero,0(t0) // PC = x[t0] + ADDRESS(branch) // Literal address of `branch` label + avoid: + + // As many instructions as we want + + branch: + // Branch target + +As it happened with constant insertion, there are positions where the veneer +insertion can be optimized a little, like right after a return or an +unconditional jump, so we don't need the protection (`j avoid` in the example). + +The bad thing about veneers is they insert a bunch of instructions in the cases +that are not in range and the jumps are done in two steps, that has a negative +effect on the performance because they drop the pre-processed instructions [in +the pipeline](https://en.wikipedia.org/wiki/Instruction_pipelining). + +Of course, the veneers themselves have to be patched too, because we won't know +the target (`branch` in the example) until we reach it. But, in the case of the +veneer we can be 100% sure that we are going to be able to point to the target. + +###### Example: Lightening's constant pools {#lightening-veneer} + +Lightening uses veneers for the jumps[^veneer-if-needed], but they are part of +Lightening's constant pool mechanism. Constant pools work the same for the +constant insertion than for veneers, because veneers are basically constants. +Remember, code is numbers! + +[^veneer-if-needed]: Only in the architectures that need them. `x86` does not + need constant pools or veneers because the ISA is complex enough to handle + the problematic cases adding levels of complexity ISAs like RISC-V or ARM + didn't want to deal with. RISC vs CISC, y'know... + +Basically anything that might be inserted as a constant, which can be a veneer +or just a number or whatever, is queued to the constant pool. The library is +going to emit instructions and check on each instruction if it needs to emit +any of the constants of the pool. + +The constant pool and each of the entries on the pool have associated +information that tells the emitter if they need to be emitted now or if they +can wait for later so the emitter can decide to insert them. + +The literal pool entries have, of course, an associated relocation that +contains information of the original jump or load instructions we may need to +patch, as we already saw. So, in the case of a veneer emission, we need to +patch the original jump to the veneer and remember the veneer needs to be +patched later, when we find its target. + +The mechanism is not complex, but it's not simple neither. There are several +kinds of relocations, depending on what we want to do with them, different kind +of patches we need to do, address calculations and all those things that +require a level of attention to the detail I'm not prepared to talk about. + +#### Problem: Register access {#reg-access} + +You may have seen a problematic point in some of the solutions we worked with: +we are using registers. + +It's not a problem by itself, but using registers might be really problematic +if we are inserting code between the instructions someone else wrote because we +can't control the register use the original program did and we might be +changing the values inside of the registers in the magic tricks we sneakily +inserted. + +Imagine we use, say, `t0` register in our veneer but the original program uses +that register for something else. That's a problem. We are messing with the +value in the register and potentially (surely) breaking the program. + +##### Solution: use the stack {#stack} + +The most obvious solution you can think of is to use the stack. We can surround +our veneers or code insertions with some protection code that saves the values +of the registers on the stack and restores them when we finished. + +It's a simple solution in your mind, but if you need to deal with the jumps it +can get messy. You may need to restore the register far away in the code and +keeping track of everything. It can be complicated. + +On the other hand, memory access is slow and boring and we don like that kind +of things in our lives. We need more dynamite. + +##### Solution: controlled register access {#controlled-regs} + +The other solution we can provide is to keep control of the registers that are +being accessed and use others for our intervention. + +A simple way to do this is to provide functions to get and release temporary +registers, instead of letting the programmers do whatever they want. This makes +sure that all the register access is controlled and we are not changing the +values of any register in use. + +The main problem we can have comes when the programmer needs all the register +for their things and then we can't really use any for our magic tricks. But we +can always keep at least one register for us and only for us (throwing an error +to the programmer when they use it) or even combine the use of the stack with +this solution. + +If we are directly working with assembly code, where we can't force the +programmer to use the interface we want, we can choose the solutions that don't +involve register access so we don't need to analyze the code to deduce if the +programmer is using the registers or not. Avoiding the problem is sometimes the +best solution. + +In the case of libraries like Lightening register access control is a must +because Lightening can't control how its (virtual-) instructions are translated +to machine code instructions: each machine has its own peculiarities and +details. In many cases they need to make use of temporary registers and, as the +instructions are built incrementally, preventing instructions from peeing on +each other is important. + +--- + +<div style=" + text-align: center; + font-size: smaller; + padding-left: 3em; + padding-right: 3em; + padding-top: 1em; + padding-bottom: 1em; + border-top: 1px solid var(--border-color); + border-bottom: 1px solid var(--border-color)"> +Please, consider supporting me on <a href="https://buymeacoffee.com/ekaitz">Buy +Me a Coffee</a> or on <a href="https://liberapay.com/ekaitz">Liberapay</a> to +encourage my free software work. +</div> + +--- + +### Final thoughts {#final} + +I know these are just a few things, but they are enough to let you make you +first program that involves machine code generation to certain level. + +I'm not a computer scientist but a telecommunication engineer[^engineer], so I +may put the focus on things that are obvious for the average reader of these +kind of posts, but at the same time I may be flying over things that I +consider basic due to my studies but the average reader doesn't. In any case, +feel free to [contact me](https://ekaitz.elenq.tech/pages/about.html) if you +have questions or corrections. + +Some of the tricks and lessons I included here are more important than others, +but the most important thing is to start thinking in these terms. Try to +understand the problems you face when you have separate compilation, assume +the fact that you can't know the future... The mindset is the most important +point of all this and, once you have it, everything comes easier. + +It's also a lot of fun to realize code is just numbers in memory you can mess +around with. I hope you keep it in your brain forever. + +I hope this post throws some light on this dark hole that machine code +generation is and makes you try to make your own findings on this beautiful +area of compilers, machines and extremely long blog entries. + + +[^engineer]: So, for all that software developers that write blog posts like + "Are we really engineers?" or stuff like that: **I am**, thanks for the + interest. LOL |