US6463582B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Dynamic optimizing object code translator for architecture emulation and dynamic optimizing object code translation method
Assignee: Fujitsu Ltd
•
Filing: 1998-10-21
•
Granted: 2002-10-08
•
Expires: 2018-10-21
Abstract
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.
Inventors
- 👤 Richard A. Lethin
- 👤 Joseph A. Bank, III
- 👤 Charles D. Garrett
- 👤 Mikayo Wada
- 👤 Mitsuo Sakurai
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 21:06
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/44; G06F9/455; G06F9/45504
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
118 words
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.
Claim 2
Dependent Claim
118 words
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.
Claim 3
Dependent Claim
24 words
The computer architecture emulation system according to claim 1 , wherein branch instructions corresponding to segments which are not compiled are stored in memory.
Claim 4
Dependent Claim
26 words
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.
Claim 5
Dependent Claim
33 words
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.
Claim 6
Dependent Claim
29 words
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.
Claim 7
Dependent Claim
28 words
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.
Claim 8
Dependent Claim
51 words
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.
Claim 9
Dependent Claim
36 words
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.
Claim 10
Dependent Claim
36 words
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.
Claim 11
Dependent Claim
40 words
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.
Claim 12
Dependent Claim
46 words
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.
Claim 13
Dependent Claim
53 words
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.
Claim 14
Dependent Claim
60 words
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.
Claim 15
Dependent Claim
28 words
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.
Claim 16
Dependent Claim
42 words
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.
Claim 17
Dependent Claim
141 words
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.
Claim 18
Dependent Claim
141 words
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.
Claim 19
Dependent Claim
153 words
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.
Claim 20
Dependent Claim
153 words
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.
Claim 21
Dependent Claim
37 words
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.
Claim 22
Dependent Claim
160 words
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.
Claim 23
Dependent Claim
160 words
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.
Claim 24
Dependent Claim
39 words
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.
Claim 25
Dependent Claim
136 words
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.
Claim 26
Dependent Claim
136 words
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.
Claim 27
Dependent Claim
38 words
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.
Claim 28
Dependent Claim
40 words
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.
Claim 29
Dependent Claim
65 words
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.
Claim 30
Dependent Claim
51 words
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.
Claim 31
Dependent Claim
33 words
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.
Claim 32
Dependent Claim
41 words
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.
Claim 33
Dependent Claim
57 words
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.
Claim 34
Dependent Claim
99 words
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.
Claim 35
Dependent Claim
88 words
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.
Claim 36
Dependent Claim
159 words
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.
Claim 37
Dependent Claim
159 words
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.
Claim 38
Dependent Claim
43 words
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.
References Cited (Backward Citations)
JPH04213730A
Cited
JPH06282437A
Cited
US5751982A
Cited
US5761477A
Cited
US6115809A
Cited
US6158047A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-10-07 | 2006-04-08 | 2006-10-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-10-07 | 2010-04-08 | 2010-10-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-10-07 | 2014-04-08 | 2014-10-08 | $7700.00 | Window Closed / Lapsed |