US5598560A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Tracking condition codes in translation code for different machine architectures
Assignee: Hewlett Packard Development Co LP
•
Filing: 1991-03-07
•
Granted: 1997-01-28
•
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-02 14:09
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/70; G06F8/76; G06F8/40; G06F8/52
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
201 words
A method of processing input computer code by a computer in a code translator to produce translated code, comprising the steps of: accessing and parsing said code by said computer to generate a flow graph in an intermediate language from said code, the flow graph being a data structure 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 with no intermediate entry or exit; tracing through each said block of elements in a reverse direction from its exit to its entry to detect any elements which read or set condition codes, where said condition codes represent bits set in a status register in a processor executing said computer code; producing from those detected elements which read condition codes a first set of condition codes; removing from the first set those condition codes which are set by other detected elements to produce a second required set of required condition codes; and generating from the required set instructions in said translated code to set the required condition codes to simulate reading and setting of the condition codes.
Claim 2
Independent Claim
201 words
A method of processing input computer code by a computer in a code translator to produce translated code, comprising the steps of: accessing and parsing said code by said computer to generate a flow graph in an intermediate language from said code, the flow graph being a data structure 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 with no intermediate entry or exit; tracing through each said block of elements in a reverse direction from its exit to its entry to detect any elements which read or set condition codes, where said condition codes represent bits set in a status register in a processor executing said computer code; producing from those detected elements which read condition codes a first set of condition codes; removing from the first set those condition codes which are set by other detected elements to produce a second required set of required condition codes; and generating from the required set instructions in said translated code to set the required condition codes to simulate reading and setting of the condition codes.
Claim 3
Dependent Claim
39 words
A method according to claim 1 further comprising tracing all paths in aid flow graph from the end of said code to the beginning of said code even if some blocks are visited more than once in said tracing.
Claim 4
Dependent Claim
26 words
A method according to claim 2 wherein said step of removing said condition codes includes resetting bits in said first set which have previously been set.
Claim 5
Dependent Claim
46 words
A method according to claim 3 wherein said step of tracing includes the step of searching said flow graph to find any elements defining jump-to-subroutine instructions where the required set is not empty, and reporting such occurrence to a user of said computer as non-transportable code.
Claim 6
Dependent Claim
44 words
A method according to claim 4 wherein said step of searching is responsive to any elements defining routine entry points where the required set is not empty, and reporting such occurrence to a user of said computer as a possible error in said code.
Claim 7
Dependent Claim
50 words
A method according to claim 3 wherein said step of tracing includes the step of searching said flow graph to find any elements defining jump-to-subroutine instructions where the required set is not empty, and reporting such occurrence to a user of said computer as a possible error in said code.
Claim 8
Dependent Claim
13 words
A method according to claim 1 wherein each said element is a tuple.
Claim 9
Dependent Claim
21 words
A method according to claim 7 wherein each said block begins with an entry and ends in a branch or return.
Claim 10
Dependent Claim
180 words
Apparatus for processing input computer code by a computer in a code translator to produce translated code, comprising: means for generating a flow graph in an intermediate language from said code, the flow graph being a data structure 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 with no intermediate exit or entry; means for tracing in a reverse direction from its exit to its entry through each block of said flow graph to detect any elements which read or set condition codes; means for producing from those detected elements which read condition codes a first set of condition codes; means for removing from the first set those condition codes which are set by other detect elements to produce a second required set of required condition codes; and means for generating from the required set instructions in said translated code to set the required condition codes to simulate reading and setting of the condition codes.
Claim 11
Dependent Claim
180 words
Apparatus for processing input computer code by a computer in a code translator to produce translated code, comprising: means for generating a flow graph in an intermediate language from said code, the flow graph being a data structure 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 with no intermediate exit or entry; means for tracing in a reverse direction from its exit to its entry through each block of said flow graph to detect any elements which read or set condition codes; means for producing from those detected elements which read condition codes a first set of condition codes; means for removing from the first set those condition codes which are set by other detect elements to produce a second required set of required condition codes; and means for generating from the required set instructions in said translated code to set the required condition codes to simulate reading and setting of the condition codes.
Claim 12
Dependent Claim
17 words
Apparatus according to claim 9, wherein said condition codes include overflow, equal to zero, negative and carry.
Claim 13
Dependent Claim
28 words
An apparatus according to claim 10 wherein said means for removing said condition codes includes means for resetting bits in said required set which have previously been set.
Claim 14
Dependent Claim
12 words
Apparatus according to claim 9 wherein each said element is a tuple.
Claim 15
Dependent Claim
20 words
Apparatus according to claim 12 wherein each said block begins with an entry and ends in a branch or return.
Claim 16
Independent Claim
210 words
A method executed by a computer for compiling input code written for a first computer architecture to produce object code for a different computer architecture, said first computer architecture including condition codes in arithmetic and logic operation, said different computer architecture not including condition codes, comprising the steps of: accessing and parsing said code by said computer to generate a flow graph in an intermediate language from said input code by a converter, the flow graph being a data structure composed of blocks, and the blocks being composed of tuples, where each tuple represents a single expression in said input code, and where each block represents a sequence of one or more tuples with no intermediate exit or entry; tracing through each block of said flow graph in a reverse direction from its exit to its entry to detect any tuples which read or set condition codes; producing from those detected tuples which read condition codes a first set of condition codes; removing from the first set those condition codes which are set by other detected tuples to produce a second set of required condition codes; and generating operations in said object code using said required set to simulate setting and reading of the condition codes in said required set.
Claim 17
Independent Claim
210 words
A method executed by a computer for compiling input code written for a first computer architecture to produce object code for a different computer architecture, said first computer architecture including condition codes in arithmetic and logic operation, said different computer architecture not including condition codes, comprising the steps of: accessing and parsing said code by said computer to generate a flow graph in an intermediate language from said input code by a converter, the flow graph being a data structure composed of blocks, and the blocks being composed of tuples, where each tuple represents a single expression in said input code, and where each block represents a sequence of one or more tuples with no intermediate exit or entry; tracing through each block of said flow graph in a reverse direction from its exit to its entry to detect any tuples which read or set condition codes; producing from those detected tuples which read condition codes a first set of condition codes; removing from the first set those condition codes which are set by other detected tuples to produce a second set of required condition codes; and generating operations in said object code using said required set to simulate setting and reading of the condition codes in said required set.
Claim 18
Dependent Claim
107 words
A method according to claim 14 including the step of, upon calling a predecessor block immediately preceding a given block, passing said required set for said given block to said predecessor block, and thereafter: if said predecessor block is encountered in another backward flow path, and another required set for said predecessor block is a subset of said required set passed to said predecessor block, then omitting visiting said predecessor block again, or if said required set passed to said predecessor block does not include a condition code of a required set of a block in said another backward flow path, then visiting said predecessor block again.
Claim 19
Dependent Claim
39 words
A method according to claim 14 further comprising tracing all paths in said flow graph from the end of said code to the beginning of said code even if some blocks are visited more than once in said tracing.
Claim 20
Dependent Claim
24 words
A method according to claim 16 wherein said set step of removing includes resetting bits in said required set which have previously been set.
Claim 21
Dependent Claim
51 words
A method according to claim 17 wherein said step of tracing includes the step of searching said flow graph to find any tuples defining jump-to-subroutine instructions where the required set is not empty, and reporting such occurrence to a user of said computer as a possible error in said input code.
Claim 22
Dependent Claim
24 words
A method according to claim 14 wherein said first computer architecture is a CISC architecture and said different computer architecture is a RISC architecture.
Claim 23
Dependent Claim
16 words
A method according to claim 14 wherein said input code includes a plurality of callable routines.
Claim 24
Independent Claim
194 words
A method of processing input computer code by a computer in a code translator to produce translated code, for detecting and reporting code errors and code which is not compilable, comprising the steps of: accessing and parsing said code by said computer to generate allow graph in an intermediate language from said code, the flow graph being a data structure 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 with no intermediate exit or entry; tracing through each block of said flow graph in a reverse direction from its exit to its entry to identify elements which read or set condition codes; producing from those detected elements which read condition codes a first set of condition codes; removing from the first set those condition codes which are set by other detected elements to produce a second required set of required condition codes; and generating from the required set instructions in said translated code to set the required condition codes to simulate reading and setting of the condition codes.
Claim 25
Independent Claim
194 words
A method of processing input computer code by a computer in a code translator to produce translated code, for detecting and reporting code errors and code which is not compilable, comprising the steps of: accessing and parsing said code by said computer to generate allow graph in an intermediate language from said code, the flow graph being a data structure 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 with no intermediate exit or entry; tracing through each block of said flow graph in a reverse direction from its exit to its entry to identify elements which read or set condition codes; producing from those detected elements which read condition codes a first set of condition codes; removing from the first set those condition codes which are set by other detected elements to produce a second required set of required condition codes; and generating from the required set instructions in said translated code to set the required condition codes to simulate reading and setting of the condition codes.
Claim 26
Dependent Claim
72 words
A method according to claim 21 including the step of, upon calling a predecessor block immediately preceding a given block, passing said required set for said given block to said predecessor block, and thereafter, if said predecessor block is encountered in another backward flow path, and another required set of said predecessor block is a subset of said required set passed to said predecessor block, then omitting visiting said predecessor block again.
Claim 27
Dependent Claim
41 words
A method according to claim 22 wherein, if said required set passed to said predecessor block does not include a condition code of a required set of a block in said another backward flow path, then visiting said predecessor block again.
Claim 28
Dependent Claim
28 words
A method according to claim 21 wherein said step of removing said condition codes includes zeroing bits in said required set which have previously been set to one.
Claim 29
Dependent Claim
51 words
A method according to claim 21 wherein said step of tracing includes the step of searching said flow graph to find any elements defining jump-to-subroutine instructions where the required set is not empty, and reporting such occurrence to a user of said computer as a possible error in said input code.
Claim 30
Dependent Claim
21 words
A method according to claim 21 wherein each said block begins with an entry and ends in a branch or return.
Claim 31
Dependent Claim
12 words
A method according to claim 26 wherein each said element is tuple.
Claim 32
Dependent Claim
42 words
A method according to claim 21 wherein said step of tracing includes the step of searching for any elements defining jump-to-subroutine instructions where the required set is not empty, and reporting such occurrence to a user of said computer as non-transportable code.
Claim 33
Dependent Claim
44 words
A method according to claim 21 wherein said step of tracing includes searching for any elements defining routine entry points where the required set is not empty, and reporting such occurrence to a user of said computer as a possible error in said code.
References Cited (Backward Citations)
US4167778A
Cited
US4642764A
Cited
US4667290A
Cited
US5142681A
Cited
US4802091A
Cited
US4951195A
Cited
WO1990001738A1
Cited
EP0372835A2
Cited
US5159687A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-01-28 | 2000-07-29 | 2001-01-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-01-28 | 2004-07-29 | 2005-01-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-01-28 | 2008-07-29 | 2009-01-28 | $7700.00 | Window Closed / Lapsed |