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 67F893858402 for ; Tue, 14 Sep 2021 01:15:44 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 67F893858402 Received: from pps.filterd (m0098409.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.1.2/8.16.0.43) with SMTP id 18E15dSB007334; Mon, 13 Sep 2021 21:15:43 -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 3b2hs005w5-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Mon, 13 Sep 2021 21:15:42 -0400 Received: from pps.filterd (ppma06ams.nl.ibm.com [127.0.0.1]) by ppma06ams.nl.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 18E17LVM001615; Tue, 14 Sep 2021 01:15:40 GMT Received: from b06cxnps3075.portsmouth.uk.ibm.com (d06relay10.portsmouth.uk.ibm.com [9.149.109.195]) by ppma06ams.nl.ibm.com with ESMTP id 3b0kqjdnu4-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Tue, 14 Sep 2021 01:15:40 +0000 Received: from d06av21.portsmouth.uk.ibm.com (d06av21.portsmouth.uk.ibm.com [9.149.105.232]) by b06cxnps3075.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 18E1Fc9n41943430 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Tue, 14 Sep 2021 01:15:38 GMT Received: from d06av21.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 3A8345204E; Tue, 14 Sep 2021 01:15:38 +0000 (GMT) Received: from luoxhus-MacBook-Pro.local (unknown [9.200.37.207]) by d06av21.portsmouth.uk.ibm.com (Postfix) with ESMTPS id 4D58752054; Tue, 14 Sep 2021 01:15:37 +0000 (GMT) Subject: Re: [PATCH] tree-optimization/102155 - fix LIM fill_always_executed_in CFG walk To: Richard Biener Cc: gcc-patches@gcc.gnu.org References: <47so1129-4rp-93pp-op88-4p649p42po80@fhfr.qr> <4a364fc3-7390-d3ca-5e71-6520061cf738@linux.ibm.com> <566e5d26-2c0e-8181-2249-211ebf369b73@linux.ibm.com> <8on1r65r-n4qr-9555-s3q6-75783p6622@fhfr.qr> <44039d9b-d481-2a11-fcdc-493915833ae9@linux.ibm.com> From: Xionghu Luo Message-ID: <6e03654b-be4c-db99-dedb-889a33819173@linux.ibm.com> Date: Tue, 14 Sep 2021 09:15:34 +0800 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) Gecko/20100101 Thunderbird/78.14.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US X-TM-AS-GCONF: 00 X-Proofpoint-ORIG-GUID: NhJxPUCrLIjBbvJkmIFkKWXMmvhaVvdF X-Proofpoint-GUID: NhJxPUCrLIjBbvJkmIFkKWXMmvhaVvdF Content-Transfer-Encoding: 8bit X-Proofpoint-UnRewURL: 0 URL was un-rewritten MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.182.1,Aquarius:18.0.687,Hydra:6.0.235,FMLib:17.0.607.475 definitions=2020-10-13_15,2020-10-13_02,2020-04-07_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 adultscore=0 bulkscore=0 mlxlogscore=999 spamscore=0 lowpriorityscore=0 mlxscore=0 priorityscore=1501 phishscore=0 malwarescore=0 clxscore=1015 impostorscore=0 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2109030001 definitions=main-2109130135 X-Spam-Status: No, score=-11.9 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, NICE_REPLY_A, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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: Tue, 14 Sep 2021 01:15:45 -0000 On 2021/9/13 16:17, Richard Biener wrote: > On Mon, 13 Sep 2021, Xionghu Luo wrote: > >> >> >> On 2021/9/10 21:54, Xionghu Luo via Gcc-patches wrote: >>> >>> >>> On 2021/9/9 18:55, Richard Biener wrote: >>>> diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c >>>> index 5d6845478e7..4b187c2cdaf 100644 >>>> --- a/gcc/tree-ssa-loop-im.c >>>> +++ b/gcc/tree-ssa-loop-im.c >>>> @@ -3074,15 +3074,13 @@ fill_always_executed_in_1 (class loop *loop, >>>> sbitmap contains_call) >>>>           break; >>>>         if (bb->loop_father->header == bb) >>>> -        { >>>> -          if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) >>>> -        break; >>>> - >>>> -          /* In a loop that is always entered we may proceed anyway. >>>> -         But record that we entered it and stop once we leave it >>>> -         since it might not be finite.  */ >>>> -          inn_loop = bb->loop_father; >>>> -        } >>>> +        /* Record that we enter into a subloop since it might not >>>> +           be finite.  */ >>>> +        /* ???  Entering into a not always executed subloop makes >>>> +           fill_always_executed_in quadratic in loop depth since >>>> +           we walk those loops N times.  This is not a problem >>>> +           in practice though, see PR102253 for a worst-case testcase.  */ >>>> +        inn_loop = bb->loop_father; >>> >>> >>> Yes your two patches extracted the get_loop_body_in_dom_order out and >>> removed >>> the inn_loop break logic when it doesn't dominate outer loop.  Confirmed the >>> replacement >>> could improve for saving ~10% build time due to not full DOM walker and >>> marked the previously >>> ignored ALWAYS_EXECUTED bbs. >>> But if we don't break for inner loop again, why still keep the *inn_loop* >>> variable? >>> It seems unnecessary and confusing, could we just remove it and restore the >>> original >>> infinte loop check in bb->succs for better understanding? >> >> >> What's more, the refine of this fix is incorrect for PR78185. >> >> >> commit 483e400870601f650c80f867ec781cd5f83507d6 >> Author: Richard Biener >> Date: Thu Sep 2 10:47:35 2021 +0200 >> >> Refine fix for PR78185, improve LIM for code after inner loops >> >> This refines the fix for PR78185 after understanding that the code >> regarding to the comment 'In a loop that is always entered we may >> proceed anyway. But record that we entered it and stop once we leave >> it.' was supposed to protect us from leaving possibly infinite inner >> loops. The simpler fix of moving the misplaced stopping code >> can then be refined to continue processing when the exited inner >> loop is finite, improving invariant motion for cases like in the >> added testcase. >> >> 2021-09-02 Richard Biener >> >> * tree-ssa-loop-im.c (fill_always_executed_in_1): Refine >> fix for PR78185 and continue processing when leaving >> finite inner loops. >> >> * gcc.dg/tree-ssa/ssa-lim-16.c: New testcase. >> >> >> 3<------- >> | | >> 6<--- | >> | \ | | >> | \ | | >> 4 8 | >> |--- | >> | | | >> 5 7------ >> | >> 1 >> >> loop 2 is an infinite loop, it is only ALWAYS_EXECUTED for loop 2, >> but r12-3313-g483e40087 sets it ALWAYS_EXECUTED for loop 1. >> We need to restore it like this: >> https://gcc.gnu.org/pipermail/gcc-patches/2021-September/579195.html > > I don't understand - BB6 is the header block of loop 2 which is > always entered and thus BB6 is always executed at least once. > > The important part is that BB4 which follows the inner loop is > _not_ always executed because we don't know if we will exit the > inner loop. > > What am I missing? Oh, I see. I only noticed the functionality change of the patch on the case and no failure check of it, misunderstood it was a regression instead of an improvement to also hoisting invariants from infinite loop, sorry about that. Finally, the function fill_always_executed_in_1 could mark all ALWAYS_EXECUTED bb both including and after all subloops' bb but break after exiting from infinite subloops with better performance, thanks. The only thing to be worried is replacing get_loop_body_in_dom_order makes the code a bit more complicated for later readers as the loop depth and DOM order is not a problem here any more? ;) > > Richard. > -- Thanks, Xionghu