Re: eliminating array bounds checking overhead

Terry Greyzck <terryg@uswest.net>
27 Apr 2000 10:53:13 -0400

          From comp.compilers

Related articles
[2 earlier articles]
Re: eliminating array bounds checking overhead vugluskr@unicorn.math.spbu.ru (2000-04-27)
Re: eliminating array bounds checking overhead jprice@scdt.intel.com (2000-04-27)
Re: eliminating array bounds checking overhead blaak@infomatch.com (Ray Blaak) (2000-04-27)
Re: eliminating array bounds checking overhead Sid-Ahmed-Ali.TOUATI@inria.fr (Sid Ahmed Ali TOUATI) (2000-04-27)
Re: eliminating array bounds checking overhead rhyde@shoe-size.com (Randall Hyde) (2000-04-27)
Re: eliminating array bounds checking overhead nr@labrador.eecs.harvard.edu (2000-04-27)
Re: eliminating array bounds checking overhead terryg@uswest.net (Terry Greyzck) (2000-04-27)
Re: eliminating array bounds checking overhead fjscipio@rochester.rr.com (Fred J. Scipione) (2000-04-27)
Re: eliminating array bounds checking overhead sandeep@ddi.com (Sandeep Dutta) (2000-04-29)
Re: eliminating array bounds checking overhead tej@melbpc.org.au (Tim Josling) (2000-04-30)
Re: eliminating array bounds checking overhead markw65@my-deja.com (Mark Williams) (2000-04-30)
Re: eliminating array bounds checking overhead d95josef@dtek.chalmers.se (2000-04-30)
Re: eliminating array bounds checking overhead mayur_naik@my-deja.com (2000-04-30)
[8 later articles]
| List of all articles for this month |

From: Terry Greyzck <terryg@uswest.net>
Newsgroups: comp.compilers
Date: 27 Apr 2000 10:53:13 -0400
Organization: Posted via Supernews, http://www.supernews.com
References: 00-04-194
Keywords: optimize

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


Post a followup to this message

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