Persistence-Based Branch Misprediction Bounds for WCET Analysis

Branch prediction is an important feature of pipelined processors to achieve high performance. However, it can lead to overly pessimistic worst-case execution time (WCET) bounds when being modeled too conservatively. This paper presents bounds on the number of branch mispredictions for local dynamic branch predictors. To handle interferences between branch instructions we use the notion of persistence, a concept that is also found in cache analyses. The bounds apply to branches in general, not only to branches that close a loop. Furthermore, the bounds can be easily integrated into integer linear programming formulations of the WCET problem. An evaluation on a number of benchmarks shows that with these bounds, dynamic branch prediction does not necessarily lead to higher WCET bounds than static prediction schemes.