Overview

Branch prediction predicts the likely direction of a conditional branch instruction to support instruction-level parallelism (ILP). The workload-characterization source frames branch prediction as a pattern-recognition problem: a predictor learns mappings from execution context to branch outcome. [C1]

Performance role

Accurate branch prediction reduces the number of instructions executed on the wrong path, which can improve both performance and energy consumption. The same workload-characterization work proposes two workload-driven identifiers for branch-prediction behavior: branch working set size and branch predictability. It reports that these identifiers are highly correlated with the misprediction rates of modern predictor schemes such as TAGE and perceptron. [C2]

That work defines the branch working set of a trace as a group of the most frequently occurring branch contexts, where a branch context is represented as a tuple containing the branch address and associated global and local history. The study reports characterizing 2,451 workload traces into seven branch-working-set-size categories and nine predictability categories. [C3]

Role in the CPU pipeline

The SNAP evidence identifies branch predictions as microarchitectural state available in the processor pipeline during program execution. In that context, branch predictions are described as invisible to software under normal execution, but available to hardware-level tracing mechanisms. [C4]

Use in SNAP fuzzing support

SNAP uses branch-related microarchitectural information to provide fuzzers with richer runtime feedback than code coverage alone. The SNAP paper states that last-executed branches can be expensive to extract in software, while branch predictions are entirely invisible to software; SNAP exposes such microarchitectural information to provide extra execution semantics, including immediate control-flow context and approximated data flows. [C5]

SNAP also uses prediction results associated with recorded branch sequences in the Last Branch Queue (LBQ). The paper states that, given prediction results for the recorded branch sequence in the LBQ, SNAP can infer a longer branch history than the captured one. If a mutated input byte changes the prediction result of a branch, SNAP treats the branch condition as likely related to that input offset, thereby approximating data flow from input to variables affecting the branch decision. [C6]

Example implementation context: RISC-V BOOM

The SNAP evaluation uses a BOOM processor configuration whose front end is listed as having 8-wide fetch, 16 RAS entries, 512 BTB entries, and a gshare branch predictor. [C7]

Security implications

Branch prediction is security-sensitive because modern processors can suffer threats that exploit branch-instruction collisions inside the branch prediction unit (BPU). The STBPU paper summary identifies such threats as including eavesdropping on secret-related branch operations and triggering malicious speculative executions. [C8]

The same source states that mitigations such as partitioning or flushing the BPU can stop some collision-based exploits only to a limited extent and can negatively affect branch prediction accuracy and CPU performance. STBPU is proposed as a secure BPU design that customizes BPU data representation for each software entity requiring isolation and monitors prediction-related events to preemptively change that representation against brute-force collision attempts. [C9]