Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-06-08
2001-11-13
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000
Reexamination Certificate
active
06317876
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to a method and apparatus for optimizing compilers by determining the maximum number of live registers used during the execution of a computer program.
BACKGROUND OF THE INVENTION
Almost all microprocessors have a load-store architecture in which values are loaded from memory into registers, operations are performed on values loaded in the registers, and the resulting values are again stored into memory. Register allocation, which is typically a function of compilation systems, determines the values that may access the registers of a computer system during any point in the execution of a program. Accordingly, register allocation is an important technique of compiler optimization because the number of computer registers is limited and because register operations are performed faster than memory loads and stores. Register allocation is discussed with reference to
Advanced Compiler Design and Implementation,
Steven S. Muchnick, 1997.
Some methods for optimizing register allocation limit the allocation of values to computer registers, to periods when an instruction associated with the value is live. It will be appreciated that a code instruction may be associated with a value, and the value is referred to as “live” during the time period in which the value may be executed. Also, the register accessed by the value is termed a “live register” during the period that the value is live. The range of code instructions in which the value is live is referred to as a live range of the value. While a value is live it is desirable to allocate a register to the value to enable instruction processing to continue without storing the value in memory, and the allocated register may be referred to as a live register. Values may reside in virtual registers and virtual registers may represent hardware registers. As used herein the phrase computer registers, represents those registers that are visible to the software developer.
Prior register allocation solutions included recording a history of read instructions and write instructions and searching the recorded events to find the maximum number of live registers, sometimes referred to as the maximum pressure point, at a particular point in the execution of the program. Therefore, the comprehensive read instruction and write instruction history related to the execution of a program must be stored, and that results in a large amount of time required for compiler optimization. It will be appreciated by those skilled in the art, that compiler optimization uses the value of the maximum number of live registers to efficiently manager register allocation.
Since the number of samples to be searched is large, the associated large amount of computing resources and searching time has inhibited improvements in compiler optimization. As known to those skilled in the art, compiler optimization solutions that increase the computer overhead necessary for compilation, reduce the usefulness of the optimization solution and reduce the productivity of software development engineers. This reduction in productivity and increase in computer system requirements has limited further improvement of software development techniques.
SUMMARY OF THE INVENTION
The present invention is a method and apparatus for determining the maximum number of live computer registers, or pressure point. Software developers typically follow a work cycle of development, debugging, and testing of code. The productivity of a software developer can be improved by reducing the time spent in any part of the development cycle. Development and debugging productivity primarily depends on compilation time. Therefore it is important to continue to create compiler optimization tools that improve the compilation process.
Accordingly it is an object of the invention to record the relevant events related to the execution of a computer program, as opposed to a comprehensive history of the read instructions and write instructions. That is, during the operation of the present embodiment events that do not affect the maximum number of live registers are not recorded.
It is also an object of the invention to maintain information about the maximum number of live registers for any partition related to the execution of a computer program. It will be understood that a partition may identify sub-sets of information related to the operation of the present invention.
It is also an object of the invention to reduce the overhead required to search the information related to execution of a computer program to determine the maximum number of live registers. Further, the present invention may bound the required system resources required to determine the maximum number of live registers to the number of registers associated with the number of partitions.
Accordingly, it is an object of the invention to improve software developer productivity by reducing the overhead required to search the information about execution to determine the maximum number of live registers.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.
REFERENCES:
patent: 5249295 (1993-09-01), Briggs et al.
patent: 5367651 (1994-11-01), Smith et al.
patent: 5367684 (1994-11-01), Smith
patent: 5946491 (1999-08-01), Aizikowitz et al.
patent: 6090156 (2000-07-01), MacLeod
patent: 6128775 (2000-10-01), Chow et al.
patent: 5249295 (1993-09-01), None
patent: 404241630 (1992-08-01), None
“Advanced Compiler Design & Implementation”, Steven S. Munchnick et al. Aug. 19, 1997, pp. 482-530.*
“Register Allocation”, IBM Technical Bulletin, Mar. 1986, vol. 28, Issue 10 pp. 4506-4513.
Dahl Peter J.
Kunz Robert C.
Hewlett--Packard Company
Ingberg Todd
Powell Mark R.
LandOfFree
Method and apparatus for determining a maximum number of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for determining a maximum number of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining a maximum number of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2583805