Bug 84321 - [8 Regression] ice in intersect_range_with_nonzero_bits, at tree-vrp.c:213
Summary: [8 Regression] ice in intersect_range_with_nonzero_bits, at tree-vrp.c:213
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 8.0
: P1 critical
Target Milestone: 8.0
Assignee: rsandifo@gcc.gnu.org
URL:
Keywords: ice-on-valid-code
Depends on:
Blocks:
 
Reported: 2018-02-11 12:17 UTC by David Binderman
Modified: 2018-02-13 22:42 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2018-02-12 00:00:00


Attachments
C source code (97.45 KB, text/plain)
2018-02-11 12:17 UTC, David Binderman
Details

Note You need to log in before you can comment on or make changes to this bug.
Description David Binderman 2018-02-11 12:17:54 UTC
Created attachment 43391 [details]
C source code

For the attached code, on recent gcc trunk, with compiler flags -O3 and -fwrapv,
does this:

src/client/refresh/files/stb_image.h:2815:17: internal compiler error: in intersect_range_with_nonzero_bits, at tree-vrp.c:213
0x6b5d59 intersect_range_with_nonzero_bits(value_range_type, generic_wide_int<wide_int_storage>*, generic_wide_int<wide_int_storage>*, generic_wide_int<wide_int_storage> const&, signop)
	../../trunk/gcc/tree-vrp.c:213
0x18f51c0 split_constant_offset_1
	../../trunk/gcc/tree-data-ref.c:728
0x18f55a6 split_constant_offset(tree_node*, tree_node**, tree_node**)
	../../trunk/gcc/tree-data-ref.c:782
0x18f4e34 split_constant_offset_1
	../../trunk/gcc/tree-data-ref.c:617

I will have my usual go at reducing the code and finding a range 
of revisions for the problem.
Comment 1 David Binderman 2018-02-11 12:37:16 UTC
Reduced code:

*a;
b, c;
d() {
  int e = 0;
  if (b == 1)
    return;
  for (; e < (b & ~7); e += 8)
    ;
  for (++e; e < b;)
    c = a[e];
}

The problem seems to occur between revisions 257477 and 257519.
Comment 2 David Binderman 2018-02-11 12:40:29 UTC
svn blame produced this for tree-vrp.c:213

