From C to machine code

Lessons 5 to 7 treated assembly language as the programmer's starting point. In practice almost all machine code is produced by tools: a compiler translates a high-level language, an assembler turns assembly into binary object files, a linker combines object files and libraries into an executable, and a loader puts the executable into memory and starts it. Each step changes the program's form while keeping its meaning, and each leaves fingerprints that you can see if you know where to look. This lesson follows a small C program through the whole toolchain, using clang and the LLVM tools targeting RV32IM, and shows the real intermediate files at each stage: the compiler's intermediate representation, assembly, object files with their symbols and relocations, the linked executable and its program headers. It then compares the code generated for RISC-V with that for x86-64 and looks briefly at interpreters and just-in-time compilers.

The four stages

Running cc prog.c on a Unix system hides four separate programs. The preprocessor handles directives such as #include and #define, producing pure C text. The compiler translates that text into assembly language for the target processor. The assembler translates assembly into an object file containing machine code and data, plus tables describing what the file defines and what it still needs. The linker combines one or more object files with library code into an executable file. When you run the executable, the operating system's loader reads it, maps its segments into memory, sets up the stack and jumps to the entry point. CMPUT-201 lesson 2 walked through these stages for x86-64 from the C programmer's point of view; this lesson looks inside the files they produce.

The example has two source files. util.c defines a global variable counter, a file-private variable scale and a function bump. main.c declares counter and bump as external, defines a constant string and an array, and calls bump. Because each file is compiled separately, the compiler working on main.c does not know where counter or bump will end up; resolving those references is the linker's job.

int counter = 5;
static int scale = 3;

int bump(int x) {
    counter += x;
    return counter * scale;
}

extern int counter;
int bump(int x);

const char greeting[] = "hi";
int table[100];

int main(void) {
    return bump(2) + counter + table[3] + greeting[0];
}

Inside the compiler

A modern compiler has three parts. The front end parses the source language, checks types and produces an intermediate representation, or IR, a simple language independent of both the source language and the target machine. The middle end, or optimizer, transforms the IR to make it faster or smaller: removing unused code, propagating constants, keeping values in registers, inlining small functions, simplifying loops. The back end translates the optimized IR into the target's assembly, choosing instructions, assigning the program's many temporary values to the processor's limited registers, and scheduling instructions to suit the pipeline. Because the parts are separate, LLVM can support many languages (C, C++, Rust, Swift) and many processors (x86-64, Arm, RISC-V, WebAssembly) with one optimizer.

LLVM's IR can be printed. Here is the optimized IR for util.c, with metadata lines removed. It looks like assembly for an imaginary machine with an unlimited number of registers, written %2, %3 and so on, each assigned exactly once.

clang --target=riscv32 -march=rv32im -mabi=ilp32 -O1 -S -emit-llvm util.c -o -

@counter = dso_local local_unnamed_addr global i32 5, align 4

define dso_local i32 @bump(i32 noundef %0) local_unnamed_addr #0 {
  %2 = load i32, ptr @counter, align 4, !tbaa !4
  %3 = add nsw i32 %2, %0
  store i32 %3, ptr @counter, align 4, !tbaa !4
  %4 = mul nsw i32 %3, 3
  ret i32 %4
}

Two optimizations are already visible. The variable scale has disappeared: it is static, so no other file can change it, and nothing in util.c ever assigns to it, so the optimizer replaced every use with the constant 3. And the IR flags the addition and multiplication with nsw, meaning no signed wrap, recording C's rule that signed overflow is undefined so that later passes may assume it does not happen.

The back end then turns the IR into RISC-V assembly. The multiplication by 3 has become a shift and an add, the strength reduction from lesson 2, because a shift and an add are cheaper than mul on most implementations.

int counter = 5;
static int scale = 3;

int bump(int x) {
    counter += x;
    return counter * scale;
}

$ clang --target=riscv32 -march=rv32im -O1 -S util.c -o -
bump:
    lui     a1, %hi(counter)
    lw      a2, %lo(counter)(a1)
    add     a2, a2, a0
    slli    a0, a2, 1
    add     a0, a0, a2
    sw      a2, %lo(counter)(a1)
    ret
counter:
    .word   5

Object files, symbols and relocations

