Fast translation and execution of a computer program on a non-native architecture by use of background translator

• US 6,091,897 A
• Filed: 01/29/1996
• Issued: 07/18/2000
• Est. Priority Date: 01/29/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Herdeg, Mark, Robinson, Scott G., Yates, John S.
• Primary Examiner(s): Banankhah, Majid A.
• Assistant Examiner(s): LAO, SUE X
• Application Number:
  US08/593,588
• Time in Patent Office: 1,632 Days
• Field of Search: 395/704, 395/705, 395/707, 395/708, 712/209
• US Class Current: 717/138
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation

Abstract

A computer system for executing a binary image conversion system which converts instructions from a instruction set of a first, non native computer system to a second, different native computer system, includes an run-time system which in response to a non-native image of an application program written for a non-native instruction set provides an native instruction or a native instruction routine. The run-time system collects profile data in response to execution of the native instructions to determine execution characteristics of the non-native instruction. Thereafter, the non-native instructions and the profile statistics are fed to a binary translator operating in a background mode and which is responsive to the profile data generated by the run-time system to form a translated native image. The run-time system and the binary translator are under the control of a server process. The non-native image is executed in two different environments with first portion executed as an interpreted image and remaining portions as a translated image. The run-time system includes an interpreter which is capable of handling condition codes corresponding to the non-native architecture. A technique is also provided to jacket calls between the two execution environments and to support object based services. Preferred techniques are also provided to determine interprocedural translation units. Further, intermixed translation/optimization techniques are discussed.

Claims

1. A memory storing as binary image conversion system which converts instructions from a non-native instruction set to a native instruction set, said binary image conversion system comprising:

a server;

a run-time system transparently initiated upon invocation of an application program, said application program comprising non-native instructions, the run-time system interpreting untranslated non-native instructions of a non-native binary image corresponding to the application program by providing and executing a native instruction or a native instruction routine comprised of a plurality of native instructions, the run-time system receiving from the server and executing previously translated portions of native code, said translated portions of native code corresponding to non-native code portions of the non-native binary image, said run-time system further comprising;

a collector for collecting profile data in response to interpretation of the non-native instructions to determine execution characteristics of the non-native instructions; and

a background system invoked by the server, responsive to the profile data generated by the run-time system, for forming translated portions of native code from and corresponding to portions of the non-native instructions of the application program, wherein said background system translates only portions of the non-native instructions of the application program which have actually been interpreted in response to invoking the application program.

2. The memory of claim 1, wherein said collector for collecting profile data maintains information about a control transfer in the non-native image.

3. The memory of claim 2, wherein said run-time system further comprises:

an interpreter which examines a single non-native instruction of the application program at a time to provide and execute the native instruction or a native instruction routine comprised of a plurality of native instructions.

4. The memory of claim 3, wherein said interpreter comprises:

an examiner for examining the non-native instruction to determine resources needed by the instruction and an equivalent native instruction routine to perform the function called for by the non-native instruction.

5. The memory of claim 4 further comprising:

a generator for producing a data structure, said data structure comprising;

a store of equivalent translated native code segments; and

an address correlation table used to track said native code segments corresponding to non-native code segments, with entries in said table corresponding to addresses of entries of the equivalent translated native code segments of the store.

6. The memory of claim 5, wherein said background system translates into a native image only those non-native instructions of the application program whose execution is predictable.

7. The memory of claim 6, wherein said only those non-native instructions of the application program whose execution is predictable excludes self modifying code.

8. The memory of claim 7 further comprising:

an invoker for invoking the server to provide translated portions of the application program for those portions of the application program which have said translated portions; and

an invoker for invoking the server to obtain from the run-time system a native instruction or a native instruction routine comprised of a plurality of native instructions for those non-native instructions of the application program for which there is no translated native instruction or translated native instruction routine.

28. The memory of claim 7, further including:

a determiner for determining if there are any translated portions of the application program;

a native loader for loading the translated portions for execution;

a non-native loader for loading other portions of the application program including non-native instructions, said non-native loader including a connecting means for connecting the translated portions to the other portions that are untranslated enabling the other portions and the translated portions to be executed in the second native computer system.

