Control path evaluating trace designator with dynamically adjustable thresholds for activation of tracing for high (hot) activity and low (cold) activity of flow control

• US 6,189,141 B1
• Filed: 05/04/1998
• Issued: 02/13/2001
• Est. Priority Date: 05/04/1998
• Status: Expired due to Term

• Current Assignee: HTC Corporation
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Benitez, Manuel E., Buzbee, William B., Shah, Lacky V., Mattson, James S. Jr.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): INGBERG, TODD D
• Application Number:
  US09/073,211
• Time in Patent Office: 1,016 Days
• Field of Search: 395/701, 395/702, 395/703, 395/704, 395/705, 395/706, 395/707, 395/708, 395/709, 395/710, 395/712, 717/1, 717/2, 717/3, 717/4, 717/5, 717/6, 717/7, 717/8, 717/9, 717/10, 717/11
• US Class Current: 717/153
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466
• CPC Class Codes: G06F 11/3636 by tracing the execution of the program
• CPC Class Codes: G06F 11/3644 by instrumenting at runtime
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

A computer-implemented system, method, and product are provided to designate and translate traces of original instructions of an executable file at run time based on dynamic evaluation of control flow through frequently executed traces of instructions. Such designation typically reduces unnecessary translations and optimizations, and thereby increases execution speed and reduces the usage of memory and other resources. The invention includes a hot trace identifier to identify frequently executed traces of instructions and a hot trace instrumenter to instrument such frequently executed traces so that control flow through them may be recorded. If the amount or rate of control flow through a frequently executed trace exceeds a threshold value, a hot trace selector is invoked to select a hot trace of original instructions including those of the frequently executed trace. The hot trace may be dynamically optimized. The system, method, and product also provide for the continuous recording of control flow through hot traces. If control flow has changed during execution, such that the amount or rate of control flow through a hot trace falls below a threshold value, the trace may be removed.

Claims

1. A computer system having at least one central processing unit (CPU), at least one memory unit having stored therein a plurality of original instructions of an executable file, and a control-path-evaluating-trace-designator, wherein:

the control-path-evaluating-trace-designator cooperates with the at least one CPU to dynamically designate at least one sequence of the plurality of original instructions to be a hot trace, if present, upon a first plurality of occurrences of control flow through the at least one sequence of the plurality of original instructions reaching a hot-trace-designation threshold.

2. The computer system of claim 1, wherein:

the hot-trace-designation threshold is a rate at which the first plurality of occurrences of control flow occurs.

3. The computer system of claim 1, wherein:

the hot-trace-designation threshold is a magnitude of the first plurality of occurrences of control flow.

4. The computer system of claim 1, wherein:

the hot-trace-designation threshold is predetermined.

5. The computer system of claim 1, wherein:

the hot-trace-designation threshold is dynamically adjusted.

6. The computer system of claim 1, wherein:

the control-path-evaluating-trace-designator further dynamically translates the hot trace, if present.

7. The computer system of claim 6, wherein:

the control-path-evaluating-trace-designator further dynamically optimizes the translated hot trace, if present.

8. The computer system of claim 6, wherein:

the control-path-evaluating-trace-designator further dynamically removes the translated hot trace, if present, upon a second plurality of occurrences of control flow through the translated hot trace reaching a cold-trace-designation threshold.

9. The computer system of claim 8, wherein:

the cold-trace-designation threshold is a rate at which the second plurality of occurrences of control flow occurs.

10. The computer system of claim 8, wherein:

the cold-trace-designation threshold is a magnitude of the second plurality of occurrences of control flow.

11. The computer system of claim 8, wherein:

the cold-trace-designation threshold is predetermined.

12. The computer system of claim 8, wherein:

the cold-trace-designation threshold is dynamically adjusted.

13. A computer system having at least one central processing unit (CPU) and at least one memory unit having stored therein a plurality of original instructions of an executable file, and also having stored therein a set of control-path-evaluating-trace-designator instructions for execution by the at least one CPU, the control-path-evaluating-trace-designator instructions designating, when so executed, at least one hot trace in the original instructions, the set of control-path-evaluating-trace-designator instructions comprising:

(1) a set of hot-block manager instructions that, when executed by the at least one CPU,

