Down to the Metal

Part VIII · Chapter 23

Compilers and Linkers

Writing assembly by hand is slow, easy to get wrong, and ties a program to one kind of processor. So we write in languages like C, and let a program translate for us. This chapter opens up that translator, the compiler, and its partner, the linker, which joins the pieces into a program you can run.

A compiler reads a program written in a high-level language, one designed for people, and writes out the same program in machine code, designed for the processor. One line of C like total += a[i]; might become three or four instructions, and the compiler picks registers, works out addresses and follows the calling convention of Chapter 22 for us. The same C source can be compiled for x86-64, for RISC-V, or for almost any other processor.

From source to program

When you type gcc -o hello hello.c, the command gcc is really a manager, a driver, that runs four separate programs one after another:

  1. The preprocessor handles the lines starting with #. #include <stdio.h> pastes in the whole file stdio.h, which describes printf and many other functions.
  2. The compiler proper (GCC's is called cc1) turns the C into assembly language.
  3. The assembler (as) turns the assembly into machine code, in an object file ending in .o.
  4. The linker (ld) joins the object files and libraries into one executable program.

Here's the classic first program, with every step's output kept, on the computer this book was written on:

#include <stdio.h>

int main(void) {
    printf("Hello, world!\n");
    return 0;
}
$ gcc -save-temps -o hello hello.c
$ ls -l                                  (sizes in bytes)
hello.c        84     ← 6 lines of C
hello.i     21316     ← after the preprocessor: 819 lines
hello.s       668     ← assembly
hello.o      1504     ← object file: machine code with holes
hello       15960     ← the finished program

Reading the program

A compiler works in stages, much like you'd read a sentence in a foreign language:

Here's a real compiler, a very small one, that does all of that for a single expression. Type your own, using the variables a, b and c, numbers, +, -, * and brackets:

Each stage runs again as you type. Try the presets, then turn on the optimiser and watch the tree and the code shrink.

Real compilers add one important idea. Between the tree and the machine code, they translate the program into an intermediate representation (IR): a simple, made-up assembly language that belongs to no real processor. The optimiser works on the IR, and only at the very end is it turned into x86-64, RISC-V or anything else. That split lets one compiler support many languages and many processors. The LLVM project is built this way: Clang (for C and C++), Rust and Swift all produce LLVM IR, and LLVM turns it into code for dozens of processors.

Making it fast

A compiler that translated each line of C on its own would produce correct but slow code. The optimiser looks at the whole function and rewrites it to do the same job with less work. You choose how hard it tries with a flag: -O0 means "don't optimise" and -O2 means "optimise well". Some common tricks:

Here's a simple function, compiled by the two big free C compilers, GCC and Clang, at different levels. The assembly and the times are real, measured on the computer this book was written on:

Compare the code and the running times. Then look closely at what Clang does with -O1. (The assembly has been reformatted slightly, with comments added.)

Optimising can surprise you. In Chapter 22, our recursive factorial in C, compiled by Clang with -O1, came out with no recursion at all: the compiler turned it into a simple loop. The program must behave exactly as written, but how it gets there is up to the compiler. That's also why you debug with -O0: the code still matches your source line for line.

Linking

Big programs are split into many source files, and each one is compiled on its own into an object file. That saves time, because only the files you change need compiling again. But it leaves a puzzle: when main.c calls a function in square.c, the compiler has no idea where that function will end up. So it leaves a hole in the machine code, and a note, called a relocation, saying what should go there.

Each object file also has a symbol table: a list of the names it defines, and the names it needs from somewhere else. The linker's job is to match every needed name with a definition, decide where everything goes in memory, and then fill in every hole. If a name is needed but never defined, you get the famous "undefined reference" error.

Two real object files, compiled separately. Press the button to link them, then fill in each hole and check the arithmetic.

Most programs also use libraries: collections of ready-made functions, like the C library with printf. A library can be linked in two ways:

Meanwhile, inside a real CPU

The -v flag makes gcc show the programs it runs: cc1 (the compiler), as (the assembler) and collect2, which runs the linker ld. Here's the compiler's output for hello.c, with a few lines of bookkeeping removed. Notice that the compiler quietly replaced printf with puts, a simpler function that does the same job when there's nothing to format, even without optimisation:

.LC0:
        .string "Hello, world!"
main:
        endbr64                          ← marks a valid jump target (Intel CET)
        pushq   %rbp
        movq    %rsp, %rbp
        leaq    .LC0(%rip), %rax
        movq    %rax, %rdi               ← first argument: the text
        call    puts@PLT
        movl    $0, %eax                 ← return 0
        popq    %rbp
        ret

That's GCC's default AT&T syntax from Chapter 21. The demo's two files, as C:

/* main.c */                                 /* square.c */
#include <stdio.h>                         int calls = 0;

int square(int x);  /* somewhere else */    int square(int x) {
extern int calls;   /* this too */             calls++;
                                           return x * x;
int main(void) {                           }
    printf("%d\n", square(7));
    printf("calls: %d\n", calls);
    return 0;
}

The nm tool lists an object file's symbol table: T for code defined here, B for a variable defined here, and U for undefined, needed from elsewhere. (Ubuntu's compiler swaps printf for __printf_chk, a version that checks for some mistakes as it runs.)

