Bug 30317 - VRP cannot extract a range from (unsigned int) i + 0x0ffffffff > 4
Summary: VRP cannot extract a range from (unsigned int) i + 0x0ffffffff > 4
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.3.0
: P3 normal
Target Milestone: 4.4.0
Assignee: Richard Biener
Keywords: missed-optimization
: 41477 (view as bug list)
Depends on:
Blocks: 31178 30911 34793
  Show dependency treegraph
Reported: 2006-12-28 12:22 UTC by Richard Biener
Modified: 2009-09-26 18:22 UTC (History)
2 users (show)

See Also:
Known to work: 4.4.0
Known to fail: 4.3.0
Last reconfirmed: 2007-01-20 13:45:05

patch (2.87 KB, patch)
2007-01-21 22:44 UTC, Richard Biener
Details | Diff
alternate patch (4.04 KB, patch)
2007-02-06 10:08 UTC, Richard Biener
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Richard Biener 2006-12-28 12:22:36 UTC
fold and VRP interact badly if we have a range test like

if (i > 0 && i <=5)

as we fold that to

if ((unsigned int) i + 0x0ffffffff > 4)

for which VRP fails to extract a range for i.  If we write the
range test so that fold doesn't see it, VRP is happy:

if (i > 0)
  if (i <= 5)
Comment 1 Andrew Pinski 2006-12-28 16:03:26 UTC
I think the range folding should late in compiling after VRP2 happens.  This will also help out code that is written like:
if (i > 0)
  if (i <= 5)
Comment 2 Richard Biener 2007-01-20 13:45:05 UTC
I teached VRP to look for this idiom and during a C only bootstrap on i686 this triggers 28921 times.
Comment 3 Richard Biener 2007-01-21 22:44:39 UTC
Created attachment 12929 [details]

This is what I currently have for this - it fails to bootstrap because it miscompares.  A variant without the support for the anti-range tests

  if (a < 1 || a > 5)


  if ((unsigned)a - 1 > 4)

bootstraps and tests ok, but the above adds useful things, so...

I guess the hunk in extract_range_from_assert may do the wrong thing
in some cases, but I didn't find a testcase for it.
Comment 4 Richard Biener 2007-02-06 10:08:55 UTC
Created attachment 13013 [details]
alternate patch

This patch tackes the issue by allowing

  a_2 = ASSERT_EXRP <a_1, (unsigned)a_1 + 5 <= 10>

(and similar expressions).  A variant of this patch which had not undergone
a last-minute cosmetic cleanup survivied all-languages bootstrap and regtest
on x86_64-unknown-linux-gnu.
Comment 5 Richard Biener 2008-03-28 12:21:01 UTC
Subject: Bug 30317

Author: rguenth
Date: Fri Mar 28 12:20:09 2008
New Revision: 133680

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=133680
2008-03-28  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/30317
	PR tree-optimization/30911
	PR tree-optimization/34793
	* tree-vrp.c (set_and_canonicalize_value_range): New function.
	(struct assert_locus_d): New member EXPR.
	(register_new_assert_for): Add EXPR parameter to support
	ASSERT_EXPR <name, expr OP limit>.
	(register_edge_assert_for_1): Adjust callers.
	(find_assert_locations): Likewise.
	(process_assert_insertions_for): Build condition from
	(extract_range_from_assert): Handle ASSERT_EXPRs
	of the form ASSERT_EXPR <name, expr OP limit>.
	(register_edge_assert_for_2): New helper registering
	asserts for comparisons.  Recognize range tests of the form
	(unsigned)i - CST1 OP CST2.
	(register_edge_assert_for_1): Use it.
	(register_edge_assert_for): Likewise.
	* tree.def (ASSERT_EXPR): Document extra allowed conditional
	(needs_overflow_infinity): Integer sub-types
	do not need overflow infinities.
	(vrp_val_is_max): The extreme values of integer sub-types
	are those of the base type.
	(vrp_val_is_min): Likewise.

	* gcc.dg/tree-ssa/vrp35.c: New testcase.
	* gcc.dg/tree-ssa/vrp36.c: Likewise.
	* gcc.dg/tree-ssa/vrp37.c: Likewise.


Comment 6 Richard Biener 2008-03-28 12:56:53 UTC
Comment 7 Andrew Pinski 2009-09-26 18:22:02 UTC
*** Bug 41477 has been marked as a duplicate of this bug. ***