Instruction prefetching device comprising a circuit for checking prediction for a branch instruction before the instruction is executed

Claim 2

1, An instruction prefetching device for use in combination with a data processing system including executing means for executing a sequence of instructions with each instruction processed successively in a plurality of stages which include an executing stage, said instruction prefetching device being for carrying out prefetch of at least one instruction from said sequence and including predicting means responsive to an instruction address for producing branch information obtained when a particular instruction having said instruction address was processed in said executing stage next prior to the prefetch of said particular instruction, said predicting means producing said branch information as predicted branch information, -the device comprising: prediction checking means coupled to said predicting means and said executing means for carrying out a check in at least one of said stages that is prior to said executing stage for said particular instruction, said check being as regards whether said predicted branch information is correct or incorrect; and prefetch controlling means coupled to said predicting means and said prediction checking means for allowing continuance of the prefetch of a subsequent instruction in compliance with said predicted branch information when said predicted branch information is correct, said prefetch controlling means being for correcting said continuance when said predicted branch information is incorrect, said subsequent instruction next following said particular instruction in said sequence.

Claim 3

An instruction prefetching device as claimed in Claim 1, said stages including an instruction decoding stage prior to said executing stage, wherein said prediction checking means is for carrying out said check immediately after said particular instruction is processed in said instruction decoding stage.

Claim 4

An instruction prefetching device as claimed in Claim 2, said particular instruction being processed in said instruction decoding stage to produce an actual branch direction indicative of a "no go" to branch direction and not a "go" to branch direction, said predicted branch information comprising a predicted branch direction for said particular instruction, wherein said prediction checking means is responsive to said actual branch direction for carrying out said check as regards said predicted branch direction to produce a result of check which represents whether said predicted branch direction indicates said "go" to branch direction or said "no go" to branch direction.

Claim 5

An instruction prefetching device as claimed in Claim 3, wherein said prefetch controlling means is responsive to said result of check for allowing said continuance when said result of check represents said "no go" to branch direction as said predicted branch direction, said prefetch controlling means being for correcting said predicted branch direction to said "no go" to branch direction and then allowing prefetch of a next instruction when said result of check represents said "go" to branch direction as said predicted branch direction, said next instruction next following said particular instruction in said sequence in said "no go" to branch direction.

Claim 6

An instruction prefetching device as claimed in Claims 2 to 4, said stages including an operand address generating and an operand address translating stages prior to said executing stage and successively following said instruction decoding stage, wherein said prediction checking means for carrying out said check to produce a first result of check immediately after said particular instruction is processed in said instruction decoding stage, for carrying out said check to produce a second result of check immediately after said particular instruction is processed in said operand address generating stage, and for carrying out said check in response to said first and said second results of check to produce a third result of check immediately after said particular instruction is processed in said operand address translating stage.

Claim 7

An instruction prefetching device as claimed in Claim 5, wherein said prefetch controlling means is responsive to said first through said third results of check for allowing said continuance when said first through said third results of check indicate that said predicted branch information is correct, said prefetch controlling means being for correcting said predicted branch information into corrected branch information and then allowing saidwcontinuance in compliance with said corrected branch information when at least one of said first through said third results of check indicates that said predicted branch information is incorrect.

Claim 8

An instruction prefetching device as claimed in Claim 5 or 6,. said executing means producing a branch indicating signal indicating an actual branch direction according to a result obtained when said particular instruction is processed in said executing stage, said predicted branch information comprising a predicted branch direction for said particular instruction, said instruction prefetching device including a prediction checking circuit coupled to said predicting means and said executing means and responsive to said branch indicating signal for checking said predicted branch direction to produce a final result of check indicative of whether said predicted branch direction is incoincident or coincident with said actual branch direction, wherein: said prediction checking means is for carrying out said check to produce a first result of check immediately after said particular instruction is processed in said instruction decoding s'cage, for carrying out said check to produce a second result of check immediately after said particular instruction is processed in said operand address generating stage, and for carrying out said check in response to said first and said second results of check to produce a third result of check immediately after said particular instruction is processed in said operand address translating stage; said prediction checking circuit being responsive to said first through said third results of check for producing said final result of check only when said first through said third results of check indicates that said predicted branch information is correct.

