Computer system branch prediction of subroutine returns

Claim 2

A computer system method for the prediction of branch instruction target addresses for subroutine returns, comprising the steps of: saving subroutine return addresses within a series of storage locations; storing first data as a prediction pointer representative of the location of a first one of said series of storage locations, wherein a next subroutine prediction address to be used for predicting a return address from a subroutine is saved in said first one of said series of storage locations; storing second data as an update pointer representative of the location of a second one of said series of storage locations, wherein said update pointer is used to modify the prediction pointer in the event of an incorrect prediction of said return address from said subroutine; from a series of executable instructions having instruction opcodes, determining potential subroutine call instructions by identifying those instructions having opcodes corresponding to potential call instructions; from a series of executable instructions having instruction opcodes, determining potential subroutine return instructions by identifying those instructions having opcodes corresponding to potential return instructions; and verifying if a predicted address is correct by completing execution of potential call instructions or potential return instructions and comparing an address of an actual next instruction to be executed with said predicted address.

Claim 3

The method of claim 1 including a step for recording branch history of potential subroutine return instructions and/or a step for saving a status of pending potential subroutine return branch instructions.

Claim 4

The method of claim 2 where said step for saving status of pending branch instructions uses a branch queue.

Claim 5

The method of claim 3 where said branch queue contains the predicted target address for one or more pending branch instructions.

Claim 6

The method of claim 3 where said branch queue contains a bit indicating whether the return instruction was predicted using said branch history step or said subroutine address step for one or more pending return instructions.

Claim 7

The method of claim 2 where said step for recording branch history of subroutine instructions records the history in a branch history table.

Claim 8

The method of claim 2 whereby a potential return instruction not identified by said branch history step is predicted using said subroutine address saving step.

Claim 9

The method of claim 2 whereby a potential return instruction identified by said branch history step is predicted using said branch history step.

Claim 10

The method of claim 2 where said step for recording branch history of subroutine instructions stores history bits in an instruction cache of the computer system.

Claim 11

The method of claim 2 whereby a potential return instruction identified by said branch history step is predicted using said subroutine address saving step.

Claim 12

The method of claim 2 whereby a potential return instruction not identified by said branch history step is predicted using said branch history step.

Claim 13

The method of claim 2 where an entry is created in said branch history step for a potential subroutine instruction only if the instruction was predicted incorrectly using said subroutine address saving step.

Claim 14

The method of claim 1 comprising the following: if a branch instruction to be predicted is identified by said step which determines a potential subroutine call instruction, saving the return address in said saving step in one of said series of storage locations represented by said prediction pointer and updating said prediction pointer by modifying said prediction pointer so as to represent another of said series of storage locations; if a branch instruction to be predicted is identified by said step which determines a potential subroutine return instruction, the predicted address is determined by using the address in said saving step indicated by said prediction pointer and updating said prediction pointer by modifying said prediction pointer so as to represent another of said series of storage locations; if the instruction execution is to be completed for a branch instruction identified by said step which determines a potential subroutine call instruction, updating said update pointer by modifying said update pointer so as to represent another of said series of storage locations; if the instruction execution is to be completed for a branch instruction identified by said step which determines a potential subroutine return instruction that was predicted correctly, updating said update pointer by modifying said update pointer so as to represent another of said series of storage locations; if the instruction execution is to be completed for any branch instruction predicted incorrectly, updating said prediction pointer so as to correspond to said update pointer.

Claim 15

The method of claim 13 where updating said prediction pointer is done by incrementing.

Claim 16

The method of claim 13 where updating said prediction pointer is done by decrementing.

Claim 17

The method of claim 13 where updating said update pointer is done by incrementing.

Claim 18

The method of claim 13 where updating said update pointer is done by decrementing.

Claim 19

The method of claim 13 where updating said prediction pointer on a wrong prediction is done by copying to said prediction pointer from said update pointer.

Claim 20

The method of claim 13 where two branches are predicted at a time.

Claim 21

The method of claim 13 where two branches are updated at a time.

Claim 22

The method of claim 13 where conditional potential subroutine returns are handled like other branches and not like potential subroutine return branches.

Claim 23

The method of claim 1 where said step for saving subroutine return addresses uses a plurality of return address registers, forming a register bank.

Claim 24

The method of claim 1 where said step for saving subroutine return addresses uses a single register; in which case there is no need for said step for storing first data as a prediction pointer and said step for storing second data as an update pointer.

