Browse Prior Art Database

METHOD AND APPARATUS FOR RAPID RETURN ADDRESS COMPUTATION IN BINARY TRANSLATION

IP.com Disclosure Number: IPCOM000016715D
Original Publication Date: 2003-Jul-10
Included in the Prior Art Database: 2003-Jul-10
Document File: 3 page(s) / 46K

Publishing Venue

IBM

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 3

  METHOD AND APPARATUS FOR RAPID RETURN ADDRESS COMPUTATION IN BINARY TRANSLATION

Address space mapping between the original (emulated) instruction address space to translated (native) code is an important function in binary translation. Previous binary translation systems have used lookup tables to support mapping between emulated and native instruction address space. These lookup tables can be supported with appropriate hardware structures or implemented using software only.

While such a translation scheme is appropriate for general branches such as PC-relative branches, register indirect branches, or function invocation, such implementation is inappropriate for function call return. Using such mechanism does not preserve the predictability of function call return information, and thus leads to performance penalties.

To improve the performance of function call linkage in a binary translation environment, the present invention uses a hardware return address stack for binary translation architectures. The invention consists of:

A function return stack, storing the return addresses of the original emulated address space and of the host address space, one or more instructions to record both the original and translated address space return address on the function return stack (executed when control is transferred to a subroutine), and one or more instructions to effect a function return using the information stored on the function return stack (executed to determine the subroutine return address upon function exit).

The instructions to manipulate the function return stack can work either by explicit manipulation of such stack, or the functionality can be performed as a non-architected optimization to improve performance of address space mapping. (The latter method is common for native function return stack implementations used for branch prediction.)

Using a return address stack to maintain the address space mapping allows to capture function call returns with only a few entries. By comparison, a hardware based caching mechanism for translation tables as previously disclosed in IBM Invention Disclosure Docket Number YOR8-1998-0334, incurs compulsory misses for the first use of each translation. Additional misses are incurred when the entry is displaced by a mapping in the same congruence class.

A hardware return stack requires only a few entries, yielding a high translation accuracy rate with low hardware cost. Experiments have shown that using a return address stack reduces the number of entries which need to be stored in a lookup table, when a hybrid scheme is used which employs hardware-cached lookup tables for general branches and a return stack for function return.

1

Page 2 of 3

Unlike native address return stacks which are used to increase prediction accuracy of branch prediction, the present invention is used as authoritative return address information. To ensure correct operation in the pres...