Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-03-11
2001-03-13
Chaki, Kakali (Department: 2762)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C717S152000
Reexamination Certificate
active
06202204
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention relates to compilers and, more particularly, to compilers that performs redundant load elimination.
2. Background Art
A compiler is a program that reads a source program written in a source language and translates it into a target program in a target language. For example, a compiler may translate a high level source program (such as C++) into compiled code that can be understood by a processor, such as a microprocessor.
Many compilers include three stages: (1) a “front end” in which the source program is translated into intermediate representations; (2) a “middle end” in which machine independent optimizations are made; and (3) a “back end” in which machine dependent optimizations are made and code is generated. Optimizations can significantly improve running time and/or space requirements of the target program. However, “optimized” code is not necessarily optimal under any mathematical measure.
Techniques for improving the target code include local optimization, peephole optimization, and global optimization. Local optimization works on individual blocks of a function. Peephole optimization examines a short sequence of the target instructions (called the peephole) and, if possible, replaces it by a shorter and/or faster sequence. Global optimization operates over the entire function.
Redundant load elimination attempts to remove load operations that are redundant. A load is redundant if it loads a value from a memory location from which an earlier load already obtained its value and the value is still valid (that is, no store writes into the same memory location in-between). Redundant load elimination can be implemented as local, peephole, or global optimization. However, traditional redundant load elimination involves only regular loads, not more complicated load types.
Accordingly, there is a need for a compiler to handle other types of loads as well in redundant load elimination.
SUMMARY OF THE INVENTION
In one implementation of the invention, a computer implemented method used in compiling a program includes identifying a covering load, which may be one of a set of covering loads, and a redundant load. The covering load and the redundant load have a first and second load type, respectively. The first and the second load type each may be one of a group of load types including a regular load and at least one speculative-type load. In one implementation, the group of load types includes at least one check-type load. One implementation of the invention is in a machine readable medium.
REFERENCES:
patent: 5293631 (1994-03-01), Rau et al.
patent: 5526499 (1996-06-01), Bernstein et al.
patent: 5537620 (1996-07-01), Breternitz, Jr.
patent: 5542075 (1996-07-01), Ebcioglu et al.
patent: 5555412 (1996-09-01), Besaw et al.
patent: 5704053 (1997-12-01), Santhanam
patent: 5751983 (1998-05-01), Abramson et al.
patent: 5787285 (1998-07-01), Lanning
patent: 5797013 (1998-08-01), Mahadevan et al.
patent: 6029005 (2000-02-01), Radigan
Austin et al, “Zero cycle loads: Microarchitecture support for reducing load latency”, IEEE pp. 82-92, 1995.
Jegou et al, “Speculative Prefetching”, ACM ICS, pp 57-66, 1993.
Bodik et al, “Path sensitive value flow analysis”, ACM POPL pp 237-251, 1998.
Molina et al, “Dynamic removal of redundant computations”, pp 474-481, 1999.
Shavit et al, “Eliminiation trees and the constructions of pools and stacks”, ACM SPAA, pp 54-63, 1998.
Diwan et al., “Type based alias analysis”, ACM SIGPLAN, pp 106-117, Apr., 1998.
Schlansker et al., “Height reducation of control recurrence for ILP processor”, MICRO 27 ACM, pp 40-51, Mar., 1994.
Shavit et al., “Elimination trees and the construction of pools and stacks”, SPAA ACM, pp 54-63, 1995.
Mahlke et al., “Sentinel scheduling a model for compiler controlled speculation execution”, ACM Trans. Comp. Sys. vol. 11, No. 4, pp 376-408, Nov., 1993.
Lo et al., “Register promotion by sparse partial redundancy elimination of loads and stores”, SIGPLAn ACM, pp 26-37, Apr., 1998.
Rogers et al., “Software support speculative loads”, ASPLOS V ACM, pp 38-50, 1992.
A. Aho et al., “Compilers: Principles, Techniques, and Tools,” (Addison Wesley 1986), pp. 554-555, 592-595, and 627-631.
V. Kathail et al., “HPL Playdoh Architecture Specification: Version 1.0,” HP Laboratories Technical Report, HPL-93-80, Feb. 1994, pp. 1-37 and 39-48.
Lee Yong-Fong
Wu Youfeng
Aldous Alan K.
Chaki Kakali
Intel Corporation
Khatri Anil
LandOfFree
Comprehensive redundant load elimination for architectures... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Comprehensive redundant load elimination for architectures..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Comprehensive redundant load elimination for architectures... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2510344