You Wrote C. The CPU Has No Idea What C Is.

I think compilers are one of those things that become invisible way too quickly.

You write:

int add(int a, int b) {
    return a + b;
}

int main() {
    int result = add(2, 3);
    return result;
}

Then:

clang main.c -o main

And now there’s a program.

Cool.

Except the CPU has absolutely no idea what any of that means.

It doesn’t know what add is.

It doesn’t know what a variable called result is.

It doesn’t know what return means.

It doesn’t even know what C is.

So somewhere between:

result = add(2, 3);

and the processor actually doing something, our program has to become something completely different.

Turns out it doesn’t happen once.

It happens over and over again.

C source
   ↓
preprocessing
   ↓
tokens
   ↓
syntax tree
   ↓
semantic analysis
   ↓
intermediate representation
   ↓
optimization
   ↓
assembly
   ↓
machine code
   ↓
object file
   ↓
linking
   ↓
executable

That’s already more shit than I expected the first time I looked into this.

So let’s follow the program down.

And keep asking one question:

What survived?

First, the code changes before compilation really gets interesting

C has a preprocessing stage.

You’ve seen this stuff:

#include <stdio.h>
#define NUMBER 5

If you write:

#define NUMBER 5

int main() {
    return NUMBER;
}

the preprocessor turns it into something more like:

int main() {
    return 5;
}

You can see the result:

clang -E main.c

Do this on a file with a few headers and the output becomes enormous very quickly.

Turns out #include was hiding quite a lot behind that innocent little line.

For our tiny add program, though, preprocessing doesn’t do much worth staring at.

So we’ll keep moving.

The functions survived.

The variables survived.

It still looks like C.

For now.

Then your code stops being text

Take:

int result = add(2, 3);

I see a variable being declared and a function being called.

The compiler starts with characters.

It needs to work out which chunks of those characters actually mean something.

Conceptually, something like:

KEYWORD       int
IDENTIFIER    result
EQUALS        =
IDENTIFIER    add
LEFT_PAREN    (
INTEGER       2
COMMA         ,
INTEGER       3
RIGHT_PAREN   )
SEMICOLON     ;

Those are tokens.

This is lexing.

And it’s also the point where your formatting starts becoming somebody else’s problem.

This:

int result = add(2, 3);

and this crime:

int
result
=
add
(
2
,
3
)
;

mean the same thing.

All that time arguing about formatting and the lexer does not give a shit.

But a list of tokens still isn’t a program.

The compiler knows what pieces exist.

Now it needs to figure out how they fit together.

So it builds a tree

Take:

2 + 3 * 4

The compiler has to understand that multiplication has higher precedence than addition.

So the expression has structure:

       +
      / \
     2   *
        / \
       3   4

That’s the basic idea behind parsing.

For:

int result = add(2, 3);

you can imagine something like:

VariableDeclaration
├── name: result
├── type: int
└── value
    └── FunctionCall
        ├── add
        ├── 2
        └── 3

An Abstract Syntax Tree.

AST.

This is the point where the thing gets interesting to me.

Because the compiler doesn’t really need your source code anymore.

It has built its own representation of what you meant.

You can ask Clang to show you the AST:

clang -Xclang -ast-dump -fsyntax-only main.c

The real output is uglier.

Obviously.

Nobody involved in compiler development seems particularly concerned about me having a pleasant afternoon.

What survived?

Quite a lot.

result is still there.

add is still there.

The numbers are still there.

The compiler just isn’t looking at them the way we are anymore.

Valid syntax can still be bullshit

This is valid-looking structure:

int main() {
    return banana;
}

The parser can understand it.

Return an identifier called banana.

Fine.

Tiny issue.

What the fuck is banana?

Nobody declared it.

That’s the kind of thing semantic analysis deals with.

Names have to refer to things.

Types have to make sense.

Scopes matter.

The syntax can be perfectly valid while the program itself is still invalid.

That’s basically the jump here.

Earlier the compiler was asking:

What structure does this code have?

Now it has to ask:

Does this structure actually mean anything legal?

Once it knows that, your nice little C program is about to stop looking like C.

Your C code is about to disappear

Clang uses LLVM underneath.

Instead of the C frontend directly spitting out x86 instructions, the program gets lowered into an Intermediate Representation.

IR.

You can see LLVM IR with:

clang -S -emit-llvm main.c -o main.ll

Our function:

int add(int a, int b) {
    return a + b;
}

might look conceptually like:

define i32 @add(i32 %a, i32 %b) {
    %result = add i32 %a, %b
    ret i32 %result
}

Don’t learn LLVM IR from this snippet.

That is an entirely different way to lose an evening.

The point is simpler.

This isn’t C anymore.

But it isn’t machine code either.

It’s something in the middle.

The language-specific part of the compiler has taken what we wrote and turned it into a representation that other compiler passes can mess with.

And they absolutely will.

The compiler notices we’re idiots

Remember our program:

int add(int a, int b) {
    return a + b;
}

int main() {
    int result = add(2, 3);
    return result;
}

We wrote a function.

We call the function.

The function adds two numbers.

Very respectable programming.

