[LLVMdev] Dependence Analysis [was: Flow-Sensitive AA]

[Vikram S. Adve]

On Aug 24, 2008, at 4:46 PM, Wojciech Matyjewicz wrote:

>> I asked myself the same question. Without mod, how do you ensure  
>> that for instance the expression 2*i+255 was not actually 2*i-1 ?
>
> I think it is not possible in general, but I believe it is possible in
> case of affine expressions used as GEP indices.
>
> I assume, GEP indices (except indexing into struct) are interpreted as
> signed integers. It isn't explicitly stated in the LangRef, but the  
> code
> seems to treat them this way. Am I correct?
>
> If the result of an affine expression:
>   a_1*i_1 + a_2*i_2 + ... + a_n*i_n
> is interpreted as signed value during the program run, it should be  
> safe
> to assume during the program analysis that all operations  
> (coefficients)
> are signed - signed evaluation of such an expression will bring the  
> same
> result as evaluation of the expression using original signedness and
> interpretation of the produced value as signed.


That sounds correct to me.



> However, such an
> assumption requires that arbitrary precise arithmetic is used during  
> the
> program analysis. Otherwise, a signed overflow (undefined in LLVM)  
> might
> be introduced that does not appear during the program run.

I think you can do this without true arbitrary precision arithmetic,  
but just a few careful checks for overflow in the compiler.


>
>
> -Wojtek



--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.org/



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080824/2a3564af/attachment.html>