Patent ID: 7320066

Claim:
A branch predicting apparatus that performs a branch prediction in a pipeline processor, the branch predicting apparatus comprising: a branch history that stores execution history information of branch instructions including a call instruction and a return instruction, and searches through the execution history information to predict presence of a branch instruction and a branch destination corresponding to the branch instruction; a first return address stack that stores, when an execution of a call instruction of a subroutine is completed, address information of a return destination of a return instruction corresponding to the call instruction; a second return address stack that stores, when presence of a call instruction of a subroutine is predicted by the branch history, address information of a return destination of a return instruction corresponding to the call instruction; and an output selecting unit that selects, when presence of a return instruction is predicted by the branch history, if address information is stored in the second return address stack, the address information stored in the second return address stack as a result of the branch prediction, and outputs the address information selected, wherein the second return address stack expels an oldest piece of address information when an execution of any one of the call instructions is completed.