On 8 August 2016 at 19:33, Martin Jambor <mjam...@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 <mjam...@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 ?
>
>> 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
>
