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 50ED6386F433 for ; Fri, 4 Dec 2020 06:17:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 50ED6386F433 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 0B467RJF167475; Fri, 4 Dec 2020 01:17:17 -0500 Received: from pps.reinject (localhost [127.0.0.1]) by mx0b-001b2d01.pphosted.com with ESMTP id 3577654q88-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 04 Dec 2020 01:17:16 -0500 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 0B46APU7173625; Fri, 4 Dec 2020 01:17:16 -0500 Received: from ppma03dal.us.ibm.com (b.bd.3ea9.ip4.static.sl-reverse.com [169.62.189.11]) by mx0b-001b2d01.pphosted.com with ESMTP id 3577654q7y-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 04 Dec 2020 01:17:16 -0500 Received: from pps.filterd (ppma03dal.us.ibm.com [127.0.0.1]) by ppma03dal.us.ibm.com (8.16.0.42/8.16.0.42) with SMTP id 0B467n4Z027816; Fri, 4 Dec 2020 06:17:15 GMT Received: from b01cxnp23033.gho.pok.ibm.com (b01cxnp23033.gho.pok.ibm.com [9.57.198.28]) by ppma03dal.us.ibm.com with ESMTP id 356xqhgbt9-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 04 Dec 2020 06:17:15 +0000 Received: from b01ledav005.gho.pok.ibm.com (b01ledav005.gho.pok.ibm.com [9.57.199.110]) by b01cxnp23033.gho.pok.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 0B46HFZ77144088 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 4 Dec 2020 06:17:15 GMT Received: from b01ledav005.gho.pok.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id EA1ADAE062; Fri, 4 Dec 2020 06:17:14 +0000 (GMT) Received: from b01ledav005.gho.pok.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 6753AAE063; Fri, 4 Dec 2020 06:17:14 +0000 (GMT) Received: from genoa (unknown [9.40.192.157]) by b01ledav005.gho.pok.ibm.com (Postfix) with ESMTPS; Fri, 4 Dec 2020 06:17:14 +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 14:17:12 +0800 In-Reply-To: (Jiufu Guo's message of "Fri, 04 Dec 2020 11:05:38 +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-04_01:2020-12-04, 2020-12-04 signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 mlxscore=0 bulkscore=0 spamscore=0 phishscore=0 impostorscore=0 priorityscore=1501 mlxlogscore=999 adultscore=0 clxscore=1015 malwarescore=0 suspectscore=0 lowpriorityscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2009150000 definitions=main-2012040031 X-Spam-Status: No, score=-12.1 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 06:17:20 -0000 Jiufu Guo writes: > 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-= 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 |=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 = of 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 exi= t edge >>>>>> + is NEW_PROB. */ >>>>>> + >>>>>> +bool >>>>>> +recompute_loop_frequencies (class loop *loop, profile_probability n= ew_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->h= eader->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_pro= b); >>>>>> + >>>>>> + /* 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_= num, >>>>>> + after_den); >>>>>> + free (bbs); >>>>>> + >>>>>> + /* Update probability and count of the BB besides exit edge (mayb= e 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 answ= er >>>>> whether or not the block with the loop exit edge can have > 2 success= ors. >>>> 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) c= an'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. Oh, this may be indicate 'approval with comments', right? :) Thanks, Jiufu Guo. >>> >>> 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.