Method and apparatus for eliminating redundant array range checks in a compiler

• US 6,519,765 B1
• Filed: 07/09/1999
• Issued: 02/11/2003
• Est. Priority Date: 07/10/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Komatsu, Hideaki, Kawahito, Motohiro, Yasue, Toshiaki
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): DAS, CHAMELI
• Application Number:
  US09/350,242
• Time in Patent Office: 1,313 Days
• Field of Search: 717/154, 717/155, 717/146, 717/159, 717/133, 717/151, 717/156, 717/160, 717/161, 717/152, 717/127, 717/131, 717/132, 717/1, 717/108, 717/157, 717/158, 714/35
• US Class Current: 717/127
• CPC Class Codes: G06F 8/43 Checking; Contextual analysis
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

Java language 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. However, an array range check slows execution speed compared with a language which does not require it. 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 range checks greatly contributes to improved performance, and in addition, brings about an effect of expanding the range of optimization from the viewpoint of ensuring order of execution between occurrence of an exception and a process with a side effect such as an assignment of a value to an array.

Claims

1. A method for eliminating a redundant array range check of array range checks in a program, said method comprising the steps of:

in each basic block, collecting a first information about array range checks already processed, in program execution order according to a first condition, said first information being a set of array range checks;

propagating said first information along a data-flow of the program according to a second condition, and generating a second information about array range checks already processed at the beginning of each basic block; and

in each basic block, eliminating an array range check by following each instruction in program execution order with modification of said second information according to a third condition and by using the second information.

2. The method according to claim 1, wherein said first condition further comprises conditions of, in a basic block:

if an index variable of an array access is not modified, collecting array range check information for said array access as it is;

if an index variable in an array range check is modified by adding a positive or negative constant, collecting array range check information after reflecting the modification caused by subtracting said constant from said index variable.

3. The method according to claim 1, wherein said first condition further comprises a condition of:

collecting a range defined by upper and lower bounds which can be handled as already checked as to a constant index from a minimum constant offset and a maximum constant offset of an array index in an array range check and a lower bound of the array.

4. The method according to claim 1, wherein said first condition further comprises a condition of:

collecting a range defined by upper and lower bounds which can be handled as already checked as to a constant index from a lower limit value or a upper limit value of an index variable in an array range check and a lower bound of the array.

5. The method according to claim 1, wherein said second condition comprises conditions of:

if a certain basic block is at the beginning of said program, propagating as information about array range checks to be processed at the end of said certain basic block said first information about array range checks already processed itself of said certain basic block; and

if said certain basic block is not at the beginning of said program, propagating as information about array range checks to be processed at the end of said certain basic block, a sum set of a third information about array range checks already processed and said first information of said certain basic block, said third information being said second information of said certain basic block after being modified according to a fourth condition.

6. The method according to claim 1, wherein said third condition comprises a condition of:

if an index variable in an array range check is modified by adding a positive or negative constant, correcting to array range check information after reflecting the modification caused by subtracting said constant from said index variable.

7. The method according to claim 5, wherein said fourth condition comprises a condition of:

if, in said certain basic block, an index variable in an array range check included in said second information is modified by adding a positive or negative constant, reflecting the modification caused by subtracting said constant from said index variable on said array range check included in said second information.

8. An apparatus for eliminating a redundant array range check of array range checks in a program, said apparatus comprising:

means for, in each basic block, collecting a first information about array range checks already processed in program execution order according to a first condition, said first information being a set of array range checks;

means for propagating said first information along a data-flow in said program according to a second condition, and for generating a second information about array range checks already processed at the beginning of each basic block; and

means for, in each basic block, eliminating array range checks by following each instruction in program execution order with modification of said second information according to a third condition and by using said second information.