From patchwork Wed Aug 10 11:35:07 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Prathamesh Kulkarni X-Patchwork-Id: 73623 Delivered-To: patch@linaro.org Received: by 10.140.29.52 with SMTP id a49csp354649qga; Wed, 10 Aug 2016 04:35:39 -0700 (PDT) X-Received: by 10.66.43.234 with SMTP id z10mr6195401pal.137.1470828939145; Wed, 10 Aug 2016 04:35:39 -0700 (PDT) Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id t18si48258167pfa.44.2016.08.10.04.35.38 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 10 Aug 2016 04:35:39 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-433677-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org; spf=pass (google.com: domain of gcc-patches-return-433677-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=gcc-patches-return-433677-patch=linaro.org@gcc.gnu.org; dmarc=fail (p=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:from:date:message-id :subject:to:content-type; q=dns; s=default; b=KIMj0N63JMaq1s20eL J48wJsrk60goQfCsZzrmc3xIc/hPnPAI6WouvEa99s/zRJ6jAZhyT9NSBnNLGUqC NtIVUjJScUZRV80hEK+mORkJRtdufsCj+oAkIZEQChjNGjHtGT31Or0rdoH6rP1w SlgsT6E7lluU63e7NCjAYWP6o= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:in-reply-to:references:from:date:message-id :subject:to:content-type; s=default; bh=mVjQD01WdUek7cggQr5hPBTu v5s=; b=MbGmwvBMZzwqGvfADldaGeqlQ6BYYQleyNePVpj5KkgaPOMZgyAIz6Y9 Z9aqvnlEyjxCMGPownHtfrWsIrKwJN5OPtGepTMVf9vc2vAfrGtpK/pAf5oVVejx AD5g9bNK1fJn0NsRiPkM9P3uJZySZKKwzdsXpTGRqRAjaSwfLMs= Received: (qmail 113807 invoked by alias); 10 Aug 2016 11:35:22 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 113797 invoked by uid 89); 10 Aug 2016 11:35:21 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.3 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 spammy=trusted, !!!, meet, Attached X-HELO: mail-io0-f178.google.com Received: from mail-io0-f178.google.com (HELO mail-io0-f178.google.com) (209.85.223.178) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Wed, 10 Aug 2016 11:35:11 +0000 Received: by mail-io0-f178.google.com with SMTP id m101so38531580ioi.2 for ; Wed, 10 Aug 2016 04:35:10 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=XB9WLOs2dzpylxF+xXzAa8RzJQqZWiK4lMpbxn9P/zE=; b=aQte8DeE6s+RP+g2t2XB6+7vwGMILNTEGeNsn2Bk+m0nBq9mFV/xbSO26uJJF8LnsR lyrnoW4lBaV+2S31+gSaw8H7mGMT7MKxD5ttGxEa0sZXT801aD9CvDDchmjPUPAy6AXv lPgcb2YmPSppxeVYgDBQBmXWdfY0j1IWxxh48WEXGo/U2JF5b0BGkfwSQUF0gjZV0kqn CpbjJlHOvmClBnjBzST6xIeVTtxblKWA83yBmCmoNZO0uLtIDwvYAW7rzrOp4xSR3UAy MmxPGAz5wVWAjY9uHb23GDcaTbcKPgP1hdFO50iZMGcuEenhAtKz8OT2B4jqkGGUEJsL gKFA== X-Gm-Message-State: AEkoousu59qxv3p3wjGl4f+zj8fnw+vhdi3+6C7K19d95XOfL/8MCdqrLHwOP627qiVhPGHyXyfC1RL+CdIQKrrT X-Received: by 10.107.159.147 with SMTP id i141mr4452770ioe.29.1470828908210; Wed, 10 Aug 2016 04:35:08 -0700 (PDT) MIME-Version: 1.0 Received: by 10.36.208.18 with HTTP; Wed, 10 Aug 2016 04:35:07 -0700 (PDT) In-Reply-To: References: <20160805123655.c3oai3ivvecx6zbh@virgil.suse.cz> <20160808140355.sbi7zufcjeieek2p@virgil.suse.cz> <20160809110933.2dpy7qdepugoknp2@virgil.suse.cz> <20160809181309.erlp4yxnc5otdtxm@virgil.suse.cz> From: Prathamesh Kulkarni Date: Wed, 10 Aug 2016 17:05:07 +0530 Message-ID: Subject: Re: [RFC] ipa bitwise constant propagation To: Prathamesh Kulkarni , Richard Biener , Jan Hubicka , Kugan Vivekanandarajah , gcc Patches X-IsSubscribed: yes On 10 August 2016 at 14:14, Prathamesh Kulkarni wrote: > On 9 August 2016 at 23:43, Martin Jambor wrote: >> Hi, >> >> On Tue, Aug 09, 2016 at 05:17:31PM +0530, Prathamesh Kulkarni wrote: >>> On 9 August 2016 at 16:39, Martin Jambor wrote: >>> >>> ... >>> >>> >> 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 ? >> >> Actually, we no longer have DECL_ARGUMENTS during LTO WPA. But in >> most cases, you can still get at the type with something like the >> following (only very lightly tested) patch, if Honza does not think it >> is too crazy. >> >> Note that= for old K&R C sources we do not have TYPE_ARG_TYPES and so >> ipa_get_type can return NULL(!) ...however I wonder whether for such >> programs the type assumptions made in callers when constructing jump >> functions can be trusted either. >> >> I have to run, we will continue the discussion later. > Thanks for the patch. > In this version, I updated the patch to use ipa_get_type, remove > precision and sgn > from ipcp_bits_lattice and ipa_bits, and renamed member variables to > add m_ prefix. > Does it look OK ? > I am looking for test-case that affects precision and hopefully add > that along with other > test-cases in follow-up patch. > Bootstrap+test in progress on x86_64-unknown-linux-gnu. oops, I forgot to add tree-ssa-ccp.h hunk to the patch :/ Attached in this version. Thanks, Prathamesh > > Thanks, > Prathamesh >> >> Martin >> >> >> 2016-08-09 Martin Jambor >> >> * ipa-prop.h (ipa_param_descriptor): Renamed decl to decl_or_type. >> Update comment. >> (ipa_get_param): Updated comment, added assert that we have a >> PARM_DECL. >> (ipa_get_type): New function. >> * ipa-cp.c (ipcp_propagate_stage): Fill in argument types in LTO mode. >> * ipa-prop.c (ipa_get_param_decl_index_1): Use decl_or_type >> instead of decl; >> (ipa_populate_param_decls): Likewise. >> (ipa_dump_param): Likewise. >> >> >> diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c >> index 5b6cb9a..3465da5 100644 >> --- a/gcc/ipa-cp.c >> +++ b/gcc/ipa-cp.c >> @@ -1952,11 +1952,21 @@ propagate_constants_accross_call (struct cgraph_edge *cs) >> else >> i = 0; >> >> + /* !!! The following dump is of course only a demonstration that it works: */ >> + debug_generic_expr (callee->decl); >> + fprintf (stderr, "\n"); >> + >> for (; (i < args_count) && (i < parms_count); i++) >> { >> struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i); >> struct ipcp_param_lattices *dest_plats; >> >> + /* !!! The following dump is of course only a demonstration that it >> + works: */ >> + fprintf (stderr, " The type of parameter %i is: ", i); >> + debug_generic_expr (ipa_get_type (callee_info, i)); >> + fprintf (stderr, "\n"); >> + >> dest_plats = ipa_get_parm_lattices (callee_info, i); >> if (availability == AVAIL_INTERPOSABLE) >> ret |= set_all_contains_variable (dest_plats); >> @@ -2936,6 +2946,19 @@ ipcp_propagate_stage (struct ipa_topo_info *topo) >> { >> struct ipa_node_params *info = IPA_NODE_REF (node); >> >> + /* In LTO we do not have PARM_DECLs but we would still like to be able to >> + look at types of parameters. */ >> + if (in_lto_p) >> + { >> + tree t = TYPE_ARG_TYPES (TREE_TYPE (node->decl)); >> + for (int k = 0; k < ipa_get_param_count (info); k++) >> + { >> + gcc_assert (t != void_list_node); >> + info->descriptors[k].decl_or_type = TREE_VALUE (t); >> + t = t ? TREE_CHAIN (t) : NULL; >> + } >> + } >> + >> determine_versionability (node, info); >> if (node->has_gimple_body_p ()) >> { >> diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c >> index 132b622..1eaccdf 100644 >> --- a/gcc/ipa-prop.c >> +++ b/gcc/ipa-prop.c >> @@ -103,9 +103,10 @@ ipa_get_param_decl_index_1 (vec descriptors, tree ptree) >> { >> int i, count; >> >> + gcc_checking_assert (!flag_wpa); >> count = descriptors.length (); >> for (i = 0; i < count; i++) >> - if (descriptors[i].decl == ptree) >> + if (descriptors[i].decl_or_type == ptree) >> return i; >> >> return -1; >> @@ -138,7 +139,7 @@ ipa_populate_param_decls (struct cgraph_node *node, >> param_num = 0; >> for (parm = fnargs; parm; parm = DECL_CHAIN (parm)) >> { >> - descriptors[param_num].decl = parm; >> + descriptors[param_num].decl_or_type = parm; >> descriptors[param_num].move_cost = estimate_move_cost (TREE_TYPE (parm), >> true); >> param_num++; >> @@ -168,10 +169,10 @@ void >> ipa_dump_param (FILE *file, struct ipa_node_params *info, int i) >> { >> fprintf (file, "param #%i", i); >> - if (info->descriptors[i].decl) >> + if (info->descriptors[i].decl_or_type) >> { >> fprintf (file, " "); >> - print_generic_expr (file, info->descriptors[i].decl, 0); >> + print_generic_expr (file, info->descriptors[i].decl_or_type, 0); >> } >> } >> >> diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h >> index e32d078..1d5ce0b 100644 >> --- a/gcc/ipa-prop.h >> +++ b/gcc/ipa-prop.h >> @@ -283,8 +283,11 @@ ipa_get_jf_ancestor_type_preserved (struct ipa_jump_func *jfunc) >> >> struct ipa_param_descriptor >> { >> - /* PARAM_DECL of this parameter. */ >> - tree decl; >> + /* In analysis and modification phase, this is the PARAM_DECL of this >> + parameter, in IPA LTO phase, this is the type of the the described >> + parameter or NULL if not known. Do not read this field directly but >> + through ipa_get_param and ipa_get_type as appropriate. */ >> + tree decl_or_type; >> /* If all uses of the parameter are described by ipa-prop structures, this >> says how many there are. If any use could not be described by means of >> ipa-prop structures, this is IPA_UNDESCRIBED_USE. */ >> @@ -402,13 +405,31 @@ ipa_get_param_count (struct ipa_node_params *info) >> >> /* Return the declaration of Ith formal parameter of the function corresponding >> to INFO. Note there is no setter function as this array is built just once >> - using ipa_initialize_node_params. */ >> + using ipa_initialize_node_params. This function should not be called in >> + WPA. */ >> >> static inline tree >> ipa_get_param (struct ipa_node_params *info, int i) >> { >> gcc_checking_assert (!flag_wpa); >> - return info->descriptors[i].decl; >> + tree t = info->descriptors[i].decl_or_type; >> + gcc_checking_assert (TREE_CODE (t) == PARM_DECL); >> + return t; >> +} >> + >> +/* Return the type of Ith formal parameter of the function corresponding >> + to INFO if it is known or NULL if not. */ >> + >> +static inline tree >> +ipa_get_type (struct ipa_node_params *info, int i) >> +{ >> + tree t = info->descriptors[i].decl_or_type; >> + if (!t) >> + return NULL; >> + if (TYPE_P (t)) >> + return t; >> + gcc_checking_assert (TREE_CODE (t) == PARM_DECL); >> + return TREE_TYPE (t); >> } >> >> /* Return the move cost of Ith formal parameter of the function corresponding >> diff --git a/gcc/common.opt b/gcc/common.opt index 8a292ed..8bac0a2 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -1561,6 +1561,10 @@ fipa-cp-alignment Common Report Var(flag_ipa_cp_alignment) Optimization Perform alignment discovery and propagation to make Interprocedural constant propagation stronger. +fipa-cp-bit +Common Report Var(flag_ipa_cp_bit) Optimization +Perform interprocedural bitwise constant propagation. + fipa-profile Common Report Var(flag_ipa_profile) Init(0) Optimization Perform interprocedural profile propagation. diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c index b308e01..289d6c3 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,38 @@ private: bool meet_with_1 (unsigned new_align, unsigned new_misalign); }; +/* Lattice of known bits, only capable of holding one value. + Similar to ccp_lattice_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 m_lattice_val == IPA_BITS_VARYING; } + bool top_p () { return m_lattice_val == IPA_BITS_UNDEFINED; } + bool constant_p () { return m_lattice_val == IPA_BITS_CONSTANT; } + bool set_to_bottom (); + bool set_to_constant (widest_int, widest_int); + + widest_int get_value () { return m_value; } + widest_int get_mask () { return m_mask; } + + bool meet_with (ipcp_bits_lattice& other, unsigned, signop, + enum tree_code, tree); + + bool meet_with (widest_int, widest_int, unsigned); + + void print (FILE *); + +private: + enum { IPA_BITS_UNDEFINED, IPA_BITS_CONSTANT, IPA_BITS_VARYING } m_lattice_val; + widest_int m_value, m_mask; + + bool meet_with_1 (widest_int, widest_int, unsigned); + 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 +314,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 +493,21 @@ ipcp_alignment_lattice::print (FILE * f) fprintf (f, " Alignment %u, misalignment %u\n", align, misalign); } +void +ipcp_bits_lattice::print (FILE *f) +{ + if (top_p ()) + fprintf (f, " Bits unknown (TOP)\n"); + else if (bottom_p ()) + fprintf (f, " Bits unusable (BOTTOM)\n"); + else + { + fprintf (f, " Bits: value = "); print_hex (get_value (), f); + fprintf (f, ", mask = "); print_hex (get_mask (), f); + fprintf (f, "\n"); + } +} + /* Print all ipcp_lattices of all functions to F. */ static void @@ -484,6 +534,7 @@ print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits) fprintf (f, " ctxs: "); plats->ctxlat.print (f, dump_sources, dump_benefits); plats->alignment.print (f); + plats->bits_lattice.print (f); if (plats->virt_call) fprintf (f, " virt_call flag set\n"); @@ -911,6 +962,151 @@ ipcp_alignment_lattice::meet_with (const ipcp_alignment_lattice &other, return meet_with_1 (other.align, adjusted_misalign); } +/* Set lattice value to bottom, if it already isn't the case. */ + +bool +ipcp_bits_lattice::set_to_bottom () +{ + if (bottom_p ()) + return false; + m_lattice_val = IPA_BITS_VARYING; + m_value = 0; + m_mask = -1; + return true; +} + +/* Set to constant if it isn't already. Only meant to be called + when switching state from TOP. */ + +bool +ipcp_bits_lattice::set_to_constant (widest_int value, widest_int mask) +{ + gcc_assert (top_p ()); + m_lattice_val = IPA_BITS_CONSTANT; + m_value = value; + m_mask = mask; + return true; +} + +/* 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 + { + *valuep = 0; + *maskp = -1; + } +} + +/* 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, + unsigned precision) +{ + gcc_assert (constant_p ()); + + widest_int old_mask = m_mask; + m_mask = (m_mask | mask) | (m_value ^ value); + + if (wi::sext (m_mask, precision) == -1) + return set_to_bottom (); + + return m_mask != old_mask; +} + +/* Meet the bits lattice with operand + described by ctxlat.set_contains_variable (); ret |= set_agg_lats_contain_variable (plats); ret |= plats->alignment.set_to_bottom (); + ret |= plats->bits_lattice.set_to_bottom (); return ret; } @@ -1003,6 +1200,7 @@ initialize_node_lattices (struct cgraph_node *node) plats->ctxlat.set_to_bottom (); set_agg_lats_to_bottom (plats); plats->alignment.set_to_bottom (); + plats->bits_lattice.set_to_bottom (); } else set_all_contains_variable (plats); @@ -1621,6 +1819,69 @@ propagate_alignment_accross_jump_function (cgraph_edge *cs, } } +/* Propagate bits across jfunc that is associated with + edge cs and update dest_lattice accordingly. */ + +bool +propagate_bits_accross_jump_function (cgraph_edge *cs, int idx, ipa_jump_func *jfunc, + ipcp_bits_lattice *dest_lattice) +{ + if (dest_lattice->bottom_p ()) + return false; + + struct ipa_node_params *callee_info = IPA_NODE_REF (cs->callee); + tree parm_type = ipa_get_type (callee_info, idx); + + /* For K&R C programs, ipa_get_type() could return NULL_TREE. + Avoid the transform for these cases. */ + if (!parm_type) + return dest_lattice->set_to_bottom (); + + unsigned precision = TYPE_PRECISION (parm_type); + signop sgn = TYPE_SIGN (parm_type); + + if (jfunc->type == IPA_JF_PASS_THROUGH) + { + struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); + enum tree_code code = ipa_get_jf_pass_through_operation (jfunc); + tree operand = NULL_TREE; + + if (code != NOP_EXPR) + operand = ipa_get_jf_pass_through_operand (jfunc); + + int src_idx = ipa_get_jf_pass_through_formal_id (jfunc); + struct ipcp_param_lattices *src_lats + = ipa_get_parm_lattices (caller_info, src_idx); + + /* Try to propagate bits if src_lattice is bottom, but jfunc is known. + for eg consider: + int f(int x) + { + g (x & 0xff); + } + Assume lattice for x is bottom, however we can still propagate + result of x & 0xff == 0xff, which gets computed during ccp1 pass + and we store it in jump function during analysis stage. */ + + if (src_lats->bits_lattice.bottom_p () + && jfunc->bits.known) + return dest_lattice->meet_with (jfunc->bits.value, jfunc->bits.mask, + precision); + else + return dest_lattice->meet_with (src_lats->bits_lattice, precision, sgn, + code, operand); + } + + else if (jfunc->type == IPA_JF_ANCESTOR) + return dest_lattice->set_to_bottom (); + + else if (jfunc->bits.known) + return dest_lattice->meet_with (jfunc->bits.value, jfunc->bits.mask, precision); + + else + return dest_lattice->set_to_bottom (); +} + /* If DEST_PLATS already has aggregate items, check that aggs_by_ref matches NEW_AGGS_BY_REF and if not, mark all aggs as bottoms and return true (in all other cases, return false). If there are no aggregate items, set @@ -1968,6 +2229,8 @@ propagate_constants_accross_call (struct cgraph_edge *cs) &dest_plats->ctxlat); ret |= propagate_alignment_accross_jump_function (cs, jump_func, &dest_plats->alignment); + ret |= propagate_bits_accross_jump_function (cs, i, jump_func, + &dest_plats->bits_lattice); ret |= propagate_aggs_accross_jump_function (cs, jump_func, dest_plats); } @@ -4605,6 +4868,81 @@ ipcp_store_alignment_results (void) } } +/* Look up all the bits information that we have discovered and copy it over + to the transformation summary. */ + +static void +ipcp_store_bits_results (void) +{ + cgraph_node *node; + + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) + { + ipa_node_params *info = IPA_NODE_REF (node); + bool dumped_sth = false; + bool found_useful_result = false; + + if (!opt_for_fn (node->decl, flag_ipa_cp_bit)) + { + if (dump_file) + fprintf (dump_file, "Not considering %s for ipa bitwise propagation " + "; -fipa-cp-bit: disabled.\n", + node->name ()); + continue; + } + + if (info->ipcp_orig_node) + info = IPA_NODE_REF (info->ipcp_orig_node); + + unsigned count = ipa_get_param_count (info); + for (unsigned i = 0; i < count; i++) + { + ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + if (plats->bits_lattice.constant_p ()) + { + found_useful_result = true; + break; + } + } + + if (!found_useful_result) + continue; + + ipcp_grow_transformations_if_necessary (); + ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node); + vec_safe_reserve_exact (ts->bits, count); + + for (unsigned i = 0; i < count; i++) + { + ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + ipa_bits bits_jfunc; + + if (plats->bits_lattice.constant_p ()) + { + bits_jfunc.known = true; + bits_jfunc.value = plats->bits_lattice.get_value (); + bits_jfunc.mask = plats->bits_lattice.get_mask (); + } + else + bits_jfunc.known = false; + + ts->bits->quick_push (bits_jfunc); + if (!dump_file || !bits_jfunc.known) + continue; + if (!dumped_sth) + { + fprintf (dump_file, "Propagated bits info for function %s/%i:\n", + node->name (), node->order); + dumped_sth = true; + } + fprintf (dump_file, " param %i: value = ", i); + print_hex (bits_jfunc.value, dump_file); + fprintf (dump_file, ", mask = "); + print_hex (bits_jfunc.mask, dump_file); + fprintf (dump_file, "\n"); + } + } +} /* The IPCP driver. */ static unsigned int @@ -4638,6 +4976,8 @@ ipcp_driver (void) ipcp_decision_stage (&topo); /* Store results of alignment propagation. */ ipcp_store_alignment_results (); + /* Store results of bits propagation. */ + ipcp_store_bits_results (); /* Free all IPCP structures. */ free_toporder_info (&topo); diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c index 8fa1350..44ec20a 100644 --- a/gcc/ipa-prop.c +++ b/gcc/ipa-prop.c @@ -303,6 +303,15 @@ ipa_print_node_jump_functions_for_edge (FILE *f, struct cgraph_edge *cs) } else fprintf (f, " Unknown alignment\n"); + + if (jump_func->bits.known) + { + fprintf (f, " value: "); print_hex (jump_func->bits.value, f); + fprintf (f, ", mask: "); print_hex (jump_func->bits.mask, f); + fprintf (f, "\n"); + } + else + fprintf (f, " Unknown bits\n"); } } @@ -382,6 +391,7 @@ ipa_set_jf_unknown (struct ipa_jump_func *jfunc) { jfunc->type = IPA_JF_UNKNOWN; jfunc->alignment.known = false; + jfunc->bits.known = false; } /* Set JFUNC to be a copy of another jmp (to be used by jump function @@ -1675,6 +1685,26 @@ ipa_compute_jump_functions_for_edge (struct ipa_func_body_info *fbi, else gcc_assert (!jfunc->alignment.known); + if (INTEGRAL_TYPE_P (TREE_TYPE (arg)) + && (TREE_CODE (arg) == SSA_NAME || TREE_CODE (arg) == INTEGER_CST)) + { + jfunc->bits.known = true; + + if (TREE_CODE (arg) == SSA_NAME) + { + jfunc->bits.value = 0; + jfunc->bits.mask = widest_int::from (get_nonzero_bits (arg), + TYPE_SIGN (TREE_TYPE (arg))); + } + else + { + jfunc->bits.value = wi::to_widest (arg); + jfunc->bits.mask = 0; + } + } + else + gcc_assert (!jfunc->bits.known); + if (is_gimple_ip_invariant (arg) || (TREE_CODE (arg) == VAR_DECL && is_global_var (arg) @@ -3691,6 +3721,18 @@ ipa_node_params_t::duplicate(cgraph_node *src, cgraph_node *dst, for (unsigned i = 0; i < src_alignments->length (); ++i) dst_alignments->quick_push ((*src_alignments)[i]); } + + if (src_trans && vec_safe_length (src_trans->bits) > 0) + { + ipcp_grow_transformations_if_necessary (); + src_trans = ipcp_get_transformation_summary (src); + const vec *src_bits = src_trans->bits; + vec *&dst_bits + = ipcp_get_transformation_summary (dst)->bits; + vec_safe_reserve_exact (dst_bits, src_bits->length ()); + for (unsigned i = 0; i < src_bits->length (); ++i) + dst_bits->quick_push ((*src_bits)[i]); + } } /* Register our cgraph hooks if they are not already there. */ @@ -4610,6 +4652,15 @@ ipa_write_jump_function (struct output_block *ob, streamer_write_uhwi (ob, jump_func->alignment.align); streamer_write_uhwi (ob, jump_func->alignment.misalign); } + + bp = bitpack_create (ob->main_stream); + bp_pack_value (&bp, jump_func->bits.known, 1); + streamer_write_bitpack (&bp); + if (jump_func->bits.known) + { + streamer_write_widest_int (ob, jump_func->bits.value); + streamer_write_widest_int (ob, jump_func->bits.mask); + } } /* Read in jump function JUMP_FUNC from IB. */ @@ -4686,6 +4737,17 @@ ipa_read_jump_function (struct lto_input_block *ib, } else jump_func->alignment.known = false; + + bp = streamer_read_bitpack (ib); + bool bits_known = bp_unpack_value (&bp, 1); + if (bits_known) + { + jump_func->bits.known = true; + jump_func->bits.value = streamer_read_widest_int (ib); + jump_func->bits.mask = streamer_read_widest_int (ib); + } + else + jump_func->bits.known = false; } /* Stream out parts of cgraph_indirect_call_info corresponding to CS that are @@ -5051,6 +5113,28 @@ write_ipcp_transformation_info (output_block *ob, cgraph_node *node) } else streamer_write_uhwi (ob, 0); + + ts = ipcp_get_transformation_summary (node); + if (ts && vec_safe_length (ts->bits) > 0) + { + count = ts->bits->length (); + streamer_write_uhwi (ob, count); + + for (unsigned i = 0; i < count; ++i) + { + const ipa_bits& bits_jfunc = (*ts->bits)[i]; + struct bitpack_d bp = bitpack_create (ob->main_stream); + bp_pack_value (&bp, bits_jfunc.known, 1); + streamer_write_bitpack (&bp); + if (bits_jfunc.known) + { + streamer_write_widest_int (ob, bits_jfunc.value); + streamer_write_widest_int (ob, bits_jfunc.mask); + } + } + } + else + streamer_write_uhwi (ob, 0); } /* Stream in the aggregate value replacement chain for NODE from IB. */ @@ -5103,6 +5187,26 @@ read_ipcp_transformation_info (lto_input_block *ib, cgraph_node *node, } } } + + count = streamer_read_uhwi (ib); + if (count > 0) + { + ipcp_grow_transformations_if_necessary (); + ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node); + vec_safe_grow_cleared (ts->bits, count); + + for (i = 0; i < count; i++) + { + ipa_bits& bits_jfunc = (*ts->bits)[i]; + struct bitpack_d bp = streamer_read_bitpack (ib); + bits_jfunc.known = bp_unpack_value (&bp, 1); + if (bits_jfunc.known) + { + bits_jfunc.value = streamer_read_widest_int (ib); + bits_jfunc.mask = streamer_read_widest_int (ib); + } + } + } } /* Write all aggregate replacement for nodes in set. */ @@ -5405,6 +5509,56 @@ ipcp_update_alignments (struct cgraph_node *node) } } +/* Update bits info of formal parameters as described in + ipcp_transformation_summary. */ + +static void +ipcp_update_bits (struct cgraph_node *node) +{ + tree parm = DECL_ARGUMENTS (node->decl); + tree next_parm = parm; + ipcp_transformation_summary *ts = ipcp_get_transformation_summary (node); + + if (!ts || vec_safe_length (ts->bits) == 0) + return; + + vec &bits = *ts->bits; + unsigned count = bits.length (); + + for (unsigned i = 0; i < count; ++i, parm = next_parm) + { + if (node->clone.combined_args_to_skip + && bitmap_bit_p (node->clone.combined_args_to_skip, i)) + continue; + + gcc_checking_assert (parm); + next_parm = DECL_CHAIN (parm); + + if (!bits[i].known + || !INTEGRAL_TYPE_P (TREE_TYPE (parm)) + || !is_gimple_reg (parm)) + continue; + + tree ddef = ssa_default_def (DECL_STRUCT_FUNCTION (node->decl), parm); + if (!ddef) + continue; + + if (dump_file) + { + fprintf (dump_file, "Adjusting mask for param %u to ", i); + print_hex (bits[i].mask, dump_file); + fprintf (dump_file, "\n"); + } + + unsigned prec = TYPE_PRECISION (TREE_TYPE (ddef)); + signop sgn = TYPE_SIGN (TREE_TYPE (ddef)); + + wide_int nonzero_bits = wide_int::from (bits[i].mask, prec, UNSIGNED) + | wide_int::from (bits[i].value, prec, sgn); + set_nonzero_bits (ddef, nonzero_bits); + } +} + /* IPCP transformation phase doing propagation of aggregate values. */ unsigned int @@ -5424,6 +5578,7 @@ ipcp_transform_function (struct cgraph_node *node) node->name (), node->order); ipcp_update_alignments (node); + ipcp_update_bits (node); aggval = ipa_get_agg_replacements_for_node (node); if (!aggval) return 0; diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h index 1d5ce0b..e5a56da 100644 --- a/gcc/ipa-prop.h +++ b/gcc/ipa-prop.h @@ -154,6 +154,19 @@ 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_lattice_t, if xth bit of mask is 0, + implies xth bit of value is constant. */ + widest_int mask; + /* True if jump function is known. */ + bool known; +}; + /* A jump function for a callsite represents the values passed as actual arguments of the callsite. See enum jump_func_type for the various types of jump functions supported. */ @@ -166,6 +179,9 @@ struct GTY (()) ipa_jump_func /* Information about alignment of pointers. */ struct ipa_alignment alignment; + /* Information about zero/non-zero bits. */ + struct ipa_bits bits; + enum jump_func_type type; /* Represents a value of a jump function. pass_through is used only in jump function context. constant represents the actual constant in constant jump @@ -503,6 +519,8 @@ struct GTY(()) ipcp_transformation_summary ipa_agg_replacement_value *agg_values; /* Alignment information for pointers. */ vec *alignments; + /* Known bits information. */ + vec *bits; }; void ipa_set_node_agg_value_chain (struct cgraph_node *node, diff --git a/gcc/opts.c b/gcc/opts.c index 4053fb1..cde9a7b 100644 --- a/gcc/opts.c +++ b/gcc/opts.c @@ -505,6 +505,7 @@ static const struct default_options default_options_table[] = { OPT_LEVELS_2_PLUS, OPT_ftree_switch_conversion, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_fipa_cp, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_fipa_cp_alignment, NULL, 1 }, + { OPT_LEVELS_2_PLUS, OPT_fipa_cp_bit, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_fdevirtualize, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_fdevirtualize_speculatively, NULL, 1 }, { OPT_LEVELS_2_PLUS, OPT_fipa_sra, NULL, 1 }, @@ -1422,6 +1423,9 @@ enable_fdo_optimizations (struct gcc_options *opts, if (!opts_set->x_flag_ipa_cp_alignment && value && opts->x_flag_ipa_cp) opts->x_flag_ipa_cp_alignment = value; + if (!opts_set->x_flag_ipa_cp_bit + && value && opts->x_flag_ipa_cp) + opts->x_flag_ipa_cp_bit = value; if (!opts_set->x_flag_predictive_commoning) opts->x_flag_predictive_commoning = value; if (!opts_set->x_flag_unswitch_loops) diff --git a/gcc/tree-ssa-ccp.c b/gcc/tree-ssa-ccp.c index 5d5386e..d88143b 100644 --- a/gcc/tree-ssa-ccp.c +++ b/gcc/tree-ssa-ccp.c @@ -142,7 +142,7 @@ along with GCC; see the file COPYING3. If not see #include "cfgloop.h" #include "stor-layout.h" #include "optabs-query.h" - +#include "tree-ssa-ccp.h" /* Possible lattice values. */ typedef enum @@ -536,9 +536,9 @@ set_lattice_value (tree var, ccp_prop_value_t *new_val) static ccp_prop_value_t get_value_for_expr (tree, bool); static ccp_prop_value_t bit_value_binop (enum tree_code, tree, tree, tree); -static void bit_value_binop_1 (enum tree_code, tree, widest_int *, widest_int *, - tree, const widest_int &, const widest_int &, - tree, const widest_int &, const widest_int &); +void bit_value_binop (enum tree_code, signop, int, widest_int *, widest_int *, + signop, int, const widest_int &, const widest_int &, + signop, int, const widest_int &, const widest_int &); /* Return a widest_int that can be used for bitwise simplifications from VAL. */ @@ -894,7 +894,7 @@ do_dbg_cnt (void) Return TRUE when something was optimized. */ static bool -ccp_finalize (bool nonzero_p) +ccp_finalize (bool nonzero_p) { bool something_changed; unsigned i; @@ -920,7 +920,8 @@ ccp_finalize (bool nonzero_p) val = get_value (name); if (val->lattice_val != CONSTANT - || TREE_CODE (val->value) != INTEGER_CST) + || TREE_CODE (val->value) != INTEGER_CST + || val->mask == 0) continue; if (POINTER_TYPE_P (TREE_TYPE (name))) @@ -1224,10 +1225,11 @@ ccp_fold (gimple *stmt) RVAL and RMASK representing a value of type RTYPE and set the value, mask pair *VAL and *MASK to the result. */ -static void -bit_value_unop_1 (enum tree_code code, tree type, - widest_int *val, widest_int *mask, - tree rtype, const widest_int &rval, const widest_int &rmask) +void +bit_value_unop (enum tree_code code, signop type_sgn, int type_precision, + widest_int *val, widest_int *mask, + signop rtype_sgn, int rtype_precision, + const widest_int &rval, const widest_int &rmask) { switch (code) { @@ -1240,25 +1242,23 @@ bit_value_unop_1 (enum tree_code code, tree type, { widest_int temv, temm; /* Return ~rval + 1. */ - bit_value_unop_1 (BIT_NOT_EXPR, type, &temv, &temm, type, rval, rmask); - bit_value_binop_1 (PLUS_EXPR, type, val, mask, - type, temv, temm, type, 1, 0); + bit_value_unop (BIT_NOT_EXPR, type_sgn, type_precision, &temv, &temm, + type_sgn, type_precision, rval, rmask); + bit_value_binop (PLUS_EXPR, type_sgn, type_precision, val, mask, + type_sgn, type_precision, temv, temm, + type_sgn, type_precision, 1, 0); break; } CASE_CONVERT: { - signop sgn; - /* First extend mask and value according to the original type. */ - sgn = TYPE_SIGN (rtype); - *mask = wi::ext (rmask, TYPE_PRECISION (rtype), sgn); - *val = wi::ext (rval, TYPE_PRECISION (rtype), sgn); + *mask = wi::ext (rmask, rtype_precision, rtype_sgn); + *val = wi::ext (rval, rtype_precision, rtype_sgn); /* Then extend mask and value according to the target type. */ - sgn = TYPE_SIGN (type); - *mask = wi::ext (*mask, TYPE_PRECISION (type), sgn); - *val = wi::ext (*val, TYPE_PRECISION (type), sgn); + *mask = wi::ext (*mask, type_precision, type_sgn); + *val = wi::ext (*val, type_precision, type_sgn); break; } @@ -1272,15 +1272,14 @@ bit_value_unop_1 (enum tree_code code, tree type, R1VAL, R1MASK and R2VAL, R2MASK representing a values of type R1TYPE and R2TYPE and set the value, mask pair *VAL and *MASK to the result. */ -static void -bit_value_binop_1 (enum tree_code code, tree type, - widest_int *val, widest_int *mask, - tree r1type, const widest_int &r1val, - const widest_int &r1mask, tree r2type, - const widest_int &r2val, const widest_int &r2mask) +void +bit_value_binop (enum tree_code code, signop sgn, int width, + widest_int *val, widest_int *mask, + signop r1type_sgn, int r1type_precision, + const widest_int &r1val, const widest_int &r1mask, + signop r2type_sgn, int r2type_precision, + const widest_int &r2val, const widest_int &r2mask) { - signop sgn = TYPE_SIGN (type); - int width = TYPE_PRECISION (type); bool swap_p = false; /* Assume we'll get a constant result. Use an initial non varying @@ -1406,11 +1405,11 @@ bit_value_binop_1 (enum tree_code code, tree type, case MINUS_EXPR: { widest_int temv, temm; - bit_value_unop_1 (NEGATE_EXPR, r2type, &temv, &temm, - r2type, r2val, r2mask); - bit_value_binop_1 (PLUS_EXPR, type, val, mask, - r1type, r1val, r1mask, - r2type, temv, temm); + bit_value_unop (NEGATE_EXPR, r2type_sgn, r2type_precision, &temv, &temm, + r2type_sgn, r2type_precision, r2val, r2mask); + bit_value_binop (PLUS_EXPR, sgn, width, val, mask, + r1type_sgn, r1type_precision, r1val, r1mask, + r2type_sgn, r2type_precision, temv, temm); break; } @@ -1472,7 +1471,7 @@ bit_value_binop_1 (enum tree_code code, tree type, break; /* For comparisons the signedness is in the comparison operands. */ - sgn = TYPE_SIGN (r1type); + sgn = r1type_sgn; /* If we know the most significant bits we know the values value ranges by means of treating varying bits as zero @@ -1525,8 +1524,9 @@ bit_value_unop (enum tree_code code, tree type, tree rhs) gcc_assert ((rval.lattice_val == CONSTANT && TREE_CODE (rval.value) == INTEGER_CST) || wi::sext (rval.mask, TYPE_PRECISION (TREE_TYPE (rhs))) == -1); - bit_value_unop_1 (code, type, &value, &mask, - TREE_TYPE (rhs), value_to_wide_int (rval), rval.mask); + bit_value_unop (code, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask, + TYPE_SIGN (TREE_TYPE (rhs)), TYPE_PRECISION (TREE_TYPE (rhs)), + value_to_wide_int (rval), rval.mask); if (wi::sext (mask, TYPE_PRECISION (type)) != -1) { val.lattice_val = CONSTANT; @@ -1571,9 +1571,12 @@ bit_value_binop (enum tree_code code, tree type, tree rhs1, tree rhs2) && TREE_CODE (r2val.value) == INTEGER_CST) || wi::sext (r2val.mask, TYPE_PRECISION (TREE_TYPE (rhs2))) == -1); - bit_value_binop_1 (code, type, &value, &mask, - TREE_TYPE (rhs1), value_to_wide_int (r1val), r1val.mask, - TREE_TYPE (rhs2), value_to_wide_int (r2val), r2val.mask); + bit_value_binop (code, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask, + TYPE_SIGN (TREE_TYPE (rhs1)), TYPE_PRECISION (TREE_TYPE (rhs1)), + value_to_wide_int (r1val), r1val.mask, + TYPE_SIGN (TREE_TYPE (rhs2)), TYPE_PRECISION (TREE_TYPE (rhs2)), + value_to_wide_int (r2val), r2val.mask); + if (wi::sext (mask, TYPE_PRECISION (type)) != -1) { val.lattice_val = CONSTANT; @@ -1672,9 +1675,10 @@ bit_value_assume_aligned (gimple *stmt, tree attr, ccp_prop_value_t ptrval, align = build_int_cst_type (type, -aligni); alignval = get_value_for_expr (align, true); - bit_value_binop_1 (BIT_AND_EXPR, type, &value, &mask, - type, value_to_wide_int (ptrval), ptrval.mask, - type, value_to_wide_int (alignval), alignval.mask); + bit_value_binop (BIT_AND_EXPR, TYPE_SIGN (type), TYPE_PRECISION (type), &value, &mask, + TYPE_SIGN (type), TYPE_PRECISION (type), value_to_wide_int (ptrval), ptrval.mask, + TYPE_SIGN (type), TYPE_PRECISION (type), value_to_wide_int (alignval), alignval.mask); + if (wi::sext (mask, TYPE_PRECISION (type)) != -1) { val.lattice_val = CONSTANT; @@ -2409,7 +2413,7 @@ do_ssa_ccp (bool nonzero_p) ccp_initialize (); ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node); - if (ccp_finalize (nonzero_p)) + if (ccp_finalize (nonzero_p || flag_ipa_cp_bit)) { todo = (TODO_cleanup_cfg | TODO_update_ssa); diff --git a/gcc/tree-ssa-ccp.h b/gcc/tree-ssa-ccp.h new file mode 100644 index 0000000..0e619c7 --- /dev/null +++ b/gcc/tree-ssa-ccp.h @@ -0,0 +1,29 @@ +/* Copyright (C) 2016-2016 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by the +Free Software Foundation; either version 3, or (at your option) any +later version. + +GCC is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef TREE_SSA_CCP_H +#define TREE_SSA_CCP_H + +void bit_value_binop (enum tree_code, signop, int, widest_int *, widest_int *, + signop, int, const widest_int &, const widest_int &, + signop, int, const widest_int &, const widest_int &); + +void bit_value_unop (enum tree_code, signop, int, widest_int *, widest_int *, + signop, int, const widest_int &, const widest_int &); + +#endif