Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2000-09-27
2004-11-16
Das, Chameli Chaudhuri (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S140000, C717S144000, C717S145000, C717S151000, C717S154000, C717S155000
Reexamination Certificate
active
06820253
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to computer software compilation systems, and more specifically to a compiler that performs interprocedural analysis and optimization.
BACKGROUND OF THE INVENTION
A. Compilers and Interprocedural Analysis (IPA)
A program comprises one or more external source code files. Each source code file contains one or more translation units. A translation unit is a subroutine, function, or other separately compilable software entity. A compiler translates a program to one or more object files. In particular, a compiler compiles the source files of a program one at a time. For each source file, the compiler works on one translation unit at a time and generates a corresponding object file. The developer does not have to compile an entire program at one time, but rather, can compile the program in separate pieces as it is developed. After an entire program is compiled, a linkage editor processes all of the object files of the program and generates an executable program. Therefore, in a conventional compilation system, a developer invokes two separate steps: a compilation step and a link step.
There are two major phases of a compiler: a front end and a back end. The front end of a compiler consists of those phases that depend on the source language and are largely independent of the target computer. The front end typically performs lexical and syntactic analysis, creates the symbol table, performs semantic analysis, and generates intermediate code which is an intermediate representation of the source code.
The back end of a compiler includes those phases of compilation that depend on the target computer and generally do not depend on the source language, but depend on the intermediate code. The back end typically performs code optimization on the intermediate representation and generates the target object files.
A disadvantage of a conventional compilation system is that during compilation the compiler only has local information about the translation unit on which the compiler is currently working. The compiler does not have any global information pertaining to the entire program or to the relationships between the translation units of the program. Because of this lack of global information, the back end of the compiler is unable to perform certain optimizations, such as optimizing the operations involving global variables and the passing of constant parameters.
A well known technique that solves this disadvantage of conventional compilation systems is interprocedural analysis (IPA). IPA is a phase that is added to a compilation system to analyze an entire program and collect global information related to the translation units. Global information includes global variables and how the multiple translation units manipulate and reference the global variables. Once the global information is collected, it is then passed to the optimizer as part of the back end of the compilation system. Thus, when the optimizer optimizes a translation unit, the optimizer accesses this global information and performs additional and more aggressive optimization pertaining to global variables. IPA improves the efficiency of the generated object code by providing optimization at a global level, thereby improving the run-time performance of the executable program.
Existing IPA analysis defers analysis and optimization of a program until link time, at which time all translation units are effectively merged into one big aggregate translation unit, which is then analyzed and optimized. This means that if the programmer edits a single translation unit, the entire program must be reanalyzed and reoptimized. Furthermore, existing IPA analysis, by creating a monolithic translation unit, prevents distributed compilation of translation units by multiple processors.
REFERENCES:
patent: 5175856 (1992-12-01), Van Dyke et al.
patent: 5623499 (1997-04-01), Ko et al.
patent: 5671419 (1997-09-01), Carini et al.
patent: 5740443 (1998-04-01), Carini
patent: 5778212 (1998-07-01), Dehnert et al.
patent: 6282701 (2001-08-01), Wygodny et al.
patent: 6289507 (2001-09-01), Tanaka et al.
patent: 6438594 (2002-08-01), Bowman-Amuah
patent: 6530079 (2003-03-01), Midkiff et al.
patent: 6671693 (2003-12-01), Marpe et al.
patent: 6681383 (2004-01-01), Pastor et al.
Title: A comprehensive Approach to Parallel Data Flow Analysis, author: Lee et al, ACM, 1992.*
Title: Formal Callability and its Relevance and Application to Interprocedural Data-flow Analysis, author: Jens Knoop, IEEE, 1998.*
Title: A Practical Interprocedural Data Flow Analysis Algorithm, author: Barth, ACM, 1978.*
Title: An Iterprocedural Data Flow Analysis Alogorithm, author: Barth, ACM, 1997.*
Lee, Yony-fong et al., “Performing Data Flow Analysis in Parallel,” Nov. 1990, ACM Press, Proc. of the 1990 ACM/IEEE conf. on Supercomputing, p. 942-951.
LandOfFree
Method and system for interprocedural analysis with separate... 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 system for interprocedural analysis with separate..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for interprocedural analysis with separate... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3326507