What a Computer Does With a Program

12 · What a Computer Does With a Program¶

The question¶

What actually happens between a source file and a result, and which of it costs anything?

Most of it costs nothing. A great deal of what looks like work in a C program has been finished before the machine is switched on, and the part that remains is smaller and stranger than the source suggests. Separating the two is the skill the rest of Part III is built on, because you cannot ask what a program costs until you know which parts of it still exist at the time it runs.

The material¶

One command is four programs¶

gcc sameanswer.c -o sameanswer looks like one operation. gcc is a launcher that runs four programs in turn, each of which leaves a file on disk that you are allowed to look at and normally never do.

Here is the walk through them, as a shell script rather than a paragraph, so you can run it yourself:

# 1. Preprocess. Text in, text out: includes pasted in, macros expanded, comments deleted.
#    No C has been understood yet — cpp does not know what a function is.
$cc $flags -E "$source" -o "$outdir/$stem.i"

# 2. Compile. The only stage that makes decisions. C in, assembly out.
$cc $flags -S "$outdir/$stem.i" -o "$outdir/$stem.s"

# 3. Assemble. Assembly in, object out: instructions become bytes, and anything whose address is
#    not yet known becomes a relocation for the linker to fill in.
$cc $flags -c "$outdir/$stem.s" -o "$outdir/$stem.o"

# 4. Link. Objects and libraries in, one program out. -static so the result runs under user-mode
#    QEMU, which has no RISC-V loader to offer it.
$cc $flags -static "$outdir/$stem.o" -o "$outdir/$stem"

Four commands differing only in where gcc is told to stop. Run it on the program this chapter uses:

sysfs/tools/stages.sh sysfs/tools/sameanswer.c /tmp/walk
ls -l /tmp/walk

What each stage is allowed to know¶

The stages differ in what each one is allowed to know, and that difference explains most of what each one does.

The preprocessor does text substitution and nothing else. It has never heard of a function, a type, or a loop. #include means paste that file in here; a macro means replace this name with that text. What comes out — one source file with everything it included pasted in — is what the compiler actually sees, and is called a translation unit. When the preprocessor finishes, every name it introduced is gone and no later stage can tell that a macro was ever involved. This is why a macro is not a variable and why a bug in one is reported at a line that does not look wrong.

The compiler is the only stage that decides anything. It reads C and writes assembly, and between those two it is free to do whatever it can prove does not change the result. Everything this book will later say about optimisation happens here.

The assembler does a lookup. Mnemonics become bytes. It knows the addresses of things inside the file it is reading, and nothing about anything outside it — so where your code refers to something it cannot see, it writes a hole and a note describing what belongs in it. That note is a relocation The Santa Cruz Operation (n.d.).

The linker fills the holes. It gathers objects and libraries, decides where everything will live, and resolves the notes. It is the first stage that knows a real address.

The same loop, twice¶

Here is the whole of the program’s arithmetic. Two functions, close enough that you could reasonably call them the same function:

#define SYSFS_STAGES_DEFINE_SUMS                            \
  unsigned long sysfs_sum_folded(void) {                    \
    unsigned long total = 0;                                \
    for (unsigned n = 0; n < SYSFS_STAGES_SPAN; n++)        \
      total += n;                                           \
    return total;                                           \
  }                                                         \
                                                            \
  unsigned long sysfs_sum_counted(unsigned span) {          \
    unsigned long total = 0;                                \
    for (unsigned n = 0; n < span; n++)                     \
      total += n;                                           \
    return total;                                           \
  }

Same loop, same accumulator, same arithmetic, same optimisation level. The only difference is where the bound comes from: one is a number the compiler can read, the other arrives in a register while the program is running.

This is what the compiler did with the first one:

sysfs_sum_folded compiled for riscv64 at -O2 — the xv6 target’s instruction set, 2 instructions.

0000000000000000 <sysfs_sum_folded>:
   0:	li	a0,2016
   4:	ret

Conditions: target xv6 · riscv64 cross compiler, any machine — nothing here was executed · riscv64-linux-gnu-gcc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0 · -O2 -Wall -Wextra -march=rv64gc -mabi=lp64d -c · 2026-09-17 · Source: bench/results/stages-riscv64.json, code hash 44c82e8a3b25ae99.

