Browse Prior Art Database

A method for eliminating sign extensions for array bounds checking of Java on 64-bit architectures that have no 32-bit compare instruction

IP.com Disclosure Number: IPCOM000016330D
Original Publication Date: 2002-Oct-21
Included in the Prior Art Database: 2003-Jun-21
Document File: 3 page(s) / 51K

Publishing Venue

IBM

Abstract

Disclosed is a method for eliminating sign extensions for array bounds checking of Java on 64-bit architectures that have no 32-bit compare instruction. Previous elimination algorithms, such as JP920010090, simply used 32-bit compare instruction to implement array bounds checking. However, there is no approach for 64-bit architectures that have no 32-bit compare instruction. An array bounds check has two operands; that is, array index and array length. This disclosure has an assumption that a register containing array length has been already sign- or zero-extended. This assumption might not affect optimization effect, because: Many architectures have a load instruction that performs sign- or zero-extension at load. A load instruction for obtaining array length is usually loop invariant. In this case, even if an architecture does not have a sign- or zero-extension load, a sign extension is necessary only one time at out of the loop. The following four theorems enable effectively eliminating sign extensions for array bounds checking. Note that the theorems assume 64-bit wrap-around on overflow.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

  A method for eliminating sign extensions for array bounds checking of Java on 64-bit architectures that have no 32-bit compare instruction

  Disclosed is a method for eliminating sign extensions for array bounds checking of Java on 64-bit architectures that have no 32-bit compare instruction. Previous elimination algorithms, such as JP920010090, simply used 32-bit compare instruction to implement array bounds checking. However, there is no approach for 64-bit architectures that have no 32-bit compare instruction.

An array bounds check has two operands; that is, array index and array length. This disclosure has an assumption that a register containing array length has been already sign- or zero-extended. This assumption might not affect optimization effect, because:

Many architectures have a load instruction that performs sign- or zero-extension at load. A load instruction for obtaining array length is usually loop invariant. In this case, even if an architecture does not have a sign- or zero-extension load, a sign extension is necessary only one time at out of the loop.

The following four theorems enable effectively eliminating sign extensions for array bounds checking. Note that the theorems assume 64-bit wrap-around on overflow.

Theorem 1 If upper 32 bits of a variable i are initialized to zero, i does not need a sign extension for the array bounds checking.

Proof. The range of i will be 0 <= i <= 0xffffffff. The range that needs a sign extension is 0x80000000 <= i <= 0xffffffff. In this range, an exception can be always detected even if 64-bit compare instruction is used for array bounds checking.

Theorem 2 If variables i, j satisfy the following two conditions, i+j does not need a sign extension for the array bounds checking.

Both i and j have already been sign-extended from 32 bits.

Either i or j satisfies the following inequality:

0 <= i or j <= 0x7fffffff

Proof. Since i and j are commutable for i+j, it is sufficient to prove only the case in which i satisfies the second condition.

Case 0 <= i <= 0x7fffffff:

Case 0 <= j <= 0x7fffffff: Because the upper 32 bits of i+j must be zero, Theorem 2 holds using Theorem 1. Case 0xffffffff80000000 <= j <= 0xffffffffffffffff: The range of i+j will be 0xffffffff80000000 <= i+j <= 0xffff...