Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-12-28
2003-12-16
Nguyen-Ba, Hoang-Vu Antony (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S122000, C717S152000, C717S160000
Reexamination Certificate
active
06665864
ABSTRACT:
BACKGROUND OF INVENTION
1. Technical Field
This invention relates to a compiler, particularly to a method for reducing the number of array range checks in a compiler to increase execution speed of a program. An array range check is a check on whether an array access in a program is exceeding a range of the array.
2. Prior Art
There is a method for eliminating array range checks by using data-flow analysis (see “Optimizing array bound checks using flow analysis”, R. Gupta, ACM Letters on Programming Languages and Systems, 2(1-4), pp. 135 to 150, March-December, 1993, etc.). This method eliminates an array range check by the following two-phased process. Namely, (1) Insert a check near the beginning in program execution order so as to decrease array range checks. (2) Eliminate redundant array range checks. The advantage of this method is that it can apply to other places than a loop. However, it has its disadvantages, namely, the range in which it can eliminate array range checks is narrow and it can only apply to a language whose specification defines that it is a error to exceed a range.
As to other background arts, there is a method of loop conversion by loop splitting. This is a method of dividing a loop into three portions: a checked portion, an unchecked portion of the lower bound value and a checked portion of the upper bound value. For instance, a program of Table 1 is converted to of Table 2.
TABLE 1
for (i = start; i <= end; i++)
a[i] = 0;
TABLE 2
for (i = start; i <= min(max(start, 0)−1, end); i++)
a[i] = 0;
for (i = max(start, 0); (i <=min(end, N−1); i++)
a[i] = 0; /* no check required */
for (i = max(start, min(end, N−1)+1); i<=end; i++)
a[i] = 0;
If divided into three portions in this way, the second for loop can omit a range check. As a disadvantage of this method, if an array access in a loop is simple, the code size merely becomes three times larger, while, as to a case where there are a plurality of array base variables, there are more portions to be divided into and the code size becomes accordingly larger.
The Java language (Java is a trademark of Sun Microsystems, Inc.) is, as its specification, capable of detecting an access exceeding an array range, and when there is no user-defined exception handler, moving control to an invoked method after getting out of a method in which an exception occurred, or when there is a user-defined exception handler, moving the process to the exception handler. Accordingly, an array range check is essential since occurrence of an exception may be described as a correct operation in a program. However, an array range check slows execution speed compared with a language which does not require such a check. In an actual program, there is an array access to ensure that there is no access exceeding a range, and thus elimination of such redundant array range checks greatly contributes to improved performance. In addition, it is more desirable if the range of optimization can be expanded from the viewpoint of ensuring execution order between occurrence of an exception and a process with a side effect such as an assignment of a value to an array.
An object of the present invention is to reduce the number of array range checks and increase execution speed.
Another object of the present invention is to perform a two-phased check, namely to perform a wide range check by combining a plurality of array range checks, and perform a strict range check in the case that the wide range check fails, so as to provide a method for reducing the number of array range checks at execution time and allowing execution at increased speed.
A further object of the present invention is to provide a method for versioning by using information about array accesses which are always performed even if passing through any execution path in a loop. Versioning is a process which, at compilation time, (1) classifies execution states of a code of a certain portion of a program into several states, and (2) generates at execution time a check code to classify such states and an execution code of the certain portion of the program for each state.
SUMMARY OF THE INVENTION
The present invention to reduce the number of array range checks is, in a wider, to combine a plurality of array range checks and generate a code for a combined array range checks, and to generate a code for an array range check included in the plurality of array range checks in the case that the combined array range check is unsuccessful. These codes are stored in a storage and executed later by a processor. To make such a concept more specific, it becomes the following three forms.
In the first form, in the case of generating a code for an array range check for an array access in a program, it is executed, comprises: a first step of generating and storing in a storage (for instance, main memory) a first code for storing in one or a plurality of storage areas (for instance, flags of a processor) a result of combined array range check which combines a plurality of array range checks corresponding to a plurality of array accesses (for instance, VERSION_OR[B] in the Embodiments); and a second step of generating and storing in a storage a third code (for instance, a zero-cycle branch instruction in Power PC (a trademark of International Business Machines Corp.)) for checking the storage area and for invalidating a second code (an array range check which must be executed so as not to be incorrectly executed, unless invalidated by the third code) for an array range check included in the plurality of array range checks if the storage area indicates the combined array range check is successful. For instance, when using a processor whose flag can be used as a register, the second code can be invalidated at high speed and the number of array range checks can be reduced without increasing a code size so much. Using a flag as a register means that the flag can be kept without having its content arbitrarily destroyed by an arithmetical instruction, etc.
The aforementioned first step may comprise the steps of: combining array range checks for a plurality of array accesses according to a predetermined condition and storing in a storage information about a combined array range check; and allocating the combined array range check to a storage area.
In the case of versioning in the first form of the present invention, there is the further executed step of:
generating and storing in a storage a code which refers to the storage area storing the result of the combined array range check which is a condition of the versioning, if the storage area indicates that the combined array range check is successful, branches into versions not including a code for array range check included in the combined array range check, and if the storage area indicates that the combined array range check is unsuccessful, branches into versions including the second and third codes. This allows faster execution than ever even in the case that the combined array range check which is a condition of the versioning is unsuccessful.
In the second form of the present invention, in the case of generating a code for an array range check for an array access in a program, there are the performed steps of: generating and storing in a storage a second portion (for instance, part B of the Embodiments) for performing an array range check for necessary range corresponding to the array access included, the second portion corresponding to a first portion to be processed (for instance, part A of the Embodiments) of the program; performing for the first portion, an optimization process for array range checks and an elimination process for redundant array range checks regardless of the existence of a side effect instruction so that a side effect is caused by moving an array range check issuing an exception before the side effec
Kawahito Motohiro
Komatsu Hideaki
Yasue Toshiaki
Ludwin Richard M.
Nguyen-Ba Hoang-Vu Antony
Scully Scott Murphy & Presser
LandOfFree
Method and apparatus for generating code for array range... 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 generating code for array range..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating code for array range... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3148886