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: 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, 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 and 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.