array index checking optimizations?

adams@yaroslav.ai.mit.edu (Stephen Adams)
29 Apr 1996 23:03:23 -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)
[6 later articles]
| List of all articles for this month |

From: adams@yaroslav.ai.mit.edu (Stephen Adams)
Newsgroups: comp.compilers
Date: 29 Apr 1996 23:03:23 -0400
Organization: MIT Project MAC
Keywords: optimize, question

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.


If such a compiler exists:


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


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'


If not, how close is the state of the art to being capable of this
analysis?


There seem to be relatively few papers on array bounds checking in the
literature (for example, only a handful in the past 10 years in PLDI).
Most of the material that I have read will work only for simple DO
loops, or fails to incorporate information from control flow.


[I apologise for the program being a mix of Pascal, Ada, etc. I think
that what it does is reasonably apparent.]
________________________________________________________________________


function compare (a : array of char, b : array of char) returns integer
begin
    var last : integer;
    var i : integer := 0;


    if a'length < b'length then
        last = a'length
    else
        last = b'length
    end if


    while i < last do
        if a[i]=b[i] then
            i := i + 1;
        else
            return ord(a[i]) - ord(b[i]);
    end while


    return a'length - b'length
end
[Didn't the PL.8 compiler optimize this kind of stuff? -John]


--


Post a followup to this message

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