I had this idea today that one could implement a bounds checked loop over an array by constructing an iteration counter that will overflow on the last increment and stop the execution based on the generated overflow interrupt.
So assume you have an array e.g. int[32] and you want to iterate that. What you could do now to avoid the bounds check in every loop run is to register an interrupt handler for the overflow interrupt and assign a register to the value MAX - 32. This register is incremented on every loop iteration run and the last iteration run will overflow i.e. triggering the interrupt handler. Suppose the interrupt handler could increment the program counter of the original function, this mechanism could be used to avoid bounds checks.
So code like
for (int i = 0; i < array.length; i++) {
// do something
}
could be implemented like
// setup interrupt somehow
SOME_REGISTER = MAX - array.length;
while (true) {
// do something
SOME_REGISTER++;
}
I don't know if this is doable, but I heard Java is doing something like that to avoid null checks in the runtime generated code. Do you think this would be doable or has this ever been considered/tried out by any language runtime?
Taking an exception is very slow; an array would have to be huge to amortize the extra cost of leaving the loop by faulting, even if you could save an instruction inside the loop.
What you've probably read about is Array bounds checks on 64-bit hardware using hardware memory-protection : making arrays end at the end of a virtual page, and leaving the next page unmapped. The VM catches SIGSEGV and delivers an exception to the guest code if an out of bounds exception ever happens. This removes the need for bounds checks for random accesses, not in a loop.
This technique only causes an invalid page fault (segfault) when the guest code actually takes an array bounds exception, not for the normal case of exiting a loop over an array.
I think you're talking about MIPS where there's an addi instruction that traps on signed overflow. (Instead of the normal addiu that does addition without a conditional trap).
Most other ISAs don't have any efficient way to fault on signed overflow. x86 has into (interrupt of OF is set) but that's a separate instruction from the add that might set flags. You might as well use a conditional branch instead of causing an exception and catching it. Or just use dec ecx / jnz as a loop counter, or count a negative index up towards zero and index from the end of the array.
I think MIPS would require an extra addi inside the loop for a dedicated counter: MIPS's only addressing mode is reg+16_bit_constant.
So if you want to iterate an array you need a pointer increment, or else you'd need an extra add tmp, base, index inside the loop.
A loop needs a jump or branch instruction at the bottom, and it can be a conditional branch for basically no extra cost. So in MIPS, you'd calculate the end of the array outside the loop, then write a normal loop like
addu $t5, $t0, $t4 ; t5 = int *endp = start + byte_length
.loop: ; do{
addiu $t0, $t0, 4 ; p++
lw $t1, ($t0) ; *p
...
bne $t0, $t5, .loop ; }while(p != endp)
There are no wasted instructions inside the loop. Any array bounds-checking can be done outside the loop, by checking that endp is no more than one past the end of the array.
(On modern x86, cmp/jne works equivalently, decoding to a single compare-and-branch uop. Many other ISAs have a decrement-and-branch or similar instruction that allow counter loop conditions to only have one instruction of overhead.)
i < array.length as a loop condition isn't just an array bounds check.
As I said above, in a simple loop that iterates arr[i], you hoist the bounds-check out of the loop to keep it efficient that way.