Re: eliminating array bounds checking overhead

Mark Williams <markw65@my-deja.com>
4 May 2000 17:12:18 -0400

          From comp.compilers

Related articles
[12 earlier articles]
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)
Re: eliminating array bounds checking overhead terryg@uswest.net (Terry Greyzck) (2000-05-01)
Re: eliminating array bounds checking overhead monnier+comp/compilers/news/@flint.cs.yale.edu (Stefan Monnier) (2000-05-01)
Re: eliminating array bounds checking overhead r_c_chapman@my-deja.com (2000-05-01)
Re: eliminating array bounds checking overhead markw65@my-deja.com (Mark Williams) (2000-05-04)
Re: eliminating array bounds checking overhead world!bobduff@uunet.uu.net (Robert A Duff) (2000-05-04)
Re: eliminating array bounds checking overhead paule@martex.gen.oh.us (Paul Evans) (2000-05-04)
Re: eliminating array bounds checking overhead d95josef@dtek.chalmers.se (Josef Sveningsson) (2000-05-12)
Re: eliminating array bounds checking overhead mtimmerm@opentext.nospam-remove.com (Matt Timmermans) (2000-05-12)
| List of all articles for this month |

From: Mark Williams <markw65@my-deja.com>
Newsgroups: comp.compilers
Date: 4 May 2000 17:12:18 -0400
Organization: Deja.com - Before you buy.
References: 00-04-194 00-04-211 00-04-222 00-05-010
Keywords: optimize

"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


Post a followup to this message

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