[PATCH] Introduce [sg]et_nonzero_bits

[Jakub Jelinek <jakub at redhat dot com>]

Hi!

tree-ssa-ccp.c already computes which bits are known to be zero, but
we preserve that info only for pointers and not for integers.
This patch changes SSA_NAME_RANGE_INFO, so we preserve that info even for
integers.  The bitmask is also computed from range info.
There are no users of this besides ccp itself right now, but I'm working
on using that info e.g. in the vectorizer.

I had to tweak one testcase, because it relied on one of the two warnings
being emitted during VRP1 and one during VRP2, but because of the range info
derived nonzero_bits we now manage to optimize away the second test during
CCP3, which doesn't have -Wtype-limits warnings.  If it would be too
important to keep warning even there, I guess it could check get_range_info
when folding a condition to 0/1 and warn if the rhs isn't in the lhs' range.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

During the development of the patch I had there code to not only
use get_range_info if otherwise returning VARYING, but also
if it was already constant, but that failed bootstrap miserably:

It was something along the lines of:

++            /* If get_nonzero_bits tells us some bits
++               have to be zero and they aren't, something
++               went wrong.  Only bits in value where val.mask
++               has zeroes (i.e. valid bit from CCP), mask has ones
++               (don't care about bits outside of precision) and
++               has zeroes in nonzero_bits (guaranteed to be zero)
++               should be verified to be zero.  */
++            double_int valv = tree_to_double_int (val.value);
++            gcc_assert ((valv & ~val.mask
++                         & ~nonzero_bits & mask).is_zero ());
++            if (!(valv & ~nonzero_bits & mask).is_zero ())
++              val.value = double_int_to_tree (TREE_TYPE (lhs),
++                                              valv & nonzero_bits);
++            if (nonzero_bits.is_zero ())
++              val.mask = double_int_zero;
++            else
++              val.mask = val.mask & (nonzero_bits | ~mask);

The problem was that during the iteration when only a subset of the edges
were executable it sometimes failed the assertion, dunno if that is
the result of the nonzero bits info in this case coming from completely
different algorithm (from VRP ranges) and that simply until the CCP
iterations settle it can be wrong, so just to be safe in that case I'm
adding the info only in ccp_finalize (and the new nonzero_bits mask with
the old one).  From what I could see, the range info on that testcase looked
just fine, the nonzero_bits derived from it too, if desirable, I can try to
cook up a small testcase showing that (reduce from libgcov.c that exhibited
that).

2013-10-24  Jakub Jelinek  <jakub@redhat.com>

	* gimple-pretty-print.c (dump_ssaname_info): Print newline also
	in case of VR_VARYING.  Print get_nonzero_bits if not all ones.
	* tree-ssanames.h (struct range_info_def): Add nonzero_bits field.
	(set_nonzero_bits, get_nonzero_bits): New prototypes.
	* tree-ssa-ccp.c (get_default_value): Use get_range_info to see if
	a default def isn't partially constant.
	(ccp_finalize): If after IPA, set_range_info if integral SSA_NAME
	is known to be partially zero.
	(evaluate_stmt): If we'd return otherwise VARYING, use get_range_info
	to see if a default def isn't partially constant.
	* tree-ssanames.c (set_range_info): Initialize nonzero_bits upon
	creation of a range, if VR_RANGE, try to improve nonzero_bits from
	the range.
	(set_nonzero_bits, get_nonzero_bits): New functions.

	* g++.dg/warn/pr33738.C (main): Initialize a2 again to make sure
	we warn about it already during VRP1 pass.

--- gcc/gimple-pretty-print.c.jj	2013-10-23 14:43:12.000000000 +0200
+++ gcc/gimple-pretty-print.c	2013-10-24 17:26:59.650945232 +0200
@@ -1731,7 +1731,7 @@ dump_ssaname_info (pretty_printer *buffe
   if (!POINTER_TYPE_P (TREE_TYPE (node))
       && SSA_NAME_RANGE_INFO (node))
     {
-      double_int min, max;
+      double_int min, max, nonzero_bits;
       value_range_type range_type = get_range_info (node, &min, &max);
 
       if (range_type == VR_VARYING)
@@ -1744,8 +1744,20 @@ dump_ssaname_info (pretty_printer *buffe
 	  pp_printf (buffer, ", ");
 	  pp_double_int (buffer, max, TYPE_UNSIGNED (TREE_TYPE (node)));
 	  pp_printf (buffer, "]");
-	  newline_and_indent (buffer, spc);
 	}
+      nonzero_bits = get_nonzero_bits (node);
+      if (nonzero_bits != double_int_minus_one
+	  && (nonzero_bits
+	      != double_int::mask (TYPE_PRECISION (TREE_TYPE (node)))))
+	{
+	  pp_string (buffer, " NONZERO ");
+	  sprintf (pp_buffer (buffer)->digit_buffer,
+		   HOST_WIDE_INT_PRINT_DOUBLE_HEX,
+		   (unsigned HOST_WIDE_INT) nonzero_bits.high,
+		   nonzero_bits.low);
+	  pp_string (buffer, pp_buffer (buffer)->digit_buffer);
+	}
+      newline_and_indent (buffer, spc);
     }
 }
 
