From patchwork Tue Sep 22 05:37:47 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jiufu Guo X-Patchwork-Id: 1368767 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=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=gcc.gnu.org Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=XJywo3q9; dkim-atps=neutral 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 RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4BwVTC465Gz9sTM for ; Tue, 22 Sep 2020 15:38:03 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 4994F3851C09; Tue, 22 Sep 2020 05:37:59 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 4994F3851C09 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1600753079; bh=RZtWQTuD+4PzDWAj+tU9QZSBwFZyZ9zQdCzMSKfwqXk=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=XJywo3q9BoXd819FF8agygiPWdheYUHylXOgkDJ12neryvUC+acFOCo2/If5992md Ko0ocotB1mNU3GnVi9imLrd+uZ3KHnHxCUw1YJSLQHrSlyB0VOtGYjSKdIT48WEmGT JmS2gz05RoeYdkoRVyIqWamdlT+dQJjsGNKtrWjk= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx0b-001b2d01.pphosted.com (mx0b-001b2d01.pphosted.com [148.163.158.5]) by sourceware.org (Postfix) with ESMTPS id C1CE5398745C for ; Tue, 22 Sep 2020 05:37:55 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org C1CE5398745C Received: from pps.filterd (m0127361.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.0.42/8.16.0.42) with SMTP id 08M5XWsk030187; Tue, 22 Sep 2020 01:37:55 -0400 Received: from pps.reinject (localhost [127.0.0.1]) by mx0a-001b2d01.pphosted.com with ESMTP id 33q8pyu8vt-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Tue, 22 Sep 2020 01:37:54 -0400 Received: from m0127361.ppops.net (m0127361.ppops.net [127.0.0.1]) by pps.reinject (8.16.0.36/8.16.0.36) with SMTP id 08M5YLHc032203; Tue, 22 Sep 2020 01:37:54 -0400 Received: from ppma06ams.nl.ibm.com (66.31.33a9.ip4.static.sl-reverse.com [169.51.49.102]) by mx0a-001b2d01.pphosted.com with ESMTP id 33q8pyu8uy-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Tue, 22 Sep 2020 01:37:54 -0400 Received: from pps.filterd (ppma06ams.nl.ibm.com [127.0.0.1]) by ppma06ams.nl.ibm.com (8.16.0.42/8.16.0.42) with SMTP id 08M5bqDF030461; Tue, 22 Sep 2020 05:37:52 GMT Received: from b06avi18626390.portsmouth.uk.ibm.com (b06avi18626390.portsmouth.uk.ibm.com [9.149.26.192]) by ppma06ams.nl.ibm.com with ESMTP id 33n98gtrjf-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Tue, 22 Sep 2020 05:37:52 +0000 Received: from d06av22.portsmouth.uk.ibm.com (d06av22.portsmouth.uk.ibm.com [9.149.105.58]) by b06avi18626390.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 08M5aE4Y35389702 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 22 Sep 2020 05:36:14 GMT Received: from d06av22.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 9ED254C04A; Tue, 22 Sep 2020 05:37:49 +0000 (GMT) Received: from d06av22.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 7F9444C040; Tue, 22 Sep 2020 05:37:48 +0000 (GMT) Received: from genoa.aus.stglabs.ibm.com (unknown [9.40.192.157]) by d06av22.portsmouth.uk.ibm.com (Postfix) with ESMTP; Tue, 22 Sep 2020 05:37:48 +0000 (GMT) To: gcc-patches@gcc.gnu.org Subject: [RFC] update COUNTs of BB in loop. Date: Tue, 22 Sep 2020 13:37:47 +0800 Message-Id: <20200922053747.426770-1-guojiufu@linux.ibm.com> X-Mailer: git-send-email 2.25.1 MIME-Version: 1.0 X-TM-AS-GCONF: 00 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.235, 18.0.687 definitions=2020-09-22_05:2020-09-21, 2020-09-22 signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 spamscore=0 suspectscore=0 bulkscore=0 impostorscore=0 phishscore=0 clxscore=1015 mlxlogscore=999 mlxscore=0 priorityscore=1501 malwarescore=0 adultscore=0 lowpriorityscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2006250000 definitions=main-2009220046 X-Spam-Status: No, score=-11.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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: , X-Patchwork-Original-From: guojiufu via Gcc-patches From: Jiufu Guo Reply-To: guojiufu Cc: rguenther@suse.de, segher@kernel.crashing.org, wschmidt@linux.ibm.com, dje.gcc@gmail.com Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" Hi, When investigating the issue from https://gcc.gnu.org/pipermail/gcc-patches/2020-July/549786.html I find the BB COUNTs of loop seems are not accurate in some case. For example: In below figure: COUNT:268435456 pre-header | | .--------------------. | | | V v | COUNT:805306369 | / \ | 33%/ \ | / \ | v v | COUNT:268435456 COUNT:536870911 | exit-edge | latch | ._________________. Those COUNTs have below equations: COUNT of exit-edge:268435456 = COUNT of pre-header:268435456 COUNT of exit-edge:268435456 = COUNT of header:805306369 * 33 COUNT of header:805306369 = COUNT of pre-header:268435456 + COUNT of latch:536870911 While after pcom: COUNT:268435456 pre-header | | .--------------------. | | | V v | COUNT:268435456 | / \ | 50%/ \ | / \ | v v | COUNT:134217728 COUNT:134217728 | exit-edge | latch | ._________________. COUNT != COUNT + COUNT In some cases, the probility of exit-edge is easy to estimate, then those COUNTs of other BBs in loop can be re-caculated. Below is a patch to reset COUNTs as above description. Thanks for comments!! Jiufu --- gcc/cfgloopmanip.c | 43 +++++++++++++++++++++++++++++++++++++++ gcc/cfgloopmanip.h | 2 +- gcc/tree-ssa-loop-manip.c | 28 +++---------------------- 3 files changed, 47 insertions(+), 26 deletions(-) diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c index 73134a20e33..180916b0974 100644 --- a/gcc/cfgloopmanip.c +++ b/gcc/cfgloopmanip.c @@ -1773,3 +1773,46 @@ loop_version (class loop *loop, return nloop; } + +/* Recacluate the COUNTs of BBs in LOOP, if the probility of exit edge + is NEW_EXIT_P. */ + +bool +recompute_loop_frequencies (class loop *loop, profile_probability new_exit_p) +{ + edge exit = single_exit (loop); + if (!exit) + return false; + + basic_block * bbs; + profile_count exit_count = loop_preheader_edge (loop)->count (); + profile_probability exit_p = exit_count.probability_in (loop->header->count); + profile_count base_count = loop->header->count; + profile_count after_num = base_count.apply_probability (exit_p); + profile_count after_den = base_count.apply_probability (new_exit_p); + + /* Update BB counts in loop body. + COUNT = COUNT + COUNT = COUNT
* exit_edge_probility + The COUNT=COUNT * old_exit_p / new_exit_p. */ + bbs = get_loop_body (loop); + scale_bbs_frequencies_profile_count (bbs, loop->num_nodes, after_num, + after_den); + free (bbs); + + /* Update probability and count of latch. */ + edge new_nonexit = single_pred_edge (loop->latch); + new_nonexit->probability = new_exit_p.invert (); + loop->latch->count + = loop->header->count.apply_probability (new_nonexit->probability); + + /* Update probability and count of exit destination. */ + edge e; + edge_iterator ei; + exit->probability = new_exit_p; + exit->dest->count = profile_count::zero (); + FOR_EACH_EDGE (e, ei, exit->dest->preds) + exit->dest->count += e->src->count.apply_probability (e->probability); + + return true; +} diff --git a/gcc/cfgloopmanip.h b/gcc/cfgloopmanip.h index 7331e574e2f..d55bab17f65 100644 --- a/gcc/cfgloopmanip.h +++ b/gcc/cfgloopmanip.h @@ -62,5 +62,5 @@ class loop * loop_version (class loop *, void *, basic_block *, profile_probability, profile_probability, profile_probability, profile_probability, bool); - +extern bool recompute_loop_frequencies (class loop *, profile_probability); #endif /* GCC_CFGLOOPMANIP_H */ diff --git a/gcc/tree-ssa-loop-manip.c b/gcc/tree-ssa-loop-manip.c index a2717a411a3..4060d601cf8 100644 --- a/gcc/tree-ssa-loop-manip.c +++ b/gcc/tree-ssa-loop-manip.c @@ -1251,7 +1251,6 @@ tree_transform_and_unroll_loop (class loop *loop, unsigned factor, bool ok; unsigned i; profile_probability prob, prob_entry, scale_unrolled; - profile_count freq_e, freq_h; gcov_type new_est_niter = niter_for_unrolled_loop (loop, factor); unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP; auto_vec to_remove; @@ -1393,33 +1392,12 @@ tree_transform_and_unroll_loop (class loop *loop, unsigned factor, number of iterations, and change the probability of the new exit edge. */ - freq_h = loop->header->count; - freq_e = (loop_preheader_edge (loop))->count (); - if (freq_h.nonzero_p ()) - { - /* Avoid dropping loop body profile counter to 0 because of zero count - in loop's preheader. */ - if (freq_h.nonzero_p () && !(freq_e == profile_count::zero ())) - freq_e = freq_e.force_nonzero (); - scale_loop_frequencies (loop, freq_e.probability_in (freq_h)); - } - - exit_bb = single_pred (loop->latch); - new_exit = find_edge (exit_bb, rest); - new_exit->probability = profile_probability::always () - .apply_scale (1, new_est_niter + 1); - - rest->count += new_exit->count (); - - new_nonexit = single_pred_edge (loop->latch); - prob = new_nonexit->probability; - new_nonexit->probability = new_exit->probability.invert (); - prob = new_nonexit->probability / prob; - if (prob.initialized_p ()) - scale_bbs_frequencies (&loop->latch, 1, prob); + prob = profile_probability::always ().apply_scale (1, new_est_niter + 1); + recompute_loop_frequencies (loop, prob); /* Finally create the new counter for number of iterations and add the new exit instruction. */ + exit_bb = single_pred (loop->latch); bsi = gsi_last_nondebug_bb (exit_bb); exit_if = as_a (gsi_stmt (bsi)); create_iv (exit_base, exit_step, NULL_TREE, loop,