Re: [RFC] ipa bitwise constant propagation

[Richard Biener <rguenther@suse.de>]

On Tue, 9 Aug 2016, Prathamesh Kulkarni wrote:

> On 8 August 2016 at 19:33, Martin Jambor <mjambor@suse.cz> wrote:
> > Hi,
> >
> > thanks for following through.  You'll need an approval from Honza, but
> > I think the code looks good (I have looked at the places that I
> > believe have changed since the last week).  However, I have discovered
> > one new thing I don't like and still believe you need to handle
> > different precisions in lattice need:
> >
> > On Mon, Aug 08, 2016 at 03:08:35AM +0530, Prathamesh Kulkarni wrote:
> >> On 5 August 2016 at 18:06, Martin Jambor <mjambor@suse.cz> wrote:
> >>
> >> ...
> >>
> >> >> diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c
> >> >> index 5b6cb9a..b770f6a 100644
> >> >> --- a/gcc/ipa-cp.c
> >> >> +++ b/gcc/ipa-cp.c
> >> >> @@ -120,6 +120,7 @@ along with GCC; see the file COPYING3.  If not see
> >> >>  #include "params.h"
> >> >>  #include "ipa-inline.h"
> >> >>  #include "ipa-utils.h"
> >> >> +#include "tree-ssa-ccp.h"
> >> >>
> >> >>  template <typename valtype> class ipcp_value;
> >> >>
> >> >> @@ -266,6 +267,40 @@ private:
> >> >>    bool meet_with_1 (unsigned new_align, unsigned new_misalign);
> >> >>  };
> >> >>
> >> >> +/* Lattice of known bits, only capable of holding one value.
> >> >> +   Similar to ccp_prop_value_t, mask represents which bits of value are constant.
> >> >> +   If a bit in mask is set to 0, then the corresponding bit in
> >> >> +   value is known to be constant.  */
> >> >> +
> >> >> +class ipcp_bits_lattice
> >> >> +{
> >> >> +public:
> >> >> +  bool bottom_p () { return lattice_val == IPA_BITS_VARYING; }
> >> >> +  bool top_p () { return lattice_val == IPA_BITS_UNDEFINED; }
> >> >> +  bool constant_p () { return lattice_val == IPA_BITS_CONSTANT; }
> >> >> +  bool set_to_bottom ();
> >> >> +  bool set_to_constant (widest_int, widest_int, signop, unsigned);
> >> >> +
> >> >> +  widest_int get_value () { return value; }
> >> >> +  widest_int get_mask () { return mask; }
> >> >> +  signop get_sign () { return sgn; }
> >> >> +  unsigned get_precision () { return precision; }
> >> >> +
> >> >> +  bool meet_with (ipcp_bits_lattice& other, enum tree_code, tree);
> >> >> +  bool meet_with (widest_int, widest_int, signop, unsigned);
> >> >> +
> >> >> +  void print (FILE *);
> >> >> +
> >> >> +private:
> >> >> +  enum { IPA_BITS_UNDEFINED, IPA_BITS_CONSTANT, IPA_BITS_VARYING } lattice_val;
> >> >> +  widest_int value, mask;
> >> >> +  signop sgn;
> >> >> +  unsigned precision;
> >
> > I know that the existing code in ipa-cp.c does not do this, but please
> > prefix member variables with "m_" like our coding style guidelines
> > suggest (or even require?).  You routinely reuse those same names in
> > names of parameters of meet_with and I believe that is a practice that
> > will sooner or later lead to confusing the two and bugs.
> Sorry about this, will change to m_ prefix in followup patch.
> >
> >> >> +
> >> >> +  bool meet_with_1 (widest_int, widest_int);
> >> >> +  void get_value_and_mask (tree, widest_int *, widest_int *);
> >> >> +};
> >> >> +
> >> >>  /* Structure containing lattices for a parameter itself and for pieces of
> >> >>     aggregates that are passed in the parameter or by a reference in a parameter
> >> >>     plus some other useful flags.  */
> >> >> @@ -281,6 +316,8 @@ public:
> >> >>    ipcp_agg_lattice *aggs;
> >> >>    /* Lattice describing known alignment.  */
> >> >>    ipcp_alignment_lattice alignment;
> >> >> +  /* Lattice describing known bits.  */
> >> >> +  ipcp_bits_lattice bits_lattice;
> >> >>    /* Number of aggregate lattices */
> >> >>    int aggs_count;
> >> >>    /* True if aggregate data were passed by reference (as opposed to by
> >> >> @@ -458,6 +495,21 @@ ipcp_alignment_lattice::print (FILE * f)
> >> >>      fprintf (f, "         Alignment %u, misalignment %u\n", align, misalign);
> >> >>  }
> >> >>
> >>
> >> ...
> >>
> >> >> +/* Convert operand to value, mask form.  */
> >> >> +
> >> >> +void
> >> >> +ipcp_bits_lattice::get_value_and_mask (tree operand, widest_int *valuep, widest_int *maskp)
> >> >> +{
> >> >> +  wide_int get_nonzero_bits (const_tree);
> >> >> +
> >> >> +  if (TREE_CODE (operand) == INTEGER_CST)
> >> >> +    {
> >> >> +      *valuep = wi::to_widest (operand);
> >> >> +      *maskp = 0;
> >> >> +    }
> >> >> +  else if (TREE_CODE (operand) == SSA_NAME)
> >> >
> >> > IIUC, operand is the operand from pass-through jump function and that
> >> > should never be an SSA_NAME.  I have even looked at how we generate
> >> > them and it seems fairly safe to say that they never are.  If you have
> >> > seen an SSA_NAME here, it is a bug and please let me know because
> >> > sooner or later it will cause an assert.
> >> >
> >> >> +    {
> >> >> +      *valuep = 0;
> >> >> +      *maskp = widest_int::from (get_nonzero_bits (operand), UNSIGNED);
> >> >> +    }
> >> >> +  else
> >> >> +    gcc_unreachable ();
> >> >
> >> > The operand however can be any any other is_gimple_ip_invariant tree.
> >> > I assume that you could hit this gcc_unreachable only in a program
> >> > with undefined behavior (or with a Fortran CONST_DECL?) but you should
> >> > not ICE here.
> >> Changed to:
> >> if (TREE_CODE (operand) == INTEGER_CST)
> >>     {
> >>       *valuep = wi::to_widest (operand);
> >>       *maskp = 0;
> >>     }
> >>   else
> >>     {
> >>       *valuep = 0;
> >>       *maskp = -1;
> >>     }
> >>
> >> I am not sure how to extract nonzero bits for gimple_ip_invariant if
> >> it's not INTEGER_CST,
> >
> > I don't think that you reasonably can.
> >
> >> so setting to unknown (value = 0, mask = -1).
> >> Does this look OK ?
> >
> > Yes.
> >
> >> >
> >> >
> >> >> +}
> >> >> +
> >> >> +/* Meet operation, similar to ccp_lattice_meet, we xor values
> >> >> +   if this->value, value have different values at same bit positions, we want
> >> >> +   to drop that bit to varying. Return true if mask is changed.
> >> >> +   This function assumes that the lattice value is in CONSTANT state  */
> >> >> +
> >> >> +bool
> >> >> +ipcp_bits_lattice::meet_with_1 (widest_int value, widest_int mask)
> >> >> +{
> >> >> +  gcc_assert (constant_p ());
> >> >> +
> >> >> +  widest_int old_mask = this->mask;
> >> >> +  this->mask = (this->mask | mask) | (this->value ^ value);
> >> >> +
> >> >> +  if (wi::sext (this->mask, this->precision) == -1)
> >> >> +    return set_to_bottom ();
> >> >> +
> >> >> +  bool changed = this->mask != old_mask;
> >> >> +  return changed;
> >> >> +}
> >> >> +
> >> >> +/* Meet the bits lattice with operand
> >> >> +   described by <value, mask, sgn, precision.  */
> >> >> +
> >> >> +bool
> >> >> +ipcp_bits_lattice::meet_with (widest_int value, widest_int mask,
> >> >> +                           signop sgn, unsigned precision)
> >> >> +{
> >> >> +  if (bottom_p ())
> >> >> +    return false;
> >> >> +
> >> >> +  if (top_p ())
> >> >> +    {
> >> >> +      if (wi::sext (mask, precision) == -1)
> >> >> +     return set_to_bottom ();
> >> >> +      return set_to_constant (value, mask, sgn, precision);
> >> >> +    }
> >> >> +
> >> >> +  return meet_with_1 (value, mask);
> >> >
> >> > What if precisions do not match?
> >> Sorry I don't understand. Since we extend to widest_int, precision
> >> would be same ?
> >
> > I meant what if:
> >
> >   this->precision != precision /* the parameter value */
> >
> > (you see, giving both the same name is error-prone).  You are
> > propagating the recorded precision gathered from types of the actual
> > arguments in calls, those can be different.  For example, one caller
> > can pass a direct integer value with full integer precision, another
> > caller can pass in that same argument an enum value with a very
> > limited precision.  Your code ignores that difference and the
> > resulting precision is the one that arrives first.  If it is the enum,
> > it might be too small for the integer value from the other call-site?
> Ah indeed the patch incorrectly propagates precision of argument.
> So IIUC in ipcp_bits_lattice, we want m_precision to be the precision
> of parameter's type and _not_ of argument's type.
> 
> The patch incorrectly propagates precision in following case:
> 
> __attribute__((noinline))
> static int f2(short z)
> {
>   return z;
> }
> 
> __attribute__((noinline))
> static int f1(int y)
> {
>   return f2 (y & 0xff);
> }
> 
> __attribute__((noinline))
> int f(int x)
> {
>   return f1 (x);
> }
> 
> Precision for 'z' should be 16 while the patch propagates 32, which
> is precision of type of the argument passed by the caller.
> We only set m_precision when changing from TOP to CONSTANT
> state.
> 
> Instead of storing arg's precision and sign, we should store
> parameter's precision and sign in ipa_compute_jump_functions_for_edge ().
> Diff with respect to previous patch:
> 
> @@ -1688,9 +1690,9 @@ ipa_compute_jump_functions_for_edge (struct
> ipa_func_body_info *fbi,
>    && (TREE_CODE (arg) == SSA_NAME || TREE_CODE (arg) == INTEGER_CST))
>   {
>    jfunc->bits.known = true;
> -  jfunc->bits.sgn = TYPE_SIGN (TREE_TYPE (arg));
> -  jfunc->bits.precision = TYPE_PRECISION (TREE_TYPE (arg));
> -
> +  jfunc->bits.sgn = TYPE_SIGN (param_type);
> +  jfunc->bits.precision = TYPE_PRECISION (param_type);
> +
>    if (TREE_CODE (arg) == SSA_NAME)
>      {
>        jfunc->bits.value = 0;
> 
> So in ipcp_bits_lattice::meet_with(value, mask, signop, precision)
> when we propagate into
> parameter's lattice for first time, we will set m_precision ==
> precision of it's own type.
> rather than precision of the argument
> 
> For eg, consider following test-case:
> int f(int x)
> {
>   return some_operation (x);
> }
> 
> int f1(short y)
> {
>   return f (y & 0xf);
> }
> 
> int f2(char z)
> {
>   return f (z & 0xff);
> }
> 
> Assume we first propagate from f2->f.
> In this case, jump_function from f2->f is unknown (but bits.known is true),
> so we call meet_with (0, 0xff, SIGNED, 32).
> The precision and sign are of param's type because we extract them
> from param_type as shown above.
> 
> (I suppose the reason this is not pass-thru is because result y & 0xf
> is wrapped by convert_expr,
> which is actually passed to f(), so the parameter y isn't really
> involved in the call to f ?)
> 
> Since lattice of x is TOP, it will change to CONSTANT,
> and m_precision will get assigned 32.
> 
> Next propagate from f1->f
> jump_function from f1->f is unknown (but bits.known is true)
> so we call meet_with (0, 0xf, 32, SIGNED).
> Since lattice of x is already CONSTANT, it doesn't change m_precision anymore
> on this call or any subsequent calls.
> 
> So when we propagate into callee for first time, only then do we set
> the precision.
> Does this look reasonable ?

Just to chime in, please try to produce dg-do run testcase(s) for
the cases you show above that are handled wrong and add them to the
testsuite with the patch.

Richard.

> >
> >> bit_value_binop_1 requires original precision for few cases (shifts,
> >> rotates, plus, mult), so
> >
> > Yeah, so wrong precision could only be used if it got fed into the
> > binary operation routines, making the bug much harder to trigger.  But
> > it would still be a bug (or you do not need to care for original
> > precisions at all).
> >
> >> I was preserving the original precision in jump function.
> >> Later in ipcp_update_bits(), the mask is set after narrowing to the
> >> precision of the parameter.
> >> >
> >> >> +}
> >> >> +
> >> >> +/* Meet bits lattice with the result of bit_value_binop_1 (other, operand)
> >> >> +   if code is binary operation or bit_value_unop_1 (other) if code is unary op.
> >> >> +   In the case when code is nop_expr, no adjustment is required. */
> >> >> +
> >> >> +bool
> >> >> +ipcp_bits_lattice::meet_with (ipcp_bits_lattice& other, enum tree_code code, tree operand)
> >> >> +{
> >> >> +  if (other.bottom_p ())
> >> >> +    return set_to_bottom ();
> >> >> +
> >> >> +  if (bottom_p () || other.top_p ())
> >> >> +    return false;
> >> >> +
> >> >> +  widest_int adjusted_value, adjusted_mask;
> >> >> +
> >> >> +  if (TREE_CODE_CLASS (code) == tcc_binary)
> >> >> +    {
> >> >> +      tree type = TREE_TYPE (operand);
> >> >> +      gcc_assert (INTEGRAL_TYPE_P (type));
> >> >> +      widest_int o_value, o_mask;
> >> >> +      get_value_and_mask (operand, &o_value, &o_mask);
> >> >> +
> >> >> +      signop sgn = other.get_sign ();
> >> >> +      unsigned prec = other.get_precision ();
> >> >> +
> >> >> +      bit_value_binop_1 (code, sgn, prec, &adjusted_value, &adjusted_mask,
> >> >> +                      sgn, prec, other.get_value (), other.get_mask (),
> >> >> +                      TYPE_SIGN (type), TYPE_PRECISION (type), o_value, o_mask);
> >> >
> >> > It is probably just me not being particularly sharp on a Friday
> >> > afternoon and I might not understand the semantics of mask well (also,
> >> > you did not document it :-), but... assume that we are looking at a
> >> > binary and operation, other comes from an SSA pointer and its mask
> >> > would be binary 100 and its value 0 because that's what you set for
> >> > ssa names in ipa-prop.h, and the operand is binary value 101, which
> >> > means that get_value_and_mask returns mask 0 and value 101.  Now,
> >> > bit_value_binop_1 would return value 0 & 101 = 0 and mask according to
> >> >
> >> > (m1 | m2) & ((v1 | m1) & (v2 | m2))
> >> >
> >> > so in our case
> >> >
> >> > (100b & 0) & ((0 | 100b) & (101b | 0)) = 0 & 100b = 0.
> >> Shouldn't this be:
> >> (100b | 0) & ((0 | 100b) & (101b | 0)) = 100 & 100 = 100 -;)
> >
> > Eh, right, sorry.  I just find the term mask confusing when we do not
> > actually mask anything with it (but I guess it is good to be
> > consistent so let's keep it).
> >
> >> diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h
> >> index e32d078..1b9d0ef 100644
> >> --- a/gcc/ipa-prop.h
> >> +++ b/gcc/ipa-prop.h
> >> @@ -154,6 +154,23 @@ struct GTY(()) ipa_alignment
> >>    unsigned misalign;
> >>  };
> >>
> >> +/* Information about zero/non-zero bits.  */
> >> +struct GTY(()) ipa_bits
> >> +{
> >> +  /* The propagated value.  */
> >> +  widest_int value;
> >> +  /* Mask corresponding to the value.
> >> +     Similar to ccp_prop_t, if xth bit of mask is 0,
> >
> > Is ccp_prop_t a typo? I did not find it anywhere when I grepped for it.
> ah, it's ccp_lattice_t -;)
> 
> Thanks,
> Prathamesh
> >
> > Thanks,
> >
> > Martin
> >
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)