This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH] Introduce [sg]et_nonzero_bits


Hi!

On Tue, Oct 29, 2013 at 04:29:56PM +0100, Jakub Jelinek wrote:
> > Surely you can't rely on CCP and VRP compute exactly the same
> > nonzero_bits.  As you don't record/compute zero_bits you can't
> > tell whether a not set bit in nonzer_bits is "don't know" or
> > if it is "zero".  And you cannot do an assert during iteration

Unset bits in get_nonzero_bits are always known to be zero, set bits
are don't know or known to be nonzero.

> > (during iteration optimistically 'wrong' values can disappear).
> > 
> > During CCP iteration the rule is that bits may only be added to mask
> > (and obviously the constant itself on a CONSTANT lattice value may
> > not change).

Here is an untested safer variant of the original patch that attempts
to honor the constraints you've mentioned by looking at get_value
and either making nonzero_bits more conservative or not applying it at
all if the above rules would be violated.  Still, not doing anything
for the !is_constant case, because I don't know what would be the right
thing.  Say, if for iteration we assume some constant value that has some
bits unset in mask (known) and set in value (known non-zero), yet they
are clear in get_nonzero_bits, shall we punt, or ignore what the iteration
would try to do and adjust from get_nonzero_bits instead, something else?

> 
> > Factor this out to commonize with code in evaluate_stmt
> 
> Ok.

But in this more conservative patch I don't see enough code to commonize
any more.

The only change in the patch below since the previous patch is in the
evaluate_stmt function:

2013-10-29  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-29 09:25:38.365478051 +0100
+++ gcc/tree-ssa-ccp.c	2013-10-29 18:02:58.660085620 +0100
@@ -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,48 @@ 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)
+	{
+	  prop_value_t *oldval = get_value (lhs);
+	  if (oldval->lattice_val == VARYING)
+	    nonzero_bits = double_int_minus_one;
+	  else if (oldval->lattice_val == CONSTANT)
+	    {
+	      if (TREE_CODE (oldval->value) != INTEGER_CST)
+		nonzero_bits = double_int_minus_one;
+	      else
+		{
+		  /* Make sure we never remove bits from mask nor
+		     change value.  */
+		  nonzero_bits
+		    |= oldval->mask | tree_to_double_int (oldval->value);
+		  if ((nonzero_bits & mask) == mask)
+		    nonzero_bits = double_int_minus_one;
+		}
+	    }
+	  if (nonzero_bits != double_int_minus_one)
+	    {
+	      val.lattice_val = CONSTANT;
+	      if (oldval->lattice_val == CONSTANT)
+		val.value = oldval->value;
+	      else
+		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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]