62. The memory of claim 1 wherein the server invokes the background system in response to a comparison of recent profile statistics with previously stored profile statistics.

9. A code conversion system stored in memory, said memory comprising:

a run-time system initiated transparently upon invocation of an application program, said application program comprising non-native instructions, said run-time system further comprising;

means, in response to a non-native image corresponding to the application program, for providing and executing native code instructions corresponding to untranslated non-native instructions of the non-native image, and

means for collecting profile statistics characterizing targets of executed control transfer instructions;

a server means which provides, to the run-time system, translated native instructions corresponding to non-native instructions of the non-native image; and

a binary translator system invoked by the server means, said binary translator system comprising;

means, responsive to said profile statistics, for translating non-native instructions of an application program into native instructions included in a native image of the application program; and

means for storing the translated native image of the application program on a persistent storage device, wherein

said means for translating translates only portions of non-native instructions of a non-native image whose execution does not cause machine exceptions as determined by the profile statistics.

10. The code conversion system of claim 9 further comprising:

means for invoking the translating means while there is a pause the CPU utilization by the run-time system.

11. The code conversion system of claim 9 further comprising:

means for invoking the translating means after the run-time system completes execution of the program.

12. The code conversion system of claim 9 further comprising:

means for invoking the translating means during execution of the run-time system.

13. A computer system for executing a binary image conversion system which converts instructions from a non-native instruction set to a native instruction set, comprising:

a run-time system transparently initiated upon invocation of an application program, said application program comprising non-native instructions, the run-time system, in response to a non-native image having instructions of the application program, providing and executing a native instruction or a native instruction routine comprised of a plurality of native instructions, the run-time system receiving from a server and executing previously translated portions of native code corresponding to non-native code portions of the non-native binary image, said run-time system further comprising;

a collector for collecting profile data in response to execution of the native instructions and the native instruction routines to determine execution characteristics of the non-native instruction; and

a background system, invoked by said server, responsive to the profile data generated by the runtime system to form translated portions of a native image of the non-native instructions of the application program, wherein the background system translates only portions of non-native images comprising instructions which have been executed; and

said server, further comprising;

a determiner for determining whether there is any translated native image code for the application program, and

a scheduler for scheduling transactions within and between the run-time and background systems.

14. The computer system of claim 13 further comprising:

a producer for producing a data structure, said data structure comprising;

a store of equivalent translated native code segments; and

an address correlation table used to track said translated native code segments corresponding to segments of non-native code, with entries in said table corresponding to addresses of entries of the equivalent translated native code segments of the store.

15. The computer system of claim 14, wherein said collector for collecting profile data maintains information about a control transfer in the non-native image.

16. A method of converting a binary executable compiled for a first non-native architecture into a translated native image for a second native architecture comprising the steps of:

transparently executing the binary executable compiled for said first non-native architecture using an interpreter;

collecting profile data in response to the execution of the binary executable compiled for said first non-native architecture to determine various execution characteristics of instruction sequences; and

in response to the profile data generated by the interpreter, transparently forming said translated native image for at least portions of the binary executable in the non-native image in accordance with the characteristics of the profile data, and wherein, the first time the binary executable is invoked for execution, said step of executing using an interpreter is performed without performing a binary translation of any instructions included in the binary executable, and, upon subsequent invocations for execution, executing previously translated segments of native corresponding to non-native code segments, such that said step of executing using an interpreter is performed in subsequent conversions of the binary executable only for those portions of the binary executable which have not been translated.

17. The method of claim 16 further comprising the step of:

interpreting a single non-native instruction of the machine executable to provide one or more equivalent native instructions, and wherein said step of interpreting occurs each time previously unexecuted portions of the binary executable are executed.

18. The method of claim 17, wherein a server process supplies translated code to the run-time system corresponding to a portion of the binary executable;

and

if there is translated code corresponding to said portion of the binary executable, the server process has the translated code executed;

if there is no translated code corresponding to said portion of the binary executable, the server process has an interpreter perform said interpreting step to convert the portion of the binary executable currently executed in the computer system while producing profile statistics which are supplied to the server process, and wherein said server process operates at invocation time of said binary executable.

