From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 19890 invoked by alias); 9 Aug 2016 09:24:29 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 19880 invoked by uid 89); 9 Aug 2016 09:24:28 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.3 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD,SPF_PASS autolearn=ham version=3.3.2 spammy=meet, TOP, our X-HELO: mx2.suse.de Received: from mx2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (CAMELLIA256-SHA encrypted) ESMTPS; Tue, 09 Aug 2016 09:24:17 +0000 Received: from relay1.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id A1451ABE0; Tue, 9 Aug 2016 09:24:14 +0000 (UTC) Date: Tue, 09 Aug 2016 09:24:00 -0000 From: Richard Biener To: Prathamesh Kulkarni cc: Jan Hubicka , Kugan Vivekanandarajah , gcc Patches Subject: Re: [RFC] ipa bitwise constant propagation In-Reply-To: Message-ID: References: <20160805123655.c3oai3ivvecx6zbh@virgil.suse.cz> <20160808140355.sbi7zufcjeieek2p@virgil.suse.cz> User-Agent: Alpine 2.11 (LSU 23 2013-08-11) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-SW-Source: 2016-08/txt/msg00675.txt.bz2 On Tue, 9 Aug 2016, Prathamesh Kulkarni wrote: > On 8 August 2016 at 19:33, Martin Jambor 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 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 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 >> >> + > >> >> +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 SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)