llvm dev - Aug 2008 - [LLVMdev] Dependence Analysis [was: Flow-Sensitive AA]

On Sun, Aug 24, 2008 at 2:46 PM, Wojciech Matyjewicz
<wmatyjewicz at fastmail.fm> wrote:
>> 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 ?
>
> I think it is not possible in general, but I believe it is possible in
> case of affine expressions used as GEP indices.
>
> I assume, GEP indices (except indexing into struct) are interpreted as
> signed integers. It isn't explicitly stated in the LangRef, but the
code
> seems to treat them this way. Am I correct?
Well, if you assume it's impossible to allocate more than 2GB on a
32-bit platform, you can assume GEP operands are signed.  You do have
to be careful, though; it's not inconceivable that someone could
allocate more than 2GB on a 32-bit platform, and you still have to
watch out for the operands overflowing.  That said, GEP overflow is
undefined, and that might be good enough for some purposes.

Also, here's a trick that could be useful for calculations that are
sensitive to overflow: if a loop has only a single possible exit
controlled by an index variable, and it doesn't use any
synchronization primitives, you can assume the loop isn't infinite for
dependence analysis purposes.  If the loop does end up being infinite,
the results aren't visible outside of the loop, so it doesn't matter
if results aren't accurate.

-Eli

On Sun, Aug 24, 2008 at 6:28 PM, Eli Friedman <eli.friedman at gmail.com>
wrote:
> On Sun, Aug 24, 2008 at 2:46 PM, Wojciech Matyjewicz
> <wmatyjewicz at fastmail.fm> wrote:
>>> 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 ?
>>
>> I think it is not possible in general, but I believe it is possible in
>> case of affine expressions used as GEP indices.
>>
>> I assume, GEP indices (except indexing into struct) are interpreted as
>> signed integers. It isn't explicitly stated in the LangRef, but the
code
>> seems to treat them this way. Am I correct?
>
> Well, if you assume it's impossible to allocate more than 2GB on a
> 32-bit platform, you can assume GEP operands are signed.  You do have
> to be careful, though; it's not inconceivable that someone could
> allocate more than 2GB on a 32-bit platform, and you still have to
> watch out for the operands overflowing.  That said, GEP overflow is
> undefined, and that might be good enough for some purposes.
>
> Also, here's a trick that could be useful for calculations that are
> sensitive to overflow: if a loop has only a single possible exit
> controlled by an index variable, and it doesn't use any
> synchronization primitives, you can assume the loop isn't infinite for
> dependence analysis purposes.
You also have to include inline assembly, tls variables, shared global
memory, etc.
(These aren't synchronization primitives per-se, though they can be
used to implement them).

On Aug 24, 2008, at 11:10 PM, Daniel Berlin wrote:
>>
>> Also, here's a trick that could be useful for calculations that are
>> sensitive to overflow: if a loop has only a single possible exit
>> controlled by an index variable, and it doesn't use any
>> synchronization primitives, you can assume the loop isn't infinite
>> for
>> dependence analysis purposes.
>
> You also have to include inline assembly, tls variables, shared global
> memory, etc.
> (These aren't synchronization primitives per-se, though they can be
> used to implement them).


Also, any kind of output I/O.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.org/