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

[Daniel Berlin]

On Fri, Aug 22, 2008 at 5:12 PM, Chris Lattner <clattner at apple.com> wrote:
>
> On Aug 22, 2008, at 9:53 AM, Dale Johannesen wrote:
>
>>>
>>> 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.
>
> In other words, our current implementation is correct.  However, we
> are missing the opportunity to optimize some things.  Trivial examples
> include some cases where you can't compute a simple loop count due to
> potential overflow.

IBM (and Sun, but not Intel, IIRC) went even further, and at O3 or
above actually assume *unsigned* integers don't overflow or wraparound
for loops iv's.
they did this because it caused something like a 50% performance
regression on a bunch of serious applications when they were compiling
code that used 32 bit types as index variables on 64 bit machines (and
the resulting sign extensions, etc).
http://publib.boulder.ibm.com/infocenter/lnxpcomp/v7v91/index.jsp?topic=/com.ibm.vacpp7l.doc/compiler/ref/ruoptsti.htm
See /qstrict_induction

Personally i think this goes too far, but it would be nice if you
could tell a user "btw, we can't optimize this loop because we are
assuming your index variables can overflow"