$ nm main.o                     $ nm square.o
                 U calls        0000000000000000 B calls
0000000000000000 T main         0000000000000000 T square
                 U __printf_chk
                 U square

objdump -dr shows the holes and their relocation notes. The -0x4 accounts for the 4 bytes of the hole itself, since distances are measured from the end of the instruction:

   9:  e8 00 00 00 00          call   e <main+0xe>
                       a: R_X86_64_PLT32    square-0x4
  26:  8b 15 00 00 00 00       mov    edx,DWORD PTR [rip+0x0]
                       28: R_X86_64_PC32    calls-0x4

And after linking, the same instructions with the holes filled:

  1142:  e8 3e 00 00 00         call   1185 <square>
  115f:  8b 15 af 2e 00 00      mov    edx,DWORD PTR [rip+0x2eaf]   # 4014 <calls>

The linker even saved a few bytes: the text "%d\n" is the end of "calls: %d\n", so it stored the longer one only, at 0x2004, and pointed the shorter one at 0x200b, 7 bytes in. Running the program, and asking which shared libraries it needs:

$ gcc -O1 -o prog main.o square.o
$ ./prog
49
calls: 1
$ ldd prog
        linux-vdso.so.1 (0x00007ffe2db56000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x0000784bf2600000)
        /lib64/ld-linux-x86-64.so.2 (0x0000784bf29a0000)    ← the dynamic linker

Linked dynamically, the program is 15,992 bytes. Linked statically, with its own copy of everything it uses from the C library, it's 785,416 bytes: almost 50 times bigger, to print two lines.

Finally, Clang's -O1 version of sum_to for RISC-V. It found the same formula as on x86-64, built from RISC-V's simpler instructions. mulhu gives the top 64 bits of the 128-bit product, which x86's mul put in rdx:

sum_to:
    blez  a0, .LBB0_2       # n ≤ 0: the answer is 0
    slli  a1, a0, 1         # a1 = 2n
    addi  a2, a0, -1        # a2 = n − 1
    addi  a0, a0, -2        # a0 = n − 2
    mul   a3, a2, a0        # (n−1)(n−2): low 64 bits
    mulhu a0, a2, a0        #           high 64 bits
    slli  a0, a0, 63
    srli  a3, a3, 1
    or    a0, a0, a3        # … ÷ 2
    add   a0, a0, a1        # … + 2n
    addi  a0, a0, -1        # … − 1  =  n(n+1)/2
    ret
.LBB0_2:
    li    a0, 0
    ret

Try it yourself

  1. How many tokens are there in total = total + 42;?
    Show answerSix: total, =, total, +, 42 and ;. The spaces aren't tokens; they just separate them.
  2. In the syntax tree for (a + b) * c, which operator is at the top, and why?
    Show answerThe ×. The brackets make the addition happen first, so it sits lower in the tree, as the left branch of the multiplication. The top of the tree is always the operation done last.
  3. What can an optimiser do with a * (2 + 6)?
    Show answerFold the constants into a * 8, then swap the multiplication for a shift left by 3, since 8 = 2³. Try it in the tiny compiler.
  4. In the linker demo, call square is at 0x1142, is 5 bytes long, and square ends up at 0x1185. Which 4 bytes fill the hole?
    Show answerThe next instruction starts at 0x1142 + 5 = 0x1147. The distance is 0x1185 − 0x1147 = 0x3e, stored lowest byte first: 3e 00 00 00.
  5. Why is a statically linked program so much bigger, and why might you still want one?
    Show answerIt contains its own copy of all the library code it uses, instead of sharing the one copy on the system. But it needs nothing else to run, so you can copy it to another Linux computer and it works even if that computer has different library versions.

What we learned

Compiling everything to machine code ahead of time is one way to run a program. Python, JavaScript and Java take other routes. Next: interpreters, virtual machines and garbage collection.