enforce canonicalization of value_range's

enforce canonicalization of value_range's

[Aldy Hernandez]

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

This is a ping of:

https://gcc.gnu.org/ml/gcc-patches/2019-07/msg00008.html

I have addressed the comments Jeff mentioned there.

This patch goes before the VR_VARYING + types patch, but I can adapt 
either one to come first.  I can even munge them together into one 
patch, if it helps review.

Tested on x86-64 Linux.

OK (assuming ChangeLog entries)?

Aldy


[-- Attachment #2: curr.patch --]
[-- Type: text/x-patch, Size: 22963 bytes --]

commit ea908bdbfc8cdb4bb63e7d42630d01203edbac41
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Mon Jul 15 18:09:27 2019 +0200

    Enforce canonicalization in value_range.

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 594ee9adc17..de2f39d8487 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -69,23 +69,20 @@ along with GCC; see the file COPYING3.  If not see
 #include "builtins.h"
 #include "wide-int-range.h"
 
+static bool
+ranges_from_anti_range (const value_range_base *ar,
+			value_range_base *vr0, value_range_base *vr1,
+			bool handle_pointers = false);
+
 /* Set of SSA names found live during the RPO traversal of the function
    for still active basic-blocks.  */
 static sbitmap *live;
 
-void
-value_range_base::set (enum value_range_kind kind, tree min, tree max)
-{
-  m_kind = kind;
-  m_min = min;
-  m_max = max;
-  if (flag_checking)
-    check ();
-}
-
 void
 value_range::set_equiv (bitmap equiv)
 {
+  if (undefined_p () || varying_p ())
+    equiv = NULL;
   /* Since updating the equivalence set involves deep copying the
      bitmaps, only do it if absolutely necessary.
 
@@ -261,7 +258,8 @@ value_range_base::constant_p () const
 void
 value_range_base::set_undefined ()
 {
-  set (VR_UNDEFINED, NULL, NULL);
+  m_kind = VR_UNDEFINED;
+  m_min = m_max = NULL;
 }
 
 void
@@ -273,7 +271,8 @@ value_range::set_undefined ()
 void
 value_range_base::set_varying ()
 {
-  set (VR_VARYING, NULL, NULL);
+  m_kind = VR_VARYING;
+  m_min = m_max = NULL;
 }
 
 void
@@ -324,6 +323,24 @@ value_range::equiv_add (const_tree var,
 bool
 value_range_base::singleton_p (tree *result) const
 {
+  if (m_kind == VR_ANTI_RANGE)
+    {
+      if (nonzero_p ())
+	{
+	  if (TYPE_PRECISION (type ()) == 1)
+	    {
+	      if (result)
+		*result = m_max;
+	      return true;
+	    }
+	  return false;
+	}
+
+      value_range_base vr0, vr1;
+      return (ranges_from_anti_range (this, &vr0, &vr1, true)
+	      && vr1.undefined_p ()
+	      && vr0.singleton_p (result));
+    }
   if (m_kind == VR_RANGE
       && vrp_operand_equal_p (min (), max ())
       && is_gimple_min_invariant (min ()))
@@ -499,23 +516,28 @@ static assert_locus **asserts_for;
 /* Return the maximum value for TYPE.  */
 
 tree
-vrp_val_max (const_tree type)
+vrp_val_max (const_tree type, bool handle_pointers)
 {
-  if (!INTEGRAL_TYPE_P (type))
-    return NULL_TREE;
-
-  return TYPE_MAX_VALUE (type);
+  if (INTEGRAL_TYPE_P (type))
+    return TYPE_MAX_VALUE (type);
+  if (POINTER_TYPE_P (type) && handle_pointers)
+    {
+      wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
+      return wide_int_to_tree (const_cast<tree> (type), max);
+    }
+  return NULL_TREE;
 }
 
 /* Return the minimum value for TYPE.  */
 
 tree
-vrp_val_min (const_tree type)
+vrp_val_min (const_tree type, bool handle_pointers)
 {
-  if (!INTEGRAL_TYPE_P (type))
-    return NULL_TREE;
-
-  return TYPE_MIN_VALUE (type);
+  if (INTEGRAL_TYPE_P (type))
+    return TYPE_MIN_VALUE (type);
+  if (POINTER_TYPE_P (type) && handle_pointers)
+    return build_zero_cst (const_cast<tree> (type));
+  return NULL_TREE;
 }
 
 /* Return whether VAL is equal to the maximum value of its type.
@@ -626,8 +648,7 @@ intersect_range_with_nonzero_bits (enum value_range_kind vr_type,
    extract ranges from var + CST op limit.  */
 
 void
-value_range_base::set_and_canonicalize (enum value_range_kind kind,
-					tree min, tree max)
+value_range_base::set (enum value_range_kind kind, tree min, tree max)
 {
   /* Use the canonical setters for VR_UNDEFINED and VR_VARYING.  */
   if (kind == VR_UNDEFINED)
@@ -645,7 +666,9 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind,
   if (TREE_CODE (min) != INTEGER_CST
       || TREE_CODE (max) != INTEGER_CST)
     {
-      set (kind, min, max);
+      m_kind = kind;
+      m_min = min;
+      m_max = max;
       return;
     }
 
@@ -681,12 +704,13 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind,
       kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
     }
 
+  tree type = TREE_TYPE (min);
+
   /* Anti-ranges that can be represented as ranges should be so.  */
   if (kind == VR_ANTI_RANGE)
     {
       /* For -fstrict-enums we may receive out-of-range ranges so consider
          values < -INF and values > INF as -INF/INF as well.  */
-      tree type = TREE_TYPE (min);
       bool is_min = (INTEGRAL_TYPE_P (type)
 		     && tree_int_cst_compare (min, TYPE_MIN_VALUE (type)) <= 0);
       bool is_max = (INTEGRAL_TYPE_P (type)
@@ -729,22 +753,37 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind,
         }
     }
 
+  /* Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED.
+
+     Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
+     restrict those to a subset of what actually fits in the type.
+     Instead use the extremes of the type precision which will allow
+     compare_range_with_value() to check if a value is inside a range,
+     whereas if we used TYPE_*_VAL, said function would just punt
+     upon seeing a VARYING.  */
+  unsigned prec = TYPE_PRECISION (type);
+  signop sign = TYPE_SIGN (type);
+  if (wi::eq_p (wi::to_wide (min), wi::min_value (prec, sign))
+      && wi::eq_p (wi::to_wide (max), wi::max_value (prec, sign)))
+    {
+      if (kind == VR_RANGE)
+	set_varying ();
+      else if (kind == VR_ANTI_RANGE)
+	set_undefined ();
+      else
+	gcc_unreachable ();
+      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.  */
 
-  set (kind, min, max);
-}
-
-void
-value_range::set_and_canonicalize (enum value_range_kind kind,
-				   tree min, tree max, bitmap equiv)
-{
-  value_range_base::set_and_canonicalize (kind, min, max);
-  if (this->kind () == VR_RANGE || this->kind () == VR_ANTI_RANGE)
-    set_equiv (equiv);
-  else
-    equiv_clear ();
+  m_kind = kind;
+  m_min = min;
+  m_max = max;
+  if (flag_checking)
+    check ();
 }
 
 void
@@ -1174,7 +1213,8 @@ vrp_set_zero_nonzero_bits (const tree expr_type,
 
 static bool
 ranges_from_anti_range (const value_range_base *ar,
-			value_range_base *vr0, value_range_base *vr1)
+			value_range_base *vr0, value_range_base *vr1,
+			bool handle_pointers)
 {
   tree type = ar->type ();
 
@@ -1187,18 +1227,18 @@ ranges_from_anti_range (const value_range_base *ar,
   if (ar->kind () != VR_ANTI_RANGE
       || TREE_CODE (ar->min ()) != INTEGER_CST
       || TREE_CODE (ar->max ()) != INTEGER_CST
-      || !vrp_val_min (type)
-      || !vrp_val_max (type))
+      || !vrp_val_min (type, handle_pointers)
+      || !vrp_val_max (type, handle_pointers))
     return false;
 
-  if (tree_int_cst_lt (vrp_val_min (type), ar->min ()))
+  if (tree_int_cst_lt (vrp_val_min (type, handle_pointers), ar->min ()))
     vr0->set (VR_RANGE,
-	      vrp_val_min (type),
+	      vrp_val_min (type, handle_pointers),
 	      wide_int_to_tree (type, wi::to_wide (ar->min ()) - 1));
-  if (tree_int_cst_lt (ar->max (), vrp_val_max (type)))
+  if (tree_int_cst_lt (ar->max (), vrp_val_max (type, handle_pointers)))
     vr1->set (VR_RANGE,
 	      wide_int_to_tree (type, wi::to_wide (ar->max ()) + 1),
-	      vrp_val_max (type));
+	      vrp_val_max (type, handle_pointers));
   if (vr0->undefined_p ())
     {
       *vr0 = *vr1;
@@ -1209,21 +1249,20 @@ ranges_from_anti_range (const value_range_base *ar,
 }
 
 /* Extract the components of a value range into a pair of wide ints in
-   [WMIN, WMAX].
-
-   If the value range is anything but a VR_*RANGE of constants, the
-   resulting wide ints are set to [-MIN, +MAX] for the type.  */
+   [WMIN, WMAX], after having normalized any symbolics from the input.  */
 
 static void inline
-extract_range_into_wide_ints (const value_range_base *vr,
-			      signop sign, unsigned prec,
-			      wide_int &wmin, wide_int &wmax)
+extract_range_into_wide_ints (const value_range_base *vr_,
+			      tree type, wide_int &wmin, wide_int &wmax)
 {
-  gcc_assert (vr->kind () != VR_ANTI_RANGE || vr->symbolic_p ());
-  if (range_int_cst_p (vr))
+  signop sign = TYPE_SIGN (type);
+  unsigned int prec = TYPE_PRECISION (type);
+  gcc_assert (vr_->kind () != VR_ANTI_RANGE || vr_->symbolic_p ());
+  value_range vr = vr_->normalize_symbolics ();
+  if (range_int_cst_p (&vr))
     {
-      wmin = wi::to_wide (vr->min ());
-      wmax = wi::to_wide (vr->max ());
+      wmin = wi::to_wide (vr.min ());
+      wmax = wi::to_wide (vr.max ());
     }
   else
     {
@@ -1240,7 +1279,8 @@ static void
 extract_range_from_multiplicative_op (value_range_base *vr,
 				      enum tree_code code,
 				      const value_range_base *vr0,
-				      const value_range_base *vr1)
+				      const value_range_base *vr1,
+				      tree type)
 {
   gcc_assert (code == MULT_EXPR
 	      || code == TRUNC_DIV_EXPR
@@ -1250,13 +1290,31 @@ extract_range_from_multiplicative_op (value_range_base *vr,
 	      || code == ROUND_DIV_EXPR
 	      || code == RSHIFT_EXPR
 	      || code == LSHIFT_EXPR);
-  gcc_assert (vr0->kind () == VR_RANGE
-	      && vr0->kind () == vr1->kind ());
+  if (!range_int_cst_p (vr1))
+    {
+      vr->set_varying ();
+      return;
+    }
+
+  /* Even if vr0 is VARYING or otherwise not usable, we can derive
+     useful ranges just from the shift count.  E.g.
+     x >> 63 for signed 64-bit x is always [-1, 0].  */
+  value_range_base tem = vr0->normalize_symbolics ();
+  tree vr0_min, vr0_max;
+  if (tem.kind () == VR_RANGE)
+    {
+      vr0_min = tem.min ();
+      vr0_max = tem.max ();
+    }
+  else
+    {
+      vr0_min = vrp_val_min (type);
+      vr0_max = vrp_val_max (type);
+    }
 
-  tree type = vr0->type ();
   wide_int res_lb, res_ub;
-  wide_int vr0_lb = wi::to_wide (vr0->min ());
-  wide_int vr0_ub = wi::to_wide (vr0->max ());
+  wide_int vr0_lb = wi::to_wide (vr0_min);
+  wide_int vr0_ub = wi::to_wide (vr0_max);
   wide_int vr1_lb = wi::to_wide (vr1->min ());
   wide_int vr1_ub = wi::to_wide (vr1->max ());
   bool overflow_undefined = TYPE_OVERFLOW_UNDEFINED (type);
@@ -1266,9 +1324,8 @@ extract_range_from_multiplicative_op (value_range_base *vr,
 					code, TYPE_SIGN (type), prec,
 					vr0_lb, vr0_ub, vr1_lb, vr1_ub,
 					overflow_undefined))
-    vr->set_and_canonicalize (VR_RANGE,
-			      wide_int_to_tree (type, res_lb),
-			      wide_int_to_tree (type, res_ub));
+    vr->set (VR_RANGE, wide_int_to_tree (type, res_lb),
+	     wide_int_to_tree (type, res_ub));
   else
     vr->set_varying ();
 }
@@ -1662,19 +1719,30 @@ extract_range_from_binary_expr (value_range_base *vr,
      range and see what we end up with.  */
   if (code == PLUS_EXPR || code == MINUS_EXPR)
     {
+      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 ();
       /* 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.set (VR_RANGE, vrp_val_min (expr_type), vrp_val_max (expr_type));
+	{
+	  vr0_kind = VR_RANGE;
+	  vr0_min = vrp_val_min (expr_type);
+	  vr0_max = vrp_val_max (expr_type);
+	}
       if (vr1.varying_p ())
-	vr1.set (VR_RANGE, vrp_val_min (expr_type), vrp_val_max (expr_type));
+	{
+	  vr1_kind = VR_RANGE;
+	  vr1_min = vrp_val_min (expr_type);
+	  vr1_max = vrp_val_max (expr_type);
+	}
 
       const bool minus_p = (code == MINUS_EXPR);
-      tree min_op0 = vr0.min ();
-      tree min_op1 = minus_p ? vr1.max () : vr1.min ();
-      tree max_op0 = vr0.max ();
-      tree max_op1 = minus_p ? vr1.min () : vr1.max ();
+      tree min_op0 = vr0_min;
+      tree min_op1 = minus_p ? vr1_max : vr1_min;
+      tree max_op0 = vr0_max;
+      tree max_op1 = minus_p ? vr1_min : vr1_max;
       tree sym_min_op0 = NULL_TREE;
       tree sym_min_op1 = NULL_TREE;
       tree sym_max_op0 = NULL_TREE;
@@ -1687,7 +1755,7 @@ extract_range_from_binary_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
+      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)))
@@ -1767,8 +1835,8 @@ extract_range_from_binary_expr (value_range_base *vr,
       wide_int wmin, wmax;
       wide_int vr0_min, vr0_max;
       wide_int vr1_min, vr1_max;
-      extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max);
-      extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max);
+      extract_range_into_wide_ints (&vr0, expr_type, vr0_min, vr0_max);
+      extract_range_into_wide_ints (&vr1, expr_type, vr1_min, vr1_max);
       if (wide_int_range_min_max (wmin, wmax, code, sign, prec,
 				  vr0_min, vr0_max, vr1_min, vr1_max))
 	vr->set (VR_RANGE, wide_int_to_tree (expr_type, wmin),
@@ -1785,7 +1853,7 @@ extract_range_from_binary_expr (value_range_base *vr,
 	  vr->set_varying ();
 	  return;
 	}
-      extract_range_from_multiplicative_op (vr, code, &vr0, &vr1);
+      extract_range_from_multiplicative_op (vr, code, &vr0, &vr1, expr_type);
       return;
     }
   else if (code == RSHIFT_EXPR
@@ -1800,13 +1868,8 @@ extract_range_from_binary_expr (value_range_base *vr,
 	{
 	  if (code == RSHIFT_EXPR)
 	    {
-	      /* Even if vr0 is VARYING or otherwise not usable, we can derive
-		 useful ranges just from the shift count.  E.g.
-		 x >> 63 for signed 64-bit x is always [-1, 0].  */
-	      if (vr0.kind () != VR_RANGE || vr0.symbolic_p ())
-		vr0.set (VR_RANGE, vrp_val_min (expr_type),
-			 vrp_val_max (expr_type));
-	      extract_range_from_multiplicative_op (vr, code, &vr0, &vr1);
+	      extract_range_from_multiplicative_op (vr, code, &vr0, &vr1,
+						    expr_type);
 	      return;
 	    }
 	  else if (code == LSHIFT_EXPR
@@ -1822,7 +1885,7 @@ extract_range_from_binary_expr (value_range_base *vr,
 		{
 		  min = wide_int_to_tree (expr_type, res_lb);
 		  max = wide_int_to_tree (expr_type, res_ub);
-		  vr->set_and_canonicalize (VR_RANGE, min, max);
+		  vr->set (VR_RANGE, min, max);
 		  return;
 		}
 	    }
@@ -1854,9 +1917,9 @@ extract_range_from_binary_expr (value_range_base *vr,
 	 NOTE: As a future improvement, we may be able to do better
 	 with mixed symbolic (anti-)ranges like [0, A].  See note in
 	 ranges_from_anti_range.  */
-      extract_range_into_wide_ints (&vr0, sign, prec,
+      extract_range_into_wide_ints (&vr0, expr_type,
 				    dividend_min, dividend_max);
-      extract_range_into_wide_ints (&vr1, sign, prec,
+      extract_range_into_wide_ints (&vr1, expr_type,
 				    divisor_min, divisor_max);
       if (!wide_int_range_div (wmin, wmax, code, sign, prec,
 			       dividend_min, dividend_max,
@@ -1887,8 +1950,8 @@ extract_range_from_binary_expr (value_range_base *vr,
 	}
       wide_int wmin, wmax, tmp;
       wide_int vr0_min, vr0_max, vr1_min, vr1_max;
-      extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max);
-      extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max);
+      extract_range_into_wide_ints (&vr0, expr_type, vr0_min, vr0_max);
+      extract_range_into_wide_ints (&vr1, expr_type, vr1_min, vr1_max);
       wide_int_range_trunc_mod (wmin, wmax, sign, prec,
 				vr0_min, vr0_max, vr1_min, vr1_max);
       min = wide_int_to_tree (expr_type, wmin);
@@ -1906,8 +1969,8 @@ extract_range_from_binary_expr (value_range_base *vr,
 				 &may_be_nonzero0, &must_be_nonzero0);
       vrp_set_zero_nonzero_bits (expr_type, &vr1,
 				 &may_be_nonzero1, &must_be_nonzero1);
-      extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max);
-      extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max);
+      extract_range_into_wide_ints (&vr0, expr_type, vr0_min, vr0_max);
+      extract_range_into_wide_ints (&vr1, expr_type, vr1_min, vr1_max);
       if (code == BIT_AND_EXPR)
 	{
 	  if (wide_int_range_bit_and (wmin, wmax, sign, prec,
@@ -2111,8 +2174,7 @@ extract_range_from_unary_expr (value_range_base *vr,
       signop outer_sign = TYPE_SIGN (outer_type);
       unsigned inner_prec = TYPE_PRECISION (inner_type);
       unsigned outer_prec = TYPE_PRECISION (outer_type);
-      extract_range_into_wide_ints (&vr0, inner_sign, inner_prec,
-				    vr0_min, vr0_max);
+      extract_range_into_wide_ints (&vr0, inner_type, vr0_min, vr0_max);
       if (wide_int_range_convert (wmin, wmax,
 				  inner_sign, inner_prec,
 				  outer_sign, outer_prec,
@@ -2120,7 +2182,7 @@ extract_range_from_unary_expr (value_range_base *vr,
 	{
 	  tree min = wide_int_to_tree (outer_type, wmin);
 	  tree max = wide_int_to_tree (outer_type, wmax);
-	  vr->set_and_canonicalize (VR_RANGE, min, max);
+	  vr->set (VR_RANGE, min, max);
 	}
       else
 	vr->set_varying ();
@@ -2130,7 +2192,7 @@ extract_range_from_unary_expr (value_range_base *vr,
     {
       wide_int wmin, wmax;
       wide_int vr0_min, vr0_max;
-      extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max);
+      extract_range_into_wide_ints (&vr0, type, vr0_min, vr0_max);
       if (wide_int_range_abs (wmin, wmax, sign, prec, vr0_min, vr0_max,
 			      TYPE_OVERFLOW_UNDEFINED (type)))
 	vr->set (VR_RANGE, wide_int_to_tree (type, wmin),
@@ -2143,7 +2205,8 @@ extract_range_from_unary_expr (value_range_base *vr,
     {
       wide_int wmin, wmax;
       wide_int vr0_min, vr0_max;
-      extract_range_into_wide_ints (&vr0, SIGNED, prec, vr0_min, vr0_max);
+      tree signed_type = make_signed_type (TYPE_PRECISION (type));
+      extract_range_into_wide_ints (&vr0, signed_type, vr0_min, vr0_max);
       wide_int_range_absu (wmin, wmax, prec, vr0_min, vr0_max);
       vr->set (VR_RANGE, wide_int_to_tree (type, wmin),
 	       wide_int_to_tree (type, wmax));
@@ -6027,7 +6090,7 @@ value_range_base::intersect_helper (const value_range_base *vr0,
      VR_RANGE can still be a VR_RANGE.  Work on a temporary so we can
      fall back to vr0 when this turns things to varying.  */
   value_range_base tem;
-  tem.set_and_canonicalize (vr0type, vr0min, vr0max);
+  tem.set (vr0type, vr0min, vr0max);
   /* If that failed, use the saved original VR0.  */
   if (tem.varying_p ())
     return *vr0;
@@ -6132,7 +6195,7 @@ value_range_base::union_helper (const value_range_base *vr0,
 
   /* Work on a temporary so we can still use vr0 when union returns varying.  */
   value_range_base tem;
-  tem.set_and_canonicalize (vr0type, vr0min, vr0max);
+  tem.set (vr0type, vr0min, vr0max);
 
   /* Failed to find an efficient meet.  Before giving up and setting
      the result to VARYING, see if we can at least derive a useful
@@ -6212,6 +6275,58 @@ value_range::union_ (const value_range *other)
     }
 }
 
+/* Normalize symbolics into constants.  */
+
+value_range_base
+value_range_base::normalize_symbolics () const
+{
+  if (varying_p () || undefined_p ())
+    return *this;
+  tree ttype = type ();
+  bool min_symbolic = !is_gimple_min_invariant (min ());
+  bool max_symbolic = !is_gimple_min_invariant (max ());
+  if (!min_symbolic && !max_symbolic)
+    return *this;
+
+  // [SYM, SYM] -> VARYING
+  if (min_symbolic && max_symbolic)
+    {
+      value_range_base var;
+      var.set_varying ();
+      return var;
+    }
+  if (kind () == VR_RANGE)
+    {
+      // [SYM, NUM] -> [-MIN, NUM]
+      if (min_symbolic)
+	return value_range_base (VR_RANGE, vrp_val_min (ttype), max ());
+      // [NUM, SYM] -> [NUM, +MAX]
+      return value_range_base (VR_RANGE, min (), vrp_val_max (ttype));
+    }
+  gcc_assert (kind () == VR_ANTI_RANGE);
+  // ~[SYM, NUM] -> [NUM + 1, +MAX]
+  if (min_symbolic)
+    {
+      if (!vrp_val_is_max (max ()))
+	{
+	  tree n = wide_int_to_tree (ttype, wi::to_wide (max ()) + 1);
+	  return value_range_base (VR_RANGE, n, vrp_val_max (ttype));
+	}
+      value_range_base var;
+      var.set_varying ();
+      return var;
+    }
+  // ~[NUM, SYM] -> [-MIN, NUM - 1]
+  if (!vrp_val_is_min (min ()))
+    {
+      tree n = wide_int_to_tree (ttype, wi::to_wide (min ()) - 1);
+      return value_range_base (VR_RANGE, vrp_val_min (ttype), n);
+    }
+  value_range_base var;
+  var.set_varying ();
+  return var;
+}
+
 /* Visit all arguments for PHI node PHI that flow through executable
    edges.  If a valid value range can be derived from all the incoming
    value ranges, set a new range for the LHS of PHI.  */
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 4ec974f5fdb..b5830851fcb 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -71,12 +71,13 @@ public:
   /* Misc methods.  */
   tree type () const;
   bool may_contain_p (tree) const;
-  void set_and_canonicalize (enum value_range_kind, tree, tree);
   bool zero_p () const;
   bool nonzero_p () const;
   bool singleton_p (tree *result = NULL) const;
   void dump (FILE *) const;
 
+  value_range_base normalize_symbolics () const;
+
 protected:
   void check ();
   static value_range_base union_helper (const value_range_base *,
@@ -143,7 +144,6 @@ class GTY((user)) value_range : public value_range_base
 
   /* Misc methods.  */
   void deep_copy (const value_range *);
-  void set_and_canonicalize (enum value_range_kind, tree, tree, bitmap = NULL);
   void dump (FILE *) const;
 
  private:
@@ -270,8 +270,8 @@ extern int operand_less_p (tree, tree);
 extern bool vrp_val_is_min (const_tree);
 extern bool vrp_val_is_max (const_tree);
 
-extern tree vrp_val_min (const_tree);
-extern tree vrp_val_max (const_tree);
+extern tree vrp_val_min (const_tree, bool handle_pointers = false);
+extern tree vrp_val_max (const_tree, bool handle_pointers = false);
 
 extern void extract_range_from_unary_expr (value_range_base *vr,
 					   enum tree_code code,
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index 3f20c1a6fe8..10789bdd64e 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -500,9 +500,9 @@ vr_values::extract_range_for_var_from_comparison_expr (tree var,
          vice-versa.  Use set_and_canonicalize which does this for
          us.  */
       if (cond_code == LE_EXPR)
-        vr_p->set_and_canonicalize (VR_RANGE, min, max, vr_p->equiv ());
+        vr_p->set (VR_RANGE, min, max, vr_p->equiv ());
       else if (cond_code == GT_EXPR)
-        vr_p->set_and_canonicalize (VR_ANTI_RANGE, min, max, vr_p->equiv ());
+        vr_p->set (VR_ANTI_RANGE, min, max, vr_p->equiv ());
       else
 	gcc_unreachable ();
     }
@@ -574,7 +574,7 @@ vr_values::extract_range_for_var_from_comparison_expr (tree var,
 	  && vrp_val_is_max (max))
 	min = max = limit;
 
-      vr_p->set_and_canonicalize (VR_ANTI_RANGE, min, max, vr_p->equiv ());
+      vr_p->set (VR_ANTI_RANGE, min, max, vr_p->equiv ());
     }
   else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
     {

Re: enforce canonicalization of value_range's

[Jeff Law]

On 8/12/19 12:48 PM, Aldy Hernandez wrote:
> This is a ping of:
> 
> https://gcc.gnu.org/ml/gcc-patches/2019-07/msg00008.html
> 
> I have addressed the comments Jeff mentioned there.
> 
> This patch goes before the VR_VARYING + types patch, but I can adapt
> either one to come first.  I can even munge them together into one
> patch, if it helps review.
> 
> Tested on x86-64 Linux.
> 
> OK (assuming ChangeLog entries)?
> 
> Aldy
> 
> 
> curr.patch
> 
> commit ea908bdbfc8cdb4bb63e7d42630d01203edbac41
> Author: Aldy Hernandez <aldyh@redhat.com>
> Date:   Mon Jul 15 18:09:27 2019 +0200
> 
>     Enforce canonicalization in value_range.
Per your other message, I'll assume you'll write a suitable ChangeLog
entry before committing :-)


> 
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index 594ee9adc17..de2f39d8487 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -69,23 +69,20 @@ along with GCC; see the file COPYING3.  If not see
>  #include "builtins.h"
>  #include "wide-int-range.h"
>  
> +static bool
> +ranges_from_anti_range (const value_range_base *ar,
> +			value_range_base *vr0, value_range_base *vr1,
> +			bool handle_pointers = false);
> +
Presumably this was better than moving the implementation earlier.


> +/* Normalize symbolics into constants.  */
> +
> +value_range_base
> +value_range_base::normalize_symbolics () const
> +{
> +  if (varying_p () || undefined_p ())
> +    return *this;
> +  tree ttype = type ();
> +  bool min_symbolic = !is_gimple_min_invariant (min ());
> +  bool max_symbolic = !is_gimple_min_invariant (max ());
Sadly "symbolic" is a particularly poor term.  When I think symbolics, I
think SYMBOL_REF, LABEL_REF and the tree equivalents.  They're
*symbols*.  Symbolics in this case are really things like SSA_NAMEs.
Confused the hell out of me briefly.

If we weren't on a path to kill VRP I'd probably suggest a distinct
effort to constify this code.  Some of the changes were a bit confusing
when it looked like we'd dropped a call to set the range of an object.
But those were just local copies, so setting the type/min/max directly
was actually fine.  constification would make this a bit clearer.  But
again, I don't think it's worth the effort given the long term
trajectory for tree-vrp.c.


So where does the handle_pointers stuff matter?   I'm a bit surprised we
have to do anything special for them.


OK.  I don't expect the answers to the minor questions above will
ultimately change anything.

jeff

Re: enforce canonicalization of value_range's

[Aldy Hernandez]

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

On 8/12/19 7:32 PM, Jeff Law wrote:
> On 8/12/19 12:48 PM, Aldy Hernandez wrote:
>> This is a ping of:
>>
>> https://gcc.gnu.org/ml/gcc-patches/2019-07/msg00008.html
>>
>> I have addressed the comments Jeff mentioned there.
>>
>> This patch goes before the VR_VARYING + types patch, but I can adapt
>> either one to come first.  I can even munge them together into one
>> patch, if it helps review.
>>
>> Tested on x86-64 Linux.
>>
>> OK (assuming ChangeLog entries)?
>>
>> Aldy
>>
>>
>> curr.patch
>>
>> commit ea908bdbfc8cdb4bb63e7d42630d01203edbac41
>> Author: Aldy Hernandez <aldyh@redhat.com>
>> Date:   Mon Jul 15 18:09:27 2019 +0200
>>
>>      Enforce canonicalization in value_range.
> Per your other message, I'll assume you'll write a suitable ChangeLog
> entry before committing :-)

Attached patch has ChangeLog entries.

> 
> 
>>
>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>> index 594ee9adc17..de2f39d8487 100644
>> --- a/gcc/tree-vrp.c
>> +++ b/gcc/tree-vrp.c
>> @@ -69,23 +69,20 @@ along with GCC; see the file COPYING3.  If not see
>>   #include "builtins.h"
>>   #include "wide-int-range.h"
>>   
>> +static bool
>> +ranges_from_anti_range (const value_range_base *ar,
>> +			value_range_base *vr0, value_range_base *vr1,
>> +			bool handle_pointers = false);
>> +
> Presumably this was better than moving the implementation earlier.

Actually, it was for ease of review.  I made some changes to the 
function, and I didn't want the reviewer to miss them because I had 
moved the function wholesale.  I can move the function earlier, after we 
agree on the changes (see below).

> 
> 
>> +/* Normalize symbolics into constants.  */
>> +
>> +value_range_base
>> +value_range_base::normalize_symbolics () const
>> +{
>> +  if (varying_p () || undefined_p ())
>> +    return *this;
>> +  tree ttype = type ();
>> +  bool min_symbolic = !is_gimple_min_invariant (min ());
>> +  bool max_symbolic = !is_gimple_min_invariant (max ());
> Sadly "symbolic" is a particularly poor term.  When I think symbolics, I
> think SYMBOL_REF, LABEL_REF and the tree equivalents.  They're
> *symbols*.  Symbolics in this case are really things like SSA_NAMEs.
> Confused the hell out of me briefly.

Sigh, yeah.  Unfortunately, symbolics is what VRP calls anything that is 
not an INTEGER_CST (that is, PLUS_EXPR and SSA_NAMEs, etc).

> 
> If we weren't on a path to kill VRP I'd probably suggest a distinct
> effort to constify this code.  Some of the changes were a bit confusing
> when it looked like we'd dropped a call to set the range of an object.
> But those were just local copies, so setting the type/min/max directly
> was actually fine.  constification would make this a bit clearer.  But
> again, I don't think it's worth the effort given the long term
> trajectory for tree-vrp.c.

I shouldn't be introducing any new confusion.  Did I add any new methods 
that should've been const that aren't?  I can't see any??.  I'm happy to 
fix anything I introduced.

> 
> 
> So where does the handle_pointers stuff matter?   I'm a bit surprised we
> have to do anything special for them.

I've learned to touch as little of VRP as is necessary, as changing 
anything to be more consistent breaks things in unexpected ways ;-).

In this particular case, TYPE_MIN_VALUE and TYPE_MAX_VALUE are not 
defined for pointers, and I didn't want to change the meaning of 
vrp_val_{min,max} throughout.  I was trying to minimize the changes to 
existing behavior.  If it bothers you too much, we could remove it as a 
follow up when we are sure there are no expected side-effects from the 
rest of the patch. ??

> 
> 
> OK.  I don't expect the answers to the minor questions above will
> ultimately change anything.

I could appreciate a final nod before I commit.  And even then, I will 
wait until the other patch is approved and commit them simultaneously. 
They are a bit intertwined.

Thanks for your prompt reviews.

Aldy

[-- Attachment #2: curr.patch --]
[-- Type: text/x-patch, Size: 23788 bytes --]

commit 39be54a2e0ef19b3fb1cc3e51b380a6811e50ab4
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Mon Jul 15 18:09:27 2019 +0200

    Enforce canonicalization in value_range.

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 93e600d68f2..3fa864624c9 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,37 @@
+2019-08-13  Aldy Hernandez  <aldyh@redhat.com>
+
+	* tree-vrp.c (value_range_base::set): Merge in code from
+	value_range_base::set_and_canonicalize.
+	Enforce canonicalization at set time.
+	Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED.
+	(value_range_base::set_undefined): Inline call to set().
+	(value_range_base::set_varying): Same.
+	(value_range_base::singleton_p): Handle VR_ANTI_RANGEs.
+	(vrp_val_max): New argument handle_pointers.
+	(vrp_val_min): Same.
+	(ranges_from_anti_range): Same.
+	(extract_range_into_wide_ints): Use tree argument instead of sign
+	and precision.
+	(extract_range_from_multiplicative_op): Take in tree type instead
+	of precision and sign.  Adapt function for canonicalized ranges.
+	(extract_range_from_binary_expr): Pass type to
+	extract_range_from_multiplicative_op.
+	Adapt for canonicalized ranges.
+	(extract_range_from_unary_expr): Same.
+	(value_range_base::intersect_helper): Adjust for canonicalized
+	ranges.
+	(value_range_base::union_helper): Same.
+	(value_range_base::normalize_symbolics): New.
+	* tree-vrp.h (class value_range_base): Remove
+	set_and_canonicalize.
+	New prototype for normalize_symbolics.
+	(class value_range): Remove set_and_canonicalize.
+	(vrp_val_min): Adjust prototype.
+	(vrp_val_max): Same.
+	* vr-values.c
+	(vr_values::extract_range_for_var_from_comparison_expr):  Call set
+	instead of set_and_canonicalize.
+
 2019-08-12  Jakub Jelinek  <jakub@redhat.com>
 
 	PR target/83250
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index e2850682da2..77e7594eee5 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -69,23 +69,20 @@ along with GCC; see the file COPYING3.  If not see
 #include "builtins.h"
 #include "wide-int-range.h"
 
+static bool
+ranges_from_anti_range (const value_range_base *ar,
+			value_range_base *vr0, value_range_base *vr1,
+			bool handle_pointers = false);
+
 /* Set of SSA names found live during the RPO traversal of the function
    for still active basic-blocks.  */
 static sbitmap *live;
 
-void
-value_range_base::set (enum value_range_kind kind, tree min, tree max)
-{
-  m_kind = kind;
-  m_min = min;
-  m_max = max;
-  if (flag_checking)
-    check ();
-}
-
 void
 value_range::set_equiv (bitmap equiv)
 {
+  if (undefined_p () || varying_p ())
+    equiv = NULL;
   /* Since updating the equivalence set involves deep copying the
      bitmaps, only do it if absolutely necessary.
 
@@ -261,7 +258,8 @@ value_range_base::constant_p () const
 void
 value_range_base::set_undefined ()
 {
-  set (VR_UNDEFINED, NULL, NULL);
+  m_kind = VR_UNDEFINED;
+  m_min = m_max = NULL;
 }
 
 void
@@ -273,7 +271,8 @@ value_range::set_undefined ()
 void
 value_range_base::set_varying ()
 {
-  set (VR_VARYING, NULL, NULL);
+  m_kind = VR_VARYING;
+  m_min = m_max = NULL;
 }
 
 void
@@ -324,6 +323,24 @@ value_range::equiv_add (const_tree var,
 bool
 value_range_base::singleton_p (tree *result) const
 {
+  if (m_kind == VR_ANTI_RANGE)
+    {
+      if (nonzero_p ())
+	{
+	  if (TYPE_PRECISION (type ()) == 1)
+	    {
+	      if (result)
+		*result = m_max;
+	      return true;
+	    }
+	  return false;
+	}
+
+      value_range_base vr0, vr1;
+      return (ranges_from_anti_range (this, &vr0, &vr1, true)
+	      && vr1.undefined_p ()
+	      && vr0.singleton_p (result));
+    }
   if (m_kind == VR_RANGE
       && vrp_operand_equal_p (min (), max ())
       && is_gimple_min_invariant (min ()))
@@ -499,23 +516,28 @@ static assert_locus **asserts_for;
 /* Return the maximum value for TYPE.  */
 
 tree
-vrp_val_max (const_tree type)
+vrp_val_max (const_tree type, bool handle_pointers)
 {
-  if (!INTEGRAL_TYPE_P (type))
-    return NULL_TREE;
-
-  return TYPE_MAX_VALUE (type);
+  if (INTEGRAL_TYPE_P (type))
+    return TYPE_MAX_VALUE (type);
+  if (POINTER_TYPE_P (type) && handle_pointers)
+    {
+      wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
+      return wide_int_to_tree (const_cast<tree> (type), max);
+    }
+  return NULL_TREE;
 }
 
 /* Return the minimum value for TYPE.  */
 
 tree
-vrp_val_min (const_tree type)
+vrp_val_min (const_tree type, bool handle_pointers)
 {
-  if (!INTEGRAL_TYPE_P (type))
-    return NULL_TREE;
-
-  return TYPE_MIN_VALUE (type);
+  if (INTEGRAL_TYPE_P (type))
+    return TYPE_MIN_VALUE (type);
+  if (POINTER_TYPE_P (type) && handle_pointers)
+    return build_zero_cst (const_cast<tree> (type));
+  return NULL_TREE;
 }
 
 /* Return whether VAL is equal to the maximum value of its type.
@@ -626,8 +648,7 @@ intersect_range_with_nonzero_bits (enum value_range_kind vr_type,
    extract ranges from var + CST op limit.  */
 
 void
-value_range_base::set_and_canonicalize (enum value_range_kind kind,
-					tree min, tree max)
+value_range_base::set (enum value_range_kind kind, tree min, tree max)
 {
   /* Use the canonical setters for VR_UNDEFINED and VR_VARYING.  */
   if (kind == VR_UNDEFINED)
@@ -645,7 +666,9 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind,
   if (TREE_CODE (min) != INTEGER_CST
       || TREE_CODE (max) != INTEGER_CST)
     {
-      set (kind, min, max);
+      m_kind = kind;
+      m_min = min;
+      m_max = max;
       return;
     }
 
@@ -681,12 +704,13 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind,
       kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
     }
 
+  tree type = TREE_TYPE (min);
+
   /* Anti-ranges that can be represented as ranges should be so.  */
   if (kind == VR_ANTI_RANGE)
     {
       /* For -fstrict-enums we may receive out-of-range ranges so consider
          values < -INF and values > INF as -INF/INF as well.  */
-      tree type = TREE_TYPE (min);
       bool is_min = (INTEGRAL_TYPE_P (type)
 		     && tree_int_cst_compare (min, TYPE_MIN_VALUE (type)) <= 0);
       bool is_max = (INTEGRAL_TYPE_P (type)
@@ -729,22 +753,37 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind,
         }
     }
 
+  /* Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED.
+
+     Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
+     restrict those to a subset of what actually fits in the type.
+     Instead use the extremes of the type precision which will allow
+     compare_range_with_value() to check if a value is inside a range,
+     whereas if we used TYPE_*_VAL, said function would just punt
+     upon seeing a VARYING.  */
+  unsigned prec = TYPE_PRECISION (type);
+  signop sign = TYPE_SIGN (type);
+  if (wi::eq_p (wi::to_wide (min), wi::min_value (prec, sign))
+      && wi::eq_p (wi::to_wide (max), wi::max_value (prec, sign)))
+    {
+      if (kind == VR_RANGE)
+	set_varying ();
+      else if (kind == VR_ANTI_RANGE)
+	set_undefined ();
+      else
+	gcc_unreachable ();
+      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.  */
 
-  set (kind, min, max);
-}
-
-void
-value_range::set_and_canonicalize (enum value_range_kind kind,
-				   tree min, tree max, bitmap equiv)
-{
-  value_range_base::set_and_canonicalize (kind, min, max);
-  if (this->kind () == VR_RANGE || this->kind () == VR_ANTI_RANGE)
-    set_equiv (equiv);
-  else
-    equiv_clear ();
+  m_kind = kind;
+  m_min = min;
+  m_max = max;
+  if (flag_checking)
+    check ();
 }
 
 void
@@ -1180,7 +1219,8 @@ vrp_set_zero_nonzero_bits (const tree expr_type,
 
 static bool
 ranges_from_anti_range (const value_range_base *ar,
-			value_range_base *vr0, value_range_base *vr1)
+			value_range_base *vr0, value_range_base *vr1,
+			bool handle_pointers)
 {
   tree type = ar->type ();
 
@@ -1193,18 +1233,18 @@ ranges_from_anti_range (const value_range_base *ar,
   if (ar->kind () != VR_ANTI_RANGE
       || TREE_CODE (ar->min ()) != INTEGER_CST
       || TREE_CODE (ar->max ()) != INTEGER_CST
-      || !vrp_val_min (type)
-      || !vrp_val_max (type))
+      || !vrp_val_min (type, handle_pointers)
+      || !vrp_val_max (type, handle_pointers))
     return false;
 
-  if (tree_int_cst_lt (vrp_val_min (type), ar->min ()))
+  if (tree_int_cst_lt (vrp_val_min (type, handle_pointers), ar->min ()))
     vr0->set (VR_RANGE,
-	      vrp_val_min (type),
+	      vrp_val_min (type, handle_pointers),
 	      wide_int_to_tree (type, wi::to_wide (ar->min ()) - 1));
-  if (tree_int_cst_lt (ar->max (), vrp_val_max (type)))
+  if (tree_int_cst_lt (ar->max (), vrp_val_max (type, handle_pointers)))
     vr1->set (VR_RANGE,
 	      wide_int_to_tree (type, wi::to_wide (ar->max ()) + 1),
-	      vrp_val_max (type));
+	      vrp_val_max (type, handle_pointers));
   if (vr0->undefined_p ())
     {
       *vr0 = *vr1;
@@ -1215,21 +1255,20 @@ ranges_from_anti_range (const value_range_base *ar,
 }
 
 /* Extract the components of a value range into a pair of wide ints in
-   [WMIN, WMAX].
-
-   If the value range is anything but a VR_*RANGE of constants, the
-   resulting wide ints are set to [-MIN, +MAX] for the type.  */
+   [WMIN, WMAX], after having normalized any symbolics from the input.  */
 
 static void inline
-extract_range_into_wide_ints (const value_range_base *vr,
-			      signop sign, unsigned prec,
-			      wide_int &wmin, wide_int &wmax)
+extract_range_into_wide_ints (const value_range_base *vr_,
+			      tree type, wide_int &wmin, wide_int &wmax)
 {
-  gcc_assert (vr->kind () != VR_ANTI_RANGE || vr->symbolic_p ());
-  if (range_int_cst_p (vr))
+  signop sign = TYPE_SIGN (type);
+  unsigned int prec = TYPE_PRECISION (type);
+  gcc_assert (vr_->kind () != VR_ANTI_RANGE || vr_->symbolic_p ());
+  value_range vr = vr_->normalize_symbolics ();
+  if (range_int_cst_p (&vr))
     {
-      wmin = wi::to_wide (vr->min ());
-      wmax = wi::to_wide (vr->max ());
+      wmin = wi::to_wide (vr.min ());
+      wmax = wi::to_wide (vr.max ());
     }
   else
     {
@@ -1256,12 +1295,31 @@ extract_range_from_multiplicative_op (value_range_base *vr,
 	      || code == ROUND_DIV_EXPR
 	      || code == RSHIFT_EXPR
 	      || code == LSHIFT_EXPR);
-  gcc_assert (vr0->kind () == VR_RANGE
-	      && vr0->kind () == vr1->kind ());
+  if (!range_int_cst_p (vr1))
+    {
+      vr->set_varying ();
+      return;
+    }
+
+  /* Even if vr0 is VARYING or otherwise not usable, we can derive
+     useful ranges just from the shift count.  E.g.
+     x >> 63 for signed 64-bit x is always [-1, 0].  */
+  value_range_base tem = vr0->normalize_symbolics ();
+  tree vr0_min, vr0_max;
+  if (tem.kind () == VR_RANGE)
+    {
+      vr0_min = tem.min ();
+      vr0_max = tem.max ();
+    }
+  else
+    {
+      vr0_min = vrp_val_min (type);
+      vr0_max = vrp_val_max (type);
+    }
 
   wide_int res_lb, res_ub;
-  wide_int vr0_lb = wi::to_wide (vr0->min ());
-  wide_int vr0_ub = wi::to_wide (vr0->max ());
+  wide_int vr0_lb = wi::to_wide (vr0_min);
+  wide_int vr0_ub = wi::to_wide (vr0_max);
   wide_int vr1_lb = wi::to_wide (vr1->min ());
   wide_int vr1_ub = wi::to_wide (vr1->max ());
   bool overflow_undefined = TYPE_OVERFLOW_UNDEFINED (type);
@@ -1271,9 +1329,8 @@ extract_range_from_multiplicative_op (value_range_base *vr,
 					code, TYPE_SIGN (type), prec,
 					vr0_lb, vr0_ub, vr1_lb, vr1_ub,
 					overflow_undefined))
-    vr->set_and_canonicalize (VR_RANGE,
-			      wide_int_to_tree (type, res_lb),
-			      wide_int_to_tree (type, res_ub));
+    vr->set (VR_RANGE, wide_int_to_tree (type, res_lb),
+	     wide_int_to_tree (type, res_ub));
   else
     vr->set_varying ();
 }
@@ -1667,19 +1724,30 @@ extract_range_from_binary_expr (value_range_base *vr,
      range and see what we end up with.  */
   if (code == PLUS_EXPR || code == MINUS_EXPR)
     {
+      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 ();
       /* 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.set (VR_RANGE, vrp_val_min (expr_type), vrp_val_max (expr_type));
+	{
+	  vr0_kind = VR_RANGE;
+	  vr0_min = vrp_val_min (expr_type);
+	  vr0_max = vrp_val_max (expr_type);
+	}
       if (vr1.varying_p ())
-	vr1.set (VR_RANGE, vrp_val_min (expr_type), vrp_val_max (expr_type));
+	{
+	  vr1_kind = VR_RANGE;
+	  vr1_min = vrp_val_min (expr_type);
+	  vr1_max = vrp_val_max (expr_type);
+	}
 
       const bool minus_p = (code == MINUS_EXPR);
-      tree min_op0 = vr0.min ();
-      tree min_op1 = minus_p ? vr1.max () : vr1.min ();
-      tree max_op0 = vr0.max ();
-      tree max_op1 = minus_p ? vr1.min () : vr1.max ();
+      tree min_op0 = vr0_min;
+      tree min_op1 = minus_p ? vr1_max : vr1_min;
+      tree max_op0 = vr0_max;
+      tree max_op1 = minus_p ? vr1_min : vr1_max;
       tree sym_min_op0 = NULL_TREE;
       tree sym_min_op1 = NULL_TREE;
       tree sym_max_op0 = NULL_TREE;
@@ -1692,7 +1760,7 @@ extract_range_from_binary_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
+      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)))
@@ -1772,8 +1840,8 @@ extract_range_from_binary_expr (value_range_base *vr,
       wide_int wmin, wmax;
       wide_int vr0_min, vr0_max;
       wide_int vr1_min, vr1_max;
-      extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max);
-      extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max);
+      extract_range_into_wide_ints (&vr0, expr_type, vr0_min, vr0_max);
+      extract_range_into_wide_ints (&vr1, expr_type, vr1_min, vr1_max);
       if (wide_int_range_min_max (wmin, wmax, code, sign, prec,
 				  vr0_min, vr0_max, vr1_min, vr1_max))
 	vr->set (VR_RANGE, wide_int_to_tree (expr_type, wmin),
@@ -1805,12 +1873,6 @@ extract_range_from_binary_expr (value_range_base *vr,
 	{
 	  if (code == RSHIFT_EXPR)
 	    {
-	      /* Even if vr0 is VARYING or otherwise not usable, we can derive
-		 useful ranges just from the shift count.  E.g.
-		 x >> 63 for signed 64-bit x is always [-1, 0].  */
-	      if (vr0.kind () != VR_RANGE || vr0.symbolic_p ())
-		vr0.set (VR_RANGE, vrp_val_min (expr_type),
-			 vrp_val_max (expr_type));
 	      extract_range_from_multiplicative_op (vr, code, expr_type,
 						    &vr0, &vr1);
 	      return;
@@ -1828,7 +1890,7 @@ extract_range_from_binary_expr (value_range_base *vr,
 		{
 		  min = wide_int_to_tree (expr_type, res_lb);
 		  max = wide_int_to_tree (expr_type, res_ub);
-		  vr->set_and_canonicalize (VR_RANGE, min, max);
+		  vr->set (VR_RANGE, min, max);
 		  return;
 		}
 	    }
@@ -1860,9 +1922,9 @@ extract_range_from_binary_expr (value_range_base *vr,
 	 NOTE: As a future improvement, we may be able to do better
 	 with mixed symbolic (anti-)ranges like [0, A].  See note in
 	 ranges_from_anti_range.  */
-      extract_range_into_wide_ints (&vr0, sign, prec,
+      extract_range_into_wide_ints (&vr0, expr_type,
 				    dividend_min, dividend_max);
-      extract_range_into_wide_ints (&vr1, sign, prec,
+      extract_range_into_wide_ints (&vr1, expr_type,
 				    divisor_min, divisor_max);
       if (!wide_int_range_div (wmin, wmax, code, sign, prec,
 			       dividend_min, dividend_max,
@@ -1893,8 +1955,8 @@ extract_range_from_binary_expr (value_range_base *vr,
 	}
       wide_int wmin, wmax, tmp;
       wide_int vr0_min, vr0_max, vr1_min, vr1_max;
-      extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max);
-      extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max);
+      extract_range_into_wide_ints (&vr0, expr_type, vr0_min, vr0_max);
+      extract_range_into_wide_ints (&vr1, expr_type, vr1_min, vr1_max);
       wide_int_range_trunc_mod (wmin, wmax, sign, prec,
 				vr0_min, vr0_max, vr1_min, vr1_max);
       min = wide_int_to_tree (expr_type, wmin);
@@ -1912,8 +1974,8 @@ extract_range_from_binary_expr (value_range_base *vr,
 				 &may_be_nonzero0, &must_be_nonzero0);
       vrp_set_zero_nonzero_bits (expr_type, &vr1,
 				 &may_be_nonzero1, &must_be_nonzero1);
-      extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max);
-      extract_range_into_wide_ints (&vr1, sign, prec, vr1_min, vr1_max);
+      extract_range_into_wide_ints (&vr0, expr_type, vr0_min, vr0_max);
+      extract_range_into_wide_ints (&vr1, expr_type, vr1_min, vr1_max);
       if (code == BIT_AND_EXPR)
 	{
 	  if (wide_int_range_bit_and (wmin, wmax, sign, prec,
@@ -2117,8 +2179,7 @@ extract_range_from_unary_expr (value_range_base *vr,
       signop outer_sign = TYPE_SIGN (outer_type);
       unsigned inner_prec = TYPE_PRECISION (inner_type);
       unsigned outer_prec = TYPE_PRECISION (outer_type);
-      extract_range_into_wide_ints (&vr0, inner_sign, inner_prec,
-				    vr0_min, vr0_max);
+      extract_range_into_wide_ints (&vr0, inner_type, vr0_min, vr0_max);
       if (wide_int_range_convert (wmin, wmax,
 				  inner_sign, inner_prec,
 				  outer_sign, outer_prec,
@@ -2126,7 +2187,7 @@ extract_range_from_unary_expr (value_range_base *vr,
 	{
 	  tree min = wide_int_to_tree (outer_type, wmin);
 	  tree max = wide_int_to_tree (outer_type, wmax);
-	  vr->set_and_canonicalize (VR_RANGE, min, max);
+	  vr->set (VR_RANGE, min, max);
 	}
       else
 	vr->set_varying ();
@@ -2136,7 +2197,7 @@ extract_range_from_unary_expr (value_range_base *vr,
     {
       wide_int wmin, wmax;
       wide_int vr0_min, vr0_max;
-      extract_range_into_wide_ints (&vr0, sign, prec, vr0_min, vr0_max);
+      extract_range_into_wide_ints (&vr0, type, vr0_min, vr0_max);
       if (wide_int_range_abs (wmin, wmax, sign, prec, vr0_min, vr0_max,
 			      TYPE_OVERFLOW_UNDEFINED (type)))
 	vr->set (VR_RANGE, wide_int_to_tree (type, wmin),
@@ -2149,7 +2210,8 @@ extract_range_from_unary_expr (value_range_base *vr,
     {
       wide_int wmin, wmax;
       wide_int vr0_min, vr0_max;
-      extract_range_into_wide_ints (&vr0, SIGNED, prec, vr0_min, vr0_max);
+      tree signed_type = make_signed_type (TYPE_PRECISION (type));
+      extract_range_into_wide_ints (&vr0, signed_type, vr0_min, vr0_max);
       wide_int_range_absu (wmin, wmax, prec, vr0_min, vr0_max);
       vr->set (VR_RANGE, wide_int_to_tree (type, wmin),
 	       wide_int_to_tree (type, wmax));
@@ -6038,7 +6100,7 @@ value_range_base::intersect_helper (const value_range_base *vr0,
      VR_RANGE can still be a VR_RANGE.  Work on a temporary so we can
      fall back to vr0 when this turns things to varying.  */
   value_range_base tem;
-  tem.set_and_canonicalize (vr0type, vr0min, vr0max);
+  tem.set (vr0type, vr0min, vr0max);
   /* If that failed, use the saved original VR0.  */
   if (tem.varying_p ())
     return *vr0;
@@ -6143,7 +6205,7 @@ value_range_base::union_helper (const value_range_base *vr0,
 
   /* Work on a temporary so we can still use vr0 when union returns varying.  */
   value_range_base tem;
-  tem.set_and_canonicalize (vr0type, vr0min, vr0max);
+  tem.set (vr0type, vr0min, vr0max);
 
   /* Failed to find an efficient meet.  Before giving up and setting
      the result to VARYING, see if we can at least derive a useful
@@ -6223,6 +6285,58 @@ value_range::union_ (const value_range *other)
     }
 }
 
+/* Normalize symbolics into constants.  */
+
+value_range_base
+value_range_base::normalize_symbolics () const
+{
+  if (varying_p () || undefined_p ())
+    return *this;
+  tree ttype = type ();
+  bool min_symbolic = !is_gimple_min_invariant (min ());
+  bool max_symbolic = !is_gimple_min_invariant (max ());
+  if (!min_symbolic && !max_symbolic)
+    return *this;
+
+  // [SYM, SYM] -> VARYING
+  if (min_symbolic && max_symbolic)
+    {
+      value_range_base var;
+      var.set_varying ();
+      return var;
+    }
+  if (kind () == VR_RANGE)
+    {
+      // [SYM, NUM] -> [-MIN, NUM]
+      if (min_symbolic)
+	return value_range_base (VR_RANGE, vrp_val_min (ttype), max ());
+      // [NUM, SYM] -> [NUM, +MAX]
+      return value_range_base (VR_RANGE, min (), vrp_val_max (ttype));
+    }
+  gcc_assert (kind () == VR_ANTI_RANGE);
+  // ~[SYM, NUM] -> [NUM + 1, +MAX]
+  if (min_symbolic)
+    {
+      if (!vrp_val_is_max (max ()))
+	{
+	  tree n = wide_int_to_tree (ttype, wi::to_wide (max ()) + 1);
+	  return value_range_base (VR_RANGE, n, vrp_val_max (ttype));
+	}
+      value_range_base var;
+      var.set_varying ();
+      return var;
+    }
+  // ~[NUM, SYM] -> [-MIN, NUM - 1]
+  if (!vrp_val_is_min (min ()))
+    {
+      tree n = wide_int_to_tree (ttype, wi::to_wide (min ()) - 1);
+      return value_range_base (VR_RANGE, vrp_val_min (ttype), n);
+    }
+  value_range_base var;
+  var.set_varying ();
+  return var;
+}
+
 /* Visit all arguments for PHI node PHI that flow through executable
    edges.  If a valid value range can be derived from all the incoming
    value ranges, set a new range for the LHS of PHI.  */
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 4ec974f5fdb..b5830851fcb 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -71,12 +71,13 @@ public:
   /* Misc methods.  */
   tree type () const;
   bool may_contain_p (tree) const;
-  void set_and_canonicalize (enum value_range_kind, tree, tree);
   bool zero_p () const;
   bool nonzero_p () const;
   bool singleton_p (tree *result = NULL) const;
   void dump (FILE *) const;
 
+  value_range_base normalize_symbolics () const;
+
 protected:
   void check ();
   static value_range_base union_helper (const value_range_base *,
@@ -143,7 +144,6 @@ class GTY((user)) value_range : public value_range_base
 
   /* Misc methods.  */
   void deep_copy (const value_range *);
-  void set_and_canonicalize (enum value_range_kind, tree, tree, bitmap = NULL);
   void dump (FILE *) const;
 
  private:
@@ -270,8 +270,8 @@ extern int operand_less_p (tree, tree);
 extern bool vrp_val_is_min (const_tree);
 extern bool vrp_val_is_max (const_tree);
 
-extern tree vrp_val_min (const_tree);
-extern tree vrp_val_max (const_tree);
+extern tree vrp_val_min (const_tree, bool handle_pointers = false);
+extern tree vrp_val_max (const_tree, bool handle_pointers = false);
 
 extern void extract_range_from_unary_expr (value_range_base *vr,
 					   enum tree_code code,
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index 3acbdf62a56..a87cb672e36 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -522,9 +522,9 @@ vr_values::extract_range_for_var_from_comparison_expr (tree var,
          vice-versa.  Use set_and_canonicalize which does this for
          us.  */
       if (cond_code == LE_EXPR)
-        vr_p->set_and_canonicalize (VR_RANGE, min, max, vr_p->equiv ());
+        vr_p->set (VR_RANGE, min, max, vr_p->equiv ());
       else if (cond_code == GT_EXPR)
-        vr_p->set_and_canonicalize (VR_ANTI_RANGE, min, max, vr_p->equiv ());
+        vr_p->set (VR_ANTI_RANGE, min, max, vr_p->equiv ());
       else
 	gcc_unreachable ();
     }
@@ -596,7 +596,7 @@ vr_values::extract_range_for_var_from_comparison_expr (tree var,
 	  && vrp_val_is_max (max))
 	min = max = limit;
 
-      vr_p->set_and_canonicalize (VR_ANTI_RANGE, min, max, vr_p->equiv ());
+      vr_p->set (VR_ANTI_RANGE, min, max, vr_p->equiv ());
     }
   else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
     {

Re: enforce canonicalization of value_range's

[Jeff Law]

On 8/13/19 6:51 PM, Aldy Hernandez wrote:
>> Presumably this was better than moving the implementation earlier.
> 
> Actually, it was for ease of review.  I made some changes to the
> function, and I didn't want the reviewer to miss them because I had
> moved the function wholesale.  I can move the function earlier, after we
> agree on the changes (see below).
Either works for me.  I think there was an informal effort to avoid
these kinds of forward decls eons ago because our inliner sucked, but in
the IPA world order in the source file really shouldn't matter.

> 
>>
>> If we weren't on a path to kill VRP I'd probably suggest a distinct
>> effort to constify this code.  Some of the changes were a bit confusing
>> when it looked like we'd dropped a call to set the range of an object.
>> But those were just local copies, so setting the type/min/max directly
>> was actually fine.  constification would make this a bit clearer.  But
>> again, I don't think it's worth the effort given the long term
>> trajectory for tree-vrp.c.
> 
> I shouldn't be introducing any new confusion.  Did I add any new methods
> that should've been const that aren't?  I can't see any??.  I'm happy to
> fix anything I introduced.
IIRC we had an incoming range object passed by value, which we locally
modified and called the setter.

I spotted the dropped call to the setter and was going to call it out as
possibly broken.  But in investigating further I realized the object was
passed by value, so dropping the setter wasn't really a problem.

THe funny thing was we were doing this on source operands rather than
the destination operand.  Arguably the ranges for the source operands
should be constant which would have flagged that code as fishy from its
inception and I'm sure the code would have been restructured
appropriately and would have avoided the confusion.

So in summary, you didn't break anything.  It was a safe change you
made, but it wasn't immediately obvious it was safe.  If we had a
constified codebase the intent of the code would have been more obvious.


> 
>>
>>
>> So where does the handle_pointers stuff matter?   I'm a bit surprised we
>> have to do anything special for them.
> 
> I've learned to touch as little of VRP as is necessary, as changing
> anything to be more consistent breaks things in unexpected ways ;-).
> 
> In this particular case, TYPE_MIN_VALUE and TYPE_MAX_VALUE are not
> defined for pointers, and I didn't want to change the meaning of
> vrp_val_{min,max} throughout.  I was trying to minimize the changes to
> existing behavior.  If it bothers you too much, we could remove it as a
> follow up when we are sure there are no expected side-effects from the
> rest of the patch. ??
I don't mind exploring this as a follow-up.  I guess that a min/max
doesn't really have significant meaning for pointers.

I think rather than digging too deep into this, let's table it for now.
 I think the time to revisit will be as we work through removal of
tree-vrp at some point in the future.

> 
>>
>>
>> OK.  I don't expect the answers to the minor questions above will
>> ultimately change anything.
> 
> I could appreciate a final nod before I commit.  And even then, I will
> wait until the other patch is approved and commit them simultaneously.
> They are a bit intertwined.
I'm nodding :-)

jeff

Re: enforce canonicalization of value_range's

[Aldy Hernandez]

On 8/14/19 1:53 PM, Jeff Law wrote:
> On 8/13/19 6:51 PM, Aldy Hernandez wrote:
>>> Presumably this was better than moving the implementation earlier.
>>
>> Actually, it was for ease of review.  I made some changes to the
>> function, and I didn't want the reviewer to miss them because I had
>> moved the function wholesale.  I can move the function earlier, after we
>> agree on the changes (see below).
> Either works for me.  I think there was an informal effort to avoid
> these kinds of forward decls eons ago because our inliner sucked, but in
> the IPA world order in the source file really shouldn't matter.

Ok, I'll leave it as is, so I don't have to rebase the VARYING patch. 
When both patches are in, I'll move the definition up as an obvious change.

> 
>>
>>>
>>> If we weren't on a path to kill VRP I'd probably suggest a distinct
>>> effort to constify this code.  Some of the changes were a bit confusing
>>> when it looked like we'd dropped a call to set the range of an object.
>>> But those were just local copies, so setting the type/min/max directly
>>> was actually fine.  constification would make this a bit clearer.  But
>>> again, I don't think it's worth the effort given the long term
>>> trajectory for tree-vrp.c.
>>
>> I shouldn't be introducing any new confusion.  Did I add any new methods
>> that should've been const that aren't?  I can't see any??.  I'm happy to
>> fix anything I introduced.
> IIRC we had an incoming range object passed by value, which we locally
> modified and called the setter.
> 
> I spotted the dropped call to the setter and was going to call it out as
> possibly broken.  But in investigating further I realized the object was
> passed by value, so dropping the setter wasn't really a problem.
> 
> THe funny thing was we were doing this on source operands rather than
> the destination operand.  Arguably the ranges for the source operands
> should be constant which would have flagged that code as fishy from its
> inception and I'm sure the code would have been restructured
> appropriately and would have avoided the confusion.
> 
> So in summary, you didn't break anything.  It was a safe change you
> made, but it wasn't immediately obvious it was safe.  If we had a
> constified codebase the intent of the code would have been more obvious.
> 
> 
>>
>>>
>>>
>>> So where does the handle_pointers stuff matter?   I'm a bit surprised we
>>> have to do anything special for them.
>>
>> I've learned to touch as little of VRP as is necessary, as changing
>> anything to be more consistent breaks things in unexpected ways ;-).
>>
>> In this particular case, TYPE_MIN_VALUE and TYPE_MAX_VALUE are not
>> defined for pointers, and I didn't want to change the meaning of
>> vrp_val_{min,max} throughout.  I was trying to minimize the changes to
>> existing behavior.  If it bothers you too much, we could remove it as a
>> follow up when we are sure there are no expected side-effects from the
>> rest of the patch. ??
> I don't mind exploring this as a follow-up.  I guess that a min/max
> doesn't really have significant meaning for pointers.
> 
> I think rather than digging too deep into this, let's table it for now.
>   I think the time to revisit will be as we work through removal of
> tree-vrp at some point in the future.
> 
>>
>>>
>>>
>>> OK.  I don't expect the answers to the minor questions above will
>>> ultimately change anything.
>>
>> I could appreciate a final nod before I commit.  And even then, I will
>> wait until the other patch is approved and commit them simultaneously.
>> They are a bit intertwined.
> I'm nodding :-)

I've tested this patch in isolation, and am committing it while we agree 
on the varying one.

Thank you.

Aldy