Shared code caching for program code conversion

• US 7,805,710 B2
• Filed: 03/30/2004
• Issued: 09/28/2010
• Est. Priority Date: 07/15/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: North, Geraint
• Primary Examiner(s): Kang; Insun
• Application Number:
  US10/813,867
• Publication Number:
  US 20050015758A1
• Time in Patent Office: 2,373 Days
• Field of Search: 717136-161, 711/3, 711/113, 711118-146, 711/216
• US Class Current: 717/136
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation

Abstract

Subject program code is translated to target code in basic block units at run-time in a process wherein translation of basic blocks is interleaved with execution of those translations. A shared code cache mechanism is added to persistently store subject code translations, such that a translator may reuse translations that were generated and/or optimized by earlier translator instances.

Claims

1. A method of translating a subject code executable by a subject computing architecture into a target code executable by a second computing architecture, wherein the subject code includes at least a first program and a second program, comprising:

providing a first translator instance which translates the subject code of the first program into the target code including translating a first portion of the subject code into a portion of the target code;

caching said portion of the target code into a shared code cache facility;

providing a second translator instance which is different from the first translator instance and which translates the subject code of the second program into the target code, wherein the second translator instance operates simultaneously with the first translator instance;

retrieving the cached portion of the target code from the shared code cache facility upon a compatibility detection between said cached portion of the target code and a second portion of the subject code in the second program, including loading the portion of the target code in the shared code cache facility into a portion of memory which is shared amongst at least the first and second translator instances; and

,

copying at least one part of the shared code cache facility to a private portion of memory associated with the second translator instance upon modification of the at least one part of the shared code cache facility by the second translator instance.

2. The method of claim 1 wherein said compatibility detection is determined by a cache key comparison between a cache key associated with the first portion of the subject code and the second portion of the subject code.

3. The method of claim 2 wherein the cache key is a byte sequence that encodes a subject code instruction sequence of the respective first and second portions of subject code.

4. The method of claim 2 wherein the cache key is a hash of the corresponding a subject code instruction sequence of the respective first and second portions of subject code.

5. The method of claim 2 wherein the cache key comprises:

a filename of an executable file containing the subject code;

an offset and a length of the subject code instruction sequence of the respective first and second portions of the subject code;

a last modification time of the executable file;

a version number of the respective first and second translator instance; and

a subject memory address where of the subject code instruction sequence was loaded.

6. The method of claim 2 wherein the cache key comprises a plurality of metrics.

7. The method of claim 2 wherein the compatibility detection is determined by computing a cache key data structure corresponding to the subject code to be translated to a plurality of second data structures, each second data structure corresponding to a different set of cached target code instructions.

8. The method of claim 1 further including executing the target code.

9. The method of claim 1 wherein translations of self-modifying code are not cached.

10. The method of claim 1 wherein the portion of target code cached comprises a translation structure including a basic block.

11. The method of claim 1 wherein the portion of target code cached comprises one or more block translations and their respective successor lists.

12. The method of claim 1 wherein the portion of target code is converted into a single cache unit comprising a subject program and all its associated libraries.

13. The method of claim 1 wherein the portion of target code cached consists of a single instruction.

14. The method of claim 1 wherein the portion of target code cached comprises all code blocks corresponding to the same starting subject address.

15. The method of claim 1 wherein the portion of target code cached comprises a cache unit representing a discrete range of subject addresses.

16. The method of claim 1 wherein the portion of target code cached as a unit comprises a subject library.

17. The method or claim 1, wherein said target code is cached at the end of translation of said first program.

18. The method of claim 1, wherein the first translator instance translates the first subject program including the first portion of the subject code into the portion of the target code, and the second translator instance translates the second subject program including reusing the portion of the target code created by the first translator instance.

19. The method of claim 1, further comprising:

copying the portion of target code from a private storage associated with the first translator instance to a shared code cache facility;

retrieving the portion of target code from the shared code cache facility for reuse by the second translator instance.

20. The method of claim 19, further comprising:

selectively identifying one or more static target code portions amongst a plurality of portions of the target code produced by the first translator instance, wherein the static target code portions are derived from static subject code portions in the subject code; and

caching the identified static target code portions.

21. The method of claim 20, further comprising:

identifying one or more dynamic target code portions amongst a plurality of portions of the target code produced by the first translator instance, wherein the dynamic target code portions are derived from dynamically generated portions of the subject code; and

discarding the dynamic target code portions.

22. The method of claim 21, further comprising selectively identifying, caching, identifying and discarding upon completing execution of the first translator instance.

23. The method of claim 1, further comprising:

providing a shared code cache facility to cache the portion of the target code; and

