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)
Created attachment 12845 [details] preliminary patch needs proper testing / splitting.
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).
Confirmed.
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
Created attachment 27260 [details] 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.
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 [details] > --> 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.
(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).
Created attachment 27311 [details] 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.
Created attachment 27317 [details] 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.
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.
(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.
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...
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 [details] > --> 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).
Thanks for the clarifications, Marc!
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.
(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...
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
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.
(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).
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
Created attachment 27885 [details] MULT_EXPR It still requires some double-checking, a testcase, a bootstrap+regtest, but it seems to give sensible results.
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)
I think that's it for me. Should we close the bug, or is there still something missing?
That's it.