--- gcc/tree-ssanames.h.jj	2013-09-27 15:42:44.000000000 +0200
+++ gcc/tree-ssanames.h	2013-10-24 15:52:53.765955605 +0200
@@ -52,6 +52,8 @@ struct GTY (()) range_info_def {
   double_int min;
   /* Maximum for value range.  */
   double_int max;
+  /* Non-zero bits - bits not set are guaranteed to be always zero.  */
+  double_int nonzero_bits;
 };
 
 
@@ -68,10 +70,11 @@ struct GTY (()) range_info_def {
 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 ssa, double_int min, double_int max);
+extern void set_range_info (tree, double_int, double_int);
 /* Gets the value range from SSA.  */
-extern enum value_range_type  get_range_info (tree name, double_int *min,
-					      double_int *max);
+extern enum value_range_type get_range_info (tree, double_int *, double_int *);
+extern void set_nonzero_bits (tree, double_int);
+extern double_int get_nonzero_bits (tree);
 extern void init_ssanames (struct function *, int);
 extern void fini_ssanames (void);
 extern void ssanames_print_statistics (void);
--- gcc/tree-ssa-ccp.c.jj	2013-10-23 14:43:15.000000000 +0200
+++ gcc/tree-ssa-ccp.c	2013-10-24 21:16:48.673330359 +0200
@@ -260,6 +260,19 @@ get_default_value (tree var)
 	{
 	  val.lattice_val = VARYING;
 	  val.mask = double_int_minus_one;
+	  if (flag_tree_bit_ccp)
+	    {
+	      double_int nonzero_bits = get_nonzero_bits (var);
+	      double_int mask
+		= double_int::mask (TYPE_PRECISION (TREE_TYPE (var)));
+	      if (nonzero_bits != double_int_minus_one && nonzero_bits != mask)
+		{
+		  val.lattice_val = CONSTANT;
+		  val.value = build_zero_cst (TREE_TYPE (var));
+		  /* CCP wants the bits above precision set.  */
+		  val.mask = nonzero_bits | ~mask;
+		}
+	    }
 	}
     }
   else if (is_gimple_assign (stmt))
@@ -828,7 +841,8 @@ ccp_finalize (void)
   do_dbg_cnt ();
 
   /* Derive alignment and misalignment information from partially
-     constant pointers in the lattice.  */
+     constant pointers in the lattice or nonzero bits from partially
+     constant integers.  */
   for (i = 1; i < num_ssa_names; ++i)
     {
       tree name = ssa_name (i);
@@ -836,7 +850,11 @@ ccp_finalize (void)
       unsigned int tem, align;
 
       if (!name
-	  || !POINTER_TYPE_P (TREE_TYPE (name)))
+	  || (!POINTER_TYPE_P (TREE_TYPE (name))
+	      && (!INTEGRAL_TYPE_P (TREE_TYPE (name))
+		  /* Don't record nonzero bits before IPA to avoid
+		     using too much memory.  */
+		  || first_pass_instance)))
 	continue;
 
       val = get_value (name);
@@ -844,13 +862,24 @@ ccp_finalize (void)
 	  || TREE_CODE (val->value) != INTEGER_CST)
 	continue;
 
