Data processing: software development – installation – and managem – Software program development tool – Testing or debugging
Reexamination Certificate
1999-07-09
2003-02-11
Chaki, Kakali (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Testing or debugging
C717S131000, C717S132000, C717S133000, C717S157000, C717S158000, C711S108000, C714S035000
Reexamination Certificate
active
06519765
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to a compiler, more particularly to a method for eliminating or optimizing an array range check in a compiler. An array range check is a check on whether an array access in a program is exceeding its array range.
2. Prior Art
Several methods exist for eliminating an array range check based on the background art.
One such method is for checking the possibility of a range exceeding before a loop. (See “Elimination of Redundant Array Subscript Range Checks”, Priyadarshan Kolte and Michael Wolfe, In proceedings of the ACM SIGPLAN '95 Conference on Programming Language Design and Implementation, pp. 270 to 278, June 1995, etc.)
Table 1 in which 0 is the lower bound of an array and N is its size is modified to Table 2 as follows.
TABLE 1
for (i = start; i <= end; i++) a[i] = 0;
TABLE 2
if ((start <= end) &&
(start < 0 | | end > N−1)) {
exception; /* exceed an array range in a loop */
}
for (i = start; i <= end; i++) a[i] = 0; /* no check
required */
In the pseudocode of Table 1, 0 is assigned to each element of the array a. In the pseudocode of Table 2, an exception occurs in the case that the condition of if statement is fulfilled since the array access may exceed the array range, and processes it as in Table 1 in the case that it is not fulfilled.
The advantage of this method is that every array range check in a loop can be eliminated in the case that upper and lower bounds of the array access in the loop are certainly known. However, it has the following disadvantages as well. Namely, this method can only apply to a language whose specification defines that it is an error to exceed a range. Moreover, it can only apply when an array index in a loop changes monotonously. In addition, it cannot apply in the case that an ending condition of a loop cannot be put out of the loop, for instance, when end is a global variable, etc. in the above instance and end is changed by itself in the loop or by another thread.
A second method is for dividing a loop into three (See “Optimizing Array Reference Checking in Java Programs”, Samuel P. Midkiff, Jose E. Moreira, Mark Snir, IBM Research Report RC21184(94652), Computer Science/Mathematics, May 18, 1998, etc.)
This method divides a loop into three parts, namely a part not to be checked, a part for checking its lower bound, and a part for checking its upper bound. For instance, if the lower bound of an array is 0 and its size is N, Table 1 is modified to Table 3 as follows.
TABLE 3
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 in this way, in the second for-loop part, range checks can be omitted. The basic idea in this method is similar to method (1). The advantage of this method is that every array range check in a loop can be eliminated in the case that upper and lower bounds of the array access in the loop are certainly known. However, it can only apply when an array index in a loop changes monotonously. In addition, it cannot apply in the case that an ending condition of a loop cannot be put out of the loop, for instance, when end is a global variable, etc. in the above instance and end is changed by itself in the loop or by another thread. Furthermore, it requires special handling when applied to a large loop since the code size becomes three times larger.
A third method is for making array bases and indexes of the same value already checked (See the same documentation as method (1))
If there is an array access a[i] which is already checked, this method makes a[i] already checked within a range controlled from there and having the same values of a and i. Table 4 shows an example.
TABLE 4
i = k;
a [i] = j; /* check required */
a [0] = 0; /* check required */
if (...) a [i] ++; /* no check required */
t = a [i]; /* no check required */
if (...) {
i++;
a [i−1]++; /* check required */
a [i]++; /* check required */
}
t = a [i]; /* check required */
The advantage of this method is that it can apply to other places than a loop. However, it has a disadvantage that the range to be determined as already checked is small.
A fourth method is directed to for eliminating an array check by using a range of values of a variable (See “Iterative Type Analysis and Extended Message Splitting”, CRAIG CHAMBERS, DAVID UNGAR, Optimizing Dynamically-Typed Object-Oriented Programs, etc.)
It is a method to narrow down a range of a variable from information such as if statement, and eliminate an array range check by using the information. For instance, if a lower bound of an array is 0, the part which has no check required written in its comment field is an array access to be determined as no check required by this method.
TABLE 5
if (3 <= i && i <= 5) {
/* it is understood the range of the value which i has
is 3 to 5 */
a [i] = j; /* check required */
a [i−1] = 0; /* no check required from 0 < i−1 < i */
a [(i−3)*2] = 0; /* no check required from 0 <=
(i−3)*2 < i */
}
The advantage of this method is that it can apply to other places than a loop. Even if an expression of an array index is complicated as in method (1), it may be handled as already checked. However, in reality there are many cases in which a range of a variable cannot be narrowed down.
A fifth method is directed to eliminating an array check 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 an error to exceed a range.
An object of the present invention is to eliminate redundant array range checks by collecting array range check information by using data-flow analysis, etc. and moving up the checks. The redundant array range checks referred to here are those for an array access which can ensure that the array range check does not exceed its range because there is a preceding array access.
In Java (a trademark of Sun Microsystems) language, an exception occurs as its specification as a result of a range check at an array access. As this occurrence of an exception may be used to write a program, a program will not run correctly without performing array range checks. Another object of the present invention is to allow more array range checks to be eliminated by coping with a language in which occurrence of an exception may be used to write a program.
A further object of the present invention is to optimize an array range check by collecting array range check information through data-flow analysis, etc.
A still further object of the present invention is to perform a versioning for a loop by collecting array range check information on a predetermined condition.
SUMMARY OF THE INVENTION
Kawahito Motohiro
Komatsu Hideaki
Yasue Toshiaki
Chaki Kakali
Das Chameli C.
International Business Machines - Corporation
Schecter, Esq. Manny W.
Scully Scott Murphy & Presser
LandOfFree
Method and apparatus for eliminating redundant 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 eliminating redundant array range..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for eliminating redundant array range... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3150817