Dynamic optimizing object code translator for architecture emulation and dynamic optimizing object code translation method

• US 6,463,582 B1
• Filed: 10/21/1998
• Issued: 10/08/2002
• Est. Priority Date: 10/21/1998
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Sakurai, Mitsuo, Lethin, Richard A., Garrett, Charles D., Wada, Mikayo, Bank, III, Joseph A.
• Primary Examiner(s): Morse, Gregory
• Assistant Examiner(s): NGUYEN BA, HOANG VU A
• Application Number:
  US09/176,112
• Publication Number:
  US 20020147969A1
• Time in Patent Office: 1,448 Days
• Field of Search: 717/9, 717/5, 717/151-161, 717/136-145, 712/239, 709/1
• US Class Current: 717/158
• CPC Class Codes: G06F 9/45504 Abstract machines for programme code execution, e.g. Java virtual machine [JVM], interpreters, emulators

Abstract

An optimizing object code translation system and method perform dynamic compilation and translation of a target object code on a source operating system while performing optimization. Compilation and optimization of the target code is dynamically executed in real time. A compiler performs analysis and optimizations that improve emulation relative to template-based translation and interpretation such that a host processor which processes larger order instructions, such as 32-bit instructions, may emulate a target processor which processes smaller order instructions, such as 16-bit and 8-bit instructions. The optimizing object code translator does not require knowledge of a static program flow graph or memory locations of target instructions prior to run time. In addition, the optimizing object code translator does not require knowledge of the location of all join points into the target object code prior to execution. During program execution, a translator records branch operations. The logging of information identifies instructions and instruction join points. When a number of times a branch operation is executed exceeds a threshold, the destination of the branch becomes a seed for compilation and code portions between seeds are defined as segments. A segment may be incomplete allowing for modification or replacement to account for a new flow of program control during real time program execution.

Claims

1. A computer architecture emulation system which emulates a source computer architecture on a destination computer architecture, comprising:

an interpreter individually translating original object code into corresponding translated object code, determining a number of executions of branch instructions in the original object code, and comparing the number of executions of branch instructions with a threshold number; and

a compiler grouping instructions of the original object code into a segment when a number of executions of a corresponding branch instruction exceeds the threshold number, and dynamically compiling the segment,

wherein a rate of compilation of segments to be compiled is controlled by raising the threshold number when a queue to store the segments to be translated reaches a predetermined capacity.

2. The computer architecture emulation system according to claim 1, wherein branch instructions corresponding to segments which are not compiled are stored in memory.

3. The computer architecture emulation system according to claim 2, wherein segments corresponding to branch instructions which have not exceeded the threshold number are not compiled.

4. The computer architecture emulation system according to claim 1, wherein segments corresponding to branch instructions which are not compiled are stored in memory while said interpreter executes the translated object code instructions.

5. The computer architecture emulation system according to claim 1, wherein said interpreter and said compiler are tasks which operate simultaneously in a multi-tasking operating system in real time.

6. The computer architecture emulation system according to claim 1, further comprising:

a branch logger to store branch profile information of the branch instructions determined by said interpreter.

7. The computer architecture emulation system according to claim 1, wherein

a code flag is placed after branch instructions that execute a jump into or out of translatable instructions, and

successor instructions to the corresponding branch instructions are checked to determine if translatable or not by referencing the corresponding code flag.

8. The computer architecture emulation system according to claim 1, wherein

initial translation of branch instruction is performed when a number of executions of a successor instruction to the branch instruction surpasses a corresponding threshold number.

9. The computer architecture emulation system according to claim 1, wherein

said interpreter and said compiler communicate while said interpreter continues emulating the original object code to initiate translation of segments corresponding to frequently branched instructions.

10. The computer architecture emulation system according to claim 1, wherein said compiler makes an optimized object while tracing each instruction which is in memory, in order, by using a profile corresponding to an address from which compiling was started.

11. The computer architecture emulation system according to claim 10, wherein said compiler does not compile a block upon detection of a page fault, such that when a block causes a page fault, said compiler produces an object to log branch information in a branch logger.

12. The computer architecture emulation system according to claim 11, wherein if an instruction execution process does not timely execute with respect to a predetermined rate, said compiler traces the execution by using a profile, checks whether a branch count is under a predetermined number and produces an object to log branch information.

13. The computer architecture emulation system according to claim 1, further comprising:

a branch logger storing profile information of the branch instructions in the original object code comprising the number of executions, wherein said branch logger includes a cache storing profile information of frequently executed branch instructions and a branch log storing profile information of less frequently executed branch instructions.

14. The computer architecture emulation system according to claim 13, wherein the profile information is organized in the cache by combining branch address information and branch destination information.

15. The computer architecture emulation system according to claim 14, wherein the profile information organized in the cache is stored in a plurality of groups, with each group organized in a decreasing order of entry of profile information into each respective group.

16. A computer architecture emulation system which emulates a source computer architecture on a destination computer architecture, comprising:

an interpreter individually translating original object code into corresponding translated object code, determining a number of executions of branch instructions in the original object code, and comparing the number of executions of branch instructions with a threshold number;

a compiler grouping instructions of the original object code into a segment when a number of executions of a corresponding branch instruction exceeds the threshold number, and dynamically compiling the segment; and

a branch logger to store branch profile information of the branch instructions determined by said interpreter, wherein

said branch profile information includes a branch address, a branch successor, a non-branch successor, a branch execution count, and a branch taken count, and

said branch profile information is logged by said interpreter during branch instruction emulation.

17. A computer architecture emulation system which emulates a source computer architecture on a destination computer architecture, comprising:

