Re: eliminating array bounds checking overhead

"Stefan Monnier" <monnier+comp/compilers/news/@flint.cs.yale.edu> wrote:
> >>>>> "Mark" == Mark Williams <markw65@my-deja.com> writes:
> > If hi & lo are constants, then it is a very reasonable transformation
> > to expect the compiler to perform (on architectures where it is
> > beneficial). If not, then it is unlikely to be able to. Its not a
> > performance issue, its a correctness one: the two forms are only
> > equivalent when hi > lo.
>
> Very very very few languages allow arrays where the high bound is
> lower then the low bound. So the only "interesting case is when
> lo==hi, but that is also rare enough to be either disallowed or
> handled specially.


I was responding to the following quote:


  > 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.


And the question of whether or not it was reasonable to expect an
optimizing compiler to transform the tests into ((unsigned)(i - lo) <
(hi - lo)). In the case of a language with a built in range checked
array type, I wouldnt _need_ an optimizing compiler; there is no
transformation to be done (it would presumably generate the test in the
most efficient form for the target architecture). Of course, you would
still need a good optimizing compiler to eliminate the tests - but the
post I was responding to was talking about generating efficient code to
_do_ the tests.


Without knowing the origin of the hi & lo in the above post, there is no
way to know whether a compiler could determine that hi > lo.


-------------
Mark Williams

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