selectively replacing the cached portion of target code in the shared code cache facility where the second translator instance provides an updated translation of the portion of target code.

24. The method of claim 23, further comprising:

publishing the portion of target code from the first translator instance to the shared code cache facility during execution of the first translator instance; and

retrieving the portion of the target code from the shared code cache facility for reuse by the second translator instance;

wherein the first translator instance and the second translator instance execute concurrently.

25. The method of claim 24, wherein the publishing comprises publishing at cache synchronisation points having a predetermined trigger condition.

26. The method of claim 25, wherein the predetermined trigger condition is any one or more of:

idle periods when the first translator instance is inactive;

after a threshold number of translation structures have been generated; and

upon a request by the second translator instance.

27. The method of claim 1, further comprising:

providing a shared code cache facility to cache the portion of the target code; and

selectively performing optimisations of the shared code cache facility.

28. The method of claim 27 wherein the optimisations comprise any one or more of:

restructuring a cache directory structure of the shared code cache facility to make searches for a particular portion of target code more efficient;

deleting translations that have been superseded by subsequent, more optimized translations of the same subject code;

rearranging the shared code cache facility to locate frequently requested portions of target code near each other;

performing offline optimizations of cached translations; and

performing offline predictive translation to translate subject code which has not yet been translated by a translator instance but which a translator instance is expected to encounter.

29. The method of claim 1, further comprising:

providing a shared code cache facility to cache the portion of target code; and

distributing the shared code cache facility amongst two or more caches.

30. The method of claim 29, wherein the distributing comprises providing scoped caches, ranged caches, or cache policies.

31. The method of claim 1, further comprising:

aggressively optimising the translation in the first translator instance to provide an optimized portion of target code; and

reusing the optimised portion of target code in the second translator instance.

32. The method of claim 31, further comprising:

performing a less aggressive optimised translation in the second translator instance when translating the second portion of subject code for which a portion of target code is not cached.

33. A computer system, comprising:

a target processor;

a shared code cache facility; and

translator code for translating a subject program code into target code executable on said target processor, said translator code comprising code executable by said target processor to;

provide a first translator instance which translates the subject code of a first program into the target code including translating a first portion of the subject code into a portion of the target code;

cache said portion of the target code in the shared code cache facility; and

provide a second translator instance which translates the subject code of a second program into the target code,

wherein the second translator instance is different from the first translator instance and operates simultaneously with the first translator instance, and

wherein the second translator instance retrieves the cached portion of the target code from the shared code cache facility upon a compatibility detection between said cached portion of the target code and a second portion of the subject code in the second program, including loading the portion of the target code in the shared code cache facility into a portion of memory which is shared amongst at least the first and second translator instances; and

, copying at least one part of the shared code cache facility to a private portion of memory associated with the second translator instance upon modification of the at least one part of the shared code cache facility by the second translator instance.

34. The computer system combination of claim 33 wherein said compatibility detection of cache translations and subject code to be translated is determined by a cache key comparison between a cache key associated with the first portion of the subject code and with the second portion of the subject code.

35. The computer system combination of claim 34 wherein the byte sequence that encodes the corresponding a subject code instruction sequence of the respective first and second portions of the subject code.

36. The computer system combination of claim 34 wherein the cache key is a hash of the corresponding a subject code instruction sequence of the respective first and second portions of the subject code.

37. The computer system combination of claim 34 wherein the cache key comprises:

a filename of an executable file containing the subject code;

an offset and a length of the subject code instruction sequence of the respective first and second portions of the subject code;

a last modification time of the executable file;

a version number of the respective first and second translator instance; and

a subject memory address where of the subject code instruction sequence was loaded.

38. The computer system combination of claim 34 wherein the cache key comprises a plurality of metrics.

39. The computer system combination of claim 34 wherein the compatibility detection is determined by comparing a cache key data structure corresponding to the subject code to be translated to a plurality of second data structures, each second data structure corresponding to a different set of cached target code instructions.

40. The computer system combination of claim 33 further including executing the target code.

41. The computer system combination of claim 33 wherein translations of self-modifying code are not cached.

42. The computer system combination of claim 33 wherein the portion of target code cached comprises a translation structure including a basic block.

43. The computer system combination of claim 33 wherein the portion of target code cached comprises one or more block translations and their respective successor lists.

44. The computer system combination of claim 33 wherein the portion of target code is converted into a single cache unit comprising a subject program and all its associated libraries.

45. The computer system combination of claim 33 wherein the portion of target code cached consists of a single instruction.

46. The computer system combination of claim 33 wherein the portion of target code cached comprises all code blocks corresponding to the same starting subject address.

