From patchwork Sat Jan 25 13:50:10 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Feng Xue OS X-Patchwork-Id: 1229234 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-518253-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=os.amperecomputing.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha1 header.s=default header.b=RjEHTDN5; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=os.amperecomputing.com header.i=@os.amperecomputing.com header.a=rsa-sha256 header.s=selector2 header.b=Ke1FrvF7; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 484cpX5MFRz9sNx for ; Sun, 26 Jan 2020 00:50:26 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:references:in-reply-to:content-type :mime-version; q=dns; s=default; b=OdXeAbGgisa1BW5uhX3jiBUFrhX27 ZeOzWF0MNbzKqh1vpmbK5vLM2zHXgxgg/KySpvr7DbMWnrIoCgUPae7pDOLpXQjB XbJjEb74MBxu9MXNwv6wNjgREckm6Qpqwglw6W0K6A3N1yK5sxBWj+8ENrnNxoM0 1uAf6fiF2u2E8Y= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:references:in-reply-to:content-type :mime-version; s=default; bh=Q0xrjS/QUwMtYGUXt00zT+q8Kvs=; b=RjE HTDN5GluCY4c3XokoAzxS2GqRG3lg4Z/ufBrM9KL6BIfHXUaqtCi6VdMhnlwFHm7 4TuzcWixx0TXBvkJeOln+coyp7InA5w3bbH9zLbRgm0VCjWnUKpdQ4nG/WWc1pNB vBQFGnWyxwH5XtKFVf9f0eA98H9nIxjOcdvqRICk= Received: (qmail 27636 invoked by alias); 25 Jan 2020 13:50:17 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 27627 invoked by uid 89); 25 Jan 2020 13:50:17 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.1 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS, SPF_PASS autolearn=ham version=3.3.1 spammy=H*f:sk:BYAPR01, H*i:sk:BYAPR01 X-HELO: NAM04-BN3-obe.outbound.protection.outlook.com Received: from mail-eopbgr680126.outbound.protection.outlook.com (HELO NAM04-BN3-obe.outbound.protection.outlook.com) (40.107.68.126) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sat, 25 Jan 2020 13:50:14 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=oXrsitQjTUZZ+gKeCEn+WQWd/FpfLdjsTq/y7VIGjmwHqtxEPdUIXkb1U0IA6k8DpuhodtRY3VT8ed0jIQ1cQoj6S8AxhgjeQfoPPu89ihMUzAq88ZsSLV1FiX77wsP7I+V0yQmCfIA0PEjxpH/B1H5MpruaWZKOHBWcjxFbiUfeNc0pADGLXvp7oQZVCjJwYeRCg9XOaM4y4XyAJfNrNbHVR+E4MP9SX4HK8EsYOnkbsD5T2TZkuA80S9w5MfrplAV5pTsyZXMkPPqvHiVjrfO5mVH+ViQdKeu5al7/4AUVo2wRT98i7W08LtOHUPgC42onZx//7LT3LmdLDFPtFA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=wXhYpwXwpL3Vg9skAFCYHLm9RSKkYhoXPAxhru75KfM=; b=cU7pVoSDi4y8Mj4iY3h5aUkSrdyba2QN2RZ5pfnCRRTB4GqeWtSA83qkpwWa/j+L32OhEwUz9i8pZJwfGwUdHAsQNwS3pCSmRJntDMNIlp/MksFpK9SggL/Z+RzSfX1gXkha79Z3Rftu5IpMBsdUCe8MIby37IT5wkVLChWU4pPx3saFgU8Q6nOSSpwdU7fRuYBdFgyr41U9vrK/qQkXocLqgd5UmEuuBHQYKpZKTCzmPVXoc1DTdK1gFSPbcF86msJuGBO5H9g7AAeZ5VW3/HBvSJL07fzz5XaDXDrO7LptSe5SNjuY9ecsRZmZVRQeMcgGFr+yEOo8YU1OBheTVQ== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=os.amperecomputing.com; dmarc=pass action=none header.from=os.amperecomputing.com; dkim=pass header.d=os.amperecomputing.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=os.amperecomputing.com; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=wXhYpwXwpL3Vg9skAFCYHLm9RSKkYhoXPAxhru75KfM=; b=Ke1FrvF71cVM5/5WF/PUHZKdKETPJLfUKI1j0sRbhmaJ10QJ5FKeNGggJtMQsn87uzZLazoBVkmchJGWQKSOb8mia+Jwot9DTfL8zDM9io8u3dvfN4xAHVqLhMSGfm3a2m3oPfAxWbzQ2iofipZb4GlXUqmU60/O7cLiDrBzkNA= Received: from BYAPR01MB4869.prod.exchangelabs.com (20.177.226.139) by BYAPR01MB3912.prod.exchangelabs.com (52.135.199.29) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2665.23; Sat, 25 Jan 2020 13:50:11 +0000 Received: from BYAPR01MB4869.prod.exchangelabs.com ([fe80::b092:f9fd:5516:bba]) by BYAPR01MB4869.prod.exchangelabs.com ([fe80::b092:f9fd:5516:bba%7]) with mapi id 15.20.2665.017; Sat, 25 Jan 2020 13:50:10 +0000 From: Feng Xue OS To: "mjambor@suse.cz" , Jan Hubicka , "gcc-patches@gcc.gnu.org" Subject: [PATCH V2] Generalized value pass-through for self-recursive function (ipa/pr93203) Date: Sat, 25 Jan 2020 13:50:10 +0000 Message-ID: References: In-Reply-To: authentication-results: spf=none (sender IP is ) smtp.mailfrom=fxue@os.amperecomputing.com; x-ms-oob-tlc-oobclassifiers: OLM:5797; received-spf: None (protection.outlook.com: os.amperecomputing.com does not designate permitted sender hosts) x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-messagedata: BUOFsyawGAJXP6YvptqWoaiCDSqgrO3mvgWgkuS7ETIOb2YJlVQ2J9ZTcfz0PtNKvJBbyG91CE8mk0jm9B87PMp5KfcV6KTsbwSlMUmjdTpxzq1eYN0amOyrWix5/ObFMp41OpKa01EdA1GgIPRKqQ== x-ms-exchange-transport-forked: True MIME-Version: 1.0 X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-CrossTenant-userprincipalname: noeDfNhmxVZrOA+k3Eau5bbwYy4Lq0dSpY6tivI7PdEllZvsRPTcqg1wxGtz9GN/Mfe92FfoFGJFpELwPRqC/N6Se4XElWbUghyZtFaWx3I= X-IsSubscribed: yes Made some changes. Feng From 74aef0cd2f40ff828a4b2abcbbdbbf4b1aea1fcf Mon Sep 17 00:00:00 2001 From: Feng Xue Date: Tue, 21 Jan 2020 20:53:38 +0800 Subject: [PATCH] Generalized value pass-through for self-recusive function --- gcc/ipa-cp.c | 195 ++++++++++++++++++----------- gcc/testsuite/g++.dg/ipa/pr93203.C | 95 ++++++++++++++ gcc/testsuite/gcc.dg/ipa/ipcp-1.c | 2 +- 3 files changed, 216 insertions(+), 76 deletions(-) create mode 100644 gcc/testsuite/g++.dg/ipa/pr93203.C diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c index 17da1d8e8a7..64d23a34292 100644 --- a/gcc/ipa-cp.c +++ b/gcc/ipa-cp.c @@ -1850,7 +1850,7 @@ ipcp_lattice::add_value (valtype newval, cgraph_edge *cs, { ipcp_value_source *s; for (s = val->sources; s; s = s->next) - if (s->cs == cs) + if (s->cs == cs && s->val == src_val) break; if (s) return false; @@ -4207,6 +4207,33 @@ get_info_about_necessary_edges (ipcp_value *val, cgraph_node *dest, return hot; } +/* Given a NODE, and a set of its CALLERS, try to adjust order of the callers + to let a non-self-recursive caller be the first element. Thus, we can + simplify intersecting operations on values that arrive from all of these + callers, especially when there exists self-recursive call. Return true if + this kind of adjustment is possible. */ + +static bool +adjust_callers_for_value_intersection (vec callers, + cgraph_node *node) +{ + for (unsigned i = 0; i < callers.length (); i++) + { + cgraph_edge *cs = callers[i]; + + if (cs->caller != node) + { + if (i > 0) + { + callers[i] = callers[0]; + callers[0] = cs; + } + return true; + } + } + return false; +} + /* Return a vector of incoming edges that do bring value VAL to node DEST. It is assumed their number is known and equal to CALLER_COUNT. */ @@ -4230,6 +4257,9 @@ gather_edges_for_value (ipcp_value *val, cgraph_node *dest, } } + if (caller_count > 1) + adjust_callers_for_value_intersection (ret, dest); + return ret; } @@ -4241,7 +4271,6 @@ get_replacement_map (class ipa_node_params *info, tree value, int parm_num) { struct ipa_replace_map *replace_map; - replace_map = ggc_alloc (); if (dump_file) { @@ -4592,36 +4621,40 @@ create_specialized_node (struct cgraph_node *node, } /* Return true, if JFUNC, which describes a i-th parameter of call CS, is a - simple no-operation pass-through function to itself. */ + pass-through function to itself. When SIMPLE is true, further check if + JFUNC is a simple no-operation pass-through. */ static bool -self_recursive_pass_through_p (cgraph_edge *cs, ipa_jump_func *jfunc, int i) +self_recursive_pass_through_p (cgraph_edge *cs, ipa_jump_func *jfunc, int i, + bool simple = true) { enum availability availability; if (cs->caller == cs->callee->function_symbol (&availability) && availability > AVAIL_INTERPOSABLE && jfunc->type == IPA_JF_PASS_THROUGH - && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR + && (!simple || ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR) && ipa_get_jf_pass_through_formal_id (jfunc) == i) return true; return false; } /* Return true, if JFUNC, which describes a part of an aggregate represented - or pointed to by the i-th parameter of call CS, is a simple no-operation - pass-through function to itself. */ + or pointed to by the i-th parameter of call CS, is a pass-through function + to itself. When SIMPLE is true, further check if JFUNC is a simple + no-operation pass-through. */ static bool self_recursive_agg_pass_through_p (cgraph_edge *cs, ipa_agg_jf_item *jfunc, - int i) + int i, bool simple = true) { enum availability availability; if (cs->caller == cs->callee->function_symbol (&availability) && availability > AVAIL_INTERPOSABLE && jfunc->jftype == IPA_JF_LOAD_AGG && jfunc->offset == jfunc->value.load_agg.offset - && jfunc->value.pass_through.operation == NOP_EXPR - && jfunc->value.pass_through.formal_id == i) + && (!simple || jfunc->value.pass_through.operation == NOP_EXPR) + && jfunc->value.pass_through.formal_id == i + && useless_type_conversion_p (jfunc->value.load_agg.type, jfunc->type)) return true; return false; } @@ -4653,9 +4686,6 @@ find_more_scalar_values_for_callers_subset (struct cgraph_node *node, struct ipa_jump_func *jump_func; tree t; - if (IPA_NODE_REF (cs->caller) && IPA_NODE_REF (cs->caller)->node_dead) - continue; - if (!IPA_EDGE_REF (cs) || i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs)) || (i == 0 @@ -4665,10 +4695,30 @@ find_more_scalar_values_for_callers_subset (struct cgraph_node *node, break; } jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i); - if (self_recursive_pass_through_p (cs, jump_func, i)) - continue; - t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func, type); + /* Besides simple pass-through jump function, arithmetic jump + function could also introduce argument-direct-pass-through for + self-feeding recursive call. For example, + + fn (int i) + { + fn (i & 1); + } + + Given that i is 0, recursive propagation via (i & 1) also gets + 0. */ + if (self_recursive_pass_through_p (cs, jump_func, i, false)) + { + gcc_assert (newval); + t = ipa_get_jf_arith_result ( + ipa_get_jf_pass_through_operation (jump_func), + newval, + ipa_get_jf_pass_through_operand (jump_func), + type); + } + else + t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func, + type); if (!t || (newval && !values_equal_for_ipcp_p (t, newval)) @@ -4817,19 +4867,12 @@ intersect_with_plats (class ipcp_param_lattices *plats, break; if (aglat->offset - offset == item->offset) { - gcc_checking_assert (item->value); if (aglat->is_single_const ()) { tree value = aglat->values->value; if (values_equal_for_ipcp_p (item->value, value)) found = true; - else if (item->value == error_mark_node) - { - /* Replace unknown place holder value with real one. */ - item->value = value; - found = true; - } } break; } @@ -4898,12 +4941,6 @@ intersect_with_agg_replacements (struct cgraph_node *node, int index, { if (values_equal_for_ipcp_p (item->value, av->value)) found = true; - else if (item->value == error_mark_node) - { - /* Replace place holder value with real one. */ - item->value = av->value; - found = true; - } break; } } @@ -5008,31 +5045,16 @@ intersect_aggregates_with_edge (struct cgraph_edge *cs, int index, for (unsigned i = 0; i < jfunc->agg.items->length (); i++) { struct ipa_agg_jf_item *agg_item = &(*jfunc->agg.items)[i]; - struct ipa_agg_value agg_value; - - if (self_recursive_agg_pass_through_p (cs, agg_item, index)) - { - /* For a self-recursive call, if aggregate jump function is a - simple pass-through, the exact value that it stands for is - not known at this point, which must comes from other call - sites. But we still need to add a place holder in value - sets to indicate it, here we use error_mark_node to - represent the special unknown value, which will be replaced - with real one during later intersecting operations. */ - agg_value.value = error_mark_node; - } - else + tree value = ipa_agg_value_from_node (caller_info, cs->caller, + agg_item); + if (value) { - tree value = ipa_agg_value_from_node (caller_info, cs->caller, - agg_item); - if (!value) - continue; + struct ipa_agg_value agg_value; agg_value.value = value; + agg_value.offset = agg_item->offset; + inter.safe_push (agg_value); } - - agg_value.offset = agg_item->offset; - inter.safe_push (agg_value); } else FOR_EACH_VEC_ELT (inter, k, item) @@ -5053,25 +5075,32 @@ intersect_aggregates_with_edge (struct cgraph_edge *cs, int index, { tree value; - if (self_recursive_agg_pass_through_p (cs, ti, index)) - { - /* A simple aggregate pass-through in self-recursive - call should lead to same value. */ - found = true; - } - else if ((value = ipa_agg_value_from_node (caller_info, - cs->caller, ti))) - { - if (values_equal_for_ipcp_p (item->value, value)) - found = true; - else if (item->value == error_mark_node) - { - /* Replace unknown place holder value with real - one. */ - item->value = value; - found = true; - } - } + /* 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++; @@ -5147,9 +5176,6 @@ find_aggregate_values_for_callers_subset (struct cgraph_node *node, if (!item->value) continue; - /* All values must be real values, not unknown place holders. */ - gcc_assert (item->value != error_mark_node); - v = ggc_alloc (); v->index = i; v->offset = item->offset; @@ -5545,13 +5571,33 @@ decide_whether_version_node (struct cgraph_node *node) if (info->do_clone_for_all_contexts) { struct cgraph_node *clone; - vec callers; + vec callers = node->collect_callers (); + + for (int i = callers.length () - 1; i >= 0; i--) + { + cgraph_edge *cs = callers[i]; + class ipa_node_params *caller_info = IPA_NODE_REF (cs->caller); + + if (caller_info && caller_info->node_dead) + callers.unordered_remove (i); + } + + if (!adjust_callers_for_value_intersection (callers, node)) + { + /* If node is not called by anyone, or all its caller edges are + self-recursive, the node is not really be in use, no need to + do cloning. */ + callers.release (); + known_csts.release (); + known_contexts.release (); + info->do_clone_for_all_contexts = false; + return ret; + } if (dump_file) fprintf (dump_file, " - Creating a specialized node of %s " "for all known contexts.\n", node->dump_name ()); - callers = node->collect_callers (); 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 @@ -5564,7 +5610,6 @@ decide_whether_version_node (struct cgraph_node *node) } clone = create_specialized_node (node, known_csts, known_contexts, aggvals, callers); - info = IPA_NODE_REF (node); info->do_clone_for_all_contexts = false; IPA_NODE_REF (clone)->is_all_contexts_clone = true; ret = true; diff --git a/gcc/testsuite/g++.dg/ipa/pr93203.C b/gcc/testsuite/g++.dg/ipa/pr93203.C new file mode 100644 index 00000000000..b4cd69001b5 --- /dev/null +++ b/gcc/testsuite/g++.dg/ipa/pr93203.C @@ -0,0 +1,95 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -w -std=gnu++11" } */ + +class a { +public: + a(char *); +}; +class ad { +public: + ad(a *); +}; +class b {}; +using ah = class ak { + using al = char; + +public: + ak(b) : ak(0) {} + ak an() { return ap & 1; } + al ap; + ak(al af) : ap(af) {} +}; +struct at { + ah au; + int av; + char aw; + char ax; +}; +class az { +public: + struct ba { + void bb(ak am) { + ak bc = am.an(); + bb(bc); + } + }; + void bd(ak am) { be.bb(am); } + ba be; +}; +class bg { +public: + int bh; + at bi; +}; +int bj; +int *bk; +int c; +class bl { + bool bm(); + bg bn; + az bo; + int e; + int bq; +}; +class bs { +public: + bs(int *, ah *, char *, char *, int); +}; +template < typename bt > class bu : bs { + using bv = typename bt::bv; + +public: + template < typename... bx > + bu(a *by, int *bz, at body, bx...) + : bs(bz, &body.au, &body.aw, &body.ax, body.av), ca(bx()...), cb(by), + cc(by), cd(by), ce(by) {} + void cf() { + auto cg = ch(); + auto ci = *cj(); + ca.ck(this, cg, &ci); + } + bt ca; + ad cb; + ad cc; + ad cd; + ad ce; + bv *cj(); + bv ch(); +}; +class cl { +public: + using bv = struct {}; + cl(az *, int, int, int, int, a *, int, int **); + void ck(bs *, bv, bv *) { + b d; + ak ci(d); + bo.bd(ci); + } + az bo; +}; +bool bl::bm() { + a by(""); + bu< cl > cn(&by, &bj, bn.bi, &bo, c, bn.bh, e, 0, &by, bq, &bk); + cn.cf(); +} + diff --git a/gcc/testsuite/gcc.dg/ipa/ipcp-1.c b/gcc/testsuite/gcc.dg/ipa/ipcp-1.c index 952694d302b..baa9c97ffb0 100644 --- a/gcc/testsuite/gcc.dg/ipa/ipcp-1.c +++ b/gcc/testsuite/gcc.dg/ipa/ipcp-1.c @@ -45,7 +45,7 @@ main (int argc, char *argv[]) } -/* { dg-final { scan-ipa-dump "Creating a specialized node of f.*for all known contexts" "cp" } } */ +/* { dg-final { scan-ipa-dump "Creating a specialized node of f" "cp" } } */ /* { dg-final { scan-ipa-dump "replacing param .0 a with const 7" "cp" } } */ -- 2.17.1