IM Engineer Study Notes
← Back to list
Computing & Embedded
#분기예측#투기적실행#비순차실행#Spectre#파이프라인
Last updated · 2026-10-06

Speculative Execution & Branch Prediction

1. Overview

A. Definition

Branch prediction is a hardware technique that guesses in advance the direction of a conditional branch before its outcome (true/false) and target address are resolved, so that subsequent instructions can be supplied without stalling, while speculative execution is the core out-of-order mechanism that executes not-yet-resolved instructions ahead of time on the basis of that guess, committing the results if the guess is correct and rolling back (squashing) if it is wrong.

Branch prediction and speculative execution share a single purpose: "an investment to keep the pipeline from draining." Modern processors raise throughput with deep pipelines that split each instruction into stages such as fetch, decode, execute, and write-back, yet a conditional branch only reveals "which address to fetch next" once it reaches the execute stage. If the pipeline waited for every branch outcome without prediction, its front end would sit empty (bubble) for several cycles and performance would collapse. Branch prediction fills that gap with a guess, and speculative execution actually pushes the instructions on the guessed path into the compute resources, capturing the gain "if the guess is right" ahead of time.

A concept that must be distinguished here is prediction versus speculation. Prediction is the inferential act of "guessing which way it will go," while speculation is the execution model of "running ahead on the premise that the inference may be wrong, while keeping the ability to undo it." Thus speculative execution is a higher-level concept applied in common to many kinds of guessing—not only branch prediction but memory disambiguation, value prediction, and more—and the most important pillar supporting its accuracy is branch prediction. In a professional-engineer answer it is clearest to frame the two as the relationship between "a guessing brain (the branch predictor)" and "a body that moves on the guess but can be cancelled (the speculative execution engine)."

The accuracy of speculative execution rests on its misprediction recovery capability. If, when a guess is wrong, the results of speculatively executed instructions leak into the architectural state (registers and memory), the program malfunctions; so the hardware isolates the "pre-commit state" with structures such as the reorder buffer (ROB), register renaming, and checkpoints, and discards it wholesale upon misprediction. Because this "speculate-and-discard" design became the root of the 2018 Spectre and Meltdown family of vulnerabilities, this topic is a representative case where performance and security intersect.

Summarized in one sentence, the way branch prediction and speculative execution contribute to performance is "a virtuous cycle that never stalls the pipeline, and because it never stalls, keeps more instructions in flight at once." But this virtuous cycle holds only "when the guess is right often enough." As prediction accuracy drops, work pulled in speculatively is discarded in bulk, consuming only power in a vicious cycle, and the deeper the pipeline, the more that loss is amplified. Speculation is therefore not a free lunch but a credit transaction premised on the collateral of "accurate prediction," and what underwrites the quality of that collateral is a sophisticated branch predictor.

B. Background and Necessity

The need for branch prediction has grown exponentially as pipelines deepened. In the early 5-stage pipeline the branch delay was only 1–2 cycles, but as frequency competition intensified and pipelines deepened to 10–20 stages or more, a single misprediction led to tens of cycles of waste. In a typical program a branch appears roughly every 5–7 instructions, so even a small drop in prediction accuracy breaks overall performance. For instance, in a 15-stage pipeline with a 15-cycle misprediction penalty where branches make up 20% of all instructions, merely raising prediction accuracy from 90% to 95% changes perceived performance substantially. This is why CPU designers have invested a large share of their transistor budget in branch predictors.

Speculative execution is also a precondition for extracting instruction-level parallelism (ILP). An out-of-order processor executes instructions without data dependencies early, in whatever order, so the execution units never idle; but if it stalls at a branch, it cannot exploit any of the parallelism beyond it. Speculative execution pulls in and executes instructions even "beyond" the branch, enabling a wide instruction window that keeps tens to hundreds of instructions "in flight." In other words, the key driver by which today's high-performance cores raise IPC (instructions per cycle) is aggressive speculation operating on top of accurate branch prediction.

