Re: Concerning subscript bounds checks

[ok@goanna.cs.rmit.EDU.AU (Richard A. O'Keefe)]

dewar@cs.nyu.edu (Robert Dewar) writes:

>Richard said
>"The remaining 4 occur in this context:
...
>A reasonably smart compiler should be able to tell that these four
>subscripts are also safe.
>"

>I suspect this judgment is based on informal reasoning ("well it is pretty
>obvious to me that it can be figured out").

Wrong.  I worked out in some detail a straightforward method for a compiler
to handle this.  I chose not to write it up here because it's (a) obvious
and (b) old hat.

>As always compiler optimizations,
>particularly range analysis are always more complicated than they appear
>from simple examples.

Look, I was *PRAISING* Ada, not criticising anything.
I have *NO IDEA* what optimisations GNAT or any other Ada compiler does
or does not do. 

I know for a fact that the analysis required for this particular example
and for a wide range of examples like it (basically looping over a bunch
of vectors and _conditionally_ routing elements from one set of vectors
to another: APL Compress and Merge operations and a few other patterns
I've seen in Fortran code) is straightforward to specify and would take
linear time to compute (I am taking the attitude here that if a variable
outlives a goto you just throw up your hands and be pessimistic).

*Of course* doing such an analysis takes time.
*Of course* the compiler's time spent doing that could have been spent
doing other things.
*Of course* the compiler writers' time spent implementing that could
have been spent implementing other things.
*Of course* it might be beyond any reasonable dispute in some particular
case that *not* doing this optimisation might be the right choice.

>P.S. GNAT has not even started to think about optimizing checks yet,
>you get junk checks even in simple loops. It's something we plan
>to start work on soon!

The central point I was making was a very simple, very obvious, very
positive one:

    I translated an algorithm from Fortran to Ada,
    and it _easily_ and _naturally_ fell out that
    62 out of 66 subscripts could _obviously_ be
    compiled without checks using purely local
    information (no data flow or range analysis needed).

I call that a _good_ result.  (The 4 subscripts that aren't quite so
obvious are executed with low frequency, and only the upper bound is
not obviously safe.)

-- 
Fifty years of programming language research, and we end up with C++ ???
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.