15.2 Branch Prediction, Superscalar, and Out-of-Order Execution
Five-stage pipelines can overlap multiple instructions, but a branch, cache miss, or long-latency division may still stall the pipeline. Modern high-performance CPUs predict the next control flow, fetch multiple instructions in parallel, and let operations with ready operands use execution units first; they then commit visible results in program order.
This does not mean instructions run without rules. Branch prediction, superscalar execution, out-of-order execution, and in-order retirement each have a separate 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 fetch frontend needs to answer four questions early:
- Is the current instruction a branch?
- Will conditional branches jump?
- If jumping, what is the target address?
- 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-Bit Saturating Counter
One simple dynamic predictor can store a two-bit state for each branch:
0 strongly not taken
1 weakly not taken
2 weakly taken
3 strongly takenState 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 type(taken) is not bool:
raise ValueError("outcome must be bool")
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
assert mispredictions(loop_exit) == 11
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:
- Correct prediction: results continue toward retirement;
- Prediction error: mispredicted young operations are squashed, the rename map and frontend recover from the checkpoint, then fetch resumes from the correct PC.
The mispredicted path cannot commit its register or ordinary-memory results. 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
A superscalar core provides parallel front-end and execution capacity. It may decode several operations in a cycle and send ready work to integer, load/store, 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.
An in-order superscalar design can issue multiple adjacent 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 reuses them in loops. The following is generic three-address pseudo-assembly:
mul r1, r2, r3
add r4, r1, r5
sub r1, r6, r7The second instruction must read the first instruction's r1 result, a true RAW dependency. 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 P31This 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.
Renaming resources are finite. 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 completeThe 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;
- Later work must be 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.
8. Execution Can Finish Early, but Results Commit in Order
Independent operations may finish early, but cannot update architectural state arbitrarily. The ROB keeps the books in program order: a later result waits until older instructions can retire safely.
The Reorder Buffer (ROB) tracks operations in program order. Execution can complete out of order, but retirement/commit proceeds from the oldest operation onward. A retired store may still wait in a store buffer before other cores observe it; local retirement is not a single visibility timeline shared by all threads.
program order: A B C D
finish order: C A D B
retire order: A B C DIf a page fault occurs for B:
- A appears completed;
- B reports the exception;
- 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:
- Verify hotspots and input distribution;
- Check the optimized assembly to confirm that branches are still present;
- Check whether the compiler has already used conditional moves or vectorization;
- Measure branch, branch miss, cycles, instructions, and cache events;
- After modifying the data layout or algorithm, remeasure correctness and performance;
- 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
This intentionally flawed example retains signed-int overflow. Diagnose correctness before discussing its branches:
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
intoverflow 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?
A single INT_MIN can overflow sum -= value, and several ordinary positive values can overflow the total. With int32_t input, convert to int64_t before negating to obtain the magnitude. Even uint64_t accumulation should check magnitude > UINT64_MAX - sum: wider is not unlimited. Establish input bounds and an overflow policy before benchmarking, and make sure the result is used. 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; measure it.
"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;
- The ROB retires operations in program order despite out-of-order completion;
- 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.