US5287490A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Identifying plausible variable length machine code of selecting address in numerical sequence, decoding code strings, and following execution transfer paths
Assignee: Hewlett Packard Development Co LP
•
Filing: 1991-03-07
•
Granted: 1994-02-15
•
Expires: 2011-03-07
Abstract
Abstract Information about the location of untranslated instructions in an original program is discovered during execution of a partial translation of the program, and that information is used later during re-translation of the original program. Preferably the information includes origin addresses of translated instructions and corresponding destination address of untranslated instructions of execution transfers that occur during the execution of the partial translation. Preferably this feedback of information from execution to re-translation is performed after each execution of the translated program so that virtually all of the instructions in the original program will eventually be located and translated. To provide an indication of the fraction of the code that has been translated, the program is scanned to find plausible code in the areas of memory that do not contain translated code. The plausible code is identified by selecting addresses according to three different scanning modes and attempting to decode variable-length instructions beginning at the selected addresses. The scanning modes include a first mode in which addresses are selected in numerical sequence by a scan pointer, a second mode in which addresses are selected in instruction-length sequence by an instruction decode pointer, and a third mode in which the selected addresses are destination addresses of previously-decoded execution transfer instructions.
Inventors
- 👤 Richard L. Sites
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 22:07
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/52
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
296 words
A method of operating a digital computer having an addressable memory, said addressable memory containing a computer program, said computer program including instructions and data at respective address locations of said addressable memory, each of said instructions consisting of contents of a variable number of contiguous ones of said address locations depending upon an operation specified by said each of said instructions, said method identifying address locations of said addressable memory that appear to contain said instructions of said computer program, said method comprising the steps of: a) selecting program addresses in numerical sequence, and attempting to decode an instruction in said addressable memory at each program address until an initial instruction is decoded; and when said initial instruction is decoded, then b) attempting to decode a string of instructions immediately following said initial instruction until an execution transfer instruction is decoded, and when an attempt to decode an instruction fails, continuing said selecting program addresses and said attempting to decode an instruction at each program address as set out in said step a), and when an execution transfer instruction is decoded, then c) attempting to decode an instruction at a destination address of the decoded execution transfer instruction, and when the attempt to decode an instruction at the destination address of the decoded execution transfer instruction fails, continuing said selecting program addresses and said attempting to decode an instruction at each program address as set out in step a), and when the attempt to decode an instruction at the destination address of the decoded execution transfer instruction succeeds, then identifying, as said address locations of said addressable memory that appear to contain said instructions of said computer program, the address locations including said initial instruction and said string of instructions including said execution transfer instruction.
Claim 2
Independent Claim
296 words
A method of operating a digital computer having an addressable memory, said addressable memory containing a computer program, said computer program including instructions and data at respective address locations of said addressable memory, each of said instructions consisting of contents of a variable number of contiguous ones of said address locations depending upon an operation specified by said each of said instructions, said method identifying address locations of said addressable memory that appear to contain said instructions of said computer program, said method comprising the steps of: a) selecting program addresses in numerical sequence, and attempting to decode an instruction in said addressable memory at each program address until an initial instruction is decoded; and when said initial instruction is decoded, then b) attempting to decode a string of instructions immediately following said initial instruction until an execution transfer instruction is decoded, and when an attempt to decode an instruction fails, continuing said selecting program addresses and said attempting to decode an instruction at each program address as set out in said step a), and when an execution transfer instruction is decoded, then c) attempting to decode an instruction at a destination address of the decoded execution transfer instruction, and when the attempt to decode an instruction at the destination address of the decoded execution transfer instruction fails, continuing said selecting program addresses and said attempting to decode an instruction at each program address as set out in step a), and when the attempt to decode an instruction at the destination address of the decoded execution transfer instruction succeeds, then identifying, as said address locations of said addressable memory that appear to contain said instructions of said computer program, the address locations including said initial instruction and said string of instructions including said execution transfer instruction.
Claim 3
Dependent Claim
39 words
The method as claimed in claim 1, wherein program addresses are selected in numerical sequence in step a) by a scan pointer, and program addresses are selected in step b) by an instruction decode pointer for decoding the instructions.
Claim 4
Dependent Claim
50 words
The method as claimed in claim 1, further comprising the step of building a flowgraph of instructions by continuing to decode instructions in execution paths continuing from the destination of said execution transfer instruction when step c) decodes an instruction at said destination address of said decoded execution transfer instruction.
Claim 5
Dependent Claim
46 words
The method as claimed in claim 1, wherein said instructions include instructions having opcodes and variable-length specifiers used with the same opcodes, and wherein attempts to decode some of said instructions fail because specifiers required for opcodes of said some of said instruction are not decoded.
Claim 6
Dependent Claim
36 words
The method as claimed in claim 1, wherein some program addresses of said computer program are known to contain instructions, and wherein said step a) skips over the program addresses that are known to contain instructions.
Claim 7
Dependent Claim
44 words
The method as claimed in claim 1, wherein some program addresses of said computer program are known to contain instructions, and wherein the decoding of an instruction is not permitted when an instruction being decoded partially overlaps program addresses known to contain an instruction.
Claim 8
Dependent Claim
85 words
The method as claimed in claim 6, wherein an estimate of the fraction of known instructions in said computer program is computed as the ratio of the number of program addresses known to contain instructions to the sum of the number of program addresses known to contain instructions and the number of other program addresses in said program that contain instructions in execution paths including instructions decoded in both steps a) and b) and for which said execution transfer instruction has a valid destination address.
Claim 9
Dependent Claim
82 words
The method as claimed in claim 1, wherein some program addresses of said computer program are known to contain instructions, and further comprising a step d) of identifying, as said address locations of said addressable memory that appear to contain said instructions of said computer program, the address locations including said initial instruction and said string of instructions including said execution transfer instruction when said destination address of said decoded execution transfer instruction is a program address known to contain an instruction.
Claim 10
Dependent Claim
45 words
The method as claimed in claim 1, wherein said step a) skips over a program address containing a value that is included in a predefined set of values, regardless of whether an attempt to decode an instruction starting at the program address would be successful.
Claim 11
Dependent Claim
25 words
The method as claimed in claim 9, wherein said set of values includes values that indicate instructions having a length of one program address location.
Claim 12
Dependent Claim
17 words
The method as claimed in claim 9, wherein said set of values includes opcodes of privileged instructions.
Claim 13
Dependent Claim
17 words
The method as claimed in claim 9, wherein said set of values includes the value of zero.
Claim 14
Dependent Claim
27 words
The method as claimed in claim 1, wherein said step a) skips over a program address that is the first address of a string of alphanumeric characters.
Claim 15
Dependent Claim
20 words
The method as claimed in claim 13, wherein said string of alphanumeric characters includes at least four printable ASCII characters.
Claim 16
Dependent Claim
291 words
A digital computer system for identifying instructions that appear to be true instructions of a computer program; said digital computer system comprising an addressable memory, said addressable memory containing said computer program, said computer program including data and said instructions of said computer program at respective address locations of said addressable memory, each of said instructions consisting of contents of a variable number of contiguous ones of said address locations depending upon an operation specified by said each of said instructions, said digital computer system further comprising: first means for selecting program addresses in numerical sequence, second means for attempting to decode an instruction at each program address selected by said first means for selecting and for indicating when an initial instruction is decoded, third means, activated when said second means decodes an initial instruction, for attempting to decode a string of instructions in said addressable memory immediately following said initial instruction and including an execution transfer instruction, for indicating when an execution transfer instruction is decoded, and for activating said first means for selecting when a string of instructions immediately following said initial instruction and including an execution transfer instruction is not decoded; and fourth means, activated when third means decodes an execution transfer instruction, for attempting to decode an instruction at a destination address of the decoded execution transfer instruction, and for activating said first means for selecting when an instruction is not decoded at the destination address of the decoded execution transfer instruction, and when an instruction is decoded at the destination address of the decoded execution transfer instruction, then for identifying, as said instructions that appear to be true instructions of said computer program, said initial instruction and said string of instructions including said execution transfer instruction.
Claim 17
Dependent Claim
291 words
A digital computer system for identifying instructions that appear to be true instructions of a computer program; said digital computer system comprising an addressable memory, said addressable memory containing said computer program, said computer program including data and said instructions of said computer program at respective address locations of said addressable memory, each of said instructions consisting of contents of a variable number of contiguous ones of said address locations depending upon an operation specified by said each of said instructions, said digital computer system further comprising: first means for selecting program addresses in numerical sequence, second means for attempting to decode an instruction at each program address selected by said first means for selecting and for indicating when an initial instruction is decoded, third means, activated when said second means decodes an initial instruction, for attempting to decode a string of instructions in said addressable memory immediately following said initial instruction and including an execution transfer instruction, for indicating when an execution transfer instruction is decoded, and for activating said first means for selecting when a string of instructions immediately following said initial instruction and including an execution transfer instruction is not decoded; and fourth means, activated when third means decodes an execution transfer instruction, for attempting to decode an instruction at a destination address of the decoded execution transfer instruction, and for activating said first means for selecting when an instruction is not decoded at the destination address of the decoded execution transfer instruction, and when an instruction is decoded at the destination address of the decoded execution transfer instruction, then for identifying, as said instructions that appear to be true instructions of said computer program, said initial instruction and said string of instructions including said execution transfer instruction.
Claim 18
Dependent Claim
52 words
The digital computer system as claimed in claim 15, further comprising means for building a flowgraph of instructions by continuing to decode instructions in execution paths continuing from the destination of said execution transfer instruction when said fourth means decodes an instruction at said destination address of said decoded execution transfer instruction.
Claim 19
Dependent Claim
45 words
The digital computer system as claimed in claim 15, wherein some addresses of said computer program are known to contain instructions of said computer program, and wherein said first means skips over the program addresses that are known to contain instructions of said computer program.
Claim 20
Dependent Claim
47 words
The digital computer system as claimed in claim 15, wherein said first means skips over a program address containing a value that is included in a predefined set of values, regardless of whether an attempt to decode an instruction starting at the program address would be successful.
Claim 21
Dependent Claim
29 words
The digital computer system as claimed in claim 15, wherein said first means skips over a program address that contains the first character in a string of alphanumeric characters.
Claim 22
Independent Claim
387 words
A method of operating a digital computer having an addressable memory, said addressable memory containing a computer program, said computer program including instructions and data at respective address locations of said addressable memory, each of said instructions consisting of contents of a variable number of contiguous ones of said address locations depending upon an operation specified by said each of said instructions, said method identifying address locations of said addressable memory that appear to contain said instructions of said computer program, said method comprising the steps of: a) selecting program addresses in numerical sequence, and attempting to decode an instruction in said addressable memory at each program address until an initial instruction is decoded; and when said initial instruction is decoded, then b) attempting to decode a string of instructions immediately following said initial instruction until an execution transfer instruction is decoded, and when an attempt to decode an instruction fails, continuing said selecting program addresses and said attempting to decode an instruction at each program address as set out in said step a), and when an execution transfer instruction is decoded, then c) attempting to decode an instruction at a destination address of the decoded execution transfer instruction, and when the attempt to decode an instruction at the destination address of the decoded execution transfer instruction fails, continuing said selecting program addresses and said attempting to decode an instruction at each program address as set out in step a), and when the attempt to decode an instruction at the destination address of the decoded execution transfer instruction succeeds, then identifying, as said address locations of said addressable memory that appear to contain said instructions of said computer program, the address locations including said initial instruction and said string of instructions including said execution transfer instruction, wherein some program addresses of said computer program are known to contain instructions, and wherein said step a) skips over the program addresses that are known to contain instructions, wherein the decoding of an instruction is not permitted when an instruction being decoded partially overlaps program addresses known to contain an instruction, and wherein said step a) skips over a program address containing a value that is included in a predefined set of values, regardless of whether an attempt to decode an instruction starting at the program address would be successful.
Claim 23
Independent Claim
387 words
A method of operating a digital computer having an addressable memory, said addressable memory containing a computer program, said computer program including instructions and data at respective address locations of said addressable memory, each of said instructions consisting of contents of a variable number of contiguous ones of said address locations depending upon an operation specified by said each of said instructions, said method identifying address locations of said addressable memory that appear to contain said instructions of said computer program, said method comprising the steps of: a) selecting program addresses in numerical sequence, and attempting to decode an instruction in said addressable memory at each program address until an initial instruction is decoded; and when said initial instruction is decoded, then b) attempting to decode a string of instructions immediately following said initial instruction until an execution transfer instruction is decoded, and when an attempt to decode an instruction fails, continuing said selecting program addresses and said attempting to decode an instruction at each program address as set out in said step a), and when an execution transfer instruction is decoded, then c) attempting to decode an instruction at a destination address of the decoded execution transfer instruction, and when the attempt to decode an instruction at the destination address of the decoded execution transfer instruction fails, continuing said selecting program addresses and said attempting to decode an instruction at each program address as set out in step a), and when the attempt to decode an instruction at the destination address of the decoded execution transfer instruction succeeds, then identifying, as said address locations of said addressable memory that appear to contain said instructions of said computer program, the address locations including said initial instruction and said string of instructions including said execution transfer instruction, wherein some program addresses of said computer program are known to contain instructions, and wherein said step a) skips over the program addresses that are known to contain instructions, wherein the decoding of an instruction is not permitted when an instruction being decoded partially overlaps program addresses known to contain an instruction, and wherein said step a) skips over a program address containing a value that is included in a predefined set of values, regardless of whether an attempt to decode an instruction starting at the program address would be successful.
Claim 24
Dependent Claim
25 words
The method as claimed in claim 20, wherein said set of values includes values that indicate instructions having a length of one program address location.
Claim 25
Dependent Claim
17 words
The method as claimed in claim 20, wherein said set of values includes opcodes of privileged instructions.
Claim 26
Dependent Claim
17 words
The method as claimed in claim 20, wherein said set of values includes the value of zero.
Claim 27
Dependent Claim
27 words
The method as claimed in claim 20, wherein said step a) skips over a program address that is the first address of a string of alphanumeric characters.
Claim 28
Dependent Claim
20 words
The method as claimed in claim 24, wherein said string of alphanumeric characters includes at least four printable ASCII characters.
Claim 29
Independent Claim
450 words
A method of operating a digital computer having an addressable memory, said addressable memory containing a computer program, said computer program including instructions and data at respective address locations of said addressable memory, each of said instructions consisting of contents of a variable number of contiguous ones of said address locations depending upon an operation specified by said each of said instructions, said method identifying address locations of said addressable memory that appear to contain said instructions of said computer program, said method comprising the steps of: a) selecting program addresses in numerical sequence, and attempting to decode an instruction in said addressable memory at each program address until an initial instruction is decoded; and when said initial instruction is decoded, then b) attempting to decode a string of instructions immediately following said initial instruction until an execution transfer instruction is decoded, and when an attempt to decode an instruction fails, continuing said selecting program addresses and said attempting to decode an instruction at each program address as set out in said step a), and when an execution transfer instruction is decoded, then c) attempting to decode an instruction at a destination address of the decoded execution transfer instruction, and when the attempt to decode an instruction at the destination address of the decoded execution transfer instruction fails, continuing said selecting program addresses and said attempting to decode an instruction at each program address as set out in step a), and when the attempt to decode an instruction at the destination address of the decoded execution transfer instruction succeeds, then identifying, as said address locations of said addressable memory that appear to contain said instructions of said computer program, the address locations including said initial instruction and said string of instructions including said execution transfer instruction, wherein some program addresses of said computer program are known to contain instructions, and wherein said step a) skips over the program addresses that are known to contain instructions, wherein the decoding of an instruction is not permitted when an instruction being decoded partially overlaps program addresses known to contain an instruction, and wherein said step a) skips over a program address containing a value that is included in a predefined set of values, regardless of whether an attempt to decode an instruction starting at the program address would be successful, wherein said set of values includes values that indicate instructions having a length of one program address location, said set of values includes opcodes of privileged instructions, and said set of values includes the value of zero, and wherein said step a) skips over a program address that is the first address of a string of at least four printable ASCII alphanumeric characters.
Claim 30
Independent Claim
450 words
A method of operating a digital computer having an addressable memory, said addressable memory containing a computer program, said computer program including instructions and data at respective address locations of said addressable memory, each of said instructions consisting of contents of a variable number of contiguous ones of said address locations depending upon an operation specified by said each of said instructions, said method identifying address locations of said addressable memory that appear to contain said instructions of said computer program, said method comprising the steps of: a) selecting program addresses in numerical sequence, and attempting to decode an instruction in said addressable memory at each program address until an initial instruction is decoded; and when said initial instruction is decoded, then b) attempting to decode a string of instructions immediately following said initial instruction until an execution transfer instruction is decoded, and when an attempt to decode an instruction fails, continuing said selecting program addresses and said attempting to decode an instruction at each program address as set out in said step a), and when an execution transfer instruction is decoded, then c) attempting to decode an instruction at a destination address of the decoded execution transfer instruction, and when the attempt to decode an instruction at the destination address of the decoded execution transfer instruction fails, continuing said selecting program addresses and said attempting to decode an instruction at each program address as set out in step a), and when the attempt to decode an instruction at the destination address of the decoded execution transfer instruction succeeds, then identifying, as said address locations of said addressable memory that appear to contain said instructions of said computer program, the address locations including said initial instruction and said string of instructions including said execution transfer instruction, wherein some program addresses of said computer program are known to contain instructions, and wherein said step a) skips over the program addresses that are known to contain instructions, wherein the decoding of an instruction is not permitted when an instruction being decoded partially overlaps program addresses known to contain an instruction, and wherein said step a) skips over a program address containing a value that is included in a predefined set of values, regardless of whether an attempt to decode an instruction starting at the program address would be successful, wherein said set of values includes values that indicate instructions having a length of one program address location, said set of values includes opcodes of privileged instructions, and said set of values includes the value of zero, and wherein said step a) skips over a program address that is the first address of a string of at least four printable ASCII alphanumeric characters.
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-02-14 | 1997-08-16 | 1998-02-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-02-14 | 2001-08-16 | 2002-02-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-02-14 | 2005-08-16 | 2006-02-15 | $7700.00 | Window Closed / Lapsed |