Instruction prefetching device with prediction of a branch destination for each branch count instruction

Claim 2

An instruction prefetching device for use in carrying out prefetch of an instruction sequence in a data processing system which includes an executing unit, said instruction prefetching device comprising: a branch history table for memorizing a plurality of entry pairs, each entry pair comprising a first entry specifying an instruction address of a branch instruction executed by said executing unit prior to said prefetch and a second entry specifying branch information which comprises a predicted branch destination address obtained by previous execution of said branch instruction, said second entry corresponding to said first entry as regards each branch instruction; retrieving means for retrieving said branch history table for one of the first entries of said entry pairs in response to a current instruction address of a current instruction being prefetched to make said branch history table produce a corresponding second entry when said one of the first entries is located; discriminating means for discriminating whether said branch instruction is a branch count instruction or a general branch instruction which is not a branch count instruction, said discriminating means thereby providing a result of discrimination; and prefetching means responsive to said corresponding second entry and said result of discrimination for carrying out said prefetch.

Claim 3

An instruction prefetching device as claimed in Claim 1, wherein said prefetching means comprises: prediction evaluating means responsive to said corresponding second entry, said result of discrimination, and a result of execution of said current instruction for evaluating said corresponding second entry to produce a branch evaluation signal and a prediction evaluation signal, said branch evaluation signal being indicative of repeated execution of a loop for said branch count instruction and leave of said loop, said prediction evaluation signal being indicative of correctness and incorrectness of said corresponding second entry in view of said result of execution; and controlling means responsive to said corresponding second entry and said branch and said prediction evaluation signals for controlling said prefetch to be continued either when said branch evaluation signal indicates repeated execution of said loop or when said prediction evaluation signal indicates the correctness.

Claim 4

An instruction prefetching device as claimed in Claim 2, wherein said prefetching means further comprises: means responsive to the branch evaluation signal indicative of leave of said loop for carrying out said prefetch with said loop left; renewing means responsive to the prediction evaluation signal indicative of the incorrectness and irrespective of said branch evaluation signal for renewing said corresponding second entry to a new second entry according to said result of execution; and (Claim 3 continued) means responsive to said new second entry for carrying out said prefetch.

Claim 5

An instruction prefetching device as claimed in any of claims 1 to 3 wherein said prefetching means comprises: first means responsive to said branch count instruction for producing a loop repitition signal indicative of penultimate execution of said branch count instruction followed by ultimate execution of said branch count instruction for leave of said loop and either of said ultimate execution and repeated execution of said branch count instruction except said penultimate execution; and second means responsive to said corresponding second entry, said result of discrimination, and said loop repetition signal for carrying out said prefetch.

Claim 6

An instruction prefetching device as claimed in Claim 4, wherein: said branch history table is for memorizing the entry pairs in which the branch information specified by each second entry further comprises a predicted branch direction obtained by previous execution of a pertinent one of said branch count instruction and said general branch instruction; said prefetching means further comprising: third means responsive to either of said branch count instruction and said general branch instruction for producing an actual branch direction in which said prefetch should proceed; fourth means responsive to either of said branch count instruction and said general branch instruction for producing (Claim 5 continued) an actual branch destination address to which said prefetch should proceed; and prediction evaluating means responsive to said corresponding second entry, said actual branch direction and branch destination address, and said loop repetition signal for evaluating said corresponding second entry to produce a prediction failure signal and a branch history table renewing signal, said prediction failure signal and said branch history table renewing signal being concurrently produced for said general branch instruction either unless the predicted branch direction specified by said corresponding second entry as a specified branch direction is coincident with said actual branch direction or unless the predicted branch destination address specified by said corresponding second entry as a specified branch destination address is coincident with said actual branch destination address despite coincidence between said specified and said actual branch directions, said prediction failure signal and said branch history table renewing signal being concurrently produced for said branch count instruction when said loop repetition signal indicates said repeated execution and furthermore when said specified branch direction indicates leave of said loop despite the actual branch direction indicative of said repeated execution, only said branch history table renewing signal being produced for said branch count instruction when said loop repetition signal indicates either of said penultimate and said ultimate execution; said second means comprising: (Claim 5 further continued) means responsive to said corresponding second entry and coupled to said prediction evaluating means for continuing said prefetch when neither of said prediction failure signal and said branch history table renewing signal are produced for either of said general branch instruction and said branch count instruction; renewing means responsive to said prediction failure signal and said'branch history table renewing signal for renewing said corresponding second entry to a new second entry when the prediction failure signal and the branch history table renewing signal are concurrently produced for either of said general branch instruction and said branch count instruction-, said renewing means renewing the specified branch direction for said branch count instruction to a temporary branch direction indicative of leave of said loop and said temporary branch direction to a usual branch direction indicative of said repeated execution in response to the branch history table renewing signal produced when said loop repetition signal indicates said penultimate and said ultimate execution, respectively; and means responsive to one of said new second entry and said temporary and said usual branch directions for carrying out said prefetch.