US5301325A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Use of stack depth to identify architechture and calling standard dependencies in machine code
Assignee: Hewlett Packard Development Co LP
•
Filing: 1991-03-07
•
Granted: 1994-04-05
•
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 17:07
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/52; G06F8/70; G06F8/76
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
246 words
A method executed on a processor for operating on computer code, said computer code being in a first language and including references to a stack pointer, comprising the steps of: accessing said computer code and generating therefrom a flow graph in an intermediate language, 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 at least one element; tracing through each block of said flow graph to detect any stack-affecting elements which have the effect of modifying said stack pointer, said stack-affecting elements incrementing or decrementing said stack pointer, and recording for each block the difference between the number of stack-affecting elements which increment said stack pointer and the number of said stack-affecting elements which decrement said stack pointer to thereby record the net change in the stack pointer by elements of said block, and also recording the difference between the number of stack-affecting elements which increment said stack pointer and the number of said stack-affecting elements which decrement said stack pointer to thereby record the net change in the total depth of the stack from the beginning of said tracking; and in response to said recording of said net change in said stack pointer and said net change in stack depth, visually reporting to a user of said processor the identity of selected blocks, said selected blocks having potentially improper stack references.
Claim 2
Independent Claim
246 words
A method executed on a processor for operating on computer code, said computer code being in a first language and including references to a stack pointer, comprising the steps of: accessing said computer code and generating therefrom a flow graph in an intermediate language, 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 at least one element; tracing through each block of said flow graph to detect any stack-affecting elements which have the effect of modifying said stack pointer, said stack-affecting elements incrementing or decrementing said stack pointer, and recording for each block the difference between the number of stack-affecting elements which increment said stack pointer and the number of said stack-affecting elements which decrement said stack pointer to thereby record the net change in the stack pointer by elements of said block, and also recording the difference between the number of stack-affecting elements which increment said stack pointer and the number of said stack-affecting elements which decrement said stack pointer to thereby record the net change in the total depth of the stack from the beginning of said tracking; and in response to said recording of said net change in said stack pointer and said net change in stack depth, visually reporting to a user of said processor the identity of selected blocks, said selected blocks having potentially improper stack references.
Claim 3
Dependent Claim
64 words
A method according to claim 1 wherein said step of tracing includes the step of recording for each block that said block has been visited in said tracing, and in tracing through each block of said flow graph checking each block before entering to see if the block has been visited, and, if so, going to another block rather than visiting said block again.
Claim 4
Dependent Claim
52 words
A method according to claim 2 including the step of, upon completing said step of tracing, visually reporting to a user of said processor if a difference is detected in the content of recorded total depth of the stack for a current block and a successor block which has already been visited.
Claim 5
Dependent Claim
15 words
A method according to claim 3 wherein said code includes a plurality of callable routines.
Claim 6
Dependent Claim
25 words
A method according to claim 1 wherein each of said intermediate-language elements is a tuple data structure including a identity of an operation and operands.
Claim 7
Dependent Claim
35 words
A method according to claim 1 wherein each said block begins with an entry and ends in a branch or return with no intermediate entry into said block between beginning and end of said block.
Claim 8
Dependent Claim
265 words
Computer apparatus for operating on computer code, said computer code being in a first language and including references to a stack pointer, comprising: means for accessing said computer code and generating a flow graph in an intermediate language from said code, the flow graph being composed of blocks, and the blocks being composed of tuples, where each tuple represents a single expression in said code, and where each block represents a sequence of at least one tuple beginning with an entry and ending in a branch or return with no intermediate exit or entry; means for tracing through each block of said flow graph to detect any stack-affecting tuple which have the effect of modifying the stack pointer, said stack-affecting tuples incrementing or decrementing said stack pointer, and means for recording for each block the difference between the number of stack-affecting tuples which increment said stack pointer and the number of said stack-affecting tuples which decrement said stack pointer to thereby record the net change in the stack pointer by tuples of said block, and also recording the difference between the number of stack-affecting tuples which increment said stack pointer and the number of said stack-affecting tuples which decrement said stack pointer to thereby record the net change in the total depth of the stack from the beginning of said tracing; and means responsive to said recording of said net change in said stack pointer and said net change in stack depth for visually reporting to a user of said computer apparatus the identity of selected blocks, said selected blocks having potentially improper stack references.
Claim 9
Dependent Claim
265 words
Computer apparatus for operating on computer code, said computer code being in a first language and including references to a stack pointer, comprising: means for accessing said computer code and generating a flow graph in an intermediate language from said code, the flow graph being composed of blocks, and the blocks being composed of tuples, where each tuple represents a single expression in said code, and where each block represents a sequence of at least one tuple beginning with an entry and ending in a branch or return with no intermediate exit or entry; means for tracing through each block of said flow graph to detect any stack-affecting tuple which have the effect of modifying the stack pointer, said stack-affecting tuples incrementing or decrementing said stack pointer, and means for recording for each block the difference between the number of stack-affecting tuples which increment said stack pointer and the number of said stack-affecting tuples which decrement said stack pointer to thereby record the net change in the stack pointer by tuples of said block, and also recording the difference between the number of stack-affecting tuples which increment said stack pointer and the number of said stack-affecting tuples which decrement said stack pointer to thereby record the net change in the total depth of the stack from the beginning of said tracing; and means responsive to said recording of said net change in said stack pointer and said net change in stack depth for visually reporting to a user of said computer apparatus the identity of selected blocks, said selected blocks having potentially improper stack references.
Claim 10
Dependent Claim
65 words
Apparatus according to claim 7, wherein said means for tracing includes means for recording for each block that said block has been visited in said tracing, and means effective in tracing through each block of said flow graph for checking each block before entering to see if the block has been visited, and, if so, going to another block rather than visiting said block again.
Claim 11
Dependent Claim
49 words
Apparatus according to claim 7 including means for, upon completing said tracing of a block, visually reporting to a user of said processor if a difference in the content of recorded total depth of the stack for a current block and a successor block which has already been visited.
Claim 12
Dependent Claim
25 words
Apparatus according to claim 7 wherein each of said intermediate language elements is a tuple data structure including an identity of an operation and operands.
Claim 13
Dependent Claim
25 words
Apparatus according to claim 10 wherein each of said blocks begins with an entry and ends in a branch or return with no intermediate entry.
Claim 14
Independent Claim
301 words
A method executed on a processor, comprising the steps of: accessing said computer code and of compiling input code written for a first machine architecture to produce object code for a different machine architecture, said input code being in a first language and including references to a stack pointer, comprising the steps of: accessing said input code and generating a flow graph in an intermediate language from said input 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 code, and where each block represents a sequence of at least one tuple beginning with an entry and ending in a branch or return with no intermediate exit or entry; tracing through each block of said flow graph to detect stack-affecting tuples which have the effect of modifying the stack pointer, said stack-affecting tuples incrementing or decrementing said stack pointer, and recording for each block the difference between the number of stack-affecting tuples which increment said stack pointer and the number of said stack-affecting tuples which decrement said stack pointer to thereby record the net change in the stack pointer by stack-affecting tuples of said block which have the effect of modifying the stack pointer, and also recording the difference between the number of stack-affecting tuples which increment said stack pointer and the number of said stack-affecting tuples which decrement said stack pointer to thereby record the net change in the total depth of the stack from the beginning of said tracing; and in response to said recording of said net change in said stack pointer and said net change in stack depth, visually reporting to a user of said processor the identity of selected blocks, said selected blocks having potentially improper stack references.
Claim 15
Independent Claim
301 words
A method executed on a processor, comprising the steps of: accessing said computer code and of compiling input code written for a first machine architecture to produce object code for a different machine architecture, said input code being in a first language and including references to a stack pointer, comprising the steps of: accessing said input code and generating a flow graph in an intermediate language from said input 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 code, and where each block represents a sequence of at least one tuple beginning with an entry and ending in a branch or return with no intermediate exit or entry; tracing through each block of said flow graph to detect stack-affecting tuples which have the effect of modifying the stack pointer, said stack-affecting tuples incrementing or decrementing said stack pointer, and recording for each block the difference between the number of stack-affecting tuples which increment said stack pointer and the number of said stack-affecting tuples which decrement said stack pointer to thereby record the net change in the stack pointer by stack-affecting tuples of said block which have the effect of modifying the stack pointer, and also recording the difference between the number of stack-affecting tuples which increment said stack pointer and the number of said stack-affecting tuples which decrement said stack pointer to thereby record the net change in the total depth of the stack from the beginning of said tracing; and in response to said recording of said net change in said stack pointer and said net change in stack depth, visually reporting to a user of said processor the identity of selected blocks, said selected blocks having potentially improper stack references.
Claim 16
Dependent Claim
64 words
A method according to claim 10 wherein said step of tracing includes the step of recording for each block that said block has been visited in said tracing, and in tracing through each block of said flow graph checking each block before entering to see if the block has been visited, and, if so, going to another block rather than visiting said block again.
Claim 17
Dependent Claim
52 words
A method according to claim 11 including the step of, upon completing said step of tracing, visually reporting to a user of said processor if a difference is detected in the content of recorded total depth of the stack for a current block and a successor block which has already been visited.
Claim 18
Dependent Claim
15 words
A method according to claim 14 wherein said code includes a plurality of callable routines.
Claim 19
Independent Claim
271 words
A method executed on a processor for operating on computer code, said computer code being in a first language and including references to a stack pointer, comprising the steps of: accessing said computer code and generating therefrom a flow graph in an intermediate language from said code, the flow graph being composed of blocks, and the blocks being composed of tuples, where each tuple represents a single expression in said code, and where each block represents a sequence of at least one tuple beginning with an entry and ending in a branch or return with no intermediate exit or entry; tracing through each block of said flow graph to identify stack-affecting tuples which reference the stack or have the effect of incrementing or decrementing the stack pointer, and recording for each block the difference between the number of stack-affecting tuples which increment said stack pointer and the number of said stack-affecting tuples which decrement said stack pointer to thereby record the net change in the stack pointer by tuples of said block, and also recording the difference between the number of stack-affecting tuples which increment said stack pointer and the number of said stack-affecting tuples which decrement said stack pointer to thereby record the net change in the total depth of the stack from the beginning of said tracing, upon completing said step of tracing for all of said blocks, in response to said recording of said net change in said stack pointer and said net change in stack depth, visually reporting to a user of said processor the identity of selected blocks, said selected blocks having potentially improper stack references.
Claim 20
Independent Claim
271 words
A method executed on a processor for operating on computer code, said computer code being in a first language and including references to a stack pointer, comprising the steps of: accessing said computer code and generating therefrom a flow graph in an intermediate language from said code, the flow graph being composed of blocks, and the blocks being composed of tuples, where each tuple represents a single expression in said code, and where each block represents a sequence of at least one tuple beginning with an entry and ending in a branch or return with no intermediate exit or entry; tracing through each block of said flow graph to identify stack-affecting tuples which reference the stack or have the effect of incrementing or decrementing the stack pointer, and recording for each block the difference between the number of stack-affecting tuples which increment said stack pointer and the number of said stack-affecting tuples which decrement said stack pointer to thereby record the net change in the stack pointer by tuples of said block, and also recording the difference between the number of stack-affecting tuples which increment said stack pointer and the number of said stack-affecting tuples which decrement said stack pointer to thereby record the net change in the total depth of the stack from the beginning of said tracing, upon completing said step of tracing for all of said blocks, in response to said recording of said net change in said stack pointer and said net change in stack depth, visually reporting to a user of said processor the identity of selected blocks, said selected blocks having potentially improper stack references.
Claim 21
Dependent Claim
15 words
A method according to claim 16 wherein said code includes a plurality of callable routines.
Claim 22
Dependent Claim
28 words
A method according to claim 17 wherein said step of tracing includes the step of recording for each block that said block has been visited in said tracing.
Claim 23
Dependent Claim
45 words
A method according to claim 18 including the step of, in tracing through each block of said flow graph, checking each block before entering to see if the block has been visited, and, if so, going to another block rather than visiting said block again.
Claim 24
Dependent Claim
59 words
A method according to claim 19 including the step of, upon completing said steps of tracing, visually reporting to a user of said processor if a difference is detected in the content of recorded total depth of the stack for a current block and the content of recorded total depth for a successor block which has already been visited.
Claim 25
Dependent Claim
28 words
A method according to claim 16 wherein said input code is written for a first machine architecture, and said method produces object code for a different machine architecture.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-04-04 | 1997-10-04 | 1998-04-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-04-04 | 2001-10-04 | 2002-04-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-04-04 | 2005-10-04 | 2006-04-05 | $7700.00 | Window Closed / Lapsed |