[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011-12-22
     Ever Confirmed|0                           |1

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> 2011-12-22 03:24:20 UTC ---
Confirmed.

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[DMueller at suse dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

--- Comment #4 from DMueller at suse dot com 2011-12-22 03:25:02 UTC ---
Hi, 

I'm currently out of office until December 28th and your email will be handled
when I'm back. 

For urgent SUSE Maintenance related issues that can not wait until then, please
send your mail to maint-coord@suse.de instead. 

Thanks,
Dirk

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[marc.glisse at normalesup dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

--- Comment #5 from Marc Glisse <marc.glisse at normalesup dot org> 2012-04-28 13:18:25 UTC ---
Created attachment 27260
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27260
Wrap using gmp

I find it easier to use bignum and wrap at the end, instead of checking for
each operation if it overflows.

There is something wrong about having better range propagation for the wrapping
case than for the case where overflow is undefined behavior. There are cases
where a range is set to varying whereas it could be set to empty, and the
branch marked as unreachable (haven't seen how that's done). But that's not the
subject of this bug.

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[rguenther at suse dot de]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

--- Comment #6 from rguenther at suse dot de <rguenther at suse dot de> 2012-05-02 08:21:57 UTC ---
On Sat, 28 Apr 2012, marc.glisse at normalesup dot org wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318
> 
> --- Comment #5 from Marc Glisse <marc.glisse at normalesup dot org> 2012-04-28 13:18:25 UTC ---
> Created attachment 27260
>   --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27260
> Wrap using gmp
> 
> I find it easier to use bignum and wrap at the end, instead of checking for
> each operation if it overflows.

I think using GMP is way too expensive for this (simple) task.

> There is something wrong about having better range propagation for the wrapping
> case than for the case where overflow is undefined behavior. There are cases
> where a range is set to varying whereas it could be set to empty, and the
> branch marked as unreachable (haven't seen how that's done). But that's not the
> subject of this bug.

Well, my original idea was to simultanely do range propagation for
wrapping and undefined overflow, and in the case that both results
result in different final transforms warn (to avoid the fact that
we do not fully take advantage of undefined overflow during propagation
and to avoid false positives on the warnings for undefined overflow).

So at least both propagations should be powerful enough to handle
all basic arithmetic "completely".

Richard.

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[marc.glisse at normalesup dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

--- Comment #7 from Marc Glisse <marc.glisse at normalesup dot org> 2012-05-02 14:33:42 UTC ---
(In reply to comment #6)
> On Sat, 28 Apr 2012, marc.glisse at normalesup dot org wrote:
> > I find it easier to use bignum and wrap at the end, instead of checking for
> > each operation if it overflows.
> I think using GMP is way too expensive for this (simple) task.

As long as you only try to handle operations on types no larger than
HOST_WIDE_INT, using double_int should be possible. But if you want to handle
wrapping multiplication of __int128, that's going to be hard without a widening
multiplication to __int256. I guess I could implement a mulhi on double_int...
Or at least make sure the slow path is only used for __int128 and not for small
types. Or even fall back to VR_VARYING when __int128 overflows, but that's sad.

(as a side note, it is strange that double_int is signed, it seems it should
break with strict overflow)

> Well, my original idea was to simultanely do range propagation for
> wrapping and undefined overflow, and in the case that both results
> result in different final transforms warn (to avoid the fact that
> we do not fully take advantage of undefined overflow during propagation
> and to avoid false positives on the warnings for undefined overflow).

Good idea.

I guess one of my problems is that there are several possible notions of
overflow and I don't really know which gcc wants.

- wrap (unsigned and -fwrapv)
- saturating (not currently)
- trap (has to detect overflows and do something about them)
- unspecified (don't know anything about the value produced by an overflow, but
it is legal)
- illegal (we are allowed to crash the computer if such a path is ever taken,
but also to just keep going with a random value, that may not even be
consistent between uses, I guess that's -fstrict-overflow)

The comments at the definition of TYPE_OVERFLOW_UNDEFINED seem to indicate that
it means "illegal", but tree-vrp tends to use: non-wrapping => unspecified. And
I don't think value_range_d has a notion of an empty range (VR_UNDEFINED or
VR_RANGE with max<min don't seem to be used that way, and just having
TREE_OVERFLOW in one of the extremities of the interval is not preserved by
enough operations).

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

--- Comment #8 from glisse at gcc dot gnu.org 2012-05-04 21:45:49 UTC ---
Created attachment 27311
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27311
Wrap plus/minus

This patch handles combinations of range/anti_range for PLUS_EXPR and
MINUS_EXPR. I'll try to do MULT_EXPR later so that for -10<i<10 and -10<j<10 we
get the same range for (unsigned)(i*j) and (unsigned)i*(unsigned)j.

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #27311|0                           |1
        is obsolete|                            |

--- Comment #9 from Marc Glisse <glisse at gcc dot gnu.org> 2012-05-05 13:17:43 UTC ---
Created attachment 27317
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27317
Wrap plus/minus/mult

And now with MULT_EXPR as well. Strangely enough, tree-vrp doesn't mention
LSHIFT_EXPR anywhere, could be worth adding it, at least for the case with a
constant shift.

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |paolo.carlini at oracle dot
                   |                            |com

--- Comment #10 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-05 13:27:43 UTC ---
Now for the testcases... ;) Seriously, I have no idea what's the "policy" about
this kind of optimization, how many testcases are normally added, in principle
if one wanted to minimally exercise every code path would be dozens, I guess.
Personally I would be more interested in knowing how many times the new code
triggers in eg, a bootstrap.

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |glisse at gcc dot gnu.org

--- Comment #11 from Marc Glisse <glisse at gcc dot gnu.org> 2012-05-05 13:29:36 UTC ---
(In reply to comment #10)
> Now for the testcases... ;)

Yes, that w

 Seriously, I have no idea what's the "policy" about
> this kind of optimization, how many testcases are normally added, in principle
> if one wanted to minimally exercise every code path would be dozens, I guess.
> Personally I would be more interested in knowing how many times the new code
> triggers in eg, a bootstrap.

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

--- Comment #12 from Marc Glisse <glisse at gcc dot gnu.org> 2012-05-05 13:43:04 UTC ---
Er, sorry, don't know what key I accidentally pressed but it apparently sent
incomplete messages :-(

(In reply to comment #10)
> Now for the testcases... ;)

Yes, that was also my reaction when I looked at the patch...

> Seriously, I have no idea what's the "policy" about
> this kind of optimization, how many testcases are normally added, in principle
> if one wanted to minimally exercise every code path would be dozens, I guess.

You can test several almost at once, but yes, that's still quite a few.
Richard's old patch has some tests, and more importantly some nice framework to
write more.

> Personally I would be more interested in knowing how many times the new code
> triggers in eg, a bootstrap.

Some of the code (the quad_* stuff, the double_int overflow checks) is only for
__int128, so not tested a lot. On the other hand, any +/-/* operation on
unsigned types (and many on signed types, because some other pass replaces them
with unsigned) exercises this code. In a first version, because of a typo, I
ended up with a bootstrap failure caused by a miscompiled gengtype that would
create files named "gt-c-family-.h" without the "c-common" part inserted...

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[rguenther at suse dot de]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

--- Comment #13 from rguenther at suse dot de <rguenther at suse dot de> 2012-05-07 08:51:06 UTC ---
On Fri, 4 May 2012, glisse at gcc dot gnu.org wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318
> 
> --- Comment #8 from glisse at gcc dot gnu.org 2012-05-04 21:45:49 UTC ---
> Created attachment 27311
>   --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27311
> Wrap plus/minus
> 
> This patch handles combinations of range/anti_range for PLUS_EXPR and
> MINUS_EXPR. I'll try to do MULT_EXPR later so that for -10<i<10 and -10<j<10 we
> get the same range for (unsigned)(i*j) and (unsigned)i*(unsigned)j.

Btw, now that I have committed the TYPE_IS_SIZETYPE changes I have
some pending VRP patches that I like to push (I'm not sure if they
covert this, I have to revisit them first).

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|paolo.carlini at oracle dot |
                   |com                         |

--- Comment #14 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-07 09:33:16 UTC ---
Thanks for the clarifications, Marc!

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

--- Comment #15 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-05-07 13:50:17 UTC ---
Looking at your second patch it looks entirely reasonable, though not
globbing MULT_EXPR together with PLUS/MINUS might be better for readability
(thus, in the end I'd like extract_range_from_binary_expr_1 to be a big
switch-case on the operation code).  I didn't finish refactoring the code
when I last touched it - the idea was to have primitives for range
arithmetic.

I've looked at my own pending patch and it doesn't look as nicely structured
as yours.

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

--- Comment #16 from Marc Glisse <glisse at gcc dot gnu.org> 2012-05-07 14:46:03 UTC ---
(In reply to comment #15)
> Looking at your second patch it looks entirely reasonable, though not
> globbing MULT_EXPR together with PLUS/MINUS might be better for readability

I wondered about that (you can still find the patch (marked as obsolete)
without MULT_EXPR in the bug report, for comparison), and thought that the
amount of code shared was more important than separating, but it isn't hard to
unshare it if you find that better ;-)

> (thus, in the end I'd like extract_range_from_binary_expr_1 to be a big
> switch-case on the operation code).

I was indeed unhappy about breaking that structure.

> I didn't finish refactoring the code when I last touched it - 
> the idea was to have primitives for range arithmetic.

Good idea. I admit that I am scared of doing changes that are not completely
local, as I don't have a global understanding of how things work, hence my very
localized patches...

> I've looked at my own pending patch and it doesn't look as nicely structured
> as yours.

At least the patch you have attached to the bug is complementary to what I
posted, and something like it is still very much needed.

What do you think is the best way forward? I am happy to let you refactor
things the way you like and adapt this patch in a few months/years if it is
still useful. I only looked at VRP in case it could help for PR53100, but that
doesn't seem so easy...

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

--- Comment #17 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-06-20 12:00:27 UTC ---
Author: rguenth
Date: Wed Jun 20 12:00:20 2012
New Revision: 188827

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=188827
Log:
2012-06-20  Richard Guenther  <rguenther@suse.de>

    PR tree-optimization/30318
    * tree-vrp.c (range_int_cst_p): Do not reject overflowed
    constants here.
    (range_int_cst_singleton_p): But explicitely here.
    (zero_nonzero_bits_from_vr): And here.
    (extract_range_from_binary_expr_1): Re-implement PLUS_EXPR
    to cover all cases we can perform arbitrary precision
    arithmetic with double-ints.
    (intersect_ranges): Handle adjacent anti-ranges.

    * gcc.dg/tree-ssa/vrp69.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp69.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vrp.c

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

--- Comment #18 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-06-20 12:05:35 UTC ---
Marc - I have now pushed all my refactorings into VRP, including the
PLUS_EXPR handling.  The basic idea was to build on simple building blocks,
a "complete" union/intersect implementation and "complete" range-range
operations.  Mixed range/anti-range and anti-range/anti-range operations
are now decomposed into several sub-operations and the results are unioned
back together.

Can you adjust your patch with the double-double_int arithmetic stuff
to that fact?  Thx.

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

--- Comment #19 from Marc Glisse <glisse at gcc dot gnu.org> 2012-06-20 19:12:22 UTC ---
(In reply to comment #18)
> I have now pushed all my refactorings into VRP,

Thanks.

> Can you adjust your patch with the double-double_int arithmetic stuff
> to that fact?

I'll look into that later in the summer (maybe August). It seems quite possible
that much less is needed now.

(note, in case, that I don't mind in the slightest if someone beats me to it).

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

--- Comment #20 from Marc Glisse <glisse at gcc dot gnu.org> 2012-07-25 18:26:18 UTC ---
Author: glisse
Date: Wed Jul 25 18:26:12 2012
New Revision: 189861

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=189861
Log:
2012-07-25 Marc Glisse <marc.glisse@inria.fr>

    PR tree-optimization/30318
    * tree-vrp.c (extract_range_from_binary_expr_1) [PLUS_EXPR]:
    Handle __int128.
    [MINUS_EXPR]: Merge with PLUS_EXPR.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-vrp.c

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #27317|0                           |1
        is obsolete|                            |

--- Comment #21 from Marc Glisse <glisse at gcc dot gnu.org> 2012-07-29 14:44:25 UTC ---
Created attachment 27885
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27885
MULT_EXPR

It still requires some double-checking, a testcase, a bootstrap+regtest, but it
seems to give sensible results.

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

--- Comment #22 from Marc Glisse <glisse at gcc dot gnu.org> 2012-08-03 12:21:25 UTC ---
Author: glisse
Date: Fri Aug  3 12:21:14 2012
New Revision: 190125

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=190125
Log:
gcc/
2012-08-03 Marc Glisse <marc.glisse@inria.fr>

    PR tree-optimization/30318
    * double-int.c (mul_double_wide_with_sign): New function.
    (mul_double_with_sign): Call the new function.
    * double-int.h (mul_double_wide_with_sign): Declare the new function.
    * tree-vrp.c (extract_range_from_binary_expr_1) [MULT_EXPR]:
    Handle integer types that wrap on overflow.
    (quad_int_cmp): New helper function.
    (quad_int_pair_sort): Likewise.


gcc/testsuite/
2012-08-03 Marc Glisse <marc.glisse@inria.fr>

    PR tree-optimization/30318
    * gcc.dg/tree-ssa/vrp77.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp77.c   (with props)
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/double-int.c
    trunk/gcc/double-int.h
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vrp.c

Propchange: trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp77.c
            ('svn:eol-style' added)

Propchange: trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp77.c
            ('svn:keywords' added)

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

--- Comment #23 from Marc Glisse <glisse at gcc dot gnu.org> 2012-08-03 12:35:40 UTC ---
I think that's it for me. Should we close the bug, or is there still something
missing?

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
      Known to work|                            |4.8.0
         Resolution|                            |FIXED

--- Comment #24 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-08-03 12:52:25 UTC ---
That's it.

[Bug tree-optimization/30318] New: VRP does not create ANIT_RANGEs on overflow

[rguenth at gcc dot gnu dot org]

VRP should, if overfow is defined, create anti-ranges if plus or minus
cause wrapping.

void test2 (unsigned int i)
{
  if (i <= 0x0fffffffa)
    {
      return;
    }
  if (i == 0x0ffffffff)
    {
      return;
    }
  {
    unsigned int v = i + 2;
    {
      if (v != 0)
        {
          if (v != 0x0ffffffff)
            {
              link_error ();
            }
        }
    }
  }
}

we should be able to optimize this.  So [UINT_MAX-4, UINT_MAX-1] + 2
is ~[1, UINT_MAX-1].

(I have a patch)


-- 
           Summary: VRP does not create ANIT_RANGEs on overflow
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
        AssignedTo: rguenth at gcc dot gnu dot org
        ReportedBy: rguenth at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2006-12-28 19:35 -------
Created an attachment (id=12845)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=12845&action=view)
preliminary patch

needs proper testing / splitting.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318

[Bug tree-optimization/30318] VRP does not create ANTI_RANGEs on overflow

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2006-12-28 20:32 -------
Doesn't seem to work.  gcc.c-torture/execute/vrp-5.c fails because
[5, +INF] + [5, +INF] is combined to [10, +INF-1] (and 5 + +INF-5 is zero
anyways).


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30318