Array Bounds Check Elimination Utilizing a Page Protection Mechanism

In the past, there have been many research projects to eliminate array bounds checking. These approaches eliminated an array bounds check only if the array access corresponding to the check is known to be always valid. This paper presents a technique for eliminating an array bounds check even if it cannot be determined whether or not the corresponding array access for the target bounds check is always valid. We utilize a page protection mechanism to support this elimination. This technique can eliminate more array bounds checks than previous approaches. Our approach first allocates both a normal memory area and a protected area at the time of array allocation. It next analyzes whether a memory operation always accesses the protected area when the memory operation performs an invalid access. If this condition is satisfied, we eliminate the array bound check for the memory operation. This paper also covers how to limit the target arrays in order to reduce memory consumption and the cost of setting up this page protection. We select arrays by using two characteristics, the number of elements and life expectancy. Using these selection criteria, small and short-lived array objects are normally allocated.