Method, apparatus and compiler for predicting indirect branch target addresses
OwnerJan Hoogerbruggeinventor
Life of this patent
Estimating the term…
Abstract
The present invention relates to a method, processor and compiler for predicting a branch target of a program. A hint operation is provided in the program to hint the branch prediction about upcoming indirect branches. A table of branch targets of indirect branches can be used to improve prediction accuracy of indirect branches. The branch target is determined on the basis of a key information derived from the hint operation.
Claims15
A method of predicting a branch target of a program, said method comprising the steps of:
- a) providing a branch target table (104) comprising a plurality of branch targets;
- b) using a hint operation in said program for deriving a key information;
- and
- c) selecting said branch target from said branch target table (104) based on said key information.
A method according to anyone of the preceding claimsclaim 1, wherein said hint operation is incorporated into a VLIW instruction.
A method according to anyone of the preceding claimsclaim 1, wherein said key information is hashed with the address of the branch instruction or the instruction incorporating said hint operation, to obtain an index used to access said branch target table (104).
A method according to anyone of the preceding claims, wherein said branch target table is an indirect branch target buffer (104) comprising branch targets for indirect branches.
A method according to anyone of the preceding claimsclaim 1, wherein said hint operation is provided at a predetermined location of said program, said predetermined location being selected such that the hint operation is in an execution phase of an instruction execution cycle when the corresponding branch instruction is in a fetch phase of the instruction execution cycle.
A method according to anyone of the preceding claimsclaim 1, wherein said prediction method is used to predict a branch target of an indirect branch resulting from a function pointer.
A method according to anyone of the preceding claimclaim 1, further comprising the step of storing in said branch target table most recently used entries of jump tables and/or virtual function tables.
A method according to anyone of the preceding claimsclaim 1, wherein said prediction method is a compiler synthesized dynamic branch prediction method.
A processor for predicting a branch target of a program, said processor comprising:
- a) branch target buffer means (104) for storing a plurality of branch targets;
- b) decoding means (4) for detecting a hint operation of said program and for deriving a key information from said hint operation;
- c) access means (102) for accessing said branch target buffer means (104) using said key information to select said branch target.
A compiler for predicting a branch target of a program, wherein said compiler is arranged to detect a hint operation of said program, to derive a key information from said hint operation, and to determine said branch target based on said key information.
Dependencies are inferred from the claim text.