Re: eliminating array bounds checking overhead

There have been numerous compiler implementations that attempt to
remove array bounds tests from loops, and with the reference to A[i]
in your example, I am making the assumption your primary concern is
with loops.


Many of the fancier compilers will fold the condition and eliminate
the test if possible; but this isn't as common as you would think, as
the compiler has to evaluate the iteration space of 'i' and perform
some range analysis. The Cray compilers will do this, as a useful
leftover from the Ada compiler, where run time checks were the rule,
not the exception (US patent 5,361,354). This same sort of
optimization also helps to eliminate loop top tests for inner loops in
traingular/trapezoidal loop nests. This works best when 'lo', 'hi',
and the loop trio count are constants, otherwise a run time check may
be necessary to determine if the condition will trigger in the current
iteration space, and if so, on what iteration. In the worst cases you
have to evaluate a set of linear equations at run time before entering
the loop; this generally is not done, as the run-time cost of
eliminating the checks can be greater than performing the checks
themselves, depending on various characteristics of the loop that
cannot be determined at compilation time.


There is also at least one paper on the topic from Priyadarshan Kolte
and Michael Wolfe, in 1995.


Hope this helps -


Terry Greyzck
terryg@uswest.net


References:


Elimination of Redundant Array Subscript Range Checks
http://www.cse.ogi.edu/Sparse/abstract/kolte.pldi.95.html


Patent US 5,361,354: Optimization of alternate loop exits
http://patent.womplex.ibm.com/details?pn=US05361354__


mayur_naik@my-deja.com wrote:
...
>I wish to perform an array lookup of the form:
>
>if (i > lo && i < hi)
> printf("%d", A[i]);
>else
> printf("index out of bounds");
>
>The above code is executed several times. The probability that 'i' is
>between 'lo' and 'hi' is VERY high and I want to eliminate the
>overhead of the 2 less-than tests. Does any language or any machine
>provide some mechanism to:
>
>1. index an array without checking its bounds
>2. throw an exception if the index was actually out of range
>3. allow the programmer to catch and handle the exception rather than
> terminate the program


(Actually, this sounds a lot like Ada...)


terryg@uswest.net

Return to the comp.compilers page.
Search the comp.compilers archives again.