Read the original article here.

---

Speculative Execution: The CPU's Gamble for Speed (Underground Techniques Series)

Welcome, aspiring code sorcerers, to a dive into one of the fundamental performance optimization techniques employed deep within the silicon of modern computers. This isn't the stuff of standard introductory classes; understanding speculative execution takes you beyond the surface of high-level programming and into the actual dance of instructions happening on the processor. Why is it like "forbidden code"? Because while every modern program benefits from it, its internal workings are often abstracted away, and understanding its nuances – including its potential pitfalls – is key to unlocking true performance mastery or uncovering subtle security vulnerabilities.

1. What is Speculative Execution?

At its core, speculative execution is a gamble. A calculated risk taken by the computer system to avoid sitting idle. Instead of waiting until it's absolutely certain about what task to perform next, the system guesses and starts working on what it thinks will be needed.

Speculative Execution: An optimization technique where a computer system performs tasks based on a prediction or guess about a future condition or outcome, before it is known with certainty whether that work will actually be required.

The fundamental goal is simple: prevent delays. If the guess turns out to be correct, the system is already ahead. If the guess is wrong, the work performed speculatively is discarded, and the system rolls back to the point of the guess and proceeds down the correct path. The hope is that the time saved by correct guesses outweighs the cost of incorrect guesses (mispredictions) and the resources used speculatively.

This technique thrives in environments where extra processing resources (like execution units in a CPU) are available and can be used speculatively without impacting non-speculative, confirmed work.

2. Why Do We Need Speculative Execution? The Problem of Pipelines and Branches

To understand the necessity of speculation, you need a basic grasp of how modern CPUs process instructions. They don't execute one instruction entirely before starting the next. Instead, they use a pipeline, much like an assembly line. Each instruction goes through several stages (fetching, decoding, executing, writing back results).

CPU Pipeline: A technique used in microprocessor design where multiple instructions are overlapped in execution. While one instruction is in the execution stage, the next instruction is being decoded, the instruction after that is being fetched, and so on. This increases instruction throughput.

Pipelines work great for sequential code (A; B; C; D; ...). However, problems arise with control flow changes, particularly conditional branches (like if/else statements, while loops, for loops).

Consider this simple code:

if (condition) {
    // Path A
    instruction_A1;
    instruction_A2;
} else {
    // Path B
    instruction_B1;
    instruction_B2;
}
instruction_C;

In a deep pipeline, the CPU fetches instruction_A1 and instruction_B1 (which come right after the if or else block in memory, even though only one will be executed) before the condition is fully evaluated in the pipeline. The CPU needs to know whether to execute Path A or Path B to fetch instruction_C correctly. If the CPU waited for the condition to be evaluated before fetching anything from the chosen path (A or B), the pipeline would stall, losing valuable cycles.

Branch Penalty: The performance cost incurred when a CPU encounters a conditional branch and must wait until the outcome of the condition is known to fetch the next instruction. This pause causes pipeline bubbles or stalls, reducing throughput.

Speculative execution, combined with techniques like branch prediction, is the primary way modern CPUs try to hide or eliminate this branch penalty.

3. How Speculative Execution Works (The General Mechanism)

While implementations vary, the general flow of speculative execution looks something like this:

1. Prediction: The system (often a specialized unit like a branch predictor in a CPU) makes a guess about a future event. For a conditional branch, the predictor guesses whether the branch will be taken or not taken.
2. Speculative Execution: Based on the prediction, the system proceeds to execute instructions or tasks as if the prediction were correct. These instructions are executed using available resources, but their results are kept in a temporary, reversible state. They are not immediately committed to the main architectural state (registers, memory) that is visible to the program.
3. Verification: The system eventually determines the actual outcome of the event that was predicted (e.g., the condition in the if statement is evaluated).
4. Commit or Rollback:
   • Commit: If the prediction was correct, the results of the speculatively executed tasks are committed, making them permanent and visible to the program state. The system gained performance by getting a head start.
   • Rollback (or Squashing): If the prediction was incorrect (a misprediction), the system must discard all the work done speculatively along the wrong path. The temporary state is cleared, and the system reverts to the state before the prediction was made, then proceeds down the correct path. This rollback process incurs a performance penalty, the cost of the misprediction.

The effectiveness of speculative execution heavily depends on the accuracy of the predictions and the efficiency of the rollback mechanism.

4. Where Speculative Execution is Applied

Speculative execution isn't confined to just one part of a computer system. It's a powerful paradigm used across different levels:

4.1. Processor Level Optimizations

This is arguably the most common and impactful application in modern computing.