The assembler produces an object file in ELF, the Executable and Linkable Format used by Linux and most Unix-like systems. An object file is divided into sections: .text holds machine code, .data holds initialized variables, .rodata holds read-only constants such as string literals, and .bss records the size of zero-initialized variables without storing their bytes, since zeros need not be kept in the file. Other sections hold the symbol table, which lists the names the file defines and uses, and relocation records, which mark places in the code where an address must be filled in later.

clang --target=riscv32 -march=rv32im -mabi=ilp32 -O1 -c main.c util.c
llvm-nm main.o util.o
llvm-readelf -S main.o     # section list, filtered

main.o:
         U bump
         U counter
00000000 R greeting
00000000 T main
00000000 B table

util.o:
00000000 T bump
00000000 D counter
  [ 2] .text             PROGBITS        00000000 000034 00003c 00  AX  0   0  4
  [ 3] .rela.text        RELA            00000000 000180 000078 0c   I 10   2  4
  [ 4] .rodata           PROGBITS        00000000 000070 000003 00   A  0   0  1
  [ 5] .bss              NOBITS          00000000 000074 000190 00  WA  0   0  4
  [10] .symtab           SYMTAB          00000000 0000c0 0000c0 10      1   7  4

In the nm listing, T marks a symbol defined in a text section, D in a data section, R in read-only data, B in bss, and U a symbol that is used but undefined in this file. main.o defines main, greeting and table, but uses counter and bump without defining them. The section list confirms the sizes: table's 400 bytes appear as 0x190 in .bss without taking space in the file, greeting's three bytes (h, i and the terminator) are in .rodata, and .rela.text holds the relocation records.

clang --target=riscv32 -march=rv32im -mabi=ilp32 -O1 -c main.c
llvm-objdump -dr --no-show-raw-insn main.o

00000000 <main>:
       0:      	addi	sp, sp, -0x10
       4:      	sw	ra, 0xc(sp)
       8:      	li	a0, 0x2
       c:      	auipc	ra, 0x0
			0000000c:  R_RISCV_CALL_PLT	bump
			0000000c:  R_RISCV_RELAX	*ABS*
      10:      	jalr	ra <main+0xc>
      14:      	lui	a1, 0x0
			00000014:  R_RISCV_HI20	counter
			00000014:  R_RISCV_RELAX	*ABS*
      18:      	lw	a1, 0x0(a1)
			00000018:  R_RISCV_LO12_I	counter
			00000018:  R_RISCV_RELAX	*ABS*
      1c:      	lui	a2, 0x0
			0000001c:  R_RISCV_HI20	table+0xc
			0000001c:  R_RISCV_RELAX	*ABS*
      20:      	lw	a2, 0x0(a2)
			00000020:  R_RISCV_LO12_I	table+0xc
			00000020:  R_RISCV_RELAX	*ABS*
      24:      	add	a0, a0, a1
      28:      	add	a0, a0, a2
      2c:      	addi	a0, a0, 0x68
      30:      	lw	ra, 0xc(sp)
      34:      	addi	sp, sp, 0x10
      38:      	ret

Each indented line after an instruction is a relocation record. The call to bump has been assembled as auipc ra, 0 followed by jalr, with a zero offset because the target is unknown, and an R_RISCV_CALL_PLT record asks the linker to patch in the real distance. The load of counter uses a lui and lw pair, with R_RISCV_HI20 and R_RISCV_LO12_I records asking for the high 20 and low 12 bits of counter's eventual address, the same split you computed by hand in lesson 5. The access to table[3] asks for the address of table + 12. The R_RISCV_RELAX records give the linker permission to shorten these sequences if the final addresses allow it. One more optimization is visible: greeting[0] has become the constant 0x68, the ASCII code of h, because greeting is a constant array whose contents the compiler knows.

Linking

The linker reads all the object files, decides where each section will go in memory, builds a combined symbol table, and then applies every relocation using the final addresses. If a symbol is undefined everywhere, or defined twice, linking fails with an error such as undefined reference to bump. Here the link uses LLVM's linker, ld.lld, with the text segment placed at 0x00400000 as in the course's simulator.

clang --target=riscv32 -march=rv32im -mabi=ilp32 -O1 -c main.c util.c
ld.lld -m elf32lriscv -Ttext=0x00400000 -e main main.o util.o -o prog
llvm-objdump -d --no-show-raw-insn prog
llvm-nm prog