There is no loop. There is no addition. The compiler ran the loop itself, at compile time, and wrote down what it got — the entire function is a constant and a return. Whatever that sum cost, it was not paid by the machine that runs this program.

And the second:

sysfs_sum_counted compiled for riscv64 at -O2 — the xv6 target’s instruction set, 11 instructions.

0000000000000006 <sysfs_sum_counted>:
   6:	beqz	a0,1c <.L6>
   8:	slli	a4,a0,0x20
   c:	srli	a4,a4,0x20
   e:	li	a5,0
  10:	li	a0,0

0000000000000012 <.L5>:
  12:	add	a0,a0,a5
  14:	addi	a5,a5,1
  16:	bne	a5,a4,12 <.L5>
  1a:	ret

000000000000001c <.L6>:
  1c:	li	a0,0
  1e:	ret

Conditions: target xv6 · riscv64 cross compiler, any machine — nothing here was executed · riscv64-linux-gnu-gcc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0 · -O2 -Wall -Wextra -march=rv64gc -mabi=lp64d -c · 2026-09-17 · Source: bench/results/stages-riscv64.json, code hash 44c82e8a3b25ae99.

That is a loop: a counter, an accumulation, and a branch backwards. It also has a case for zero and a pair of shifts at the top, which are there because span is a 32-bit unsigned living in a 64-bit register and the compiler has to say which half of it means anything. That is ch13’s subject, arriving early.

Nothing about the source said one of these was expensive. The difference is entirely about what the compiler could prove. It may replace a loop with its answer only when it can establish that the loop terminates, that the bound is known, and that the result cannot depend on anything it cannot see. Take any one of those away and the loop comes back.

This book returns to that pattern constantly: the cost of a construct is not a property of the construct. It depends on what the compiler was able to determine about its surroundings, which is why the answer to “is this fast?” is so often “show me the rest of the file”.

What the object file still owes¶

Compile the program but do not link it, and it is incomplete in a specific and visible way:

riscv64-linux-gnu-nm -u /tmp/walk/sameanswer.o

-u lists undefined symbols — names the object uses and cannot supply. The program calls printf, which lives somewhere else entirely, so the assembler left a hole. After linking there are none: every name has been resolved to an address, which is most of what “linking” means.

What we measured¶

Nothing here is a timing. These are file sizes and symbol counts — facts about what a compiler produced, which is why they are stamped as artefacts rather than measurements and why CI regenerates them on every push rather than trusting the committed copy.

What each stage handed to the next:

Conditions: target xv6 · riscv64 cross compiler, any machine — nothing here was executed · riscv64-linux-gnu-gcc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0 · -O2 -Wall -Wextra -march=rv64gc -mabi=lp64d · 2026-09-17 · Source: bench/results/stagewalk-riscv64.json, code hash a709eb7d4f82e541.

Read the two columns against each other, because bytes and lines do not move together.

The preprocessed file is enormous compared with the source, and almost none of it is yours: one #include <stdio.h> drags in every declaration the C library wants you to have. The compiler then throws nearly all of it away — the assembly it produces is a small fraction of the text it read — because a declaration you never used generates no code. That collapse shows what a declaration is: a promise about what exists, not an instruction to build it.

Then the file gets larger in bytes while getting much smaller in lines, which is what happens when text becomes a container format. The object file is ELF: headers, a symbol table, relocations and a section of instructions, and the instructions are the smallest part.

And then linking:

Conditions: target xv6 · riscv64 cross compiler, any machine — nothing here was executed · riscv64-linux-gnu-gcc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0 · -O2 -Wall -Wextra -march=rv64gc -mabi=lp64d · 2026-09-17 · Source: bench/results/stagewalk-riscv64.json, code hash a709eb7d4f82e541.

The two linked sizes are the same program. One is linked statically — every library routine it needs copied into the file — against the GNU C library; the other is linked by xv6 against its own user library, which is a few hundred lines and knows how to do almost nothing. The difference between them is not your program — your program is identical — it is the cost of everything printf is prepared to do if asked. ch15 opens that binary up and says where it all went.

