15.2 Branch Prediction, Superscalar, and Out-of-Order Execution

The five-stage pipeline of a CPU core can now overlap multiple instructions, but if it encounters a branch, a cache miss, or a long-latency division, the entire pipeline stalls. Modern high-performance CPUs guess the next control flow, fetch multiple instructions in parallel, and let operations that already have operands occupy execution units first; finally, they submit visible results in program order.

This isn't about instructions running wildly unchecked in the cockpit. Branch prediction, superscalar execution, out-of-order execution, and in-order retirement each guard their own boundary:

• Branch prediction determines where the next instruction is fetched;
• Superscalar means multiple operations can be processed per cycle; Out-of-order execution allows subsequent independent operations to proceed past operations that haven't yet become ready;
• Ordered retirement maintains precise exceptions and architecture-visible order.

1. Branch prediction doesn't just guess "whether to jump or not"

The front-end for withdrawal needs to respond early:

1. Is the current instruction a branch?
2. Will conditional branches jump?
3. If jumping, what is the target address?
4. If a function returns, to which calling point does it return?

Different structures help answer these questions:

• direction predictor predicts taken/not taken;
• branch target buffer (BTB) caches the target location of branches;
• Return Address Stack (RAS) predicts return addresses for paired call/return sequences;
• An indirect branch predictor handles the case where a single location might jump to multiple targets.

Getting the direction right but the target not ready can still cause bubbles in the frontend. A BTB hit isn't a guarantee of zero-cost branching; instruction fetch bandwidth, cache, alignment, and backend resources all affect the outcome.

2. Two Saturated Counters

A minimum dynamic predictor can save two states for a branch:

0 strongly not taken
1 weakly not taken
2 weakly taken
3 strongly taken

State 0/1 predicts no jump, 2/3 predicts jump. Increment if actual jump occurs, decrement if no jump, with saturation at 0 and 3. A single accidental reversal won't immediately flip the "strong" prediction to the opposite direction.

Below, we'll use code to observe different patterns:

class TwoBitPredictor:
    def __init__(self):
        self.counter = 1  # weakly not taken

    def predict(self):
        return self.counter >= 2

    def update(self, taken):
        if taken:
            self.counter = min(3, self.counter + 1)
        else:
            self.counter = max(0, self.counter - 1)


def mispredictions(pattern):
    predictor = TwoBitPredictor()
    misses = 0
    for outcome in pattern:
        if predictor.predict() != outcome:
            misses += 1
        predictor.update(outcome)
    return misses


mostly_taken = [True] * 100
alternating = [True, False] * 50
loop_exit = ([True] * 9 + [False]) * 10

assert mispredictions(mostly_taken) == 1
assert mispredictions(alternating) == 100
print(mispredictions(loop_exit))

This is just a branch and a counter. A real processor uses branch address indexing to look up many prediction entries and combines local or global history, path information, and multiple predictors. The fact that a counter-based scheme fails on alternating patterns doesn't mean all modern predictors will be wrong 100 times.

3. When a prediction fails, it's the speculative work that gets rolled back

After predicting a branch, the CPU can fetch, decode, and even execute instructions along the guessed path. Once the branch condition is resolved:

• Prediction correct; related results still pending submission;
• Prediction error: mispredicted young operations are squashed, the rename map and frontend recover from the checkpoint, then fetch resumes from the correct PC.

The error path cannot formally commit architectural results from registers or memory. However, it might have altered microarchitectural state such as cache, TLB, predictor, and execution port occupancy. Spectre attacks exploit the gap between "architectural results are rolled back, yet microarchitectural traces remain observable."

Thus, branch prediction is both a performance mechanism and part of a security boundary. Avoiding the use of secrets to influence observable indices, addresses, or control flow requires specific mitigations provided by languages, compilers, and platforms, rather than disabling one prediction mechanism alone.

4. Superscalar: One cycle processes more than one instruction

Superscalar processors configure multiple parallel pathways in both the front-end and back-end. For example, in one cycle, they may decode multiple operations and route them to integer ALUs, load/store units, and vector units.

fetch/decode width
        ↓
rename and allocate
        ↓
issue queues
   ┌────┼────────┐
 integer   load/store   vector

“A width of 4” doesn’t mean IPC is always 4. Throughput is limited by branches, dependencies, cache misses, execution ports, queue depth, and front-end supply. Some instructions may break down into multiple internal operations, so ISA instruction count does not always match internal work count.

Out-of-order execution can issue multiple adjacent and independent instructions in the same cycle, while out-of-order execution allows selecting ready work from a larger window. The two can be combined, and they are not the same thing.

5. Register Renaming to Eliminate False Dependencies

The program has a limited number of architectural register names, and they are reused repeatedly in loops:

mul r1, r2, r3
add r4, r1, r5
sub r1, r6, r7

r1 is a RAW true dependency from the first instruction and must wait. The third instruction writes r1, creating a WAW name conflict, but its computation does not depend on the result of the first instruction.

The rename stage maps two r1 writes to different physical registers:

mul writes physical P20
add reads  physical P20
sub writes physical P31

This sub can execute early while preserving the semantic meaning of "the last write to r1" in program order. WAR can be eliminated via renaming, but RAW cannot, as it represents actual data flow.

Resource renaming is limited. When physical registers, the ROB, or the load/store queue are exhausted, the frontend stalls until the old operations retire and release the resources.

6. Out-of-order scheduling: Do the ready ones first