• Branch Prediction: As discussed, this is the primary technique used in pipelined processors.

  • Example: When a CPU encounters a loop's conditional branch (while (i < 100)), a branch predictor might guess it will be 'taken' most of the time. The CPU speculatively fetches and executes instructions from inside the loop for the next iteration before the comparison i < 100 for the current iteration is finished. If i eventually becomes 100 and the prediction is wrong (the branch is 'not taken'), the speculatively executed instructions from the loop body are discarded.

  Branch Prediction: A technique used in computer architecture to reduce the stall time associated with conditional branches by predicting the outcome of the branch (taken or not taken) and speculatively fetching and executing instructions along the predicted path.

• Value Prediction: A more advanced form where the system speculates on the value a particular instruction will produce, not just the control flow path.

  • Example: If a variable often holds the value 0 or 1 in a loop, the CPU might speculate that a load or computation involving that variable will result in 0 or 1. It can then speculatively execute dependent instructions using that predicted value. This is useful in exploiting "value locality" – the tendency for variables to frequently take on the same few values.

  Value Prediction: A technique where the processor predicts the result of an instruction's computation or a memory load's value before the instruction actually completes execution, allowing dependent instructions to execute speculatively with the predicted value.

• Prefetching: While sometimes considered related but distinct, prefetching can involve speculative elements, especially when fetching data based on predicted future access patterns.

  • Example: When a program is iterating through a large array, the CPU's prefetcher might detect this pattern and speculatively load the next few cache lines of the array into the cache before the program explicitly requests them. This hides the latency of accessing main memory. If the program changes direction (e.g., jumps out of the loop), the prefetched data was speculative and might not be used.

  Prefetching: Loading data into the processor cache or instructions into the instruction cache before they are actually needed by the program, in anticipation of their use. This is often based on predicted access patterns.

4.2. System Level Optimizations

Speculation isn't limited to the CPU pipeline. It can be applied at higher levels of abstraction.

• Optimistic Concurrency Control (Database Systems): This is a classic example outside the CPU. Instead of locking resources upfront (which can cause delays if others need them), transactions proceed optimistically, assuming no conflicts will occur.

  • Example: Two users, A and B, try to update the same database record. In optimistic concurrency, both read the record and start preparing their changes without locking it. When they try to commit their changes, the system checks if the underlying data was modified by someone else since they read it. If not (the optimistic guess was correct), the commit succeeds. If it was modified (a conflict, the guess was wrong), one transaction is typically rolled back and might need to retry. This avoids locking overhead when conflicts are rare.

  Optimistic Concurrency Control (OCC): A method of dealing with conflicting access to data in concurrent systems (like databases) where transactions proceed without acquiring locks upfront, assuming conflicts are rare. Conflicts are checked only when a transaction attempts to commit, and if found, the conflicting transaction is rolled back.

4.3. Programming Language / Runtime Level

Even programming language runtimes can explore speculative execution, though it's more complex due to the potential for side effects.

• Speculation in Lazy Languages (e.g., Haskell): Lazy evaluation means expressions are only evaluated when their value is actually needed. Eager evaluation evaluates them immediately. Integrating speculation into a lazy language involves speculatively evaluating expressions before they are strictly needed. This is challenging because evaluating an expression might have side effects (like I/O), which are hard to roll back if the speculative result is discarded. Research has explored techniques like "optimistic execution" with complex abortion mechanisms, but it's often deemed too complicated or risky for general use compared to hardware speculation.

  Lazy Execution (or Lazy Evaluation): An evaluation strategy that delays the evaluation of an expression until its value is actually needed. It is the opposite of eager evaluation, which evaluates expressions as soon as they are bound to a variable or passed as an argument.

• Runahead Execution: A specific microarchitectural technique where, upon encountering a very long-latency event (like a cache miss requiring main memory access), the processor doesn't completely stall. Instead, it enters a "runahead" mode, speculatively executing future independent instructions using available resources and predicted values. Results are stored in a temporary buffer. When the long-latency event completes, if the speculation was correct, the buffered results can be quickly committed. If not, they are discarded. This is a form of speculation aimed specifically at hiding memory latency.

5. Types of Speculative Execution Variants

While the core principle is similar, different approaches exist based on what and how much is speculated:

• Eager Execution: This is the most aggressive form. For a conditional branch, the system doesn't just predict one path; it speculatively executes both paths simultaneously.

  • The results of both paths are computed, but only the results of the path corresponding to the actual branch outcome are committed.
  • Benefit: Guarantees no pipeline stalls due to branches (assuming resources). Theoretically matches "oracle execution" (perfect prediction).
  • Cost: Requires significant redundant resources (double the execution units, registers, etc., for each speculative level). The resource requirement grows exponentially with nested branches executed eagerly. Rarely implemented in pure form due to resource cost.

