[LLVMdev] GSoC - Range Analysis

[John Criswell]

On 4/2/12 11:35 AM, John Regehr wrote:
>> from what I understand of the analysis, to come to its conclusions it assumes
>> that there is no overflow.  That doesn't make it useless for removing integer
>> overflow checks: you can successively walk variables, and if you can prove that
>> there is no overflow of a variable X given your analysis of previously seen
>> variables, then X can safely be added to the set of analysed variables.  Rinse
>> and repeat.  However this probably doesn't work for variables inside loops.
> I'd also be interested to hear more from the range analysis authors about
> this.
>
> Remaining faithful to the C/C++ overflow rules while operating on LLVM IR
> may be very tricky, particularly with respect to integer promotions and
> similar constructs, which may have no representation in the IR (even
> before optimization).
>
> An analysis that is not sound with respect to the original C/C++ semantics
> would be of little use to anyone.

I actually disagree on the last point.  For static array bounds checking 
with SAFECode, we want to assume that all integer operations can 
overflow (including those with the nsw attribute).  We don't care about 
the other integer semantic rules from C (like the promotion rules) or 
whether overflow is language defined or not (for those who don't know, 
unsigned ints have defined overflow in C; signed ints do not).  All we 
want to know is whether a pointer p is within the bounds of a set of 
valid objects, and we just need to take integer overflow into account 
because it can happen on the hardware.

-- John T.


>
> John
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev