US5339238A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Register usage tracking in translating code for different machine architectures by forward and reverse tracing through the program flow graph
Assignee: Hewlett Packard Development Co LP
•
Filing: 1991-03-07
•
Granted: 1994-08-16
•
Expires: 2011-03-07
Abstract
Abstract A code translator, constructed similar to a compiler, accepts as an input to be translated the assembly code written for one architecture (e.g., VAX), and produces as an output object code for a different machine architecture (e.g., RISC). The input code is converted into an intermediate language, and a flow graph is constructed. The flow graph is referenced by a flow analyzer for recognizing certain architecture-specific and calling standard-specific coding practices or idioms that cannot be automatically converted, particularly relating to stack usage, register usage, condition codes, and passing arguments for procedure calls. By tracking stack usage within routines, the compiler can distinguish up-level stack and return address references from valid local references. Also, it can inform the user of stack misalignment, which has a severe performance penalty, and can detect code segments where different flow paths may result in different stack depths at runtime, which may indicate a source code error. Register usage is likewise tracked to determine which registers are destroyed by a routine, and generate routine prologue and epilogue code which performs register saves, as well as provide register "hints" to aid the user in adding an entry point declaration or documentation for the routine. The usage of condition codes is likewise tracked, by a backward walk through the flow graph, so that code to fabricate needed values is generated. In addition, all argument pointer based memory references in the input code is tracked to determine how the same argument reference may be made in the target environment.
Inventors
- 👤 Thomas R. Benson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 12:27
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/70; G06F8/76; G06F8/40; G06F8/52
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
273 words
A method of processing a first computer code in a compiler or a code translator, said method being executed by a computer, comprising the steps of: generating a flow graph in an intermediate language from said first computer code, the flow graph being composed of blocks, and the blocks being composed of intermediate-language elements, where each element represents a single expression in said first computer code, and where each block represents a sequence of one or more elements; tracing through each block of said flow graph in a forward direction to detect references to registers and to create an output-register set, and in each said block: if a reference to a register is a read from the register not yet written to in the current block, recording such register in an input-register set for this block, if a reference to a register is a write, adding such register to the output-register set, if a reference to a register is a read from the register already written to in the current block, removing such register from the output-register set, if a reference to a register is a write to the register, recording such register in a written-register set for this block, passing said output-register set to the succeeding block, and including the step of tracing through each block of said flow graph in a reverse direction, and for each said block passing the input-register set to a predecessor block, and in each predecessor block updating the input-register set to include registers in the input-register set passed to this predecessor block by a successor block and not in the written-register set for this predecessor block.
Claim 2
Independent Claim
273 words
A method of processing a first computer code in a compiler or a code translator, said method being executed by a computer, comprising the steps of: generating a flow graph in an intermediate language from said first computer code, the flow graph being composed of blocks, and the blocks being composed of intermediate-language elements, where each element represents a single expression in said first computer code, and where each block represents a sequence of one or more elements; tracing through each block of said flow graph in a forward direction to detect references to registers and to create an output-register set, and in each said block: if a reference to a register is a read from the register not yet written to in the current block, recording such register in an input-register set for this block, if a reference to a register is a write, adding such register to the output-register set, if a reference to a register is a read from the register already written to in the current block, removing such register from the output-register set, if a reference to a register is a write to the register, recording such register in a written-register set for this block, passing said output-register set to the succeeding block, and including the step of tracing through each block of said flow graph in a reverse direction, and for each said block passing the input-register set to a predecessor block, and in each predecessor block updating the input-register set to include registers in the input-register set passed to this predecessor block by a successor block and not in the written-register set for this predecessor block.
Claim 3
Dependent Claim
58 words
A method according to claim 1 including the step of, upon completing said steps of tracing in the forward direction and tracing in the reverse direction, reporting by visual means to a user of said processor the content of said output-register set for said code, said input-register set for said code, and said written-register set for said code.
Claim 4
Dependent Claim
28 words
A method according to claim 2 wherein said first computer code includes a plurality of callable routines, and said steps of reporting are performed for each said routine.
Claim 5
Dependent Claim
45 words
A method according to claim 1 including the step of, upon completing said steps of tracing in the forward direction and tracing in the reverse direction, generating object code for a different computer architecture from said flow graph using said output-, input-, and written-register sets.
Claim 6
Dependent Claim
39 words
A method according to claim 1 wherein each of said intermediate language elements is a tuple data structure, and wherein each of said blocks begins with an entry and ends in a branch or return with no intermediate entry.
Claim 7
Dependent Claim
283 words
Apparatus executed by a processor for processing a first computer code in a compiler or code translator, comprising: means for generating a flow graph in an intermediate language from said first computer code, the flow graph being composed of blocks, and the blocks being composed of intermediate language elements, where each element represents a single expression in said code, and where each block represents a sequence of one or more elements; means for tracing in a forward direction through each block of said flow graph to detect references to registers and to create an output-register set, and in each said block: means for recording identity of a register in an input-register set for this block if a reference to such register is a read from the register not yet written to in the current block, means for adding identity of a register to the output-register reference to such register is a write to the register. means for removing identity of a register from the output-register set if a register reference is a read from the register already written to in the current block, means for recording identity of the register in a written-register set for this block if a reference to such register is a write to the register, means for passing said output-register set to the succeeding block: and including means for tracing through each block of said flow graph in a reverse direction, and for each said block passing the input-register set to a predecessor block, and in each predecessor block updating the input-register set to include registers in the input-register set passed to this predecessor block by a successor block and not in the written-register set for this predecessor block.
Claim 8
Dependent Claim
283 words
Apparatus executed by a processor for processing a first computer code in a compiler or code translator, comprising: means for generating a flow graph in an intermediate language from said first computer code, the flow graph being composed of blocks, and the blocks being composed of intermediate language elements, where each element represents a single expression in said code, and where each block represents a sequence of one or more elements; means for tracing in a forward direction through each block of said flow graph to detect references to registers and to create an output-register set, and in each said block: means for recording identity of a register in an input-register set for this block if a reference to such register is a read from the register not yet written to in the current block, means for adding identity of a register to the output-register reference to such register is a write to the register. means for removing identity of a register from the output-register set if a register reference is a read from the register already written to in the current block, means for recording identity of the register in a written-register set for this block if a reference to such register is a write to the register, means for passing said output-register set to the succeeding block: and including means for tracing through each block of said flow graph in a reverse direction, and for each said block passing the input-register set to a predecessor block, and in each predecessor block updating the input-register set to include registers in the input-register set passed to this predecessor block by a successor block and not in the written-register set for this predecessor block.
Claim 9
Dependent Claim
64 words
Apparatus according to claim 6 including means for reporting by visual means to a user of said processor the content of said output-register set upon completing said tracing for all of said blocks, and including means for reporting by visual means to a user of said processor said input-register set and said written-register set upon completing said step of tracing in the reverse direction.
Claim 10
Dependent Claim
38 words
Apparatus according to claim 6 wherein each of said intermediate language elements is a tuple data structure, and wherein each of said blocks begins with an entry and ends in a branch or return with no intermediate entry.
Claim 11
Independent Claim
313 words
A method of compiling input computer code written for a first machine architecture to produce object code for a second different machine architecture, said method being executed by a processor, comprising the steps of: generating a flow graph in an intermediate language from said input computer code by a converter, the flow graph being composed of blocks, and the blocks being composed of tuples, where each tuple represents a single expression in said input computer code, and where each block represents a sequence of one or more tuples beginning with an entry expression and ending in a branch expression or a return expression with no intermediate entry; tracing through each block of said flow graph in a forward direction to detect reference to registers and to create an output-register set, and in each said block: if a reference to a register is a read from the register not yet written to in the current block, recording such register is an input-register set for this block, if a reference to a register is a write, adding such register to the output-register set, if the register reference is a read from the register already written to in the current block, removing such register from the output-register set, passing said output-register set to the succeeding block, tracing through each block of said flow graph in a reverse direction, and for each said block passing the input-register set to a predecessor block, and in each predecessor block updating the input-register set to include registers in the input-register set passed to this predecessor block by a successor block and not in the written-register set for this predecessor block upon completing said steps of tracing in the forward direction and tracing in the reverse direction for all of said blocks, reporting to a user of said processor by visible means the content of said output-register set for said code.
Claim 12
Independent Claim
313 words
A method of compiling input computer code written for a first machine architecture to produce object code for a second different machine architecture, said method being executed by a processor, comprising the steps of: generating a flow graph in an intermediate language from said input computer code by a converter, the flow graph being composed of blocks, and the blocks being composed of tuples, where each tuple represents a single expression in said input computer code, and where each block represents a sequence of one or more tuples beginning with an entry expression and ending in a branch expression or a return expression with no intermediate entry; tracing through each block of said flow graph in a forward direction to detect reference to registers and to create an output-register set, and in each said block: if a reference to a register is a read from the register not yet written to in the current block, recording such register is an input-register set for this block, if a reference to a register is a write, adding such register to the output-register set, if the register reference is a read from the register already written to in the current block, removing such register from the output-register set, passing said output-register set to the succeeding block, tracing through each block of said flow graph in a reverse direction, and for each said block passing the input-register set to a predecessor block, and in each predecessor block updating the input-register set to include registers in the input-register set passed to this predecessor block by a successor block and not in the written-register set for this predecessor block upon completing said steps of tracing in the forward direction and tracing in the reverse direction for all of said blocks, reporting to a user of said processor by visible means the content of said output-register set for said code.
Claim 13
Dependent Claim
15 words
A method according to claim 9 wherein said output-register set is recorded in each block.
Claim 14
Dependent Claim
31 words
A method according to claim 9 wherein said input code contains one or more routines, and the content of said output-register set is reported to the user for each said routine.
Claim 15
Dependent Claim
36 words
A method according to claim 9 wherein said step of tracing in the reverse direction includes, if a register reference is a write to a register, recording such register in a written-register set for this block.
Claim 16
Independent Claim
291 words
A method executed by a processor for processing a first computer code in a compiler or code translator, comprising the steps of: generating a flow graph in an intermediate language from said first computer code, the flow graph being composed of blocks, and the blocks being composed of intermediate-language elements, where each element represents a single expression in said first computer code, and where each block represents a sequence of one or more elements; tracing through each block of said flow graph in a forward direction to detect reference to registers and to create an output-register set, and in each said block: if a reference to a register is a read from a register already written to in the current block, removing such register from the output-register set, if a reference to a register is a write, adding such register to the output-register set, if a reference to a register is a write to the register, recording such register in a written-register set for this block, if a reference to a register is a read from the register not yet written to in the current block, recording such register in an input-register set for this block, passing said output-register set to the succeeding block, tracing through each block of said flow graph in a reverse direction, and for each said block passing the input-register set to a predecessor block, and in each predecessor block updating the input-register set to include registers in the input-register set passed to this predecessor block by a successor block and not in the written-register set for this predecessor block, upon completing said step of tracing for all of said blocks, reporting by visual means to a user of said processor the content of said output-register set.
Claim 17
Independent Claim
291 words
A method executed by a processor for processing a first computer code in a compiler or code translator, comprising the steps of: generating a flow graph in an intermediate language from said first computer code, the flow graph being composed of blocks, and the blocks being composed of intermediate-language elements, where each element represents a single expression in said first computer code, and where each block represents a sequence of one or more elements; tracing through each block of said flow graph in a forward direction to detect reference to registers and to create an output-register set, and in each said block: if a reference to a register is a read from a register already written to in the current block, removing such register from the output-register set, if a reference to a register is a write, adding such register to the output-register set, if a reference to a register is a write to the register, recording such register in a written-register set for this block, if a reference to a register is a read from the register not yet written to in the current block, recording such register in an input-register set for this block, passing said output-register set to the succeeding block, tracing through each block of said flow graph in a reverse direction, and for each said block passing the input-register set to a predecessor block, and in each predecessor block updating the input-register set to include registers in the input-register set passed to this predecessor block by a successor block and not in the written-register set for this predecessor block, upon completing said step of tracing for all of said blocks, reporting by visual means to a user of said processor the content of said output-register set.
Claim 18
Dependent Claim
40 words
A method according to claim 13 including the step of, upon completing said step of tracing all of said blocks in the reverse direction, reporting by visual means to a user of said processor said input-register set for said code.
Claim 19
Dependent Claim
37 words
A method according to claim 14 including the step of, upon completing said step of tracing all of said blocks in the reverse direction, reporting by visual means to a user of said processor said written-register set.
Claim 20
Dependent Claim
28 words
A method according to claim 15 wherein said first computer code includes a plurality of callable routines, and said steps of reporting are performed for each said routine.
Claim 21
Dependent Claim
31 words
A method according to claim 13 wherein said steps of tracing in the forward and reverse directions include recording for each block processed an indication that said block has been processed.
Claim 22
Dependent Claim
29 words
A method according to claim 13 wherein said first computer code is written for a first machine architecture, and said method produces object code for a different machine architecture.
Claim 23
Dependent Claim
33 words
A method according to claim 13 wherein each said element is a tuple, and wherein each said block begins with an entry and ends in a branch or return with no intermediate entry.
References Cited (Backward Citations)
US4667290A
Cited
US4642765A
Cited
US4802091A
Cited
US4992938A
Cited
US4951195A
Cited
WO1990001738A1
Cited
EP0372835A2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-08-15 | 1998-02-14 | 1998-08-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-08-15 | 2002-02-14 | 2002-08-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-08-15 | 2006-02-14 | 2006-08-16 | $7700.00 | Window Closed / Lapsed |