From patchwork Thu Jan 5 16:46:56 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Martin Jambor X-Patchwork-Id: 1722011 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=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (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 4Nnsp307xMz23db for ; Fri, 6 Jan 2023 03:47:21 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E4D033858416 for ; Thu, 5 Jan 2023 16:47:18 +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 67A8F3858D28 for ; Thu, 5 Jan 2023 16:47:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 67A8F3858D28 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 D67C320986; Thu, 5 Jan 2023 16:46:56 +0000 (UTC) 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 C9CBD138DF; Thu, 5 Jan 2023 16:46:56 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id EQo/MQD/tmOLUgAAMHmgww (envelope-from ); Thu, 05 Jan 2023 16:46:56 +0000 From: Martin Jambor To: GCC Patches Cc: Jan Hubicka , Jan Hubicka Subject: [PATCH] ipa: Sort ipa_param_body_adjustments::m_replacements (PR 108110) User-Agent: Notmuch/0.37 (https://notmuchmail.org) Emacs/28.2 (x86_64-suse-linux-gnu) Date: Thu, 05 Jan 2023 17:46:56 +0100 Message-ID: MIME-Version: 1.0 Authentication-Results: smtp-out2.suse.de; none X-Spam-Level: X-Spam-Score: -0.10 X-Spamd-Result: default: False [-0.10 / 50.00]; ARC_NA(0.00)[]; RCVD_VIA_SMTP_AUTH(0.00)[]; FROM_HAS_DN(0.00)[]; RCPT_COUNT_THREE(0.00)[3]; TO_MATCH_ENVRCPT_ALL(0.00)[]; MIME_GOOD(-0.10)[text/plain]; TO_DN_ALL(0.00)[]; FROM_EQ_ENVFROM(0.00)[]; MIME_TRACE(0.00)[0:+]; RCVD_COUNT_TWO(0.00)[2]; RCVD_TLS_ALL(0.00)[]; MID_RHS_MATCH_FROM(0.00)[] X-Spam-Status: No, score=-3039.3 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_STATUS, KAM_SHORT, SPF_HELO_NONE, SPF_PASS, TXREP 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: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Hi, the problem in PR 108110 is that elements describing the same base parameter in ipa_param_body_adjustments::m_replacements are not adjacent to each other, which is something that ipa_param_body_adjustments::modify_call_stmt when it gathers all replacements for a parameter. One option would be to simply always keep looking until the end of the vector (see bugzilla comment 15 for a one-line fix) but the correct thing to do is to keep the elements of the vector sorted and thus make such elements adjacent again. This patch does that and then also modifies the look-ups to take advantage of it. Since the one user of ipa_param_body_adjustments that is not tree-inline.cc, which is OpenMP declare SIMD cloning code, also registers its own replacements and in theory pointers to elements of the m_replacements vector can leak through public method get_expr_replacement, I decided that in those cases it is the responsibility of the user of the class to call the sorting method between the replacement registrations and the first lookup. That is why the patch also adds a line to omp-simd-clone.cc. Bootstrapped, tested and LTO-bootstrapped on x86_64-linux. OK for trunk? Thanks, Martin gcc/ChangeLog: 2023-01-04 Martin Jambor * ipa-param-manipulation.h (ipa_param_body_adjustments): New members sort_replacements, lookup_first_base_replacement and m_sorted_replacements_p. * ipa-param-manipulation.cc: Define INCLUDE_ALGORITHM. (ipa_param_body_adjustments::register_replacement): Set m_sorted_replacements_p to false. (compare_param_body_replacement): New function. (ipa_param_body_adjustments::sort_replacements): Likewise. (ipa_param_body_adjustments::common_initialization): Call sort_replacements. (ipa_param_body_adjustments::ipa_param_body_adjustments): Initialize m_sorted_replacements_p. (ipa_param_body_adjustments::lookup_replacement_1): Rework to use std::lower_bound. (ipa_param_body_adjustments::lookup_first_base_replacement): New function. (ipa_param_body_adjustments::modify_call_stmt): Use lookup_first_base_replacement. * omp-simd-clone.cc (ipa_simd_modify_function_body): Call adjustments->sort_replacements. gcc/testsuite/ChangeLog: 2023-01-04 Martin Jambor * g++.dg/ipa/pr108110.C: New test. --- gcc/ipa-param-manipulation.cc | 116 +++++++++++++++++++++------- gcc/ipa-param-manipulation.h | 9 +++ gcc/omp-simd-clone.cc | 1 + gcc/testsuite/g++.dg/ipa/pr108110.C | 32 ++++++++ 4 files changed, 132 insertions(+), 26 deletions(-) create mode 100644 gcc/testsuite/g++.dg/ipa/pr108110.C diff --git a/gcc/ipa-param-manipulation.cc b/gcc/ipa-param-manipulation.cc index a0e4098a3f1..8d78ef57c12 100644 --- a/gcc/ipa-param-manipulation.cc +++ b/gcc/ipa-param-manipulation.cc @@ -18,6 +18,7 @@ You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see . */ +#define INCLUDE_ALGORITHM #include "config.h" #include "system.h" #include "coretypes.h" @@ -1000,6 +1001,7 @@ ipa_param_body_adjustments::register_replacement (tree base, psr.dummy = NULL_TREE; psr.unit_offset = unit_offset; m_replacements.safe_push (psr); + m_sorted_replacements_p = false; } /* Register that REPLACEMENT should replace parameter described in APM. */ @@ -1015,6 +1017,36 @@ ipa_param_body_adjustments::register_replacement (ipa_adjusted_param *apm, replacement); } +/* Comparator to qsort ipa_param_body_adjustments::m_replacements. */ + +static int +compare_param_body_replacement (const void *va, const void *vb) +{ + const ipa_param_body_replacement *a = (const ipa_param_body_replacement *) va; + const ipa_param_body_replacement *b = (const ipa_param_body_replacement *) vb; + + if (DECL_UID (a->base) < DECL_UID (b->base)) + return -1; + if (DECL_UID (a->base) > DECL_UID (b->base)) + return 1; + if (a->unit_offset < b->unit_offset) + return -1; + if (a->unit_offset > b->unit_offset) + return 1; + return 0; +} + +/* Sort m_replacements and set m_sorted_replacements_p to true. */ + +void +ipa_param_body_adjustments::sort_replacements () +{ + if (m_sorted_replacements_p) + return; + m_replacements.qsort (compare_param_body_replacement); + m_sorted_replacements_p = true; +} + /* Copy or not, as appropriate given m_id and decl context, a pre-existing PARM_DECL T so that it can be included in the parameters of the modified function. */ @@ -1426,6 +1458,7 @@ ipa_param_body_adjustments::common_initialization (tree old_fndecl, } } } + sort_replacements (); if (tree_map) { @@ -1503,7 +1536,7 @@ ipa_param_body_adjustments m_dead_stmt_debug_equiv (), m_fndecl (fndecl), m_id (NULL), m_oparms (), m_new_decls (), m_new_types (), m_replacements (), m_split_agg_csts_inits (), m_removed_decls (), m_removed_map (), - m_method2func (false) + m_method2func (false), m_sorted_replacements_p (true) { common_initialization (fndecl, NULL, NULL); } @@ -1521,7 +1554,7 @@ ipa_param_body_adjustments m_dead_ssa_debug_equiv (), m_dead_stmt_debug_equiv (), m_fndecl (fndecl), m_id (NULL), m_oparms (), m_new_decls (), m_new_types (), m_replacements (), m_split_agg_csts_inits (), m_removed_decls (), m_removed_map (), - m_method2func (false) + m_method2func (false), m_sorted_replacements_p (true) { common_initialization (fndecl, NULL, NULL); } @@ -1545,7 +1578,7 @@ ipa_param_body_adjustments m_dead_ssa_debug_equiv (), m_dead_stmt_debug_equiv (), m_fndecl (fndecl), m_id (id), m_oparms (), m_new_decls (), m_new_types (), m_replacements (), m_split_agg_csts_inits (), m_removed_decls (), m_removed_map (), - m_method2func (false) + m_method2func (false), m_sorted_replacements_p (true) { common_initialization (old_fndecl, vars, tree_map); } @@ -1616,16 +1649,54 @@ ipa_param_body_replacement * ipa_param_body_adjustments::lookup_replacement_1 (tree base, unsigned unit_offset) { - unsigned int len = m_replacements.length (); - for (unsigned i = 0; i < len; i++) - { - ipa_param_body_replacement *pbr = &m_replacements[i]; + gcc_assert (m_sorted_replacements_p); + ipa_param_body_replacement key; + key.base = base; + key.unit_offset = unit_offset; + ipa_param_body_replacement *res + = std::lower_bound (m_replacements.begin (), m_replacements.end (), key, + [] (const ipa_param_body_replacement &elt, + const ipa_param_body_replacement &val) + { + if (DECL_UID (elt.base) < DECL_UID (val.base)) + return true; + if (DECL_UID (elt.base) > DECL_UID (val.base)) + return false; + if (elt.unit_offset < val.unit_offset) + return true; + return false; + }); - if (pbr->base == base - && (pbr->unit_offset == unit_offset)) - return pbr; - } - return NULL; + if (res == m_replacements.end () + || res->base != base + || res->unit_offset != unit_offset) + return NULL; + return res; +} + +/* Find the first replacement for BASE among m_replacements and return pointer + to it, or NULL if there is none. */ + +ipa_param_body_replacement * +ipa_param_body_adjustments::lookup_first_base_replacement (tree base) +{ + gcc_assert (m_sorted_replacements_p); + ipa_param_body_replacement key; + key.base = base; + ipa_param_body_replacement *res + = std::lower_bound (m_replacements.begin (), m_replacements.end (), key, + [] (const ipa_param_body_replacement &elt, + const ipa_param_body_replacement &val) + { + if (DECL_UID (elt.base) < DECL_UID (val.base)) + return true; + return false; + }); + + if (res == m_replacements.end () + || res->base != base) + return NULL; + return res; } /* Given BASE and UNIT_OFFSET, find the corresponding replacement expression @@ -1997,6 +2068,7 @@ ipa_param_body_adjustments::modify_call_stmt (gcall **stmt_p, gcall *stmt = *stmt_p; unsigned nargs = gimple_call_num_args (stmt); bool recreate = false; + gcc_assert (m_sorted_replacements_p); for (unsigned i = 0; i < gimple_call_num_args (stmt); i++) { @@ -2029,19 +2101,11 @@ ipa_param_body_adjustments::modify_call_stmt (gcall **stmt_p, if (TREE_CODE (base) != PARM_DECL) continue; - bool base_among_replacements = false; - unsigned j, repl_list_len = m_replacements.length (); - for (j = 0; j < repl_list_len; j++) - { - ipa_param_body_replacement *pbr = &m_replacements[j]; - if (pbr->base == base) - { - base_among_replacements = true; - break; - } - } - if (!base_among_replacements) + ipa_param_body_replacement *first_rep + = lookup_first_base_replacement (base); + if (!first_rep) continue; + unsigned first_rep_index = first_rep - m_replacements.begin (); /* We still have to distinguish between an end-use that we have to transform now and a pass-through, which happens in the following @@ -2060,7 +2124,7 @@ ipa_param_body_adjustments::modify_call_stmt (gcall **stmt_p, recreate = true; gcc_assert (POINTER_TYPE_P (TREE_TYPE (t))); pass_through_args.safe_push (i); - pass_through_pbr_indices.safe_push (j); + pass_through_pbr_indices.safe_push (first_rep_index); pass_through_offsets.safe_push (agg_arg_offset); } else if (!by_ref && AGGREGATE_TYPE_P (TREE_TYPE (t))) @@ -2078,7 +2142,7 @@ ipa_param_body_adjustments::modify_call_stmt (gcall **stmt_p, { recreate = true; pass_through_args.safe_push (i); - pass_through_pbr_indices.safe_push (j); + pass_through_pbr_indices.safe_push (first_rep_index); pass_through_offsets.safe_push (agg_arg_offset); } } diff --git a/gcc/ipa-param-manipulation.h b/gcc/ipa-param-manipulation.h index 0281ac4d901..9cc957ae7bb 100644 --- a/gcc/ipa-param-manipulation.h +++ b/gcc/ipa-param-manipulation.h @@ -318,6 +318,10 @@ public: void register_replacement (tree base, unsigned unit_offset, tree replacement); /* Register a replacement decl for the transformation done in APM. */ void register_replacement (ipa_adjusted_param *apm, tree replacement); + /* Sort m_replacements and set m_sorted_replacements_p to true. Users that + call register_replacement themselves must call the method before any + lookup and thus also any statement or expression modification. */ + void sort_replacements (); /* Lookup a replacement for a given offset within a given parameter. */ tree lookup_replacement (tree base, unsigned unit_offset); /* Lookup a replacement for an expression, if there is one. */ @@ -367,6 +371,7 @@ private: unsigned get_base_index (ipa_adjusted_param *apm); ipa_param_body_replacement *lookup_replacement_1 (tree base, unsigned unit_offset); + ipa_param_body_replacement *lookup_first_base_replacement (tree base); tree replace_removed_params_ssa_names (tree old_name, gimple *stmt); bool modify_expression (tree *expr_p, bool convert); bool modify_assignment (gimple *stmt, gimple_seq *extra_stmts); @@ -425,6 +430,10 @@ private: its this pointer and must be converted to a normal function. */ bool m_method2func; + + /* True if m_replacements have ben sorted since the last insertion. */ + + bool m_sorted_replacements_p; }; void push_function_arg_decls (vec *args, tree fndecl); diff --git a/gcc/omp-simd-clone.cc b/gcc/omp-simd-clone.cc index 92b629b1021..0949b8ba288 100644 --- a/gcc/omp-simd-clone.cc +++ b/gcc/omp-simd-clone.cc @@ -1229,6 +1229,7 @@ ipa_simd_modify_function_body (struct cgraph_node *node, j += vector_unroll_factor (node->simdclone->simdlen, simd_clone_subparts (vectype)) - 1; } + adjustments->sort_replacements (); tree name; FOR_EACH_SSA_NAME (i, name, cfun) diff --git a/gcc/testsuite/g++.dg/ipa/pr108110.C b/gcc/testsuite/g++.dg/ipa/pr108110.C new file mode 100644 index 00000000000..e9f3b5efc04 --- /dev/null +++ b/gcc/testsuite/g++.dg/ipa/pr108110.C @@ -0,0 +1,32 @@ +/* { dg-do compile } */ +/* { dg-options "-O3" } */ + +void __throw_out_of_range_fmt(...); +char *_M_p; +struct Trans_NS___cxx11_basic_string { + long _M_string_length; + long _M_check___pos; + Trans_NS___cxx11_basic_string() { + long __length = 0; + _M_string_length = __length; + } + long size() { return _M_string_length; } + long foo___pos; + char foo() { return _M_p[foo___pos]; } + int compare() { __throw_out_of_range_fmt(_M_check___pos, _M_string_length); __builtin_trap(); } +}; +bool str_starts_with(Trans_NS___cxx11_basic_string &str, + Trans_NS___cxx11_basic_string prefix) { + if (str.size() < prefix.size()) + str.compare(); + for (; prefix.size();) { + char __trans_tmp_2 = prefix.foo(); + if (__trans_tmp_2) + return false; + } + __builtin_trap(); +} +void testStartsWith() { + Trans_NS___cxx11_basic_string s1, s2; + str_starts_with(s1, s2); +}