Understanding Compiler Optimizations Through CPU Architecture, Part 1: Superscalar, OoO, and Store Buffer

Why Doesn't Compiler-Generated Code Look Like What You Wrote?

The code you write might look like this:

a = b + c + d + e

But after compiler optimization, the logic may look more like this:

a1 = b + c

a2 = d + e

a = a1 + a2

Originally, this could be written in one line. Why would the compiler split it into more steps? Wouldn’t more steps make performance worse?

The goal of this kind of optimization is to improve how efficiently the CPU executes instructions.

To understand why this helps, we first need to understand how a CPU executes instructions.

How Does a CPU Execute Instructions?

The simplest CPU model is made of a control unit, an ALU, registers, and memory.

The control unit reads and decodes instructions, and coordinates other hardware units. In modern CPUs, complex instructions may also be decoded into smaller micro-operations, usually called micro-ops or uops.

The ALU handles integer arithmetic and logic operations, such as addition, subtraction, multiplication, division, and bit operations.

Registers are the fastest storage locations inside the CPU. They hold operands and computation results.

Memory can be understood as data outside the CPU core or inside the cache hierarchy, such as L1 cache, L2 cache, and RAM.

From this, we can see that the control unit and the ALU are different hardware units. They are like two different workstations in a factory. Each can process its own part of the work.

Assume we have two instructions: A and B.

If the control unit and ALU were treated as one shared workstation, the flow might look like this:

cycle 1: decode A

cycle 2: execute A

cycle 3: decode B

cycle 4: execute B

It takes 4 cycles to finish. But if decode and execute are handled by separate workstations, the flow can become:

cycle 1: decode A

cycle 2: execute A, while decoding B

cycle 3: execute B

Now it finishes in 3 cycles. This is the core idea of a pipeline:

It does not make a single instruction complete faster, but it overlaps different stages of multiple instructions to improve overall throughput.

If we expand the model a little, a classic pipeline can be simplified into five stages:

Instruction Fetch → Decode → Execute → Memory → Write Back

Instruction Fetch: fetch instruction, using the program counter to read the instruction from instruction cache

Decode: decode the instruction and identify the opcode, source registers, and destination register

Execute: use the ALU or another execution unit to perform the operation

Memory: load or store data

Write Back: write the result back to a register

Each stage is handled by different hardware logic and has its own workstation. At this point, another question naturally appears:

If the CPU already has multiple hardware units, can we add more ALUs so more instructions can execute at the same time?

Can a CPU Add More Hardware Units to Improve Instruction Throughput?

Yes. This is the idea behind superscalar execution inside a single core.

But first, we need to separate two things: adding more ALUs inside one core is not the same as having a multi-core CPU.

Multi-core is thread-level parallelism. Different threads or processes can be scheduled onto different cores.

Multiple ALUs inside one core are for instruction-level parallelism. The CPU tries to execute multiple instructions from the same thread at the same time using different execution units, such as ALUs.

The precondition for instruction-level parallelism is that the instructions being executed in parallel must not depend on each other.

For example:

x = a + b

y = c + d

These two additions do not depend on each other. In theory, two ALUs can process them at the same time.

But consider this:

x = a + b

y = x + d

The second instruction needs the value of x produced by the first instruction. They cannot execute at the same time. This is a dependency.

Therefore, adding more ALUs only provides more execution resources. To make those resources useful, the CPU still needs to solve instruction dependency problems.

How Does a CPU Handle Instruction Dependencies?

Instruction dependencies can first be divided into false dependencies and true dependencies.

A false dependency means two instructions appear to use the same value, usually the same register, but they are not actually using the same logical value.

The first case is WAW, write after write.

first write: r1 = a + b

second write: r1 = c + d

Both instructions write to r1. They appear to write to the same variable. If they execute in parallel, the CPU may worry that the final value of r1 will not come from the second write.

But from the data perspective, these two writes can be treated as two different versions of r1. This is the problem register renaming solves.

