Method and system for implementing subroutine calls and returns in binary translation sub-systems of computers

• US 6,711,672 B1
• Filed: 09/22/2000
• Issued: 03/23/2004
• Est. Priority Date: 09/22/2000
• Status: Expired due to Term

• Current Assignee: VMware, Inc. (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Agesen, Ole
• Primary Examiner(s): TSAI, HENRY
• Application Number:
  US09/668,091
• Time in Patent Office: 1,278 Days
• Field of Search: 712/242, 712/243, 712/244, 712/231, 712/241, 712/202, 712/203, 712/32, 712/208, 712/209, 712/211, 712/215, 712/226, 712/228, 712/227, 712/229
• US Class Current: 712/227
• CPC Class Codes: G06F 2212/451 Stack data
• CPC Class Codes: G06F 8/52 Binary to binary
• CPC Class Codes: G06F 9/4484 Executing subprograms

Abstract

A sequence of input language (IL) instructions of a guest system is converted, for example by binary translation, into a corresponding sequence of output language (OL) instructions of a host system, which executes the OL instructions. In order to determine the correct return address after any IL call to a subroutine, the corresponding OL return address is stored in an array at a location determined by a hash function. After completion of execution of the OL translation of the IL subroutine, execution is transferred to the address stored in the array at the location where the correct OL return address was previously stored. This location may have been overwritten by some other OL return address. This transfer will therefore be to one of three places: 1) either back to the correct OL call site, in which case execution may continue as normal; 2) directly to a back-up return address recovery module; or 3) to an incorrect OL call site (created upon translation of some other IL subroutine call), in which case execution is transferred to the back-up recovery module. A confirmation instruction block is included in each OL call site to determine whether the transfer was to the correct or incorrect call site.

Claims

1. A method for implementing subroutine calls and returns in a computer system comprising the following steps:

A) converting a sequence of input language (IL) instructions of a guest system into a corresponding sequence of output language (OL) instructions of a host system;

B) executing the OL instructions in the host system;

C) for each call to an IL subroutine made from an IL call site in the IL instruction sequence;

i) storing a correct IL return address R on a stack;

ii) calculating a first hint index by evaluating a predetermined hint function with R as an argument;

iii) storing a corresponding correct OL return address R′

in a return target cache at a location determined by the first hint index;

iv) executing an OL subroutine translation of the called IL subroutine;

D) upon completion of execution of the OL subroutine translation;

i) retrieving a current value from the stack;

ii) calculating a second hint index by evaluating the hint function with the value retrieved from the stack as the argument;

iii) retrieving a target address from a location in the return target cache determined by the second hint index; and

iv) continuing execution beginning at the target address.

2. A method as in claim 1, further including the following steps:

if the target address is not the correct OL return address, transferring execution to a back-up return address recovery module; and

in the back-up return address recovery module, reconstructing the correct OL return address using a predetermined, secondary address recovery routine.

3. A method as in claim 2, in which there is a plurality of IL call sites, further including the following steps:

translating each IL call site into a corresponding OL call site;

inserting a confirmation block of instructions into each OL call site;

upon execution of any confirmation block of instructions;

comparing the value retrieved from the stack with the correct IL return address corresponding to the current OL call site;

if the value retrieved from the stack is equal to the correct IL return address, continuing execution of the OL instructions following the OL call site; and

if the value retrieved from the stack is not equal to the correct IL return address, transferring execution to the back-up return address recovery module.

4. A method as in claim 2, in which the return target cache is an array having a plurality of elements, further including the step of initializing the return target cache by storing in each element a beginning address of the back-up return address recovery module.

5. A method as in claim 1, in which:

the return target cache is an array having a plurality of elements; and

the hint function maps IL return addresses substantially uniformly over the return target cache.

6. A method as in claim 5, in which:

each of the elements of the return target cache is identified by an array index; and

the hint function forms a bitwise logical AND between bits of the IL return address R and a predetermined constant.

