A branch history stores execution history information of branch instructions, and predicts presence of a branch instruction and a corresponding branch destination. A first return address stack stores, when an execution of a call instruction of a subroutine is completed, address information of a return destination of a corresponding return instruction. A second return address stack stores, when presence of a call instruction of a subroutine is predicted, address information of a return destination of a corresponding return instruction. An output selecting unit selects, when presence of a return instruction is predicted, if address information is stored in the second return address stack, the address information as a result of the branch prediction with a highest priority, and outputs the address information selected.