Registers can be divided into architectural registers and physical registers.

An architectural register is a logical register number defined by the ISA, or Instruction Set Architecture. The machine instructions generated by the compiler refer to these registers.

But the CPU internally stores actual data in physical registers, such as p10, p11, and p12. Register renaming dynamically maps architectural registers to physical registers.

So the WAW example above can become:

r1 = a + b maps to physical register p10

r1 = c + d maps to physical register p11

Now the two writes go to different physical registers and do not overwrite each other. If a later instruction reads r1, it maps to p11 and reads the latest value.

The second kind of false dependency is WAR, write after read.

first read: r2 = r1 + a

second write: r1 = b + c

The first instruction needs to read the old r1. The second instruction writes a new r1. Without register renaming, the CPU has to worry that the second instruction writes r1 too early and destroys the old value needed by the first instruction.

Register renaming keeps the old physical register for the first read, while assigning a new physical register for the second write:

first read: r2 = old r1 in p11 + a

second write: new r1 goes to p12

This way, the second instruction does not destroy the old value required by the first instruction.

The other kind of dependency cannot be removed. This is a true dependency. Register renaming is still used to identify it clearly.

For example, RAW, read after write.

first write: r1 = a + b

second read: r2 = r1 + c

The second instruction truly needs the new r1 produced by the first instruction. Register renaming cannot remove this dependency. It can only record it clearly:

first write: p10 = a + b

second read: r2 = p10 + c

In other words, the second instruction must wait until the value in p10 is ready.

After dependencies are marked, the CPU also needs a scheduler to send decoded uops to different execution units, such as ALUs, memory load units, and memory store units. Therefore, a modern CPU pipeline is more detailed than the classic five-stage model. Conceptually, it looks like this:

instruction fetch → decode → rename → schedule → execute → memory → write back

Rename maps architectural registers to physical registers and builds dependency information. The schedule stage uses those dependencies to decide which uops can be issued to execution units.

But just because the CPU can do dependency tracking does not mean the compiler can ignore everything. The compiler should still try to generate an instruction stream that is easier to execute in parallel.

How Does the Compiler Optimize Code to Maximize Instruction Parallelism?

One core compiler optimization is to expose instruction-level parallelism. In other words, the compiler tries to make more independent work visible to the CPU.

The most typical example is loop unrolling.

Original program:

for (int i = 0; i < n; i++) {
  sum += a[i];
}

Conceptually, this might become:

i = 0
loop_start:
load tmp, a[i]
add sum, sum, tmp
add i, i, 1
cmp i, n
branch_if_less loop_start

There are two problems here.

First, each loop iteration only performs one sum += a[i], and each iteration depends on the previous value of sum. This creates a long dependency chain.

Second, each iteration processes only one element but still needs one branch. The branch itself has a cost.

The compiler can unroll the loop:

for (int i = 0; i < n; i += 4) {
  sum1 += a[i];
  sum2 += a[i + 1];
  sum3 += a[i + 2];
  sum4 += a[i + 3];
}

sum = sum1 + sum2 + sum3 + sum4

Now sum1, sum2, sum3, and sum4 are four relatively independent accumulation chains. The CPU can see more independent adds and loads, and the number of branches is reduced.

Another example is the expression reassociation from the beginning of the article.

Original:

a = b + c + d + e

If evaluated from left to right, it looks like this:

t1 = b + c
t2 = t1 + d
a = t2 + e

This is a three-level dependency chain.

But if it is rewritten as:

a1 = b + c
a2 = d + e
a = a1 + a2

a1 and a2 can be computed first in parallel. The dependency depth is reduced from three levels to two.

This is why optimized logic may look like it has more steps. The compiler is not only counting the number of instructions. It is looking at how CPU architecture can execute the instruction stream in parallel.

But this optimization has limits. For integers, addition can usually be reassociated like this. For floating-point addition, however, rounding error means the association order cannot always be changed freely.