Except for this program, 2 + 3 is always 5.

There isn’t much mystery here.

Compile without optimization:

clang -O0 -S main.c -o slow.s

Then:

clang -O2 -S main.c -o fast.s

Depending on your compiler version, platform, target and optimization level, you’ll get different output.

But the interesting possibility is that the compiler can look at all this:

int result = add(2, 3);
return result;

and eventually reduce the useful part to:

return 5;

Maybe it inlines add.

Maybe it sees that both arguments are constants.

Maybe it evaluates the addition during compilation.

Maybe the function stops being needed entirely.

The exact sequence isn’t the interesting part.

This is:

What survived?

result?

Gone.

The call to add?

Gone.

add itself?

Possibly gone.

The addition?

Could be gone too.

We wrote a variable, a function call and an addition.

The final program might contain none of them.

And still behave exactly the way we wanted.

That fucked with my mental model a little.

I used to think a compiler mostly translated things.

C goes in.

Assembly comes out.

But that’s not really what this feels like.

It’s more like the compiler keeps asking:

Do I actually need this?

And sometimes the answer is no.

Very rude.

Also useful.

Eventually we hit assembly

At some point, the compiler does have to generate code for a real processor.

Let’s say x86-64.

If our add function actually survives optimization, under one common calling convention it might look roughly like:

mov eax, edi
add eax, esi
ret

You do not need to know assembly to get the idea.

Roughly:

take a
put it where the return value will go
add b
return

Our:

return a + b;

is still there.

Just wearing significantly less clothing now.

But look at what disappeared.

No braces.

No C syntax.

No source-level variable names.

No int a.

No int b.

The values may still exist in registers.

But the names we gave them?

Those were for us.

The processor was never invited to that part of the conversation.

Assembly still isn’t machine code

This is one of those details I knew intellectually and still somehow skipped over in my head.

Assembly like:

mov eax, 5
ret

is still text.

The CPU does not see:

mov

and think:

Ah yes.

Move.

An assembler encodes instructions into bytes.

For a particular x86 sequence, you might see bytes like:

b8 05 00 00 00
c3

Those are encoded machine instructions.

We started with:

return add(2, 3);

Now we’re looking at hex.

result is long dead.

Except we’re still not done

Try:

clang -c main.c -o main.o

Now you have an object file.

It contains machine code and other information, but it may not be a complete program yet.

This gets easier to see when you use something you didn’t write.

Like:

printf("hello");

Your code calls printf.

But the implementation of printf isn’t sitting in your source file.

So your object file can basically say:

I need something called printf.

Somebody else deal with that.

That somebody is the linker.

It connects references like that to definitions supplied by other object files or libraries.

So this:

clang main.c -o main

looks like one thing.

It really isn’t.

Compile.

Assemble.

Link.

Done.

We type one command and all of it disappears behind the terminal prompt.

Then the operating system joins in

Even after the executable exists, the CPU doesn’t magically notice it sitting on disk.

You run:

./main

The operating system loads what the program needs into memory.

Sets up the process.

Deals with libraries.

Eventually execution reaches the machine code produced from our program.

And now the CPU finally gets involved.

Not with C.

Not with tokens.

Not with an AST.

Not with LLVM IR.

Not even with assembly text.

Machine instructions.

That’s what made it all the way down.

The source code is basically gone.

Its behavior isn’t.

You can actually watch your program disappear

This is probably more useful than me explaining another twenty paragraphs about compilers.

Take:

int add(int a, int b) {
    return a + b;
}

int main() {
    int result = add(2, 3);
    return result;
}

Then poke at it.

Preprocessed source:

clang -E main.c

AST:

clang -Xclang -ast-dump -fsyntax-only main.c

LLVM IR:

clang -S -emit-llvm main.c -o main.ll

Unoptimized assembly:

clang -O0 -S main.c -o main_O0.s

Optimized assembly:

clang -O2 -S main.c -o main_O2.s

Object file:

clang -c main.c -o main.o

Disassemble it:

objdump -d main.o

Or:

llvm-objdump -d main.o

Don’t try to understand every line.

Seriously.

Just keep finding your program.

Can you still see result?

What happened to add?

Can you find the addition?

What changes when you use -O2?

At some point you’ll be staring at a handful of instructions and realize almost none of the structure you wrote made it this far.

I think that’s the fun part.

Anyway

I used to think compilation was basically:

C → machine code

And honestly, most of the time that mental model is good enough.

You do not need to think about syntax trees every time you compile something.

But underneath that tiny arrow is this ridiculous chain where your program keeps becoming something else.

Text.

Tokens.

A tree.

Meaning attached to that tree.

IR.

Optimized IR.

Assembly.

Machine code.

An object file.

An executable.

And every step cares a little less about how you described the program.

The variable name can disappear.

The function can disappear.

The calculation itself can disappear.

The structure is negotiable.

Only what the program does has to survive.

You wrote C.

The CPU never understood C.

It never even tried.

A bunch of software stood in the middle and translated the whole thing, one representation at a time.

And then we type:

clang main.c -o main

wait half a second,

and complain that the build is slow.