System and method for jump-evaluated trace designation

• US 6,148,437 A
• Filed: 05/04/1998
• Issued: 11/14/2000
• Est. Priority Date: 05/04/1998
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Buzbee, William B., Shah, Lacky V., Mattson, James S. Jr.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): ZHEN, WEI Y
• Application Number:
  US09/073,197
• Time in Patent Office: 925 Days
• Field of Search: 395/704, 717/4
• US Class Current: 717/128
• CPC Class Codes: G06F 9/45525 Optimisation or modification within the same instruction set architecture, e.g. HP Dynamo

Abstract

A computer-implemented system and method are provided to designate traces of original instructions of an executable file at run time based on evaluations of control flow through jump instructions. Such designation typically increases the opportunities for dynamic optimization based on loop unrolling and other modifications of the control-flow structure of the executable file. The target of a jump instruction is designated as the start of a trace if the number of times that control has passed to it through any one or more jump instructions of a predetermined type of jump instruction reaches a predetermined start-trace threshold. The trace is ended if the number of times that control has passed through jump instructions of one of a variety of particular types of jump instructions reaches an end-trace threshold that is predetermined for each such type of jump instruction. The invention includes an instruction emulator, a start-end designator, a trace translator and optimizer, and a backpatch manager. The instruction emulator emulates original instructions that have not been translated. The start-end designator designates the start and end of traces. The trace translator and optimizer translates and optimizes traces designated by the start-end designator. The backpatch manager backpatches jump instructions in translated instructions so that they jump to target instructions that have been translated, when present.

Claims

1. 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, the plurality of original instructions comprising a plurality of target instructions and a plurality of jump instructions, the at least one memory unit also having a set of jump-evaluating-trace-designator instructions for execution by the at least one CPU, the jump-evaluating-trace-designator instructions designating, when so executed, at least one trace in the original instructions, the at least one trace having a start instruction and an end instruction, the set of jump-evaluating-trace-designator instructions comprising

a set of start-end-designator instructions that, when executed by the at least one CPU,

(a) designates a target instruction as the start instruction upon at least one start-trace counter corresponding to the target instruction reaching a start-trace threshold, wherein the reaching of the start-trace threshold is determined by control passing to the target instruction, and

(b) designates a jump instruction as the end instruction upon at least one jump-type counter corresponding to the jump instruction reaching an end-trace threshold, wherein the reaching of the end-trace threshold is determined by control passing through the jump instruction.

2. The computer system of claim 1, further comprising

an operating system, and

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

3. The computer system of claim 1, wherein:

the reaching of the start-trace threshold by the at least one start-trace counter is determined by a first number of times that control has passed to the target instruction; and

the reaching of the end-trace threshold by the at least one jump-type counter is determined by a second number of times that control has passed through the jump instruction.

4. The computer system of claim 3, wherein:

the plurality of jump instructions comprises at least one type of jump instructions;

the start-trace threshold comprises at least one jump-instruction-specific start-trace threshold, each corresponding to at least one of the types of jump instructions; and

the end-trace threshold comprises one or more jump-instruction-specific end-trace thresholds, each corresponding to at least one of the one or more types of jump instructions.

5. The computer system of claim 4, wherein the jump-evaluating-trace-designator instructions further comprise:

instructions for implementing a jump instruction look-up table for storing the jump-instruction-specific start-trace thresholds and the jump-instruction-specific end-trace thresholds, and for correlating each of the types of jump instructions with one jump-instruction-specific start-trace threshold and with one jump-instruction-specific end-trace threshold.

6. The computer system of claim 4, wherein:

at least one of the jump-instruction-specific start-trace thresholds has a value that represents a threshold that can never be reached.

7. The computer system of claim 4, wherein:

at least one of the jump-instruction-specific end-trace thresholds has a value that represents a threshold that can never be reached.

8. The computer system of claim 4, wherein:

the first number is equal to or greater than at least one of the jump-instruction-specific-start-trace thresholds.

9. The computer system of claim 8, wherein:

the at least one jump-instruction-specific-start-trace threshold corresponds to the jump instruction through which control last passed to the target instruction, whereupon the target instruction is designated as the start instruction.

10. The computer system of claim 4, wherein:

the second number is equal to or greater than the jump-instruction-specific end-trace threshold corresponding to the type of jump instruction of the jump instruction through which control last passed, whereupon the jump instruction through which control last passed is designated as the end instruction.

11. The computer system of claim 4, wherein the set of jump-evaluating-trace-designator instructions further comprises:

a trace instruction counter configured to count a third number of instructions in a trace; and

a set of end-trace-detector instructions that, when executed by the at least one CPU, designate a jump instruction as the end instruction upon the trace instruction counter reaching or exceeding a corresponding jump-instruction-specific maximum end-trace threshold.

12. The computer system of claim 11, wherein:

the third number comprises at least one jump-instruction-specific maximum number, each corresponding to at least one type of jump instruction;

wherein the third number is equal to or greater than the jump-instruction-specific maximum number corresponding to the jump instruction through which control last passed, whereupon the jump instruction is designated as the maximum-trace original instruction.

