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

Chris Lattner clattner at apple.com
Fri Aug 22 09:34:00 PDT 2008

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.


> 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

More information about the llvm-dev mailing list