• Predictive Execution: This is the more common approach used in modern CPUs (like with branch prediction).

  • The system predicts one outcome (e.g., branch taken).
  • Execution proceeds speculatively down the predicted path.
  • If the prediction is correct, committed. If wrong, rolled back.
  • Benefit: More resource efficient than eager execution as it only executes one path speculatively.
  • Cost: Performance depends heavily on prediction accuracy. Mispredictions incur a significant penalty (the cost of rollback and fetching the correct path).

6. The Flip Side: Lazy Execution

It's worth noting that speculative execution (often leaning towards eager principles) is contrasted with Lazy Execution.

• Speculative Execution: Does work early based on a guess that it might be needed soon.
• Lazy Execution: Delays work until it is definitely needed.

While seeming opposite, they tackle different problems. Speculation is about performance under uncertainty by using available resources. Lazy execution is about correctness and efficiency by avoiding computation (potentially with side effects) until its result is absolutely required. As seen with Haskell, integrating speculation into a fundamentally lazy model adds significant complexity.

7. The Dark Side: Security Vulnerabilities

For many years, speculative execution was primarily viewed through the lens of performance. However, starting in 2017, a series of critical security vulnerabilities were discovered that leveraged the side effects of speculative execution.

The core issue: Even if the results of speculatively executed instructions are rolled back and discarded, the process of executing them can leave observable traces in the microarchitectural state of the CPU, such as in the cache or branch predictor state.

• How it Works: A malicious process or piece of code can craft operations where sensitive data (which it shouldn't have access to) is speculatively loaded or used during a path that is later determined to be incorrect and rolled back. While the data isn't committed to architectural registers, its value might influence which cache lines are accessed or how branch predictor states are updated. By carefully timing subsequent operations, an attacker can infer the value of the sensitive data based on these microarchitectural side effects (e.g., observing which cache lines are faster to access).

These attacks are often referred to as Transient Execution Attacks because they exploit instructions that are executed transiently (briefly and later discarded) during speculation.

Transient Execution Attacks: Security vulnerabilities that exploit the microarchitectural side effects of instructions executed speculatively by the CPU along a path that is later abandoned. Although the architectural state is rolled back, observable changes in the microarchitectural state (like cache contents or timing) can leak information about the data processed during the transient execution.

Notable vulnerabilities in this class include:

• Meltdown: Allows a less-privileged process to read memory from more-privileged processes or the operating system kernel by exploiting how speculative loads handle memory protection checks.
• Spectre: Tricks the processor into speculatively executing code sequences that leak sensitive data through microarchitectural side channels (like the cache or branch prediction state). It involves injecting malicious patterns into the victim's branch predictor or exploiting other speculative features.
• Microarchitectural Data Sampling (MDS): A class of vulnerabilities allowing data to be inferred from microarchitectural buffers used during speculative execution.
• Foreshadow, SPOILER, Pacman, etc.: Other variants exploiting similar principles on different microarchitectural components or architectures.

Understanding speculative execution is no longer just about squeezing performance; it's also about understanding fundamental hardware-level security weaknesses that affect almost every device we use. Patches often involve disabling certain speculative features or adding microcode updates that insert performance-costly serialization instructions to prevent speculative execution across security boundaries.

8. Related Concepts

Several other low-level CPU optimizations are closely related to or enable speculative execution:

• Out-of-Order Execution: Processors don't necessarily execute instructions in the exact order they appear in the program code. They can reorder instructions if their dependencies allow, keeping execution units busy. Speculative execution often happens within this out-of-order engine.
• Speculative Multithreading: A parallel processing technique where a single program thread is divided into multiple threads that run speculatively in parallel. This is a higher-level form of speculation applied across multiple cores or hardware threads.

9. Conclusion

Speculative execution is a powerful, pervasive optimization technique that is absolutely critical to the performance of modern computer systems, especially CPUs. By gambling on the likely outcome of uncertain events, processors can avoid costly stalls and keep their pipelines full, delivering the speed we expect.

However, this performance comes at the cost of complexity and, as recent discoveries have shown, opens the door to subtle yet critical security vulnerabilities. For those truly seeking to understand the "forbidden code" – the low-level mechanics often hidden from view – grasping speculative execution, its benefits, its mechanisms, and its risks is essential. It's a prime example of how deep technical knowledge is necessary not just for optimization, but also for understanding the fundamental security landscape of the systems we rely on.