Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-06-18
2004-08-03
Dam, Tuan (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S150000, C717S156000
Reexamination Certificate
active
06772414
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
This invention generally relates to the optimization of computer programs, and more specifically relates to a computer mechanism and method for optimizing a computer program by hoisting loop-invariant computations out of loops in the computer program.
2. Background Art
The development of the EDVAC computer system in 1948 is generally considered the beginning of the computer era. Since that time, dramatic advances in both hardware and software (e.g., computer programs) have drastically improved the performance of computer systems. Modern software has become very complex when compared to early computer programs. Many modern computer programs execute tens or hundreds of thousands of instructions. The execution time (and hence, performance) of a computer program is very closely related to the number of instructions that are executed as the computer program runs. Thus, as the size and complexity of computer programs increase, the execution time of the computer program increases as well.
Unlike early computer programs, modern computer programs are typically written in a high-level language that is easy to understand by a human programmer. Special software tools known as compilers take the human-readable form of a computer program, known as “source code”, and convert it into “machine code” or “object code” instructions that may be executed by a computer system. Because a compiler generates the stream of machine code instructions that are eventually executed on a computer system, the manner in which the compiler converts the source code to object code affects the execution time of the computer program.
A computer program of any complexity will contain many loops for repetitively executing a set of instructions until some condition is satisfied. Modern compilers typically include a mechanism for moving computations in a loop outside of the loop if the result of the computation doesn't change within the loop. If the result of a computation doesn't change within the loop, the computation is said to be loop-invariant. The process of moving loop-invariant computations outside of the loop is commonly known in the art as “hoisting”. The concept of hoisting computations from loops is well-known, as discussed in Aho et al.,
Compilers: Principles, Techniques and Tools
, section 10.7, pp. 638-643 (March 1988). By hoisting loop-invariant computations from within the loop to outside of the loop, the performance of the computer program is enhanced.
Known mechanisms and methods for hoisting loop-invariant computations out of a loop only consider computations one at a time. These mechanisms and methods do not recognize that certain groups of computations, taken together, may be legal and profitable to hoist out of a loop, even though no single computation in the group can be legally hoisted independently. Without an improved mechanism and method for hoisting loop-invariant computations from loops, the computer industry will continue to suffer from computer programs that are not fully optimized.
DISCLOSURE OF INVENTION
According to the present invention, a mechanism and method for hoisting invariant computations from loops analyzes the lifetimes of fixed processor resources defined by an instruction, and determines whether a group of computations present in multiple instructions within the lifetime are, taken together, loop-invariant and legal to hoist from the loop. If the group of computations within the lifetime of the fixed processor resource are loop-invariant and hoistable, all of the computations are hoisted out of the loop as a group. By determining the lifetimes of fixed processor resources defined in an instruction, the hoisting mechanism succeeds in hoisting out groups of computations that cannot be individually hoisted out of a loop, thereby achieving better performance when the computer program executes.
The foregoing and other features and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention, as illustrated in the accompanying drawings.
REFERENCES:
Aho et al., “Compiler, Principles, Techniques, and Tools”, Addison-Wesley Publishing, pp. 1-5, 585-645, Mar. 1988.*
Gupta, “Code Optimization as a Side Effect of Instruction Scheduling”, IEEE, pp. 370-377, Dec. 1997.*
Knoop et al., “The Power of Assignment Motion”, ACM, pp. 233-245, Jun. 1995.*
Knoop et al., “Partial Dead Code Elimination”, ACM, pp. 147-158, Jun. 1994.
Roediger Robert Ralph
Schmidt William Jon
Dam Tuan
Martin Derek P.
Martin & Associates LLC
Vo Ted T.
LandOfFree
Lifetime-sensitive mechanism and method for hoisting... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Lifetime-sensitive mechanism and method for hoisting..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lifetime-sensitive mechanism and method for hoisting... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3307866