Introduce [sg]et_nonzero_bits

On Tue, Oct 29, 2013 at 12:55:04PM +0100, Richard Biener 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
> (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).

> Factor this out to commonize with code in evaluate_stmt

Ok.

> > +	  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);
> 
> This looks odd to me - shouldn't it be simply
> 
>    nonzero_bits = ~val->mask & tree_to_double_int (val->value);

Bits set in the mask are for the bits where the value is unknown,
so potentially nonzero bits.  Where bits are clear in the mask,
but set in the value, those are surely nonzero bits.
The only known zero bits are where both mask and value are zero,
and as nonzero_bits is defined to be 1 where the bit may be non-zero,
0 where it must be zero (like it is for nonzero_bits* in RTL),
I think val->mask | tree_to_double_int (val->value); is exactly
what we want.

> ?  &= of get_nonzero_bits either is not necessary or shows the
> lattice is unnecessarily conservative because you apply it too early
> during propagation?
> 
> > +	  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
> ^^^
> 
> ah, so if the bit-CCP part figured out a set of known bits
> then you don't do anything here while in fact you can
> still remove bits from mask with get_nonzero_bits info.

Yeah, that was not to lose info for the case where the lattice
is already CONSTANT.

Originally, I had code like:

in the patch, but that breaks e.g. on
void
foo (unsigned int a, unsigned b, unsigned **c, void *d[8], int e)
{
  int i;
  for (i = 0; i != e; i++);
  if (a)
    {
      for (i = 0;;)
	{
	  i--;
	  if (bar ())
	    goto lab2;
	}
    lab1:;
      __builtin_printf ("%d\n", i < 0 ? -1 - i : i);
      return;
    }
lab2:;
  if (!d[b] && *c)
    goto lab1;
}
at -O2 - VRP1 figures out:
  if (i_3 < 0)
    goto <bb 10>;
  else
    goto <bb 11>;

  <bb 10>:
  # RANGE [0, 2147483647] NONZERO 0x0000000007fffffff
  iftmp.0_23 = ~i_3;

  <bb 11>:
  # RANGE [0, 2147483647] NONZERO 0x0000000007fffffff
  # iftmp.0_4 = PHI <iftmp.0_23(10), i_3(9)>
through the edge assertions, but CPP of course doesn't have edge
assertions and during iterations just at some point assumes
i_3 can be zero and processes bb 10 with that, which leads
to value -1 that triggers the above assert.  So, I still have
no clue how I could safely add the nonzero_bits info during the iteration
(nor am I 100% sure if even the addition of the info for the VARYING
case in evaluate_stmt is safe, but it at least survived bootstrap/regtest
- even in that case, I bet we could have lattice for some SSA_NAME CONSTANT
with one constant, then drop to VARYING and at that point mix in the
non-zero bits info and set it to different CONSTANT with different mask.

	Jakub

On Tue, 29 Oct 2013, Jakub Jelinek wrote:

> On Tue, Oct 29, 2013 at 12:55:04PM +0100, Richard Biener 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
> > (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).
> 
> > Factor this out to commonize with code in evaluate_stmt
> 
> Ok.
> 
> > > +	  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);
> > 
> > This looks odd to me - shouldn't it be simply
> > 
> >    nonzero_bits = ~val->mask & tree_to_double_int (val->value);
> 
> Bits set in the mask are for the bits where the value is unknown,
> so potentially nonzero bits.  Where bits are clear in the mask,
> but set in the value, those are surely nonzero bits.
> The only known zero bits are where both mask and value are zero,
> and as nonzero_bits is defined to be 1 where the bit may be non-zero,
> 0 where it must be zero (like it is for nonzero_bits* in RTL),
> I think val->mask | tree_to_double_int (val->value); is exactly
> what we want.

Ah, I think I missed that detail (1 in nonzero_bits means
maybe non-zero and 0 means must-be zero) - a bit odd, but yeah,
making it consistent with RTL sounds good.

> > ?  &= of get_nonzero_bits either is not necessary or shows the
> > lattice is unnecessarily conservative because you apply it too early
> > during propagation?
> >
> > > +	  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
> > ^^^
> > 
> > ah, so if the bit-CCP part figured out a set of known bits
> > then you don't do anything here while in fact you can
> > still remove bits from mask with get_nonzero_bits info.
> 
> Yeah, that was not to lose info for the case where the lattice
> is already CONSTANT.

CONSTANT and with mask == 0, sure.  Remember the lattice is
also CONSTANT if only some bits are known.

> Originally, I had code like:
> 
> --- tree-ssa-ccp.c.xx	2013-10-29 15:31:03.000000000 +0100
> +++ tree-ssa-ccp.c	2013-10-29 15:34:44.257977817 +0100
> @@ -1701,8 +1701,7 @@ evaluate_stmt (gimple stmt)
>      }
>  
>    if (flag_tree_bit_ccp
> -      && !is_constant
> -      && likelyvalue != UNDEFINED
> +      && (is_constant || likelyvalue != UNDEFINED)
>        && gimple_get_lhs (stmt)
>        && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME)
>      {
> @@ -1711,11 +1710,27 @@ evaluate_stmt (gimple stmt)
>        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)
> +	    {
> +	      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;
> +	    }
> +	  else
> +	    {
> +	      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);
> +	    }
>  	}
>      }
>  
> in the patch, but that breaks e.g. on
> void
> foo (unsigned int a, unsigned b, unsigned **c, void *d[8], int e)
> {
>   int i;
>   for (i = 0; i != e; i++);
>   if (a)
>     {
>       for (i = 0;;)
> 	{
> 	  i--;
> 	  if (bar ())
> 	    goto lab2;
> 	}
>     lab1:;
>       __builtin_printf ("%d\n", i < 0 ? -1 - i : i);
>       return;
>     }
> lab2:;
>   if (!d[b] && *c)
>     goto lab1;
> }
> at -O2 - VRP1 figures out:
>   if (i_3 < 0)
>     goto <bb 10>;
>   else
>     goto <bb 11>;
> 
>   <bb 10>:
>   # RANGE [0, 2147483647] NONZERO 0x0000000007fffffff
>   iftmp.0_23 = ~i_3;
> 
>   <bb 11>:
>   # RANGE [0, 2147483647] NONZERO 0x0000000007fffffff
>   # iftmp.0_4 = PHI <iftmp.0_23(10), i_3(9)>
> through the edge assertions, but CPP of course doesn't have edge
> assertions and during iterations just at some point assumes
> i_3 can be zero and processes bb 10 with that, which leads
> to value -1 that triggers the above assert.  So, I still have
> no clue how I could safely add the nonzero_bits info during the iteration
> (nor am I 100% sure if even the addition of the info for the VARYING
> case in evaluate_stmt is safe, but it at least survived bootstrap/regtest
> - even in that case, I bet we could have lattice for some SSA_NAME CONSTANT
> with one constant, then drop to VARYING and at that point mix in the
> non-zero bits info and set it to different CONSTANT with different mask.

I think you can safely apply it to all partially-constant or non-constant
lattice values.

Richard.