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

[Vikram S. Adve]

On Aug 22, 2008, at 11:53 AM, Dale Johannesen wrote:

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

Ok, I thought they both had the same wraparound behavior: thanks for  
clarifying that.



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


That makes sense.  But we would have to distinguish them during  
dependence analysis at least, if we want to use the solution Chris  
suggested.  Which brings me to a question:


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


But signed and unsigned values are not distinguished any more in the  
LLVM IR, and I don't think you're suggesting we restore unsigned  
types.  What do you have in mind here?

--Vikram