The same program in both worlds¶

Build it for each target and run it:

make xv6-qemu                 # then, at the xv6 prompt: sameanswer
python3 -m pytest tests/test_stages.py -q

Both print the same six lines. The folded route and the counted route agree, as they must — they compute the same sum, and the compiler is not permitted to change the answer, only the work.

What the two targets will not tell you is which route was faster. QEMU has no opinion about time worth listening to, and the board is not attached to this chapter. ch23 puts that question properly, and ch26 answers it.

What this cannot tell you¶

Nothing here is a cost. The sizes above are how much space a compiler used, and space is not time: a smaller binary is not automatically a faster one, and a function that compiles to two instructions is not automatically cheaper than one that compiles to ten. ch27 shows a case where more instructions run faster, for reasons entirely outside the instruction count.

It is one compiler, at one optimisation level. Everything in this chapter is what gcc at -O2 decided, and the conditions line under each table says which gcc. A different version may fold a loop this one leaves alone. That is why the listings are regenerated by CI instead of transcribed: if the compiler changes its mind the build fails, rather than the book quietly becoming wrong.

“The compiler folded it” is a description, not a mechanism. This chapter shows you that it happened and states the conditions under which it is allowed to. It does not show you how the decision is made, and this book never will — that is a compiler course, and an honest systems book is better off teaching you to look at the output than to model the optimiser.

One #include is not a fair account of the C library. The preprocessed size above measures <stdio.h> and its dependencies, not “the cost of libc”. A program that includes more headers preprocesses to more text and may still link to the same binary.

And that size briefly depended on where the repository sat on disk. The preprocessor writes into its output the name of every file it pasted in, spelled exactly as the command line spelled it. So an absolute include path makes the preprocessed file longer on a machine whose checkout sits deeper, and the same commit measured larger on a CI runner than on a laptop — the whole difference being the lines the preprocessor writes to say which file each piece came from, naming one header. Nothing about the number could have given that away; a size is a size. It surfaced only because CI regenerates this result instead of trusting the committed copy, and the two disagreed. stages.sh now names every path relative to the repository root, and the runner refuses to stamp a result if any file the walk produced mentions where the repository lives. It shows exactly what stage 1 does: it pastes text, and the paths are part of the text.

Problems¶

Three. Each has a test that passes only when you have solved it, and none of them has an answer stored anywhere in this repository.

12.1 — Which stage produced this? tests/what_a_computer_does_with_a_program/problem_1_stages.py gives you fragments of the four files and asks which program wrote each one. The fragments are real. The fastest way to solve it is not to stare at them but to run sysfs/tools/stages.sh yourself and look at your own.

python3 -m pytest tests/what_a_computer_does_with_a_program/test_problem_1_stages.py

12.2 — Predict the ripple. Four edits to the program. For each one, say which stages produce a different file afterwards.

This test stores no expected answers. It makes each change, runs the toolchain, and compares the bytes — so you are not being marked against an answer key, you are being marked against a compiler. When you disagree with it, it is right, and the interesting question is what you believed that was not true.

python3 -m pytest tests/what_a_computer_does_with_a_program/test_problem_2_ripple.py

12.3 — Take the folding away. Write a function that computes the same sum and that the compiler cannot evaluate for you. It must still contain a loop, and the machine must actually run it — the test disassembles what came out and looks for a backward branch, so returning a constant will not pass and neither will a loop the optimiser can see through.

python3 -m pytest tests/what_a_computer_does_with_a_program/test_problem_3_unfold.py

There is more than one way to do it and they are not equally good. The section on the same loop twice says what the compiler has to be able to prove; take away whichever of those you like.

Where to go next¶

The ELF specification The Santa Cruz Operation (n.d.) defines the object format the assembler writes and the linker reads: sections, symbols and relocations, all of which ch15 takes apart properly. It is worth skimming now purely to see that the thing nm printed is a documented structure rather than a convention.

The RISC-V psABI RISC-V International (n.d.) says which relocation types exist and what each one means, and is the document that explains why a call to printf looks the way it does in the object file.

ch13 goes back to the thing the compiler was manipulating in the first place: what a number is to this machine, and when that answer bites.