From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx0a-001b2d01.pphosted.com (mx0a-001b2d01.pphosted.com [148.163.156.1]) by sourceware.org (Postfix) with ESMTPS id D44AF385802E for ; Fri, 4 Dec 2020 03:06:30 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org D44AF385802E Received: from pps.filterd (m0187473.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.0.42/8.16.0.42) with SMTP id 0B434lcd052147; Thu, 3 Dec 2020 22:06:28 -0500 Received: from pps.reinject (localhost [127.0.0.1]) by mx0a-001b2d01.pphosted.com with ESMTP id 357734qn2h-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 03 Dec 2020 22:06:28 -0500 Received: from m0187473.ppops.net (m0187473.ppops.net [127.0.0.1]) by pps.reinject (8.16.0.36/8.16.0.36) with SMTP id 0B435I8O053651; Thu, 3 Dec 2020 22:05:56 -0500 Received: from ppma01dal.us.ibm.com (83.d6.3fa9.ip4.static.sl-reverse.com [169.63.214.131]) by mx0a-001b2d01.pphosted.com with ESMTP id 357734qmxa-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 03 Dec 2020 22:05:55 -0500 Received: from pps.filterd (ppma01dal.us.ibm.com [127.0.0.1]) by ppma01dal.us.ibm.com (8.16.0.42/8.16.0.42) with SMTP id 0B42vabm024394; Fri, 4 Dec 2020 03:05:43 GMT Received: from b01cxnp23033.gho.pok.ibm.com (b01cxnp23033.gho.pok.ibm.com [9.57.198.28]) by ppma01dal.us.ibm.com with ESMTP id 355rf81vna-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 04 Dec 2020 03:05:42 +0000 Received: from b01ledav006.gho.pok.ibm.com (b01ledav006.gho.pok.ibm.com [9.57.199.111]) by b01cxnp23033.gho.pok.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 0B435gFA44040464 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 4 Dec 2020 03:05:42 GMT Received: from b01ledav006.gho.pok.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 326F6AC05E; Fri, 4 Dec 2020 03:05:42 +0000 (GMT) Received: from b01ledav006.gho.pok.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id A65E8AC05B; Fri, 4 Dec 2020 03:05:41 +0000 (GMT) Received: from genoa (unknown [9.40.192.157]) by b01ledav006.gho.pok.ibm.com (Postfix) with ESMTPS; Fri, 4 Dec 2020 03:05:41 +0000 (GMT) From: Jiufu Guo To: Jeff Law Cc: Richard Biener , gcc-patches@gcc.gnu.org, wschmidt@linux.ibm.com, dje.gcc@gmail.com, segher@kernel.crashing.org, Jan Hubicka Subject: Re: [PATCH 1/2] correct BB frequencies after loop changed References: <20201009101242.2478660-1-guojiufu@linux.ibm.com> <0ddac0c9-9654-435e-939a-e783eaf02b0b@redhat.com> <5c0c5060-15d2-b628-1b32-6bf32164e193@redhat.com> Date: Fri, 04 Dec 2020 11:05:38 +0800 In-Reply-To: (Jiufu Guo's message of "Tue, 24 Nov 2020 13:44:35 +0800") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-TM-AS-GCONF: 00 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.312, 18.0.737 definitions=2020-12-03_15:2020-12-03, 2020-12-03 signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 lowpriorityscore=0 mlxlogscore=999 spamscore=0 phishscore=0 clxscore=1015 priorityscore=1501 mlxscore=0 bulkscore=0 impostorscore=0 adultscore=0 suspectscore=0 malwarescore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2009150000 definitions=main-2012040017 X-Spam-Status: No, score=-12.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, 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, 04 Dec 2020 03:06:32 -0000 Jiufu Guo writes: > Jeff Law writes: > >> On 11/18/20 12:28 AM, Richard Biener wrote: >>> On Tue, 17 Nov 2020, Jeff Law wrote: >>> >>>> Minor questions for Jan and Richi embedded below... >>>> >>>> On 10/9/20 4:12 AM, guojiufu via Gcc-patches wrote: >>>>> When investigating the issue from https://gcc.gnu.org/pipermail/gcc-p= atches/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 |=20 >>>>> exit-edge | latch | >>>>> ._________________. >>>>> >>>>> Those COUNTs have below equations: >>>>> COUNT of exit-edge:268435456 =3D COUNT of pre-header:268435456 >>>>> COUNT of exit-edge:268435456 =3D COUNT of header:805306369 * 33 >>>>> COUNT of header:805306369 =3D COUNT of pre-header:268435456 + COUNT o= f latch:536870911 >>>>> >>>>> >>>>> While after pcom: >>>>> >>>>> COUNT:268435456 pre-header >>>>> | >>>>> | .--------------------. >>>>> | | | >>>>> V v | >>>>> COUNT:268435456 | >>>>> / \ | >>>>> 50%/ \ | >>>>> / \ | >>>>> v v | >>>>> COUNT:134217728 COUNT:134217728 |=20 >>>>> exit-edge | latch | >>>>> ._________________. >>>>> >>>>> COUNT !=3D COUNT + COUNT >>>>> COUNT !=3D 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" >>>>>=20=20 >>>>> static void copy_loops_to (class loop **, int, >>>>> class loop *); >>>>> @@ -1773,3 +1774,55 @@ loop_version (class loop *loop, >>>>>=20=20 >>>>> 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 ne= w_prob) >>>>> +{ >>>>> + edge exit =3D single_exit (loop); >>>>> + if (!exit) >>>>> + return false; >>>>> + >>>>> + edge e; >>>>> + edge_iterator ei; >>>>> + edge non_exit; >>>>> + basic_block * bbs; >>>>> + profile_count exit_count =3D loop_preheader_edge (loop)->count (); >>>>> + profile_probability exit_p =3D exit_count.probability_in (loop->he= ader->count); >>>>> + profile_count base_count =3D loop->header->count; >>>>> + profile_count after_num =3D base_count.apply_probability (exit_p); >>>>> + profile_count after_den =3D base_count.apply_probability (new_prob= ); >>>>> + >>>>> + /* Update BB counts in loop body. >>>>> + COUNT =3D COUNT >>>>> + COUNT =3D COUNT
* exit_edge_probility >>>>> + The COUNT =3D COUNT * old_exit_p / new_= prob. */ >>>>> + bbs =3D get_loop_body (loop); >>>>> + scale_bbs_frequencies_profile_count (bbs, loop->num_nodes, after_n= um, >>>>> + 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 !=3D exit) >>>>> + break; >>>>> + non_exit =3D e; >>>> Are we sure that exit->src has just two successors (will that case be >>>> canonicalized before we get here?).? If it has > 2 successors, then I'm >>>> pretty sure the frequencies get mucked up.? Richi could probably answer >>>> whether or not the block with the loop exit edge can have > 2 successo= rs. >>> There's nothing preventing more than two edges in the SRC generally >>> (the exit could be an edge off a switch). >> That's precisely the case I was concerned about. >> >>> But of course this function >>> is very likely called on loops that are countable which means niter >>> analysis has to handle it which in turn means all exits are controlled >>> by simple conditions on IVs. >> Thanks.=C2=A0 It sounds like it's unlikely we'll have > 2 out edges. >>> >>> I guess adding a gcc_assert (EDGE_COUNT (exit->src->succs) =3D=3D 2) ca= n't=20 >>> hurt (with a comment reflecting the above). >> Sounds good to me.=C2=A0=C2=A0 Just catching this case if it happens is = good >> enough for me -- if it trips we can come back and adjust the code to >> distribute across the edges. > With this gcc_assert, run bootstrap and regression test, no failure > occur. > For this patch, in the original code, there is code: > - new_nonexit =3D single_pred_edge (loop->latch); > - prob =3D new_nonexit->probability; > - new_nonexit->probability =3D new_exit->probability.invert (); > Which is also assume 2 successors. So, it may relative safe. > > Thanks, > Jiufu Guo. > >> >> So if Jan could chime in on the downstream edge updates question then I >> think we'd be ready to move forward. >> >> jeff Hi, I saw Jeff say ok for patch [PATCH 2/2] https://gcc.gnu.org/pipermail/gcc-patches/2020-December/560833.html. I'm wondering if we can approval this patch [PATCH 1/2] https://gcc.gnu.org/pipermail/gcc-patches/2020-October/555871.html. and then I may commit these patches to trunk. :) Thanks, Jiufu Guo.