[LLVMdev] Re: llvm -> array bound checking at compile time

[Dinakar Dhurjati]

To add to John's repsonse,

> Now, on to your question:
>
> LLVM does not provide static or runtime checks of array bounds (unlike
> the Java Virtual Machine, which performs run-time checks) nor is there
> an instruction to do so.  This allows LLVM to compile arbitrary
> programs, regardless of whether the program is safe or not.
>
> That said, a compiler can always insert these checks when compiling into
> LLVM bytecode.  So, if you wrote a Java to LLVM compiler, the checks
> would be there.
>
> It may also be possible to write analysis and transformation passes to
> do this, although I imagine that this would be non-trivial for
> type-unsafe code.


Sumant Kowshik and I  have been working on  the same thing for type unsafe
code in our SAFECode project. see http://safecode.cs.uiuc.edu

We try to statically prove safety of array accesses wherever possible.
Specifically, if the index expression used in the array access is provably
affine in terms of the array size, we try and prove the safety of that
access using a theorem prover.  It involves interprocedural propagation of
constraints on array sizes, indices. This procedure can also be used to
remove unnecessary bounds checks in type safe languages like Java etc. For
more details, look in to the array safety sections in the two
publications,

http://llvm.cs.uiuc.edu/pubs/2003-05-05-LCTES03-CodeSafety.html
http://llvm.cs.uiuc.edu/pubs/2002-08-08-CASES02-ControlC.html

For those array accesses  for which we cannot statically prove the safety,
we insert run time checks.

Dinakar