US 6,289,444 B1Granted

Method and apparatus for subroutine call-return prediction

AssigneeInternational Business Machines Corporation

InventorRavindra K. Nair

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method for associating subroutine calls with corresponding targets includes the step of maintaining a first table of entries. Each entry in the first table includes: a first table first address identifying an entry point address for a corresponding subroutine; and a first table second address identifying a return address of a return for the corresponding subroutine. A second table of entries is also maintained. Each entry in the second table includes: a second table first address identifying a return address of a return for a respective subroutine called by a corresponding subroutine call instruction; a second table second address identifying a target address of the return for the respective subroutine; and a second table third address identifying an entry point address for the respective subroutine. It is determined whether the second table stores an entry whose second table first address corresponds to a return address of a return for a considered subroutine. If so, a target address of the return for the considered subroutine is predicted to be the second table second address of the corresponding entry.

Claims20

Dependent claims

A method for associating subroutine return branches with corresponding targets, comprising the steps of:

storing in a first table a plurality of entries for at least one subroutine that has been executed, wherein each entry in the first table comprises:
a first table first address identifying an entry point address for a corresponding subroutine and
a first table second address identifying a return address of a return for the corresponding subroutine;
upon generation of a target address for a subroutine call instruction associated with a subroutine, in a second table, building a new entry for the subroutine call instruction and updating an in pointer of the second table to point to the new entry, wherein each entry in the second table comprises:
a second table first address identifying a return address of a return for a respective subroutine called by a corresponding subroutine call instruction,
a second table second address identifying a target address of the return for the respective subroutine, and
a second table third address identifying an entry point address for the respective subroutine, said building step comprising the steps of:
setting a second table second address of the new entry to an address corresponding to a sum of the subroutine call instruction and one instruction;
setting a second table third address of the new entry to the target address for the subroutine call instruction;
determining whether the first table stores an entry whose first table first address matches the target address for the subroutine call instruction;
and
if so, setting a second table first address of the new entry to the first table second address of the matching entry.

9 more elements

A method for associating subroutine calls with corresponding targets, comprising the steps of:

maintaining a first table of entries, wherein each entry in the first table comprises:
a first table first address identifying an entry point address for a corresponding subroutine and
a first table second address identifying a return address of a return for the corresponding subroutine;
maintaining a second table of entries, wherein each entry in the second table comprises:
a second table first address identifying a return address of a return for a respective subroutine called by a corresponding subroutine call instruction,
a second table second address identifying a target address of the return for the respective subroutine, and
a second table third address identifying an entry point address for the respective subroutine,
determining whether the second table stores an entry whose second table first address corresponds to a return address of a return for a considered subroutine;
if so, predicting a target address of the return for the considered subroutine to be the second table second address of the corresponding entry.

6 more elements

Dependencies are inferred from the claim text.