Compilation, Assembly, Linking, and Execution: From Code to Process
The Four Stages of Compilation
What we usually call compilation actually comprises four stages: preprocessing, compilation, assembly, and linking. For example, running gcc without any additional options performs all four in one go, taking a.c through to a.out.
Preprocessing
Preprocessing is straightforward: handle all the preprocessing directives, including macro definitions, conditional compilation, and #include.
For example, suppose we have this simple program:
#include <stdio.h>
int main() {
printf("Hello, World!\n");
return 0;
}
During preprocessing, the #include directive is expanded, inserting the entire stdio header into the current file.
This happens implicitly, without generating a visible intermediate file. To inspect it, use gcc -E to perform preprocessing only and print the result to stdout.
Compilation
Compilation is, of course, the most important and complex of the four stages. It contains many smaller steps: lexical analysis, syntax analysis, semantic analysis, intermediate code generation, code optimization, and more.
Lexical Analysis
During lexical analysis, the lexer converts source code into a series of tokens. Spaces, line breaks, comments, and similar elements are removed, leaving meaningful symbols such as keywords and variable names.
For example, int main() { return 0; } is broken into the tokens int, main, (, ), {, return, 0, }, and ;.
Syntax Analysis
Next comes syntax analysis, usually called parsing. The parser takes the lexer’s output and constructs an abstract syntax tree (AST) according to the language’s grammar.
For the simple example above, the AST might look like this:
Program
|
Function
/ \
/ Body
/ / \
"int main" Call Return
| |
"printf" "0"
|
"Hello, World!\n"
Semantic Analysis
The AST then undergoes semantic analysis, which generally includes type checking, scope rules, function definitions and calls, assignments, and so on.
For our AST, the compiler might first check that main’s return type conforms to the C standard. It might then check the argument types in the call to printf, as well as checking that the call is within main’s scope. Although this example contains no assignments, it does return the integer 0, so the compiler also checks that this matches the function’s return type.
The result is an enhanced AST, potentially carrying additional type and binding information. For example, the 0 in return 0 is annotated as an int, and printf is bound to its declaration in stdio.h. Naturally, any problems detected here also produce warnings or errors.
Intermediate Code Generation and Optimization
The AST is then converted into an intermediate representation (IR). An IR is generally designed to be independent of a specific source language or machine, allowing the compiler to support multiple languages. It is also usually easy to analyze and optimize, making it convenient to implement techniques such as code elimination and loop optimization.
A simple example of loop optimization starts with this code:
int i;
int n = 10;
int a = 5;
int b = 6;
int array[10];
for (i = 0; i < n; i++) {
array[i] = a * b + i;
}
The value of a * b is the same on every iteration, regardless of i, so it can be moved out of the loop. The result is equivalent to:
int i;
int n = 10;
int a = 5;
int b = 6;
int array[10];
int temp = a * b;
for (i = 0; i < n; i++) {
array[i] = temp + i;
}
Of course, optimization operates on the IR, so no readable source code like this is actually generated. The IR’s logic is simply equivalent to it.
Target Code Generation
The IR is then converted into assembly code. For the simple C program at the beginning, the generated assembly might resemble this:
.section .rodata
.LC0:
.string "Hello, World!\n"
.text
.globl main
.type main, @function
main:
pushq %rbp
movq %rsp, %rbp
leaq .LC0(%rip), %rdi
call puts
movl $0, %eax
popq %rbp
ret
This stage involves register allocation, instruction scheduling, and code layout, all of which significantly affect execution efficiency.
Registers are much faster to access than memory, so keeping frequently used variables in registers wherever possible can greatly improve overall access speed. A suitable instruction order reduces processor waiting time, mainly by avoiding stalls caused by data dependencies.
Code layout determines how the program’s parts are arranged in memory. Modern CPU branch prediction tends to favor continuing along the sequential execution path rather than jumping, so placing the more likely branch on that path is more efficient. Ideally, a branch would therefore produce assembly like the following, with near_branch on the sequential path and far_branch reached by a jump:
cmp eax, 1
je near_branch
jmp far_branch
near_branch:
; high frequency
jmp continue_execution
far_branch:
; low frequency
continue_execution:
This completes compilation and produces assembly code, usually stored in an .s or .asm file.
Assembly
Assembly is relatively simple. It is a mechanical, one-to-one mapping: look up each assembly instruction and translate it into its corresponding binary form.
For example, this instruction moves the number 1 into the AX register:
MOV AX, 1
On x86 in little-endian form, it should always correspond to:
B8 01 00
Here B8 is the opcode for MOV AX, immediate, and 01 00 is the 16-bit representation of 1.
Assembly produces an object file, usually with an .obj or .o extension.
ELF Files
Unlike C source and assembly files, an object file is already binary rather than plain text. We therefore need to understand its format to see what it contains.
On Unix, binaries including object files use ELF (Executable and Linkable Format). Besides object files, ELF also covers shared object files (.so) and actual executables such as /bin/bash.
An ELF file starts with an ELF header containing its metadata. First comes the magic number identifying it as ELF: 45 4c 46 is the ASCII for the letters ELF, while the leading 7f is a historical inheritance from the PDP-11. This is followed by information such as the ELF version and ABI version. For example, the simple program above has this ELF header:
$ readelf -h hello
ELF Header:
Magic: 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
Class: ELF64
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: UNIX - System V
ABI Version: 0
Type: DYN (Shared object file)
Machine: Advanced Micro Devices X86-64
Version: 0x1
Entry point address: 0x1060
Start of program headers: 64 (bytes into file)
Start of section headers: 14712 (bytes into file)
Flags: 0x0
Size of this header: 64 (bytes)
Size of program headers: 56 (bytes)
Number of program headers: 13
Size of section headers: 64 (bytes)
Number of section headers: 31
Section header string table index: 30
The body of an ELF file consists of sections. It is useful to think of ELF as a general-purpose container for binary data: whatever information is needed can be defined in separate sections. ELF therefore also contains a directory of those sections, the Section Header Table.
Some of the most important and common sections are:
.text: executable program code..data: initialized global and static variables..bss: uninitialized global and static variables..rodata: read-only data, such as string literals and other constants..symtab: the symbol table, containing information about symbols such as functions and variables.
All of these sections exist after assembly, though some may be modified during static linking.
If the ELF is executable, it also has a Program Header Table containing the information needed to load the different parts of the program or system into memory.
The overall structure is therefore:
| ELF Header | |
|---|---|
| Program Header Table (Optional) | |
| .text | (Section) |
| .rodata | (Section) |
| … | (Section) |
| .data | (Section) |
| Section Header Table |
Static Linking
After assembly, we have a collection of ELF object files. Static linking still needs to reconcile the symbol definitions across them: a very common case is a function defined in another file.
To do this, the linker first resolves all the symbols—variable names, function names, and other identifiers—so that it has a global view of their definitions and uses. It can then connect function calls to the corresponding function definitions.
For those references to point to the right final addresses, the linker must allocate a unified address space for the contents of all the ELF files. Each ELF file assigns addresses to its own sections independently, so most addresses change after unification. Any direct references to variable or function addresses in the pre-link ELF files, such as pointers, must therefore be corrected to point to the new addresses. The original ELF files contain relocation tables, which the linker can use to make these corrections directly.
Sections are merged as part of this allocation. The binary produced by static linking is still an ELF container, so its format remains similar. There will not be multiple .text sections, for example: the .text sections from different object files are merged into one in the linked ELF file.
Loading
Loading is the process by which the loader moves the ELF’s contents into memory.
The loader views the ELF differently, as a collection of segments rather than sections. These are usually called the linking view and the execution view, respectively. The execution view is mainly concerned with differences in the permissions the contents require, resulting in major loaded segments for .text, .data, and .bss. .text is usually grouped with .rodata in a read-only memory region, helping prevent the program’s code from being modified during execution. .data and .bss naturally need to be readable and writable. The difference is that .bss, used for uninitialized global variables, is zeroed during loading.
Besides loading the ELF’s contents into memory, the OS allocates address space for the stack and heap when initializing the program. The stack stores function arguments, return addresses, and local variables: whenever a function call occurs, its metadata is saved there. From the application developer’s perspective, the stack should not be accessed or managed directly.
The heap is the part application developers do manage manually. Memory allocated with malloc, for example, comes from the heap. In principle, memory allocation is the kernel’s responsibility and requires a system call such as mmap or brk. For efficiency, the runtime library, such as libc, may therefore obtain a large block of memory “wholesale” and then distribute it “retail” to the places that actually need it.