Patent US5664191A successfully refreshed from Google Patents.
US5664191A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for improving the locality of memory references during execution of a computer program
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1994-06-30
•
Granted: 1997-09-02
•
Expires: 2014-06-30
Abstract
Abstract The present invention provides a method and system for determining an optimal placement order for basic blocks within a computer program to improve locality of reference and reduce the working set of the computer program. By reducing the working set, the computer program requires less memory than it normally would require to execute on a computer system. The optimal placement order for basic blocks within a computer program reflects the concurrency of usage for basic blocks during execution of the computer program. The method for determining an optimal placement order includes analyzing the computer program to identify all of the basic blocks, determining how many times each basic block is executed, assigning a placement order to each basic block depending upon how many times each basic block was executed, and reordering the basic blocks according to their assigned placement orders to produce an optimized computer program. The method used to identify all of the basic blocks includes disassembling known instruction addresses to identify the beginning and end of basic blocks and processing jump tables to identify more instruction addresses. Processing jump tables includes processing the first entry of every jump table before processing the second entry of any jump table. The present invention further optimizes a computer program by replacing rarely executed instructions with other instructions that require a smaller amount of storage space.
Inventors
- 👤 Robert I. Davidson
- 👤 Nathan Myhrvold
- 👤 Keith Randel Vogel
- 👤 Gideon Andreas Yuval
- 👤 Richard Shupak
- 👤 Norman Eugene Apperson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 20:42
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443; G06F8/4441; G06F8/4442
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
126 words
In a computer system, a method of identifying a plurality of basic blocks within a computer program comprising the steps of: identifying a plurality of jump tables within the computer program, each jump table having one or more entries, each entry representing a starting address of a basic block, the entries being ordered from a lowest to a highest entry; repeating the following sequence of steps until either all entries in the plurality of jump tables have been selected or it is determined that all of the basic blocks of the computer program have been identified; selecting the lowest entry that has not already been selected from among the plurality of jump tables; and identifying basic blocks which begin at the address of the selected entry.
Claim 2
Dependent Claim
126 words
In a computer system, a method of identifying a plurality of basic blocks within a computer program comprising the steps of: identifying a plurality of jump tables within the computer program, each jump table having one or more entries, each entry representing a starting address of a basic block, the entries being ordered from a lowest to a highest entry; repeating the following sequence of steps until either all entries in the plurality of jump tables have been selected or it is determined that all of the basic blocks of the computer program have been identified; selecting the lowest entry that has not already been selected from among the plurality of jump tables; and identifying basic blocks which begin at the address of the selected entry.
Claim 3
Dependent Claim
135 words
In a computer system, a method of code size reduction, the code including live code segments and dead code segments, comprising: locating a conditional branch from a live code segment to a dead code segment; replacing the located conditional branch with a conditional branch to the live code segment; storing the address of the conditional branch to the live code segment and the address of the dead code segment in a storage data structure outside of the live code segment; and providing a monitoring means for detecting execution of the conditional branch to the live code segment during execution of the live code, and, upon detection, searching the storage data structure for the address of the dead code segment corresponding to the address of the conditional branch, and causing execution of the dead code segment.
Claim 4
Dependent Claim
135 words
In a computer system, a method of code size reduction, the code including live code segments and dead code segments, comprising: locating a conditional branch from a live code segment to a dead code segment; replacing the located conditional branch with a conditional branch to the live code segment; storing the address of the conditional branch to the live code segment and the address of the dead code segment in a storage data structure outside of the live code segment; and providing a monitoring means for detecting execution of the conditional branch to the live code segment during execution of the live code, and, upon detection, searching the storage data structure for the address of the dead code segment corresponding to the address of the conditional branch, and causing execution of the dead code segment.
Claim 5
Dependent Claim
46 words
The method according to claim 2 wherein the providing step includes detecting the execution of the conditional branch by monitoring the program counter so that when the address of the conditional branch is stored in the program counter, the execution of the conditional branch is detected.
Claim 6
Dependent Claim
46 words
The method according to claim 2 wherein the providing step includes causing execution of the dead code segment by directly storing the address of the dead code segment corresponding to the address of the detected conditional branch in the program counter without executing a jump instruction.
Claim 7
Dependent Claim
20 words
The method according to claim 2 wherein the program counter is used as an index into the storage data structure.
Claim 8
Dependent Claim
133 words
A computer system for optimization of a program, comprising: replacing means for deleting a conditional branch instruction from a live code segment to a dead code segment and replacing the deleted conditional branch instruction with a conditional branch instruction from the live code segment to the live code segment; storage means for storing the address of the conditional branch instruction deleted by the replacing means and the address of the dead code segment corresponding to the deleted conditional branch instruction; upon execution of the program, monitoring means for detecting execution of the inserted conditional branch instruction in the live code segment, and upon detection, searching the storage means for the address of the dead code segment corresponding to the address of the inserted conditional branch, and causing execution of the dead code segment.
Claim 9
Dependent Claim
133 words
A computer system for optimization of a program, comprising: replacing means for deleting a conditional branch instruction from a live code segment to a dead code segment and replacing the deleted conditional branch instruction with a conditional branch instruction from the live code segment to the live code segment; storage means for storing the address of the conditional branch instruction deleted by the replacing means and the address of the dead code segment corresponding to the deleted conditional branch instruction; upon execution of the program, monitoring means for detecting execution of the inserted conditional branch instruction in the live code segment, and upon detection, searching the storage means for the address of the dead code segment corresponding to the address of the inserted conditional branch, and causing execution of the dead code segment.
Claim 10
Dependent Claim
79 words
The method of claim 2 wherein the replacing step replaces the located conditional branch with a conditional branch to self, and wherein the monitoring means provided in the providing step detects the execution of the conditional branch to self by monitoring a program counter for the address of the conditional branch to self, and wherein the monitoring means causes the execution of the dead code segment by storing the address of the dead code segment in the program counter.
Claim 11
Dependent Claim
132 words
A computer system for identifying a plurality of basic blocks within a computer program, comprising: a jump table identifier for identifying a plurality of jump tables within the computer program, each jump table having one or more entries, each entry representing a starting address of a basic block, the entries being ordered from a lowest to a highest entry; and a jump table traversing subsystem for repeating the following sequence of steps until either all entries in the plurality of jump tables have been selected or it is determined that all of the basic blocks of the computer program have been identified: selecting the lowest entry that has not already been selected from among the plurality of jump tables; and identifying basic blocks which begin at the address of the selected entry.
Claim 12
Dependent Claim
132 words
A computer system for identifying a plurality of basic blocks within a computer program, comprising: a jump table identifier for identifying a plurality of jump tables within the computer program, each jump table having one or more entries, each entry representing a starting address of a basic block, the entries being ordered from a lowest to a highest entry; and a jump table traversing subsystem for repeating the following sequence of steps until either all entries in the plurality of jump tables have been selected or it is determined that all of the basic blocks of the computer program have been identified: selecting the lowest entry that has not already been selected from among the plurality of jump tables; and identifying basic blocks which begin at the address of the selected entry.
Claim 13
Dependent Claim
130 words
A computer-readable medium whose contents cause a computer system to identify a plurality of basic blocks within a computer program by performing the steps of: identifying a plurality of jump tables within the computer program, each jump table having one or more entries, each entry representing a starting address of a basic block, the entries being ordered from a lowest to a highest entry; repeating the following sequence of steps until either all entries in the plurality of jump tables have been selected or it is determined that all of the basic blocks of the computer program have been identified: selecting the lowest entry that has not already been selected from among the plurality of jump tables; and identifying basic blocks which begin at the address of the selected entry.
Claim 14
Dependent Claim
130 words
A computer-readable medium whose contents cause a computer system to identify a plurality of basic blocks within a computer program by performing the steps of: identifying a plurality of jump tables within the computer program, each jump table having one or more entries, each entry representing a starting address of a basic block, the entries being ordered from a lowest to a highest entry; repeating the following sequence of steps until either all entries in the plurality of jump tables have been selected or it is determined that all of the basic blocks of the computer program have been identified: selecting the lowest entry that has not already been selected from among the plurality of jump tables; and identifying basic blocks which begin at the address of the selected entry.
Claim 15
Dependent Claim
143 words
A computer-readable medium whose contents cause a computer system to reduce the size of code that includes live code segments and dead code segments by performing the steps of: locating a conditional branch from a live code segment to a dead code segment; replacing the located conditional branch with a conditional branch to the live code segment; storing the address of the conditional branch to the live code segment and the address of the dead code segment in a storage data structure outside of the live code segment; and providing a monitoring means for detecting execution of the conditional branch to the live code segment during execution of the live code, and, upon detection, searching the storage data structure for the address of the dead code segment corresponding to the address of the conditional branch, and causing execution of the dead code segment.
Claim 16
Dependent Claim
143 words
A computer-readable medium whose contents cause a computer system to reduce the size of code that includes live code segments and dead code segments by performing the steps of: locating a conditional branch from a live code segment to a dead code segment; replacing the located conditional branch with a conditional branch to the live code segment; storing the address of the conditional branch to the live code segment and the address of the dead code segment in a storage data structure outside of the live code segment; and providing a monitoring means for detecting execution of the conditional branch to the live code segment during execution of the live code, and, upon detection, searching the storage data structure for the address of the dead code segment corresponding to the address of the conditional branch, and causing execution of the dead code segment.
Claim 17
Dependent Claim
80 words
The computer-readable medium of claim 10 wherein the replacing step replaces the located conditional branch with a conditional branch to self, and wherein the monitoring means provided in the providing step detects the execution of the conditional branch to self by monitoring a program counter for the address of the conditional branch to self, and wherein the monitoring means causes the execution of the dead code segment by storing the address of the dead code segment in the program counter.
Claim 18
Independent Claim
97 words
A method in a computer system for reducing the size of a set of executable instructions, the method comprising the steps of: identifying an executably contiguous subset of the set of instructions for performing a behavior that is infrequently executed; replacing the identified subset of instructions with an instruction that is shorter than the identified subset of instructions; while the set of instructions is executing, periodically determining which instruction of the set of instructions is currently executing; and when it is determined that the shorter instruction is executing, performing the behavior of the identified subset of instructions.
Claim 19
Independent Claim
97 words
A method in a computer system for reducing the size of a set of executable instructions, the method comprising the steps of: identifying an executably contiguous subset of the set of instructions for performing a behavior that is infrequently executed; replacing the identified subset of instructions with an instruction that is shorter than the identified subset of instructions; while the set of instructions is executing, periodically determining which instruction of the set of instructions is currently executing; and when it is determined that the shorter instruction is executing, performing the behavior of the identified subset of instructions.
Claim 20
Dependent Claim
99 words
A computer-readable medium whose contents cause a computer system to reduce the size of a set of executable instructions by performing the steps of: identifying an executably contiguous subset of the set of instructions for performing a behavior that is infrequently executed; replacing the identified subset of instructions with an instruction that is shorter than the identified subset of instructions; while the set of instructions is executing, periodically determining which instruction of the set of instructions is currently executing; and when it is determined that the shorter instruction is executing, performing the behavior of the identified subset of instructions.
Claim 21
Dependent Claim
99 words
A computer-readable medium whose contents cause a computer system to reduce the size of a set of executable instructions by performing the steps of: identifying an executably contiguous subset of the set of instructions for performing a behavior that is infrequently executed; replacing the identified subset of instructions with an instruction that is shorter than the identified subset of instructions; while the set of instructions is executing, periodically determining which instruction of the set of instructions is currently executing; and when it is determined that the shorter instruction is executing, performing the behavior of the identified subset of instructions.
References Cited (Backward Citations)
US4047243A
Cited
US4731740A
Cited
US4656583A
Cited
US4763255A
Cited
US4642765A
Cited
US4868738A
Cited
US5212794A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-09-01 | 2001-03-03 | 2001-09-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-09-01 | 2005-03-03 | 2005-09-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-09-01 | 2009-03-03 | 2009-09-02 | $7700.00 | Window Closed / Lapsed |