[RFC] ipa bitwise constant propagation

[Martin Jambor]

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.

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

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

Thanks,

Martin