[patch] canonicalize unsigned [1,MAX] ranges into ~[0,0]

[Aldy Hernandez <aldyh@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 1159 bytes --]

When I did the value_range canonicalization work, I noticed that an 
unsigned [1,MAX] and an ~[0,0] could be two different representations 
for the same thing.  I didn't address the problem then because callers 
to ranges_from_anti_range() would go into an infinite loop trying to 
extract ~[0,0] into [1,MAX] and [].  We had a lot of callers to 
ranges_from_anti_range, and it smelled like a rat's nest, so I bailed.

Now that we have one main caller (from the symbolic PLUS/MINUS 
handling), it's a lot easier to contain.  Well, singleton_p also calls 
it, but it's already handling nonzero specially, so it wouldn't be affected.

With some upcoming cleanups I'm about to post, the fact that [1,MAX] and 
~[0,0] are equal_p(), but not nonzero_p(), matters.  Plus, it's just 
good form to have one representation, giving us the ability to pick at 
nonzero_p ranges with ease.

The code in extract_range_from_plus_minus_expr() continues to be a mess 
(as it has always been), but at least it's contained, and with this 
patch, it's slightly smaller.

Note, I'm avoiding adding a comment header for functions with highly 
descriptive obvious names.

OK?

Aldy

[-- Attachment #2: canonicalize-nonzero-ranges.patch --]
[-- Type: text/x-patch, Size: 7733 bytes --]

commit 1c333730deeb4ddadc46ad6d12d5344f92c0352c
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Fri Oct 4 08:51:25 2019 +0200

    Canonicalize UNSIGNED [1,MAX] into ~[0,0].
    
    Adapt PLUS/MINUS symbolic handling, so it doesn't call
    ranges_from_anti_range with a VR_ANTI_RANGE containing one sub-range.

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 6e4f145af46..3934b41fdf9 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,18 @@
+2019-10-04  Aldy Hernandez  <aldyh@redhat.com>
+
+	* tree-vrp.c (value_range_base::singleton_p): Use num_pairs
+	instead of calling vrp_val_is_*.
+	(value_range_base::set): Canonicalize unsigned [1,MAX] into
+	non-zero.
+	(range_has_numeric_bounds_p): New.
+	(range_int_cst_p): Use range_has_numeric_bounds_p.
+	(ranges_from_anti_range): Assert that we won't recurse
+	indefinitely.
+	(extract_extremes_from_range): New.
+	(extract_range_from_plus_minus_expr): Adapt so we don't call
+	ranges_from_anti_range with an anti-range containing only one
+	sub-range.
+
 2019-10-04  Aldy Hernandez  <aldyh@redhat.com>
 
 	(value_range_from_overflowed_bounds): Rename from
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index a2ab4a21925..97dd2b7a734 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -379,10 +379,7 @@ value_range_base::singleton_p (tree *result) const
 	    }
 	  return false;
 	}
-
-      /* An anti-range that includes an extreme, is just a range with
-	 one sub-range.  Use the one sub-range.  */
-      if (vrp_val_is_min (m_min, true) || vrp_val_is_max (m_max, true))
+      if (num_pairs () == 1)
 	{
 	  value_range_base vr0, vr1;
 	  ranges_from_anti_range (this, &vr0, &vr1, true);
@@ -843,6 +840,17 @@ value_range_base::set (enum value_range_kind kind, tree min, tree max)
       return;
     }
 
+  /* Unsigned [1, MAX] is canonicalized as ~[0, 0].  */
+  if (kind == VR_RANGE && TYPE_UNSIGNED (type)
+      && prec > 1
+      && wi::eq_p (wi::to_wide (min), wi::one (prec))
+      && wi::eq_p (wi::to_wide (max), wi::max_value (prec, sign)))
+    {
+      m_kind = VR_ANTI_RANGE;
+      m_min = m_max = build_int_cst (type, 0);
+      return;
+    }
+
   /* Do not drop [-INF(OVF), +INF(OVF)] to varying.  (OVF) has to be sticky
      to make sure VRP iteration terminates, otherwise we can get into
      oscillations.  */
@@ -913,15 +921,21 @@ vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2)
 	      && bitmap_equal_p (b1, b2)));
 }
 
+static bool
+range_has_numeric_bounds_p (const value_range_base *vr)
+{
+  return (vr->min ()
+	  && TREE_CODE (vr->min ()) == INTEGER_CST
+	  && TREE_CODE (vr->max ()) == INTEGER_CST);
+}
+
 /* Return true if max and min of VR are INTEGER_CST.  It's not necessary
    a singleton.  */
 
 bool
 range_int_cst_p (const value_range_base *vr)
 {
-  return (vr->kind () == VR_RANGE
-	  && TREE_CODE (vr->min ()) == INTEGER_CST
-	  && TREE_CODE (vr->max ()) == INTEGER_CST);
+  return (vr->kind () == VR_RANGE && range_has_numeric_bounds_p (vr));
 }
 
 /* Return true if VR is a INTEGER_CST singleton.  */
