Branch prediction (all processors)

Document - https://www.agner.org/optimize/microarchitecture.pdf

The pipeline in a modern microprocessor contains many stages, including instruction fetch, decoding, register allocation and renaming, µop reordering, execution, and retirement.

Handling instructions in a pipelined manner allows the microprocessor to do many things at the same time.

Branch prediction (in processors) is a technique used by modern processors to improve performance by guessing which branch in a conditional statement (e.g., if-else) will be executed.

📝 Summary: Pipeline and Branch Prediction in CPU

🔹 1. Pipelining

Modern CPUs execute instructions in stages, breaking them down into stages:

1. Fetch – loading instructions from memory.
2. Decode – decoding in microop (µop).
3. Rename/Allocate – rename registers (for Out-of-Order).
4. Execute – execution (ALU, memory access).
5. Retire – fixing the result (writing to registers/memory).

🔻 Problem: Branches they interfere with the pipeline, since the CPU does not know which instruction will be next until the condition is calculated.

🔹 2. Speculative Execution

Speculative execution is an optimization technique where a computer system performs some task that may not be needed.

The CPU predicts which code branch will execute and starts executing it before the condition is checked.

🔸 How does it work?

• If the prediction is correct → the results ** are fixed (retire)**.

• If incorrect → the pipeline is reset (flush), the correct branch is executed.

• What is dangerous?

• Spectre attacks use speculative execution to leak data.

Spectre (security vulnerability)

Spectre is one of the speculative execution CPU vulnerabilities which involve microarchitectural side-channel attacks. (These affect modern microprocessors that perform branch prediction and other forms of speculation)

Spectre: CPU vulnerability analysis, operation mechanism and protection

1. What is Spectre?

Spectre (CVE-2017-5753, CVE-2017-5715) is a vulnerability of the class of side-channel attacks that uses speculative execution in modern processors to read protected data from memory.

Key Features:

• Almost all CPUs are affected (Intel, AMD, ARM, IBM)
• Cannot be fixed by the microarchitecture patch (requires software changes)
• Allows you to read the memory of the kernel, other processes, and the hypervisor.

2. How does Spectre work?

🔹 The main components of the attack

1. Speculative Execution
2. The CPU anticipates branches and executes the code before checking the conditions

3. The results are not recorded, but leave traces in the cache

4. Timing Attack

5. Measuring data access time allows you to determine whether a secret key has been speculatively downloaded

6. Cache Side-Channel Attack

7. Using Flush+Reload or Prime+Probe to extract data

🔹 Detailed mechanism (using the example of Spectre v1)

Step 1: Cheating the Branch Predictor

if (x < array1_size) { // The CPU speculatively executes this block, even if x > array1_size
    value = array2[array1[x] * 256]; // Reading outside the array!
}

• The attacker selects x to bypass the border check
• CPU speculatively loads array1[x]

Step 2: Impact on Cache

• Processor caches array2[array1[x] * 256]
• Even if the branch is rolled back, the cache remains changed

Step 3: Reading through Timing

// Attacker measures access time to array2 elements
for (int i = 0; i < 256; i++) {
if(measure_access_time(array2[i * 256]) { // Quick access = was in cache
        // Guessing the value of array1[x]
    }
}

3. Spectre Variants

4. Protection methods

🔹 Hardware (microcode/architecture)

1. Retpoline (Google)

   • Replacing indirect calls with protected sequences
   • Example for GCC: -mretpoline

2. IBRS/STIBP (Intel)

3. BTB isolation between processes

4. Enhanced IBRS (Ice Lake+)

5. Hardware suppression of speculative execution

🔹 Software (compilers/OS)

1. LFENCE-barriers
2. Elimination of branches
3. KPTI (Kernel Page Table Isolation)
4. Separation of the core and user page tables

5. Current status

• Spectre is still relevant (new variations appear regularly)
• Protection reduces productivity (up to 30% for some workloads)
• Best prevention:
• CPU microcode updates
• Compilation with -mretpoline -fno-strict-aliasing
• Disabling hypertrading in critical systems

📚 Sources

1. Original article about Spectre (M. Lipp et al.)
2. Intel Analysis of Speculative Execution
3. ARM Mitigations Guide

🔹 3. Branch Prediction

The CPU uses two mechanisms:

1. Will there be a jump?

2. The history of previous jumps (for example, 1-bit/2-bit predictor).

   • If a branch is frequently taken → the CPU predicts "taking".

3. Where will he jump?

4. BTB (Branch Target Buffer) – cache of hop addresses.

   • Stores the address of the target for each jump (jump/call).

🔸 Problems:

• BTB overflows → different jumps crowd each other → prediction errors.
• Conditional jumps (JZ, JNZ) predicted worse than unconditional (JMP).

Branch Target Buffer (BTB) is a cache in the processor that remembers where conditional instructions go (for example, if). It predicts where the program will go next time, so that the processor does not wait, but immediately starts executing the necessary code. This speeds up the work, but sometimes it makes mistakes, and then you have to redo everything.

🔹 4. Prediction Error (Branch Misprediction)

• What's going on?
• The pipeline is reset (flush).
• The CPU loses N clock cycles, where N = pipeline length (for example, 14 clock cycles in Intel Skylake).

🔸 How to minimize it?

• Branch reduction (replacing if with bit operations).
• Hint instructions (__builtin_expect in C/C++).

// Better (fewer branches):

x = (a > b) * c;

// Worse (branch misprediction):
if (a > b) x = c; else x = 0;

📌 Output: Key Points

✅ Pipeline – execution of instructions in stages for parallelism.

Speculative execution – The CPU guesses the branch and executes it in advance.

• BTB – cache of jump addresses for fast prediction. Prediction error → pipeline reset → loss of performance.

the following will be (in detail)
3.1 Prediction methods for conditional jumps

see u later )