19. The method of claim 18, further including the step of:

storing he profile statistics with the server process.

20. The method of claim 19, wherein said step of storing the profile statistics further includes the steps of:

merging new profile statistics with existing profile statistics producing merged profile statistics;

comparing the merged profile statistics to the existing profile statistics;

determining, in response to said comparing step, if there are differences between the merged and existing profile statistics; and

initiating a translation of the binary executable by performing said forming step if said determining step determines there are differences.

21. The method of claim 20, wherein said step of determining if there are differences between the merged and existing profile statistics is performed in accordance with a threshold value establishing a level of difference required to be determined prior to performing said initiating step.

22. The method of claim 21, wherein said level of difference is selectable.

23. The method of claim 18, further including the step of:

forming a unique key associated with the binary executable compiled for a first non-native architecture.

24. The method of claim 23, wherein said server process performs said step of determining said unique key.

25. The method of claim 23, wherein said step of forming said unique key uses attributes of the binary executable to form said unique key.

26. The method of claim 25, wherein said attributes include one of:

a file size, a creation date of said binary executable, and a time-stamp.

27. The method of claim 25, wherein said unique key is used by the server process to associate the profile statistics with the binary executable.

29. A binary image conversion system which converts instructions from an instruction set of a first, non native computer system to a second, different, native computer system, said binary image conversion system comprising:

a server;

a run-time system transparently initiated upon invocation of an application program comprising non-native instructions which, in response to the non-native instructions, provides a native instruction or a native instruction routine comprised of a plurality of native instructions, said run-time system further comprising;

a component for collecting profile data in response to execution of the native instructions and the native instruction routines to determine execution characteristics of the non-native instruction;

a component for querying the server to determine whether there exists any native image code for the non-native instructions of the application program; and

an interpreter which examines a single non-native instruction of the application program at a time to provide the native instruction or a native instruction routine comprised of a plurality of native instructions, said server invoking said interpreter upon making a determination while executing said application program that there is no native image code corresponding to the single non-native instruction; and

a background system invoked by the server, responsive to the profile data generated by the run-time system for forming translated portions of a native image corresponding to portions of the non-native instructions of the application program which have already been interpreted in response to invoking the application program.

30. The binary conversion system of claim 29, wherein said component for collecting profile data maintains information about a control transfer in the non-native image.

31. The binary conversion system of claim 30, wherein said interpreter comprises:

an instruction examiner for examining the non-native instruction to determine resources needed by the instruction and an equivalent native instruction routine to perform the function called for by the non-native instruction.

32. The binary conversion system of claim 31 further comprising:

a component for producing a data structure, said data structure comprising;

a store of equivalent translated native code segments; and

an address correlation table used to track said native code segments corresponding to non-native code segments with entries in said table corresponding to addresses of entries of the equivalent translated native code segments of the store.

33. The binary conversion system of claim 32, wherein said background system translates into a native image only those non-native instructions of the application program whose execution is predictable.

34. The binary conversion system of claim 33, wherein said only those non-native instructions of the application program whose execution is predictable excludes self modifying code.

35. The binary conversion system of claim 34 further comprising:

an invoker for invoking the server to provide translated portions of the application program for those portions of the application program which have said translated portions; and

an invoker for invoking the server to provide from the run-time system a native instruction or a native instruction routine comprised of a plurality of native instructions for those non-native instructions of the application program for which there is no translated native instruction or translated native instruction routine.

36. The binary conversion system of claim 34, further including:

a component for determining if there are any translated portions of the application program;

a native loader for loading the translated portions for execution;

a non-native loader for loading other portions of the application program including non-native instructions, said non-native loader including a connecting means for connecting the translated portions to the other portions that are untranslated enabling the other portions and the translated portions to be executed in the second native computer system.

37. The binary conversion system of claim 36, wherein the runtime system is implemented in software and the background system is implemented in hardware.

38. The binary conversion system of claim 29, wherein the runtime system is implemented in hardware and the background system is implemented in software.

39. The binary conversion system of claim 29, wherein the runtime system and the background system are implemented in hardware.

