[PR,87415] handle 1 bit bit fields in set_value_range_with_overflow()
diff mbox series

Message ID 97983076-9ed7-2b34-1ef2-5183fa9bf0d9@redhat.com
State New
Headers show
Series
  • [PR,87415] handle 1 bit bit fields in set_value_range_with_overflow()
Related show

Commit Message

Aldy Hernandez Sept. 26, 2018, 5:46 p.m. UTC
As I've said in the PR...

For a 1-bit signed field we are trying to subtract the following ranges:

    [0, 0] - VR_VARYING

Mathematically these are:

    [MAX, MAX] - [MIN, MAX]
    [0, 0] - [MIN, MAX]
=> [0, 0] - [-1, 0]

For ranges: [a, b] - [c, d] is [a - d, b - c], so combine_bounds() yields:

    [0, OVERFLOW]

Then we adjust the result for overflows in 
set_value_range_with_overflow() we transform the above into:

    [0, +INF]

And since +INF is 0, we get [0, 0] which is incorrect.

[0, 0] - [MIN, MAX] should have given [MIN, MAX].

1-bit signed fields are weird in that 0 - (-MIN) is still -MIN.  In any 
other world, it is an impossible result.  For instance, in an 8-bit 
signed world, 0 - (-128) is invalid.

One option would be to treat signed bit fields as TYPE_OVERFLOW wraps, 
since they seem to have wrapping properties, but I'm afraid such a heavy 
handed approach would yield latent bugs across the compiler.  What VRP 
seems to currently be doing in set_and_canonicalize_value_range(), is 
just special casing the wrapping of 1-bit fields:

   /* Wrong order for min and max, to swap them and the VR type we need
      to adjust them.  */
   if (tree_int_cst_lt (max, min))
     {
       tree one, tmp;

       /* For one bit precision if max < min, then the swapped
	 range covers all values, so for VR_RANGE it is varying and
	 for VR_ANTI_RANGE empty range, so drop to varying as well.  */
       if (TYPE_PRECISION (TREE_TYPE (min)) == 1)
	{
	  set_value_range_to_varying (vr);
	  return;
	}
...
     }

I've done the same in set_value_range_with_overflow().

BTW, I believe this is a latent bug.  Had the MINUS_EXPR code been 
handed down [0,0] - [-1,0] instead of [0,0] - VR_VARYING, we would've 
triggered it.

Tested on x86-64 Linux.

OK for trunk?

Comments

Richard Biener Sept. 27, 2018, 10:49 a.m. UTC | #1
On Wed, Sep 26, 2018 at 7:46 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> As I've said in the PR...
>
> For a 1-bit signed field we are trying to subtract the following ranges:
>
>     [0, 0] - VR_VARYING
>
> Mathematically these are:
>
>     [MAX, MAX] - [MIN, MAX]
>     [0, 0] - [MIN, MAX]
> => [0, 0] - [-1, 0]
>
> For ranges: [a, b] - [c, d] is [a - d, b - c], so combine_bounds() yields:
>
>     [0, OVERFLOW]
>
> Then we adjust the result for overflows in
> set_value_range_with_overflow() we transform the above into:
>
>     [0, +INF]
>
> And since +INF is 0, we get [0, 0] which is incorrect.
>
> [0, 0] - [MIN, MAX] should have given [MIN, MAX].
>
> 1-bit signed fields are weird in that 0 - (-MIN) is still -MIN.  In any
> other world, it is an impossible result.  For instance, in an 8-bit
> signed world, 0 - (-128) is invalid.

I think that set_value_range_with_overflow saturates to the wrong end, possibly
because wi::sub computes the wrong overflow?

You can't really argue that 0 - (-128) is "invalid" in any sense since
-128 might
not be represented at runtime so you cannot use overflow semantics to restrict
what is valid and what is not when doing the actual operations.

> One option would be to treat signed bit fields as TYPE_OVERFLOW wraps,
> since they seem to have wrapping properties, but I'm afraid such a heavy
> handed approach would yield latent bugs across the compiler.  What VRP
> seems to currently be doing in set_and_canonicalize_value_range(), is
> just special casing the wrapping of 1-bit fields:
>
>    /* Wrong order for min and max, to swap them and the VR type we need
>       to adjust them.  */
>    if (tree_int_cst_lt (max, min))
>      {
>        tree one, tmp;
>
>        /* For one bit precision if max < min, then the swapped
>          range covers all values, so for VR_RANGE it is varying and
>          for VR_ANTI_RANGE empty range, so drop to varying as well.  */
>        if (TYPE_PRECISION (TREE_TYPE (min)) == 1)
>         {
>           set_value_range_to_varying (vr);
>           return;
>         }
> ...
>      }
>
> I've done the same in set_value_range_with_overflow().
>
> BTW, I believe this is a latent bug.  Had the MINUS_EXPR code been
> handed down [0,0] - [-1,0] instead of [0,0] - VR_VARYING, we would've
> triggered it.
>
> Tested on x86-64 Linux.
>
> OK for trunk?

Still OK.

Thanks,
Richard.

Patch
diff mbox series

gcc/

	PR tree-optimization/87415
	* tree-vrp.c (set_value_range_with_overflow): Special case one bit
	precision fields.

diff --git a/gcc/testsuite/gcc.dg/pr87415.c b/gcc/testsuite/gcc.dg/pr87415.c
new file mode 100644
index 00000000000..473384ac479
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr87415.c
@@ -0,0 +1,20 @@ 
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+struct A
+{
+  int b:1;
+};
+
+int d;
+
+int main ()
+{
+  struct A e = { 0 };
+  if (!d)
+    e.b = -1;
+  if (!e.b)
+    __builtin_abort ();
+
+  return 0;
+}
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index f95437b3040..77fe98a62e3 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -1116,6 +1116,15 @@  set_value_range_with_overflow (value_range &vr,
   const unsigned int prec = TYPE_PRECISION (type);
   vr.type = VR_RANGE;
   vr.equiv = NULL;
+
+  /* For one bit precision if max < min, then the swapped
+     range covers all values.  */
+  if (prec == 1 && wi::lt_p (wmax, wmin, sgn))
+    {
+      set_value_range_to_varying (&vr);
+      return;
+    }
+
   if (TYPE_OVERFLOW_WRAPS (type))
     {
       /* If overflow wraps, truncate the values and adjust the