Prediction Mechanism for Subroutine Returns in Binary Translation Sub-Systems of Computers

A method for implementing subroutine calls and returns in a computer system, the method comprising:

• 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) translating each IL call site into a corresponding OL call site;
• ii) storing a call site IL return address Rcall on a stack;
• iii) calculating a first index by evaluating a function with P as an argument, where P is a procedure entry address of the subroutine;
• iv) storing a corresponding OL return address in a return target cache at a location determined by the first index, the return target cache comprising an array of elements;
• and
• v) executing an OL subroutine translation of the called IL subroutine;
• D) upon completion of execution of the OL subroutine translation,
• i) retrieving an OL target address from the return target cache at the location indicated by a second index;
• and
• ii) continuing execution beginning at the OL target address;
• E) generating a confirm block of instructions corresponding to each OL call site and, upon execution of any confirm block of instructions:
• i) comparing an actual IL return target address Ractual fetched from the stack with a predicted IL return address Rpred;
• ii) if Ractual is equal to Rpred, continuing execution of the OL instructions following the OL call site;
• and
• iii) if Ractual is not equal to Rpred, transferring execution to the back-up return address recovery module;
• and
• F) in the back-up return address recovery module, determining a correct OL return address.

A method for implementing subroutine calls and returns in a computer system, the method comprising:

• A) converting a sequence of input language (IL) instructions into a corresponding sequence of output language (OL) instructions;
• B) executing the OL instructions;
• C) for each call to an IL subroutine made from an IL call site in the IL instruction sequence:
• i) storing a call site IL return address Rcall on a stack;
• ii) calculating a first index by evaluating a function with P as an argument, where P is a procedure entry address of the subroutine;
• iii) storing a corresponding OL return address in a return target cache at a location indicated by the first index;
• iv) executing an OL subroutine translation of the called IL subroutine;
• D) upon completion of execution of the OL subroutine translation,
• i) in a launch block of instructions, retrieving an OL target address from the return target cache at the location indicated by a second index;
• and
• ii) continuing execution beginning at the OL target address;
• in which:
• the return target cache is an array having a plurality of elements;
• the function maps IL procedure entry addresses substantially uniformly over the return target cache;
• and
• each of the elements of the return target cache is identified by an array index, and the function extracts a number of bits from the address P.

A method for implementing subroutine calls and returns in a computer system, the method comprising:

• A) converting a sequence of input language (IL) instructions into a corresponding sequence of output language (OL) instructions;
• B) executing the OL instructions;
• C) for each call to an IL subroutine made from an IL call site in the IL instruction sequence:
• i) storing a call site IL return address Rcall on a stack;
• ii) calculating a first index by evaluating a function with P as an argument, where P is a procedure entry address of the subroutine;
• iii) storing a corresponding OL return address in a return target cache at a location indicated by the first index;
• iv) executing an OL subroutine translation of the called IL subroutine;
• D) upon completion of execution of the OL subroutine translation,
• i) in a launch block of instructions, retrieving an OL target address from the return target cache at the location indicated by a second index;
• and
• ii) continuing execution beginning at the OL target address;
• in which:
• the step of calculating the first index k is performed as part of the step of converting the IL call into the corresponding sequence of OL instructions.

A method comprising:

• translating a first sequence of input instructions in an input language (IL) to output instructions in an output language (OL), the first sequence of input instructions including a call statement, the call statement directing execution to a subroutine P having an IL procedure entry address P;
• translating the call statement into an OL call block of instructions, the call block storing a known OL return address in a return target cache at a location corresponding to a value derived from the IL procedure entry address P, wherein the known OL return address corresponds to the IL return address R;
• and
• inserting a confirm block of instructions at an address following the call block of instructions, the confirm block confirming that an OL target address obtained from the return target cache corresponds to the IL return address by comparing the IL return address R with a predicted IL return address, the predicted IL return address corresponding to the OL return address.