Array access boundary check by executing BNDCHK instruction...

Details Array access boundary check by executing BNDCHK instruction... Array access boundary check by executing BNDCHK instruction...

2002-04-08

2003-04-01

Kim, Kenneth S. (Department: 2183)

Electrical computers and digital processing systems: processing

Processing control

Specialized instruction processing in support of testing,...

C711S152000, C711S171000, C712S208000, C712S225000

Reexamination Certificate

active

06542990

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to microprocessors, and more particularly, to a boundary check acceleration instruction.
BACKGROUND
Reduced Instruction Set Computing (RISC) microprocessors are well known. RISC microprocessors are characterized by a smaller number of instructions, which are relatively simple to decode, and by requiring that all arithmetic/logic operations be performed register-to-register. RISC instructions are generally of only one length (e.g., 32-bit instructions). RISC instruction execution is of the direct hardwired type, as opposed to microcoding. There is a fixed instruction cycle time, and the instructions are defined to be relatively simple so that each instruction generally executes in one relatively short cycle.
A RISC microprocessor typically includes an instruction for accessing a data object such as an array. However, a typical array access may not be preceded by a check for a valid array access. If an array access is preceded by a check for a valid array access, it is accomplished in a typical RISC microprocessor by executing multiple conditional branches and test instructions.
A RISC microprocessor also typically provides one or more compare instructions that compare the value of two operands. However, these instructions alter the program-visible state by storing the result of the compare operation in a result register. Accordingly, when using a compare operation to determine whether boundary conditions exist, the instruction's cycle time must include the time it takes to store the result in the result register.
Speed of execution is also highly dependent on the sequentiality of the instruction stream executed by the microprocessor. Branches in the instruction stream disrupt the sequentiality of the instruction stream executed by the microprocessor and generate stalls while the prefetched instruction stream is flushed and a new instruction stream begun.
Speed of execution is also highly dependent on the number and type of program-visible changes that occur during the execution of an instruction, because such changes require additional cycle time. An instruction that can perform bound checking without changing the state of the processor would allow for speedier execution.
SUMMARY
The present invention provides a cost-effective and high-performance implementation of a boundary check instruction executed on a microprocessor. By providing the boundary check instruction, many branches can be eliminated altogether, thereby speeding up memory accesses that would otherwise require conditional branches to perform the validity checks as discussed below. Also, by eliminating unnecessary branch operations, the boundary check instruction avoids wasting entries in a limited-size hardware branch prediction table.
Moreover, in the context of bounds checking for array accesses, operation of the boundary check instruction accelerates array accesses in which the validity of each array access is checked prior to performing the array access. This robust approach to checking the validity of each array access provides for improved security features, which is desired in various environments, such as a Java™ computing environment. For example, this method can be used for various instruction sets such as Sun Microsystems, Inc.'s Majc™ instruction set.
In one embodiment, a method for boundary check acceleration includes executing a boundary check instruction. In at least one embodiment, the boundary check instruction is decoded before it is executed. Various extensions of the boundary check instruction perform various combinations of three separate comparisons. For each extension, the boundary check instruction contains the operands, or indicates the location of the operands, discussed below.
All of the extensions perform a less-than-zero comparison, evaluating whether the value of an operand, the “less-than-zero” operand, is less than zero. If so, the boundary check instruction generates a trap. For each extension, the boundary check instruction indicates the location of the less-than-zero operand. In addition to the less-than-zero comparison, each of the three extensions of the boundary check instruction performs at least one other comparison. These other comparisons are the zero-compare comparison, where the value of a “zero-compare” operand is compared with zero, and the range comparison, where it is determined whether the value of the “less-than-zero” operand is greater than or equal to the value of an upper-range operand.
When the boundary check instruction is used to perform accelerated bound checking for array accesses, the zero-compare operand is the base address of an array object, the less-than-zero operand is an index offset for an entry in the array, and the upper-range operand is a value indicating the number of entries (i.e., maximum size) in the array.
In at least one embodiment, the method of performing a boundary check instruction involves performing, in addition to the less-than-zero comparison, the range comparison. In this embodiment, the range operand either constitutes an immediate value in the boundary check instruction, or resides in the register indicated by a specifier in the boundary check instruction. The range operand is an immediate value if an immediate bit in the opcode is set. If the immediate bit in the opcode is reset, the range value resides in a register. In this embodiment, a trap is generated if the less-than zero comparison evaluates to true. A trap is also generated if the range comparison evaluates to true.
In another embodiment, executing the boundary check instruction includes performing the zero-compare comparison in addition to the less-than-zero comparison. In this embodiment, a trap is generated if the less-than zero comparison evaluates to true. A trap is also generated if the zero-compare comparison evaluates to true.
In another embodiment, executing the boundary check instruction includes performing all three of the comparisons: the zero-compare comparison, the less-than-zero comparison, and the range comparison. For each comparison, a trap is generated if the comparison evaluates to true. When this embodiment is used to perform accelerated bounds checking for array accesses, a trap will be generated if the contents of the zero-compare operand equals zero (i.e., the object pointer for the array to be accessed is a null pointer), if the value of the less-than-zero operand is less than zero (i.e., the index to be accessed is less than zero), or if the value of the less-than-zero operand is greater than or equal to the value of the range operand (i.e., the index to be accessed is greater than or equal to N, where N is the size of the array). The boundary check operation therefore results in a trap prior to the execution of an invalid array access.
Other aspects and advantages of the present invention will become apparent from the following detailed description and accompanying drawings.


REFERENCES:
patent: 4760374 (1988-07-01), Moller
patent: 5568624 (1996-10-01), Sites et al.
patent: 5878245 (1999-03-01), Johnson et al.
patent: 6014723 (2000-01-01), Tremblay et al.
patent: 6185673 (2001-02-01), Dewan
patent: 6298365 (2001-10-01), Dubey et al.
patent: 2002/0029332 (2002-03-01), Saulsbury
Marc Tremblay and William Joy;A Multiple-Thread Processor For Threaded Software Applications:U.S. Ser. No.: 09/204,480; Filed Dec. 3, 1998; 33 pages of Specification (including claims and Abstract); and 10 Sheets of Formal Drawings. (Copy Enclosed).
Linley Gwenap; “MAJC Gives VLIW A New Twist;”Microprocessor Report: The Insider's Guide To Microprocessor Hardware; vol. 13, No. 12; Sep. 13, 1999; 5 pages. (Copy Enclosed).

Affiliated with

Also associated with

Rating

Array access boundary check by executing BNDCHK instruction... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Array access boundary check by executing BNDCHK instruction..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Array access boundary check by executing BNDCHK instruction... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3086055