-      /* Trailing constant bits specify the alignment, trailing value
-	 bits the misalignment.  */
-      tem = val->mask.low;
-      align = (tem & -tem);
-      if (align > 1)
-	set_ptr_info_alignment (get_ptr_info (name), align,
-				TREE_INT_CST_LOW (val->value) & (align - 1));
+      if (POINTER_TYPE_P (TREE_TYPE (name)))
+	{
+	  /* Trailing mask bits specify the alignment, trailing value
+	     bits the misalignment.  */
+	  tem = val->mask.low;
+	  align = (tem & -tem);
+	  if (align > 1)
+	    set_ptr_info_alignment (get_ptr_info (name), align,
+				    (TREE_INT_CST_LOW (val->value)
+				     & (align - 1)));
+	}
+      else
+	{
+	  double_int nonzero_bits = val->mask;
+	  nonzero_bits = nonzero_bits | tree_to_double_int (val->value);
+	  nonzero_bits &= get_nonzero_bits (name);
+	  set_nonzero_bits (name, nonzero_bits);
+	}
     }
 
   /* Perform substitutions based on the known constant values.  */
@@ -1671,6 +1700,25 @@ evaluate_stmt (gimple stmt)
       is_constant = (val.lattice_val == CONSTANT);
     }
 
+  if (flag_tree_bit_ccp
+      && !is_constant
+      && likelyvalue != UNDEFINED
+      && gimple_get_lhs (stmt)
+      && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME)
+    {
+      tree lhs = gimple_get_lhs (stmt);
+      double_int nonzero_bits = get_nonzero_bits (lhs);
+      double_int mask = double_int::mask (TYPE_PRECISION (TREE_TYPE (lhs)));
+      if (nonzero_bits != double_int_minus_one && nonzero_bits != mask)
+	{
+	  val.lattice_val = CONSTANT;
+	  val.value = build_zero_cst (TREE_TYPE (lhs));
+	  /* CCP wants the bits above precision set.  */
+	  val.mask = nonzero_bits | ~mask;
+	  is_constant = true;
+	}
+    }
+
   if (!is_constant)
     {
       /* The statement produced a nonconstant value.  If the statement
--- gcc/tree-ssanames.c.jj	2013-10-23 14:43:16.000000000 +0200
+++ gcc/tree-ssanames.c	2013-10-24 17:32:22.127281080 +0200
@@ -189,11 +189,30 @@ set_range_info (tree name, double_int mi
     {
       ri = ggc_alloc_cleared_range_info_def ();
       SSA_NAME_RANGE_INFO (name) = ri;
+      ri->nonzero_bits = double_int::mask (TYPE_PRECISION (TREE_TYPE (name)));
     }
 
   /* 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)
+    {
+      int prec = TYPE_PRECISION (TREE_TYPE (name));
+      double_int xorv;
+
+      min = min.zext (prec);
+      max = max.zext (prec);
+      xorv = min ^ 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);
+    }
 }
 
 
@@ -233,6 +252,47 @@ get_range_info (tree name, double_int *m
   return range_type;
 }
 
+/* Change non-zero bits bitmask of NAME.  */
+
+void
+set_nonzero_bits (tree name, double_int mask)
+{
+  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))));
+  range_info_def *ri = SSA_NAME_RANGE_INFO (name);
+  ri->nonzero_bits
+    = mask & double_int::mask (TYPE_PRECISION (TREE_TYPE (name)));
+}
+
+/* Return a double_int with potentially non-zero bits in SSA_NAME
+   NAME, or double_int_minus_one if unknown.  */
+
+double_int
+get_nonzero_bits (tree name)
+{
+  if (POINTER_TYPE_P (TREE_TYPE (name)))
+    {
+      struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
+      if (pi && pi->align)
+	{
+	  double_int al = double_int::from_uhwi (pi->align - 1);
+	  return ((double_int::mask (TYPE_PRECISION (TREE_TYPE (name))) & ~al)
+		  | double_int::from_uhwi (pi->misalign));
+	}
+      return double_int_minus_one;
+    }
+
+  range_info_def *ri = SSA_NAME_RANGE_INFO (name);
+  if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name)))
+	      > 2 * HOST_BITS_PER_WIDE_INT))
+    return double_int_minus_one;
+
+  return ri->nonzero_bits;
+}
+
 /* We no longer need the SSA_NAME expression VAR, release it so that
    it may be reused.
 
--- gcc/testsuite/g++.dg/warn/pr33738.C.jj	2010-05-04 12:02:18.000000000 +0200
+++ gcc/testsuite/g++.dg/warn/pr33738.C	2013-10-25 08:52:24.052881493 +0200
@@ -18,6 +18,7 @@ int main() {
  if (a2 == -1) {	// { dg-warning "always false due" }
     link_error ();
  }
+ a2 = static_cast<Alpha>(GetM1());
  if (-1 == a2) {	// { dg-warning "always false due" }
     link_error ();
  }

	Jakub