llvm dev - Apr 2004 - [LLVMdev] Re: 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 at 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.

 > Hello,

 > does there exist an explicit instruction in the llvm-IR for performing 
> checks on array bounds? Or is array bound checking done implicitly at  >
run-time?


-- 
*********************************************************************
* John T. Criswell                         Email: criswell at uiuc.edu *
* Research Programmer                                               *
* University of Illinois at Urbana-Champaign                        *
*                                                                   *
* "It's today!" said Piglet. "My favorite day," said
Pooh.          *
*********************************************************************

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