From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 63767 invoked by alias); 16 Jul 2019 06:54:51 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 63756 invoked by uid 89); 16 Jul 2019 06:54:50 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-20.9 required=5.0 tests=AWL,BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_LOW,SPF_PASS autolearn=ham version=3.3.1 spammy= X-HELO: mx0a-001b2d01.pphosted.com Received: from mx0b-001b2d01.pphosted.com (HELO mx0a-001b2d01.pphosted.com) (148.163.158.5) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 16 Jul 2019 06:54:49 +0000 Received: from pps.filterd (m0098419.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.0.27/8.16.0.27) with SMTP id x6G6sapX072153 for ; Tue, 16 Jul 2019 02:54:47 -0400 Received: from e06smtp05.uk.ibm.com (e06smtp05.uk.ibm.com [195.75.94.101]) by mx0b-001b2d01.pphosted.com with ESMTP id 2ts9a5gvyk-1 (version=TLSv1.2 cipher=AES256-GCM-SHA384 bits=256 verify=NOT) for ; Tue, 16 Jul 2019 02:54:45 -0400 Received: from localhost by e06smtp05.uk.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Tue, 16 Jul 2019 07:53:22 +0100 Received: from b06avi18626390.portsmouth.uk.ibm.com (9.149.26.192) by e06smtp05.uk.ibm.com (192.168.101.135) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; (version=TLSv1/SSLv3 cipher=AES256-GCM-SHA384 bits=256/256) Tue, 16 Jul 2019 07:53:18 +0100 Received: from d06av26.portsmouth.uk.ibm.com (d06av26.portsmouth.uk.ibm.com [9.149.105.62]) by b06avi18626390.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id x6G6r42h31326628 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 16 Jul 2019 06:53:04 GMT Received: from d06av26.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id A0A1BAE055; Tue, 16 Jul 2019 06:53:17 +0000 (GMT) Received: from d06av26.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id AE2C2AE04D; Tue, 16 Jul 2019 06:53:15 +0000 (GMT) Received: from luoxhus-mbp.cn.ibm.com (unknown [9.200.154.76]) by d06av26.portsmouth.uk.ibm.com (Postfix) with ESMTP; Tue, 16 Jul 2019 06:53:15 +0000 (GMT) Subject: Re: [PATCH v3] Generalize get_most_common_single_value to return k_th value & count To: =?UTF-8?Q?Martin_Li=c5=a1ka?= , gcc-patches@gcc.gnu.org Cc: hubicka@ucw.cz, segher@kernel.crashing.org, wschmidt@linux.ibm.com References: <20190715082043.24541-1-luoxhu@linux.ibm.com> <622d5e32-f430-2b07-2902-463f8770e984@suse.cz> From: luoxhu Date: Tue, 16 Jul 2019 07:42:00 -0000 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:60.0) Gecko/20100101 Thunderbird/60.7.2 MIME-Version: 1.0 In-Reply-To: <622d5e32-f430-2b07-2902-463f8770e984@suse.cz> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit x-cbid: 19071606-0020-0000-0000-00000353F1D6 X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 19071606-0021-0000-0000-000021A7BC49 Message-Id: X-SW-Source: 2019-07/txt/msg01083.txt.bz2 Currently get_most_common_single_value could only return the max hist , add qsort to enable this function return nth value. Rename it to get_nth_most_common_value. v3 Changes: 1. Move sort to profile.c after loading values from disk. Simplify get_nth_most_common_value. 2. Make qsort stable with value check if count is same. 3. Other comments from v2. gcc/ChangeLog: 2019-07-15 Xiong Hu Luo * ipa-profile.c (get_most_common_single_value): Use get_nth_most_common_value. * profile.c (struct value_count_t): New struct. (cmp_counts): New function. (sort_hist_value): New function. (compute_value_histograms): Call sort_hist_value to sort the values after loading from disk. * value-prof.c (get_most_common_single_value): Rename to ... get_nth_most_common_value. Add input params n, return the n_th value and count. (gimple_divmod_fixed_value_transform): Use get_nth_most_common_value. (gimple_ic_transform): Likewise. (gimple_stringops_transform): Likewise. * value-prof.h (get_most_common_single_value): Add input params n, default to 0. --- gcc/ipa-profile.c | 4 +-- gcc/profile.c | 74 +++++++++++++++++++++++++++++++++++++++++++++++ gcc/value-prof.c | 53 +++++++++++++++------------------ gcc/value-prof.h | 9 +++--- 4 files changed, 103 insertions(+), 37 deletions(-) diff --git a/gcc/ipa-profile.c b/gcc/ipa-profile.c index 1fb939b73d0..970dba39c80 100644 --- a/gcc/ipa-profile.c +++ b/gcc/ipa-profile.c @@ -192,8 +192,8 @@ ipa_profile_generate_summary (void) if (h) { gcov_type val, count, all; - if (get_most_common_single_value (NULL, "indirect call", - h, &val, &count, &all)) + if (get_nth_most_common_value (NULL, "indirect call", h, + &val, &count, &all)) { struct cgraph_edge * e = node->get_edge (stmt); if (e && !e->indirect_unknown_callee) diff --git a/gcc/profile.c b/gcc/profile.c index 441cb8eb183..54780b44859 100644 --- a/gcc/profile.c +++ b/gcc/profile.c @@ -743,6 +743,74 @@ compute_branch_probabilities (unsigned cfg_checksum, unsigned lineno_checksum) free_aux_for_blocks (); } +struct value_count_t +{ + gcov_type value; + gcov_type count; +}; + +static int +cmp_counts (const void *v1, const void *v2) +{ + const value_count_t *h1 = (const value_count_t *) v1; + const value_count_t *h2 = (const value_count_t *) v2; + if (h1->count < h2->count) + return 1; + if (h1->count > h2->count) + return -1; + if (h1->count == h2->count) + { + if (h1->value < h2->value) + return 1; + if (h1->value > h2->value) + return -1; + } + /* There may be two entries with same count as well as value very unlikely + in a multi-threaded instrumentation. But the memory layout of the {value, + count} tuple can be different. The function will return K-th most + common value. */ + return 0; +} + +/* Sort the histogram value and count for TOPN and INDIR_CALL type. */ + +static bool +sort_hist_value (histogram_value hist) +{ + auto_vec value_vec; + struct value_count_t temp; + unsigned i; + + if (hist->hvalue.counters[2] == -1) + return false; + + gcc_assert (hist->type == HIST_TYPE_TOPN_VALUES + || hist->type == HIST_TYPE_INDIR_CALL); + + gcc_assert (hist->n_counters == GCOV_TOPN_VALUES_COUNTERS); + + for (i = 0; i < GCOV_TOPN_VALUES; i++) + { + gcov_type v = hist->hvalue.counters[2 * i + 1]; + gcov_type c = hist->hvalue.counters[2 * i + 2]; + + temp.value = v; + temp.count = c; + + value_vec.safe_push (temp); + } + + value_vec.qsort (cmp_counts); + + gcc_assert (value_vec.length () == GCOV_TOPN_VALUES); + + for (i = 0; i < GCOV_TOPN_VALUES; i++) + { + hist->hvalue.counters[2 * i + 1] = value_vec[i].value; + hist->hvalue.counters[2 * i + 2] = value_vec[i].count; + } + return true; +} /* Load value histograms values whose description is stored in VALUES array from .gcda file. @@ -808,6 +876,12 @@ compute_value_histograms (histogram_values values, unsigned cfg_checksum, else hist->hvalue.counters[j] = 0; + if (hist->type == HIST_TYPE_TOPN_VALUES + || hist->type == HIST_TYPE_INDIR_CALL) + { + sort_hist_value (hist); + } + /* Time profiler counter is not related to any statement, so that we have to read the counter and set the value to the corresponding call graph node. */ diff --git a/gcc/value-prof.c b/gcc/value-prof.c index 32e6ddd8165..97e4ae18ba3 100644 --- a/gcc/value-prof.c +++ b/gcc/value-prof.c @@ -713,45 +713,38 @@ gimple_divmod_fixed_value (gassign *stmt, tree value, profile_probability prob, return tmp2; } -/* Return most common value of TOPN_VALUE histogram. If - there's a unique value, return true and set VALUE and COUNT +/* Return the n-th value count of TOPN_VALUE histogram. If + there's a value, return true and set VALUE and COUNT arguments. */ bool -get_most_common_single_value (gimple *stmt, const char *counter_type, - histogram_value hist, - gcov_type *value, gcov_type *count, - gcov_type *all) +get_nth_most_common_value (gimple *stmt, const char *counter_type, + histogram_value hist, gcov_type *value, + gcov_type *count, gcov_type *all, unsigned n) { if (hist->hvalue.counters[2] == -1) return false; + gcc_assert (n < GCOV_TOPN_VALUES); + *count = 0; *value = 0; gcov_type read_all = hist->hvalue.counters[0]; - for (unsigned i = 0; i < GCOV_TOPN_VALUES; i++) - { - gcov_type v = hist->hvalue.counters[2 * i + 1]; - gcov_type c = hist->hvalue.counters[2 * i + 2]; - - /* Indirect calls can't be vereified. */ - if (stmt && check_counter (stmt, counter_type, &c, &read_all, - gimple_bb (stmt)->count)) - return false; + gcov_type v = hist->hvalue.counters[2 * n + 1]; + gcov_type c = hist->hvalue.counters[2 * n + 2]; - *all = read_all; + /* Indirect calls can't be vereified. */ + if (stmt + && check_counter (stmt, counter_type, &c, &read_all, + gimple_bb (stmt)->count)) + return false; - if (c > *count) - { - *value = v; - *count = c; - } - else if (c == *count && v > *value) - *value = v; - } + *all = read_all; + *value = v; + *count = c; return true; } @@ -784,8 +777,8 @@ gimple_divmod_fixed_value_transform (gimple_stmt_iterator *si) if (!histogram) return false; - if (!get_most_common_single_value (stmt, "divmod", histogram, &val, &count, - &all)) + if (!get_nth_most_common_value (stmt, "divmod", histogram, &val, &count, + &all)) return false; value = histogram->hvalue.value; @@ -1439,8 +1432,8 @@ gimple_ic_transform (gimple_stmt_iterator *gsi) if (!histogram) return false; - if (!get_most_common_single_value (NULL, "indirect call", histogram, &val, - &count, &all)) + if (!get_nth_most_common_value (NULL, "indirect call", histogram, &val, + &count, &all)) return false; if (4 * count <= 3 * all) @@ -1658,8 +1651,8 @@ gimple_stringops_transform (gimple_stmt_iterator *gsi) if (!histogram) return false; - if (!get_most_common_single_value (stmt, "stringops", histogram, &val, - &count, &all)) + if (!get_nth_most_common_value (stmt, "stringops", histogram, &val, &count, + &all)) return false; gimple_remove_histogram_value (cfun, stmt, histogram); diff --git a/gcc/value-prof.h b/gcc/value-prof.h index ca846d08cbd..1078722163b 100644 --- a/gcc/value-prof.h +++ b/gcc/value-prof.h @@ -89,11 +89,10 @@ void free_histograms (function *); void stringop_block_profile (gimple *, unsigned int *, HOST_WIDE_INT *); gcall *gimple_ic (gcall *, struct cgraph_node *, profile_probability); bool check_ic_target (gcall *, struct cgraph_node *); -bool get_most_common_single_value (gimple *stmt, const char *counter_type, - histogram_value hist, - gcov_type *value, gcov_type *count, - gcov_type *all); - +bool get_nth_most_common_value (gimple *stmt, const char *counter_type, + histogram_value hist, gcov_type *value, + gcov_type *count, gcov_type *all, + unsigned n = 0); /* In tree-profile.c. */ extern void gimple_init_gcov_profiler (void); -- 2.22.0.428.g6d5b264208