After renaming, the operation enters the scheduling structure, waiting for source operands and execution units:

older load: cache miss ───────────────┐
dependent add: waits for load        │
independent multiply: ready → execute│
independent branch: ready → execute  │
                                      ▼
                              results complete

The subsequent independent operations can bypass miss and utilize the originally idle units. This can only hide a limited amount of delay:

• The instruction window must be large enough to accommodate sufficient follow-up work;
• Future work must be genuinely independent;
• The execution unit and memory request slots should have headroom;
• Branch prediction must continue to provide the correct path;
• The oldest pause might eventually block retirement.

Pointer chasing often creates a dependency chain of the form load → address → next load, making it hard to parallelize. In contrast, multiple independent array streams are more likely to enable memory-level parallelism.

7. Memory ordering is harder to manage than registers

The CPU could figure out register names from instruction encoding early on, but might not know until after address calculation:

store [p] = 1
load  r = [q]

Are p and q the same? The load/store queue tracks in-flight memory accesses, performs memory disambiguation, and allows loads to bypass older stores when safety is proven or predicted.

If an address conflict is discovered later, incorrect load results and dependent operations must be replayed. Stores typically cannot irrevocably update the cache's architectural visibility state before instruction retirement, otherwise exceptions or mispredictions would be hard to recover from.

These internal rules aren't the same as a language thread memory model. When one thread on another core can observe a write also involves cache coherence, memory ordering, and synchronization operations, which will be discussed further in Chapter 16.

The engine can be completed early, but the ledger must be posted in order

The independent operation can be completed in the execution unit first, but the results cannot be arbitrarily written into architecture state. The reorder buffer is like a ledger ordered by program sequence: results from later instructions become visible only after all preceding instructions have safely committed.

The Reorder Buffer (ROB) tracks operations in program order. Execution can complete out of order, but retirement/commit proceeds from the oldest operation onward.

program order:  A  B  C  D
finish order:   C  A  D  B
retire order:   A  B  C  D

If a page fault occurs for B:

• A can represent something that has already been completed;
• B reports an anomaly;
• C, D even if calculated, can't leave any visible architectural results;
• The saved B corresponds to a state sufficient for the system to handle exceptions.

This is at the heart of the precise exception mechanism. The specific fields of ROB, result storage locations, and free-list design vary with microarchitecture and cannot be represented by a single textbook diagram as a universal CPU circuit diagram.

9. The Actual Optimization Order of Branches and Data

Don't immediately add __builtin_expect when you see if. A more reliable order is:

1. Verify hotspots and input distribution;
2. Check the optimized assembly to confirm that branches are still present;
3. Check whether the compiler has already used conditional moves or vectorization;
4. Measure branch, branch miss, cycles, instructions, and cache events;
5. After modifying the data layout or algorithm, remeasure correctness and performance;
6. Verify on different target CPUs.

Compiler hints mainly affect code layout and optimization decisions, and don't directly insert commands into hardware predictors. Incorrect hints could lead to suboptimal layout of common execution paths.

Linux perf can access certain hardware counters, but event names, permissions, and availability vary by CPU and environment. First use perf list to check the local system, then decide on the event combinations; virtual machines or containers may expose only limited counters.

10. A complete analysis example

int classify_and_sum(const int *values, int length) {
    int sum = 0;
    for (int i = 0; i < length; ++i) {
        int value = values[i];
        if (value >= 0) {
            sum += value;
        } else {
            sum -= value;
        }
    }
    return sum;
}

Analysis should propose rather than assume:

• Does the compiler keep the branch, or does it turn it into conditional moves/absolute value/vector instructions?
• How much parallelism is limited by the cyclic dependency of sum?
• Is the data sequential, and can it hit the cache and trigger prefetching?
• Can signed int overflow cause undefined behavior in the source program?
• Has there been a stable historical distribution of positive and negative outcomes, and can a predictor learn from it?

If you want to establish a baseline, first define the correct semantics using data types that won't overflow or a wider type, then prevent the compiler from eliminating the result. Otherwise, you might encounter undefined behavior or empty loops.

11. Common Misconceptions

"Out-of-order execution changes the order of program results." Internal execution can reorder, but architectural state typically retires in order and is constrained by ISA memory-ordering rules.

"ROB ensures all threads see a consistent order." ROB primarily addresses retirement ordering and exceptions within a single core; cross-core visibility requires cache coherence and memory models.

"Branch prediction only affects control flow." False paths also consume cache, TLB, and execution resources, and introduce side-channel risks.

"Branchless is always faster." A branchless version might execute more instructions, introduce dependencies, or hinder vectorization, measures are required.

"High IPC means the program runs faster." IPC can increase due to more unnecessary instructions. Ultimately, it must be combined with total instructions, cycles, time, and business throughput.

12. Summary

Modern CPUs expand the parallelism window through prediction and dynamic scheduling:

• The direction predictor, BTB, and RAS work together to maintain instruction fetch;
• Superscalar architecture enables multiple operations to be processed per clock cycle;
• Eliminates WAR/WAW false dependencies via register renaming;
• issue queue selects operations that are ready;
• The load/store queue handles memory dependencies that haven't been fully resolved;
• ROB gets out of order to complete the final retirement in program order;
• A misprediction will roll back the architectural result but may leave microarchitectural traces.

The next chapter moves on to C and Memory Model, clearly separating speculative execution within a single core from the ordering that multithreaded programs may observe.