Re: range checking

["Nick Roberts" <nickroberts@blueyonder.co.uk>]

"Dinakar Dhurjati" <dhurjati@uiuc.edu> wrote in message
news:Pine.SOL.4.44.0307021627430.15367-100000@tank.cs.uiuc.edu...

> I am looking to adapt Ada's subrange idea for eliminating
> some array bounds checks for a different language. I am
> curious as to how the thing works in common
> implementations. Any pointers welcome.
>
> Specifically
>
> (1) Are there any compilers which try to infer the subranges
> themselves.

It is possible, by doing data-flow analysis, but I'm not sure whether there
are any compilers which actually do it. I suspect it is generally seen as an
unimportant optimisation (I do not entirely share this view).

> Or the subranges have to be given by the programmer  ?

There is an advantage to a valid range being specified by the programmer,
separate to -- and probably more important than -- optimisation, in that it
can provide a check upon the correctness of the program.

Of course, it will often be the case that the programmer has more knowledge
than the compiler can infer from a (typical) data-flow analysis, and can
therefore explicitly specify a range that is a sufficiently smaller subset
of the range the compiler can deduce to enable valuable optimisations (such
as reduced register size or memory usage, or knock-on optimisations).

> (2) If a variable is declared is of type some subrange, then
> every assignment to that variable needs to be checked for
> correctness -- i.e. if the assigned value is with in the
> subrange, right ?

After every update of a variable of a scalar type (whose subtype has range
which is a subset of that of the type), a check must be notionally performed
(before the variable could possibly be read) against each bound of the range
of its subtype. If the compiler can deduce that the update could not
possibly exceed the bound, the check can be eliminated, otherwise it must
actually be performed.

> Are these checks done statically or at runtime ?

If the new value (the value to which the variable is updated) is a static
constant, each check can be performed statically (at compile time),
otherwise it must be performed dynamically (code must be inserted which will
perform the check at run time). If a static check fails, the code which
updates the variable can be replaced by code which raises the exception
Constraint_Error (but generally no side effects may be eliminated), and it
might be nice for the compiler to issue a warning (but not necessarily).

> Are there any compilers which try to reduce the amount
> of runtime checks that need to be done ?

I think most Ada compilers do.

--
Nick Roberts
Jabber: debater@charente.de [ICQ: 159718630]