Timely, Efficient, and Accurate Branch Precomputation

Out-of-order cores rely on high-accuracy branch predictors to supply useful instructions to the processor backend. However, there remains a large fraction of mispredictions caused by hard-to-predict (H2P) branches that modern predictors have been unable to improve. Precomputation is an alternative to prediction that speculatively executes the dependence chain of a branch earlier to override the branch predictor at Fetch time. However, prior work sacrifices H2P branch coverage and precomputation accuracy to produce timely results.

Our work relaxes this timeliness constraint by using precomputation results to issue early misprediction flushes instead of overriding the branch predictor. This allows us to construct a highly accurate precomputation thread with good misprediction coverage, without sacrificing timeliness. The thread is efficient as it utilizes on-core execution resources and re-uses existing hardware for issuing early flushes. Using our Timely, Efficient, and Accurate thread for precomputation yields a 10.1% improvement in performance over an aggressive baseline OoO core.