US5450575A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Use of stack depth to identify machine code mistakes
Assignee: Hewlett Packard Development Co LP
•
Filing: 1991-03-07
•
Granted: 1995-09-12
•
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 can produce mistakes if not revised before converting, particularly relating to stack usage. By tracking stack usage within and across 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.
Inventors
- 👤 Richard L. Sites
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 05:02
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/36; G06F11/3604; G06F8/00; G06F8/40; G06F8/52
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
195 words
A method of processing computer code in a compiler or code translator, comprising the steps of: generating a flow graph representing said code, said flow graph being composed of a plurality of blocks, and said blocks being composed of a plurality of elements, each of said elements representing a single action in said code, each of said blocks representing a sequence of one or more of said elements beginning with an entry and ending in a branch or return, and each said block having no intermediate entry; tracing through each said block of said flow graph to detect any said elements which have an effect of modifying a stack pointer for a stack, and recording for each said block a net change in said stack pointer by said block and a total depth of said stack from a beginning of said tracing; and recording for each said block that said block has been visited in said tracing, and, in tracing through each said block of said flow graph, checking each said block before entering to see if said block has been visited, and, if so, going to another path rather than visiting said block again.
Claim 2
Independent Claim
195 words
A method of processing computer code in a compiler or code translator, comprising the steps of: generating a flow graph representing said code, said flow graph being composed of a plurality of blocks, and said blocks being composed of a plurality of elements, each of said elements representing a single action in said code, each of said blocks representing a sequence of one or more of said elements beginning with an entry and ending in a branch or return, and each said block having no intermediate entry; tracing through each said block of said flow graph to detect any said elements which have an effect of modifying a stack pointer for a stack, and recording for each said block a net change in said stack pointer by said block and a total depth of said stack from a beginning of said tracing; and recording for each said block that said block has been visited in said tracing, and, in tracing through each said block of said flow graph, checking each said block before entering to see if said block has been visited, and, if so, going to another path rather than visiting said block again.
Claim 3
Dependent Claim
39 words
A method according to claim 1 including the step of, upon completing said tracing step, reporting a difference in the recorded total depth of said stack for a current block and a successor block which has already been visited.
Claim 4
Dependent Claim
17 words
A method according to claim 1 wherein each of said elements is an instruction in object code.
Claim 5
Dependent Claim
30 words
A method according to claim 1 wherein said code includes a plurality of callable routines, and including the step of recording the stack depth while tracing each said callable routine.
Claim 6
Dependent Claim
36 words
A method according to claim 4 including the step of generating a plurality of code images from input computer code, and wherein at least two of said code images contain calls from one to the other.
Claim 7
Dependent Claim
24 words
A method according to claim 5 including the step of recording a stack depth for callable routines across said at least two code images.
Claim 8
Dependent Claim
200 words
Apparatus for processing computer code in a compiler or code translator, comprising: means for generating a flow graph representing said code, said flow graph being composed of a plurality of blocks, and said blocks being composed of a plurality of elements, each of said elements representing a single expression in said code, each of said blocks representing a sequence of one or more said elements beginning with an entry and ending in a branch or return, each of said blocks having no intermediate exit or entry; means for tracing through each said block of said flow graph to detect any said elements which have an effect of modifying said stack pointer, and means for recording for each said block a net change in a stack pointer of a stack by each said block and a total depth of said stack from a beginning of said tracing; and means for recording for each said block that said block has been visited in said tracing, and, in tracing through each said block of said flow graph, checking said block before entering to see if said block has been visited, and, if so, going to another path rather than visiting said block again.
Claim 9
Dependent Claim
200 words
Apparatus for processing computer code in a compiler or code translator, comprising: means for generating a flow graph representing said code, said flow graph being composed of a plurality of blocks, and said blocks being composed of a plurality of elements, each of said elements representing a single expression in said code, each of said blocks representing a sequence of one or more said elements beginning with an entry and ending in a branch or return, each of said blocks having no intermediate exit or entry; means for tracing through each said block of said flow graph to detect any said elements which have an effect of modifying said stack pointer, and means for recording for each said block a net change in a stack pointer of a stack by each said block and a total depth of said stack from a beginning of said tracing; and means for recording for each said block that said block has been visited in said tracing, and, in tracing through each said block of said flow graph, checking said block before entering to see if said block has been visited, and, if so, going to another path rather than visiting said block again.
Claim 10
Dependent Claim
39 words
Apparatus according to claim 7 including means for, upon completing a tracing of a block, reporting a difference in the recorded total depth of said stack for a current block and a successor block which has already been visited.
Claim 11
Independent Claim
182 words
A method of translating input code written for a first machine architecture to produce object code for a different machine architecture, comprising the steps of: generating a flow graph representing said input code, said flow graph being composed of a plurality of blocks, and said blocks being composed of a plurality of elements, each said element representing a single expression in said input code; tracing through each said block of said flow graph to detect any said elements which have an effect of modifying a stack pointer of a stack, and recording for each block a net change in said stack pointer by said elements of said block which have an effect of modifying said stack pointer and a total depth of said stack from a beginning of said tracing; and recording for each said block that said block has been visited in said tracing, and, in tracing through each said block of said flow graph, checking said block before entering to see if said block has been visited, and, if so, going to another path rather than visiting said block again.
Claim 12
Independent Claim
182 words
A method of translating input code written for a first machine architecture to produce object code for a different machine architecture, comprising the steps of: generating a flow graph representing said input code, said flow graph being composed of a plurality of blocks, and said blocks being composed of a plurality of elements, each said element representing a single expression in said input code; tracing through each said block of said flow graph to detect any said elements which have an effect of modifying a stack pointer of a stack, and recording for each block a net change in said stack pointer by said elements of said block which have an effect of modifying said stack pointer and a total depth of said stack from a beginning of said tracing; and recording for each said block that said block has been visited in said tracing, and, in tracing through each said block of said flow graph, checking said block before entering to see if said block has been visited, and, if so, going to another path rather than visiting said block again.
Claim 13
Dependent Claim
15 words
A method according to claim 9 wherein said different machine architecture is a RISC architecture.
Claim 14
Dependent Claim
35 words
A method according to claim 9 wherein each said block represents a sequence of one or more elements beginning with an entry and ending in a branch or return, and further has no immediate entry.
Claim 15
Dependent Claim
39 words
A method according to claim 9 including the step of, upon completing said tracing step, reporting a difference in the recorded total depth of said stack for a current block and a successor block which has already been visited.
Claim 16
Dependent Claim
15 words
A method according to claim 12 wherein said code includes a plurality of callable routines.
Claim 17
Independent Claim
135 words
A method of processing computer code in a compiler or code translator, comprising the steps of: generating a flow graph representing said code, said flow graph being composed of a plurality of blocks, and said blocks being composed of a plurality of elements, each said element representing a single expression in said code; tracing through each said block of said flow graph to identify any said elements which reference a stack or have an effect of modifying a stack pointer, and recording for each said block a net change in said stack pointer by said block and a total depth of said stack from a beginning of said tracing, and upon completing said step of tracing for all of said blocks, reporting to a user an identity of said blocks having potentially improper stack references.
Claim 18
Independent Claim
135 words
A method of processing computer code in a compiler or code translator, comprising the steps of: generating a flow graph representing said code, said flow graph being composed of a plurality of blocks, and said blocks being composed of a plurality of elements, each said element representing a single expression in said code; tracing through each said block of said flow graph to identify any said elements which reference a stack or have an effect of modifying a stack pointer, and recording for each said block a net change in said stack pointer by said block and a total depth of said stack from a beginning of said tracing, and upon completing said step of tracing for all of said blocks, reporting to a user an identity of said blocks having potentially improper stack references.
Claim 19
Dependent Claim
28 words
A method according to claim 14 wherein said input code is written for a first machine architecture, and said method produces object code for a different machine architecture.
Claim 20
Dependent Claim
35 words
A method according to claim 14 wherein each said block represents a sequence of one or more elements beginning with an entry and ending in a branch or return, and further has no intermediate entry.
Claim 21
Dependent Claim
17 words
A method according to claim 14 wherein each of said elements is an instruction in object code.
Claim 22
Dependent Claim
15 words
A method according to claim 14 wherein said code includes a plurality of callable routines.
Claim 23
Dependent Claim
24 words
A method according to claim 18 including the step of recording for each said block that said block has been visited in said tracing.
Claim 24
Dependent Claim
46 words
A method according to claim 19 including the step of, in tracing through each block of said flow graph, checking each said block before entering to see if said block has been visited, and, if so, going to another path rather than visiting said block again.
Claim 25
Dependent Claim
45 words
A method according to claim 20 including the step of, upon completing said steps of tracing, reporting a difference in the recorded total depth of the stack for a current block and the recorded total depth for a successor block which has already been visited.
Claim 26
Dependent Claim
30 words
A method according to claim 14 wherein said code includes a plurality of callable routines, and including the step of recording the stack depth while tracing each said callable routine.
Claim 27
Dependent Claim
36 words
A method according to claim 22 including the step of generating a plurality of code images from input computer code, and wherein at least two of said code images contain calls from one to the other.
Claim 28
Dependent Claim
24 words
A method according to claim 23 including the step of recording a stack depth for callable routines across said at least two code images.
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) | 1998-09-11 | 1999-03-13 | 1999-09-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-09-11 | 2003-03-13 | 2003-09-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-09-11 | 2007-03-13 | 2007-09-12 | $7700.00 | Window Closed / Lapsed |