BOLT ORC-based linker

A high-level view on the simple linker used to insert auxiliary/library code into the final binary produced by BOLT. This is built on top of LLVM's ORC infra (the newest iteration on JITting for LLVM).

Several levels of code injection

When BOLT starts processing an input executable, its first task is to raise the binary to a low-level IR with CFG. After this is done, we are ready to change code in this binary. Throughout BOLT's pipeline of code transformations, there are plenty of situations when we need to insert new code or fix existing code.

If operating with small code changes inside a basic block, we typically defer this work to MCPlusBuilder. This is our target-independent interface to create new instructions, but it also contains some functions that may create code spanning multiple basic blocks (for instance, when doing indirect call promotion and unrolling an indirect call into a ladder of comparisons/direct calls). The implementation here usually boils down to programmatically creating new MCInst instructions while setting their opcodes according to the target list (see X86GenInstOpcodes.inc generated by tablegen in an LLVM build).

However, this approach quickly becomes awkward if we want to insert a lot of code, especially if this code is frozen and never changes. In these situations, it is more convenient to have a runtime library with all the code you need to insert. This library defines some symbols and can be linked into the final binary. In this case, all you need to do in a BOLT transformation is to insert a call to your library.

The runtime library

Currently, our runtime library is written in C++ and contains code that helps us instrument a binary.

Limitations

Our library is not written with regular C++ code as it is not linked against any other libraries (this means we cannnot rely on anything defined on libstdc++, glibc, libgcc etc), but is self sufficient. In runtime/CMakeLists.txt, we can see it is built with -ffreestanding, which requires the compiler to avoid using a runtime library by itself.

While this requires us to make our own syscalls, it does simplify our linker a lot, which is very limited and can only do basic function name resolving. However, this is a big improvement in comparison with programmatically generating the code in assembly language using MCInsts.

A few more quirks:

  • No BSS section: don't use uninitialized globals
  • No dependencies on foreign code: self sufficient
  • You should closely watch the generated bolt_rt object files, anything requiring fancy linker features will break. We only support bare bones .text, .data and nothing else.

Read instr.cpp opening comment for more details.

Linking

While RewriteInstance::emitAndLink() will perform an initial link step to resolve all references of the input program, it will not start linking the runtime library right away. The input program lives in its own module that may end up with unresolved references to the runtime library.

RewriteInstance::linkRuntime() has the job of actually reading individual .o files and adding them to the binary. We currently have a single .o file, so after it is read, ORC can finally resolve references from the first module to the newly inserted .o objects.

This sequence of steps is done by calls to addObject() and emitAndFinalize(). The latter will trigger symbol resolution, relying on the symbol resolver provided by us when calling createLegacyLookupResolver().