System and method for using a branch mis-prediction buffer

1. A system for executing conditional branch instructions, the system comprising:

a branch mis-prediction buffer;

a processor to execute sequential pipeline stages of instructions;

a branch predictor to predict one or more predicted instructions that depend on a conditional branch instruction during execution of the sequential pipeline stages;

a program memory; and

a fetch unit to retrieve the one or more predicted instructions from the program memory during execution of the sequential pipeline stages;

wherein the processor is further to:

during execution of the sequential pipeline stages, search the branch mis-prediction buffer for decoded non-predicted instructions that were not predicted by the branch predictor and if the decoded non-predicted instructions are found in the branch mis-prediction buffer, retrieve the decoded non-predicted instructions from the branch mis-prediction buffer simultaneously with retrieval of the one or more predicted instructions from the program memory;

determine actual branch direction of the branch instruction;

if the one or more predicted instructions are correct, decode the one or more predicted instructions; and

if the one or more predicted instructions are not correct and the decoded non-predicted instructions are found in the branch mis-prediction buffer, execute the decoded non-predicted instructions retrieved from the branch mis-prediction buffer;

wherein, if the one or more predicted instructions are not correct and the decoded non-predicted instructions are not found in the branch mis-prediction buffer:

the fetch unit to retrieve one or more non-predicted instructions from the program memory,

the processor to dispatch and decode the one or more non-predicted instructions, and

the branch mis-prediction buffer to store the one or more decoded non-predicted instructions retrieved from the program memory for use in subsequent conditional branch instructions.

2. The system of claim 1 , wherein the branch mis-prediction buffer stores instructions using a least recently used (LRU) algorithm.

3. The system of claim 1 , wherein the branch mis-prediction buffer stores all instructions of a loop.

4. The system of claim 1 , comprising:

a branch mechanism to determine that an instruction is a conditional branch instruction.

5. The system of claim 1 , wherein the one or more predicted instructions retrieved from the program memory and the decoded non-predicted instructions retrieved from the branch mis-prediction buffer are both available to the processor in a same computational cycle.

6. The system of claim 1 , wherein the one or more predicted instructions may be any one of multiple different instructions.

7. A method for executing a conditional branch instruction, the branch instruction is associated with one or more predicted instructions that are predicted to follow the conditional branch instruction and one or more non-predicted instructions, the method comprising:

retrieving the one or more predicted instructions from a program memory;

retrieving the one or more decoded non-predicted instructions from a branch mis-prediction buffer that stores previously used decoded non-predicted instructions that were not predicted during a previous branch mis-prediction, wherein retrieving the one or more decoded non-predicted instructions from the branch mis-prediction buffer is being performed simultaneously with retrieving the one or more predicted instructions from the program memory; and

if a current branch mis-prediction occurs, executing the decoded non-predicted instructions retrieved from the branch mis-prediction buffer.

8. The method of claim 7 , further comprising:

retrieving one or more new non-predicted instructions from the program memory when another branch mis-prediction occurs and the one or more non-predicted instructions are not stored in the branch mis-prediction buffer.

9. The method of claim 8 , further comprising dispatching, decoding and storing the one or more new non-predicted instructions retrieved from the program memory in the branch mis-prediction buffer.

10. The method of claim 7 , wherein the one or more non-predicted instructions are executed after the conditional branch instruction is executed.

11. The method of claim 7 , wherein the branch mis-prediction buffer stores instructions using a least recently used (LRU) algorithm.

12. The method of claim 7 , comprising storing all instructions of a loop in the branch mis-prediction buffer and retrieving the loop instructions from the branch mis-prediction buffer when the branch instruction is a loop instruction.

13. A method for storing instructions in a branch mis-prediction buffer, the method comprising:

retrieving from a program memory one or more first predicted instructions that depend on a conditional branch instruction;

determining that a current branch mis-prediction has occurred and that the first one or more predicted instructions are incorrect;

retrieving a correct one or more non-predicted instructions from the program memory;

temporarily storing the correct one or more non-predicted instructions in a program cache for use in the current branch mis-prediction;

decoding the correct one or more non-predicted instructions from the program cache following the conditional branch instruction;

storing the decoded correct one or more non-predicted instructions in the branch mis-prediction buffer for use in subsequent branch mis-predictions; and

in a subsequent branch mis-prediction:

retrieving from the program memory one or more predicted instructions that depend on a subsequent conditional branch instruction; and

retrieving one or more decoded non-predicted instructions associated with the subsequent conditional branch instruction and stored in the branch mis-prediction buffer simultaneously with retrieving from the program memory the one or more predicted instructions that depend on the subsequent conditional branch instruction;

determining actual branch direction of the subsequent conditional branch instruction;

if the one or more predicted instructions are correct, decoding the one or more predicted instructions; and

if the one or more predicted instructions are not correct and the decoded non-predicted instructions associated with the subsequent conditional branch instruction are found in the branch mis-prediction buffer, executing the decoded non-predicted instructions associated with the subsequent conditional branch instruction retrieved from the branch mis-prediction buffer.

14. The method of claim 13 , comprising storing all instructions of a loop in the branch mis-prediction buffer and retrieving the loop instructions when the loop is taken.

15. The method of claim 13 , wherein the branch mis-prediction buffer stores instructions using a least recently used (LRU) algorithm.

16. The method of claim 13 , wherein the one or more second predicted instructions retrieved from the program memory and the decoded non-predicted instructions retrieved from the branch mis-prediction buffer are both available to a processor in a same computational cycle.