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

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.

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.