Claim 9

An instruction prefetching device as claimed in Claim 7. wherein said prefetch controlling means is responsive to said first through said third results of check for allowing said continuance when said first through said third results of check indicate that said predicted branch information is correct, said prefetch controlling means being for correcting said predicted branch information into corrected branch information and then allowing said continuance in compliance with said corrected oranch information when at least one of said first through said third results of check indicates that said predicted branch information is incorrect, said prefetch controlling means being for allowing said continuance when said final result of check indicates that said predicted branch direction is coincident with said actual branch direction, said prefetch controlling means being for correcting said predicted branch direction into said actual branch direction and then allowing said continuance in compliance with said actual branch direction.

Claim 10

An instruction prefetching device as claimed in Claim 1, said stages including an operand address generating stage prior to said executing stage, wherein said prediction checking means is for carrying out said check immediately after said particular instruction is processed in said operand address generating stage.

Claim 11

An instruction prefetching device as claimed in Claim 9, said particular instruction being processed in said operand address generating stage to produce a consequence indicative of whether said particular instruction always indicates a "go" to branch direction and never indicates a "no go" to branch direction, said predicted branch information comprising a predicted branch direction for said particular instruction, wherein said prediction checking means is responsive to said consequence for carrying out said check as regards said predicted branch direction to produce a result of check which represents whether said predicted branch direction indicates said "no go" to branch direction or said "go" to branch direction.

Claim 12

An instruction prefetching device as claimed in Claim 10, wherein said prefetch controlling means is responsive to said result of check for allowing said continuance when said result of check represents said "go" to branch direction as said predicted branch direction, said prefetch-controlling means being for correcting said predicted branch direction to said "go" to branch direction and then allowing prefetch of a next instruction when said result of check represents said "no go" to branch direction as said predicted branch direction, said next instruction next following said particular instruction in said "go" to branch direction.

Claim 13

An instruction prefetching device as claimed in Claim 9, said particular instruction being processed in said operand address generating stage to produce a variable count and a consequence indicative of whether or not said particular instruction is a branch count instruction which indicate a "go" to branch direction and a "no go" to branch direction unless and only when said variable count is equal to unity, respectively, said predicted branch information including a predicted branch direction for said branch count instruction, wherein said prediction checking means is responsive to said variable count and said consequence for carrying out said check as regards said predicted branch direction to produce a result of check which represents for said branch count instruction whether or not said predicted branch direction.indicates said "no go" to branch direction and said "go" to branch direction when said variable count is not and is equal to unity, respectively.

Claim 14

An instruction prefetching device as claimed in Claim 12, wherein said prediction checking means comprises a comparator for comparing said variable count with unity to produce a count one signal indicative of whether said variable count is not or is equal to unity, and means responsive to said count one signal and-:said consequence for carrying out said check as regards said predicted branch direction to produce said result of check with said result of check made to represent for said branch count instruction whether or not said predicted branch direction indicates said "no go" to branch direction and said "go" to branch direction when said count one signal indicates that said variable count is not and is equal to unity, respectively.

Claim 15

An instruction prefetching device as claimed in Claim 12, wherein said prediction checking means comprises a subtracter for subtracting one from said variable count to produce a count zero signal indicative of whether said variable count less one is not or is equal to zero, and means responsive to said count zero signal and said consequence for carrying out said check as regards said predicted branch direction to produce said result of check with said result of check made to represent for said branch count instruction whether or not said predicted branch direction indicates said "no go" to and said "go" to branch directions when said count zero signal indicates that said variable count less one is not and is equal to zero, respectively,

