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

[Dale Johannesen]

On Aug 22, 2008, at 9:34 AMPDT, Chris Lattner wrote:

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

More precisely, signed integer overflow is undefined behavior, which  
gives the compiler great latitude.
Assuming this will never happen and doing optimizations on that basis  
is valid, but so are other things.
An easy implementation, which often matches user expectations because  
it is what most hardware does,
is to treat signed and unsigned overflow alike, with clean wraparound.

> 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
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev