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 a mapping from an execution context to a 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 3-part tuple containing the branch address and the 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

Branch predictions are part of the microarchitectural state available in the processor pipeline during program execution. In the context of SNAP, branch predictions are described as invisible to software under normal execution, but available to hardware-level tracing mechanisms such as those used by SNAP. [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 much longer branch history than the captured one. Because most branch conditions are data-dependent, 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 the input to the variables that affect the branch decision with near-zero cost. [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]

Verification: branch mis-prediction as a functional test target

Functional verification of pipelined microprocessors treats branch mis-prediction as an explicit testcase category. The UCI technical report on Architecture Description Language driven functional test program generation lists a Branch Prediction class of testcases whose goal is to generate inputs that cause branch mis-prediction and the resulting pipeline stalls and flushing, so that the committed architectural state in the presence of such hazards can be checked. The report also lists a related Feedback Paths category of testcases that exercises every feedback path in the pipeline, of which the branch-prediction feedback path is one instance, and frames this as part of functional-coverage-driven verification. [C11]

Relationship with RISC-V Control Transfer Records (CTR)

The RISC-V Control Transfer Records (CTR) extension provides hardware CSRs for recording control transfers, including branches, and supports exposing branch-prediction-related information to software. A Linux perf patch adding CTR CSR definitions defines configuration bits including CTRCTL_BPFRZ (BP freeze), CTRCTL_TKBRINH (taken-branch inhibit), CTRCTL_NTBREN (not-taken branch enable), and per-transfer-type inhibit bits such as CTRCTL_INDCALL_INH, CTRCTL_DIRCALL_INH, CTRCTL_INDJUMP_INH, CTRCTL_DIRJUMP_INH, CTRCTL_CORSWAP_INH, CTRCTL_RET_INH, CTRCTL_INDOJUMP_INH, and CTRCTL_DIROJUMP_INH. The patch also defines CTRTARGET_MISP, indicating that CTR records can carry misprediction information from the branch predictor, and CTRDATA_TYPE_TAKEN_BRANCH / CTRDATA_TYPE_NONTAKEN_BRANCH record types that distinguish branch outcomes. CTR is therefore a related mechanism that exposes branch outcomes and misprediction state to privileged software, complementing other software-invisible branch-prediction state used by mechanisms such as SNAP. [C10]