Re: Idea: Array Boundary Checks on Write Access Only

[Lieven Marchand <mal@bewoner.dma.be>]

Markus Kuhn <Markus.Kuhn@cl.cam.ac.uk> writes:

> Lieven Marchand wrote:
> > About the only commonly used case that most compilers don't handle is
> > where you put in the check yourself.
> 
> It would be really neat if Ada compilers would keep track not only of
> the declared range of a subtype, but also of the effectively possible
> range of Integer variables inside a certain program fragment as part
> of the flow analysis.
> 
> For instance in code such as
> 
>   if J > 0 then
>      -- compiler notes that here J : range 1 .. J'Last
>      if I > J then
>         -- compiler notes that here I : range 1 .. I'Last
> 
> then the compiler should know that inside the second "if" I > 0 always
> holds. This need not be a full blown automatic proof system, just some
> logic that understands simple inequalities and monotonic expressions
> and that keeps track of the effective maximum and minimum value
> of integer variables and supresses most checks accordingly.
> 

Actually, most algorithms for this kind of thing would do that. Check
out "Elimination of Redundant Array Subscript Range Checks" from
P. Kolte and M. Wolfe for a nice introduction to this stuff. It's
available on the web from cse.ogi.edu but I haven't got the URL
handy. They cite the Alsys and Karlsruhe Ada compiler as previous
work. In their examples (with Fortran) they eliminate typically 98% of
the checks that a naive implementation inserts but I have the feeling
this would be too optimistical in general.  Earlier work by Gupta
using a slightly different approach gives elimination percentages from
52 to 100 with typical values around 80-90.

One of the problems in doing this with Ada is that the language spec
describes the exact behaviour for errors like this. You have to raise
the correct exception after having done all the previous effects. This
restricts the freedom of the compiler to rearrange checks. In
languages with similar semantics for arrays like Modula-3 the only
behaviour prescribed is that it is a checked runtime error with leaves
the implementation with much more freedom. One way to solve this is to
do the rearrangements with the minimal checks to determine a bounds
violation and on detection switch to a slower version of the routine
that has the correct error behaviour but this would introduce a lot of
code bloat.

-- 
Lieven Marchand <mal@bewoner.dma.be> 
------------------------------------------------------------------------------
Few people have a talent for constructive laziness. -- Lazarus Long