Method for selecting active code traces for translation in a caching dynamic translator

• US 6,351,844 B1
• Filed: 11/05/1998
• Issued: 02/26/2002
• Est. Priority Date: 11/05/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Bala, Vasanth
• Primary Examiner(s): Ellis, Richard L.
• Application Number:
  US09/186,945
• Time in Patent Office: 1,209 Days
• Field of Search: 712/227, 712/23, 712/233, 712/244, 712/209, 717/1, 717/5, 717/8, 717/7, 717/9, 717/10, 717/4, 703/22, 703/26, 709/331, 710/226
• US Class Current: 717/128
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 9/30061 Multi-way branch instructions, e.g. CASE
• CPC Class Codes: G06F 9/3808 for instruction reuse, e.g. trace cache, branch target cache
• CPC Class Codes: G06F 9/45504 Abstract machines for programme code execution, e.g. Java virtual machine [JVM], interpreters, emulators

Abstract

A method is shown for selecting active, or hot, code traces in an executing program for storage in a code cache. A trace is a sequence of dynamic instructions characterized by a start address and a branch history which allows the trace to be dynamically disassembled. Each trace is terminated by execution of a trace terminating condition which is a backward taken branch, an indirect branch, or a branch whose execution causes the branch history for the trace to reach a predetermined limit. As each trace is generated by the executing program, it is loaded into a buffer for processing. When the buffer is full, a counter corresponding to the start address of each trace is incremented. When the count for a start address exceeds a threshold, then the start address is marked as being hot. Each hot trace is then checked to see if the next trace in the buffer shares the same start address, in which case the hot trace is cyclic. If the start address of the next trace is not the same as the hot trace, then the traces in the buffer are checked to see they form a larger cycle of execution. If the traces subsequent to the hot trace are not hot themselves and are followed by a trace having the same start address as the hot trace, then their branch histories are companded with the branch history of the hot trace to form a cyclic trace. The cyclic traces are then disassembled and the instructions executed in the trace are stored in a code cache.

Claims

1. A dynamic translator for executing a non-native program, the translator comprising:

an interpreter configured to receive non-native code words from a non-native code image of the non-native program and interpret the non-native code words into corresponding native code words, wherein the interpreter is configured to generate branch history data for each of a series of traces during execution of the non-native program;

a trace buffer configured to receive and store the branch history data for the series of traces;

a trace selector configured to receive the branch history data for the series of traces stored in the trace buffer and to use the received branch history data to identify hot traces, and is further configured to receive the non-native code image and to disassemble and translate the non-native code words for each hot trace into a translated code segment, wherein the branch history data includes a start address and a branch history value and wherein the trace selector is configured to count occurrences of one of (i) the start address and (ii) a combination of the start address and corresponding branch history value, and the trace selector is configured to mark as hot those traces corresponding to a count that exceeds a threshold, and wherein the trace selector is further configured to search for first and second traces in the series of traces having the same start address value which is marked as hot and where there are intervening traces which do not have the same start address value an the first and second traces and where the start address of the intervening traces are not marked as hot, where the trace selector is further configured to compand the intervening traces with the first trace to form a cyclic trace, and wherein the trace selector disassembles each hot trace by sequentially walking through the non-native code image beginning with the start address of the hot trace and translating each non-native code word into the translated code segment for the hot trace until a branch instruction is encountered whereupon a bit of the branch history value of the hot trace corresponding to the branch instruction is checked and, if the corresponding bit indicates that the branch was taken, then the branch instruction is inverted, the branch instruction is translated into the translated code segment and disassembly resumes at the target address of the branch instruction, and, if the corresponding bit indicates that the branch was not taken, the branch instruction is translated into the translated code segment and disassembly resumes with the next instruction in the sequence of the non-native code image; and

a translated code cache configured to receive and store the translated code segment for each hot trace.

2. The dynamic translator of claim 1:

wherein the interpreter further includes a control section configured to output the start address of a currently executing trace and receive a cache hit signal and a cache miss signal, and wherein the control section suspends operation of the interpreter responsive to the cache hit signal and continues operation of the interpreter responsive to the cache miss signal; and