47. The computer system combination of claim 33 wherein the portion of target code cached comprises a cache unit representing a discrete range of subject addresses.

48. The computer system combination of claim 33 wherein the portion of target code cached as a unit comprises a subject library.

49. A program storage medium storing translator code for translating subject code into target code, wherein the subject code includes at least a first program and a second program, said translator code, when executed by a computer, comprising:

providing a first translator instance executing on the computer which translates the subject code of the first program into the target code including translating a first portion of the subject code into a portion of the target code;

caching said portion of the target code into a shared code cache facility; and

providing a second translator instance executing on the computer,

wherein the second translator instance is different from the first translator instance and

wherein the second translator instance translates the subject code of the second program into the target code, including retrieving the cached portion of the target code from the shared code cache facility upon a compatibility detection between said cached portion of the target code and a second portion of the subject code in the second program, including loading the portion of the target code in the shared code cache facility into a portion of memory which is shared amongst at least the first and second translator instances; and

, copying at least one part of the shared code cache facility to a private portion of memory associated with the second translator instance upon modification of the at least one part of the shared code cache facility by the second translator instance.

50. The storage medium of claim 49 wherein said compatibility detection of cache translations and subject code to be translated is determined by a cache key comparison between a cache key associated with the first portion of the subject code and the second portion of the subject code.

51. The storage medium of claim 50 wherein the cache key is a the byte sequence that encodes the corresponding a subject code instruction sequence of the respective first and second portions of subject code.

52. The storage medium of claim 50 wherein the cache key is a hash of the corresponding a subject code instruction sequence of the respective first and second portions of subject code.

53. The storage medium of claim 50 wherein the cache key comprises:

a filename of an executable file containing the subject code;

an offset and a length of the subject code instruction sequence of the respective first and second portions of the subject code;

a last modification time of the executable file;

a version number of the respective first and second translator instance; and

a subject memory address where of the subject code instruction sequence was loaded.

54. The storage medium of claim 50 wherein the cache key comprises a plurality of metrics.

55. The storage medium of claim 50 wherein the compatibility detection is determined by computing a cache key data structure corresponding to the subject code to be translated to a plurality of second data structures, each second data structure corresponding to a different set of cached target code instructions.

56. The storage medium of claim 49 further including executing the target code.

57. The storage medium of claim 49 wherein translations of self-modifying code are not cached.

58. The storage medium of claim 49 wherein the portion of target code cached comprises a translation structure including a basic block.

59. The storage medium of claim 49 wherein the portion of target code cached comprises one or more block translations and their respective successor lists.

60. The storage medium of claim 49 wherein the portion of target code is converted into a single cache unit comprising a subject program and all its associated libraries.

61. The storage medium of claim 49 wherein the portion of target code cached consists of a single instruction.

62. The storage medium of claim 49 wherein the portion of target code cached comprises all code blocks corresponding to the same starting subject address.

63. The storage medium of claim 49 wherein the portion of target code cached comprises a cache unit representing a discrete range of subject addresses.

64. The storage medium of claim 49 wherein the portion of target code cached as a unit comprises a subject library.

65. A program storage medium storing translator code for translating subject code into target code when said translator code is executed by a computer, the translator code comprising:

program code providing a first translator instance for translating a first portion of subject

code in a first program into a portion of target code; and

program code for caching said portion of target code into a shared code cache facility and for providing a second translator instance for retrieving said target code from said shared code cache facility upon detection of compatibility between a second portion of subject code in a second program and said portion of target code,

wherein said second translator instance operates simultaneously with the first translator instance, and program code for loading the portion of the target code in the shared code cache facility into a portion of memory which is shared amongst at least the first and second translator instances; and

, copying at least one part of the shared code cache facility to a private portion of memory associated with the second translator instance upon modification of the at least one part of the shared code cache facility by the second translator instance.

66. A method of translating a subject code executable by a subject computing architecture into a target code executable by a second computing architecture, wherein the subject code includes at least a first program and a second program, comprising:

providing a first translator instance which translates the subject code of the first program into the target code including translating a first portion of the subject code into a first portion of the target code;

caching said first portion of the target code into a shared code cache facility;

providing a second translator instance which is different from the first translator instance and which translates the subject code of the second program into the target code, including translating a second portion of the subject code of the second program into a second portion of the target code; and

retrieving the cached first portion of the target code from the shared code cache facility upon a compatibility detection between said first cached portion of the target code and a second portion of the subject code in the second program and a determination that the first cached portion is better than the second portion of the target code, including loading the first portion of the target code in the shared code cache facility into a portion of memory which is shared amongst at least the first and second translator instances.