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

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.

Does anyone know of any C/C++ programs that require integer overflow  
on signed arithmetic (even though it is not strictly allowed by the  
standard)?

Also, does anyone know how -ftrapv is implemented on processors that  
don't have hardware detection of integer overflow?  It sounds very  
expensive to do entirely in software.

Thanks,

--Vikram
Associate Professor, Computer Science
University of Illinois at Urbana-Champaign
http://llvm.org/~vadve




On Aug 22, 2008, at 3:50 PM, Mike Stump wrote:
> On Aug 22, 2008, at 9:34 AM, Chris Lattner wrote:
>> C has a way to express this: signed integers are defined to never
>> overflow, unsigned integers are defined to wrap gracefully on
>> overflow.
>
> And gcc has yet more fun in it:
>
>        -fstrict-overflow
>            Allow the compiler to assume strict signed overflow rules,
> depending on the language
>            being compiled.  For C (and C++) this means that overflow
> when doing arithmetic with
>            signed numbers is undefined, which means that the compiler
> may assume that it will
>            not happen.  This permits various optimizations.  For
> example, the compiler will
>            assume that an expression like "i + 10 > i" will
always be
> true for signed "i".  This
>            assumption is only valid if signed overflow is undefined,
> as the expression is false
>            if "i + 10" overflows when using twos complement
> arithmetic.  When this option is in
>            effect any attempt to determine whether an operation on
> signed numbers will overflow
>            must be written carefully to not actually involve overflow.
>
>            See also the -fwrapv option.  Using -fwrapv means that
> signed overflow is fully
>            defined: it wraps.  When -fwrapv is used, there is no
> difference between
>            -fstrict-overflow and -fno-strict-overflow.  With -fwrapv
> certain types of overflow
>            are permitted.  For example, if the compiler gets an
> overflow when doing arithmetic
>            on constants, the overflowed value can still be used with -
> fwrapv, but not otherwise.
>
>            The -fstrict-overflow option is enabled at levels -O2, -
> O3, -Os.
>
>        -ftrapv
>            This option generates traps for signed overflow on
> addition, subtraction,
>            multiplication operations.
>
>        -fwrapv
>            This option instructs the compiler to assume that signed
> arithmetic overflow of
>            addition, subtraction and multiplication wraps around
> using twos-complement
>            representation.  This flag enables some optimizations and
> disables others.  This
>            option is enabled by default for the Java front-end, as
> required by the Java language
>            specification.
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On Fri, Aug 22, 2008 at 5:03 PM, Vikram S. Adve <vadve at cs.uiuc.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.
>
> Does anyone know of any C/C++ programs that require integer overflow
> on signed arithmetic (even though it is not strictly allowed by the
> standard)?
Yes, see the unending discussion on the gcc mailing list about
programs we are breaking that led to the introduction of this option.

My serious suggestion would be to tell any users who require this flag
to shove it.
:)

(Otherwise you end up in a very dark place because there are a lot of
optimizations that make assumptions about overflow when rearranging
expressions, etc).

On Aug 22, 2008, at 2:03 PM, Vikram S. Adve 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.
>
> Does anyone know of any C/C++ programs that require integer overflow
> on signed arithmetic (even though it is not strictly allowed by the
> standard)?
Yes, it is a common bug to depend on this.  See (for example):
http://www.kb.cert.org/vuls/id/162289
> Also, does anyone know how -ftrapv is implemented on processors that
> don't have hardware detection of integer overflow?  It sounds very
> expensive to do entirely in software.
GCC's -ftrapv option is not fully implemented on any target, so it is  
not really dependable.  The Ada frontend (which requires trap on  
overflow in some cases) for example implement their own range checks  
instead of relying on GCC's ftrapv support.

-Chris

On Aug 22, 2008, at 4:14 PM, Daniel Berlin wrote:
> On Fri, Aug 22, 2008 at 5:03 PM, Vikram S. Adve <vadve at
cs.uiuc.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.
>>
>> Does anyone know of any C/C++ programs that require integer overflow
>> on signed arithmetic (even though it is not strictly allowed by the
>> standard)?
>
> Yes, see the unending discussion on the gcc mailing list about
> programs we are breaking that led to the introduction of this option.
>
> My serious suggestion would be to tell any users who require this flag
> to shove it.
> :)
That sounds good to me!  In any case, for dependence analysis and  
parallel code generation at least, we have many more fish to fry  
before this even becomes an issue.
>
>
> (Otherwise you end up in a very dark place because there are a lot of
> optimizations that make assumptions about overflow when rearranging
> expressions, etc).


--Vikram
Associate Professor, Computer Science
University of Illinois at Urbana-Champaign
http://llvm.org/~vadve

On Friday 22 August 2008 16:14, Daniel Berlin wrote:
> On Fri, Aug 22, 2008 at 5:03 PM, Vikram S. Adve <vadve at
cs.uiuc.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.
> >
> > Does anyone know of any C/C++ programs that require integer overflow
> > on signed arithmetic (even though it is not strictly allowed by the
> > standard)?
>
> Yes, see the unending discussion on the gcc mailing list about
> programs we are breaking that led to the introduction of this option.
>
> My serious suggestion would be to tell any users who require this flag
> to shove it.
>
> :)
Right on!
> (Otherwise you end up in a very dark place because there are a lot of
> optimizations that make assumptions about overflow when rearranging
> expressions, etc).
Exactly right.  One of my first jobs here was to fix a bunch of overflow 
problems exposed by optimization.  It's now become a tradition to
give this task to any new optimizer employee.  :)

                                                  -Dave

> 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.
> Does anyone know of any C/C++ programs that require integer overflow
> on signed arithmetic (even though it is not strictly allowed by the
> standard)?
I've seen embedded programs that do this.

Of course, the C standard is clear: these programs are wrong.

John

On Aug 22, 2008, at 4:49 PM, John Regehr wrote:
> Has anyone quantified the optimizations afforded by undefined signed
> overflow?  I'd expect that the benefits are minimal for most codes.
In most cases, I agree.  But for codes that depend heavily on  
dependence analysis, I would think that being conservative with index  
expressions would really kill any disambiguation capability and make  
many loop optimizations and other dependence-based optimizations much  
weaker.  For example, static scheduling of array intensive loops seems  
vulnerable to this.

--Vikram

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)