00400000 <main>:
  400000:      	addi	sp, sp, -0x10
  400004:      	sw	ra, 0xc(sp)
  400008:      	li	a0, 0x2
  40000c:      	jal	0x400038 <bump>
  400010:      	lui	a1, 0x402
  400014:      	lw	a1, 0x58(a1)
  400018:      	lui	a2, 0x402
  40001c:      	lw	a2, 0x68(a2)
  400020:      	add	a0, a0, a1
  400024:      	add	a0, a0, a2
  400028:      	addi	a0, a0, 0x68
  40002c:      	lw	ra, 0xc(sp)
  400030:      	addi	sp, sp, 0x10
  400034:      	ret

00400038 <bump>:
  400038:      	lui	a1, 0x402
  40003c:      	lw	a2, 0x58(a1)
  400040:      	add	a2, a2, a0
  400044:      	slli	a0, a2, 0x1
  400048:      	add	a0, a0, a2
  40004c:      	sw	a2, 0x58(a1)
  400050:      	ret
00400038 T bump
00402058 D counter
00401054 R greeting
00400000 T main
0040205c B table

Compare this with the object file. The two-instruction auipc and jalr call has been relaxed to a single jal, because bump ended up only a few dozen bytes away, well within jal's ±1 MiB reach; the program is one instruction shorter than the compiler's output. The lui instructions now contain real upper address bits, and the loads have real offsets: counter lives at 0x00402058 and table at 0x0040205C. bump follows main directly in the text segment.

Libraries complicate the picture slightly. A static library is an archive of object files, and the linker copies in just the ones the program needs. A shared library, a .so file on Linux or a .dll on Windows, is linked at load time or run time instead, so many programs can share one copy in memory and a library can be updated without relinking its users. Calls into shared libraries go through small stubs in a procedure linkage table (PLT), and addresses of shared data go through a global offset table (GOT), both filled in by the dynamic linker, which is why the relocation above mentions PLT even though this program is linked statically.

Loading and starting a program

An executable also contains program headers, which tell the loader which parts of the file to map into memory, at which addresses and with which permissions. The section headers are for linkers and debuggers; the program headers are for the loader. The readelf listing below shows that the text is loaded read-and-execute, the read-only data read-only, and the data and bss read-write, with a memory size larger than the file size: the difference is the bss, which the loader fills with zeros.

llvm-readelf -l prog     # program headers

Elf file type is EXEC (Executable file)
Entry point 0x400000
There are 7 program headers, starting at offset 52
Program Headers:
  Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
  PHDR           0x000034 0x00010034 0x00010034 0x000e0 0x000e0 R   0x4
  LOAD           0x000000 0x00010000 0x00010000 0x00114 0x00114 R   0x1000
  LOAD           0x001000 0x00400000 0x00400000 0x00054 0x00054 R E 0x1000
  LOAD           0x001054 0x00401054 0x00401054 0x00003 0x00003 R   0x1000
  LOAD           0x001058 0x00402058 0x00402058 0x00004 0x00194 RW  0x1000
  GNU_STACK      0x000000 0x00000000 0x00000000 0x00000 0x00000 RW  0x0

On Linux, the execve system call does the loading. The kernel checks the file's header, maps each LOAD segment at its address with the requested permissions, allocates a stack, copies the program's arguments and environment strings onto it, and starts executing at the entry point. For dynamically linked programs, the entry point first belongs to the dynamic linker, which maps the shared libraries and fills in the GOT. The entry point of a normal C program is not main but a small piece of startup code, often called crt0 or _start, which sets up the global pointer and stack, initializes the C library and calls main with argc and argv; when main returns, it calls exit with main's return value. The course's simulator uses an even smaller startup sequence that calls main and then requests the exit service.

Mapping segments with separate permissions is an important security property. Because the text segment is not writable, a bug cannot modify the program's code, and because the data and stack are not executable, injected data cannot be run as code. Address space layout randomization, mentioned in lesson 7, places these segments at different addresses each time, which is why real systems compile code as position-independent, using auipc-relative addresses instead of the absolute lui addresses in this example.

The same C code on two ISAs