257491   rsandifo       gcc_checking_assert (wi::le_p (*min, *max, sgn));
Comment 3 Andrew Pinski 2018-02-12 08:26:15 UTC
(In reply to David Binderman from comment #2)
> svn blame produced this for tree-vrp.c:213
> 
> 257491   rsandifo       gcc_checking_assert (wi::le_p (*min, *max, sgn));

r257491
Comment 4 Jakub Jelinek 2018-02-12 10:03:36 UTC
Less reduced testcase so that it is valid:

int c;

void
foo (int *a, int b)
{
  int e;
  if (b == 1)
    return -1;
  for (e = 0; e < (b & ~7); e += 8)
    ;
  for (++e; e < b;)
    c = a[e];
}

This is because the range info and nonzero bits improvements improve just gradually and improvements on nonzero bits don't have immediate effect on the min/max.
We initially have:
  # RANGE [-2147483648, 2147483647] NONZERO 4294967288
  # e_11 = PHI <e_6(4)>
  # RANGE [-2147483648, 2147483647] NONZERO 4294967289
  e_13 = e_11 + 1;
i.e. basically all range, but 0xfffffff8 and 0xfffffff9 masks.
Then vrp1 improves that to:
  # RANGE [0, 2147483647] NONZERO 2147483640
  # e_11 = PHI <e_6(4)>
  # RANGE ~[-2147483647, 0] NONZERO 4294967289
  e_13 = e_11 + 1;
which is conservatively correct, but not perfect, because of the 0x7fffffff8
nonzero mask on the PHI guarantees that the actual range must be
[0, 2147483640].  And because e_11 is never INT_MAX, e_11 + 1 will never be INT_MIN.  Later on ccp3 improves it further:
  # RANGE [0, 2147483647] NONZERO 2147483640
  # e_18 = PHI <e_12(4), 0(3)>
  # RANGE ~[-2147483647, 0] NONZERO 2147483641
  e_13 = e_18 + 1;
but just the nonzero mask.
So, while it would be nice to optimize this better, the asserts in intersect_range_with_nonzero_bits are just wrong, just punt (return VR_UNDEFINED) in those cases.
Comment 5 Jakub Jelinek 2018-02-12 10:24:05 UTC
Note, we have in set_range_info_raw:
  /* If it is a range, try to improve nonzero_bits from the min/max.  */
  if (range_type == VR_RANGE)
    {
      wide_int xorv = ri->get_min () ^ ri->get_max ();
      if (xorv != 0)
        xorv = wi::mask (precision - wi::clz (xorv), false, precision);
      ri->set_nonzero_bits (ri->get_nonzero_bits () & (ri->get_min () | xorv));
    }
but don't have anything similar for VR_ANTI_RANGE (that is ok) and don't have anything similar in set_nonzero_bits.
Comment 6 rsandifo@gcc.gnu.org 2018-02-12 10:29:57 UTC
This should become a VR_RANGE rather than drop to VR_UNDEFINED.
Comment 7 Jakub Jelinek 2018-02-12 10:33:30 UTC
int c;

void
foo (int *a, int b)
{
  int e;
  if (b == 1)
    return;
  for (e = 0; e < (b & ~7); e += 8)
    ;
  for (++e; e < b;)
    c = a[e];
}

actually.
Comment 8 Jakub Jelinek 2018-02-12 10:34:16 UTC
This seems to fix it.  But as I said, the asserts still need to go.

--- gcc/tree-ssanames.c.jj	2018-01-30 12:30:27.678359900 +0100
+++ gcc/tree-ssanames.c	2018-02-12 11:32:51.768829381 +0100
@@ -464,6 +464,21 @@ set_nonzero_bits (tree name, const wide_
     }
   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
   ri->set_nonzero_bits (mask);
+  /* If it is a range, try to improve min/max from nonzero_bits.  */
+  if (SSA_NAME_RANGE_TYPE (name) == VR_RANGE)
+    {
+      wide_int msk = ri->get_nonzero_bits ();
+      wide_int min = wi::round_up_for_mask (ri->get_min (), msk);
+      wide_int max = wi::round_down_for_mask (ri->get_max (), msk);
+      signop sgn = TYPE_SIGN (TREE_TYPE (name));
+      if (wi::le_p (min, max, sgn)
+	  && wi::le_p (min, ri->get_max (), sgn)
+	  && wi::le_p (ri->get_min (), max, sgn))
+	{
+	  ri->set_min (min);
+	  ri->set_max (max);
+	}
+    }
 }
 
 /* Return a widest_int with potentially non-zero bits in SSA_NAME
Comment 9 Jakub Jelinek 2018-02-12 10:35:18 UTC
Perhaps we can handle anti range similarly and then not to intersect_range_with_nonzero_bits at all.
Comment 10 rsandifo@gcc.gnu.org 2018-02-12 10:48:56 UTC
(In reply to Jakub Jelinek from comment #8)
> This seems to fix it.  But as I said, the asserts still need to go.
> 
> --- gcc/tree-ssanames.c.jj	2018-01-30 12:30:27.678359900 +0100
> +++ gcc/tree-ssanames.c	2018-02-12 11:32:51.768829381 +0100
> @@ -464,6 +464,21 @@ set_nonzero_bits (tree name, const wide_
>      }
>    range_info_def *ri = SSA_NAME_RANGE_INFO (name);
>    ri->set_nonzero_bits (mask);
> +  /* If it is a range, try to improve min/max from nonzero_bits.  */
> +  if (SSA_NAME_RANGE_TYPE (name) == VR_RANGE)
> +    {
> +      wide_int msk = ri->get_nonzero_bits ();
> +      wide_int min = wi::round_up_for_mask (ri->get_min (), msk);
> +      wide_int max = wi::round_down_for_mask (ri->get_max (), msk);
> +      signop sgn = TYPE_SIGN (TREE_TYPE (name));
> +      if (wi::le_p (min, max, sgn)
> +	  && wi::le_p (min, ri->get_max (), sgn)
> +	  && wi::le_p (ri->get_min (), max, sgn))
> +	{
> +	  ri->set_min (min);
> +	  ri->set_max (max);
> +	}
> +    }
>  }
>  
>  /* Return a widest_int with potentially non-zero bits in SSA_NAME

I'd tried doing this in set_nonzero_bits first, before adding intersect_range_with_nonzero_bits.  See https://gcc.gnu.org/ml/gcc-patches/2018-02/msg00095.html for why it didn't work.
Comment 11 Jakub Jelinek 2018-02-12 11:22:41 UTC
(In reply to rsandifo@gcc.gnu.org from comment #10)
> I'd tried doing this in set_nonzero_bits first, before adding
> intersect_range_with_nonzero_bits.  See
> https://gcc.gnu.org/ml/gcc-patches/2018-02/msg00095.html for why it didn't
> work.

IMHO that is a risk of all the VRP changes that some case will regress, the more important question is how much it will help in general, and I think it would.
If it is only done in this special case, other passes can't benefit from the more accurate range info.
That said, such a change is likely inappropriate for stage4 at this point.
Comment 12 rsandifo@gcc.gnu.org 2018-02-12 11:45:44 UTC
(In reply to Jakub Jelinek from comment #11)
> (In reply to rsandifo@gcc.gnu.org from comment #10)
> > I'd tried doing this in set_nonzero_bits first, before adding
> > intersect_range_with_nonzero_bits.  See
> > https://gcc.gnu.org/ml/gcc-patches/2018-02/msg00095.html for why it didn't
> > work.
> 
> IMHO that is a risk of all the VRP changes that some case will regress, the
> more important question is how much it will help in general, and I think it
> would.

Yeah I'd hoped so too, but...

> If it is only done in this special case, other passes can't benefit from the
> more accurate range info.

...when I did a comparison of the testsuite assembly output on a range
of targets, I didn't find any examples of things benefiting outside of
split_constant_offset, but quite a few regressions caused by trying
to interesect a VR_ANTI_RANGE with a reduced VR_RANGE.

The testsuite isn't the most representative codebase around, but still,
it suggests that we'd need to add some special cases elsewhere to
compensate.
Comment 13 rsandifo@gcc.gnu.org 2018-02-12 11:55:54 UTC
Testing a patch.  The VR_ANTI_RANGE code was wrong in a few ways. :-(
Comment 14 Jeffrey A. Law 2018-02-13 15:49:13 UTC
Author: law
Date: Tue Feb 13 15:48:38 2018
New Revision: 257629

URL: https://gcc.gnu.org/viewcvs?rev=257629&root=gcc&view=rev
Log:
2018-02-12  Richard Sandiford  <richard.sandiford@linaro.org>

gcc/
	PR tree-optimization/84321
	* tree-vrp.c (intersect_range_with_nonzero_bits): Fix VR_ANTI_RANGE
	handling.  Also check whether the anti-range contains any values
	that satisfy the mask; switch to a VR_RANGE if not.

gcc/testsuite/
	PR tree-optimization/84321
	* gcc.dg/pr84321.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/pr84321.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vrp.c
Comment 15 Jeffrey A. Law 2018-02-13 22:42:19 UTC
Fixed by Richard's change on the trunk.