Re: array index checking optimizations?

> From: adams@yaroslav.ai.mit.edu (Stephen Adams)
>
> I am curious if there are any compilers out there that can detect that
> all the array references in the following program are safe, and thus
> no array indexes need to be checked.


kik@zia.cray.com (Krishna Ksheerabdhi) writes:
      I don't know about safety, but nothing short of some kind of theorem
      proving will achieve that information.


Actually, there are numerous common, simple patterns for array
expressions that you can recognize and optimize that don't require
general purpose theorem proving. For example (in Java notation):


for(int i=0;i<a.length;i++) a[i] = 0;


Of course, there are some properties for the loop body that you need
to verify (you might quibble and call this "theorem proving", but the
code to do it doesn't resemble a traditional theorem prover at all).


What those patterns come down to, in general, is recognizing that you
are iterating through the common index set of a set of arrays. Rather
than recognizing such patterns, it might be better to actually create
an explicit construct:


for(int i in_index_set_of a,b,c) { a[i] = b[i] + c[i] + d[i/2]; }


This could eliminate the bounds check on accesses to a, b, and c when
subscripted by i.


I have my doubts if more heroic optimizations really help you in
practice, but people have tried.


Thomas.


--

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