Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-09-30
2001-11-27
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C709S241000
Reexamination Certificate
active
06324689
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to the field of computer software and more particularly to software optimization and analysis tools.
BACKGROUND OF THE INVENTION
As is known in the art, computers operate using a combination of hardware and software. The software controls how the computer hardware functions to produce a desired result. The software that is provided on a computer system includes an operating system and may include one or more software applications. The operating system controls the basic operations of the computer hardware and presents a framework for allowing other software applications to interface with the hardware. Known operating systems include the VMS operating system, MS DOS, Windows 95, Windows NT, or UNIX, among others.
Another software application that is often included in the software of the computer system is a compiler. The compiler is a software routine that translates software applications, written in a high level code such as C++, into an executable file capable of being run on the computer hardware. The executable file includes a set of instructions and data for implementing the software application on the computer hardware. The set of instructions comprises instructions from an instruction set of the computer. For example, a reduced instruction set computer (RISC) has an instruction set that includes simple operations, such as load and store operations. In general, the order of instructions in the executable file mirrors the order of instructions in the software application listing; with each instruction of the software application being translated into one or more corresponding instructions from the instruction set of the computer.
Once an executable file of the software application has been generated, the software application may be executed on the computer system. Generally, the executable file is stored in a memory of the computer system, such as main memory, disk drive or other such device. As the software application is executed, portions are moved from an external memory into a local memory referred to as a cache memory. The cache memory is a relatively fast memory that is used for temporary storage of instructions and data that are to be executed on a processor of the computer hardware. By providing fast access to the instructions and data, the cache memory helps to improve the performance of the software application by reducing the delay incurred when retrieving instructions and data from memory.
Each time that an instruction or data is required for operation of the software application, if the instruction or data is not stored in the cache it must be fetched from the memory. Because of the delays associated with retrieving data from memory, it is desirable to ensure that those instructions that are to be executed frequently are stored in the cache.
Optimization tools have been provided to improve the performance of software applications by re-arranging the order of instructions in the executable files to maximize cache usage. Re-arranging the order of the instructions in the executable files may be done to group together frequently executed instructions such that the group may be forwarded to the cache in one operation. Optimization tools may also re-arrange the order of instructions for a variety of other purposes.
One problem encountered by optimization tools is that the executable files provided by different compilers of different operating systems frequently have different formats. Some operating system compilers, such as the Windows NT compiler, interleave instructions and data to ensure that data that is needed by instructions is also moved to the cache when the associated instructions are moved to the cache. By placing data near the instructions, fewer cache accesses need to be made, fewer delays are incurred and the overall performance of applications is increased.
However, because the instructions and data are basically both multi-bit data words, when instructions and data are interleaved it is difficult for the optimization tool to identify which multi-bit data words are instructions capable of being re-arranged. Thus, it is often difficult to optimize executables generated by operating systems that interleave instructions and data.
SUMMARY OF THE lNVENTION
A method for permitting, software optimization tools, instrumenting tools and other software analysis devices to re-write executables having, mixed instructions and data uses a data structure having an entry for each multi-bit word in an executable file. Each entry of the data structure includes a number of flags that are set to identify the type of the multi-bit word in the associated line of the executable file. The types include instruction, data and unclassified. Each entry also includes a flag that indicates that the multi-bit word should not be optimized and a flag indicating that the multi-bit word is a branch.
The executable code is iteratively traversed to identify those multi-bit words that are instructions and those multi-bit words that are data. After the traversal there may remain unclassified multi-bit words; i.e., multi-bit words which have not been classified yet as either data or instruction type. A traversal is then made of the unclassified multi-bit words. When an ambiguous multi-bit word is encountered, it is determined whether or not the unclassified multi-bit word is a potential branch instruction. If the multi-bit word is a potential branch, then the number of instructions displacing the potential branch instruction from the target is maintained as a constant. In one embodiment, a region of multi-bit words from the potential branch instruction to the potential branch destination is frozen; i.e., those multi-bit words within the region will have their associated no optimization flag set in the data structure so that the multi-bit word will not be optimized. Freezing the region of instruction preserves flow control and data integrity as will be described in more detail later herein. In an alternative embodiment, instructions within the region may change in order, provided the total displacement from the branch to the target remains constant.
In addition, during the traversal of multi-bit words, when an ambiguous multi-bit word is encountered prior to a series of identified instructions, the ambiguous multi-bit word is marked as a branch instruction having a flow through path to the list of instructions. The ambiguous multi-bit word is marked by asserting the appropriate flag in the associated entry of the data structure. Thus, if the ambiguous multi-bit word is later moved by the optimization tool, a branch will be inserted by the optimization tool back to the series of identified instructions, thereby preserving the flow of operations of the software application.
Therefore, according to one aspect of the invention, a method for re-writing an executable comprising the steps of analyzing a plurality of words in the executable to classify each of the plurality of words as one of either instruction, data or unclassified, storing data representing a classification of each of the plurality of words in the executable in a data structure, and during optimization, selecting words of the executable for re-ordering responsive to the data in the data structure.
According to another aspect of the invention, a computer readable medium having a data structure stored thereon is provided. The data structure comprises a plurality of entries corresponding to a plurality of words in an executable file, with each entry of the data structure further including a flag for indicating whether a word in a corresponding location of the executable tile is an instruction and a flag for indicating whether a word in a corresponding location of the executable file is a data word.
REFERENCES:
patent: 5157759 (1992-10-01), Bachenko
patent: 5230050 (1993-07-01), Iistuko et al.
patent: 5274811 (1993-12-01), Borg et al.
patent: 5375242 (1994-12-01), Kumar et al.
patent: 5504901 (1996-04-01), Peterson
patent: 5598560 (1997-01-01), Bensen
patent: 568062
Cohn Robert
Goodwin David William
Lowney Paul Geoffrey
Compaq Computer Corporation
Hamilton Brook Smith & Reynolds P.C.
Khatrli Anil
Powell Mark R.
LandOfFree
Mechanism for re-writing an executable having mixed code and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Mechanism for re-writing an executable having mixed code and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mechanism for re-writing an executable having mixed code and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2600375