What a Compiler Does

A compiler is the program that translates source code written by people, such as C, into the machine instructions a processor runs. Almost every instruction a processor executes was chosen by a compiler, so the compiler decides a large part of how fast a program runs, how much memory it needs and how much energy it uses. This article opens up GCC, a widely used compiler, and follows one real loop through its three parts: the front end that reads the C, the optimizer that improves it, and the back end that writes the machine instructions.

16 min read | Beginner

What You'll Learn

• Describe the three parts of a compiler (front end, optimizer and back end) and what passes between them
• Read a compiler's intermediate representation and recognize what the optimizer changed
• Explain instruction selection, register allocation and instruction scheduling with real listings
• Say which part of the compiler changes when the target processor changes

From Source Code to Machine Code

A processor understands only machine instructions: 32-bit numbers that each ask for one small step, such as "add two registers" or "load a word from memory". People do not write programs that way. They write in a high-level language such as C, where one line like s += a[i]; means "add element i of the array a to s" without saying which registers to use, where the array is, or how to compute the address of element i. The compiler fills in all of that.

The compiler in this article is GCC 13.2, in the version called riscv64-unknown-elf-gcc. The name says what it produces: code for RISC-V, with no operating system underneath ("unknown" vendor, programs in the standard ELF file format). It runs on an ordinary x86 computer but produces code for a different processor, which makes it a cross compiler. Two options pick the exact target: -march=rv32i says which instructions exist (the 32-bit base set only, with no multiply instruction), and -mabi=ilp32 says how data types and function calls are laid out. What an ISA Defines measures what -march changes, and The Calling Convention and ABI explains the ABI.

Compiling is only the first step of building a program. The compiler turns each C file into assembly code, an assembler turns that into an object file, and a linker joins the object files into one program. Assembling, Linking and Loading covers those later steps; this article stays inside the compiler.

The Three Parts of a Compiler

Every modern compiler is organized in three parts, joined by a common internal language:

• The front end reads the source code, checks that it is valid C and turns it into the compiler's internal form. It knows everything about C and nothing about RISC-V.
• The optimizer (also called the middle end) rewrites that internal form into an equivalent one that will run faster or take less space. Most of its work is independent of both the language and the processor.
• The back end turns the internal form into instructions for one particular processor: here, RV32I assembly code. It knows everything about RISC-V and nothing about C.

The internal form is called the intermediate representation, or IR. It is a simple, regular language designed to be easy for programs to analyze, not for people to write. The three-part design exists because of a multiplication. A compiler family that supports 5 languages and 20 processors would need 100 separate translators if each pair were built directly; with a shared IR it needs 5 front ends and 20 back ends, and every improvement to the optimizer helps all 100 combinations at once. GCC supports C, C++, Fortran, Ada, Go and others on dozens of processor families this way, and the LLVM project behind the Clang compiler follows the same plan.

The picture below shows a loop from a small C program, sum.c, which adds up 1,024 array elements, at four points on its way through GCC. Every box is copied from a real file: GCC writes its IR to a text file when given options such as -fdump-tree-gimple.

The Front End

The front end works in a few steps. First the preprocessor handles the lines that start with #: it copies in the header files named by #include and replaces macros such as N by their values. The 14-line sum.c becomes a 32-line file after preprocessing, because a header with its type names and a helper function is pasted in.

Next the lexer splits the text into tokens (names, numbers, operators, punctuation) and the parser arranges them into a tree that follows the grammar of C: a for statement containing an assignment containing an addition. Then comes semantic analysis, where the compiler looks up every name, works out every type and checks that the program makes sense: that a is an array, that s is an unsigned 32-bit integer, that a function is called with the right number of arguments. Almost all the error messages a programmer sees come from this step.

Finally the front end lowers the tree into GIMPLE, the first IR of GCC. GIMPLE is a three-address code: every statement does at most one operation, with at most two inputs and one output, and new temporary names such as _3 hold the intermediate values. The single C statement s += a[i]; becomes two GIMPLE statements, _3 = a[i]; and s = s + _3;. The for loop becomes plain labels and goto statements, with the test if (i <= 1023): the front end has already rewritten i < N as i <= 1023, because for unsigned numbers the two mean the same thing. At this stage nothing has been optimized; the IR still does exactly what the C says, in the same order.

The Optimizer

The optimizer is a long series of passes. Each pass reads the whole function in IR form, looks for one kind of improvement and rewrites the IR. The number in each dump file name is the position of the pass in that series: the GIMPLE above is dump 006, the optimized version is dump 254. Every pass must keep the meaning of the program exactly the same; the only thing allowed to change is the cost.

