From 2118438f49f0c193abe3fa3def350a8129045746 Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Mon, 26 Oct 2020 17:50:37 +0100
Subject: [PATCH] Handle signed 1-bit ranges in irange::invert.

The problem here is we are trying to add 1 to a -1 in a signed 1-bit
field and coming up with UNDEFINED because of the overflow.

Signed 1-bits are annoying because you can't really add or subtract
one, because the one is unrepresentable.  For invert() we have a
special subtract_one() function that handles 1-bit signed fields.

This patch implements the analogous add_one() function so that invert
works.

gcc/ChangeLog:

	PR tree-optimization/97555
	* range-op.cc (range_tests): Test 1-bit signed invert.
	* value-range.cc (subtract_one): Adjust comment.
	(add_one): New.
	(irange::invert): Call add_one.

gcc/testsuite/ChangeLog:

	* gcc.dg/pr97555.c: New test.
---
 gcc/range-op.cc                | 17 +++++++++++++++--
 gcc/testsuite/gcc.dg/pr97555.c | 22 ++++++++++++++++++++++
 gcc/value-range.cc             | 23 +++++++++++++++++------
 3 files changed, 54 insertions(+), 8 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/pr97555.c

diff --git a/gcc/range-op.cc b/gcc/range-op.cc
index ee62f10..74ab2e5 100644
--- a/gcc/range-op.cc
+++ b/gcc/range-op.cc
@@ -3680,15 +3680,28 @@ range_tests ()
   // Test 1-bit signed integer union.
   // [-1,-1] U [0,0] = VARYING.
   tree one_bit_type = build_nonstandard_integer_type (1, 0);
+  tree one_bit_min = vrp_val_min (one_bit_type);
+  tree one_bit_max = vrp_val_max (one_bit_type);
   {
-    tree one_bit_min = vrp_val_min (one_bit_type);
-    tree one_bit_max = vrp_val_max (one_bit_type);
     int_range<2> min (one_bit_min, one_bit_min);
     int_range<2> max (one_bit_max, one_bit_max);
     max.union_ (min);
     ASSERT_TRUE (max.varying_p ());
   }
 
+  // Test inversion of 1-bit signed integers.
+  {
+    int_range<2> min (one_bit_min, one_bit_min);
+    int_range<2> max (one_bit_max, one_bit_max);
+    int_range<2> t;
+    t = min;
+    t.invert ();
+    ASSERT_TRUE (t == max);
+    t = max;
+    t.invert ();
+    ASSERT_TRUE (t == min);
+  }
+
   // Test that NOT(255) is [0..254] in 8-bit land.
   int_range<1> not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE);
   ASSERT_TRUE (not_255 == int_range<1> (UCHAR (0), UCHAR (254)));
diff --git a/gcc/testsuite/gcc.dg/pr97555.c b/gcc/testsuite/gcc.dg/pr97555.c
new file mode 100644
index 0000000..625bc6f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr97555.c
@@ -0,0 +1,22 @@
+// { dg-do run }
+// { dg-options "-Os" }
+
+struct {
+  int a:1;
+} b;
+
+int c, d, e, f = 1, g;
+
+int main ()
+{
+  for (; d < 3; d++) {
+    char h = 1 % f, i = ~(0 || ~0);
+    c = h;
+    f = ~b.a;
+    ~b.a | 1 ^ ~i && g;
+    if (~e)
+      i = b.a;
+    b.a = i;
+  }
+  return 0;
+}
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index 7847104..0e633c1 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -1772,19 +1772,30 @@ irange::irange_intersect (const irange &r)
     verify_range ();
 }
 
+// Signed 1-bits are strange.  You can't subtract 1, because you can't
+// represent the number 1.  This works around that for the invert routine.
+
 static wide_int inline
 subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow)
 {
-  // A signed 1-bit bit-field, has a range of [-1,0] so subtracting +1
-  // overflows, since +1 is unrepresentable.  This is why we have an
-  // addition of -1 here.
   if (TYPE_SIGN (type) == SIGNED)
-    return wi::add (x, -1 , SIGNED, &overflow);
+    return wi::add (x, -1, SIGNED, &overflow);
   else
     return wi::sub (x, 1, UNSIGNED, &overflow);
 }
 
-/* Return the inverse of a range.  */
+// The analogous function for adding 1.
+
+static wide_int inline
+add_one (const wide_int &x, tree type, wi::overflow_type &overflow)
+{
+  if (TYPE_SIGN (type) == SIGNED)
+    return wi::sub (x, -1, SIGNED, &overflow);
+  else
+    return wi::add (x, 1, UNSIGNED, &overflow);
+}
+
+// Return the inverse of a range.
 
 void
 irange::invert ()
@@ -1881,7 +1892,7 @@ irange::invert ()
   // set the overflow bit.
   if (type_max != wi::to_wide (orig_range.m_base[i]))
     {
-      tmp = wi::add (wi::to_wide (orig_range.m_base[i]), 1, sign, &ovf);
+      tmp = add_one (wi::to_wide (orig_range.m_base[i]), ttype, ovf);
       m_base[nitems++] = wide_int_to_tree (ttype, tmp);
       m_base[nitems++] = wide_int_to_tree (ttype, type_max);
       if (ovf)
-- 
2.7.4