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

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.
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. | #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

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