Speculative branch target allocation

A method and apparatus for improving branch prediction, the method including determining a target of a branch instruction; storing the target of the branch instruction before the branch instruction is fully executed; and re-encountering the branch instruction and predicting a target for the branch instruction by accessing the stored target for the branch instruction.

DETAILED DESCRIPTION Various embodiments disclosed herein overcome the problems in the existing art described above by providing a method and apparatus which utilize a cache to improve branch target prediction. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the various embodiments. It will be apparent, however, to one skilled in the art that the embodiments may be practiced without some of these specific details. The following description and the accompanying drawings provide examples for the purposes of illustration. However, these examples should not be construed in a limiting sense as they are merely intended to provide exemplary embodiments rather than to provide an exhaustive list of all possible implementations. In other instances, well-known structures and devices are shown in block diagram form in order to avoid obscuring the details of the various embodiments. Referring now to FIG. 1, a flow chart is shown which illustrates the manner in which an embodiment improves branch prediction. Initially, a branch target for a branch instruction is determined at block 10 . In an embodiment, a decoder is used to determine the target for the branch instruction. The target is then allocated (e.g., stored) at block 12 before the branch instruction is fully executed. In an embodiment, allocating the target at block 12 includes saving the target to a cache, other fast memory, or the like. At blocks 14 and 16 respectively, the branch instruction is re-encountered, and the branch target is predicted by accessing the allocated target. In this manner, branch prediction is improved since the prediction can occur prior to complete execution of the first occurrence of the branch instruction. This is of even greater importance when processing programs which are highly dependent on small loops since a branch instruction may be re-encountered several times before the initial occurrence has been fully executed. Thus, multiple target mispredictions can be avoided. In an embodiment, the branch target is also stored in a Branch Prediction Unit (“BPU”) after the branch instruction has been fully executed. This facilitates prediction of branch targets when the same branch instruction is subsequently re-encountered. However, various embodiments, which include additionally storing the branch target in the BPU, contemplate predicting the target before the target is stored in the BPU. For instance, a target for a branch instruction is determined, and the target is allocated (e.g., to a cache) before execution of the branch instruction is completed. Subsequent to the initial allocation and while the first occurrence of the branch instruction is being executed, the branch instruction is re-encountered, and the target is predicted by accessing the stored target. Finally, after the first occurrence of the branch instruction is fully executed, the target is additionally allocated to the BPU for future predictions. In various embodiments, future predictions which involve the BPU as well as the cache proceed as follows. Upon re-encountering the branch instruction, the BPU accesses (e.g., a lookup) the cache and the branch target buffer located within the BPU for targets. The BPU prioritizes the targets obtained from the cache and the branch target buffer and generates a prediction based on the prioritized targets. In some embodiments, after the branch target has been allocated to the BPU, the branch target continues to be allocated to the cache and/or the BPU as the branch instruction is re-encountered. In other embodiments, after the branch target has been allocated to the BPU, the branch target is no longer allocated to the cache once the target for that branch instruction has been allocated to the BPU. It should be noted that the branch instruction can be a direct branch and/or a backward branch. A direct branch is a branch which enables the target address to be calculated by the decoder. Thus, the target may be immediately allocated once it is determined, rather than waiting to allocate after execution of the branch instruction. A backward branch is a branch which is a loop, and therefore, the branch instruction would be expected to reoccur. As such, allocating the target of a backward branch in anticipation of re-encountering the branch instruction improves branch prediction. Turning now to FIG. 2, a system is shown which illustrates the components which comprise an embodiment for improving branch prediction. It should be noted that various components have been omitted in order to avoid obscuring the details of the embodiment shown. The system includes a processor 18 capable of pipelining instructions coupled to a chipset 20 and a main memory 22 . The processor 18 includes a BPU 24 and a decoder 26 . The decoder 26 has a cache 28 disposed within the decoder 26 . Although the embodiment shown in FIG. 2 has the cache 28 disposed within the decoder 26 , it is contemplated to have the cache 28 located elsewhere within the system. In accordance with various embodiments discussed above, the decoder 26 determines the branch target for a branch instruction and allocates the target to the cache 28 . While the processor 18 is executing the branch instruction, the branch instruction is re-encountered. The BPU 24 predicts the target by conducting a lookup to the cache 28 within the decoder 26 in order to obtain the target previously allocated to the cache 28 . As the BPU 24 does not have a target stored in its branch target buffer (not shown), the BPU predicts the target obtained from the cache 28 . If, however, the BPU 24 also has a target stored in its branch target buffer, the BPU 24 will prioritize the target obtained from the cache 28 and the target obtained from the BPU branch target buffer. Once prioritized, the BPU 24 will generate a final prediction based on the prioritized targets. It is to be understood that even though numerous characteristics and advantages of various embodiments have been set forth in the foregoing description, together with details of the structure and function of the various embodiments, this disclosure is illustrative only. Changes may be made in detail, especially matters of structure and management of parts, without departing from the scope of the present invention as expressed by the broad general meaning of the terms of the appended claims.