Patent ID: 7757071

Claim:
A branch predicting apparatus that makes a branch prediction in a pipeline processor, the branch predicting apparatus comprising: a branch predicting unit that stores execution history information on a branch instruction that includes a return address in response to a return instruction that corresponds to a call instruction, and that performs the branch prediction based on the execution history information; a first return-address storage unit that stores, when the branch predicting unit predicts presence of the call instruction in a sub-routine, a return address in response to the return instruction that corresponds to the call instruction in a first-in last-out manner; a second return-address storage unit that stores, when the call instruction in the sub-routine is executed, a return address in response to the return instruction that corresponds to the call instruction in the sub-routine in the first-in last-out manner; a return stack pointer that points to an entry that stores a return address to be output; an output selecting unit that selects an appropriate return address from return addresses stored in the branch predicting unit, the return address stored in the first return-address storage unit, and the return address stored in the second return-address storage unit, and that outputs the return address selected; a valid-entry designating unit that designates either of an entry of the first return-address storage unit and an entry of the second return-address storage unit as a valid entry at a point in time, wherein the output selecting units outputs, when the branch predicting unit predicts presence of the return instruction, the return address stored in the entry of the first return-address storage unit or the second return-address storage unit, designated by the valid-entry designating unit and then the valid-entry designation unit turns OFF the valid entry designation of the first return-address storage unit or of the second return-address storage unit that stored the return address last output by the output selecting unit; and the output selecting unit outputs, when the entry of the first return-address storage unit or the entry of the second return-address storage unit is pointed by the return stack pointer and neither the entry of the first return-address storage unit nor the entry of the second return-address storage unit is designated as a valid entry by the valid-entry designating unit, the return address stored in the branch predicting unit.