Re: array index checking optimizations?

adams@yaroslav.ai.mit.edu (Stephen Adams) writes:
> 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.


The Harris Ada compiler does this sort of optimization. In fact, it
optimizes all range checks required by the language.


> 1. How does the analysis determine that the array indexes
> are in range?


The analysis actually determines that a test of 'i' against the range
of allowed array indices would always be true. It does this by
performing interval arithmetic on operations involving 'i' and using
flow analysis to propagate the results of assignments to 'i' to its
uses.


> 2. How fragile is the analysis, for example, does it still
> work if the condition in the while loop is changed to
> `while i <> last do'


Your example, not being legal Ada, is difficult to analyze to answer
your question. The main difficulty is that you haven't declared any
bounds on the arrays, so it's hard to know what information the
compiler has available.


If the bounds are compile-time constants (unlikely for array
arguments, at least in Ada), then I believe our compiler would
correctly eliminate the index tests, assuming that the initial value
of 'i' is within bounds.


--
Bill Leonard
Harris Computer Systems Corporation
2101 W. Cypress Creek Road
Fort Lauderdale, FL 33309
Bill.Leonard@mail.hcsc.com
--

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