range checking

range checking

[Dinakar Dhurjati]

Hi,

I am a researcher in compilers/security.

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
Or the subranges have to be given by the programmer  ?

(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 ? Are these checks done
statically or at runtime ? Are there any compilers which try to reduce the
amount of runtime checks that need to be done ?

Thanks,

Dinakar

Re: range checking

[Martin Krischik]

Dinakar Dhurjati wrote:

> Hi,
> 
> I am a researcher in compilers/security.
> 
> 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
> Or the subranges have to be given by the programmer  ?

The compiler can deduct the range on assignment:

x : String (0 .. 10);
y : String := x;

Once y has x assigned to it the range is frozen and cannot be changed. The
size does not need to be known at compile time:

procedure x (Size : Integer)
is
    x : String (0 .. Size);
begin
    null;
end x;

> (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 ? Are these checks done
> statically or at runtime ? Are there any compilers which try to reduce the
> amount of runtime checks that need to be done ?

The optimizer usualy analyzes the assignment and removed unneded checks. So
in x := x + 1; only the upper bound need to be checked.

The optimizer usualy will also make a static checks and issue a warning.
i.E.:

x : Interger := Integer'Last;
x := x + 1;

might raise a warning at compile time. However the language standart does
not enforce the existance of an optimizer.

With Regards

Martin

-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com

Re: range checking

[Nick Roberts]

"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]