Once more instruction-level parallelism is exposed, the CPU has a better chance of keeping multiple execution units busy. But there is another major issue that affects throughput: memory load and store.

Why Do Memory Load and Store Affect CPU Instruction Throughput?

Registers are fast, but memory is much slower. Even when the data is in L1 cache, latency is still higher than a typical ALU operation. If there is a cache miss and the CPU has to go to RAM, the wait is even longer.

Assume the instruction stream is:

instruction 1: load x
instruction 2: a = 1 + x
instruction 3: d = e + f

Instruction 2 needs x, so it depends on the load result from instruction 1. If load x has not completed, instruction 2 cannot issue. If the CPU uses in-order issue, then even though instruction 3 does not depend on the previous instructions, it still has to wait for instruction 2 to issue first. It cannot immediately issue to an idle ALU. The result is that instruction 3 also waits behind the memory load, and the pipeline stalls.

A better order is:

instruction 1: load x
instruction 2: d = e + f
instruction 3: a = 1 + x

The slow load is issued first. At the same time, instruction 2 can also be issued. After the ALU finishes d = e + f, the load may have returned, and the scheduler can issue instruction 3. The pipeline does not sit idle.

Compiler optimization can change instruction order, but this is static instruction scheduling. The compiler cannot always know runtime state, such as cache hits and misses, actual memory latency, or whether a dependency will really block execution.

Therefore, modern high-performance CPUs perform more aggressive scheduling at runtime. This is out-of-order issue.

How Does the CPU Schedule Stage Implement Out-of-Order Issue?

Out-of-order (OoO) issue does not mean the whole CPU is out of order from beginning to end.

More precisely, the CPU front end usually still fetches, decodes, and renames in program order, then places uops into a scheduling window. The scheduler then starts issuing instructions out of order to different execution units.

The scheduler checks each uop:

- Whether source operands are ready, for example already available in a register

- Whether the required execution unit is available

If the operands are ready and the execution unit is available, the uop can be issued. It does not necessarily have to wait for earlier uops to issue first.

For example:

instruction 1: load x
instruction 2: a = 1 + x
instruction 3: d = e + f

When load x has not returned yet, instruction 2 cannot execute. But instruction 3 does not depend on x, so the scheduler can issue instruction 3 first.

This is the core of OoO issue: from the uops already inside the scheduling window, pick the ready ones and send them to execution units first.

But this creates a new correctness problem: instructions can execute out of order, but the results observed by the program must not become out of order. Therefore, the CPU needs in-order commit.

Why Does Out-of-Order (OoO) Issue Need ROB In-Order Commit?

Consider this example:

int x = 0;

int *p = NULL;

int a = *p;

x = 10;

From the program’s semantics, int a = *p should execute first. Since p is NULL, this line raises an exception. The later x = 10 should not actually happen.

But in an OoO CPU, store 10 to x does not appear to depend on int a = *p, so it may execute earlier than the load.

If the store really becomes externally visible first, the exception would happen with an incorrect state: x has become 10. This is similar to a dirty read in a database transaction.

To solve this problem, the CPU needs a Reorder Buffer (ROB).

The ROB can be understood as a circular queue ordered by program order. Before instructions enter the OoO backend, they are assigned ROB entries in their original order. After that, they may execute out of order, but when they complete, they update their own ROB entry status.

Then, on each CPU cycle, the CPU checks from the ROB head:

- If the head instruction has completed and has no exception, commit it

- If the next instruction has also completed, keep committing

- If it reaches an instruction that has not completed or has an exception, stop

So the purpose of the ROB is not to prevent out-of-order execution. It is to make sure results become official in program order.

This is the basis of precise exceptions: when an exception happens, all earlier instructions appear to have completed, and all later instructions appear not to have happened.

But store has a special problem.

Can ROB In-Order Commit Prevent Store from Becoming Visible to Other Threads Too Early?

Store is different from a normal register write. A normal ALU instruction first writes its result to a physical register. That result is internal state inside the CPU core. But store writes to memory. If a store writes to memory immediately after execution, another thread may see the value before the store commits. A store that has not committed yet is a speculative store.