Claim 16

An instruction prefetching device as claimed in Claim 14, wherein said prefetch controlling means is responsive to said result of check for allowing said continuance when sadd result of check represents said "go" to and said "no go" to branch directions as said predicted branch direction when said variable count is not and is equal to unity, respectively, said prefetch controlling means being for correcting said predicted branch direction to said "go" to branch direction and then allowing prefetch of a branch destination instruction whenever said result of check does not represent said "go" to branch direction as said predicted branch direction, said branch destination instruction next following said branch count instruction in said sequence in said "go" to branch direction, said prefetch controlling means being for correcting said predicted branch direction to said "no go" to branch direction and then allowing prefetch of a next instruction whenever said result of check does not represent said "no go" to branch direction as said predicted branch direction, said next instruction next following said branch count instruction is said sequence in said "no go" to branch direction.

Claim 17

16, An instruction prefetching device as claimed in Claim 9, said stages including an operand address translating stage prior to said executing stage and:next following said operand address generating stage, wherein said prediction checking means is for again carrying out said check immediately after said particular instruction is precessed in said operand address translating stage,

Claim 18

An instruction prefetching device as claimed in Claim 16, said stages including an instruction decoding stage next prior to said operand address generating stage and an instruction address translating stage prior to said executing stage, said particular instruction being processed in said instruction decoding stage to produce a consequence indicative of whether said particular instruction indicates a next instruction or a branch destination instruction, said next instruction next following said particular instruction in said sequence in a "no go" to branch direction, said branch destination instruction next following said particular instruction in said sequence in a "go" to branch direction, said branch destination instruction being processed in said instruction address translating stage to produce a decoded branch destination address concurrently when said particular instruction is processed in said operand address translating stage, said predicted branch information comprising a predicted branch direction for said particular instruction and a predicted destination address of said branch destination instruction, wherein said prediction checking means comprises: first means responsive to said consequence for carrying out said check as regards said predicted branch direction to produce one of a first and a second result of check at a time, , said first result of check representing whether or not said predicted branch direction indicates said predicted branch direction indicates said "go" to branch direction when said particular instruction indicates said next instruction, said second result of check representing whether or not said predicted branch direction indicates said "no go" to branch direction when said particular instruction indicates said branch destination instruction; and second means responsive to said decoded branch destination address and said first and said second results of check for carrying out said check as regards said predicted destination address to produce a third result of check which represents whether said predicted destination address is incoincident or coincident with, said decoded branch destination address if said first result of check does not represent said "go" to branch direction as said predicted branch direction when said particular instruction indicates said next instruction and if said second result of check does not represent said "no go" to branch direction as said predicted branch direction when said particular instruction indicates said branch destination instruction, said second means being quiescent if said first result of check represents said "no'go" to branch direction as said predicted branch direction when said particular instruction indicates said branch destination instruction and if said second result of check represents said "go" to branch direction as said predicted branch direction when said particular instruction indicates said next instruction.

Claim 19

18, An instruction prefetching device as claimed in Claim 17, wherein said prefetch controlling means is responsive to said first through said third results of check for allowing said continuance if said first result of check does not represent said "go" to branch direction as said predicted branch direction when said particular instruction indicates said next instruction and for allowing said continuance if said second result of check does not represent said "no go" to branch direction as said predicted branch direction when said particular instruction indicates said branch destination instruction and furthermore if said third result of check represents coincidence between said predicted destination address and said decoded branch destination address, said prefetch controlling means being for correcting said predicted branch direction to said "no go" to branch direction and then allowing prefetch of said next instruction if said first result of check represents said "go" to branch direction as said predicted branch direction when said particular instruction indicates said next instruction, said prefetch controlling means being for correcting said predicted destination address to said decoded branch destination address and = then allowing prefetch of said branch destination instruction if said first result of check does not represent said "go" to branch direction as said predicted branch direction when said particular instruction indicates said branch destination instruction and furthermore if said third result of check represents coincidence between said predicted destination address and said decoded branch destination address, said prefetch controlling means being for correcting said predicted branch direction to said "go" to branch direction and then allowing prefetch of said branch destination instruction if said second result of check does not represent said "no go" to branch direction as said predicted branch direction when said particular instruction indicates said branch destination instruction and furthermore if said third result of check represents coincidence between said predicted destination address and said decoded branch destination address.

