The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Sep. 02, 1997
Filed:
Jun. 30, 1994
Robert I Davidson, Bellevue, WA (US);
Nathan Myhrvold, Bellevue, WA (US);
Keith Randel Vogel, Duvall, WA (US);
Gideon Andreas Yuval, Mercer Island, WA (US);
Richard Shupak, Bellevue, WA (US);
Norman Eugene Apperson, Bellevue, WA (US);
Microsoft Corporation, Redmond, WA (US);
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.