Re: [PATCH] Introduce [sg]et_nonzero_bits

[Richard Biener <rguenther at suse dot de>]

On Tue, 29 Oct 2013, Jakub Jelinek wrote:

> 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?

Well, you'd unconditionally make the lattice value "more constant"
using get_nonzero_bits (which doesn't change during iteration).
If it is applied consistently then convergence shouldn't change.
So as how get_nonzero_bits works you can only force the kown
zero bits to the lattice.  You don't need to be concerned about
invalid lattice transitions as with always applying a constant
op you'll never get those.  [and if you'd ever arrive at
get_nonzero_bits saying that a bit is zero but the lattice
value is not zero in that bit you have the choice of dropping
to don't know for that bit or enforcing the zeroness of the
bit by changing the lattice value as well as its mask]

Richard.

> > 
> > > 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
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend