Adding a new target/object backend to LLVM JITLink

MotivationFor the last year, I have been contributing to LLVM JITLink. This post aims todoubly serve as a summary of my work and documentation for future contributors looking to add a new target/objectbackend to LLVM JITLink.We will start by establishing some background and definitions of relevant concepts. Then, we will talk about whatthe project actually entailed. Finally, we will go over the execution details of the project.The end goal of the project was to make LLVM JITLink capable of linking a 32-bit ELF object file, with i386specific relocations, into a 32-bit process on the i386 hardware architecture.If the goal of the project already makes sense to you and you are looking to get started with adding a newtarget/object backend to LLVM JITLink yourself, you can skip to the “Recap and conveniences”section.BackgroundLinkingOur code often relies on external dependencies. For example, even a simple hello-world program written in C dependson the C stdlib for the printf function. These external dependencies are expressed as symbolic references, which Iwill henceforth refer to as just symbols. Symbols are names of data or functions that have unknown addresses andare resolved or fixed up during the linking process.In chronological order -The compiler converts source code to machine code.The assembler converts machine code to object files (ELF, MachO, COFF etc.)The linker links one or more object files (fixing up symbolic references along the way) and produces anexecutable or a shared library (also called shared object or dylib).For the purposes of this discussion we will focus on executables, but the points that will be made hold for sharedobjects as well.JIT linkingUnlike static linking, JIT (Just-in-time) linking is performed at runtime. While a static linker producesexecutables that are stored on disk, a JIT linker produces an in-memory image of the executable – essentiallyready to execute bytes in memory. JIT linking a C program may feel very much like running a shell script. Underthe hood though, the C program is linked into the memory of the invoking process, also commonly referredto as the executor process. The JIT linker patches up the executor process’ memory to account for the addresses ofsymbols at runtime, and executes necessary initializers.If you are familiar with dynamic loading then JIT linking may sound familiar, and the two have a lot in common,however they are not the same. JIT linking operates on relocatable objects (vs shared objects/dylibs for dynamicloading), and performs both the static linker’s and the dynamic loader’s jobs. Doing so allows the JITlinker to dead-strip redundant symbols, which dynamic loading cannot do, and this allows JIT linking to supportfiner grained compilation of languages that tend to produce a lot of redundant symbol definitions(e.g. C++).Need for JIT linkingJIT linking is primarily useful in the context of pre-compiled languages, such as C, C++, Rust etc. Why? At run time,these languages have no way1 to bring new symbol definitions into a running process’ memory and resolvereferences to them. Although dynamic loading partially solves this issue, it has its drawbacks (discussed above)and lags far behind the static linking experience.With JIT linking, at run time, symbolic references can be resolved to existing symbols (from the newly JIT’d code), orto newly JIT’d symbols (from the pre-compiled code). The below toy example shows what this looks like in code.// Let's assume we have the following, rather contrived,// C++ program that wants to add 2 numbers, but wants to use// an `add` function from a relocatable object file supplied by// the user.//// Let's also assume that the add function in the user-supplied// relocatable object will reference a symbol named `MAGIC` in its// definition.const int MAGIC = 42;int main(int argc, char* argv[]) { int a = 1; int b = 2; // Read the path of the user supplied relocatable object. string userSuppliedObjectPath = ...; // Initialize your JIT class that uses JIT linking under the hood. JIT J; // Add the relocatable object to your JIT. J.addObject(userSuppliedObjectPath); // Lookup the `add` function in the newly added JIT object. // Once all symbolic references within the user supplied object // are resolved, the content is fixed up and emitted to memory. // And we can then get a pointer to the `add` function. auto *add = (int(*)(int, int))J.lookup("add").getAddress(); // At this point the symbolic reference to `MAGIC` in add's // definition must have been resolved to the memory address // of the constant `MAGIC` that we defined in this program. // Run the add function found in the JIT module. int result = add(a, b);}That said, JIT linking by itself is not something that is very useful for an end user. JIT linking is an enablerfor certain use-cases with pre-compiled languages (some use-cases exist for JIT-compiled languages as well2).JIT compilers (think of something like the JIT compilation component of the Java Hotspot VM, but for astatically compiled language)Debugger expression evaluators (such as the LLDB expression evaluator)REPLs (such as Cling and the currently experimental3 Clang-REPL)Standalone scripts (such as the Swift scripts, where the JIT linking isused to add an immediate mode tothe compiler, which runs your code in-place via a JIT, rather than compiling it)Scriptable extensions (think about running JIT’d code in the context of some existing app, allowing the appto be extended by JIT’d code rather than precompiled plugins)While the above use cases may seem different, they are really the same — JIT linking enables linking code intoexisting processes (that may or may not already contain state/context), in an ABI-compatible way.LLVM JITLinkLLVM JITLink is a JIT linking implementation, in the form of a low-level library within the LLVM infrastructure.It powers LLVM’s ORC JIT APIs, which is what end-users would usually use forbuilding runtime linking environments. It provides primitives for:Re-using existing compilers to generate relocatable objects at runtime.Allocating memory within a target executor process.Linking code into a target executor process in an ABI-compatible way.In simple words, a program Y, running in a process X, can hand JITLink a relocatable object file and JITLink willlink the object file’s code into X’s memory and run it under X’s existing context (globals, functions etc.), as ifit were part of a dynamic library loaded into process X4.The projectHaving set up all that background, let’s understand the main task and the end goal of the project.The task - Adding the i386(target)/ELF(object)backend to JITLinkWhat is a target?Target here, refers to a hardware architecture. i386 is a 32 bit x86 architecture.What is an object?Object here, refers to an object file format. ELFis the object format commonly used on Linux systems.Why do different target/object combinations matter and need additional work?Different target/object combinations matter, because each combination may use distinct methods for connectingsymbolic references to symbol definitions. These methods are commonly referred to asrelocations.The end goalThe end goal of the project was to make LLVM JITLink capable of linking a 32-bit ELF object file, with i386 specificrelocations, into a 32-bit process on the i386 hardware architecture.ExecutionUnderstanding high level constructsLinkGraphThe LLVM JITLink documentation has an excellent description of LinkGraph.I recommend reading it after the below, high-level description of LinkGraph.LinkGraph is an internal representation of an object file within LLVM JITLink. While object formats may havedifferent schemas and terminology for similar concepts, they all aim to represent machine code that can be relocatedin virtual memory. The purpose of a LinkGraph is to provide a generic representation of these concepts and nuancesacross different object file formats.To draw conceptual analogies between the LinkGraph and an object format, let’s use ELF as an example. An ELF objectcontains:Sections - Any chunk of bytes that must be moved into memory as a unit.Symbols - A named chunk of bytes that could represent either data or executable instructions. Symbols occur aschildren of sections.Relocations - A description of how to fix up bytes within a section once the address of the relocation’starget symbol is resolved.A LinkGraph is capable of representing all of the above concepts. It first defines some building blocks.Addressable - Anything that can be assigned an address in the executor process’ virtual address space.Block - A chunk of bytes that is addressable and occurs as part of a section.On top of these building blocks, it defines the higher level object format concepts.Symbol - Equivalent of a symbol in the ELF format. Represented using an offset from the base (address) of aBlock and a size in bytes.Section - Equivalent of a section in the ELF format. Represented using a collection of symbols and blocks.Edge - Equivalent of a relocation in the ELF format. Represented using an offset from the start of thecontaining block (indicating the storage location that needs to be fixed up), a pointer to the target whose address needs to be used for the fix-up and a kind to specify the patching formula.JITLinkContextJITLinkContext represents the target process that you’re linking into, and it provides the JIT linker with theability to ask questions about and take actions within the process. This includes the ability to look up symbols andallocate memory, in the target process, as well as to publish the results of the linking process to the broaderenvironment. Specifically, the JITLinkContext informs others of the addresses it has assigned to symbols and when thosesymbols become available in memory.Understanding the JIT linking algorithmThe LLVM JITLink linking algorithm happens in multiple phases, with each phase consisting of passes over theLinkGraph and a call to the next phase at the end. In each phase the algorithm modifies the LinkGraph as needed, bythe end, producing a ready to execute in-memory image of the relocatable object that we started out with.Something that did not click for me initially, but simplified things significantly once it did, was the fact thatthe LinkGraph was just that, a graph! Re-reading LLVM JITLink’s high-level description of the generic JIT linkingalgorithm with this simple view of the LinkGraph madeit much easier and intuitive to make sense of what was going on in the JIT linking process.The algorithm also provides, implementers and users of JITLink, hooks to tap into the linking process. These hooks canbe used to achieve a number of things, including but not limited to, link-time optimizations, testing, validation etc.The tangiblesFirst, I set up a test loop to validate whether LLVM JITLink is able to link 32-bit i386 ELF objects, containingvalid i386/ELF relocations, into a 32 bit process. The existing llvm-jitlink tool, which is built and put into the binfolder by default when you build the LLVM project, came in handy. llvm-jitlink is a command line wrapper for theJITLink library. It takes relocatable objects as input and links them into the executor process using JITLink.The tricky part here, at least for me, was to get a 32-bit llvm-jitlink ELF executable. By default, Clang producesexecutables for the host architecture because of which I had to understand cross-compilation5 (compiling for atarget different from the host architecture) since I was developing on x86-64 hardware. In order to obtain a 32-bitllvm-jitlink ELF executable, on an x86-64 system, I needed the following -Cross-compiler - A cross-compiler that could generate 32 bit x86 code. Clang generates 32-bit x86 code if thefollowing flags are specified in the build configuration:CMAKE_CXX_FLAGS="-m32" or CMAKE_C_FLAGS="-m32" - instructs Clang to generate 32-bit code instead of thedefault 64-bit code.LLVM_DEFAULT_TARGET_TRIPLE=X86 - instructs Clang to generate machine code for the x86 target by default.Target shared libraries - 32 bit x86 shared libraries, that might be checked against during compilation. In mycase installing libstdc++.i686 and glibc-devel.i686 sufficed since that is all I needed to generate programscontaining all possible i386/ELF relocations.The full command that I used to generate my build configuration was -cmake -DCMAKE_CXX_FLAGS="-m32" -DCMAKE_C_FLAGS="-m32" \ -DCMAKE_CXX_COMPILER=<PATH_PREFIX>/bin/clang++ \-DCMAKE_BUILD_TYPE=Debug \ // It is important that the `llvm-tblgen`executable is for the host architecture-DLLVM_TABLEGEN=<LLVM_BUILD_DIR_FOR_HOST_ARCH>/bin/llvm-tblgen \-DLLVM_DEFAULT_TARGET_TRIPLE=i386-unknown-linux-gnu \// Set of targets that the compiler must be able to generate code for. // Can save compilation time by omitting redundant target backends.-DLLVM_TARGETS_TO_BUILD=X86 \-G "Ninja" ../llvmThe last piece of my test loop was the plumbing in LLVM JITLink, on top of which I could start adding i386/ELFrelocations. I added this plumbing as part of my first commit to LLVM JITLink.At a high level, there were 2 things that I implemented in that commit -ELFLinkGraphBuilder_i386 - contained specialized logic for parsing i386/ELF relocations from an object file.ELFJITLinker_i386 - contained specialized logic for fixing up i386/ELF relocations in the executable imagesupposed to be emitted to memory.Having set up a test loop, I incrementally added support for the following i386/ELF relocations to LLVM JITLink.Quick aside, before we talk about the individual relocations! Let’s recall what relocations are.The compiler generates code which contains symbolic references to actual symbols (everything other than localvariables in a function and functions themselves). The compiler just refers to symbols by the names used by theprogrammer and leaves a set of TODOs for the linker to complete during linking.In ELF objects, these TODOs are found in the relocationsection. They tell the linker where and how a symbolic reference needs to be fixed. The linker then, for the mostpart, follows the compiler’s instructions and resolves all the relocations in the program. The linker can resolverelocations because it has a view of the entire compiled program.R_386_32What - Tells the linker to replace the symbolic reference with the symbol’s absolute memory address.When - Used to reference global and static variables in non position-independent code (PIC). PIC allows codeto be loaded at any address in memory, rather than at a fixed address.Code -// Compile with => clang -m32 -c -o obj.o obj.c// declare a global variable xint x;int main() { // Compiler should generate a R_386_32 relocation here. x += 1; return 0;}00000000 <main>:0: 55 push %ebp1: 89 e5 mov %esp,%ebp3: 50 push %eax4: c7 45 fc 00 00 00 00 movl $0x0,-0x4(%ebp)// Compiler wants to move the value of x into// the eax register but doesn't know the address// of x. So it leaves a TODO for the linker and// temporarily uses 0 as x's address.b: a1 00 00 00 00 mov 0x0,%eax c: R_386_32 x10: 83 c0 01 add $0x1,%eax// Same thing here13: a3 00 00 00 00 mov %eax,0x0 14: R_386_32 x18: 31 c0 xor %eax,%eax1a: 83 c4 04 add $0x4,%esp1d: 5d pop %ebp1e: c3 retR_386_PC32What - Tells the linker to resolve the symbolic reference using the symbol’s relative offset to the currentprogram counter (PC). The linker finds the offset of the referenced symbol, relative to the PC and hard-codesit in the corresponding assembly instruction. At run time, the processor looks at the call instruction’sencoding and knows that the operand to the instruction represents the symbol’s offset to the PC.When - Used to call functions in PIC.Code -// Compile with => clang -m32 -ffunction-sections -c -o obj.o obj.c // declare a global function x void x {} int main() { // Compiler should generate a R_386_PC32 relocation here. x(); return 0; }00000000 <x>:0: 55 push %ebp1: 89 e5 mov %esp,%ebp3: 5d pop %ebp4: c3 ret00000000 <main>:0: 55 push %ebp1: 89 e5 mov %esp,%ebp3: 83 ec 08 sub $0x8,%esp6: c7 45 fc 00 00 00 00 movl $0x0,-0x4(%ebp)// Compiler wants to call function x// but doesn't know its address. So it leaves// a TODO for the linker and temporarily uses garbage// bytes as x's address.//// The linker will replace the garbage bytes 0xfffffffc// with `offset => PC - address of x`.// `e8` here tells the i386 processor that the operand// is a PC relative offset and that the address of x needs// to be computed using `PC + offset`d: e8 fc ff ff ff call e <main+0xe> e: R_386_PC32 x12: 31 c0 xor %eax,%eax14: 83 c4 08 add $0x8,%esp17: 5d pop %ebp18: c3 retAnother short detour to talk about dynamic linking because the remaining relocations are what enable dynamic linking.In static linking, if your program accesses even a single symbol from a given library, then that entire library islinked with your program, which among other issues, increases the size of the generated executable. For instance, let’stalk about that simple C program that just prints hello world again. With static linking, the executable that’sgenerated from your program is going to pull in the entire C standard library, because your program accessed theprintf function.In dynamic linking, referenced libraries are accessed at build time but they are not brought into the linkedexecutable. Instead, the referenced global variables from these libraries are linked at load time (when the program isloaded into memory, to be run) and referenced functions from these libraries are linked at invocation time.There’s pros and cons to both approaches, whose details I will not go into, but will cursorily mention below.With static linking the only thing the user of your executable needs is the executable itself. They won’t runinto issues of missing libraries.With dynamic linking you don’t need to update your executable, if the shared library is updated. This isespecially useful if you are distributing your executable.Dynamic linking is just harder to implement than static linking.If you’re not already familiar with the concepts of GOT and PLT, I also recommend you take yet another quick detourfor some visual explanations!R_386_GOTPC -What - Tells the linker to replace the symbolic reference with the delta between the storage location, wherethe relocation has to be applied (or the fixup location) and the address of the GLOBAL_OFFSET_TABLE (GOT) symbol.When - This relocation isn’t used in isolation. Rather it is an enabler for R_386_GOTOFF, R_386_GOT32 andR_386_PLT32, which need to use the memory address of the GOT.Code -// Compile with => clang -m32 -fPIC -c -o obj.o obj.c// Declare a global staticstatic int a = 42;int main() { // Since we passed the `PIC` flag to Clang to // indicate that we want position independent code // Clang will generate code to access `a` using // the GOT. return a;}00000000 <main>:0: 55 push %ebp1: 89 e5 mov %esp,%ebp3: 50 push %eax// This `call` instr is just telling the processor to// push the next instr's address on the stack and jump to// address 9. But 9 is the address of the next line. That's// weird...4: e8 00 00 00 00 call 9 <main+0x9>// And now that we did jump to 9, all we did was pop // the value that was on the stack and store it in ebx.// Wasn't the value on the stack just 9's address? Even // weirder...9: 58 pop %ebx// Wait a minute. The compiler left a TODO here for the// linker, to find the delta between the fixup location // and the address of the GOT. // // Ok, so if the address of the GOT was let's say 20, // then the linker will try to hardcode the value // `0x20-0xc => 0x14` and add it to the value in eax (0x9),// which will give us `0x14 + 0x9 => 0x1d`. // // Ah, that's not the address of the GOT. Yes, but // `0x1d + 0x3 => 0x20` is. Well, where is the 3 coming from?// The compiler helps us here, a bit. The address in eax isn't// the address of the fixup location it's off by 0x3. So along// with leaving us a TODO, the compiler also leaves us a reminder// to add 0x3 to our delta calculation, in order to arrive at // the correct address of the GOT.a: 81 c0 03 00 00 00 add $0x3,%ebx c: R_386_GOTPC _GLOBAL_OFFSET_TABLE_// Not super important what happens after the R_386_GOTPC// relocation is resolved for now...R_386_GOTOFF -What - Tells the linker to resolve the symbolic reference with the offset between the symbol’s address andthe address of the GOT’s base (computed and stored in a register when the R_386_GOTPC relocation is handled).When - Used by shared libraries and executables to access internal symbols in a position independent way.Code -// Compile with => clang -m32 -fPIC -c -o obj.o obj.c// Declare a global staticstatic int a = 42;int main() { // Since we passed the `PIC` flag to Clang to // indicate that we want position independent code // Clang will generate code to access `a` using // the GOT. return a;}00000000 <main>:0: 55 push %ebp1: 89 e5 mov %esp,%ebp3: 50 push %eax4: e8 00 00 00 00 call 9 <main+0x9>9: 58 pop %eax// We saw above how the R_386_GOTPC relocation gets resolved// and that the ebx register contains the address of the // GOT after the relocation is resolved.a: 81 c0 03 00 00 00 add $0x3,%ebx c: R_386_GOTPC _GLOBAL_OFFSET_TABLE_10: c7 45 fc 00 00 00 00 movl $0x0,-0x4(%ebp)// Compiler wants to access `a`, but since we told it// to generate position-independent code, it generates access// to `a` using the GOT and leaves a TODO for the linker to find// the offset of `a` from the base of the GOT.//// The linker already knows the address of the base of the GOT// at this point - it's stored in ebx. It computes the address of// `a` and fixes up the 4 bytes after `0x8b 0x80`, to store the// offset between `a` and the GOT's base.17: 8b 80 00 00 00 00 mov 0x0(%ebx),%eax 19: R_386_GOTOFF a1d: 83 c4 04 add $0x4,%esp20: 5d pop %ebp21: c3 retR_386_GOT32What - Tells the linker to resolve the symbolic reference with the offset between the address of the GOT’sbase and the symbol’s entry in the GOT (essentially computing an index into the GOT).When - Used by shared libraries and executable to access external data symbols in a position independent way.Code -// Compile with => clang -m32 -fPIC -c -o obj.o obj.c// Declaring that `a` is defined externally.extern int a;int main() { // Since we passed the `PIC` flag to Clang to // indicate that we want position independent code // Clang will generate code to access `a` using // the GOT. return a;}00000000 <main>:0: 55 push %ebp1: 89 e5 mov %esp,%ebp3: 50 push %eax4: e8 00 00 00 00 call 9 <main+0x9