Comparing the two dumps of the loop shows what the passes achieved. The counter i is gone. In its place is a pointer (ivtmp.10) that starts at the address of a and moves forward by 4 bytes, one element, on every pass, and the loop now ends when the pointer reaches _32, which the optimizer computed once before the loop as the address of a plus 4,096 bytes. The address calculation "a plus i times 4" that the original code implies on every element has disappeared. Replacing a multiplication inside a loop by a running addition like this is strength reduction; Arithmetic, Logic and Immediates shows another example of it.

The optimized dump also gives every value a version number: s_18 is the total at the top of the loop and s_10 the new total after the addition. This is static single assignment form (SSA): each name is assigned exactly once, and where two paths join, a PHI statement picks the right version (the total is 0 on entry and s_10 after each pass). SSA makes it easy for a pass to see where each value comes from, which is why almost every modern compiler uses it.

Beyond strength reduction, the most common optimizations are:

• Constant folding: computing at compile time what can be computed then, such as 4 * 1024.
• Dead code elimination: removing code whose result is never used.
• Common subexpression elimination: computing a repeated expression once and reusing the result.
• Loop-invariant code motion: moving work that gives the same result on every pass of a loop, such as the end address _32, out of the loop.
• Inlining: copying the body of a small function into its caller instead of calling it.
• Loop unrolling: repeating the loop body several times per pass so that fewer branches run.

How many of these a compiler runs is up to the user. Compiler Optimization Levels explains the settings, and works through inlining and unrolling step by step.

The Back End

The back end turns the optimized IR into instructions for the target processor. It has three main jobs, and each one leaves a visible mark in the compiled code.

Instruction Selection

Instruction selection picks the machine instructions for each IR operation. Often the match is direct: the load _3 = MEM[...] becomes lw, the addition becomes add, the pointer step becomes addi with the constant 4, and the loop test becomes bne, a branch if not equal. Sometimes one IR operation needs several instructions, such as a 32-bit constant built from lui and addi, and sometimes several IR operations fit into one instruction, such as an address addition folded into the offset of a load.

When the target has no instruction for an operation, the back end calls a library routine instead. RV32I has no multiply instruction, so every A[i][k] * B[k][j] in a matrix program becomes a call to __mulsi3, a small routine from GCC's support library that multiplies by shifting and adding. The Datapath counts what those calls cost.

Register Allocation

The IR has no limit on the number of values; the processor has 31 usable registers. Register allocation decides which value lives in which register at each point, and which values must be kept in memory instead. It is the single most important job of the back end, because a value in a register costs nothing to read, while a value in memory costs a load each time. Registers and the Register File compares one loop with and without allocation.

GCC's option -O0 turns optimization off, and -O2 is the usual setting for finished software. At -O0, GCC gives every variable a home on the stack and loads it before each use and stores it after each change. That is why unoptimized code is so heavy. In one test, an unoptimized checksum program made more than fifty times as many loads as the optimized build of the same program, which did exactly the same job. Almost all of those loads fetched values that could have stayed in a register.

Instruction Scheduling

Instruction scheduling chooses the order of the instructions, within the freedom the data dependences leave. Order matters because of the pipeline, the processor's habit of working on several instructions at once. On many processors, a value loaded from memory is not ready for the very next instruction, and if that instruction needs it, the processor must wait. This wait is a load-use stall, introduced in Loads, Stores and Addressing.

Two builds of the same loop show the effect clearly. They execute exactly the same instructions, but in a different order:

-O1 build                               -O2 build
44:  lw   a5,0(a4)                      44:  lw   a5,0(a4)
48:  add  a0,a0,a5   # needs a5 now     48:  addi a4,a4,4     # independent work
4c:  addi a4,a4,4                       4c:  add  a0,a0,a5    # a5 is ready
50:  bne  a4,a2,44                      50:  bne  a4,a2,44

The left loop uses the loaded value immediately, so the processor waits once per element. The right loop puts an unrelated instruction between the load and its use, so nothing waits. In one test this made the whole program about 8 percent faster without removing a single instruction. The gain depends on the processor: a design with a longer wait gains more from this reordering, and a design that can get around the wait gains less.

Why Architects Care About the Compiler

For a computer architect the compiler is part of the machine. Instruction sets are designed around what compilers can use: RISC-V has many general registers and simple, regular instructions because register allocators and instruction selectors work best with those, and it has no instructions that a compiler would rarely be able to generate. Microarchitecture features are judged on compiled code: the value of a branch predictor depends on how many branches the compiler leaves in, and the value of a faster load path depends on how well the scheduler already hides load latency.

Compiler Optimization Levels shows how much the compiler's settings can change the result. Assembling, Linking and Loading follows the assembly code that the back end writes out through the rest of the build, until it becomes the words in the processor's memory.

Common Mistakes