Return to the previous example:

int x = 0;

int *p = NULL;

int a = *p;

x = 10;

If x = 10 is issued out of order and really writes to memory first, then even if the CPU later discovers that int a = *p should raise an exception, x may already have been seen by another thread. This breaks precise exception semantics.

Therefore, a speculative store cannot write directly to memory at execute time. A speculative store is usually split into several pieces:

1. Compute the store address

2. Prepare the store data

3. Put the address and data into a store buffer or store queue

4. After the store passes ROB commit, allow it to drain into the cache coherence system

This lets the store complete its computation early without blocking the pipeline. But before it is allowed to officially take effect, it does not pollute memory.

Therefore, the division of responsibility between the ROB and the store buffer is:

The ROB decides when this store commits.

The store buffer holds stores that are already prepared but not yet externally visible.

However, after a store drains into the cache coherence system, cross-core visibility involves mechanisms such as cache line ownership, invalidation, and data propagation. These are usually handled asynchronously.

The order observed by other threads does not necessarily match the original program order exactly. Which ordering guarantees actually hold depends on the hardware memory model. For example, x86 and ARM provide different ordering guarantees.

What Problem Happens If Other Threads Cannot Observe the Correct Data Order?

The store buffer is a private write queue for each core. It solves two problems.

First, a store does not need to wait for cache coherence to complete before the CPU continues running. The store can enter the buffer first and drain into the cache hierarchy later.

Second, during OoO issue, a store does not pollute memory too early. Only after ROB commit is the store allowed to become externally visible.

If a later load on the same core wants to read the value that was just stored, it can use store-to-load forwarding to read the new value from its own store buffer.

For example:

x = 1
r = x

Even if x = 1 is still in the store buffer, r = x can still read 1.

But other cores cannot see your store buffer. They can only observe the write after the store has committed through the ROB and drained into cache coherence so the data becomes synchronized.

When the hardware memory model allows the drain order and cache coherence synchronization order to differ, a multithreaded program can run into this situation:

Thread A:

a = 10
b = 10

Thread B:

if (b == 10) {
  print(a)
}

From Thread A’s own perspective, the order is fine. But Thread B may see b = 10 first, while print(a) still prints the old value, such as 0.

Therefore, we need atomic operations to define which orders cannot be broken.

How Does Atomic Solve Multithreaded Data Synchronization?

For example:

Thread A:

a = 10
atomic.Store release b = 10

Thread B:

if (atomic.Load acquire b == 10) {
  print(a)
}

A release store is like placing a memory fence at a certain line of code. Stores before this fence must become externally visible before the store on this line. A simple way to understand it is that it restricts the order of writes to memory: store 10 to a must be written first, and only then can store 10 to b be written.

More precisely, atomic operations restrict the synchronization behavior of different hardware memory models. Synchronization does not always happen through RAM. Through the cache coherence system, a core may also read data from another core’s L1 cache. The purpose of atomic is to tell the underlying hardware system the required visibility order, or ordering boundary.

At this point, you may wonder: if atomic store already restricts write ordering, why does Thread B still need atomic.Load?

That part is no longer about the store buffer. It is related to cache coherence and the invalidation queue. For a full explanation, see my other article on cache coherence and atomic:

Summary

Starting from the CPU pipeline and moving through superscalar execution, register renaming, OoO issue, ROB, and the store buffer, we can see that compiler optimization is not simply about making code shorter.

What the compiler really wants is to generate an instruction stream that fits the CPU better: independent instructions should be easier to see, the pipeline should stall less often, and the OoO scheduler should have more ready work to choose from.

But every layer of freedom introduced by the CPU for performance also creates new correctness problems. OoO needs the ROB to keep commit ordered. The store buffer needs memory ordering to constrain cross-core visibility. In the next article, we can look at another problem that makes the pipeline harder to keep full: branch prediction.