llvm dev - Aug 2008 - [LLVMdev] Dependence Analysis [was: Flow-Sensitive AA]

>However, there is one issue I have ignored - possibility of overflow in
>the index expression. Suppose, we have such a loop:
>  for (i8 i = 0; i != 200; ++i) {
>    A[2 * i + 5] = ...
>    ... = A[2 * i + 3]
>  }
>If both index expressions are evaluated in 8-bit arithmetic,
>then the dependence equation should be solved in modular arithmetic:
>  2 * i + 5 == 2 * (i + delta) + 3 (mod 256)
>So the dependence distance is delta == 1 or delta == -127 what gives
>two direction vectors: (<), (>). My version will produce only the
first
>one. Taking into account overflow issue during dependence analysis seems
>very difficult to me. Does anybody have some experience in this area?
>Fortunately, programmers generally do not write programs in such a
>nasty way.
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 ?

In the general case, I think you have to be conservative about this  
because programmers may deliberately want this kind of "wraparound"  
behavior, e.g., with periodic boundary conditions.  But 99.9% of  
programs probably don't need that so it would be bad to penalize them  
for this corner case.  In such a situation, I think you just have to  
support both choices, but choose the default as sensibly as possible.   
I discussed this with Matthieu and this is what we came up with:

1. (Eventually) Support both choices: conservative or optimistic.   
Conservative means you assume that index arithmetic can wrap around;  
optimistic assumes it cannot.  What I think you've implemented is the  
optimistic case.

2. Have a default choice but give the programmer an option to force  
this on or off.

3. (Matthieu's idea) Default to optimistic if the index expressions  
are i32, but conservative if i8 or i16.  This assumes that there is no  
good reason to use i8 or i16 index variables except for wraparound  
behavior (and it is highly unlikely that programmers are using arrays  
of size 2^32 *and* requiring wraparound behavior for that).

Of course, for now, we don't have to implement the conservative  
version: what you've done should be good enough.

--Vikram
Associate Professor, Computer Science
University of Illinois at Urbana-Champaign
http://llvm.org/~vadve




On Aug 22, 2008, at 9:41 AM, matthieu at illinois.edu wrote:
>
>
>
>> However, there is one issue I have ignored - possibility of  
>> overflow in
>> the index expression. Suppose, we have such a loop:
>> for (i8 i = 0; i != 200; ++i) {
>>   A[2 * i + 5] = ...
>>   ... = A[2 * i + 3]
>> }
>> If both index expressions are evaluated in 8-bit arithmetic,
>> then the dependence equation should be solved in modular arithmetic:
>> 2 * i + 5 == 2 * (i + delta) + 3 (mod 256)
>> So the dependence distance is delta == 1 or delta == -127 what gives
>> two direction vectors: (<), (>). My version will produce only the
>> first
>> one. Taking into account overflow issue during dependence analysis  
>> seems
>> very difficult to me. Does anybody have some experience in this area?
>> Fortunately, programmers generally do not write programs in such a
>> nasty way.
>
> 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 ?
>
>

On Aug 22, 2008, at 9:30 AM, Vikram S. Adve wrote:
> In the general case, I think you have to be conservative about this
> because programmers may deliberately want this kind of
"wraparound"
> behavior, e.g., with periodic boundary conditions.  But 99.9% of
> programs probably don't need that so it would be bad to penalize them
> for this corner case.  In such a situation, I think you just have to
> support both choices, but choose the default as sensibly as possible.
> I discussed this with Matthieu and this is what we came up with:
C has a way to express this: signed integers are defined to never  
overflow, unsigned integers are defined to wrap gracefully on  
overflow.  Other languages that target this may want some sort of  
command line option to control the behavior or the language may define  
it one way or the other.

We don't model this in LLVM IR, but this is a desired feature if  
anyone is interested.  Capturing this in the IR is a better way to go  
than having the optimizers have a big global knob.

-Chris
>
>
> 1. (Eventually) Support both choices: conservative or optimistic.
> Conservative means you assume that index arithmetic can wrap around;
> optimistic assumes it cannot.  What I think you've implemented is the
> optimistic case.
>
> 2. Have a default choice but give the programmer an option to force
> this on or off.
>
> 3. (Matthieu's idea) Default to optimistic if the index expressions
> are i32, but conservative if i8 or i16.  This assumes that there is no
> good reason to use i8 or i16 index variables except for wraparound
> behavior (and it is highly unlikely that programmers are using arrays
> of size 2^32 *and* requiring wraparound behavior for that).
>
> Of course, for now, we don't have to implement the conservative
> version: what you've done should be good enough.
>
> --Vikram
> Associate Professor, Computer Science
> University of Illinois at Urbana-Champaign
> http://llvm.org/~vadve
>
>
>
>
> On Aug 22, 2008, at 9:41 AM, matthieu at illinois.edu wrote:
>
>>
>>
>>
>>> However, there is one issue I have ignored - possibility of
>>> overflow in
>>> the index expression. Suppose, we have such a loop:
>>> for (i8 i = 0; i != 200; ++i) {
>>>  A[2 * i + 5] = ...
>>>  ... = A[2 * i + 3]
>>> }
>>> If both index expressions are evaluated in 8-bit arithmetic,
>>> then the dependence equation should be solved in modular
arithmetic:
>>> 2 * i + 5 == 2 * (i + delta) + 3 (mod 256)
>>> So the dependence distance is delta == 1 or delta == -127 what
gives
>>> two direction vectors: (<), (>). My version will produce only
the
>>> first
>>> one. Taking into account overflow issue during dependence analysis
>>> seems
>>> very difficult to me. Does anybody have some experience in this  
>>> area?
>>> Fortunately, programmers generally do not write programs in such a
>>> nasty way.
>>
>> 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 ?
>>
>>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

> 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. 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.

-Wojtek

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>

On Sun, Aug 24, 2008 at 2:46 PM, Wojciech Matyjewicz
<wmatyjewicz at fastmail.fm> 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?
Well, if you assume it's impossible to allocate more than 2GB on a
32-bit platform, you can assume GEP operands are signed.  You do have
to be careful, though; it's not inconceivable that someone could
allocate more than 2GB on a 32-bit platform, and you still have to
watch out for the operands overflowing.  That said, GEP overflow is
undefined, and that might be good enough for some purposes.

Also, here's a trick that could be useful for calculations that are
sensitive to overflow: if a loop has only a single possible exit
controlled by an index variable, and it doesn't use any
synchronization primitives, you can assume the loop isn't infinite for
dependence analysis purposes.  If the loop does end up being infinite,
the results aren't visible outside of the loop, so it doesn't matter
if results aren't accurate.

-Eli