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

Fri Aug 22 09:30:14 PDT 2008

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

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

```