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

[Vikram S. Adve]

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