Claim 25

The method of claim 1 where said step for storing first data as a prediction pointer uses a register.

Claim 26

The method of claim 1 where said step for storing second data as an update pointer uses a register.

Claim 27

The method of claim 1 where said step which determines a potential subroutine call instruction is performed by decode logic that examines the instruction.

Claim 28

The method of claim 1 where said step which determines a potential subroutine return instruction is performed by decode logic that examines the instruction.

Claim 29

The method of claim 1 where said prediction verification step uses a comparator comparing said predicted address and a correct address.

Claim 30

A computer system, comprising: a main memory 101; a second level cache 102 connected to said main memory; an execution unit 108; a first level data cache 104 coupled between said second level cache and said execution unit; and a first level instruction cache 103; said second level cache being connected to said first level data cache and adapted to transmit instructions to said first level instruction cache; an instruction buffer 105 connected to said first level instruction cache and adapted to transmit instructions to said execution unit and to a branch unit 107; said branch unit having bidirection communication to said instruction buffer and to said execution unit and adapted to transmit instruction addresses to said instruction cache; and said branch unit comprises a system mechanism for the prediction of branch instruction target addresses for subroutine returns including: means for saving subroutine return addresses within a series of storage locations; means for storing first data as a prediction pointer representative of the location of a first one of said series of storage locations, wherein a next subroutine prediction address to be used for predicting a return address from a subroutine is saved in said first one of said series of storage locations; means for storing second data as an update pointer representative of the location of a second one of said series of storage locations, wherein said update pointer is used to modify the prediction pointer in the event of an incorrect prediction of said return address from said subroutine; means for determining, from a series of executable instructions having instruction opcodes, potential subroutine call instructions by identifying those instructions having opcodes corresponding to potential call instructions; means for determining, from a series of executable instructions having instruction opcodes, potential subroutine return instructions by identifying those instructions having opcodes corresponding to potential return instructions; and means for verifying if a predicted address is correct by comparing, upon completion of execution of potential call instructions or potential return instructions, an address of an actual next instruction to be executed with said predicted address.

Claim 31

A computer system, comprising: a main memory 101; a second level cache 102 connected to said main memory; an execution unit 108; a first level data cache 104 coupled between said second level cache and said execution unit; and a first level instruction cache 103; said second level cache being connected to said first level data cache and adapted to transmit instructions to said first level instruction cache; an instruction buffer 105 connected to said first level instruction cache and adapted to transmit instructions to said execution unit and to a branch unit 107; said branch unit having bidirection communication to said instruction buffer and to said execution unit and adapted to transmit instruction addresses to said instruction cache; and said branch unit comprises a system mechanism for the prediction of branch instruction target addresses for subroutine returns including: means for saving subroutine return addresses within a series of storage locations; means for storing first data as a prediction pointer representative of the location of a first one of said series of storage locations, wherein a next subroutine prediction address to be used for predicting a return address from a subroutine is saved in said first one of said series of storage locations; means for storing second data as an update pointer representative of the location of a second one of said series of storage locations, wherein said update pointer is used to modify the prediction pointer in the event of an incorrect prediction of said return address from said subroutine; means for determining, from a series of executable instructions having instruction opcodes, potential subroutine call instructions by identifying those instructions having opcodes corresponding to potential call instructions; means for determining, from a series of executable instructions having instruction opcodes, potential subroutine return instructions by identifying those instructions having opcodes corresponding to potential return instructions; and means for verifying if a predicted address is correct by comparing, upon completion of execution of potential call instructions or potential return instructions, an address of an actual next instruction to be executed with said predicted address.

Claim 32

A computer system according to claim 29 wherein said means for saving subroutine return addresses includes one or more registers.

Claim 33

A computer system according to claim 29 wherein said means for storing first data as a prediction pointer includes a register for indexing into said means for saving subroutine addresses.

Claim 34

A computer system according to claim 29 wherein said means for storing second data as an update pointer includes a register for indexing into said means for saving subroutine addresses.

Claim 35

A computer system according to claim 29 wherein said means for determining potential subroutine call instructions includes logic to examine an instruction in an instruction buffer.

Claim 36

A computer system according to claim 29 wherein said means for determining potential subroutine return instructions includes logic to examine an instruction in an instruction buffer.

Claim 37

A computer system according to claim 29 wherein said means for verifying if a predicted address is correct includes a comparator.