Re: wide-int, gimple

[Richard Sandiford <rdsandiford at googlemail dot com>]

Jakub Jelinek <jakub@redhat.com> writes:
> On Mon, Nov 25, 2013 at 09:16:24PM +0000, Richard Sandiford wrote:
>> > Well, the range_info_def struct right now contains 3 double_ints, which is
>> > unnecessary overhead for the most of the cases where the SSA_NAME's type
>> > has just at most HOST_BITS_PER_WIDE_INT bits and thus we could fit all 3 of
>> > them into 3 HOST_WIDE_INTs rather than 3 double_ints.  So supposedly struct
>> > range_info_def could be a template on the type's precision rounded up to HWI
>> > bits, or say have 3 alternatives there, use
>> > FIXED_WIDE_INT (HOST_BITS_PER_WIDE_INT) for the smallest types,
>> > FIXED_WIDE_INT (2 * HOST_BITS_PER_WIDE_INT) aka double_int for the larger
>> > but still common ones, and widest_int for the rest, then the API to set/get
>> > it could use widest_int everywhere, and just what storage we'd use would
>> > depend on the precision of the type.
>> 
>> Would it make sense to just use trees for the min and max?
>
> Note, we don't have just min/max, but also nonzero_bits.

Right, that would need to be dealt with separately.  But if min and max
are trees then we have just one widest_int, which can be a trailing structure.

> Anyway, I don't think that is a good idea, you can fairly often end up with
> values that can't be shared with something else, and the overhead of
> INTEGER_CST is quite large then.

But my point is that at the moment we always have trees for the ranges
we want to record, so it seems simplest just to store those in the
structure.  I was thinking of something like the attached (only just
started testing, no changelog yet).

> range_info_def could very well be just struct with HOST_WIDE_INT flexible
> array member or just array of HOST_WIDE_INTs, all the routines that care
> about the internal details of the representation are in tree-ssanames.c
> - [sg]et_range_info, [sg]et_nonzero_bits and
> duplicate_ssa_name_range_info/duplicate_ssa_name_fn.  All of those
> work solely for INTEGRAL_TYPE_P tree types of SSA_NAMEs, and all the
> functions have access to the SSA_NAME from which you can find out the
> precision.

Yeah, I was just hoping to keep it simple :-)  But if the patch below
is a no-go then I'll look into it.

Thanks,
Richard


Index: gcc/tree-core.h
===================================================================
--- gcc/tree-core.h	2013-11-25 21:37:12.205346686 +0000
+++ gcc/tree-core.h	2013-11-25 21:37:12.581349611 +0000
@@ -822,6 +822,9 @@ struct GTY(()) tree_base {
        TRANSACTION_EXPR_OUTER in
 	   TRANSACTION_EXPR
 
+       SSA_NAME_ANTI_RANGE_P in
+	   SSA_NAME
+
    public_flag:
 
        TREE_OVERFLOW in
Index: gcc/tree-ssanames.c
===================================================================
--- gcc/tree-ssanames.c	2013-11-25 21:37:12.206346696 +0000
+++ gcc/tree-ssanames.c	2013-11-25 21:38:02.895739211 +0000
@@ -183,12 +183,14 @@ make_ssa_name_fn (struct function *fn, t
   return t;
 }
 
-/* Store range information MIN, and MAX to tree ssa_name NAME.  */
+/* Store range information RANGE_TYPE, MIN, and MAX to tree ssa_name NAME.  */
 
 void
-set_range_info (tree name, double_int min, double_int max)
+set_range_info (tree name, enum value_range_type range_type,
+		tree min, tree max)
 {
   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
+  gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE);
   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
 
   /* Allocate if not available.  */
@@ -199,26 +201,30 @@ set_range_info (tree name, double_int mi
       ri->nonzero_bits = double_int::mask (TYPE_PRECISION (TREE_TYPE (name)));
     }
 
+  /* Record the range type.  */
+  if (SSA_NAME_RANGE_TYPE (name) != range_type)
+    SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE);
+
   /* Set the values.  */
   ri->min = min;
   ri->max = max;
 
   /* If it is a range, try to improve nonzero_bits from the min/max.  */
