A branch instruction includes a set of branch prediction information 13b and a set of branch history information 13c. The set of branch prediction information 13b is made up of 1 bit which predicts whether a branch will be performed during the next execution of the instruction. The set of branch history information 13c is made up of 2 bits showing a frequency, with which the branch has been taken, is "very high", "high", "low" or "very low". An instruction fetching unit 12 prefetches an instruction from a cache memory 11a in accordance with the set of branch prediction information 13b. After an instruction executing unit 15 completes an execution of the branch instruction, a branch history information generating unit 16 generates a new set of branch history information and a branch prediction information generating unit 17 generates a new set of branch prediction information, in accordance with the execution result and the preceding branch history information 13c. A branch instruction updating unit 18 overwrites the generated set of branch history information and the generated set of branch prediction information on the corresponding branch instruction stored in the main memory 11a.