Caching and predicting branch sequences for improved fetch effectiveness

A sequence of branch instructions in the dynamic instruction stream forms a branch sequence if at most one non-branch instruction separates each consecutive pair of branches in the sequence. We propose a branch prediction scheme in which branch sequence history is explicitly maintained to identify frequently encoun-tered branch sequences at runtime and when the rst branch in the sequence is encountered, the outcomes of the all of the branches in the sequence are pre-dicted. We have designed an implementation of a branch sequence predictor which provides overall mis-prediction rates that are comparable with the gshare single branch predictor. Using this branch sequence predictor we have devised a new instruction fetch mech-anism. By saving the instructions following the rst branch belonging to a branch sequence in a sequence ta-ble, the proposed mechanism eliminates fetches of non-consecutive instruction cache lines containing these in-structions and therefore delays associated with their fetching is avoided. Experiments comparing the pro-posed fetch mechanism with a simple fetch mechanism based upon a single branch prediction for Spec95 bench-marks demonstrate that the total number of I-cache lines fetched during execution decreases by as much as 15%, the number of useful instructions per fetched cache line increases by as much as 18%, and the over-all IPCs achieved on a superscalar processor increase by as much as 17 % for some benchmarks