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

On Fri, Aug 22, 2008 at 5:49 PM, John Regehr <regehr at cs.utah.edu>
wrote:
>> Thanks!  This is all very interesting, and tells me that LLVM has a
>> way to go to fully support all of these capabilities (if that is the
>> right thing to do, which isn't clear).  OTOH, it looks like a lot
of
>> real-world software that is using LLVM already doesn't seem to be
>> affected by the lack of them.
>
> LLVM's current choice is safe for all applications.  The trapping
behavior
> would be a really nice addition, though.
>
> Has anyone quantified the optimizations afforded by undefined signed
> overflow?  I'd expect that the benefits are minimal for most codes.  On
> the other hand I've seen reports that gcc's -fwrapv hurts
performance of
> gcc output significantly.  I'm not sure if that is true.  Also, it
could
> be the case that -fwrapv is implemented poorly.
No, it's not implemented badly.  We've quantified it's performance
before and it hurts about 3-5 without high level loop
opts/vectorization on.  With them on, they do roughly nothing in the
presence of -fwrapv because you can't determine bounds of any non
trivial loop.


take a simple loop

void foo(int a)
{
for (int i = 0; i < a; i += 2)
{
}
}
If you assume signed overflow is undefined, this loop iterates at max,
a/2 times.
If you assume it is defined to wraparound, it can iterate forever
(consider a == INT_MAX)

On Fri, Aug 22, 2008 at 8:50 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> On Fri, Aug 22, 2008 at 5:49 PM, John Regehr <regehr at cs.utah.edu>
wrote:
>>> Thanks!  This is all very interesting, and tells me that LLVM has a
>>> way to go to fully support all of these capabilities (if that is
the
>>> right thing to do, which isn't clear).  OTOH, it looks like a
lot of
>>> real-world software that is using LLVM already doesn't seem to
be
>>> affected by the lack of them.
>>
>> LLVM's current choice is safe for all applications.  The trapping
behavior
>> would be a really nice addition, though.
>>
>> Has anyone quantified the optimizations afforded by undefined signed
>> overflow?  I'd expect that the benefits are minimal for most codes.
On
>> the other hand I've seen reports that gcc's -fwrapv hurts
performance of
>> gcc output significantly.  I'm not sure if that is true.  Also, it
could
>> be the case that -fwrapv is implemented poorly.
> No, it's not implemented badly.  We've quantified it's
performance
> before and it hurts about 3-5 without high level loop
> opts/vectorization on.
3-5%, sorry.

> before and it hurts about 3-5 without high level loop
> opts/vectorization on.  With them on, they do roughly nothing in the
> presence of -fwrapv because you can't determine bounds of any non
> trivial loop.
Very interesting, thanks!  Before hearing this I'd have said that 
Java-style overflow is the right language design, but if this makes loop 
optimizations impossible that is not so good.

John

On Fri, Aug 22, 2008 at 11:18 PM, John Regehr <regehr at cs.utah.edu>
wrote:
>> before and it hurts about 3-5 without high level loop
>> opts/vectorization on.  With them on, they do roughly nothing in the
>> presence of -fwrapv because you can't determine bounds of any non
>> trivial loop.
>
> Very interesting, thanks!  Before hearing this I'd have said that
> Java-style overflow is the right language design, but if this makes loop
> optimizations impossible that is not so good.
Java JIT's work very hard to work around the fact that the language
backs them into a corner.
FWIW, You can replace i+=2 with i++ or i-- in my example and still not
be able to determine the loop bounds :(