1. Field of the Invention
This invention relates to data processing systems. More particularly, this invention relates to branch prediction within data processing systems.
2. Description of the Prior Art
It is known to provide data processing systems which incorporate branch prediction mechanisms. High performance data processors typically include a mechanism to prefetch program instructions from memory in advance of those program instructions being required for execution by the processor. Once a given program instruction is executed it is normal to proceed to execute the program instruction at the immediately following memory address location unless a branch instruction has occurred redirecting the program flow to a different point. Thus, a simple prefetch mechanism may prefetch instructions from a sequence of immediately adjacent memory address locations. However, if a branch instruction is encountered causing a jump away from this normal sequence, then the prefetching that has taken place will have been incorrect and there will be a time penalty incurred as the next required instruction is fetched from the memory. To address this problem branch prediction mechanisms are known to be provided.
Broadly speaking, branch prediction mechanisms seek to identify branch instructions occurring within the program flow and modify the behaviour of the instruction prefetching mechanisms based upon a prediction as to whether or not the branch instruction concerned will or will not result in a jump away from the normal sequence of program instruction addresses.
One type of branch prediction mechanism is termed static branch prediction whereby a branch instruction is identified by the opcode for a branch instruction being returned from the memory and then a rule applied to predict whether or not that branch instruction will result in a jump. One rule is that branch instructions specifying a backward jump in the program flow are predicted to be taken whereas branch instructions indicating a forward jump are predicted not to be taken. Static branch prediction has the advantage of being relatively simple to implement, but the disadvantages that it is not until the opcode is returned for the branch instruction that the branch instruction is identified as such and so some incorrect further prefetches may have already been initiated as well as the limitation to the fixed rule for making a prediction which is non-responsive to actual observed behaviour.
Another type of branch prediction can be based upon historical activity. As an example, such predictors may seek to identify patterns arising in the execution of the code such as every third branch being taken. Whilst such branch prediction mechanisms may produce more accurate predictions than static branch prediction mechanisms, they suffer from the disadvantage of being more complex and consuming more circuit resource.
Another known type of branch prediction mechanism utilises a branch target address cache (BTAC) which stores a plurality of branch instruction addresses each associated with their target instruction addressees and data indicating the likelihood of that branch being taken, e.g. strongly predicted, weakly predicted, weakly non-predicted and strongly non-predicted. The data specifying the prediction associated with each branch is dynamically updated based upon the result of the associated branch instruction when it is actually executed. BTAC mechanisms can be responsive to the attempted prefetching from a memory address from which a branch address has previously been fetched and the target address and result cached such that the prefetching address sequence can be modified before the actual branch instruction opcode is returned from the memory in a way that would enable it to be recognised by a static branch prediction mechanism as discussed above. Whilst BTAC mechanisms provide good performance advantages, they are disadvantageously complex and require a disadvantageous amount of circuit resource to implement.
Another way of dealing with the occurrence of branch instructions disrupting prefetch behaviour is to provide a sufficiently large prefetch instruction buffer together with the ability to fetch instructions from memory at a faster rate than they are consumed from the prefetch buffer by execution. In such systems a branch prediction mechanism which suffers from a delay in identifying a branch instruction until it is actually returned as an opcode, e.g. a static branch predictor as discussed above, may be compensated for in that incorrectly prefetched instructions can be flushed from the prefetch buffer and the prefetch buffer refilled without any interruption in the supply of instructions from the prefetch buffer to the mechanisms for executing the instructions. However, this approach does not address problems associated with tight program loops and also requires significant circuit resource.