From patchwork Tue Aug 30 17:05:54 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Martin Jambor X-Patchwork-Id: 1671971 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=suse.cz header.i=@suse.cz header.a=rsa-sha256 header.s=susede2_rsa header.b=eKBqs0WH; dkim=pass header.d=suse.cz header.i=@suse.cz header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=NdW3F6QR; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4MHDH3583zz1ynD for ; Wed, 31 Aug 2022 03:06:19 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 38E5B3959C5D for ; Tue, 30 Aug 2022 17:06:17 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2001:67c:2178:6::1c]) by sourceware.org (Postfix) with ESMTPS id 64C87385841A for ; Tue, 30 Aug 2022 17:05:56 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 64C87385841A Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: sourceware.org; spf=fail smtp.mailfrom=suse.cz Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 1625421EA0; Tue, 30 Aug 2022 17:05:55 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1661879155; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=nw8fpT4x9B1CpcnX6av19y98cBUh3qRLXGyu120Nm2w=; b=eKBqs0WHPUHzpoPVxWAoOFqqOuidNRqqEnG9t6R5SwLSVGQ3f18d+oljU8+hDg/kXxb4zF 7WpqdnB+gk+LGPJjywhCM0JMrmdhe7Z7x7lyzU4FPKJhoOoPlKVo4MEGObKWt7+vzX+Ubd r6yqI8xpS3LjwW0syqYO0A15WY3ixjc= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1661879155; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=nw8fpT4x9B1CpcnX6av19y98cBUh3qRLXGyu120Nm2w=; b=NdW3F6QRRAl6oYgmvmsvr03TARzMlIs4XbUpJO4dUg3dMD0g8O3cK5VhctMAkxcLg8cLvy +S0ScA+PphfOxNDQ== Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id F066B13B0C; Tue, 30 Aug 2022 17:05:54 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id 1myQOnJDDmPEWQAAMHmgww (envelope-from ); Tue, 30 Aug 2022 17:05:54 +0000 From: Martin Jambor To: GCC Patches Subject: [PATCH 1/2] ipa-cp: Better representation of aggregate values we clone for User-Agent: Notmuch/0.35 (https://notmuchmail.org) Emacs/28.1 (x86_64-suse-linux-gnu) Date: Tue, 30 Aug 2022 19:05:54 +0200 Message-ID: MIME-Version: 1.0 X-Spam-Status: No, score=-11.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_SOFTFAIL, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Jan Hubicka , Jan Hubicka Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Hi, this patch replaces linked lists of ipa_agg_replacement_value with vectors of similar structures called ipa_argagg_value and simplifies how we compute them in the first place. Having a vector should also result in less overhead when allocating and because we keep it sorted, it leads to logarithmic searches. The slightly obnoxious "argagg" bit in the name can be changed into "agg" after the next patch removes our current ipa_agg_value type. The patch also introduces type ipa_argagg_value_list which serves as a common view into a vector of ipa_argagg_value structures regardless whether they are stored in GC memory (required for IPA-CP transformation summary because we store trees) or in an auto_vec which is hopefully usually only allocated on stack. The calculation of aggreagete costant values for a given subsert of callers is then rewritten to compute known constants for each edge (some pruning to skip obviously not needed is still employed and should not be really worse than what I am replacing) and these vectors are there intersected, which can be done linearly since they are sorted. The patch also removes a lot of heap allocations of small lists of aggregate values and replaces them with stack based auto_vecs. As Richard Sandiford suggested, I use std::lower_bound from rather than re-implementing bsearch for array_slice. The patch depends on the patch which adds the ability to construct array_slices from gc-allocated vectors. Bootstrapped, LTO-bootstrapped and tested on x86_64-linux (and a slightly older version also on aarch64-linux). LTO-profiledbootstrap is currently underway. Given the size of the patch I assume there will be concerns/questions but I'm looking for an approval to commit a version of this. Thanks, Martin gcc/ChangeLog: 2022-08-26 Martin Jambor * ipa-prop.h (IPA_PROP_ARG_INDEX_LIMIT_BITS): New. (ipcp_transformation): Added forward declaration. (ipa_argagg_value): New type. (ipa_argagg_value_list): New type. (ipa_agg_replacement_value): Removed type. (ipcp_transformation): Switch from using ipa_agg_replacement_value to ipa_argagg_value_list. (ipa_get_agg_replacements_for_node): Removed. (ipa_dump_agg_replacement_values): Removed declaration. * ipa-cp.cc: Include . (values_equal_for_ipcp_p): Moved up in the file. (ipa_argagg_value_list::dump): Likewise. (ipa_argagg_value_list::debug): Likewise. (ipa_argagg_value_list::get_elt): Likewise. (ipa_argagg_value_list::get_elt_for_index): Likewise. (ipa_argagg_value_list::get_value): New overloaded functions. (ipa_argagg_value_list::superset_of_p): New function. (new ipa_argagg_value_list::push_adjusted_values): Likewise. (push_agg_values_from_plats): Likewise. (intersect_argaggs_with): Likewise. (get_clone_agg_value): Removed. (ipa_agg_value_from_node): Make last parameter const, use ipa_argagg_value_list to search values coming from clones. (ipa_get_indirect_edge_target_1): Use ipa_argagg_value_list to search values coming from clones. (ipcp_discover_new_direct_edges): Pass around a vector of ipa_argagg_values rather than a link list of replacement values. (cgraph_edge_brings_value_p): Use ipa_argagg_value_list to search values coming from clones. (create_specialized_node): Work with a vector of ipa_argagg_values rather than a link list of replacement values. (self_recursive_agg_pass_through_p): Make the pointer parameters const. (copy_plats_to_inter): Removed. (intersect_with_plats): Likewise. (agg_replacements_to_vector): Likewise. (intersect_with_agg_replacements): Likewise. (intersect_aggregates_with_edge): Likewise. (push_agg_values_for_index_from_edge): Likewise. (push_agg_values_from_edge): Likewise. (find_aggregate_values_for_callers_subset): Rewrite. (cgraph_edge_brings_all_agg_vals_for_node): Likewise. (ipcp_val_agg_replacement_ok_p): Use ipa_argagg_value_list to search aggregate values. (decide_about_value): Work with a vector of ipa_argagg_values rather than a link list of replacement values. (decide_whether_version_node): Likewise. (ipa_analyze_node): Check number of parameters, assert that there are no descriptors when bailing out. * ipa-prop.cc (ipa_set_node_agg_value_chain): Switch to a vector of ipa_argagg_value. (ipa_node_params_t::duplicate): Removed superfluous handling of ipa_agg_replacement_values. Name of src parameter removed because it is no longer used. (ipcp_transformation_t::duplicate): Replaced duplication of ipa_agg_replacement_values with copying vector m_agg_values. (ipa_dump_agg_replacement_values): Removed. (write_ipcp_transformation_info): Stream the new data-structure instead of the old. (read_ipcp_transformation_info): Likewise. (adjust_agg_replacement_values): Work with ipa_argagg_values instead of linked lists of ipa_agg_replacement_values, copy the items and truncate the vector as necessary to keep it sorted instead of marking items as invalid. Return one bool if CFG should be updated. (ipcp_modif_dom_walker): Store ipcp_transformation instead of linked list of ipa_agg_replacement_values. (ipcp_modif_dom_walker::before_dom_children): Use ipa_argagg_value_list instead of walking a list of ipa_agg_replacement_values. (ipcp_transform_function): Switch to the new data structure, adjust dumping. gcc/testsuite/ChangeLog: 2022-08-15 Martin Jambor * gcc.dg/ipa/ipcp-agg-11.c: Adjust dumps. * gcc.dg/ipa/ipcp-agg-8.c: Likewise. --- gcc/ipa-cp.cc | 1010 ++++++++++++------------ gcc/ipa-prop.cc | 254 +++--- gcc/ipa-prop.h | 139 +++- gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c | 4 +- gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c | 4 +- 5 files changed, 736 insertions(+), 675 deletions(-) diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc index 543a9334e2c..024f8c06b5d 100644 --- a/gcc/ipa-cp.cc +++ b/gcc/ipa-cp.cc @@ -127,6 +127,7 @@ along with GCC; see the file COPYING3. If not see #include "attribs.h" #include "dbgcnt.h" #include "symtab-clones.h" +#include template class ipcp_value; @@ -455,6 +456,26 @@ ipcp_lattice::is_single_const () return true; } +/* Return true iff X and Y should be considered equal values by IPA-CP. */ + +static bool +values_equal_for_ipcp_p (tree x, tree y) +{ + gcc_checking_assert (x != NULL_TREE && y != NULL_TREE); + + if (x == y) + return true; + + if (TREE_CODE (x) == ADDR_EXPR + && TREE_CODE (y) == ADDR_EXPR + && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL + && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL) + return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)), + DECL_INITIAL (TREE_OPERAND (y, 0)), 0); + else + return operand_equal_p (x, y, 0); +} + /* Print V which is extracted from a value in a lattice to F. */ static void @@ -1217,6 +1238,272 @@ ipcp_bits_lattice::meet_with (ipcp_bits_lattice& other, unsigned precision, drop_all_ones); } +/* Dump the contents of the list to FILE. */ + +void +ipa_argagg_value_list::dump (FILE *f) +{ + bool comma = false; + for (const ipa_argagg_value &av : m_elts) + { + fprintf (f, "%s %i[%u]=", comma ? "," : "", + av.index, av.unit_offset); + print_generic_expr (f, av.value); + if (av.by_ref) + fprintf (f, "(by_ref)"); + comma = true; + } + fprintf (f, "\n"); +} + +/* Dump the contents of the list to stderr. */ + +void +ipa_argagg_value_list::debug () +{ + dump (stderr); +} + +/* Return the item describing a constant stored for INDEX at UNIT_OFFSET or + NULL if there is no such constant. */ + +const ipa_argagg_value * +ipa_argagg_value_list::get_elt (int index, unsigned unit_offset) const +{ + ipa_argagg_value key; + key.index = index; + key.unit_offset = unit_offset; + const ipa_argagg_value *res + = std::lower_bound (m_elts.begin (), m_elts.end (), key, + [] (const ipa_argagg_value &elt, + const ipa_argagg_value &val) + { + if (elt.index < val.index) + return true; + if (elt.index > val.index) + return false; + if (elt.unit_offset < val.unit_offset) + return true; + return false; + }); + + if (res == m_elts.end () + || res->index != index + || res->unit_offset != unit_offset) + res = nullptr; + + /* TODO: perhaps remove after some extensive testing? */ + if (!flag_checking) + return res; + + const ipa_argagg_value *slow_res = NULL; + int prev_index = -1; + unsigned prev_unit_offset = 0; + for (const ipa_argagg_value &av : m_elts) + { + gcc_assert (prev_index < 0 + || prev_index < av.index + || prev_unit_offset < av.unit_offset); + prev_index = av.index; + prev_unit_offset = av.unit_offset; + if (av.index == index + && av.unit_offset == unit_offset) + slow_res = &av; + } + gcc_assert (res == slow_res); + + return res; +} + +/* Return the first item describing a constant stored for parameter with INDEX, + regardless of offset or reference, or NULL if there is no such constant. */ + +const ipa_argagg_value * +ipa_argagg_value_list::get_elt_for_index (int index) const +{ + const ipa_argagg_value *res + = std::lower_bound (m_elts.begin (), m_elts.end (), index, + [] (const ipa_argagg_value &elt, unsigned idx) + { + return elt.index < idx; + }); + if (res == m_elts.end () + || res->index != index) + res = nullptr; + return res; +} + +/* Return the aggregate constant stored for INDEX at UNIT_OFFSET, not + performing any check of whether value is passed by reference, or NULL_TREE + if there is no such constant. */ + +tree +ipa_argagg_value_list::get_value (int index, unsigned unit_offset) const +{ + const ipa_argagg_value *av = get_elt (index, unit_offset); + return av ? av->value : NULL_TREE; +} + +/* Return the aggregate constant stored for INDEX at UNIT_OFFSET, if it is + passed by reference or not according to BY_REF, or NULL_TREE if there is + no such constant. */ + +tree +ipa_argagg_value_list::get_value (int index, unsigned unit_offset, + bool by_ref) const +{ + const ipa_argagg_value *av = get_elt (index, unit_offset); + if (av && av->by_ref == by_ref) + return av->value; + return NULL_TREE; +} + +/* Turn all values that are not present in OTHER into NULL_TREEs. Return the + number of remaining valid entries. */ + +bool +ipa_argagg_value_list::superset_of_p (const ipa_argagg_value_list &other) const +{ + unsigned j = 0; + for (unsigned i = 0; i < other.m_elts.size (); i++) + { + unsigned this_index = other.m_elts[i].index; + unsigned this_offset = other.m_elts[i].unit_offset; + + while (j < m_elts.size () + && (m_elts[j].index < this_index + || (m_elts[j].index == this_index + && m_elts[j].unit_offset < this_offset))) + j++; + + if (j >= m_elts.size () + || m_elts[j].index != this_index + || m_elts[j].unit_offset != this_offset + || m_elts[j].by_ref != other.m_elts[i].by_ref + || !m_elts[j].value + || !values_equal_for_ipcp_p (m_elts[j].value, other.m_elts[i].value)) + return false; + } + return true; +} + +/* Push into RES aggregate all stored aggregate values relating to parameter + with SRC_INDEX as those relating to of DST_INDEX while subtracting + UNIT_DELTA from the individual unit offsets. */ + +void +ipa_argagg_value_list::push_adjusted_values (unsigned src_index, + unsigned dest_index, + unsigned unit_delta, + vec *res) const +{ + const ipa_argagg_value *av = get_elt_for_index (src_index); + if (!av) + return; + unsigned prev_unit_offset = 0; + bool first = true; + for (; av < m_elts.end (); ++av) + { + if (av->index > src_index) + return; + if (av->index == src_index + && (av->unit_offset >= unit_delta) + && av->value) + { + ipa_argagg_value new_av; + gcc_checking_assert (av->value); + new_av.value = av->value; + new_av.unit_offset = av->unit_offset - unit_delta; + new_av.index = dest_index; + new_av.by_ref = av->by_ref; + + gcc_assert (first + || new_av.unit_offset > prev_unit_offset); + prev_unit_offset = new_av.unit_offset; + first = false; + + res->safe_push (new_av); + } + } +} + +/* Push to RES information about single lattices describing aggregate values in + PLATS as those describing parameter DEST_INDEX and the original offset minus + UNIT_DELTA. Return true if any item has been pushed to RES. */ + +static bool +push_agg_values_from_plats (ipcp_param_lattices *plats, int dest_index, + unsigned unit_delta, + vec *res) +{ + if (plats->aggs_contain_variable) + return false; + + bool pushed_sth = false; + bool first = true; + unsigned prev_unit_offset = 0; + for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next) + if (aglat->is_single_const () + && (aglat->offset / BITS_PER_UNIT - unit_delta) >= 0) + { + ipa_argagg_value iav; + iav.value = aglat->values->value; + iav.unit_offset = aglat->offset / BITS_PER_UNIT - unit_delta; + iav.index = dest_index; + iav.by_ref = plats->aggs_by_ref; + + gcc_assert (first + || iav.unit_offset > prev_unit_offset); + prev_unit_offset = iav.unit_offset; + first = false; + + pushed_sth = true; + res->safe_push (iav); + } + return pushed_sth; +} + +/* Turn all values in LIST that are not present in OTHER into NULL_TREEs. + Return the number of remaining valid entries. */ + +static unsigned +intersect_argaggs_with (vec &elts, + const vec &other) +{ + unsigned valid_entries = 0; + unsigned j = 0; + for (unsigned i = 0; i < elts.length (); i++) + { + if (!elts[i].value) + continue; + + unsigned this_index = elts[i].index; + unsigned this_offset = elts[i].unit_offset; + + while (j < other.length () + && (other[j].index < this_index + || (other[j].index == this_index + && other[j].unit_offset < this_offset))) + j++; + + if (j >= other.length ()) + { + elts[i].value = NULL_TREE; + continue; + } + + if (other[j].index == this_index + && other[j].unit_offset == this_offset + && other[j].by_ref == elts[i].by_ref + && other[j].value + && values_equal_for_ipcp_p (other[j].value, elts[i].value)) + valid_entries++; + else + elts[i].value = NULL_TREE; + } + return valid_entries; +} + /* Mark bot aggregate and scalar lattices as containing an unknown variable, return true is any of them has not been marked as such so far. */ @@ -1401,26 +1688,6 @@ ipacp_value_safe_for_type (tree param_type, tree value) return false; } -/* Return true iff X and Y should be considered equal values by IPA-CP. */ - -static bool -values_equal_for_ipcp_p (tree x, tree y) -{ - gcc_checking_assert (x != NULL_TREE && y != NULL_TREE); - - if (x == y) - return true; - - if (TREE_CODE (x) == ADDR_EXPR - && TREE_CODE (y) == ADDR_EXPR - && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL - && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL) - return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)), - DECL_INITIAL (TREE_OPERAND (y, 0)), 0); - else - return operand_equal_p (x, y, 0); -} - /* Return the result of a (possibly arithmetic) operation on the constant value INPUT. OPERAND is 2nd operand for binary operation. RES_TYPE is the type of the parameter to which the result is passed. Return @@ -1701,26 +1968,6 @@ ipa_value_range_from_jfunc (ipa_node_params *info, cgraph_edge *cs, return vr; } -/* See if NODE is a clone with a known aggregate value at a given OFFSET of a - parameter with the given INDEX. */ - -static tree -get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset, - int index) -{ - struct ipa_agg_replacement_value *aggval; - - aggval = ipa_get_agg_replacements_for_node (node); - while (aggval) - { - if (aggval->offset == offset - && aggval->index == index) - return aggval->value; - aggval = aggval->next; - } - return NULL_TREE; -} - /* Determine whether ITEM, jump function for an aggregate part, evaluates to a single known constant value and if so, return it. Otherwise return NULL. NODE and INFO describes the caller node or the one it is inlined to, and @@ -1729,7 +1976,7 @@ get_clone_agg_value (struct cgraph_node *node, HOST_WIDE_INT offset, static tree ipa_agg_value_from_node (class ipa_node_params *info, struct cgraph_node *node, - struct ipa_agg_jf_item *item) + const ipa_agg_jf_item *item) { tree value = NULL_TREE; int src_idx; @@ -1749,9 +1996,13 @@ ipa_agg_value_from_node (class ipa_node_params *info, { if (item->jftype == IPA_JF_PASS_THROUGH) value = info->known_csts[src_idx]; - else - value = get_clone_agg_value (node, item->value.load_agg.offset, - src_idx); + else if (ipcp_transformation *ts = ipcp_get_transformation_summary (node)) + { + ipa_argagg_value_list avl (ts); + value = avl.get_value (src_idx, + item->value.load_agg.offset / BITS_PER_UNIT, + item->value.load_agg.by_ref); + } } else if (info->lattices) { @@ -2979,15 +3230,16 @@ propagate_constants_across_call (struct cgraph_edge *cs) } /* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS - KNOWN_CONTEXTS, KNOWN_AGGS or AGG_REPS return the destination. The latter - three can be NULL. If AGG_REPS is not NULL, KNOWN_AGGS is ignored. */ + KNOWN_CONTEXTS, and known aggregates either in AVS or KNOWN_AGGS return + the destination. The latter three can be NULL. If AGG_REPS is not NULL, + KNOWN_AGGS is ignored. */ static tree ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, const vec &known_csts, const vec &known_contexts, const vec &known_aggs, - struct ipa_agg_replacement_value *agg_reps, + const ipa_argagg_value_list *avs, bool *speculative) { int param_index = ie->indirect_info->param_index; @@ -3007,20 +3259,10 @@ ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, if (ie->indirect_info->agg_contents) { t = NULL; - if (agg_reps && ie->indirect_info->guaranteed_unmodified) - { - while (agg_reps) - { - if (agg_reps->index == param_index - && agg_reps->offset == ie->indirect_info->offset - && agg_reps->by_ref == ie->indirect_info->by_ref) - { - t = agg_reps->value; - break; - } - agg_reps = agg_reps->next; - } - } + if (avs && ie->indirect_info->guaranteed_unmodified) + t = avs->get_value (param_index, + ie->indirect_info->offset / BITS_PER_UNIT, + ie->indirect_info->by_ref); if (!t) { const ipa_agg_value_set *agg; @@ -3063,20 +3305,10 @@ ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, t = NULL; /* Try to work out value of virtual table pointer value in replacements. */ - if (!t && agg_reps && !ie->indirect_info->by_ref) - { - while (agg_reps) - { - if (agg_reps->index == param_index - && agg_reps->offset == ie->indirect_info->offset - && agg_reps->by_ref) - { - t = agg_reps->value; - break; - } - agg_reps = agg_reps->next; - } - } + if (!t && avs && !ie->indirect_info->by_ref) + t = avs->get_value (param_index, + ie->indirect_info->offset / BITS_PER_UNIT, + true); /* Try to work out value of virtual table pointer value in known aggregate values. */ @@ -4103,7 +4335,7 @@ ipcp_discover_new_direct_edges (struct cgraph_node *node, vec known_csts, vec known_contexts, - struct ipa_agg_replacement_value *aggvals) + vec *aggvals) { struct cgraph_edge *ie, *next_ie; bool found = false; @@ -4114,8 +4346,9 @@ ipcp_discover_new_direct_edges (struct cgraph_node *node, bool speculative; next_ie = ie->next_callee; + ipa_argagg_value_list avs (aggvals); target = ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts, - vNULL, aggvals, &speculative); + vNULL, &avs, &speculative); if (target) { bool agg_contents = ie->indirect_info->agg_contents; @@ -4249,11 +4482,15 @@ cgraph_edge_brings_value_p (cgraph_edge *cs, ipcp_value_source *src, if (caller_info->ipcp_orig_node) { - tree t; + tree t = NULL_TREE; if (src->offset == -1) t = caller_info->known_csts[src->index]; - else - t = get_clone_agg_value (cs->caller, src->offset, src->index); + else if (ipcp_transformation *ts + = ipcp_get_transformation_summary (cs->caller)) + { + ipa_argagg_value_list avl (ts); + t = avl.get_value (src->index, src->offset / BITS_PER_UNIT); + } return (t != NULL_TREE && values_equal_for_ipcp_p (src->val->value, t)); } @@ -5060,13 +5297,12 @@ static struct cgraph_node * create_specialized_node (struct cgraph_node *node, vec known_csts, vec known_contexts, - struct ipa_agg_replacement_value *aggvals, + vec *aggvals, vec &callers) { ipa_node_params *new_info, *info = ipa_node_params_sum->get (node); vec *replace_trees = NULL; vec *new_params = NULL; - struct ipa_agg_replacement_value *av; struct cgraph_node *new_node; int i, count = ipa_get_param_count (info); clone_info *cinfo = clone_info::get (node); @@ -5194,8 +5430,8 @@ create_specialized_node (struct cgraph_node *node, new_node->expand_all_artificial_thunks (); ipa_set_node_agg_value_chain (new_node, aggvals); - for (av = aggvals; av; av = av->next) - new_node->maybe_create_reference (av->value, NULL); + for (const ipa_argagg_value &av : aggvals) + new_node->maybe_create_reference (av.value, NULL); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -5210,7 +5446,11 @@ create_specialized_node (struct cgraph_node *node, } } if (aggvals) - ipa_dump_agg_replacement_values (dump_file, aggvals); + { + fprintf (dump_file, " Aggregate replacements:"); + ipa_argagg_value_list avs (aggvals); + avs.dump (dump_file); + } } new_info = ipa_node_params_sum->get (new_node); @@ -5219,7 +5459,8 @@ create_specialized_node (struct cgraph_node *node, new_info->known_csts = known_csts; new_info->known_contexts = known_contexts; - ipcp_discover_new_direct_edges (new_node, known_csts, known_contexts, aggvals); + ipcp_discover_new_direct_edges (new_node, known_csts, known_contexts, + aggvals); return new_node; } @@ -5252,7 +5493,8 @@ self_recursive_pass_through_p (cgraph_edge *cs, ipa_jump_func *jfunc, int i, pass-through. */ static bool -self_recursive_agg_pass_through_p (cgraph_edge *cs, ipa_agg_jf_item *jfunc, +self_recursive_agg_pass_through_p (const cgraph_edge *cs, + const ipa_agg_jf_item *jfunc, int i, bool simple = true) { enum availability availability; @@ -5427,376 +5669,215 @@ find_more_contexts_for_caller_subset (cgraph_node *node, } } -/* Go through PLATS and create a vector of values consisting of values and - offsets (minus OFFSET) of lattices that contain only a single value. */ +/* Push all aggregate values coming along edge CS for parameter number INDEX to + RES. If INTERIM is non-NULL, it contains the current interim state of + collected aggregate values which can be used to compute values passed over + self-recursive edges. -static vec -copy_plats_to_inter (class ipcp_param_lattices *plats, HOST_WIDE_INT offset) -{ - vec res = vNULL; - - if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom) - return vNULL; - - for (struct ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next) - if (aglat->is_single_const ()) - { - struct ipa_agg_value ti; - ti.offset = aglat->offset - offset; - ti.value = aglat->values->value; - res.safe_push (ti); - } - return res; -} - -/* Intersect all values in INTER with single value lattices in PLATS (while - subtracting OFFSET). */ + This basically one iteration of push_agg_values_from_edge over one + parameter, which allows for simpler early returns. */ static void -intersect_with_plats (class ipcp_param_lattices *plats, - vec *inter, - HOST_WIDE_INT offset) +push_agg_values_for_index_from_edge (struct cgraph_edge *cs, int index, + vec *res, + const ipa_argagg_value_list *interim) { - struct ipcp_agg_lattice *aglat; - struct ipa_agg_value *item; - int k; + bool agg_values_from_caller = false; + bool agg_jf_preserved = false; + unsigned unit_delta = UINT_MAX; + int src_idx = -1; + ipa_jump_func *jfunc = ipa_get_ith_jump_func (ipa_edge_args_sum->get (cs), + index); - if (!plats->aggs || plats->aggs_contain_variable || plats->aggs_bottom) - { - inter->release (); - return; - } - - aglat = plats->aggs; - FOR_EACH_VEC_ELT (*inter, k, item) - { - bool found = false; - if (!item->value) - continue; - while (aglat) - { - if (aglat->offset - offset > item->offset) - break; - if (aglat->offset - offset == item->offset) - { - if (aglat->is_single_const ()) - { - tree value = aglat->values->value; - - if (values_equal_for_ipcp_p (item->value, value)) - found = true; - } - break; - } - aglat = aglat->next; - } - if (!found) - item->value = NULL_TREE; - } -} - -/* Copy aggregate replacement values of NODE (which is an IPA-CP clone) to the - vector result while subtracting OFFSET from the individual value offsets. */ - -static vec -agg_replacements_to_vector (struct cgraph_node *node, int index, - HOST_WIDE_INT offset) -{ - struct ipa_agg_replacement_value *av; - vec res = vNULL; - - for (av = ipa_get_agg_replacements_for_node (node); av; av = av->next) - if (av->index == index - && (av->offset - offset) >= 0) - { - struct ipa_agg_value item; - gcc_checking_assert (av->value); - item.offset = av->offset - offset; - item.value = av->value; - res.safe_push (item); - } - - return res; -} - -/* Intersect all values in INTER with those that we have already scheduled to - be replaced in parameter number INDEX of NODE, which is an IPA-CP clone - (while subtracting OFFSET). */ - -static void -intersect_with_agg_replacements (struct cgraph_node *node, int index, - vec *inter, - HOST_WIDE_INT offset) -{ - struct ipa_agg_replacement_value *srcvals; - struct ipa_agg_value *item; - int i; - - srcvals = ipa_get_agg_replacements_for_node (node); - if (!srcvals) - { - inter->release (); - return; - } - - FOR_EACH_VEC_ELT (*inter, i, item) - { - struct ipa_agg_replacement_value *av; - bool found = false; - if (!item->value) - continue; - for (av = srcvals; av; av = av->next) - { - gcc_checking_assert (av->value); - if (av->index == index - && av->offset - offset == item->offset) - { - if (values_equal_for_ipcp_p (item->value, av->value)) - found = true; - break; - } - } - if (!found) - item->value = NULL_TREE; - } -} - -/* Intersect values in INTER with aggregate values that come along edge CS to - parameter number INDEX and return it. If INTER does not actually exist yet, - copy all incoming values to it. If we determine we ended up with no values - whatsoever, return a released vector. */ - -static vec -intersect_aggregates_with_edge (struct cgraph_edge *cs, int index, - vec inter) -{ - struct ipa_jump_func *jfunc; - jfunc = ipa_get_ith_jump_func (ipa_edge_args_sum->get (cs), index); if (jfunc->type == IPA_JF_PASS_THROUGH && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR) { - ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller); - int src_idx = ipa_get_jf_pass_through_formal_id (jfunc); - - if (caller_info->ipcp_orig_node) - { - struct cgraph_node *orig_node = caller_info->ipcp_orig_node; - class ipcp_param_lattices *orig_plats; - ipa_node_params *orig_info = ipa_node_params_sum->get (orig_node); - orig_plats = ipa_get_parm_lattices (orig_info, src_idx); - if (agg_pass_through_permissible_p (orig_plats, jfunc)) - { - if (!inter.exists ()) - inter = agg_replacements_to_vector (cs->caller, src_idx, 0); - else - intersect_with_agg_replacements (cs->caller, src_idx, - &inter, 0); - return inter; - } - } - else - { - class ipcp_param_lattices *src_plats; - src_plats = ipa_get_parm_lattices (caller_info, src_idx); - if (agg_pass_through_permissible_p (src_plats, jfunc)) - { - /* Currently we do not produce clobber aggregate jump - functions, adjust when we do. */ - gcc_checking_assert (!jfunc->agg.items); - if (!inter.exists ()) - inter = copy_plats_to_inter (src_plats, 0); - else - intersect_with_plats (src_plats, &inter, 0); - return inter; - } - } + agg_values_from_caller = true; + agg_jf_preserved = ipa_get_jf_pass_through_agg_preserved (jfunc); + src_idx = ipa_get_jf_pass_through_formal_id (jfunc); + unit_delta = 0; } else if (jfunc->type == IPA_JF_ANCESTOR && ipa_get_jf_ancestor_agg_preserved (jfunc)) { - ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller); - int src_idx = ipa_get_jf_ancestor_formal_id (jfunc); - class ipcp_param_lattices *src_plats; - HOST_WIDE_INT delta = ipa_get_jf_ancestor_offset (jfunc); + agg_values_from_caller = true; + agg_jf_preserved = true; + src_idx = ipa_get_jf_ancestor_formal_id (jfunc); + unit_delta = ipa_get_jf_ancestor_offset (jfunc) / BITS_PER_UNIT; + } + ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller); + if (agg_values_from_caller) + { if (caller_info->ipcp_orig_node) { - if (!inter.exists ()) - inter = agg_replacements_to_vector (cs->caller, src_idx, delta); - else - intersect_with_agg_replacements (cs->caller, src_idx, &inter, - delta); + struct cgraph_node *orig_node = caller_info->ipcp_orig_node; + ipcp_transformation *ts + = ipcp_get_transformation_summary (cs->caller); + ipa_node_params *orig_info = ipa_node_params_sum->get (orig_node); + ipcp_param_lattices *orig_plats + = ipa_get_parm_lattices (orig_info, src_idx); + if (ts + && orig_plats->aggs + && (agg_jf_preserved || !orig_plats->aggs_by_ref)) + { + ipa_argagg_value_list src (ts); + src.push_adjusted_values (src_idx, index, unit_delta, res); + return; + } } else { - src_plats = ipa_get_parm_lattices (caller_info, src_idx); - /* Currently we do not produce clobber aggregate jump - functions, adjust when we do. */ - gcc_checking_assert (!src_plats->aggs || !jfunc->agg.items); - if (!inter.exists ()) - inter = copy_plats_to_inter (src_plats, delta); - else - intersect_with_plats (src_plats, &inter, delta); + ipcp_param_lattices *src_plats + = ipa_get_parm_lattices (caller_info, src_idx); + if (src_plats->aggs + && !src_plats->aggs_bottom + && (agg_jf_preserved || !src_plats->aggs_by_ref)) + { + if (interim && self_recursive_pass_through_p (cs, jfunc, index)) + { + interim->push_adjusted_values (src_idx, index, unit_delta, + res); + return; + } + if (!src_plats->aggs_contain_variable) + { + push_agg_values_from_plats (src_plats, index, unit_delta, + res); + return; + } + } } - return inter; } - if (jfunc->agg.items) + if (!jfunc->agg.items) + return; + bool first = true; + unsigned prev_unit_offset = 0; + for (const ipa_agg_jf_item &agg_jf : *jfunc->agg.items) { - ipa_node_params *caller_info = ipa_node_params_sum->get (cs->caller); - struct ipa_agg_value *item; - int k; + tree value, srcvalue; + /* Besides simple pass-through aggregate jump function, arithmetic + aggregate jump function could also bring same aggregate value as + parameter passed-in for self-feeding recursive call. For example, - if (!inter.exists ()) - for (unsigned i = 0; i < jfunc->agg.items->length (); i++) - { - struct ipa_agg_jf_item *agg_item = &(*jfunc->agg.items)[i]; - tree value = ipa_agg_value_from_node (caller_info, cs->caller, - agg_item); - if (value) - { - struct ipa_agg_value agg_value; + fn (int *i) + { + int j = *i & 1; + fn (&j); + } - agg_value.value = value; - agg_value.offset = agg_item->offset; - inter.safe_push (agg_value); - } - } + Given that *i is 0, recursive propagation via (*i & 1) also gets 0. */ + if (interim + && self_recursive_agg_pass_through_p (cs, &agg_jf, index, false) + && (srcvalue = interim->get_value(index, + agg_jf.offset / BITS_PER_UNIT))) + value = ipa_get_jf_arith_result (agg_jf.value.pass_through.operation, + srcvalue, + agg_jf.value.pass_through.operand, + agg_jf.type); else - FOR_EACH_VEC_ELT (inter, k, item) - { - int l = 0; - bool found = false; + value = ipa_agg_value_from_node (caller_info, cs->caller, + &agg_jf); + if (value) + { + struct ipa_argagg_value iav; + iav.value = value; + iav.unit_offset = agg_jf.offset / BITS_PER_UNIT; + iav.index = index; + iav.by_ref = jfunc->agg.by_ref; - if (!item->value) - continue; + gcc_assert (first + || iav.unit_offset > prev_unit_offset); + prev_unit_offset = iav.unit_offset; + first = false; - while ((unsigned) l < jfunc->agg.items->length ()) - { - struct ipa_agg_jf_item *ti; - ti = &(*jfunc->agg.items)[l]; - if (ti->offset > item->offset) - break; - if (ti->offset == item->offset) - { - tree value; - - /* Besides simple pass-through aggregate jump function, - arithmetic aggregate jump function could also bring - same aggregate value as parameter passed-in for - self-feeding recursive call. For example, - - fn (int *i) - { - int j = *i & 1; - fn (&j); - } - - Given that *i is 0, recursive propagation via (*i & 1) - also gets 0. */ - if (self_recursive_agg_pass_through_p (cs, ti, index, - false)) - value = ipa_get_jf_arith_result ( - ti->value.pass_through.operation, - item->value, - ti->value.pass_through.operand, - ti->type); - else - value = ipa_agg_value_from_node (caller_info, - cs->caller, ti); - - if (value && values_equal_for_ipcp_p (item->value, value)) - found = true; - break; - } - l++; - } - if (!found) - item->value = NULL; - } + res->safe_push (iav); + } } - else - { - inter.release (); - return vNULL; - } - return inter; + return; } -/* Look at edges in CALLERS and collect all known aggregate values that arrive - from all of them. */ +/* Push all aggregate values coming along edge CS to RES. DEST_INFO is the + description of ultimate callee of CS or the one it was cloned from (the + summary where lattices are). If INTERIM is non-NULL, it contains the + current interim state of collected aggregate values which can be used to + compute values passed over self-recursive edges and to skip values which + clearly will not be part of intersection with INTERIM. */ -static struct ipa_agg_replacement_value * +static void +push_agg_values_from_edge (struct cgraph_edge *cs, + ipa_node_params *dest_info, + vec *res, + const ipa_argagg_value_list *interim) +{ + ipa_edge_args *args = ipa_edge_args_sum->get (cs); + if (!args) + return; + + int count = MIN (ipa_get_param_count (dest_info), + ipa_get_cs_argument_count (args)); + + unsigned interim_index = 0; + for (int index = 0; index < count; index++) + { + if (interim) + { + while (interim_index < interim->m_elts.size () + && interim->m_elts[interim_index].value + && interim->m_elts[interim_index].index < index) + interim_index++; + if (interim_index >= interim->m_elts.size () + || interim->m_elts[interim_index].index > index) + continue; + } + + ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, index); + if (plats->aggs_bottom) + continue; + push_agg_values_for_index_from_edge (cs, index, res, interim); + } +} + + +/* Look at edges in CALLERS and collect all known aggregate values that arrive + from all of them. Return nullptr if there are none. */ + +static struct vec * find_aggregate_values_for_callers_subset (struct cgraph_node *node, const vec &callers) { ipa_node_params *dest_info = ipa_node_params_sum->get (node); - struct ipa_agg_replacement_value *res; - struct ipa_agg_replacement_value **tail = &res; - struct cgraph_edge *cs; - int i, j, count = ipa_get_param_count (dest_info); + if (dest_info->ipcp_orig_node) + dest_info = ipa_node_params_sum->get (dest_info->ipcp_orig_node); - FOR_EACH_VEC_ELT (callers, j, cs) + /* gather_edges_for_value puts a non-recursive call into the first element of + callers if it can. */ + auto_vec interim; + push_agg_values_from_edge (callers[0], dest_info, &interim, NULL); + + unsigned valid_entries = interim.length (); + if (!valid_entries) + return nullptr; + + unsigned caller_count = callers.length(); + for (unsigned i = 1; i < caller_count; i++) { - ipa_edge_args *args = ipa_edge_args_sum->get (cs); - if (!args) - { - count = 0; - break; - } - int c = ipa_get_cs_argument_count (args); - if (c < count) - count = c; + auto_vec last; + ipa_argagg_value_list avs (&interim); + push_agg_values_from_edge (callers[i], dest_info, &last, &avs); + + valid_entries = intersect_argaggs_with (interim, last); + if (!valid_entries) + return nullptr; } - for (i = 0; i < count; i++) - { - struct cgraph_edge *cs; - vec inter = vNULL; - struct ipa_agg_value *item; - class ipcp_param_lattices *plats = ipa_get_parm_lattices (dest_info, i); - int j; - - /* Among other things, the following check should deal with all by_ref - mismatches. */ - if (plats->aggs_bottom) - continue; - - FOR_EACH_VEC_ELT (callers, j, cs) - { - struct ipa_jump_func *jfunc - = ipa_get_ith_jump_func (ipa_edge_args_sum->get (cs), i); - if (self_recursive_pass_through_p (cs, jfunc, i) - && (!plats->aggs_by_ref - || ipa_get_jf_pass_through_agg_preserved (jfunc))) - continue; - inter = intersect_aggregates_with_edge (cs, i, inter); - - if (!inter.exists ()) - goto next_param; - } - - FOR_EACH_VEC_ELT (inter, j, item) - { - struct ipa_agg_replacement_value *v; - - if (!item->value) - continue; - - v = ggc_alloc (); - v->index = i; - v->offset = item->offset; - v->value = item->value; - v->by_ref = plats->aggs_by_ref; - *tail = v; - tail = &v->next; - } - - next_param: - if (inter.exists ()) - inter.release (); - } - *tail = NULL; + vec *res = NULL; + vec_safe_reserve_exact (res, valid_entries); + for (const ipa_argagg_value &av : interim) + if (av.value) + res->quick_push(av); + gcc_checking_assert (res->length () == valid_entries); return res; } @@ -5837,72 +5918,23 @@ cgraph_edge_brings_all_scalars_for_node (struct cgraph_edge *cs, /* Determine whether CS also brings all aggregate values that NODE is specialized for. */ + static bool cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs, struct cgraph_node *node) { - struct ipa_agg_replacement_value *aggval; - int i, ec, count; - - aggval = ipa_get_agg_replacements_for_node (node); - if (!aggval) + ipcp_transformation *ts = ipcp_get_transformation_summary (node); + if (!ts || vec_safe_is_empty (ts->m_agg_values)) return true; - ipa_node_params *clone_node_info = ipa_node_params_sum->get (node); - count = ipa_get_param_count (clone_node_info); - ec = ipa_get_cs_argument_count (ipa_edge_args_sum->get (cs)); - if (ec < count) - for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next) - if (aggval->index >= ec) - return false; - - ipa_node_params *orig_node_info - = ipa_node_params_sum->get (clone_node_info->ipcp_orig_node); - - for (i = 0; i < count; i++) - { - class ipcp_param_lattices *plats; - bool interesting = false; - for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next) - if (aggval->index == i) - { - interesting = true; - break; - } - if (!interesting) - continue; - - plats = ipa_get_parm_lattices (orig_node_info, aggval->index); - if (plats->aggs_bottom) - return false; - - vec values = intersect_aggregates_with_edge (cs, i, vNULL); - if (!values.exists ()) - return false; - - for (struct ipa_agg_replacement_value *av = aggval; av; av = av->next) - if (aggval->index == i) - { - struct ipa_agg_value *item; - int j; - bool found = false; - FOR_EACH_VEC_ELT (values, j, item) - if (item->value - && item->offset == av->offset - && values_equal_for_ipcp_p (item->value, av->value)) - { - found = true; - break; - } - if (!found) - { - values.release (); - return false; - } - } - values.release (); - } - return true; + const ipa_argagg_value_list existing (ts->m_agg_values); + auto_vec edge_values; + ipa_node_params *dest_info = ipa_node_params_sum->get (node); + gcc_checking_assert (dest_info->ipcp_orig_node); + dest_info = ipa_node_params_sum->get (dest_info->ipcp_orig_node); + push_agg_values_from_edge (cs, dest_info, &edge_values, &existing); + const ipa_argagg_value_list avl (&edge_values); + return avl.superset_of_p (existing); } /* Given an original NODE and a VAL for which we have already created a @@ -6006,28 +6038,22 @@ copy_known_vectors_add_val (ipa_auto_call_arg_values *avals, AGGVALS list. */ DEBUG_FUNCTION bool -ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *aggvals, +ipcp_val_agg_replacement_ok_p (vec *aggvals, int index, HOST_WIDE_INT offset, tree value) { if (offset == -1) return true; - while (aggvals) - { - if (aggvals->index == index - && aggvals->offset == offset - && values_equal_for_ipcp_p (aggvals->value, value)) - return true; - aggvals = aggvals->next; - } - return false; + const ipa_argagg_value_list avl (aggvals); + tree v = avl.get_value (index, offset / BITS_PER_UNIT); + return v && values_equal_for_ipcp_p (v, value); } /* Return true if offset is minus one because source of a polymorphic context cannot be an aggregate value. */ DEBUG_FUNCTION bool -ipcp_val_agg_replacement_ok_p (ipa_agg_replacement_value *, +ipcp_val_agg_replacement_ok_p (vec *, int , HOST_WIDE_INT offset, ipa_polymorphic_call_context) { @@ -6047,7 +6073,6 @@ decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset, ipcp_value *val, ipa_auto_call_arg_values *avals, vec *self_gen_clones) { - struct ipa_agg_replacement_value *aggvals; int caller_count; sreal freq_sum; profile_count count_sum, rec_count_sum; @@ -6126,7 +6151,8 @@ decide_about_value (struct cgraph_node *node, int index, HOST_WIDE_INT offset, } find_more_scalar_values_for_callers_subset (node, known_csts, callers); find_more_contexts_for_caller_subset (node, &known_contexts, callers); - aggvals = find_aggregate_values_for_callers_subset (node, callers); + vec *aggvals + = find_aggregate_values_for_callers_subset (node, callers); gcc_checking_assert (ipcp_val_agg_replacement_ok_p (aggvals, index, offset, val->value)); val->spec_node = create_specialized_node (node, known_csts, known_contexts, @@ -6277,7 +6303,7 @@ decide_whether_version_node (struct cgraph_node *node) = copy_useful_known_contexts (avals.m_known_contexts); find_more_scalar_values_for_callers_subset (node, known_csts, callers); find_more_contexts_for_caller_subset (node, &known_contexts, callers); - ipa_agg_replacement_value *aggvals + vec *aggvals = find_aggregate_values_for_callers_subset (node, callers); if (!known_contexts_useful_p (known_contexts)) diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc index ca5b9f31570..6196d7e6bdb 100644 --- a/gcc/ipa-prop.cc +++ b/gcc/ipa-prop.cc @@ -3057,13 +3057,11 @@ ipa_analyze_node (struct cgraph_node *node) return; info->analysis_done = 1; - if (ipa_func_spec_opts_forbid_analysis_p (node)) + if (ipa_func_spec_opts_forbid_analysis_p (node) + || (count_formal_params (node->decl) + >= (1 << IPA_PROP_ARG_INDEX_LIMIT_BITS))) { - for (int i = 0; i < ipa_get_param_count (info); i++) - { - ipa_set_param_used (info, i, true); - ipa_set_controlled_uses (info, i, IPA_UNDESCRIBED_USE); - } + gcc_assert (!ipa_get_param_count (info)); return; } @@ -4383,11 +4381,11 @@ ipcp_free_transformation_sum (void) void ipa_set_node_agg_value_chain (struct cgraph_node *node, - struct ipa_agg_replacement_value *aggvals) + vec *aggs) { ipcp_transformation_initialize (); ipcp_transformation *s = ipcp_transformation_sum->get_create (node); - s->agg_values = aggvals; + s->m_agg_values = aggs; } /* Hook that is called by cgraph.cc when an edge is removed. Adjust reference @@ -4532,12 +4530,10 @@ ipa_add_new_function (cgraph_node *node, void *data ATTRIBUTE_UNUSED) /* Hook that is called by summary when a node is duplicated. */ void -ipa_node_params_t::duplicate(cgraph_node *src, cgraph_node *dst, +ipa_node_params_t::duplicate(cgraph_node *, cgraph_node *, ipa_node_params *old_info, ipa_node_params *new_info) { - ipa_agg_replacement_value *old_av, *new_av; - new_info->descriptors = vec_safe_copy (old_info->descriptors); new_info->lattices = NULL; new_info->ipcp_orig_node = old_info->ipcp_orig_node; @@ -4547,23 +4543,6 @@ ipa_node_params_t::duplicate(cgraph_node *src, cgraph_node *dst, new_info->analysis_done = old_info->analysis_done; new_info->node_enqueued = old_info->node_enqueued; new_info->versionable = old_info->versionable; - - old_av = ipa_get_agg_replacements_for_node (src); - if (old_av) - { - new_av = NULL; - while (old_av) - { - struct ipa_agg_replacement_value *v; - - v = ggc_alloc (); - memcpy (v, old_av, sizeof (*v)); - v->next = new_av; - new_av = v; - old_av = old_av->next; - } - ipa_set_node_agg_value_chain (dst, new_av); - } } /* Duplication of ipcp transformation summaries. */ @@ -4576,17 +4555,9 @@ ipcp_transformation_t::duplicate(cgraph_node *, cgraph_node *dst, /* Avoid redundant work of duplicating vectors we will never use. */ if (dst->inlined_to) return; + dst_trans->m_agg_values = vec_safe_copy (src_trans->m_agg_values); dst_trans->bits = vec_safe_copy (src_trans->bits); dst_trans->m_vr = vec_safe_copy (src_trans->m_vr); - ipa_agg_replacement_value *agg = src_trans->agg_values, - **aggptr = &dst_trans->agg_values; - while (agg) - { - *aggptr = ggc_alloc (); - **aggptr = *agg; - agg = agg->next; - aggptr = &(*aggptr)->next; - } } /* Register our cgraph hooks if they are not already there. */ @@ -4703,23 +4674,6 @@ ipa_print_all_params (FILE * f) ipa_print_node_params (f, node); } -/* Dump the AV linked list. */ - -void -ipa_dump_agg_replacement_values (FILE *f, struct ipa_agg_replacement_value *av) -{ - bool comma = false; - fprintf (f, " Aggregate replacements:"); - for (; av; av = av->next) - { - fprintf (f, "%s %i[" HOST_WIDE_INT_PRINT_DEC "]=", comma ? "," : "", - av->index, av->offset); - print_generic_expr (f, av->value); - comma = true; - } - fprintf (f, "\n"); -} - /* Stream out jump function JUMP_FUNC to OB. */ static void @@ -5356,31 +5310,31 @@ write_ipcp_transformation_info (output_block *ob, cgraph_node *node) int node_ref; unsigned int count = 0; lto_symtab_encoder_t encoder; - struct ipa_agg_replacement_value *aggvals, *av; - aggvals = ipa_get_agg_replacements_for_node (node); encoder = ob->decl_state->symtab_node_encoder; node_ref = lto_symtab_encoder_encode (encoder, node); streamer_write_uhwi (ob, node_ref); - for (av = aggvals; av; av = av->next) - count++; - streamer_write_uhwi (ob, count); - - for (av = aggvals; av; av = av->next) - { - struct bitpack_d bp; - - streamer_write_uhwi (ob, av->offset); - streamer_write_uhwi (ob, av->index); - stream_write_tree (ob, av->value, true); - - bp = bitpack_create (ob->main_stream); - bp_pack_value (&bp, av->by_ref, 1); - streamer_write_bitpack (&bp); - } - ipcp_transformation *ts = ipcp_get_transformation_summary (node); + if (ts && !vec_safe_is_empty (ts->m_agg_values)) + { + streamer_write_uhwi (ob, ts->m_agg_values->length ()); + for (const ipa_argagg_value &av : ts->m_agg_values) + { + struct bitpack_d bp; + + stream_write_tree (ob, av.value, true); + streamer_write_uhwi (ob, av.unit_offset); + streamer_write_uhwi (ob, av.index); + + bp = bitpack_create (ob->main_stream); + bp_pack_value (&bp, av.by_ref, 1); + streamer_write_bitpack (&bp); + } + } + else + streamer_write_uhwi (ob, 0); + if (ts && vec_safe_length (ts->m_vr) > 0) { count = ts->m_vr->length (); @@ -5432,26 +5386,27 @@ static void read_ipcp_transformation_info (lto_input_block *ib, cgraph_node *node, data_in *data_in) { - struct ipa_agg_replacement_value *aggvals = NULL; unsigned int count, i; count = streamer_read_uhwi (ib); - for (i = 0; i 0) { - struct ipa_agg_replacement_value *av; - struct bitpack_d bp; + ipcp_transformation_initialize (); + ipcp_transformation *ts = ipcp_transformation_sum->get_create (node); + vec_safe_grow_cleared (ts->m_agg_values, count, true); + for (i = 0; i m_agg_values)[i];; - av = ggc_alloc (); - av->offset = streamer_read_uhwi (ib); - av->index = streamer_read_uhwi (ib); - av->value = stream_read_tree (ib, data_in); - bp = streamer_read_bitpack (ib); - av->by_ref = bp_unpack_value (&bp, 1); - av->next = aggvals; - aggvals = av; + av->value = stream_read_tree (ib, data_in); + av->unit_offset = streamer_read_uhwi (ib); + av->index = streamer_read_uhwi (ib); + + bitpack_d bp = streamer_read_bitpack (ib); + av->by_ref = bp_unpack_value (&bp, 1); + } } - ipa_set_node_agg_value_chain (node, aggvals); - + count = streamer_read_uhwi (ib); if (count > 0) { @@ -5595,56 +5550,75 @@ ipcp_read_transformation_summaries (void) } } -/* Adjust the aggregate replacements in AGGVAL to reflect parameters skipped in +/* Adjust the aggregate replacements in TS to reflect parameters skipped in NODE but also if any parameter was IPA-SRAed into a scalar go ahead with substitution of the default_definitions of that new param with the appropriate constant. - Return two bools. the first it true if at least one item in AGGVAL still - exists and function body walk should go ahead. The second is true if any - values were already substituted for scalarized parameters and update_cfg - shuld be run after replace_uses_by. */ + If after adjustments there are no aggregate replacements left, the + m_agg_values will be set to NULL. In other cases, it may be shrunk. -static std::pair + Return true if any values were already substituted for scalarized parameters + and update_cfg shuld be run after replace_uses_by. */ + +static bool adjust_agg_replacement_values (cgraph_node *node, - ipa_agg_replacement_value *aggval, + ipcp_transformation *ts, const vec &descriptors) { - struct ipa_agg_replacement_value *v; clone_info *cinfo = clone_info::get (node); if (!cinfo || !cinfo->param_adjustments) - return std::pair (true, false); + return false; - bool anything_left = false; + bool removed_item = false; bool done_replacement = false; - for (v = aggval; v; v = v->next) + unsigned dst_index = 0; + unsigned count = ts->m_agg_values->length (); + for (unsigned i = 0; i < count; i++) { + ipa_argagg_value *v = &(*ts->m_agg_values)[i]; gcc_checking_assert (v->index >= 0); - unsigned unit_offset = v->offset / BITS_PER_UNIT; tree cst_type = TREE_TYPE (v->value); int split_idx; int new_idx = cinfo->param_adjustments->get_updated_index_or_split (v->index, - unit_offset, + v->unit_offset, cst_type, &split_idx); - v->index = new_idx; if (new_idx >= 0) - anything_left = true; - else if (split_idx >= 0) { - tree parm = ipa_get_param (descriptors, split_idx); - tree ddef = ssa_default_def (cfun, parm); - if (ddef) + v->index = new_idx; + if (removed_item) + (*ts->m_agg_values)[dst_index] = *v; + dst_index++; + } + else + { + removed_item = true; + if (split_idx >= 0) { - replace_uses_by (ddef, v->value); - done_replacement = true; + tree parm = ipa_get_param (descriptors, split_idx); + tree ddef = ssa_default_def (cfun, parm); + if (ddef) + { + replace_uses_by (ddef, v->value); + done_replacement = true; + } } } } - return std::pair (anything_left, done_replacement); + + if (dst_index == 0) + { + ggc_free (ts->m_agg_values); + ts->m_agg_values = NULL; + } + else if (removed_item) + ts->m_agg_values->truncate (dst_index); + + return done_replacement; } /* Dominator walker driving the ipcp modification phase. */ @@ -5654,10 +5628,9 @@ class ipcp_modif_dom_walker : public dom_walker public: ipcp_modif_dom_walker (struct ipa_func_body_info *fbi, vec *descs, - struct ipa_agg_replacement_value *av, - bool *sc) + ipcp_transformation *ts, bool *sc) : dom_walker (CDI_DOMINATORS), m_fbi (fbi), m_descriptors (descs), - m_aggval (av), m_something_changed (sc) {} + m_ts (ts), m_something_changed (sc) {} edge before_dom_children (basic_block) final override; bool cleanup_eh () @@ -5666,7 +5639,7 @@ public: private: struct ipa_func_body_info *m_fbi; vec *m_descriptors; - struct ipa_agg_replacement_value *m_aggval; + ipcp_transformation *m_ts; bool *m_something_changed; auto_bitmap m_need_eh_cleanup; }; @@ -5677,10 +5650,9 @@ ipcp_modif_dom_walker::before_dom_children (basic_block bb) gimple_stmt_iterator gsi; for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { - struct ipa_agg_replacement_value *v; gimple *stmt = gsi_stmt (gsi); tree rhs, val, t; - HOST_WIDE_INT offset; + HOST_WIDE_INT bit_offset; poly_int64 size; int index; bool by_ref, vce; @@ -5708,32 +5680,30 @@ ipcp_modif_dom_walker::before_dom_children (basic_block bb) continue; if (!ipa_load_from_parm_agg (m_fbi, m_descriptors, stmt, rhs, &index, - &offset, &size, &by_ref)) + &bit_offset, &size, &by_ref)) continue; - for (v = m_aggval; v; v = v->next) - if (v->index == index - && v->offset == offset) - break; + unsigned unit_offset = bit_offset / BITS_PER_UNIT; + ipa_argagg_value_list avl (m_ts); + tree v = avl.get_value (index, unit_offset, by_ref); + if (!v - || v->by_ref != by_ref - || maybe_ne (tree_to_poly_int64 (TYPE_SIZE (TREE_TYPE (v->value))), - size)) + || maybe_ne (tree_to_poly_int64 (TYPE_SIZE (TREE_TYPE (v))), size)) continue; - gcc_checking_assert (is_gimple_ip_invariant (v->value)); - if (!useless_type_conversion_p (TREE_TYPE (rhs), TREE_TYPE (v->value))) + gcc_checking_assert (is_gimple_ip_invariant (v)); + if (!useless_type_conversion_p (TREE_TYPE (rhs), TREE_TYPE (v))) { - if (fold_convertible_p (TREE_TYPE (rhs), v->value)) - val = fold_build1 (NOP_EXPR, TREE_TYPE (rhs), v->value); + if (fold_convertible_p (TREE_TYPE (rhs), v)) + val = fold_build1 (NOP_EXPR, TREE_TYPE (rhs), v); else if (TYPE_SIZE (TREE_TYPE (rhs)) - == TYPE_SIZE (TREE_TYPE (v->value))) - val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (rhs), v->value); + == TYPE_SIZE (TREE_TYPE (v))) + val = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (rhs), v); else { if (dump_file) { fprintf (dump_file, " const "); - print_generic_expr (dump_file, v->value); + print_generic_expr (dump_file, v); fprintf (dump_file, " can't be converted to type of "); print_generic_expr (dump_file, rhs); fprintf (dump_file, "\n"); @@ -5742,7 +5712,7 @@ ipcp_modif_dom_walker::before_dom_children (basic_block bb) } } else - val = v->value; + val = v; if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -6019,7 +5989,6 @@ ipcp_transform_function (struct cgraph_node *node) { vec *descriptors = NULL; struct ipa_func_body_info fbi; - struct ipa_agg_replacement_value *aggval; int param_count; gcc_checking_assert (cfun); @@ -6031,18 +6000,17 @@ ipcp_transform_function (struct cgraph_node *node) ipcp_update_bits (node); ipcp_update_vr (node); - aggval = ipa_get_agg_replacements_for_node (node); - if (!aggval) + ipcp_transformation *ts = ipcp_get_transformation_summary (node); + if (!ts || vec_safe_is_empty (ts->m_agg_values)) return 0; param_count = count_formal_params (node->decl); if (param_count == 0) return 0; vec_safe_grow_cleared (descriptors, param_count, true); ipa_populate_param_decls (node, *descriptors); - std::pair rr - = adjust_agg_replacement_values (node, aggval, *descriptors); - bool cfg_changed = rr.second; - if (!rr.first) + + bool cfg_changed = adjust_agg_replacement_values (node, ts, *descriptors); + if (vec_safe_is_empty (ts->m_agg_values)) { vec_free (descriptors); if (dump_file) @@ -6053,7 +6021,11 @@ ipcp_transform_function (struct cgraph_node *node) return 0; } if (dump_file) - ipa_dump_agg_replacement_values (dump_file, aggval); + { + fprintf (dump_file, " Aggregate replacements:"); + ipa_argagg_value_list avs (ts); + avs.dump (dump_file); + } fbi.node = node; fbi.info = NULL; @@ -6064,7 +6036,7 @@ ipcp_transform_function (struct cgraph_node *node) bool modified_mem_access = false; calculate_dominance_info (CDI_DOMINATORS); - ipcp_modif_dom_walker walker (&fbi, descriptors, aggval, &modified_mem_access); + ipcp_modif_dom_walker walker (&fbi, descriptors, ts, &modified_mem_access); walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); free_dominance_info (CDI_DOMINATORS); cfg_changed |= walker.cleanup_eh (); @@ -6076,7 +6048,7 @@ ipcp_transform_function (struct cgraph_node *node) fbi.bb_infos.release (); ipcp_transformation *s = ipcp_transformation_sum->get (node); - s->agg_values = NULL; + s->m_agg_values = NULL; s->bits = NULL; s->m_vr = NULL; diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h index 8811e0ea987..b04c1d1e8f9 100644 --- a/gcc/ipa-prop.h +++ b/gcc/ipa-prop.h @@ -25,6 +25,11 @@ along with GCC; see the file COPYING3. If not see #define IPA_UNDESCRIBED_USE -1 +/* Index identifying an actualargument or a formal parameter may have only this + many bits. */ + +#define IPA_PROP_ARG_INDEX_LIMIT_BITS 16 + /* ipa-prop.cc stuff (ipa-cp, indirect inlining): */ /* A jump function for a callsite represents the values passed as actual @@ -184,6 +189,92 @@ struct GTY(()) ipa_agg_jump_function bool by_ref; }; +class ipcp_transformation; + +/* Element of a vector describing aggregate values for a number of arguments in + a particular context, be it a call or the aggregate constants that a node is + specialized for. */ + +struct GTY(()) ipa_argagg_value +{ + /* The constant value. In the contexts where the list of known values is + being pruned, NULL means a variable value. */ + tree value; + /* Unit offset within the aggregate. */ + unsigned unit_offset; + /* Index of the parameter, as it was in the original function (i.e. needs + remapping after parameter modification is carried out as part of clone + materialization). */ + unsigned index : IPA_PROP_ARG_INDEX_LIMIT_BITS; + /* Whether the value was passed by reference. */ + unsigned by_ref : 1; +}; + +/* A view into a sorted list of aggregate values in a particular context, be it + a call or the aggregate constants that a node is specialized for. The + actual data is stored in the vector this has been constructed from. */ + +class ipa_argagg_value_list +{ +public: + ipa_argagg_value_list () = delete; + ipa_argagg_value_list (const vec *values) + : m_elts (values) + {} + ipa_argagg_value_list (const vec *values) + : m_elts (*values) + {} + ipa_argagg_value_list (const ipcp_transformation *tinfo); + + /* Return the aggregate constant stored for INDEX at UNIT_OFFSET, if it is + passed by reference or not according to BY_REF, or NULL_TREE + otherwise. */ + + tree get_value (int index, unsigned unit_offset, bool by_ref) const; + + /* Return the aggregate constant stored for INDEX at UNIT_OFFSET, not + performing any check of whether value is passed by reference. Return + NULL_TREE if there is no such constant. */ + + tree get_value (int index, unsigned unit_offset) const; + + /* Return the item describing a constant stored for INDEX at UNIT_OFFSET or + NULL if there is no such constant. */ + + const ipa_argagg_value *get_elt (int index, unsigned unit_offset) const; + + /* Return the first item describing a constant stored for parameter with + INDEX, regardless of offset or reference, or NULL if there is no such + constant. */ + + const ipa_argagg_value *get_elt_for_index (int index) const; + + /* Return true if all elements present in OTHER are also present in this + class. */ + + bool superset_of_p (const ipa_argagg_value_list &other) const; + + /* Push into RES aggregate all stored aggregate values relating to parameter + with SRC_INDEX as those relating to of DST_INDEX while subtracting + UNIT_DELTA from the individual unit offsets. */ + + void push_adjusted_values (unsigned src_index, unsigned dest_index, + unsigned unit_delta, + vec *res) const; + + /* Dump aggregate constants to FILE. */ + + void dump (FILE *f); + + /* Dump aggregate constants to stderr. */ + + void debug (); + + /* Array slice pointing to the actual storage. */ + + array_slice m_elts; +}; + /* An element in an aggregate part describing a known value at a given offset. All unlisted positions are assumed to be unknown and all listed values must fulfill is_gimple_ip_invariant. */ @@ -882,28 +973,12 @@ ipa_is_param_used_by_polymorphic_call (class ipa_node_params *info, int i) return (*info->descriptors)[i].used_by_polymorphic_call; } -/* Information about replacements done in aggregates for a given node (each - node has its linked list). */ -struct GTY(()) ipa_agg_replacement_value -{ - /* Next item in the linked list. */ - struct ipa_agg_replacement_value *next; - /* Offset within the aggregate. */ - HOST_WIDE_INT offset; - /* The constant value. */ - tree value; - /* The parameter index. */ - int index; - /* Whether the value was passed by reference. */ - bool by_ref; -}; - /* Structure holding information for the transformation phase of IPA-CP. */ struct GTY(()) ipcp_transformation { - /* Linked list of known aggregate values. */ - ipa_agg_replacement_value *agg_values; + /* Known aggregate values. */ + vec *m_agg_values; /* Known bits information. */ vec *bits; /* Value range information. */ @@ -911,26 +986,25 @@ struct GTY(()) ipcp_transformation /* Default constructor. */ ipcp_transformation () - : agg_values (NULL), bits (NULL), m_vr (NULL) + : m_agg_values (NULL), bits (NULL), m_vr (NULL) { } /* Default destructor. */ ~ipcp_transformation () { - ipa_agg_replacement_value *agg = agg_values; - while (agg) - { - ipa_agg_replacement_value *next = agg->next; - ggc_free (agg); - agg = next; - } + vec_free (m_agg_values); vec_free (bits); vec_free (m_vr); } }; +inline +ipa_argagg_value_list::ipa_argagg_value_list (const ipcp_transformation *tinfo) + : m_elts (tinfo->m_agg_values) +{} + void ipa_set_node_agg_value_chain (struct cgraph_node *node, - struct ipa_agg_replacement_value *aggvals); + vec *aggs); void ipcp_transformation_initialize (void); void ipcp_free_transformation_sum (void); @@ -1107,15 +1181,6 @@ ipcp_get_transformation_summary (cgraph_node *node) return ipcp_transformation_sum->get (node); } -/* Return the aggregate replacements for NODE, if there are any. */ - -static inline struct ipa_agg_replacement_value * -ipa_get_agg_replacements_for_node (cgraph_node *node) -{ - ipcp_transformation *ts = ipcp_get_transformation_summary (node); - return ts ? ts->agg_values : NULL; -} - /* Function formal parameters related computations. */ void ipa_initialize_node_params (struct cgraph_node *node); bool ipa_propagate_indirect_call_infos (struct cgraph_edge *cs, @@ -1171,8 +1236,6 @@ struct ipcp_agg_lattice; extern object_allocator ipcp_agg_lattice_pool; -void ipa_dump_agg_replacement_values (FILE *f, - struct ipa_agg_replacement_value *av); void ipa_prop_write_jump_functions (void); void ipa_prop_read_jump_functions (void); void ipcp_write_transformation_summaries (void); diff --git a/gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c b/gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c index 3c496eeef39..48bf77222b2 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c +++ b/gcc/testsuite/gcc.dg/ipa/ipcp-agg-11.c @@ -73,5 +73,5 @@ entry () /* { dg-final { scan-ipa-dump "offset: 0, type: int, CONST: 101" "cp" } } */ /* { dg-final { scan-ipa-dump "offset: 32, type: int, PASS THROUGH: 0, op trunc_mod_expr 7" "cp" } } */ /* { dg-final { scan-ipa-dump "offset: 64, type: int, LOAD AGG: 1 \\\[offset: 0, by reference], op plus_expr 6" "cp" } } */ -/* { dg-final { scan-ipa-dump "Aggregate replacements: 0\\\[0]=1, 0\\\[32]=105, 0\\\[64]=-18" "cp" } } */ -/* { dg-final { scan-ipa-dump "Aggregate replacements: 0\\\[0]=101, 0\\\[32]=2, 0\\\[64]=9" "cp" } } */ +/* { dg-final { scan-ipa-dump "Aggregate replacements: 0\\\[0]=1\\(by_ref\\), 0\\\[4]=105\\(by_ref\\), 0\\\[8]=-18\\(by_ref\\)" "cp" } } */ +/* { dg-final { scan-ipa-dump "Aggregate replacements: 0\\\[0]=101, 0\\\[4]=2, 0\\\[8]=9" "cp" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c b/gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c index 2d9c82f7310..8234702dd6e 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c +++ b/gcc/testsuite/gcc.dg/ipa/ipcp-agg-8.c @@ -48,5 +48,5 @@ entry (int c) foo (4, i, &s); } } -/* { dg-final { scan-ipa-dump "Aggregate replacements: 1\\\[32]=64, 1\\\[64]=32" "cp" } } */ -/* { dg-final { scan-ipa-dump "Aggregate replacements: 1\\\[32]=0" "cp" } } */ +/* { dg-final { scan-ipa-dump "Aggregate replacements: 1\\\[4]=64\\(by_ref\\), 1\\\[8]=32\\(by_ref\\)" "cp" } } */ +/* { dg-final { scan-ipa-dump "Aggregate replacements: 1\\\[4]=0\\(by_ref\\)" "cp" } } */ From patchwork Tue Aug 30 17:06:06 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Martin Jambor X-Patchwork-Id: 1671972 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=suse.cz header.i=@suse.cz header.a=rsa-sha256 header.s=susede2_rsa header.b=mfZvWc5P; dkim=pass header.d=suse.cz header.i=@suse.cz header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=YHL5B52l; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4MHDH75cSYz1ynD for ; Wed, 31 Aug 2022 03:06:27 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 8520F39960F6 for ; Tue, 30 Aug 2022 17:06:24 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id 675603959C5D for ; Tue, 30 Aug 2022 17:06:08 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 675603959C5D Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.cz Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out2.suse.de (Postfix) with ESMTPS id 1E1E21FA05; Tue, 30 Aug 2022 17:06:07 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1661879167; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=rRYcxAMTJRCbSAFPT2Fgwx7VgsEy+/iboFe7mXI12nw=; b=mfZvWc5PYOFxn0iRvtGZ8t5kvoFjULkpMEoYj4XcmiqZ5VD7ddYSqgL+54hPO0aYfLxqtf +LGTI4WJkZlGPIEKJcs7hRvJckRHM7Cn706xUMkjbkGIFN0/N4GeE7K3QLg68IiyPSpPqJ tfOT8FjxOktOixyRPIswt3O3MzWseOk= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1661879167; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=rRYcxAMTJRCbSAFPT2Fgwx7VgsEy+/iboFe7mXI12nw=; b=YHL5B52l3UkfvTHbpwX1yAbVdd1FvOgxxJj2eQMcxXMSOHBqVruZSTqguuFC2h5wab+hOd F95DPMNODxwW7FBQ== Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 0B05A13B0C; Tue, 30 Aug 2022 17:06:07 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id ZDiuAn9DDmPbWQAAMHmgww (envelope-from ); Tue, 30 Aug 2022 17:06:07 +0000 From: Martin Jambor To: GCC Patches Subject: [PATCH 2/2] ipa-cp: Better representation of aggregate values in call contexts User-Agent: Notmuch/0.35 (https://notmuchmail.org) Emacs/28.1 (x86_64-suse-linux-gnu) Date: Tue, 30 Aug 2022 19:06:06 +0200 Message-ID: MIME-Version: 1.0 X-Spam-Status: No, score=-11.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Jan Hubicka , Jan Hubicka Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Hi this patch extends the previous one by using the same data structure to represent aggregate values in classes ipa_auto_call_arg_values and ipa_call_arg_values. This usually simplifies handling and makes allocations of memory much cheaper because only a single vectore is needed, as opposed to vectors with each element pointing at other vecs. The only functions which unfortunately are a bit more complec are estimate_local_effects in ipa-cp.cc and ipa_call_context::equal_to but I hope not too much - the latter could probably be shorteneed at the expense of readability. The patch removes types ipa_agg_value ipa_agg_value_set which is no longer used with it. This means that we could replace the "_argagg_" part of the types introduced by the previous patches with more reasonable "_agg_" - possibly as a follow-up patch. Bootstrapped, LTO-bootstrapped and tested on x86_64-linux (and a slightly older version also on aarch64-linux). LTO-profiledbootstrap is currently underway. Given the size of the patch I assume there will be concerns/questions but I'm looking for an approval to commit a version of this. Thanks, Martin gcc/ChangeLog: 2022-08-26 Martin Jambor * ipa-prop.h (ipa_agg_value): Remove type. (ipa_agg_value_set): Likewise. (ipa_copy_agg_values): Remove function. (ipa_release_agg_values): Likewise. (ipa_auto_call_arg_values) Add a forward declaration. (ipa_call_arg_values): Likewise. (class ipa_argagg_value_list): New constructors, added member function value_for_index_p. (class ipa_auto_call_arg_values): Removed the destructor and member function safe_aggval_at. Use ipa_argagg_values for m_known_aggs. (class ipa_call_arg_values): Removed member function safe_aggval_at. Use ipa_argagg_values for m_known_aggs. (ipa_get_indirect_edge_target): Removed declaration. (ipa_find_agg_cst_for_param): Likewise. (ipa_find_agg_cst_from_init): New declaration. (ipa_agg_value_from_jfunc): Likewise. (ipa_agg_value_set_from_jfunc): Removed declaration. (ipa_push_agg_values_from_jfunc): New declaration. * ipa-cp.cc (ipa_agg_value_from_node): Renamed to ipa_agg_value_from_jfunc, made public. (ipa_agg_value_set_from_jfunc): Removed. (ipa_push_agg_values_from_jfunc): New function. (ipa_get_indirect_edge_target_1): Removed known_aggs parameter, use avs for this purpose too. (ipa_get_indirect_edge_target): Removed the overload working on ipa_auto_call_arg_values, use ipa_argagg_value_list in the remaining one. (devirtualization_time_bonus): Use ipa_argagg_value_list and ipa_get_indirect_edge_target_1 instead of ipa_get_indirect_edge_target. (context_independent_aggregate_values): Removed function. (gather_context_independent_values): Work on ipa_argagg_value_list. (estimate_local_effects): Likewise, define some iterator variables only in the construct where necessary. (ipcp_discover_new_direct_edges): Adjust the call to ipa_get_indirect_edge_target_1. (push_agg_values_for_index_from_edge): Adjust the call ipa_agg_value_from_node which has been renamed to ipa_agg_value_from_jfunc. * ipa-fnsummary.cc (evaluate_conditions_for_known_args): Work on ipa_argagg_value_list. (evaluate_properties_for_edge): Replace manual filling in aggregate values with call to ipa_push_agg_values_from_jfunc. (estimate_calls_size_and_time): Work on ipa_argagg_value_list. (ipa_cached_call_context::duplicate_from): Likewise. (ipa_cached_call_context::release): Likewise. (ipa_call_context::equal_to): Likewise. * ipa-prop.cc (ipa_find_agg_cst_from_init): Make public. (ipa_find_agg_cst_for_param): Removed function. (ipa_find_agg_cst_from_jfunc_items): New function. (try_make_edge_direct_simple_call): Replace calls to ipa_agg_value_set_from_jfunc and ipa_find_agg_cst_for_param with ipa_find_agg_cst_from_init and ipa_find_agg_cst_from_jfunc_items. (try_make_edge_direct_virtual_call): Replace calls to ipa_agg_value_set_from_jfunc and ipa_find_agg_cst_for_param with simple query of constant jump function and a call to ipa_find_agg_cst_from_jfunc_items. (ipa_auto_call_arg_values::~ipa_auto_call_arg_values): Removed. --- gcc/ipa-cp.cc | 234 +++++++++++++++++-------------------------- gcc/ipa-fnsummary.cc | 105 ++++++++++--------- gcc/ipa-prop.cc | 110 ++++++-------------- gcc/ipa-prop.h | 172 +++++++------------------------ 4 files changed, 218 insertions(+), 403 deletions(-) diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc index 024f8c06b5d..098392d9b90 100644 --- a/gcc/ipa-cp.cc +++ b/gcc/ipa-cp.cc @@ -1973,10 +1973,9 @@ ipa_value_range_from_jfunc (ipa_node_params *info, cgraph_edge *cs, NODE and INFO describes the caller node or the one it is inlined to, and its related info. */ -static tree -ipa_agg_value_from_node (class ipa_node_params *info, - struct cgraph_node *node, - const ipa_agg_jf_item *item) +tree +ipa_agg_value_from_jfunc (ipa_node_params *info, cgraph_node *node, + const ipa_agg_jf_item *item) { tree value = NULL_TREE; int src_idx; @@ -2059,37 +2058,38 @@ ipa_agg_value_from_node (class ipa_node_params *info, item->type); } -/* Determine whether AGG_JFUNC evaluates to a set of known constant value for - an aggregate and if so, return it. Otherwise return an empty set. NODE - and INFO describes the caller node or the one it is inlined to, and its - related info. */ +/* Process all items in AGG_JFUNC relative to caller (or the node the original + caller is inlined to) NODE which described by INFO and push the results to + RES as describing values passed in parameter DST_INDEX. */ -struct ipa_agg_value_set -ipa_agg_value_set_from_jfunc (class ipa_node_params *info, cgraph_node *node, - struct ipa_agg_jump_function *agg_jfunc) +void +ipa_push_agg_values_from_jfunc (ipa_node_params *info, cgraph_node *node, + ipa_agg_jump_function *agg_jfunc, + unsigned dst_index, + vec *res) { - struct ipa_agg_value_set agg; - struct ipa_agg_jf_item *item; - int i; + unsigned prev_unit_offset = 0; + bool first = true; - agg.items = vNULL; - agg.by_ref = agg_jfunc->by_ref; - - FOR_EACH_VEC_SAFE_ELT (agg_jfunc->items, i, item) + for (const ipa_agg_jf_item &item : agg_jfunc->items) { - tree value = ipa_agg_value_from_node (info, node, item); + tree value = ipa_agg_value_from_jfunc (info, node, &item); + if (!value) + continue; - if (value) - { - struct ipa_agg_value value_item; + ipa_argagg_value iav; + iav.value = value; + iav.unit_offset = item.offset / BITS_PER_UNIT; + iav.index = dst_index; + iav.by_ref = agg_jfunc->by_ref; - value_item.offset = item->offset; - value_item.value = value; + gcc_assert (first + || iav.unit_offset > prev_unit_offset); + prev_unit_offset = iav.unit_offset; + first = false; - agg.items.safe_push (value_item); - } + res->safe_push (iav); } - return agg; } /* If checking is enabled, verify that no lattice is in the TOP state, i.e. not @@ -3238,8 +3238,7 @@ static tree ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, const vec &known_csts, const vec &known_contexts, - const vec &known_aggs, - const ipa_argagg_value_list *avs, + const ipa_argagg_value_list &avs, bool *speculative) { int param_index = ie->indirect_info->param_index; @@ -3259,31 +3258,16 @@ ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, if (ie->indirect_info->agg_contents) { t = NULL; - if (avs && ie->indirect_info->guaranteed_unmodified) - t = avs->get_value (param_index, - ie->indirect_info->offset / BITS_PER_UNIT, - ie->indirect_info->by_ref); - if (!t) - { - const ipa_agg_value_set *agg; - if (known_aggs.length () > (unsigned int) param_index) - agg = &known_aggs[param_index]; - else - agg = NULL; - bool from_global_constant; - t = ipa_find_agg_cst_for_param (agg, - (unsigned) param_index - < known_csts.length () - ? known_csts[param_index] - : NULL, - ie->indirect_info->offset, - ie->indirect_info->by_ref, - &from_global_constant); - if (t - && !from_global_constant - && !ie->indirect_info->guaranteed_unmodified) - t = NULL_TREE; - } + if ((unsigned) param_index < known_csts.length () + && known_csts[param_index]) + t = ipa_find_agg_cst_from_init (known_csts[param_index], + ie->indirect_info->offset, + ie->indirect_info->by_ref); + + if (!t && ie->indirect_info->guaranteed_unmodified) + t = avs.get_value (param_index, + ie->indirect_info->offset / BITS_PER_UNIT, + ie->indirect_info->by_ref); } else if ((unsigned) param_index < known_csts.length ()) t = known_csts[param_index]; @@ -3300,28 +3284,22 @@ ipa_get_indirect_edge_target_1 (struct cgraph_edge *ie, return NULL_TREE; gcc_assert (!ie->indirect_info->agg_contents); + gcc_assert (!ie->indirect_info->by_ref); anc_offset = ie->indirect_info->offset; t = NULL; - /* Try to work out value of virtual table pointer value in replacements. */ - if (!t && avs && !ie->indirect_info->by_ref) - t = avs->get_value (param_index, - ie->indirect_info->offset / BITS_PER_UNIT, - true); + if ((unsigned) param_index < known_csts.length () + && known_csts[param_index]) + t = ipa_find_agg_cst_from_init (known_csts[param_index], + ie->indirect_info->offset, true); - /* Try to work out value of virtual table pointer value in known - aggregate values. */ - if (!t && known_aggs.length () > (unsigned int) param_index - && !ie->indirect_info->by_ref) - { - const ipa_agg_value_set *agg = &known_aggs[param_index]; - t = ipa_find_agg_cst_for_param (agg, - (unsigned) param_index - < known_csts.length () - ? known_csts[param_index] : NULL, - ie->indirect_info->offset, true); - } + /* Try to work out value of virtual table pointer value in replacements. */ + /* or known aggregate values. */ + if (!t) + t = avs.get_value (param_index, + ie->indirect_info->offset / BITS_PER_UNIT, + true); /* If we found the virtual table pointer, lookup the target. */ if (t) @@ -3440,23 +3418,10 @@ ipa_get_indirect_edge_target (struct cgraph_edge *ie, ipa_call_arg_values *avals, bool *speculative) { + ipa_argagg_value_list avl (avals); return ipa_get_indirect_edge_target_1 (ie, avals->m_known_vals, avals->m_known_contexts, - avals->m_known_aggs, - NULL, speculative); -} - -/* The same functionality as above overloaded for ipa_auto_call_arg_values. */ - -tree -ipa_get_indirect_edge_target (struct cgraph_edge *ie, - ipa_auto_call_arg_values *avals, - bool *speculative) -{ - return ipa_get_indirect_edge_target_1 (ie, avals->m_known_vals, - avals->m_known_contexts, - avals->m_known_aggs, - NULL, speculative); + avl, speculative); } /* Calculate devirtualization time bonus for NODE, assuming we know information @@ -3477,7 +3442,10 @@ devirtualization_time_bonus (struct cgraph_node *node, tree target; bool speculative; - target = ipa_get_indirect_edge_target (ie, avals, &speculative); + ipa_argagg_value_list avl (avals); + target = ipa_get_indirect_edge_target_1 (ie, avals->m_known_vals, + avals->m_known_contexts, + avl, &speculative); if (!target) continue; @@ -3613,32 +3581,6 @@ good_cloning_opportunity_p (struct cgraph_node *node, sreal time_benefit, } } -/* Return all context independent values from aggregate lattices in PLATS in a - vector. Return NULL if there are none. */ - -static vec -context_independent_aggregate_values (class ipcp_param_lattices *plats) -{ - vec res = vNULL; - - if (plats->aggs_bottom - || plats->aggs_contain_variable - || plats->aggs_count == 0) - return vNULL; - - for (struct ipcp_agg_lattice *aglat = plats->aggs; - aglat; - aglat = aglat->next) - if (aglat->is_single_const ()) - { - struct ipa_agg_value item; - item.offset = aglat->offset; - item.value = aglat->values->value; - res.safe_push (item); - } - return res; -} - /* Grow vectors in AVALS and fill them with information about values of parameters that are known to be independent of the context. Only calculate m_known_aggs if CALCULATE_AGGS is true. INFO describes the function. If @@ -3658,8 +3600,6 @@ gather_context_independent_values (class ipa_node_params *info, avals->m_known_vals.safe_grow_cleared (count, true); avals->m_known_contexts.safe_grow_cleared (count, true); - if (calculate_aggs) - avals->m_known_aggs.safe_grow_cleared (count, true); if (removable_params_cost) *removable_params_cost = 0; @@ -3694,16 +3634,7 @@ gather_context_independent_values (class ipa_node_params *info, avals->m_known_contexts[i] = ctxlat->values->value; if (calculate_aggs) - { - vec agg_items; - struct ipa_agg_value_set *agg; - - agg_items = context_independent_aggregate_values (plats); - agg = &avals->m_known_aggs[i]; - agg->items = agg_items; - agg->by_ref = plats->aggs_by_ref; - ret |= !agg_items.is_empty (); - } + ret |= push_agg_values_from_plats (plats, i, 0, &avals->m_known_aggs); } return ret; @@ -3774,7 +3705,7 @@ static void estimate_local_effects (struct cgraph_node *node) { ipa_node_params *info = ipa_node_params_sum->get (node); - int i, count = ipa_get_param_count (info); + int count = ipa_get_param_count (info); bool always_const; int removable_params_cost; @@ -3840,7 +3771,7 @@ estimate_local_effects (struct cgraph_node *node) } - for (i = 0; i < count; i++) + for (int i = 0; i < count; i++) { class ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); ipcp_lattice *lat = &plats->itself; @@ -3874,7 +3805,7 @@ estimate_local_effects (struct cgraph_node *node) avals.m_known_vals[i] = NULL_TREE; } - for (i = 0; i < count; i++) + for (int i = 0; i < count; i++) { class ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); @@ -3909,30 +3840,49 @@ estimate_local_effects (struct cgraph_node *node) avals.m_known_contexts[i] = ipa_polymorphic_call_context (); } - for (i = 0; i < count; i++) + unsigned all_ctx_len = avals.m_known_aggs.length (); + auto_vec all_ctx; + all_ctx.reserve_exact (all_ctx_len); + all_ctx.splice (avals.m_known_aggs); + avals.m_known_aggs.safe_grow_cleared (all_ctx_len + 1); + + unsigned j = 0; + for (int index = 0; index < count; index++) { - class ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i); + class ipcp_param_lattices *plats = ipa_get_parm_lattices (info, index); if (plats->aggs_bottom || !plats->aggs) continue; - ipa_agg_value_set *agg = &avals.m_known_aggs[i]; for (ipcp_agg_lattice *aglat = plats->aggs; aglat; aglat = aglat->next) { ipcp_value *val; if (aglat->bottom || !aglat->values - /* If the following is true, the one value is in known_aggs. */ + /* If the following is true, the one value is already part of all + context estimations. */ || (!plats->aggs_contain_variable && aglat->is_single_const ())) continue; + unsigned unit_offset = aglat->offset / BITS_PER_UNIT; + while (j < all_ctx_len + && (all_ctx[j].index < index + || (all_ctx[j].index == index + && all_ctx[j].unit_offset < unit_offset))) + { + avals.m_known_aggs[j] = all_ctx[j]; + j++; + } + + for (unsigned k = j; k < all_ctx_len; k++) + avals.m_known_aggs[k+1] = all_ctx[k]; + for (val = aglat->values; val; val = val->next) { - struct ipa_agg_value item; - - item.offset = aglat->offset; - item.value = val->value; - agg->items.safe_push (item); + avals.m_known_aggs[j].value = val->value; + avals.m_known_aggs[j].unit_offset = unit_offset; + avals.m_known_aggs[j].index = index; + avals.m_known_aggs[j].by_ref = plats->aggs_by_ref; perform_estimation_of_a_value (node, &avals, removable_params_cost, 0, val); @@ -3942,7 +3892,7 @@ estimate_local_effects (struct cgraph_node *node) fprintf (dump_file, " - estimates for value "); print_ipcp_constant_value (dump_file, val->value); fprintf (dump_file, " for "); - ipa_dump_param (dump_file, info, i); + ipa_dump_param (dump_file, info, index); fprintf (dump_file, "[%soffset: " HOST_WIDE_INT_PRINT_DEC "]: time_benefit: %g, size: %i\n", plats->aggs_by_ref ? "ref " : "", @@ -3950,8 +3900,6 @@ estimate_local_effects (struct cgraph_node *node) val->local_time_benefit.to_double (), val->local_size_cost); } - - agg->items.pop (); } } } @@ -4348,7 +4296,7 @@ ipcp_discover_new_direct_edges (struct cgraph_node *node, next_ie = ie->next_callee; ipa_argagg_value_list avs (aggvals); target = ipa_get_indirect_edge_target_1 (ie, known_csts, known_contexts, - vNULL, &avs, &speculative); + avs, &speculative); if (target) { bool agg_contents = ie->indirect_info->agg_contents; @@ -5777,8 +5725,8 @@ push_agg_values_for_index_from_edge (struct cgraph_edge *cs, int index, agg_jf.value.pass_through.operand, agg_jf.type); else - value = ipa_agg_value_from_node (caller_info, cs->caller, - &agg_jf); + value = ipa_agg_value_from_jfunc (caller_info, cs->caller, + &agg_jf); if (value) { struct ipa_argagg_value iav; diff --git a/gcc/ipa-fnsummary.cc b/gcc/ipa-fnsummary.cc index e2a86680a21..fd3d7d6c5e8 100644 --- a/gcc/ipa-fnsummary.cc +++ b/gcc/ipa-fnsummary.cc @@ -386,15 +386,6 @@ evaluate_conditions_for_known_args (struct cgraph_node *node, int j; struct expr_eval_op *op; - /* We allow call stmt to have fewer arguments than the callee function - (especially for K&R style programs). So bound check here (we assume - m_known_aggs vector is either empty or has the same length as - m_known_vals). */ - gcc_checking_assert (!avals->m_known_aggs.length () - || !avals->m_known_vals.length () - || (avals->m_known_vals.length () - == avals->m_known_aggs.length ())); - if (c->agg_contents) { if (c->code == ipa_predicate::changed @@ -402,14 +393,14 @@ evaluate_conditions_for_known_args (struct cgraph_node *node, && (avals->safe_sval_at(c->operand_num) == error_mark_node)) continue; - if (ipa_agg_value_set *agg = avals->safe_aggval_at (c->operand_num)) + if (tree sval = avals->safe_sval_at (c->operand_num)) + val = ipa_find_agg_cst_from_init (sval, c->offset, c->by_ref); + if (!val) { - tree sval = avals->safe_sval_at (c->operand_num); - val = ipa_find_agg_cst_for_param (agg, sval, c->offset, - c->by_ref); + ipa_argagg_value_list avs (avals); + val = avs.get_value (c->operand_num, c->offset / BITS_PER_UNIT, + c->by_ref); } - else - val = NULL_TREE; } else { @@ -674,17 +665,9 @@ evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p, /* Determine known aggregate values. */ if (fre_will_run_p (caller)) - { - ipa_agg_value_set agg - = ipa_agg_value_set_from_jfunc (caller_parms_info, - caller, &jf->agg); - if (agg.items.length ()) - { - if (!avals->m_known_aggs.length ()) - avals->m_known_aggs.safe_grow_cleared (count, true); - avals->m_known_aggs[i] = agg; - } - } + ipa_push_agg_values_from_jfunc (caller_parms_info, + caller, &jf->agg, i, + &avals->m_known_aggs); } /* For calls used in polymorphic calls we further determine @@ -3446,8 +3429,7 @@ estimate_calls_size_and_time (struct cgraph_node *node, int *size, { if (ipa_is_param_used_by_indirect_call (params_summary, i) && (avals->safe_sval_at (i) - || (avals->m_known_aggs.length () > i - && avals->m_known_aggs[i].items.length ()))) + || (ipa_argagg_value_list (avals).value_for_index_p (i)))) use_table = false; else if (ipa_is_param_used_by_polymorphic_call (params_summary, i) && (avals->m_known_contexts.length () > i @@ -3583,14 +3565,12 @@ ipa_cached_call_context::duplicate_from (const ipa_call_context &ctx) m_avals.m_known_aggs = vNULL; if (ctx.m_avals.m_known_aggs.exists ()) { - unsigned int n = MIN (ctx.m_avals.m_known_aggs.length (), nargs); - - for (unsigned int i = 0; i < n; i++) + const ipa_argagg_value_list avl (&ctx.m_avals); + for (unsigned int i = 0; i < nargs; i++) if (ipa_is_param_used_by_indirect_call (params_summary, i) - && !ctx.m_avals.m_known_aggs[i].is_empty ()) + && avl.value_for_index_p (i)) { - m_avals.m_known_aggs - = ipa_copy_agg_values (ctx.m_avals.m_known_aggs); + m_avals.m_known_aggs = ctx.m_avals.m_known_aggs.copy (); break; } } @@ -3607,7 +3587,7 @@ ipa_cached_call_context::release () /* See if context is initialized at first place. */ if (!m_node) return; - ipa_release_agg_values (m_avals.m_known_aggs, true); + m_avals.m_known_aggs.release (); m_avals.m_known_vals.release (); m_avals.m_known_contexts.release (); m_inline_param_summary.release (); @@ -3708,28 +3688,59 @@ ipa_call_context::equal_to (const ipa_call_context &ctx) } if (m_avals.m_known_aggs.exists () || ctx.m_avals.m_known_aggs.exists ()) { - for (unsigned int i = 0; i < nargs; i++) + unsigned i = 0, j = 0; + while (i < m_avals.m_known_aggs.length () + || j < ctx.m_avals.m_known_aggs.length ()) { - if (!ipa_is_param_used_by_indirect_call (params_summary, i)) - continue; - if (i >= m_avals.m_known_aggs.length () - || m_avals.m_known_aggs[i].is_empty ()) + if (i >= m_avals.m_known_aggs.length ()) { - if (i < ctx.m_avals.m_known_aggs.length () - && !ctx.m_avals.m_known_aggs[i].is_empty ()) + int idx2 = ctx.m_avals.m_known_aggs[j].index; + if (ipa_is_param_used_by_indirect_call (params_summary, idx2)) return false; + j++; continue; } - if (i >= ctx.m_avals.m_known_aggs.length () - || ctx.m_avals.m_known_aggs[i].is_empty ()) + if (j >= ctx.m_avals.m_known_aggs.length ()) { - if (i < m_avals.m_known_aggs.length () - && !m_avals.m_known_aggs[i].is_empty ()) + int idx1 = m_avals.m_known_aggs[i].index; + if (ipa_is_param_used_by_indirect_call (params_summary, idx1)) return false; + i++; continue; } - if (!m_avals.m_known_aggs[i].equal_to (ctx.m_avals.m_known_aggs[i])) + + int idx1 = m_avals.m_known_aggs[i].index; + int idx2 = ctx.m_avals.m_known_aggs[j].index; + if (idx1 < idx2) + { + if (ipa_is_param_used_by_indirect_call (params_summary, idx1)) + return false; + i++; + continue; + } + if (idx1 > idx2) + { + if (ipa_is_param_used_by_indirect_call (params_summary, idx2)) + return false; + j++; + continue; + } + if (!ipa_is_param_used_by_indirect_call (params_summary, idx1)) + { + i++; + j++; + continue; + } + + if ((m_avals.m_known_aggs[i].unit_offset + != ctx.m_avals.m_known_aggs[j].unit_offset) + || (m_avals.m_known_aggs[i].by_ref + != ctx.m_avals.m_known_aggs[j].by_ref) + || !operand_equal_p (m_avals.m_known_aggs[i].value, + ctx.m_avals.m_known_aggs[j].value)) return false; + i++; + j++; } } return true; diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc index 6196d7e6bdb..ee1acf85a95 100644 --- a/gcc/ipa-prop.cc +++ b/gcc/ipa-prop.cc @@ -3608,7 +3608,7 @@ find_constructor_constant_at_offset (tree constructor, HOST_WIDE_INT req_offset) invariant from a static constructor and if so, return it. Otherwise return NULL. */ -static tree +tree ipa_find_agg_cst_from_init (tree scalar, HOST_WIDE_INT offset, bool by_ref) { if (by_ref) @@ -3628,47 +3628,24 @@ ipa_find_agg_cst_from_init (tree scalar, HOST_WIDE_INT offset, bool by_ref) return find_constructor_constant_at_offset (DECL_INITIAL (scalar), offset); } -/* Retrieve value from AGG, a set of known offset/value for an aggregate or - static initializer of SCALAR (which can be NULL) for the given OFFSET or - return NULL if there is none. BY_REF specifies whether the value has to be - passed by reference or by value. If FROM_GLOBAL_CONSTANT is non-NULL, then - the boolean it points to is set to true if the value comes from an - initializer of a constant. */ +/* Retrieve value from AGG_JFUNC for the given OFFSET or return NULL if there + is none. BY_REF specifies whether the value has to be passed by reference + or by value. */ -tree -ipa_find_agg_cst_for_param (const ipa_agg_value_set *agg, tree scalar, - HOST_WIDE_INT offset, bool by_ref, - bool *from_global_constant) +static tree +ipa_find_agg_cst_from_jfunc_items (struct ipa_agg_jump_function *agg_jfunc, + ipa_node_params *src_info, + cgraph_node *src_node, + HOST_WIDE_INT offset, bool by_ref) { - struct ipa_agg_value *item; - int i; + if (by_ref != agg_jfunc->by_ref) + return NULL_TREE; - if (scalar) - { - tree res = ipa_find_agg_cst_from_init (scalar, offset, by_ref); - if (res) - { - if (from_global_constant) - *from_global_constant = true; - return res; - } - } + for (const ipa_agg_jf_item &item : agg_jfunc->items) + if (item.offset == offset) + return ipa_agg_value_from_jfunc (src_info, src_node, &item); - if (!agg - || by_ref != agg->by_ref) - return NULL; - - FOR_EACH_VEC_ELT (agg->items, i, item) - if (item->offset == offset) - { - /* Currently we do not have clobber values, return NULL for them once - we do. */ - gcc_checking_assert (is_gimple_ip_invariant (item->value)); - if (from_global_constant) - *from_global_constant = false; - return item->value; - } - return NULL; + return NULL_TREE; } /* Remove a reference to SYMBOL from the list of references of a node given by @@ -3765,24 +3742,19 @@ try_make_edge_direct_simple_call (struct cgraph_edge *ie, class ipa_node_params *new_root_info) { struct cgraph_edge *cs; - tree target; + tree target = NULL_TREE; bool agg_contents = ie->indirect_info->agg_contents; tree scalar = ipa_value_from_jfunc (new_root_info, jfunc, target_type); if (agg_contents) { - bool from_global_constant; - ipa_agg_value_set agg = ipa_agg_value_set_from_jfunc (new_root_info, - new_root, - &jfunc->agg); - target = ipa_find_agg_cst_for_param (&agg, scalar, - ie->indirect_info->offset, - ie->indirect_info->by_ref, - &from_global_constant); - agg.release (); - if (target - && !from_global_constant - && !ie->indirect_info->guaranteed_unmodified) - return NULL; + if (scalar) + target = ipa_find_agg_cst_from_init (scalar, ie->indirect_info->offset, + ie->indirect_info->by_ref); + if (!target && ie->indirect_info->guaranteed_unmodified) + target = ipa_find_agg_cst_from_jfunc_items (&jfunc->agg, new_root_info, + new_root, + ie->indirect_info->offset, + ie->indirect_info->by_ref); } else target = scalar; @@ -3857,15 +3829,14 @@ try_make_edge_direct_virtual_call (struct cgraph_edge *ie, { tree vtable; unsigned HOST_WIDE_INT offset; - tree scalar = (jfunc->type == IPA_JF_CONST) ? ipa_get_jf_constant (jfunc) - : NULL; - ipa_agg_value_set agg = ipa_agg_value_set_from_jfunc (new_root_info, - new_root, - &jfunc->agg); - tree t = ipa_find_agg_cst_for_param (&agg, scalar, - ie->indirect_info->offset, - true); - agg.release (); + tree t = NULL_TREE; + if (jfunc->type == IPA_JF_CONST) + t = ipa_find_agg_cst_from_init (ipa_get_jf_constant (jfunc), + ie->indirect_info->offset, true); + if (!t) + t = ipa_find_agg_cst_from_jfunc_items (&jfunc->agg, new_root_info, + new_root, + ie->indirect_info->offset, true); if (t && vtable_pointer_value_to_vtable (t, &vtable, &offset)) { bool can_refer; @@ -6060,21 +6031,4 @@ ipcp_transform_function (struct cgraph_node *node) } -/* Return true if OTHER describes same agg value. */ -bool -ipa_agg_value::equal_to (const ipa_agg_value &other) -{ - return offset == other.offset - && operand_equal_p (value, other.value, 0); -} - -/* Destructor also removing individual aggregate values. */ - -ipa_auto_call_arg_values::~ipa_auto_call_arg_values () -{ - ipa_release_agg_values (m_known_aggs, false); -} - - - #include "gt-ipa-prop.h" diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h index b04c1d1e8f9..1ff3cd48a6a 100644 --- a/gcc/ipa-prop.h +++ b/gcc/ipa-prop.h @@ -190,6 +190,8 @@ struct GTY(()) ipa_agg_jump_function }; class ipcp_transformation; +class ipa_auto_call_arg_values; +class ipa_call_arg_values; /* Element of a vector describing aggregate values for a number of arguments in a particular context, be it a call or the aggregate constants that a node is @@ -224,6 +226,8 @@ public: ipa_argagg_value_list (const vec *values) : m_elts (*values) {} + ipa_argagg_value_list (const ipa_auto_call_arg_values *aavals); + ipa_argagg_value_list (const ipa_call_arg_values *gavals); ipa_argagg_value_list (const ipcp_transformation *tinfo); /* Return the aggregate constant stored for INDEX at UNIT_OFFSET, if it is @@ -243,12 +247,22 @@ public: const ipa_argagg_value *get_elt (int index, unsigned unit_offset) const; + /* Return the first item describing a constant stored for parameter with INDEX, regardless of offset or reference, or NULL if there is no such constant. */ const ipa_argagg_value *get_elt_for_index (int index) const; + /* Return true if there is an aggregate constant referring to a value passed + in or by parameter with INDEX (at any offset, whether by reference or + not). */ + + bool value_for_index_p (int index) const + { + return !!get_elt_for_index (index); + } + /* Return true if all elements present in OTHER are also present in this class. */ @@ -275,105 +289,6 @@ public: array_slice m_elts; }; -/* An element in an aggregate part describing a known value at a given offset. - All unlisted positions are assumed to be unknown and all listed values must - fulfill is_gimple_ip_invariant. */ - -struct ipa_agg_value -{ - /* The offset at which the known value is located within the aggregate. */ - HOST_WIDE_INT offset; - - /* The known constant. */ - tree value; - - /* Return true if OTHER describes same agg value. */ - bool equal_to (const ipa_agg_value &other); -}; - -/* Structure describing a set of known offset/value for aggregate. */ - -struct ipa_agg_value_set -{ - /* Description of the individual item. */ - vec items; - /* True if the data was passed by reference (as opposed to by value). */ - bool by_ref; - - /* Return true if OTHER describes same agg values. */ - bool equal_to (const ipa_agg_value_set &other) - { - if (by_ref != other.by_ref) - return false; - if (items.length () != other.items.length ()) - return false; - for (unsigned int i = 0; i < items.length (); i++) - if (!items[i].equal_to (other.items[i])) - return false; - return true; - } - - /* Return true if there is any value for aggregate. */ - bool is_empty () const - { - return items.is_empty (); - } - - ipa_agg_value_set copy () const - { - ipa_agg_value_set new_copy; - - new_copy.items = items.copy (); - new_copy.by_ref = by_ref; - - return new_copy; - } - - void release () - { - items.release (); - } -}; - -/* Return copy of a vec. */ - -static inline vec -ipa_copy_agg_values (const vec &aggs) -{ - vec aggs_copy = vNULL; - - if (!aggs.is_empty ()) - { - ipa_agg_value_set *agg; - int i; - - aggs_copy.reserve_exact (aggs.length ()); - - FOR_EACH_VEC_ELT (aggs, i, agg) - aggs_copy.quick_push (agg->copy ()); - } - - return aggs_copy; -} - -/* For vec, DO NOT call release(), use below function - instead. Because ipa_agg_value_set contains a field of vector type, we - should release this child vector in each element before reclaiming the - whole vector. */ - -static inline void -ipa_release_agg_values (vec &aggs, - bool release_vector = true) -{ - ipa_agg_value_set *agg; - int i; - - FOR_EACH_VEC_ELT (aggs, i, agg) - agg->release (); - if (release_vector) - aggs.release (); -} - /* Information about zero/non-zero bits. */ class GTY(()) ipa_bits { @@ -551,28 +466,15 @@ ipa_get_jf_ancestor_keep_null (struct ipa_jump_func *jfunc) class ipa_auto_call_arg_values { public: - ~ipa_auto_call_arg_values (); - /* If m_known_vals (vector of known "scalar" values) is sufficiantly long, return its element at INDEX, otherwise return NULL. */ tree safe_sval_at (int index) { - /* TODO: Assert non-negative index here and test. */ if ((unsigned) index < m_known_vals.length ()) return m_known_vals[index]; return NULL; } - /* If m_known_aggs is sufficiantly long, return the pointer rto its element - at INDEX, otherwise return NULL. */ - ipa_agg_value_set *safe_aggval_at (int index) - { - /* TODO: Assert non-negative index here and test. */ - if ((unsigned) index < m_known_aggs.length ()) - return &m_known_aggs[index]; - return NULL; - } - /* Vector describing known values of parameters. */ auto_vec m_known_vals; @@ -580,15 +482,22 @@ public: auto_vec m_known_contexts; /* Vector describing known aggregate values. */ - auto_vec m_known_aggs; + auto_vec m_known_aggs; /* Vector describing known value ranges of arguments. */ auto_vec m_known_value_ranges; }; +inline +ipa_argagg_value_list +::ipa_argagg_value_list (const ipa_auto_call_arg_values *aavals) + : m_elts (aavals->m_known_aggs) +{} + /* Class bundling the various potentially known properties about actual arguments of a particular call. This variant does not deallocate the - bundled data in any way. */ + bundled data in any way as the vectors can either be pointing to vectors in + ipa_auto_call_arg_values or be allocated independently. */ class ipa_call_arg_values { @@ -613,22 +522,11 @@ public: return its element at INDEX, otherwise return NULL. */ tree safe_sval_at (int index) { - /* TODO: Assert non-negative index here and test. */ if ((unsigned) index < m_known_vals.length ()) return m_known_vals[index]; return NULL; } - /* If m_known_aggs is sufficiantly long, return the pointer rto its element - at INDEX, otherwise return NULL. */ - ipa_agg_value_set *safe_aggval_at (int index) - { - /* TODO: Assert non-negative index here and test. */ - if ((unsigned) index < m_known_aggs.length ()) - return &m_known_aggs[index]; - return NULL; - } - /* Vector describing known values of parameters. */ vec m_known_vals = vNULL; @@ -636,12 +534,17 @@ public: vec m_known_contexts = vNULL; /* Vector describing known aggregate values. */ - vec m_known_aggs = vNULL; + vec m_known_aggs = vNULL; /* Vector describing known value ranges of arguments. */ vec m_known_value_ranges = vNULL; }; +inline +ipa_argagg_value_list +::ipa_argagg_value_list (const ipa_call_arg_values *gavals) + : m_elts (gavals->m_known_aggs) +{} /* Summary describing a single formal parameter. */ @@ -1190,9 +1093,6 @@ bool ipa_propagate_indirect_call_infos (struct cgraph_edge *cs, tree ipa_get_indirect_edge_target (struct cgraph_edge *ie, ipa_call_arg_values *avals, bool *speculative); -tree ipa_get_indirect_edge_target (struct cgraph_edge *ie, - ipa_auto_call_arg_values *avals, - bool *speculative); struct cgraph_edge *ipa_make_edge_direct_to_target (struct cgraph_edge *, tree, bool speculative = false); tree ipa_impossible_devirt_target (struct cgraph_edge *, tree); @@ -1204,9 +1104,8 @@ ipa_bits *ipa_get_ipa_bits_for_value (const widest_int &value, void ipa_analyze_node (struct cgraph_node *); /* Aggregate jump function related functions. */ -tree ipa_find_agg_cst_for_param (const ipa_agg_value_set *agg, tree scalar, - HOST_WIDE_INT offset, bool by_ref, - bool *from_global_constant = NULL); +tree ipa_find_agg_cst_from_init (tree scalar, HOST_WIDE_INT offset, + bool by_ref); bool ipa_load_from_parm_agg (struct ipa_func_body_info *fbi, vec *descriptors, gimple *stmt, tree op, int *index_p, @@ -1243,6 +1142,8 @@ void ipcp_read_transformation_summaries (void); int ipa_get_param_decl_index (class ipa_node_params *, tree); tree ipa_value_from_jfunc (class ipa_node_params *info, struct ipa_jump_func *jfunc, tree type); +tree ipa_agg_value_from_jfunc (ipa_node_params *info, cgraph_node *node, + const ipa_agg_jf_item *item); unsigned int ipcp_transform_function (struct cgraph_node *node); ipa_polymorphic_call_context ipa_context_from_jfunc (ipa_node_params *, cgraph_edge *, @@ -1250,9 +1151,10 @@ ipa_polymorphic_call_context ipa_context_from_jfunc (ipa_node_params *, ipa_jump_func *); value_range ipa_value_range_from_jfunc (ipa_node_params *, cgraph_edge *, ipa_jump_func *, tree); -ipa_agg_value_set ipa_agg_value_set_from_jfunc (ipa_node_params *, - cgraph_node *, - ipa_agg_jump_function *); +void ipa_push_agg_values_from_jfunc (ipa_node_params *info, cgraph_node *node, + ipa_agg_jump_function *agg_jfunc, + unsigned dst_index, + vec *res); void ipa_dump_param (FILE *, class ipa_node_params *info, int i); void ipa_release_body_info (struct ipa_func_body_info *); tree ipa_get_callee_param_type (struct cgraph_edge *e, int i);