From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx0a-001b2d01.pphosted.com (mx0b-001b2d01.pphosted.com [148.163.158.5]) by sourceware.org (Postfix) with ESMTPS id EA4E23861812 for ; Fri, 9 Oct 2020 10:12:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org EA4E23861812 Received: from pps.filterd (m0098413.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.0.42/8.16.0.42) with SMTP id 099A5YhK026183; Fri, 9 Oct 2020 06:12:49 -0400 Received: from pps.reinject (localhost [127.0.0.1]) by mx0b-001b2d01.pphosted.com with ESMTP id 342nf98s49-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 09 Oct 2020 06:12:49 -0400 Received: from m0098413.ppops.net (m0098413.ppops.net [127.0.0.1]) by pps.reinject (8.16.0.36/8.16.0.36) with SMTP id 099A9sMo040391; Fri, 9 Oct 2020 06:12:49 -0400 Received: from ppma04fra.de.ibm.com (6a.4a.5195.ip4.static.sl-reverse.com [149.81.74.106]) by mx0b-001b2d01.pphosted.com with ESMTP id 342nf98s3m-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 09 Oct 2020 06:12:48 -0400 Received: from pps.filterd (ppma04fra.de.ibm.com [127.0.0.1]) by ppma04fra.de.ibm.com (8.16.0.42/8.16.0.42) with SMTP id 099AC7rO022723; Fri, 9 Oct 2020 10:12:47 GMT Received: from b06avi18626390.portsmouth.uk.ibm.com (b06avi18626390.portsmouth.uk.ibm.com [9.149.26.192]) by ppma04fra.de.ibm.com with ESMTP id 3429hs0940-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 09 Oct 2020 10:12:47 +0000 Received: from d06av23.portsmouth.uk.ibm.com (d06av23.portsmouth.uk.ibm.com [9.149.105.59]) by b06avi18626390.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 099ACi1T25100620 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 9 Oct 2020 10:12:44 GMT Received: from d06av23.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 2DE07A4040; Fri, 9 Oct 2020 10:12:44 +0000 (GMT) Received: from d06av23.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 47BB6A4053; Fri, 9 Oct 2020 10:12:43 +0000 (GMT) Received: from genoa.aus.stglabs.ibm.com (unknown [9.40.192.157]) by d06av23.portsmouth.uk.ibm.com (Postfix) with ESMTP; Fri, 9 Oct 2020 10:12:43 +0000 (GMT) From: guojiufu To: gcc-patches@gcc.gnu.org Cc: guojiufu@linux.ibm.com, wschmidt@linux.ibm.com, segher@kernel.crashing.org, dje.gcc@gmail.com Subject: [PATCH 1/2] correct BB frequencies after loop changed Date: Fri, 9 Oct 2020 18:12:41 +0800 Message-Id: <20201009101242.2478660-1-guojiufu@linux.ibm.com> X-Mailer: git-send-email 2.25.1 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-TM-AS-GCONF: 00 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.235, 18.0.687 definitions=2020-10-09_05:2020-10-09, 2020-10-09 signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 mlxscore=0 priorityscore=1501 bulkscore=0 malwarescore=0 adultscore=0 suspectscore=0 impostorscore=0 clxscore=1015 phishscore=0 mlxlogscore=999 spamscore=0 lowpriorityscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2009150000 definitions=main-2010090068 X-Spam-Status: No, score=-11.0 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-List-Received-Date: Fri, 09 Oct 2020 10:12:51 -0000 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 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. Bootstrap and regtest pass on ppc64le. Is this ok for trunk? Jiufu gcc/ChangeLog: 2020-10-09 Jiufu Guo * cfgloopmanip.h (recompute_loop_frequencies): New function. * cfgloopmanip.c (recompute_loop_frequencies): New implementation. * tree-ssa-loop-manip.c (tree_transform_and_unroll_loop): Call recompute_loop_frequencies. --- gcc/cfgloopmanip.c | 53 +++++++++++++++++++++++++++++++++++++++ gcc/cfgloopmanip.h | 2 +- gcc/tree-ssa-loop-manip.c | 28 +++------------------ 3 files changed, 57 insertions(+), 26 deletions(-) diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c index 73134a20e33..b0ca82a67fd 100644 --- a/gcc/cfgloopmanip.c +++ b/gcc/cfgloopmanip.c @@ -31,6 +31,7 @@ along with GCC; see the file COPYING3. If not see #include "gimplify-me.h" #include "tree-ssa-loop-manip.h" #include "dumpfile.h" +#include "cfgrtl.h" static void copy_loops_to (class loop **, int, class loop *); @@ -1773,3 +1774,55 @@ loop_version (class loop *loop, return nloop; } + +/* Recalculate the COUNTs of BBs in LOOP, if the probability of exit edge + is NEW_PROB. */ + +bool +recompute_loop_frequencies (class loop *loop, profile_probability new_prob) +{ + edge exit = single_exit (loop); + if (!exit) + return false; + + edge e; + edge_iterator ei; + edge non_exit; + 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_prob); + + /* Update BB counts in loop body. + COUNT = COUNT + COUNT = COUNT
* exit_edge_probility + The COUNT = COUNT * old_exit_p / new_prob. */ + 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 the BB besides exit edge (maybe latch). */ + FOR_EACH_EDGE (e, ei, exit->src->succs) + if (e != exit) + break; + non_exit = e; + + non_exit->probability = new_prob.invert (); + non_exit->dest->count = profile_count::zero (); + FOR_EACH_EDGE (e, ei, non_exit->dest->preds) + non_exit->dest->count += e->src->count.apply_probability (e->probability); + + /* Update probability and count of exit destination. */ + exit->probability = new_prob; + exit->dest->count = profile_count::zero (); + FOR_EACH_EDGE (e, ei, exit->dest->preds) + exit->dest->count += e->src->count.apply_probability (e->probability); + + if (current_ir_type () != IR_GIMPLE) + update_br_prob_note (exit->src); + + 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, -- 2.25.1