llvm -> array bound checking at compile time

Dear Boris,

I managed to see your question and rescue it from the llvm-announce mailing list filter. I'm forwarding your question to the llvmdev@cs.uiuc.edu mailing list; that list is used for questions and answers about LLVM.

For future reference, the llvm-announce list is used to send announcements regarding LLVM releases. The llvmdev list is for general discussion.

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.

Regards,

-- John T.

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