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.


I don't know about safety, but nothing short of some kind of theorem
proving will achieve that information. Mainly due to indices that
depend on values only to be known at run-time. The partial evaluation
folks have looked at such problems, since they have to somehow
'execute' their programs to produce residuals. One work I am familiar
with is that by Carlo Ghezzi et al. where they use a theorem prover to
resolve conjectures about ranges (its been a while since I read the
paper so be warned)


@ARTICLE{cppgm91,
AUTHOR = {Alberto Coen Porisini and Flavio De Paoli and Carlo
Ghezzi and Dino Mandriolli},
TITLE = {Software Specialization via Symbolic Execution},
JOURNAL = {IEEE Transactions on Software Engineering},
YEAR = {1991},
VOLUME = {17},
NUMBER = {9},
PAGES = {884-899},
MONTH = {September}
}


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


Symbolic analysis is definitely a way to go but it is expensive to put
it in its entire glory in a commercial compiler.


Mohammad Reza Hahinghat's (sp?) thesis from UIUC in the area of
symbolic analysis would be a good place to see some of the state of
the art abd references. I think his thesis was published by Kluwer,
but am not sure.


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


Actually, I recall Rajiv Gupta's paper in PLDI (one of the last ones?)
was definitely handling more than DO loops. But the effort there and
in the area of array bounds checking was/is to remove unecessary
bounds tests (or move them to better places) not safety.


Following are some bounds checking references you may find handy.


@ARTICLE{wh77,
                AUTHOR = {William H. Harrison},
                TITLE = {Compiler Analysis of the Value Ranges of Variables},
                JOURNAL = {IEEE Transactions on Software Engineering},
                YEAR = {1977},
                VOLUME = {SE-3},
                NUMBER = {3},
                PAGES = {243-250},
                MONTH = {May}
}


@BOOK{h77,
                AUTHOR = {M.S. Hecht},
                TITLE = {Flow Analysis of Computer Programs},
                PUBLISHER = {Elsevier-North Holland, New York},
                YEAR = {1977}
}


@INPROCEEDINGS{rg90,
                AUTHOR = {Rajiv Gupta},
                TITLE = {A Fresh Look at Optimizing Array Bound Checking},
                BOOKTITLE = {ACM SIGPLAN '90 Conference on Programming
Language Design and Implementation},
                YEAR = {1990},
                PAGES = {272-282},
                MONTH = {June}
}


@ARTICLE{jb74,
                AUTHOR = {James R. Bell},
                TITLE = {Rapid Calculations of Subscripted Array Addresses},
                JOURNAL = {Software--Practice and Experience},
                YEAR = {1974},
                VOLUME = {4},
                PAGES = {275-277}
}


Cheers
ksh
----
Ksheerabdhi Krishna
Cray Research, Inc. Phone: (505) 988-2468 (x28)
Santa Fe, NM 87505 e-mail: kik@cray.com
--

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