Compilers - array bounds checking

Author

array bounds checking

2005-11-26, 3:58 am

Hi
I am wondering if anybody knew how array bounds checks worked when
they are references through multiple indirections of pointers. Eg: p =
A ; q= &p; ***q+100=0; So q is referencing A. And hence I would like
a check inserted there.
Do array bounds checking handle these cases, because this
also would need pointer analysis.

Any ideas/pointers to any papers ...
thanks
dz
[Depends on the language and implementation. If it has "fat" pointers that contain
type info, then the bounds can be in the pointers, or pointed to by fields in the
pointers. -John]

Nick Maclaren

2005-11-27, 3:57 am

dz <drizzle76@gmail.com> wrote:
> I am wondering if anybody knew how array bounds checks worked when
>they are references through multiple indirections of pointers. Eg: p =
>A ; q= &p; ***q+100=0; So q is referencing A. And hence I would like
>a check inserted there.
> Do array bounds checking handle these cases, because this
>also would need pointer analysis.

If you are talking about C, array bounds checking is effectively
hopeless. If you were talking about Fortran, it is fairly easy.

>[Depends on the language and implementation. If it has "fat" pointers
>that contain type info, then the bounds can be in the pointers, or
>pointed to by fields in the pointers. -John]

The main alternative approach is to have arrays implemented as structures,
including the bounds and data pointer.

Regards,
Nick Maclaren.

Sudesh Chandna, Noida

2005-11-29, 7:03 pm

Hi,

>_I am wondering if anybody knew how array bounds checks worked when
>they are references through multiple indirections of pointers. Eg: p =
>A ; q= &p; ***q+100=0; So q is referencing A. And hence I would like a
>check inserted there.
>___________________Do array bounds checking handle these cases, because
>this also would need pointer analysis.

This can be easily done by having a data structure commonly known as
"descriptor" for pointer which can hold lower bound, upper bound, stride
corresponding to all dimensions of the array. Also descriptor should have rank
( dimension ) and address of the array. Now for languages such as FORTRAN
where its possible to say

Ptr => ary(1:10:2)

Descriptor values lower bound would be 1
Upper bound would be 5
Stride would be say 8 (2*size of element)
Rank would be 1
And addr will hold starting address.

This information can be used at runtime to do bounds checking.

Thanks & Best Regards,
Sudesh Chandna
Senior Member Technical Staff

glen herrmannsfeldt

2005-12-03, 7:00 pm

Sudesh Chandna, Noida wrote:

> This can be easily done by having a data structure commonly known as
> "descriptor" for pointer which can hold lower bound, upper bound, stride
> corresponding to all dimensions of the array. Also descriptor should have rank
> ( dimension ) and address of the array. Now for languages such as FORTRAN
> where its possible to say

> Ptr => ary(1:10:2)

> Descriptor values lower bound would be 1
> Upper bound would be 5
> Stride would be say 8 (2*size of element)
> Rank would be 1
> And addr will hold starting address.

Ones I know store the virtual origin, the address of element (0,...,0).
It makes it easy to do the calculation, multiply the strides by the
subscripts and add. (After checking bounds.)

-- glen

neal.wang@gmail.com

2005-12-08, 3:59 am

dz wrote:
> Hi
> I am wondering if anybody knew how array bounds checks worked when
> they are references through multiple indirections of pointers. Eg: p =
> A ; q= &p; ***q+100=0; So q is referencing A. And hence I would like
> a check inserted there.
> Do array bounds checking handle these cases, because this
> also would need pointer analysis.

It's mostly hopeless if you want static bounds checks.
Please check Necula's "CCured: Type-Safe Retrofitting of Legacy Code",
It automatically does pointer kind type inference and insert runtime
bounds check
for wild pointers. pointer analysis is also needed to find the correct
targets.

Cheers,
Neal

Sponsored Links