Re: [RFC] ipa bitwise constant propagation

[Prathamesh Kulkarni <prathamesh dot kulkarni at linaro dot org>]

On 9 August 2016 at 16:39, Martin Jambor <mjambor@suse.cz> wrote:
> Hi,
>
> On Tue, Aug 09, 2016 at 01:41:21PM +0530, Prathamesh Kulkarni wrote:
>> On 8 August 2016 at 19:33, Martin Jambor <mjambor@suse.cz> wrote:
>> >> >> +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.
>
> Thanks a lot.
>
>> >
>> >> >> +
>> >> >> +  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);
>> >> >>  }
>> >> >>
>> >>
>> >> ...
>> >>
>> >> >> +}
>> >> >> +
>> >> >> +/* 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.
>
> That is true but you never use precison of z (in this example), do
> you?  You would only use a precision from a jump function of y in
> meet_with if there was a pass-through function, am I right?
Yes, the example was artificial.
>
>> 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 you want to use the precision of the formal parameter then you do
> not need to store it to jump functions.  Parameter DECLs along with
> their types are readily accessible in IPA (even with LTO).  It would
> also be much clearer what is going on, IMHO.
Could you please point out how to access parameter decl in wpa ?
The only reason I ended up putting this in jump function was because
I couldn't figure out how to access param decl during WPA.
I see there's ipa_get_param() in ipa-prop.h however it's gated on
gcc_checking_assert (!flag_wpa), so I suppose I can't use this
during WPA ?

Alternatively I think I could access cs->callee->decl and get to the param decl
by walking DECL_ARGUMENTS ?

Getting param decl would be indeed much clearer. Storing param
precision and sign
in jump function is admittedly quite ugly and as you mentioned below,
we could get rid of precision and signop from ipcp_bits_lattice and ipa_bits.
>
>>    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 ?)
>
> I haven't seen the IL but most probably yes.  If you want to be
> experimenting with this, I beleive you need an example with types of
> the same size but different precisions (C++ enums might work nicely, I
> beleive).
I will try to come up with a test-case.

Thanks,
Prathamesh
>
> If you managed to come up with a testcase with a pass through jump
> function with an operation in which the precision actually affects the
> result, that would be great.
>
>>
>> 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 ?
>
> It does, but to summarize what I wrote above, I believe that with this
> approach you can and should remove the precision field from jump
> functions and lattices.
>
> Thanks,
>
>
> Martin