Bounds-checking elimination
Encyclopedia
In computer science
, bounds-checking elimination is a compiler optimization
useful in programming languages or runtimes that enforce bounds checking
, the practice of consistently checking every index into an array to verify that the index is within the defined valid range of indexes. Its goal is to detect which of these indexing operations do not need to be validated at runtime, and eliminating those checks.
One common example is accessing an array element, modifying it, and storing the modified value in the same array at the same location. Normally, this example would result in a bounds check when the element is read from the array and a second bounds check when the modified element is stored using the same array index.
Bounds-checking elimination could eliminate the second check if the compiler or runtime can determine that the array size cannot change and the index cannot change between the two array operations.
Another example occurs when a programmer loops over the elements of the array, and the loop condition guarantees that the index is within the bounds of the array. It may be difficult to detect that the programmer's manual check renders the automatic check redundant. However, it may still be possible for the compiler or runtime to perform proper bounds-checking elimination in this case.
representation and for each array create a new type representing a safe index for that particular array. The first use of a value as an array index results in a runtime type cast (and appropriate check), but subsequently the safe index value can be used without a type cast, without sacrificing correctness or safety.
languages such as Java
often check indexes at runtime before accessing Arrays
. Some just-in-time compilers such as HotSpot
are able to eliminate some of these checks if they discover that the index is always within the correct range, or if an earlier check would have already thrown an exception.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, bounds-checking elimination is a compiler optimization
Compiler optimization
Compiler optimization is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied...
useful in programming languages or runtimes that enforce bounds checking
Bounds checking
In computer programming, bounds checking is any method of detecting whether a variable is within some bounds before its use. It is particularly relevant to a variable used as an index into an array to ensure its value lies within the bounds of the array...
, the practice of consistently checking every index into an array to verify that the index is within the defined valid range of indexes. Its goal is to detect which of these indexing operations do not need to be validated at runtime, and eliminating those checks.
One common example is accessing an array element, modifying it, and storing the modified value in the same array at the same location. Normally, this example would result in a bounds check when the element is read from the array and a second bounds check when the modified element is stored using the same array index.
Bounds-checking elimination could eliminate the second check if the compiler or runtime can determine that the array size cannot change and the index cannot change between the two array operations.
Another example occurs when a programmer loops over the elements of the array, and the loop condition guarantees that the index is within the bounds of the array. It may be difficult to detect that the programmer's manual check renders the automatic check redundant. However, it may still be possible for the compiler or runtime to perform proper bounds-checking elimination in this case.
In natively compiled languages
One technique for bounds-checking elimination is to use a typed static single assignment formStatic single assignment form
In compiler design, static single assignment form is a property of an intermediate representation , which says that each variable is assigned exactly once...
representation and for each array create a new type representing a safe index for that particular array. The first use of a value as an array index results in a runtime type cast (and appropriate check), but subsequently the safe index value can be used without a type cast, without sacrificing correctness or safety.
In JIT-compiled languages
Just-in-time compiledJust-in-time compilation
In computing, just-in-time compilation , also known as dynamic translation, is a method to improve the runtime performance of computer programs. Historically, computer programs had two modes of runtime operation, either interpreted or static compilation...
languages such as Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
often check indexes at runtime before accessing Arrays
Array data type
In computer science, an array type is a data type that is meant to describe a collection of elements , each selected by one or more indices that can be computed at run time by the program. Such a collection is usually called an array variable, array value, or simply array...
. Some just-in-time compilers such as HotSpot
HotSpot
HotSpot is a Java virtual machine for desktops and servers, maintained and distributed by Oracle Corporation. It features techniques such as just-in-time compilation and adaptive optimization designed to improve performance.-History:...
are able to eliminate some of these checks if they discover that the index is always within the correct range, or if an earlier check would have already thrown an exception.
External links
- W. Amme, J. von Ronne, M. Franz. Using the SafeTSA Representation to Boost the Performance of an Existing Java Virtual Machine (2002).