(a) identifies a plurality of blocks of the plurality of original instructions as hot locks upon a first plurality of occurrences of control through each of the blocks reaching a start instruction frequency threshold, and

(b) translates and instruments the hot blocks to record occurrences of control flow through them; and

(2) a set of hot trace selector instructions that, when executed by the at least one CPU, selects at least one hot trace, if present, comprising;

(a) a first hot block of the plurality of hot blocks upon a second plurality of occurrences of control through the first block reaching a start-trace threshold, and

(b) at least a second hot block related to the first hot block upon a third plurality of occurrences of control through the second hot block reaching a trace-inclusion threshold.

14. The computer system of claim 13, further comprising

an operating system, and

wherein the set of control-path-evaluating-trace-designator instructions is executed by the at least one CPU in cooperation with the operating system.

15. The computer system of claim 13, wherein:

the start-trace threshold is a rate at which the second plurality of occurrences of control flow occurs.

16. The computer system of claim 13, wherein:

the start-trace threshold is a magnitude of the second plurality of occurrences of control flow.

17. The computer system of claim 13, wherein:

the start-trace threshold is predetermined.

18. The computer system of claim 13, wherein:

the start-trace threshold is dynamically adjusted.

19. The computer system of claim 13, wherein the set of hot block manager instructions further:

(c) removes at least a third hot block, if present, upon a fourth plurality of occurrences of control flow through the third hot block reaching a cold-block threshold.

20. The computer system of claim 13, wherein the set of control-path-evaluating-trace-designator instructions further comprises:

(3) a set of backpatcher instructions that;

(a) determines if a first translated hot block comprises at least one target instruction that is a target of at least one translated jump instruction that is included in any one of the plurality of translated hot blocks;

(b) if so, backpatches the translated jump instruction so that control is directed through it to the target instruction.

21. The computer system of claim 13, wherein the set of control-path-evaluating-trace-designator instructions further comprises:

(3) a set of hot trace optimizer and instrumenter instructions that;

(a) dynamically translates at least a first hot trace of the at least one hot trace.

22. The computer system of claim 21, wherein the set of hot trace optimizer and instrumenter instructions further:

(b) instruments the first hot trace to record occurrences of control flow through it.

23. The computer system of claim 22, wherein the set of hot trace optimizer and instrumenter instructions further:

(c) dynamically optimizes the translated and instrumented first hot trace.

24. The computer system of claim 22, wherein the set of hot trace optimizer and instrumenter instructions further:

(c) selectively removes at least a second hot trace of the at least one hot trace, if present, upon a fourth plurality of occurrences of control flow through the second hot trace reaching a cold-trace threshold.

25. The computer system of claim 21, wherein the set of hot trace optimizer and instrumenter instructions further:

(b) dynamically optimizes the translated first hot trace.

26. The computer system of claim 21, wherein the set of control-path-evaluating-trace-designator instructions further comprises:

(4) a set of backpatcher instructions that;

(a) determines if the first hot trace comprises at least one target instruction that is a target of at least one translated jump instruction;

(b) if so, backpatches the translated jump instruction so that control is directed through it to the target instruction.

27. The computer system of claim 26, wherein:

the translated jump instruction is included in any one of the plurality of translated hot blocks.

28. The computer system of claim 26, wherein:

the translated jump instruction is included in a translated third hot trace of the at least one hot trace.

29. The computer system of claim 21, wherein the set of control-path-evaluating-trace-designator instructions further comprises:

(4) a set of emulator instructions that emulates at least one of the plurality of original instructions, if present, that is not included in any of the translated at least a first hot trace.

30. The computer system of claim 13, wherein the set of control-path-evaluating-trace-designator instructions further comprises:

(3) a set of emulator instructions that emulates at least one of the plurality of original instructions, if present, that is not included in any of the plurality of translated hot blocks.

31. A computer system having at least one central processing unit (CPU), at least one memory unit having stored therein a plurality of original instructions of an executable file, and a control-path-evaluating trace designator configured to cooperate with the at least one CPU to designate at least one hot trace in the original instructions, the control-path-evaluating trace designator comprising:

(1) a hot block manager that