wherein the translated code cache receives the start address of the currently executing trace from the control section of the interpreter and, responsive thereto, generates the cache hit signal if a translated code segment corresponding to the start address resides in the cache and generates the cache miss signal if a translated code segment corresponding to the start address does not reside in the cache.

3. The dynamic translator of claim 2 wherein the translated code cache returns an untranslated instruction address as the target address when execution of the translated code segment branches to the untranslated instruction address.

4. The dynamic translator of claim 1, wherein the trace selector is further configured to search for first and second traces in the series of traces having the same start address value which is marked as hot and where there are intervening traces which do not have the same start address value as the first and second traces and where the start address of the intervening traces are not marked as hot, where the trace selector is further configured to compand the intervening traces with the first trace to form a cyclic trace.

5. The dynamic translator of claim 1, wherein the trace selector disassembles each hot trace by sequentially walking through the non-native code image beginning with the start address of the hot trace and translating each non-native code word into the translated code segment for the hot trace until a branch instruction is encountered whereupon a bit of the branch history value of the hot trace corresponding to the branch instruction is checked and, if the corresponding bit indicates that the branch was taken, then the branch instruction is inverted, the branch instruction is translated into the translated code segment and disassembly resumes at the target address of the branch instruction, and, if the corresponding bit indicates that the branch was not taken, the branch instruction is translated into the translated code segment and disassembly resumes with the next instruction in the sequence of the non-native code image.

6. A dynamic translator for executing a non-native program, the translator comprising:

an interpreter configured to receive non-native code words from a non-native code image of the non-native program and interpret the non-native code words into corresponding native code words, wherein the interpreter is configured to generate branch history data for each of a series of traces during execution of the non-native program;

a trace buffer configured to receive and store the branch history data for the series of traces;

a trace selector configured to receive the branch history data for the series of traces stored in the trace buffer and to use the received branch history data to identify hot traces, and is further configured to receive the non-native code image and to disassemble and translate the non-native code words for each hot trace into a translated code segment, wherein the trace selector disassembles each hot trace by sequentially walking through the non-native code image beginning with the start address of the hot trace and translating each non-native code word into the translated code segment for the hot trace until a branch instruction is encountered whereupon a bit of the branch history value of the hot trace corresponding to the branch instruction is checked and, if the corresponding bit indicates that the branch was taken, then the branch instruction is inverted, the branch instruction is translated into the translated code segment and disassembly resumes at the target address of the branch instruction, and, if the corresponding bit indicates that the branch was not taken, the branch instruction is translated into the translated code segment and disassembly resumes with the next instruction in the sequence of the non-native code image; and

a translated code cache configured to receive and store the translated code segment for each hot trace.

7. The dynamic translator of claim 6, wherein the branch history data includes a start address and a branch history value and wherein the trace selector is configured to count occurrences of one of (i) the start address and (ii) a combination of the start address and corresponding branch history value, and the trace selector is configured to mark as hot those traces corresponding to a count that exceeds a threshold.

8. The dynamic translator of claim 6:

wherein the interpreter further includes a control section configured to output the start address of a currently executing trace and receive a cache hit signal and a cache miss signal, and wherein the control section suspends operation of the interpreter responsive to the cache hit signal and continues operation of the interpreter responsive to the cache miss signal; and

wherein the translated code cache receives the start address of the currently executing trace from the control section of the interpreter and, responsive thereto, generates the cache hit signal if a translated code segment corresponding to the start address resides in the cache and generates the cache miss signal if a translated code segment corresponding to the start address does not reside in the cache.

9. The dynamic translator of claim 8 wherein the translated code cache returns an untranslated instruction address as the target address when execution of the translated code segment branches to the untranslated instruction address.

10. The dynamic translator of claim 6, wherein the trace selector is further configured to search for first and second traces in the series of traces having the same start address value which is marked as hot and where there are intervening traces which do not have the same start address value as the first and second traces and where the start address of the intervening traces are not marked as hot, where the trace selector is further configured to compand the intervening traces with the first trace to form a cyclic trace.