@@ -1327,6 +1341,10 @@ ranges_from_anti_range (const value_range_base *ar,
 			value_range_base *vr0, value_range_base *vr1,
 			bool handle_pointers)
 {
+  /* An unsigned ~[0,0] cannot be split into [1,MAX] because it gets
+     normalized back into ~[0,0].  Avoid infinite loop.  */
+  gcc_checking_assert (!ar->nonzero_p () || !TYPE_UNSIGNED (ar->type ()));
+
   tree type = ar->type ();
 
   vr0->set_undefined ();
@@ -1582,6 +1600,22 @@ extract_range_from_pointer_plus_expr (value_range_base *vr,
     vr->set_varying (expr_type);
 }
 
+static void
+extract_extremes_from_range (const value_range_base *vr, tree *min, tree *max)
+{
+  if (range_has_numeric_bounds_p (vr))
+    {
+      *min = wide_int_to_tree (vr->type (), vr->lower_bound ());
+      *max = wide_int_to_tree (vr->type (), vr->upper_bound ());
+    }
+  else
+    {
+      gcc_checking_assert (vr->kind () != VR_ANTI_RANGE);
+      *min = vr->min ();
+      *max = vr->max ();
+    }
+}
+
 /* Extract range information from a PLUS/MINUS_EXPR and store the
    result in *VR.  */
 
@@ -1597,9 +1631,18 @@ extract_range_from_plus_minus_expr (value_range_base *vr,
   value_range_base vr0 = *vr0_, vr1 = *vr1_;
   value_range_base vrtem0, vrtem1;
 
+  /* We can't do anything with symbolic anti ranges.  */
+  if ((vr0.kind () == VR_ANTI_RANGE && !range_has_numeric_bounds_p (&vr0))
+      || (vr1.kind () == VR_ANTI_RANGE && !range_has_numeric_bounds_p (&vr1)))
+    {
+      vr->set_varying (expr_type);
+      return;
+    }
+
   /* Now canonicalize anti-ranges to ranges when they are not symbolic
      and express ~[] op X as ([]' op X) U ([]'' op X).  */
   if (vr0.kind () == VR_ANTI_RANGE
+      && vr0.num_pairs () == 2
       && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1))
     {
       extract_range_from_plus_minus_expr (vr, code, expr_type, &vrtem0, vr1_);
@@ -1614,6 +1657,7 @@ extract_range_from_plus_minus_expr (value_range_base *vr,
     }
   /* Likewise for X op ~[].  */
   if (vr1.kind () == VR_ANTI_RANGE
+      && vr1.num_pairs () == 2
       && ranges_from_anti_range (&vr1, &vrtem0, &vrtem1))
     {
       extract_range_from_plus_minus_expr (vr, code, expr_type, vr0_, &vrtem0);
@@ -1628,26 +1672,10 @@ extract_range_from_plus_minus_expr (value_range_base *vr,
     }
 
   value_range_kind kind;
-  value_range_kind vr0_kind = vr0.kind (), vr1_kind = vr1.kind ();
-  tree vr0_min = vr0.min (), vr0_max = vr0.max ();
-  tree vr1_min = vr1.min (), vr1_max = vr1.max ();
   tree min = NULL, max = NULL;
-
-  /* This will normalize things such that calculating
-     [0,0] - VR_VARYING is not dropped to varying, but is
-     calculated as [MIN+1, MAX].  */
-  if (vr0.varying_p ())
-    {
-      vr0_kind = VR_RANGE;
-      vr0_min = vrp_val_min (expr_type);
-      vr0_max = vrp_val_max (expr_type);
-    }
-  if (vr1.varying_p ())
-    {
-      vr1_kind = VR_RANGE;
-      vr1_min = vrp_val_min (expr_type);
-      vr1_max = vrp_val_max (expr_type);
-    }
+  tree vr0_min, vr0_max, vr1_min, vr1_max;
+  extract_extremes_from_range (&vr0, &vr0_min, &vr0_max);
+  extract_extremes_from_range (&vr1, &vr1_min, &vr1_max);
 
   const bool minus_p = (code == MINUS_EXPR);
   tree min_op0 = vr0_min;
@@ -1666,10 +1694,9 @@ extract_range_from_plus_minus_expr (value_range_base *vr,
      single-symbolic ranges, try to compute the precise resulting range,
      but only if we know that this resulting range will also be constant
      or single-symbolic.  */
-  if (vr0_kind == VR_RANGE && vr1_kind == VR_RANGE
-      && (TREE_CODE (min_op0) == INTEGER_CST
-	  || (sym_min_op0
-	      = get_single_symbol (min_op0, &neg_min_op0, &min_op0)))
+  if ((TREE_CODE (min_op0) == INTEGER_CST
+       || (sym_min_op0
+	   = get_single_symbol (min_op0, &neg_min_op0, &min_op0)))
       && (TREE_CODE (min_op1) == INTEGER_CST
 	  || (sym_min_op1
 	      = get_single_symbol (min_op1, &neg_min_op1, &min_op1)))
@@ -1724,18 +1751,6 @@ extract_range_from_plus_minus_expr (value_range_base *vr,
     }
   else
     {
-      /* For other cases, for example if we have a PLUS_EXPR with two
-	 VR_ANTI_RANGEs, drop to VR_VARYING.  It would take more effort
-	 to compute a precise range for such a case.
-	 ???  General even mixed range kind operations can be expressed
-	 by for example transforming ~[3, 5] + [1, 2] to range-only
-	 operations and a union primitive:
-	 [-INF, 2] + [1, 2]  U  [5, +INF] + [1, 2]
-	 [-INF+1, 4]     U    [6, +INF(OVF)]
-	 though usually the union is not exactly representable with
-	 a single range or anti-range as the above is
-	 [-INF+1, +INF(OVF)] intersected with ~[5, 5]
-	 but one could use a scheme similar to equivalences for this. */
       vr->set_varying (expr_type);
       return;
     }