(a) identifies a plurality of blocks of the plurality of original instructions as hot blocks upon a first plurality of occurrences of control through each of the blocks reaching a start-instruction frequency threshold, and

(b) translates and instruments the hot blocks to record occurrences of control flow through them; and

(2) a hot trace selector that selects at least one hot trace, if present, comprising;

(a) a first hot block of the plurality of hot blocks upon a second plurality of occurrences of control through the first block reaching a start-trace threshold, and

(b) at least a second hot block related to the first hot block upon a third plurality of occurrences of control through the second hot block reaching a trace-inclusion threshold.

32. The computer system of claim 31, further comprising

an operating system, and

wherein the control-path-evaluating trace designator cooperates with the operating system.

33. The computer system of claim 31, wherein:

the start-trace threshold is a rate at which the second plurality of occurrences of control flow occurs.

34. The computer system of claim 31, wherein:

the start-trace threshold is a magnitude of the second plurality of occurrences of control flow.

35. The computer system of claim 31, wherein:

the start-trace threshold is predetermined.

36. The computer system of claim 31, wherein:

the start-trace threshold is dynamically adjusted.

37. The computer system of claim 31, wherein the hot block manager further:

(c) removes at least a third hot block, if present, upon a fourth plurality of occurrences of control flow through the third hot block reaching a cold-block threshold.

38. The computer system of claim 31, wherein the control-path-evaluating trace designator further comprises:

(3) a backpatcher that;

(a) determines if a first translated hot block comprises at least one target instruction that is a target of at least one translated jump instruction that is included in any one of the plurality of translated hot blocks;

(b) if so, backpatches the translated jump instruction so that control is directed through it to the target instruction.

39. The computer system of claim 31, wherein the control-path-evaluating trace designator further comprises:

(3) a hot trace optimizer and instrumenter that;

(a) dynamically translates at least a first hot trace of the at least one hot trace.

40. The computer system of claim 39, wherein the hot trace optimizer and instrumenter further:

(b) instruments the first hot trace to record occurrences of control flow through it.

41. The computer system of claim 40, wherein the hot trace optimizer and instrumenter further:

(c) dynamically optimizes the translated and instrumented first hot trace.

42. The computer system of claim 40, wherein the hot trace optimizer and instrumenter further:

(c) selectively removes at least a second hot trace of the at least one hot trace, if present, upon a fourth plurality of occurrences of control flow through the second hot trace reaching a cold-trace threshold.

43. The computer system of claim 39, wherein the hot trace optimizer and instrumenter further:

(b) dynamically optimizes the translated first hot trace.

44. The computer system of claim 39, wherein the control-path-evaluating trace designator further comprises:

(4) a set of backpatcher instructions that;

(a) determines if the first hot trace comprises at least one target instruction that is a target of at least one translated jump instruction;

(b) if so, backpatches the translated jump instruction so that control is directed through it to the target instruction.

45. The computer system of claim 44, wherein:

the translated jump instruction is included in any one of the plurality of translated hot blocks.

46. The computer system of claim 44, wherein:

the translated jump instruction is included in a translated third hot trace of the at least one hot trace.

47. The computer system of claim 39, wherein the control-path-evaluating trace designator further comprises:

(4) a set of emulator instructions that emulates at least one of the plurality of original instructions, if present, that is not included in any of the translated at least a first hot trace.

48. The computer system of claim 31, wherein the control-path-evaluating trace designator further comprises:

(3) an emulator that emulates at least one of the plurality of original instructions, if present, that is not included in any of the plurality of translated hot blocks.

49. A computer-implemented method for designating from a plurality of original instructions of an executable file at least one hot trace, the method comprising the steps of:

(1) identifying a plurality of blocks of the plurality of original instructions as hot blocks upon a first plurality of occurrences of control through each of the blocks reaching a start-instruction frequency threshold;

(2) translating and instrumenting the hot blocks to record occurrences of control flow through them; and

(3) selecting at least one hot trace, if present, comprising;

(a) a first hot block of the plurality of hot blocks upon a second plurality of occurrences of control through the first block reaching a start-trace threshold, and

(b) at least a second hot block related to the first hot block upon a third plurality of occurrences of control through the second hot block reaching a trace-inclusion threshold.

50. The method of claim 49, wherein:

the start-trace threshold is a rate at which the second plurality of occurrences of control flow occurs.

51. The method of claim 49, wherein:

the start-trace threshold is a magnitude of the second plurality of occurrences of control flow.

52. The method of claim 49, wherein:

the start-trace threshold is predetermined.

53. The method of claim 49, wherein:

the start-trace threshold is dynamically adjusted.

54. The method of claim 49, further comprising the step of:

(4) removing at least a third hot block, if present, upon a fourth plurality of occurrences of control flow through the third hot block reaching a cold-block threshold.

55. The method of claim 49, further comprising the step of:

(4) determining if a first translated hot block comprises at least one target instruction that is a target of at least one translated jump instruction that is included in any one of the plurality of translated hot blocks; and

(5) if so, backpatching the translated jump instruction so that control is directed through it to the target instruction.

56. The method of claim 49, further comprising the step of:

(4) dynamically translating at least a first hot trace of the at least one hot trace.

57. The method of claim 56, further comprising the step of:

(5) instrumenting the first hot trace to record occurrences of control flow through it.

58. The method of claim 57, further comprising the step of:

(6) dynamnically optimizing the translated and instrumented first hot trace.

59. The method of claim 57, further comprising the step of:

(6) selectively removing at least a second hot trace of the at least one hot trace, if present, upon a fourth plurality of occurrences of control flow through the second hot trace reaching a cold-trace threshold.

60. The method of claim 56, further comprising the step of:

(5) dynamically optimizing the translated first hot trace.

61. The method of claim 56, further comprising the steps of:

(5) determining if the first hot trace comprises at least one target instruction that is a target of at least one translated jump instruction; and

(6) if so, backpatching the translated jump instruction so that control is directed through it to the target instruction.

62. The method of claim 61, wherein:

the translated jump instruction is included in any one of the plurality of translated hot blocks.

63. The method of claim 61, wherein:

the translated jump instruction is included in a translated third hot trace of the at least one hot trace.

64. The method of claim 56, further comprising the step of:

(5) emulating at least one of the plurality of original instructions, if present, that is not included in any of the translated at least a first hot trace.

65. The method of claim 49, further comprising the step of:

(4) emulating at least one of the plurality of original instructions, if present, that is not included in any of the plurality of translated hot blocks.

66. Storage media that contains software that, when executed on an appropriate computing system having at least one central processing unit (CPU) and at least one memory unit having stored therein a plurality of original instructions of an executable file, performs a method comprising the steps of:

(1) identifying a plurality of blocks of the plurality of original instructions as hot blocks upon a first plurality of occurrences of control through each of the blocks reaching a start-instruction frequency threshold;

(2) translating and instrumenting the hot blocks to record occurrences of control flow through them; and

(3) selecting at least one hot trace, if present, comprising;

(a) a first hot block of the plurality of hot blocks upon a second plurality of occurrences of control through the first block reaching a start-trace threshold, and

(b) at least a second hot block related to the first hot block upon a third plurality of occurrences of control through the second hot block reaching a trace-inclusion threshold.

67. The storage media of claim 66, further comprising the steps of:

(4) dynamically translating at least a first hot trace of the at least one hot trace; and

(5) dynamically optimizing the translated first hot trace.

68. A computer program product for use with an appropriate computing system having at least one central processing unit (CPU) and at least one memory unit having stored therein a plurality of original instructions of an executable file, the computer program product comprising a computer usable medium having embodied therein computer readable program code method steps, the method steps comprising:

(1) identifying a plurality of blocks of the plurality of original instructions as hot blocks upon a first plurality of occurrences of control through each of the blocks reaching a start-instruction frequency threshold;

(2) translating and instrumenting the hot blocks to record occurrences of control flow through them; and

(3) selecting at least one hot trace, if present, comprising;

(a) a first hot block of the plurality of hot blocks upon a second plurality of occurrences of control through the first block reaching a start-trace threshold, and

(b) at least a second hot block related to the first hot block upon a third plurality of occurrences of control through the second hot block reaching a trace-inclusion threshold.

69. The computer program product of claim 68, wherein the method steps further comprise:

(4) dynamically translating at least a first hot trace of the at least one hot trace; and

(5) dynamically optimizing the translated first hot trace.