13. The computer system of claim 1, wherein:

the reaching of the start-trace threshold by the at least one start-trace counter is determined by a first frequency with which control has passed to the target instruction; and

the reaching of the end-trace threshold by the at least one jump-type counter is determined by a second frequency with which control has passed through the jump instruction.

14. The computer system of claim 1, wherein:

the start-trace threshold and the end-trace threshold are predetermined.

15. The computer system of claim 1, wherein:

the start-trace threshold and the end-trace threshold are user-selectable.

16. The computer system of claim 1, wherein:

the start-trace threshold and the end-trace threshold are automatically adjustable.

17. The computer system of claim 1, wherein:

the set of jump-evaluating-trace-designator instructions further comprises;

a set of translator instructions that, when executed by the at least one CPU, translate the at least one trace to produce a plurality of translated instructions.

18. The computer system of claim 17, wherein:

the set of jump-evaluating-trace-designator instructions further comprises;

a set of dynamic-optimizer instructions that, when executed by the at least one CPU, dynamically optimize at least one of the plurality of translated instructions.

19. The computer system of claim 17, wherein:

the set of jump-evaluating-trace-designator instructions further comprises;

a set of backpatch-manager instructions that, when executed by the at least one CPU, backpatch a first translated instruction to pass control to a second translated instruction, when present; and

wherein the second translated instruction corresponds to an original instruction that is the target of the first translated instruction.

20. The computer system of claim 1, wherein:

the set of jump-evaluating-trace-designator instructions further comprises;

a set of original-instruction-processor instructions that, when executed by the at least one CPU, cooperate with the at least one CPU to assume control over execution of at least one original instruction.

21. The computer system of claim 20, wherein:

the set of jump-evaluating-trace-designator instructions further comprises;

a set of translator instructions that, when executed by the at least one CPU, translate the at least one trace to produce a plurality of translated instructions; and

a set of instruction-emulator instructions that, when executed by the at least one CPU, emulate at least one original instruction;

and wherein the set of original-instruction-processor instructions further selectively direct control to one of the group consisting of the instruction-emulator instructions, the start-end-designator instructions, and at least one translated instruction.

22. The computer system of claim 1, wherein:

the set of jump-evaluating-trace-designator instructions further comprises;

a set of instruction-emulator instructions that, when executed by the at least one CPU, emulate at least one original instruction.

23. 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, the plurality of original instructions comprising a plurality of target instructions and a plurality of jump instructions, and a jump-evaluating trace designator configured to cooperate with the at least one CPU to designate at least one trace having a start instruction and an end instruction, the jump-evaluating trace designator comprising

a start-end designator configured:

(a) to designate a target instruction as the start instruction upon at least one start-trace counter corresponding to the target instruction reaching a start-trace threshold, wherein the reaching of the start-trace threshold is determined by control passing to the target instruction, and

(b) to designate a jump instruction as the end instruction upon at least one jump-type counter corresponding to the jump instruction reaching an end-trace threshold, wherein the reaching of the end-trace threshold is determined by control passing through the jump instruction.

24. The computer system of claim 23, further comprising

an operating system, and

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

25. The computer system of claim 23, wherein:

the reaching of the start-trace threshold by the at least one start-trace counter is determined by a first number of times that control has passed to the target instruction; and

the reaching of the end-trace threshold by the at least one jump-type counter is determined by a second number of times that control has passed through the jump instruction.

26. The computer system of claim 25, wherein:

the reaching of the start-trace threshold by the at least one start-trace counter is determined by a first frequency with which control has passed to the target instruction; and

the reaching of the end-trace threshold by the at least one jump-type counter is determined by a second number of times that control has passed through the jump instruction.

27. The computer system of claim 25, wherein:

the plurality of jump instructions comprises at least one type of jump instructions;

the start-trace threshold comprises at least one jump-instruction-specific start-trace threshold, each corresponding to at least one of the types of jump instructions; and

the end-trace threshold comprises at least one jump-instruction-specific end-trace threshold, each corresponding to at least one of the types of jump instructions.

28. The computer system of claim 27, wherein:

the first number is equal to or greater than at least one of the jump-instruction-specific-start-trace thresholds.

29. The computer system of claim 28, wherein:

the at least one jump-instruction-specific-start-trace threshold corresponds to the jump instruction through which control last passed to the target instruction, whereupon the target instruction is designated as the start instruction.

30. The computer system of claim 29, wherein:

the jump-evaluating trace designator further comprises;

a translator configured to translate the at least one trace to produce a plurality of translated instructions; and

an instruction emulator configured to emulate at least one original instruction;

and wherein the original instruction processor further is configured selectively to direct control to one of the group consisting of the instruction emulator, the start-end designator, and at least one translated instruction.

31. The computer system of claim 27, wherein:

the second number is equal to or greater than the jump-instruction-specific end-trace threshold corresponding to the type of jump instruction of the jump instruction through which control last passed, whereupon the jump instruction through which control last passed is designated as the end instruction.

32. The computer system of claim 27, wherein:

the jump-evaluating trace designator further comprises;

a dynamic optimizer configured dynamically to optimize at least one of the plurality of translated instructions.

33. The computer system of claim 27, wherein:

the jump-evaluating trace designator further comprises;

a backpatch manager configured to backpatch a first translated instruction to pass control to a second translated instruction, when present; and

wherein the second translated instruction corresponds to an original instruction that is the target of the first translated instruction.

34. The computer system of claim 23, wherein:

the start-trace threshold and the end-trace threshold are predetermined.

35. The computer system of claim 23, wherein:

the jump-evaluating trace designator further comprises;

a translator configured to translate the at least one trace to produce a plurality of translated instructions.

36. The computer system of claim 23, wherein:

the jump-evaluating trace designator further comprises;

an original instruction processor configured to cooperate with the operating system and the at least one CPU to assume control over execution of at least one original instruction.

37. The computer system of claim 23, wherein:

the jump-evaluating trace designator further comprises;

an instruction emulator configured to emulate at least one original instruction.

38. A computer-implemented method for designating from a plurality of original instructions of an executable file at least one trace having a start instruction and an end instruction, the plurality of original instructions comprising a plurality of target instructions and a plurality of jump instructions, the method comprising the steps of:

(a) designating a target instruction as the start instruction upon at least one start-trace counter corresponding to the target instruction reaching a start-trace threshold, wherein the reaching of the start-trace threshold is determined by control passing to the target instruction; and

(b) designating a jump instruction as the end instruction upon at least one jump-type counter corresponding to the jump instruction reaching an end-trace threshold, wherein the reaching of the end-trace threshold is determined by control passing through the jump instruction.

39. The method of claim 38, wherein:

the reaching of the start-trace threshold by the at least one start-trace counter is determined by a first number of times that control has passed to the target instruction; and

the reaching of the end-trace threshold by the at least one jump-type counter is determined by a second number of times that control has passed through the jump instruction.

40. The method of claim 39, wherein:

the plurality of jump instructions comprises at least one type of jump instructions;

the start-trace threshold comprises at least one jump-instruction-specific start-trace threshold, each corresponding to at least one of the types of jump instructions; and

the end-trace threshold comprises at least one jump-instruction-specific end-trace threshold, each corresponding to at least one of the types of jump instructions.

41. The method of claim 40, further comprising the step of:

(c) designating the target instruction as the start instruction upon the first number being equal to or greater than at least one of the jump-instruction-specific-start-trace thresholds.

42. The method of claim 41, wherein:

the at least one jump-instruction-specific-start-trace threshold corresponds to the jump instruction through which control last passed to the target instruction, whereupon the target instruction is designated as the start instruction.

43. The method of claim 40, further comprising the step of:

(c) upon the second number being equal to or greater than the jump-instruction-specific end-trace threshold corresponding to the type of jump instruction of the jump instruction through which control last passed, designating the jump instruction through which control last passed as the end instruction.

44. The method of claim 38, further comprising the step of:

(c) translating the at least one trace to produce a plurality of translated instructions.

45. The method of claim 44, further comprising the step of:

(d) dynamically optimizing at least one of the plurality of translated instructions.

46. 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, the plurality of original instructions comprising a plurality of target instructions and a plurality of jump instructions, performs a method comprising the steps of:

(a) designating a target instruction as a start of a trace upon at least one start-trace counter corresponding to the target instruction reaching a start-trace threshold, wherein the reaching of the start-trace threshold is determined by control passing to the target instruction; and

(b) designating a jump instruction as an end of the trace upon at least one jump-type counter corresponding to the jump instruction reaching an end-trace threshold, wherein the reaching of the end-trace threshold is determined by control passing through the jump instruction.

47. The storage media of claim 46, wherein:

the plurality of jump instructions comprises at least one type of jump instructions;

the start-trace threshold comprises at least one jump-instruction-specific start-trace threshold, each corresponding to at least one of the types of jump instructions; and

the end-trace threshold comprises at least one jump-instruction-specific end-trace thresholds, each corresponding to at least one of the one or more types of jump instructions.

48. The storage media of claim 46, wherein the method further comprises the steps of:

(c) translating the at least one trace to produce a plurality of translated instructions; and

(d) dynamically optimizing at least one of the plurality of translated instructions.

49. 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 plurality of original instructions comprising a plurality of target instructions and a plurality of jump instructions, the computer program product comprising:

a computer usable medium having embodied therein computer readable program code method steps, the method steps comprising;

(a) designating a target instruction as a start of a trace upon at least one start-trace counter corresponding to the target instruction reaching a start-trace threshold, wherein the reaching of the start-trace threshold is determined by control passing to the target instruction; and

(b) designating a jump instruction as an end of the trace upon at least one jump-type counter corresponding to the jump instruction reaching an end-trace threshold, wherein the reaching of the end-trace threshold is determined by control passing through the jump instruction.

50. The computer program product of claim 49, wherein the method steps further comprise:

(c) translating the at least one trace to produce a plurality of translated instructions; and

(d) dynamically optimizing at least one of the plurality of translated instructions.