This necessity is directly tied to real-world performance across servers, mobile, and HPC alike. Branch-heavy query processing in database engines, instruction dispatch in interpreters and JITs, and branch-intensive loops in game engines are all sensitive to branch-prediction accuracy. Conversely, from a security standpoint, it was found that secret data can leak through the traces that a "speculatively executed and then discarded instruction" leaves in microarchitectural state such as the cache—exposing the paradox that speculation for performance becomes an attack surface. This topic is therefore a core professional-engineer area requiring simultaneous understanding of architectural performance and system security.

Historically, branch prediction and speculative execution became mainstream alongside the commercialization of superscalar, out-of-order processors in the 1990s (Intel P6, MIPS R10000, and others). Designers of the era made "keeping the execution units busy by any means" their supreme goal, and the answer was speculation that runs ahead beyond the branch. Over the following two-plus decades, predictors steadily grew more refined—from 2-bit counters to correlating predictors, tournament designs, and TAGE/perceptron—and the instruction window widened from tens to hundreds of instructions. Speculation is thus not the technique of one particular generation but a continuous design philosophy that has underpinned the performance of modern general-purpose CPUs, and precisely because it is so deeply rooted, it became a structure that could not easily be removed even after Spectre.

2. Structure of the Speculative Execution Pipeline

The branch predictor and the speculative execution engine cooperate, split into "prediction" at the fetch stage and "verification/recovery" at the execute and commit stages, as shown below.

flowchart LR
  PC["Program Counter(PC)"] --> FETCH["Instruction Fetch(Fetch)"]
  BP["Branch Predictor(BHT/BTB/RAS)"] -->|"predicted direction·target"| FETCH
  FETCH --> DEC["Decode·Rename(Decode/Rename)"]
  DEC --> ROB["enqueue into Reorder Buffer(ROB)"]
  ROB --> EXEC["Out-of-Order Execution(Out-of-Order)"]
  EXEC -->|"actual branch outcome"| CHK{"prediction hit?"}
  CHK -->|"Yes(Hit)"| COMMIT["in-order Commit(Commit)"]
  CHK -->|"No(Miss)"| FLUSH["pipeline flush·state recovery"]
  FLUSH -->|"re-fetch from correct PC"| PC
  COMMIT -->|"update predictor(learn)"| BP
  FLUSH -->|"update predictor(learn)"| BP
  style BP fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
  style CHK fill:#fef7e0,stroke:#f9ab00,stroke-width:2px

The flow can be organized at a glance as follows. Branch prediction runs on four beats—"guess, execute, verify, recover"—with each stage meshing asynchronously at a different pipeline location.

sequenceDiagram
  participant F as Fetch Stage(Fetch)
  participant P as Branch Predictor(Predictor)
  participant E as Execution Unit(Execute)
  participant R as Reorder Buffer(ROB)
  F->>P: direction·target of this PC's branch?
  P-->>F: prediction(taken, target address)
  F->>R: enqueue speculative instructions in order
  R->>E: execute ready instructions out of order
  E-->>R: report actual branch outcome
  alt prediction hit
    R->>R: commit in order(commit)
    R-->>P: train predictor with the outcome
  else misprediction
    R->>R: squash everything after the branch(squash)
    R-->>F: request re-fetch from correct PC
    R-->>P: correct the predictor with the wrong outcome
  end

The key in the two figures above is the temporal separation of prediction and verification. The fetch stage trusts the direction/target supplied by the branch predictor and feeds instructions without pause, while the actual branch outcome is settled much later at the execute stage. In between, the fetched and speculatively executed instructions are loaded into the ROB in order and marked "not yet committed." If the prediction is right, the branch and the instructions after it commit into architectural state one by one in program order; if wrong, all ROB entries after that branch are invalidated and re-fetching begins at the correct address. Whether commit or flush, the outcome is fed back to the predictor and used for learning that raises the accuracy of the next prediction.

A. Components of the Branch Predictor