40. The binary conversion system of claim 29, wherein the runtime system and the background system are implemented in software.

41. The binary conversion system of claim 29, wherein the runtime system and the background system have portions which are implemented in both hardware and software.

42. A binary translator system comprising:

a runtime system transparently initiated upon invocation of an application program comprising non-native instructions, for generating profile data during execution of an application program describing the execution of the application program;

a component, invoked by a server component, responsive to profile data generated by the run time system, for transparently translating non-native instructions of the application program into native instructions included in a translated native image of the application program wherein said non-native instructions have previously been executed upon invocation of the application program and wherein said non-native instructions have not yet been translated;

a runtime interpreter for interpreting non-native instructions at runtime of said applications program; and

said server component for determining at runtime of said application program whether to invoke said component for translating or said runtime interpreter to execute a current non-native instruction of said application program.

43. The binary translator system of claim 42, wherein said run time system is implemented in software, and said component for translating non-native instructions is implemented in hardware.

44. The binary translator system of claim 42, wherein said run time system is implemented in hardware, and said component for translating non-native instructions is implemented in software.

45. The binary translator system of claim 42, wherein said run time system and said component for translating non-native instructions are implemented in hardware.

46. The binary translator system of claim 42, wherein said run time system and said component for translating non-native instructions are implemented in software.

47. The binary translator system of claim 42, wherein said run time system and said component for translating non-native instructions have portions which are implemented in both hardware and software.

48. The binary translator system of claim 42 further comprising:

said run-time system which, responsive to a non-native image, converts instructions of the non-native image into native code; and

a component for collecting run-time profile statistics characterizing targets of control transfer instructions.

49. The binary translator system of claim 48, wherein said component for translating translates only portions of non-native instructions of a non-native image whose execution does not cause machine exceptions as determined by the profile statistics.

50. The binary translator system of claim 49 further comprising:

a component for invoking said component for translating while there is a pause in CPU utilization by the run-time system.

51. The binary translator system of claim 49 further comprising:

a component for invoking said component for translating after the run-time system completes execution of the program.

52. The binary translator system of claim 49 further comprising:

a component for invoking said component for translating during execution of the program by the run-time system.

53. A binary image conversion system which converts instructions from an instruction set of a non native computer system to an instruction set of a native computer system, comprising:

a run-time system transparently initiated upon invocation of an application program comprising non-native instructions, which, in response to a non-native image having instructions of the application program, provides and executes a native instruction or a native instruction routine comprised of a plurality of native instruction, wherein the run-time system executes previously translated portions of native code corresponding to non-native code portions of the non-native binary image, said run-time system further comprising;

a component for collecting profile data in response to execution of the native instructions and the native instruction routines to determine execution characteristics of the non-native instruction;

a background system responsive to the profile data generated by the runtime system to form translated portions of a native image of the non-native instructions of the application program, wherein the background system translates only portions of non-native images comprising instructions which have been executed;

a component for invoking the background system;

a component for determining whether there is any translated native image code for the application program; and

a component for scheduling transactions within and between the run-time and background systems.

54. The binary image conversion system of claim 53, wherein the background system is implemented in software, and the run-time system is implemented in hardware.

55. The binary image conversion system of claim 53, wherein the background system is implemented in hardware, and the run-time system is implemented in software.

56. The binary image conversion system of claim 53, wherein the background system and the run-time system are implemented in hardware.

57. The binary image conversion system of claim 53, wherein the background system and the rum-time system are implemented in software.

58. The binary image conversion system of claim 53, wherein the background system and the run-time system have portions which are implemented in both hardware and software.

59. The binary image conversion system of claim 53, wherein the background system translates only portions of non-native images comprised of instructions whose execution is predictable.

60. The binary image conversion system of claim 59 further comprising:

a component for producing a data structure, said data structure comprising;

a store of equivalent translated native code segments; and

an address correlation table used to track said translated native code segments corresponding to segments of non-native code, with entries in said table corresponding to addresses of entries of the equivalent translated native code segments of the store.

61. The binary image conversion system of claim 60, wherein said means for collecting profile data maintains information about a control transfer in the non-native image.