-  if (min.cmp (max, TYPE_UNSIGNED (TREE_TYPE (name))) != 1)
+  if (range_type == VR_RANGE)
     {
       int prec = TYPE_PRECISION (TREE_TYPE (name));
       double_int xorv;
 
-      min = min.zext (prec);
-      max = max.zext (prec);
-      xorv = min ^ max;
+      double_int ext_min = tree_to_double_int (min).zext (prec);
+      double_int ext_max = tree_to_double_int (max).zext (prec);
+      xorv = ext_min ^ ext_max;
       if (xorv.high)
 	xorv = double_int::mask (2 * HOST_BITS_PER_WIDE_INT
 				 - clz_hwi (xorv.high));
       else if (xorv.low)
 	xorv = double_int::mask (HOST_BITS_PER_WIDE_INT
 				 - clz_hwi (xorv.low));
-      ri->nonzero_bits = ri->nonzero_bits & (min | xorv);
+      ri->nonzero_bits = ri->nonzero_bits & (ext_min | xorv);
     }
 }
 
@@ -230,7 +236,6 @@ set_range_info (tree name, double_int mi
 enum value_range_type
 get_range_info (const_tree name, double_int *min, double_int *max)
 {
-  enum value_range_type range_type;
   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
   gcc_assert (min && max);
   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
@@ -241,22 +246,9 @@ get_range_info (const_tree name, double_
 	      > 2 * HOST_BITS_PER_WIDE_INT))
     return VR_VARYING;
 
-  /* If min > max, it is VR_ANTI_RANGE.  */
-  if (ri->min.cmp (ri->max, TYPE_UNSIGNED (TREE_TYPE (name))) == 1)
-    {
-      /* VR_ANTI_RANGE ~[min, max] is encoded as [max + 1, min - 1].  */
-      range_type = VR_ANTI_RANGE;
-      *min = ri->max + double_int_one;
-      *max = ri->min - double_int_one;
-    }
-  else
-  {
-    /* Otherwise (when min <= max), it is VR_RANGE.  */
-    range_type = VR_RANGE;
-    *min = ri->min;
-    *max = ri->max;
-  }
-  return range_type;
+  *min = tree_to_double_int (ri->min);
+  *max = tree_to_double_int (ri->max);
+  return SSA_NAME_RANGE_TYPE (name);
 }
 
 /* Change non-zero bits bitmask of NAME.  */