Branch prediction is complete only when it gets both the "direction (taken/not-taken)" and the "target address" right. The representative structure handling direction prediction is the branch history table (BHT). In its most basic form it places a 2-bit saturating counter at each index hashed from a branch address, managing four states: strongly-taken, weakly-taken, weakly-not-taken, and strongly-not-taken. A 1-bit predictor has the weakness of being wrong twice in a row at the start and end of a loop, whereas 2 bits add the inertia of "not flipping direction immediately after one miss," yielding around 95% accuracy on repetitive patterns. This tiny state machine is the classic starting point of branch prediction.

Looking a little deeper at how the 2-bit saturating counter works makes its design intent clear. The states are 00 (strong not-taken), 01 (weak not-taken), 10 (weak taken), and 11 (strong taken); the counter increments by 1 when the branch is taken and decrements by 1 when not-taken, saturating at both ends. The prediction is decided by the most significant bit (taken if 10 or 11). The crux of this structure is that even when an exceptional outcome occurs once in a "strong" state, it does not flip the predicted direction immediately but only moves to a "weak" state. Thanks to this, an "exception within the rule"—such as the single not-taken at the end of a loop that iterates 100 times—does not spoil the prediction when the loop is entered next. It can be said to be a design that packs the statistical intuition "trust the recent tendency but be tolerant of a single anomaly" into a very small state machine.

The structure handling target prediction is the branch target buffer (BTB). If the BHT answers "whether to go," the BTB stores "where it goes if taken," like a cache. When the BTB is looked up by PC at the fetch stage and hits, the target address is obtained immediately so that address can be fetched the next cycle—without even waiting to decode the branch instruction. Especially in code with many indirect branches, such as function calls/returns, the BTB hit rate governs performance. Function return addresses are predicted almost perfectly by a separate return address stack (RAS), exploiting the fact that calls and returns nest like a stack: push the return address on a call and pop it on a return to supply the target, which is highly accurate except for deep recursion.

The decisive idea that pushes up direction-prediction accuracy is the correlating, two-level predictor. Starting from the observation that one branch's outcome is correlated with the outcomes of other recent branches, it also uses a global history register (GHR), which records recent branch outcomes as a bit string, in indexing the BHT. The representative gshare forms an index by XORing the branch address with the global history, so that even the same branch uses a different counter when its context (history) differs. Going further, a tournament predictor keeps both a global-history-based predictor and a local (per-branch) history-based predictor, and lets yet another selector (meta-predictor) choose which is more accurate. The latest high-performance cores adopt TAGE (TAgged GEometric), which combines different history lengths, or a neural-network-based perceptron predictor, reaching around 99% accuracy.

B. Speculative Execution and Misprediction Recovery

The heart of the speculative execution engine is the reorder buffer (ROB) and register renaming. Instructions execute out of order, but only the "commit" that reflects into architectural state must obey program order, and the ROB serves as a circular queue that preserves this order. Each instruction takes its slot in the ROB in fetch order and, even after it finishes executing, holds its result temporarily until all instructions ahead of it have committed. Register renaming maps the architectural registers onto a larger set of physical registers, placing speculatively computed values in "pre-commit physical registers" to eliminate false dependencies and ease rollback.

The recovery process at the instant a misprediction is detected determines the correctness of speculative execution. When a branch instruction produces its actual outcome at the execute stage and it differs from the prediction, the hardware squashes all instructions that entered the ROB after that branch, rolls the renaming table back to the snapshot (checkpoint) at the branch point, and resumes fetching at the correct target. To avoid having already reflected writes into memory, store instructions stay only in the store buffer until commit and drain to the cache/memory only at ROB commit. Thanks to this, a speculative store is in principle prevented from becoming visible to other cores or leaving an irreversible side effect.

