Evolution of Branch Prediction and Its Parallels with SSA → SSI

Evolution of Branch Prediction and Its Parallels with SSA → SSI

1. Branch Prediction Evolution

Branch prediction has been one of the most important microarchitectural techniques for exploiting instruction-level parallelism in CPUs.

• Static Prediction (pre-1980s):
  • Early CPUs simply recorded which way the branch went last time and predicted the same outcome.
  • Accuracy: ~85%.
  • Hardware cost: ~1K bits.
• Two-bit and Multi-bit Counters (1980s--1990s):
  • Added history with saturating counters (2-bit, 3-bit, etc.).
  • Improved accuracy to ~90--92%.
  • Example: "predict taken if counter ≥ threshold."
  • Hardware: a few kilobits.
• Global + Local History (1990s--2000s):
  • Recognized that outcome may depend on how you got there (path history).
  • E.g., "Bob likes Jane" vs "Bob likes Jill" example → different outcomes.
  • Combined global history with counters.
• Neural / Perceptron Predictors (2000s--today):
  • Use perceptron-like learning: weight vectors times history bits.
  • Essentially a small neural net in silicon.
  • Accuracy >95--99%.
  • Hardware cost: tens of megabits.
  • Modern branch predictors are like "tiny supercomputers" inside CPUs.
• Speculative Execution with Invariance Tracking (modern research):
  • Even if mispredicted, CPU can sometimes reuse invariant computations.
  • Analogy: misunderstanding a paragraph but still being able to use facts in the next one.

2. SSA → SSI Evolution

In compiler theory, Static Single Assignment (SSA) form also evolved to handle path-sensitive information, which parallels branch prediction evolution.

• SSA (1980s):
  • Each variable is assigned exactly once.
  • φ-nodes merge values from different control-flow paths.
  • Enables easier dataflow analysis.
• SSI (Static Single Information, 1990s):
  • Extends SSA with σ-nodes (propagation of predicates along branches).
  • Adds history/context: the value of a variable may depend on the branch condition taken.
  • This is similar to branch predictors adding path history for accuracy.

3. Parallels Between Branch Prediction and SSA → SSI

• Base Case (Last Outcome vs SSA):
  • Last-outcome prediction is like plain SSA: keeps track of values (or outcomes) but without context.
• Adding History (Counters vs σ-nodes):
  • Multi-bit counters and global history parallel the move from SSA to SSI, where additional information (context) is preserved.
• Learning-based (Neural Predictors vs Path-sensitive IR):
  • Just as neural predictors recognize deeper patterns, SSI and advanced compiler IRs capture richer flow-sensitive invariants.

4. Timeline Summary

• 1980s: Last-outcome prediction, SSA formalization.
• 1990s: Two-bit counters, global history predictors, SSI introduction.
• 2000s--2020s: Perceptron predictors, neural nets; research into predicate-sensitive IR and advanced SSA variants.

5. References / Papers

• J.E. Smith, "A study of branch prediction strategies," ISCA 1981.\
• Yeh & Patt, "Two-level adaptive branch prediction," MICRO 1991.\
• Jiménez & Lin, "Dynamic Branch Prediction with Perceptrons," HPCA 2001.\
• Cytron et al., "Efficiently Computing Static Single Assignment Form," TOPLAS 1991.\
• Ananian, "The Static Single Information Form," MIT CSAIL TR-827, 1999.