7. A method as in claim 1, in which:

the return target cache is an array having a plurality of elements;

the hint function maps IL return addresses substantially uniformly over the return target cache;

equality and inequality between the value retrieved from the stack and the correct IL return address are defined as a hit and a non-hit, respectively;

further including the following steps;

calculating a return success measure as a predetermined function of the frequency of occurrence of hits relative to the frequency of occurrence of non-hits;

adjusting the number of elements in the return target cache according to a predetermined function of the return success measure.

8. A method as in claim 1, in which the step of calculating the first hint index is performed as part of the step of converting the sequence of IL instructions into the corresponding sequence of OL instructions.

9. A method for implementing subroutine calls and returns in a computer system comprising the following steps:

A) converting a sequence of input language (IL) instructions of a guest system into a corresponding sequence of output language (OL) instructions of a host system;

B) executing the OL instructions in the host system;

C) for each call to an IL subroutine made from any of a plurality of IL call sites in the IL instruction sequence;

i) storing a correct IL return address R on a stack;

ii) calculating a first hint index by evaluating a predetermined hint function with R as an argument;

iii) storing a corresponding correct OL return address R′

in a return target cache at a location determined by the first hint index, the return target cache comprising an array of elements;

iv) executing an OL subroutine translation of the called IL subroutine;

D) upon completion of execution of the OL subroutine translation;

i) retrieving a current value from the stack;

ii) calculating a second hint index by evaluating the hint function with the value retrieved from the stack as the argument;

iii) retrieving a target address from a location in the return target cache determined by the second hint index; and

iv) continuing execution beginning at the target address;

E) if the target address is not the correct OL return address, transferring execution to a back-up return address recovery module;

F) in the back-up return address recovery module, reconstructing the correct OL return address using a predetermined, secondary address recovery routine;

G) translating each IL call site into a corresponding OL call site;

H) inserting a confirmation block of instructions into each OL call site and, upon execution of any confirmation block of instructions;

i) comparing the value retrieved from the stack with the correct IL return address corresponding to the current OL call site;

ii) if the value retrieved from the stack is equal to the correct IL return address, continuing execution of the OL instructions following the OL call site; and

iii) if the value retrieved from the stack is not equal to the correct IL return address, transferring execution to the back-up return address recovery module.

10. A system for implementing subroutine calls and returns in a computer system comprising:

A) a host computer system that executes host instructions in an output language OL;

B) a guest system that is operatively connected to the host system;

C) a binary translator converting a sequence of input language (IL) instructions of the guest system into a corresponding sequence of the output language (OL) instructions of the host system and storing the OL instructions in a translation cache,

D) the binary translator forming means for inserting a call block and a launch block into the sequence of OL instructions,

E) the call block, upon each call to an IL subroutine from an IL call site in the IL instruction sequence forming means

i) for storing a correct IL return address R on a stack;

ii) for determining a first hint index by evaluating a predetermined hint function with R as an argument; and

iii) for storing a corresponding correct OL return address R′

in a return target cache at a location determined by the hint index;

iv) for transferring execution to the OL subroutine translation of the called IL subroutine;

F) the launch block, upon completion of execution of the OL subroutine translation, forming means

i) for retrieving a current value from the stack;

ii) for calculating a second hint index by evaluating the hint function with the value retrieved from the stack as the argument;

iii) for retrieving a target address from a location in the return target cache determined by the second hint index; and

iv) for continuing execution beginning at the target address.

11. A system as in claim 10, in which:

there is a plurality of IL call sites;

the binary translator further forms means

for translating each IL call site into a corresponding OL call site;

for inserting a confirmation block of instructions into each OL call site;

for comparing the value retrieved from the stack with the correct IL return address corresponding to the current OL call site;

for continuing execution of the OL instructions following the OL call site if value retrieved from the stack the is equal to the correct IL return address; and

for transferring execution to the back-up return address recovery module if the value retrieved from the stack is not equal to the correct IL return address.