The problem is that while the "architectural state" is recovered perfectly, the microarchitectural state is not. If a speculatively executed load touches some memory address, the trace of that data being loaded into the cache remains even if the instruction is later discarded. An attacker can trace back this trace through a cache side channel that measures access-time differences, and reconstruct the secret value touched by a path that "should never have executed." That is, the hardware succeeded in "making the result as if it never happened" but could not erase "the physical trace that it was executed," and this gap is precisely the essence of speculative execution vulnerabilities.

C. Two Axes of Speculation: Control Speculation and Data Speculation

Speculative execution can be divided, by "what is being guessed," into control speculation and data speculation, and branch prediction is the representative case of the former. Control speculation, as explained above, guesses a branch's direction/target to advance the control flow in advance, pre-empting the program's execution path itself. The deeper the pipeline, the greater both the reward and the risk of control speculation, and in that a single misprediction throws away tens of instructions packed into the window, it takes on the character of a "high-risk, high-return" investment.

Data speculation appears mainly in memory disambiguation prediction. In out-of-order execution, when one wants to execute a later load before an earlier store, whether the two instructions' addresses overlap (depend on each other) cannot be known before execution. The processor guesses "they will not overlap" and executes the load early, but rolls back that load and the following instructions if the addresses turn out to overlap later. The structure handling this prediction is the memory dependence predictor, and Intel's store-to-load forwarding optimization is a representative example. Whether control or data speculation, the skeleton of "guess-execute-verify-recover" is the same, and both share the security commonality that misprediction traces can leak through a side channel.

A practically important implication here is that "speculation depth" is a design parameter. The wider the instruction window and the more unresolved branches are speculated in overlap, the greater the ILP, but so too grow the cost of discarding when one branch is wrong and the side-channel surface left by the wrong path. Thus high-performance server cores allow a wide window of hundreds of instructions and multi-branch speculation, whereas power-constrained embedded and mobile cores narrow the window and limit speculation depth to choose efficiency and safety—so the aggressiveness of speculation itself becomes a design decision that separates product lines.

3. Types and Comparison

Branch predictors are classified as follows by their information source and storage structure, with a clear trade-off between accuracy and hardware cost.

Category Prediction basis Representative structure Accuracy Cost/limitation
Static prediction fixed rule at compile time always-taken, backward branch=taken low (60–70%) cannot reflect runtime patterns
1-bit dynamic the single previous outcome simple BHT medium two errors at loop boundaries
2-bit dynamic inertia of previous outcomes saturating counter 90s% no inter-branch correlation
2-level/correlating global·local history gshare, tournament 95%+ history table capacity·aliasing
Advanced multiple history lengths·learning TAGE, perceptron around 99% increased area·power·complexity

The difference between static and dynamic prediction goes beyond a mere accuracy gap to the question of "when the information is obtained." Static prediction embeds rules—such as "the backward branch of a loop is usually taken"—by looking only at code structure in the compiler, so the hardware is simple, but it cannot capture runtime behavior that varies with input data. Dynamic prediction, by contrast, learns from history accumulated during execution and thus captures even data-dependent patterns. In practice the two are used complementarily. For example, the Linux kernel's likely()/unlikely() macros convey developer knowledge to the compiler as a static hint to optimize branch placement, on top of which the hardware dynamic predictor handles the fine patterns.

The reason a correlating predictor is superior to a plain 2-bit one is "context separation." Even the same branch often has outcomes that differ depending on which path was traversed just before (e.g., chained conditionals sharing a variable such as if (a) ...; if (a && b) ...), and mixing global history into the index lets each context learn a different counter, reducing interference. However, as the history bits lengthen, the table grows and aliasing—where different branches contend for the same entry—increases, so collisions are mitigated by techniques such as gshare's XOR hashing or TAGE's tag matching. This design tension of "holding more context in less storage" is a core axis of branch-prediction research.

Let us gauge the effect with concrete numbers. In a core with a 20% branch ratio and a 15-cycle misprediction penalty, assuming a base of 1 cycle per instruction, at 90% prediction accuracy the extra delay from branches is about 0.2 × 0.10 × 15 = 0.30 cycles per instruction, but raising it to 99% reduces it to 0.2 × 0.01 × 15 = 0.03 cycles—one tenth—noticeably improving CPI (cycles per instruction). Precisely because of this sensitivity, top-tier CPUs devote considerable area to multi-level predictors of thousands to tens of thousands of entries and to dedicated storage.