@@ -266,9 +258,8 @@ set_nonzero_bits (tree name, double_int
 {
   gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
   if (SSA_NAME_RANGE_INFO (name) == NULL)
-    set_range_info (name,
-		    tree_to_double_int (TYPE_MIN_VALUE (TREE_TYPE (name))),
-		    tree_to_double_int (TYPE_MAX_VALUE (TREE_TYPE (name))));
+    set_range_info (name, VR_RANGE, TYPE_MIN_VALUE (TREE_TYPE (name)),
+		    TYPE_MAX_VALUE (TREE_TYPE (name)));
   range_info_def *ri = SSA_NAME_RANGE_INFO (name);
   ri->nonzero_bits
     = mask & double_int::mask (TYPE_PRECISION (TREE_TYPE (name)));
Index: gcc/tree-ssanames.h
===================================================================
--- gcc/tree-ssanames.h	2013-11-25 21:37:12.206346696 +0000
+++ gcc/tree-ssanames.h	2013-11-25 21:37:12.582349619 +0000
@@ -49,9 +49,9 @@ struct GTY(()) ptr_info_def
 
 struct GTY (()) range_info_def {
   /* Minimum for value range.  */
-  double_int min;
+  tree min;
   /* Maximum for value range.  */
-  double_int max;
+  tree max;
   /* Non-zero bits - bits not set are guaranteed to be always zero.  */
   double_int nonzero_bits;
 };
@@ -70,7 +70,7 @@ #define ssa_name(i) ((*cfun->gimple_df->
 enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING };
 
 /* Sets the value range to SSA.  */
-extern void set_range_info (tree, double_int, double_int);
+extern void set_range_info (tree, enum value_range_type, tree, tree);
 /* Gets the value range from SSA.  */
 extern enum value_range_type get_range_info (const_tree, double_int *,
 					     double_int *);
Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c	2013-11-25 21:37:12.208346720 +0000
+++ gcc/tree-vrp.c	2013-11-25 21:37:12.583349627 +0000
@@ -6588,7 +6588,8 @@ remove_range_assertions (void)
 		    && all_imm_uses_in_stmt_or_feed_cond (var, stmt,
 							  single_pred (bb)))
 		  {
-		    set_range_info (var, SSA_NAME_RANGE_INFO (lhs)->min,
+		    set_range_info (var, SSA_NAME_RANGE_TYPE (lhs),
+				    SSA_NAME_RANGE_INFO (lhs)->min,
 				    SSA_NAME_RANGE_INFO (lhs)->max);
 		    maybe_set_nonzero_bits (bb, var);
 		  }
@@ -9594,36 +9595,11 @@ vrp_finalize (void)
 	continue;
 
 	if ((TREE_CODE (vr_value[i]->min) == INTEGER_CST)
-	    && (TREE_CODE (vr_value[i]->max) == INTEGER_CST))
-	  {
-	    if (vr_value[i]->type == VR_RANGE)
-	      set_range_info (name,
-			      tree_to_double_int (vr_value[i]->min),
-			      tree_to_double_int (vr_value[i]->max));
-	    else if (vr_value[i]->type == VR_ANTI_RANGE)
-	      {
-		/* VR_ANTI_RANGE ~[min, max] is encoded compactly as
-		   [max + 1, min - 1] without additional attributes.
-		   When min value > max value, we know that it is
-		   VR_ANTI_RANGE; it is VR_RANGE otherwise.  */
-
-		/* ~[0,0] anti-range is represented as
-		   range.  */
-		if (TYPE_UNSIGNED (TREE_TYPE (name))
-		    && integer_zerop (vr_value[i]->min)
-		    && integer_zerop (vr_value[i]->max))
-		  set_range_info (name,
-				  double_int_one,
-				  double_int::max_value
-				  (TYPE_PRECISION (TREE_TYPE (name)), true));
-		else
-		  set_range_info (name,
-				  tree_to_double_int (vr_value[i]->max)
-				  + double_int_one,
-				  tree_to_double_int (vr_value[i]->min)
-				  - double_int_one);
-	      }
-	  }
+	    && (TREE_CODE (vr_value[i]->max) == INTEGER_CST)
+	    && (vr_value[i]->type == VR_RANGE
+		|| vr_value[i]->type == VR_ANTI_RANGE))
+	  set_range_info (name, vr_value[i]->type, vr_value[i]->min,
+			  vr_value[i]->max);
       }
 
   /* Free allocated memory.  */
Index: gcc/tree.h
===================================================================
--- gcc/tree.h	2013-11-25 21:37:12.209346731 +0000
+++ gcc/tree.h	2013-11-25 21:52:01.523293851 +0000
@@ -1432,6 +1432,14 @@ #define SSA_NAME_IS_DEFAULT_DEF(NODE) \
 #define SSA_NAME_PTR_INFO(N) \
    SSA_NAME_CHECK (N)->ssa_name.info.ptr_info
 
+/* True if SSA_NAME_RANGE_INFO describes an anti-range.  */
+#define SSA_NAME_ANTI_RANGE_P(N) \
+    SSA_NAME_CHECK (N)->base.static_flag
+
+/* The type of range described by SSA_NAME_RANGE_INFO.  */
+#define SSA_NAME_RANGE_TYPE(N) \
+    (SSA_NAME_ANTI_RANGE_P (N) ? VR_ANTI_RANGE : VR_RANGE)
+
 /* Value range info attributes for SSA_NAMEs of non pointer-type variables.  */
 #define SSA_NAME_RANGE_INFO(N) \
     SSA_NAME_CHECK (N)->ssa_name.info.range_info