Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2000-02-09
2003-02-25
Dam, Tuan Q. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S131000, C717S152000, C717S153000, C712S226000, C712S227000
Reexamination Certificate
active
06526572
ABSTRACT:
BACKGROUND OF THE INVENTION
One technique commonly used in program optimization is register renaming, which reduces false dependencies among the instructions, and gives an optimizer greater freedom to reorder instructions. This technique is especially useful in binary translators, emulators, and just-in-time compilers, which preferably preserve the register state at the exit of each basic block. Since register renaming generally requires the translator to insert additional instructions into the code, which copies the renamed register back to its original location, it is preferable to only rename registers when it will improve the performance of the code. Therefore, it is a problem in the art that it is not known when the benefits of renaming registers outweigh the cost.
Another technique sometimes used by optimizers is load speculation. Load speculation involves reordering program instructions which load information from memory. There are two forms of load speculation. If a load instruction is reordered so as to precede a branch, it is possible for the load instruction to execute even though the instruction would not even have been executed in the original program. This form of speculation is called “control speculation,” since it is speculating that the branch will not cause the execution path to change.
A second form of speculation is “data speculation.” In this situation, a load instruction is reordered so as to precede a store instruction, which may access the same memory location. For the speculation to be effective, it is preferable to determine whether the store instruction actually accesses the same memory location as the load instruction.
Some processors provide hardware support for control and data speculation. Using this approach, the optimizer splits the load instruction into two instructions. The first instruction, called a speculative load, performs the load without generating a trap. The second instruction checks to see whether the speculative load was successful, and takes some sort of corrective action if it was not. Load speculation allows the optimizer greater freedom to reorder instructions. However, since the optimizer generally inserts instructions at the original places to check for success of the speculation, there is a computational cost to this operation. Load speculation should therefore only be performed when the benefits of doing so outweigh the costs. It is a problem in the art that it is not known when it would be beneficial to speculate load instructions.
Therefore, there is a need in the art for a mechanism for determining when speculating load instructions would be computationally beneficial.
There is a further need in the art for a mechanism which will rename registers only when program efficiency will be enhanced by doing so.
There is a still further need in the art for a mechanism which will speculate load instructions only when program efficiency will be enhanced by doing so.
SUMMARY OF THE INVENTION
These and other objects, features and technical advantages are achieved by a mechanism which selects candidates for register renaming and instruction speculating, and then proceeds to rename the selected registers and to speculate selected instructions so as to optimize program performance.
In a preferred embodiment, at any given time, the mechanism's analysis is restricted to a set of instructions called the instruction window. The mechanism preferably has two distinct phases of operation each involving two optimizing operations: register renaming and instruction speculation.
In phase one, the Dependency Analysis Phase, the mechanism preferably decides which registers are candidates for renaming, and which instructions are candidates for speculation (re-ordering). The selection of candidates is preferably accomplished by analyzing the dependency of each instruction with respect to other instructions. The mechanism then preferably constructs a dependency graph from the dependency information gathered on the individual instructions.
In a preferred embodiment, when an optimizing operation may be beneficial for a particular instruction, the mechanism provisionally performs the operation, but preserves information about the state of the program prior to said operation. Preferably, the information so preserved may be used to reverse the operation if the mechanism later determines that the operation was not actually beneficial to program performance. An operation may be beneficial if the target of the instruction is located later in the instruction window than the instruction itself, and the optimizing operation permits the mechanism to move the instruction to an earlier point in the instruction stream.
In phase two, the Instruction Scheduling Phase, the mechanism preferably first determines whether the individual optimizing operations provisionally performed in Phase one were actually beneficial to program performance. Generally, an optimizing operation is actually beneficial if the mechanism cannot reschedule the original instruction in unoptimized form later in the instruction stream without lengthening the critical path of program execution in the instruction window.
Generally, if the operation is found to be actually beneficial, the optimized instruction concerned will preferably remain in optimized form and be executed. If the operation is found not to be actually beneficial, the mechanism preferably reverses the optimizing operation using the information about the state of the program prior to the operation which was preserved by the mechanism in phase one.
Generally, scheduling means placing instructions into templates to enable execution of the instructions with an minimum number of cycles without violating any data dependencies. Generally, speculation may violate data dependencies, but whether any data dependencies are actually violated is generally not known until run-time. Generally, hardware functionality will support a check operation to recover from any dependency violations.
Therefore, it is a technical advantage of a preferred embodiment of the invention that register renaming operations are performed only when doing so actually improves program performance.
It is a further technical advantage of a preferred embodiment of the present invention that instructions are speculated only when doing so actually improves program performance.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims.
REFERENCES:
patent: 5787287 (1998-07-01), Bharadwaj
patent: 5933635 (1999-08-01), Holzle et al.
patent: 6070009 (2000-05-01), Dean et al.
patent: 6128775 (2000-10-01), Chow et al.
patent: 6158049 (2000-12-01), Goodwin et al.
patent: 6223340 (2001-04-01), Detlefs
Debugging optimized code with Dynamic Deoptimization,© 1992, p. 32-43 ACM.*
Patterson, David A. and John L. Hennessy, “Computer Architecture A Quantitative Approach”, Second Edition, 1996, Morgan Kaufmann Publishers, Inc. Enclosed are copies of the cover, table of contents, index and the entire Chapter 4, which appears to be the most relevant chapter. However, Applicant will produce any portion of the book requested by Examiner).
Brauch Rupert
Dunn David A.
Dam Tuan Q.
Kendall Chuck
LandOfFree
Mechanism for software register renaming and load... 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 software register renaming and load..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mechanism for software register renaming and load... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3130547