As a practical case, the branch-performance difference between a sorted array and an unsorted array dramatically shows the power of branch prediction. In a well-known benchmark, running the same if (data[i] >= 128) sum += data[i]; loop with the data merely sorted is several times faster than when it is unsorted. On sorted data the branch outcome follows a regular pattern that is "continuously not-taken and then continuously taken from some point" relative to the threshold, so the predictor almost always hits, whereas on random data the branches scatter like coin tosses and mispredictions explode. This case, where measured performance diverges several-fold even with identical algorithmic complexity, reminds us that performance analysis must also consider microarchitectural effects not explained by "Big-O" alone.

Another case is instruction dispatch in an interpreter. The central switch of a bytecode interpreter jumps to a different indirect branch on each iteration, and a single BTB entry predicted this multi-way indirect branch poorly, so mispredictions were frequent. To mitigate this, the threaded code (computed goto) technique, which replicates the dispatch branch at the end of each bytecode handler, was used; dispersing the branch sites this way lets each site learn a different history context, raising prediction accuracy and improving interpreter performance. That said, one should also understand that advances in modern TAGE and indirect-branch predictors have narrowed that gap compared with the past.

4. Deep Dive: Speculative Execution Vulnerabilities (Spectre·Meltdown) and Responses

Spectre and Meltdown, disclosed in 2018, were a turning point that showed how "speculation for performance" can break security boundaries. They are transient execution attacks that abuse normal CPU functions (speculative execution, out-of-order execution, caches), and the impact was large in that they were not software bugs but side channels inherent in the microarchitectural design. The common principle has four steps: "speculatively read a secret value, use it as an index to access memory → it is discarded but leaves a trace in the cache → measure the trace through a side channel → reconstruct the secret."

Spectre Variant 1 (Bounds Check Bypass), in code like if (x < array_len) y = array2[array[x] * 4096];, makes the branch predictor guess "in range" even when x is out of range, so it speculatively reads array[x] (an out-of-bounds secret) and uses that value to load a specific cache line of array2. When the branch outcome resolves, that load is discarded, but measuring the cache trace left in array2 reveals the secret byte. Variant 2 (Branch Target Injection) has the attacker poison the BTB so that a victim process's indirect branch speculatively jumps to a gadget chosen by the attacker. Meltdown is a variant that speculatively reads kernel memory before the privilege check completes during out-of-order execution, directly breaking the user-kernel boundary.

Distinguishing the fundamental difference between Spectre and Meltdown is a knack for the professional-engineer answer. Because Meltdown abuses a race between the privilege check and speculative execution, it is blocked relatively cleanly simply by separating the kernel address table from user page tables (KPTI). That is, a solution that "prevents the illegal access itself" exists. Spectre, by contrast, abuses branch prediction—a normal and essential performance feature—so the predictor itself cannot be removed, and only mitigations that selectively cut off speculation for specific code patterns are possible. Hence an asymmetry arises: Meltdown is closer to a "fixable defect" and Spectre closer to a "structurally remaining risk."

The reason these attacks opened the new field of "microarchitectural security" from the outset is that the target of attack is not a logical flaw in software but a "measurable physical side effect." Minute timing differences left by normal operation—such as whether a cache was loaded, port contention, or TLB state changes—can all become channels for secret leakage. To block the attack completely one would have to create "unobservable speculation," which is hard to achieve without sacrificing performance. Ultimately, speculative-execution security settled as a risk-mitigation problem whose realistic goal is not "reducing leaked information to zero" but "lowering the leakage bandwidth to the point where the attack is impractical."