Comparing the output for two ISAs shows how much of a program's machine code reflects the source and how much reflects the processor. Here is a short function that counts how many elements of an array exceed a threshold, compiled by clang for RV32IM and by gcc for x86-64 at the same optimization level.

int count_above(const int *a, int n, int t) {
    int c = 0;
    for (int i = 0; i < n; i++)
        if (a[i] > t)
            c++;
    return c;
}

$ clang --target=riscv32 -march=rv32im -O1 -S count.c -o -
count_above:
    li      a3, 0
    blez    a1, .LBB0_3
    slli    a1, a1, 2
    add     a1, a0, a1
.LBB0_2:
    lw      a4, 0(a0)
    slt     a4, a2, a4
    addi    a0, a0, 4
    add     a3, a3, a4
    bne     a0, a1, .LBB0_2
.LBB0_3:
    mv      a0, a3
    ret
$ gcc -O1 -masm=intel -S count.c -o -   (x86-64)
count_above:
    test    esi, esi
    jle     .L5
    mov     rax, rdi
    movsx   rsi, esi
    lea     rdi, [rdi+rsi*4]
    mov     ecx, 0
.L4:
    cmp     DWORD PTR [rax], edx
    setg    sil
    movzx   esi, sil
    add     ecx, esi
    add     rax, 4
    cmp     rax, rdi
    jne     .L4
.L1:
    mov     eax, ecx
    ret
.L5:
    mov     ecx, 0
    jmp     .L1

Both compilers turned the loop into a pointer walk and avoided a branch for the if. clang used slt, which directly produces the 0 or 1 to add, in the style of lesson 2; gcc used x86-64's setg instruction, which reads the condition flags written by cmp. The x86-64 code can add a memory operand directly in instructions such as cmp DWORD PTR [rax], edx, which RISC-V cannot; RISC-V needs a separate lw. On the other hand every RISC-V instruction is 4 bytes, while the x86-64 instructions here range from 1 byte (ret) to 5 bytes (mov ecx, 0), so the two functions end up almost the same size: 52 bytes for RISC-V and 50 for x86-64. The x86-64 loop body has seven instructions to RISC-V's five, partly because turning a flag into a number takes two instructions, setg and movzx. Differences like these are real but modest; for performance, the microarchitecture that runs the code usually matters more than the ISA it is written in.

Optimizing compilers apply many more transformations than these examples show. Inlining replaces a call with a copy of the callee's body, removing the call overhead and exposing more optimization. Loop unrolling repeats the loop body several times per iteration to reduce branch overhead. Vectorization uses SIMD instructions, which lesson 12 introduces, to process several array elements at once. Each makes the generated code harder to match with the source, which is why debuggers struggle with optimized programs and why compilers offer -Og, an optimization level that keeps code debuggable.

Interpreters, bytecode and just-in-time compilation

Not every language is compiled ahead of time to machine code. Python compiles source to bytecode, instructions for a virtual stack machine, and an interpreter written in C executes the bytecode one instruction at a time. Each bytecode instruction costs many machine instructions, which is a large part of why pure Python loops run tens of times more slowly than C loops. The dis module shows the bytecode.

import dis

def count_above(a, t):
    c = 0
    for x in a:
        if x > t:
            c += 1
    return c

print(count_above([5, 12, 7, 20, 3], 6))
ops = [ins.opname for ins in dis.get_instructions(count_above)]
print(len(ops), 'bytecode instructions; loop uses', ', '.join(dict.fromkeys(ops[4:14])))

3
20 bytecode instructions; loop uses GET_ITER, FOR_ITER, STORE_FAST, LOAD_FAST_LOAD_FAST, COMPARE_OP, POP_JUMP_IF_TRUE, JUMP_BACKWARD, LOAD_FAST, LOAD_CONST, BINARY_OP

Java and C# compile to bytecode too, but their virtual machines include just-in-time (JIT) compilers that translate frequently executed bytecode into native machine code while the program runs, using information about how the program actually behaves to optimize it. JavaScript engines in web browsers do the same, and recent CPython versions include an experimental JIT compiler. The trade-offs are those of this whole lesson in miniature: interpreting is simple and portable, compiling ahead of time gives fast start-up and predictable speed, and JIT compilation can approach or occasionally beat ahead-of-time code at the cost of warm-up time and memory.