Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1996-04-18
2002-05-28
Courtenay, III, St. John (Department: 2151)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06397380
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to computer-program compilers comprising a program augmentation capability.
BACKGROUND OF THE INVENTION
Computer-program compilers comprise programs or hardware that can translate programs written in a source language into those written in a target language. For example, the source language may comprise a high level language such as Fortran, and the target language may also comprise a high level language e.g., a transformed Fortran, or alternatively, an assembly code or machine language.
SUMMARY OF THE INVENTION
Our work comprises combining and integrating two disparate concepts, as they relate to computer program compilers.
The first concept centers around compiler techniques comprising code optimization, which seek a transformation of the program with an aim of improving (optimizing) an efficiency or performance of a target program. For example, a goal of an optimizing compiler may be to generate a smaller or a faster set of object code that exactly duplicates a function of the program as it was written.
The second concept comprises directly providing a compiler with a program augmentation capability; e.g., an automatic symbolic differentiation capability (comprising a forward, reverse, or hybrid mode) which can augment the compiled program to include values for derivatives of the program's function. This second concept also comprises other augmentations to the compiled program e.g., consistency verification under dimensional analysis.
We combine these two concepts in the following way.
First, we recognize that an efficient employment of symbolic derivatives may be enhanced by identifying expressions that have equal values and eliminating redundant calculations along any path in the target program. Hence, no mathematical expression along any path in a target program is evaluated more than once. This is an optimization of the target program and it may be achieved for any operation, or sequence of operations, that are valid in the language of the source program. These include, but are not limited to, feedback loops, conditional branching and GO TO jumps in the control flow, subroutine calls, MAX, MIN or ABS (Absolute) evaluations, and table look-up data. We refer to this optimization as redundant expression elimination. Furthermore, we recognize that not all intermediate derivatives are needed. Therefore, the program augmentation capability preferably does not generate them in the first place. We refer to this optimization as an employment of global dependency information.
Secondly, we observe that extant compilers do not directly comprise a symbolic differentiation capability. Instead, this function can be done by an automatic symbolic differentiation preprocessing program.
Thirdly, we observe that extant automatic differentiation programs comprise a structure/sequence wherein automatic symbolic differentiation is done locally on a statement-by-statement basis. That is to say, the structure/sequencing of an extant automatic differentiation program is such that it can not avail itself of global dependency information or redundant expression elimination as it references automatic symbolic differentiation. Accordingly, from a vantage point of our invention, it is not possible to obtain an optimal or highly efficient code using extant automatic differentiation program structures.
We have now discovered a novel compiler structure/sequencing apparatus that is predicated on our employment of global dependency information and redundant expression elimination (in contrast to prior art local schema), which enables one to comprehend automatic symbolic differentiation as being inherently enhanced by its incorporation in proximity to, or within, a compiler's code optimization, thereby generating highly efficient code.
In a first aspect, the present invention comprises a method for optimizing and transforming a program to be compiled in a computer system. The method comprises the steps of:
1) constructing a compiler comprising a program augmentation capability; and
2) locating this capability in association with phases of a standard compilation process.
In a second aspect, the present invention comprises a compiler apparatus for compiling a program to be executed on a general purpose target computer system. The compiler apparatus comprises:
1) a front end (FE) for initially processing an input program;
2) a symbol-information data structure (SIDS) in communication with the front end for recording information about symbols in an input program;
3) an intermediate language generator (ILG) in communication with the front end and the symbol-information data structure for producing intermediate language instruction;
4) an optimizer (OPT) in communication with the symbol-information data structure and the intermediate language generator;
5) a means for locating a program augmentation capability in operative association with the optimizer; and
6) a back end (BE) in communication with the optimizer and/or the intermediate language generator for translating a program into target code.
The present invention as defined can realize several significant advantages.
First of all, as alluded to above, the qualities and attributes of the highly efficient code presently generated, arise in part from the fact that in our employment of e.g., symbolic differentiation done in operative association with the compiler optimizer, we can immediately avoid redundant calculations in the target program. This situation, concomitantly, can advantageously reduce the time needed to perform a required calculation which, in turn, can save money and speed up developmental processes. Other advantages are enumerated below.
REFERENCES:
patent: 4656583 (1987-04-01), Auslander et al.
patent: 4722071 (1988-01-01), Gates et al.
patent: 4802091 (1989-01-01), Cocke et al.
patent: 5127104 (1992-06-01), Dennis
patent: 5136686 (1992-08-01), Koza
patent: 5280613 (1994-01-01), Chan et al.
patent: 5355496 (1994-10-01), Fant et al.
patent: 5396631 (1995-03-01), Hayashi
patent: 5428805 (1995-06-01), Morgan
Bittner Calvin John
Grossman Bertrand M.
Jenks Richard Dimick
Watt Stephen Michael
Williams Richard Quimby
Courtenay III St. John
International Business Machines - Corporation
Kaufman Stephen C.
Scully Scott Murphy & Presser
LandOfFree
Computer-program compilers comprising a program augmentation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer-program compilers comprising a program augmentation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer-program compilers comprising a program augmentation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2877014