Claim 20

An instruction prefetching device as claimed in Claim 1, said stages including an operand address translating stage prior to said executing stage, wherein said prediction checking means is for carrying out said check immediately after said particular instruction is processed in said operand address translating stage.

Claim 21

20, An instruction prefetching device as claimed in Claim 19, said stages including an instruction decoding stage prior to said operand address translating stage and an instruction address translating stage prior to said executing stage, said particular instruction being processed in said instruction decoding stage to produce a consequence indicative of whether said particular instruction indicates a next instruction or a branch destination instruction, said next instruction next following said particular instruction in said sequence in a "no go" to branch direction, said branch destination instruction next following said particular instruction in said sequence in a "go" to branch direction, said branch destination instruction being processed in said instruction translating stage to produce a decoded branch destination address concurrently when said particular insstruction is processed in said operand address translating stage, said predicted.:branch information comprising a predicted branch direction for said particular instruction and a predicted destination address of said branch destination instruction, wherein said prediction checking means comprises: first means responsive to said consequence for carrying out said check as regards said predicted branch direction to produce one of a first and a second result of check at a time, said first result of check representing whether or not said predicted branch direction indicates said "go" to branch direction when said particular instruction indicates said next instruction, said second result of check representing whether or not said predicted branch direction indicates said "no go" to branch direction when said particular instruction indicates said branch destination instruction; and second means responsive to said decoded branch destination address and said first and said second results of check for carrying out said check as regards said predicted destination address to produce a third result of check which represents whether said predicted destination address is incoincident or coincident with said decoded branch destination address if said first result of check does not represent said "go" to branch direction as said predicted branch direction when said particular instruction indicates said next instruction and if said second result of check does not represent said "no go" to branch derection as said predicted branch direction when said particular instruction indicates said branch destination instruction, said second means being quiescent if said first result of check represents said "no go" to branch direction as said predicted branch direction when said particular instruction indicates said branch destination instruction and if said second result of check represents said "go" to branch direction as said predicted branch direction when said particular instruction indicates said next instruction.

Claim 22

An instruction prefetching device as claimed in Claim 20, wherein said prefetch controlling means is responsive to said first through said third results of check for allowing said continuance if said first result of check does not represent said "go" to branch direction as said predicted branch direction when said particular instruction indicates said next instruction and for allowing said continuance if said second result of check does not represent said "no go" to branch direction as said predicted branch direction when said particular instruction indicates said branch destination instruction and furthermore if said third result of check represents coincidence between said predicted destination address and said zecoded branch destination address, said prefetch controlling means being for corresting said predicted branch direction to said "no go" to branch direction and then allowing prefetch of said next instruction if said first result of check represents said "go" to branch direction as said predicted branch direction when said particular instruction indicates said next instruction, said prefetch controlling means being for correcting said predicted destination address to said decoded branch destination address and then allowing prefetch of said branch destination instruction if said first result of check does not represent said "go" to branch direction as said predicted branch direction when said particular instruction indicates said branch destination instruction and furthermore if said third result of check represents coincidence between said predicted destination address and said decoded branch destination address, said prefetch controlling means being for correcting said predicted branch,.direction to said "go" to branch direction and then allowing prefetch of said branch destination instruction if said second result of check does not represent said "no go" to branch direction as said predicted branch direction when said particular instruction indicates said branch destination instruction and furthermore if said third result of check represents coincidence between said predicted destination address and said decoded branch destination address.