Subsequent research revealed that Spectre and Meltdown were special cases, uncovering a broad landscape of transient execution attacks. There followed the MDS family (ZombieLoad, RIDL, Fallout), which leaks stale data by exploiting load-port delays; L1TF (Foreshadow), which targets the L1 cache in virtualized environments; Retbleed, which abuses return prediction to bypass retpoline; and Downfall, which targets floating-point and vector registers. Although their attack vectors differ (branch predictor, store buffer, return stack, and so on), they share the common skeleton of "speculatively touching a secret and leaving a microarchitectural trace." Thus a "whack-a-mole" pattern has recurred, in which blocking one variant still lets a new variant appear as long as a similar vector remains.

Responses were made at three layers: software, microcode, and hardware. On the software side were introduced inserting an LFENCE that blocks speculation after a bounds check, retpoline that turns indirect branches into an unpredictable form to prevent BTB injection, and KPTI (KAISER), which separates the kernel address space from user page tables. On the hardware/microcode side were added always-on isolation features such as IBRS, IBPB, STIBP, which prevent cross-contamination of branch-predictor state, and eIBRS in later-generation CPUs. However, these mitigations usually entail performance degradation (from a few to tens of percent on some workloads), once again driving home the "security-performance trade-off," and microarchitectural security became a permanent research topic as variants such as MDS, L1TF, Retbleed, and Downfall continued thereafter. The recent trend converges on designs that keep speculatively loaded data from affecting side channels (e.g., delaying speculative data's reflection into the cache, hardware-level isolation) and on compiler/OS techniques that selectively disable speculation in security-sensitive regions.

5. Considerations and Implications

From a professional-engineer perspective, speculative execution and branch prediction carry the following strategic implications spanning performance design and security operations.

First, performance optimization must start from "branch-friendly code." Because branch predictors are strong on regular patterns and weak on data-dependent random branches, in hot loops it is effective to replace branches with conditional moves (cmov), branchless bit operations, or lookup tables, or to sort data to raise the predictability of branch outcomes. Using the compiler's PGO (Profile-Guided Optimization) together with likely/unlikely hints can systematically reduce mispredictions on the hot path.

Second, the security-performance trade-off must be decided to match the organization's threat model. In environments that cross trust boundaries, such as multi-tenant clouds and browsers, Spectre mitigations should be enabled by default, but on HPC nodes of a single trust domain it is also reasonable to selectively relax some mitigations to recover performance. That is, differential application based on "where the boundary is" is more sensible than blanket application of mitigations, and for that, threat classification by asset and workload must come first.

Third, hardware vulnerabilities are a new axis of patch-lifecycle management. Unlike software vulnerabilities, microarchitectural flaws are entangled across microcode, firmware, kernel, and hypervisor, so a configuration- and change-management regime that links the CPU vendor's microcode distribution with OS patches is needed. Including a given CPU generation's vulnerability history and mitigation cost among evaluation items at the procurement stage is also a decision at the professional-engineer level.

Fourth, architectural choices are coupled with power, heat, and scalability. Aggressive speculation raises ILP, but on misprediction all the work performed is wasted, lowering power efficiency. On mobile and edge, predictors are simplified and speculation depth limited to save power, whereas servers maximize throughput with accurate large predictors. As workloads with few branches and high data parallelism, such as AI inference, increase, the role division between speculation-centric general-purpose CPUs and GPUs/NPUs with low speculation dependence should be considered as an architectural strategy.

Fifth, observability-based diagnosis is important. Because most CPUs expose branch-misprediction rates, BTB misses, and the like through performance counters (PMU), one should instrument mispredictions at hot spots with tools such as perf and select optimization targets on an evidence basis. Not optimization that relies on guesswork, but the measure-analyze-improve cycle, is the standard of performance engineering.

References

In one line: Branch prediction guesses a branch's direction/target in advance to fill the gaps of a deep pipeline, and speculative execution is the ILP engine that pulls instructions in and runs them on that guess, rolling back on misprediction; the architectural state is recovered, but microarchitectural traces such as the cache remain and become the root of Spectre and Meltdown, so performance and security must be designed together.