an interpreter individually translating original object code into corresponding translated object code, determining a number of executions of branch instructions in the original object code, and comparing the number of executions of branch instructions with a threshold number; and

a compiler grouping instructions of the original object code into a segment when a number of executions of a corresponding branch instruction exceeds the threshold number, and dynamically compiling the segment,

wherein each branch instruction is a seed, said compiler further comprising;

a block picker selecting a segment of the original object code to compile based upon the seed and the profile information of the branch,

a block layout unit flattening the segment into a linear list of instructions, and

an optimizing code generation unit performing the actual compilation of original instructions into tanslated code segment instructions.

18. The computer architecture emulation system according to claim 17, wherein the block picker creates a control flow graph that describes the original instructions to compile and passes the control flow graph to the block layout unit.

19. A computer architecture emulation system which emulates a source computer architecture on a destination computer architecture, comprising:

a plurality of interpreters individually translating original object code into corresponding translated object code, wherein each of said plurality of interpreters profiles original object code branch information in real time while executing translated object code instructions, the profile information comprising a number of executions of branch instructions, and each of said interpreters comparing the number of executions of branch instructions with a threshold number; and

a compiler grouping original object code instructions from any of said plurality of interpreters into segments based upon corresponding branch instructions in the original object code and dynamically compiling the segments of the original object code when the corresponding branch instruction is greater than the threshold number,

wherein a rate of compilation of segments to be compiled is controlled by raising the threshold number when a queue to store the segments to be translated reaches a predetermined capacity.

20. The computer architecture emulation system according to claim 19, wherein each of said plurality of said interpreters profiles the branch instructions and stores the branch instructions which have not exceeded the threshold number by calling a branch logger.

21. A computer architecture emulation system which emulates a source computer architecture on a destination computer architecture, comprising:

an interpreter individually translating original object code into corresponding translated object code, wherein said interpreter profiles-branch instructions of the original object code by storing a number of executions for each branch instruction and comparing the number of executions with a threshold number, such that branch instructions which exceed the threshold number are designated as seeds; and

a compiler grouping instructions of the original object code into segments based upon the seeds and dynamically compiling the segments of the original object code during translation and profiling by said interpreter,

wherein a rate of compilation of segments to be compiled is controlled by raising the threshold number when a queue to store the segments to be translated reaches a predetermined capacity.

22. The computer architecture emulation system according to claim 21, wherein

each segment contains instructions that result from optimizing the original object code based on a corresponding seed, and

each segment is installed and uninstalled as a unit.

23. The computer architecture emulation system according to claim 22, wherein branch instructions corresponding to segments which are not compiled are stored in memory while segments corresponding to branch instructions which have not exceeded the threshold number are not compiled.

24. The computer architecture emulation system according to claim 22, further comprising:

a branch logger storing branch profile information of the branch instructions determined by said interpreter,

wherein the branch profile information comprises a branch address, a branch successor, a non-branch successor, a branch execution count, and a branch taken count, and the branch profile information is logged by said interpreter during branch instruction emulation.

25. The computer architecture emulation system according to claim 22, wherein a code flag is placed after branch instructions that execute a jump into or out of translatable instructions, and

successor instructions are checked to determine if the corresponding branch instructions are translatable or not by referencing the corresponding code flag.

26. The computer architecture emulation system according to claim 22, wherein

branch instruction are initially translated when a number of executions of a successor instruction to the branch instruction surpasses a threshold value.

27. The computer architecture emulation system according to claim 22, wherein

a rate of compilation of segments is controlled to be compiled by raising the threshold number when a queue to store the segments to be translated reaches a predetermined capacity.

28. The computer architecture emulation system according to claim 22, wherein if an instruction execution process does not timely execute with respect to a predetermined rate, said compiler traces the execution by using a profile, checks whether a branch count is under a predetermined number and produces an object to log branch information like the page fault.

29. The computer architecture emulation system according to claim 22, further comprising:

a branch logger storing profile information of the branch instructions in the original object code comprising the number of executions, wherein said branch logger comprises a cache storing profile information of frequently executed branch instructions and a branch log to store profile information of less frequently executed branch instructions,

wherein the profile information is organized in the cache by combining branch address information and branch destination information and the profile information is stored in a plurality of groups in a decreasing order of entry into the group.

30. The computer architecture emulation system according to claim 22, wherein said compiler further comprises:

a block picker selecting a segment of the original object code to compile based upon the seed and the profile information of the branch, wherein the block picker creates a control flow graph that describes the original instructions to compile;

a block layout unit flattening the control flow graph into a linear list of instructions; and

an optimizing code generation unit performing the actual compilation of original instructions into translated code segment instructions.

31. A multi-tasking computer architecture emulation system which emulates a source computer architecture on a multi-tasking destination computer architecture, comprising:

an interpreter task individually translating original object code into corresponding translated object code and determining a number of executions of branch instructions in the original object code, and comparing the number of executions of branch instructions with a threshold number; and

a compiler task, operating with said interpreter task on the multi-tasking destination computer architecture, to group instructions of the original object code into a segment when a number of executions of a corresponding branch instruction exceeds the threshold number, and dynamically compiling the segment,

wherein said multi-tasking computer architecture emulation system is a dynamic translation system, said multi-tasking computer architecture system further comprising software feedback equalizing a rate of compilation requests sent by said interpreter task and the rate of compilations completed by said compiler task, without allowing the compiler task to become idle by varying the threshold number.

32. The multi-tasking computer architecture emulation system according to claim 31, further comprising:

a queue storing segments to be compiled by said compiler task, wherein the threshold number is compared with a minimum threshold number to turn said compiler task on or off.