Re: array index checking optimizations?

tmb@best.com (.)
1 May 1996 23:01:08 -0400

          From comp.compilers

Related articles
array index checking optimizations? adams@yaroslav.ai.mit.edu (1996-04-29)
Re: array index checking optimizations? bill@amber.ssd.hcsc.com (1996-04-30)
Re: array index checking optimizations? kik@zia.cray.com (1996-04-30)
Re: array index checking optimizations? tmb@best.com (1996-05-01)
Re: array index checking optimizations? Laurent.Guerby@enst-bretagne.fr (Laurent Guerby) (1996-05-01)
Re: array index checking optimizations? markt@harlequin.co.uk (1996-05-01)
array index checking optimizations? dave@occl-cam.demon.co.uk (Dave Lloyd) (1996-05-02)
Re: array index checking optimizations? mad@math.keio.ac.jp (1996-05-03)
Re: array index checking optimizations? prener@watson.ibm.com (1996-05-03)
Re: array index checking optimizations? ben@sys.toronto.edu (1996-05-03)
[3 later articles]
| List of all articles for this month |

From: tmb@best.com (.)
Newsgroups: comp.compilers
Date: 1 May 1996 23:01:08 -0400
Organization: home
References: 96-04-140 96-04-166
Keywords: optimize



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


--


Post a followup to this message

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