(1) Field of the Invention
The present invention relates to a compiling apparatus for converting a source program into its machine language or assembly language equivalent which can be executed at a high speed. More particularly, the invention relates to a compiling apparatus which has a function to analyze overlaps of memory addresses of two or more data expressions and a function to optimize code of the object program.
In the following, the compiling apparatus is called a compiler. Compilers translate source programs written in a high-order programming language such as C, FORTRAN, AND COBOL into object programs written in machine oriented language such as machine language, assembly language.
A term intermediate language is one used by the compiler to represent the program being compiled. It is usually at a lower level than the source language and a higher level than the target language. Generally, compilers optimize a source program through intermediate language programs, which are synonymous with intermediate representations, intermediate texts, or internal representations.
The "optimization" of compiling means to compile a source program in such a way as to improve the execution speed of the compiled program and reduce the memory area required by the compiled program, without changing the meaning of the source program. Some of representations of intermediate language program are eliminated, moved, and integrated through optimization, to thereby provide optimized object program. The selection of representations of intermediate language program which are optimized, therefore, affects the performance and speed of optimization.
Computers are now required to operate at high speed. To improve the operation speed, the number of machine cycles per second of the computers are increased. However, an increase in the number of machine cycles generally involves a very high cost. Therefore, computers that simultaneously execute a plurality of instructions, namely, parallel processing computers have been attracting attention as computers which offer a high operating speed. In order to realize a practical improvement in the total speed of the above computers, an improvement in compilers is important. Therefore, the improvement of the optimization function of the compilers is further required. However, the present invention can be applied not only to the compiler of parallel processing computers but also to the compiler of normal computers.
(2) Description of the Related Art
In programs, data is pointed to by variables and arrays. Names of variables and arrays in the source program are converted into addresses indicating memory positions at which corresponding variables and arrays are stored. In many recent programs, variables which directly point to addresses indicating memory positions are used. These variables are called "pointers". In this way, data expressed by variables, arrays, and pointers are mapped to a real memory address area.
It can occur that two or more data expressions of such variables, arrays, and pointers denote the same memory address. This means that different data pointed by two or more data expressions overlap one another. If the data expressions are in the above case, we say that the expressions are aliases of one another.
The overlaps of data expressions influence the optimization. For example, when two memory addresses of data expressions indicated by two assignment statements overlap each other, data accessed by the former assignment statement does not need to be accessed once more by the later assignment statement because these data are same. Therefore, the later assignment statement can be omitted. Further, if two memory addresses of data expressions overlap each other, when data pointed to by one expression changes, data pointed to by the other expression also changes. For example, when the first one of the overlapping pointers indicates a constant memory address, the value pointed to by the first pointer is sequentially rewritten according to the value pointed to by the second pointer, and the final value pointed to by the first pointer is necessary, the value pointed to by the first pointer needs to be stored after every rewriting operation because the value pointed to by the second pointer is necessary to be rewritten when the first and second pointers point same addresses. However, when memory addresses of two data expressions do not overlap each other, the value pointed to by the first pointer does not need to be stored after every rewriting operation because the rewritten value pointed to by the first pointer does not influence the values pointed to by the second pointer, and only the final value pointed to by the first pointer is necessary. Namely, in this case, when memory addresses of two data expressions do not overlap each other, the storing statements to store the value pointed by the first pointer can be omitted. As described above, it is important for the optimization to know whether or not memory addresses of two or more data expressions overlap.
Scheduling of the program is carried out as a part of the optimization in a broad sense. The scheduling of the program is also influenced by the overlaps of data expressions.
Recent compiling apparatuses usually provide a functional portion to statically analyze overlaps of memory addresses of two or more data expressions. This functional portion is called a static aliasing analysis unit.
Many studies to develop static aliasing analysis methods have been made for many kinds of compilers. For example, the following documents disclose such compilers.
(1) "Compiler Principles, Techniques, and Tools" (A. V.Aho, et al. Addison-Wesley 1988);
(2) "Dependence Analysis for Pointer Variables" (Susan Horwitz, et al. ACM 0-89791-306-X 1989);
(3) "A Safe Approximate Algorithm for Interprocedual Pointer Aliasing" (William Landi, et al. ACM SIGPLAN '92 PLDI-6/92/CA 1992); and
(4) Japanese Unexamined Patent Publication (Kokai) No.4-25942.
The static aliasing analysis methods of the conventional compilers disclosed in the above documents statically judge whether or not memory addresses of two or more data expressions overlap one another. This means that the analysis is superficially carried out without practically executing the programs. However, programs usually have portions in which overlaps of memory addresses of data expressions cannot be analyzed without practically executing the program. For example, when variables are passed as arguments, overlaps of memory addresses accessed by these variables cannot be analyzed without practical execution of the program. Further, when variables are indirectly expressed by a plurality of functions which call functions one after another, overlaps of memory addresses accessed by these variables are very complicated, therefore, the analysis of the overlaps of memory addresses is practically impossible because the analysis time required by the static aliasing analysis unit becomes very large. In this case, it is judged that the overlap of memory addresses of data expressions is obscure, and this portion of the program is excluded from the optimization process and the scheduling process. Therefore, there is a problem that the effect of optimization by this program is not enough.
If optimization and scheduling can be applied to data expressions which are judged to have obscure overlaps, more efficient object program can be obtained.
In some conventional compiling methods such as Fujitsu Fortran 77 EX/VP, an user can indicate existence of overlaps of memory addresses of data by inserting compile statements into the source program, and the compiler carries out the optimization process and the scheduling process according to these indications. However, these compiling methods have problems in that they are not automatic.
USPTO Backgrounds
USPTO Backgrounds