From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id 3B1FE3858D35 for ; Mon, 13 Sep 2021 08:17:31 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 3B1FE3858D35 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id EBBBF21F23; Mon, 13 Sep 2021 08:17:29 +0000 (UTC) Received: from murzim.suse.de (murzim.suse.de [10.160.4.192]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id CFEEFA3B89; Mon, 13 Sep 2021 08:17:29 +0000 (UTC) Date: Mon, 13 Sep 2021 10:17:29 +0200 (CEST) From: Richard Biener To: Xionghu Luo cc: gcc-patches@gcc.gnu.org Subject: Re: [PATCH] tree-optimization/102155 - fix LIM fill_always_executed_in CFG walk In-Reply-To: Message-ID: 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> User-Agent: Alpine 2.21 (LSU 202 2017-01-01) MIME-Version: 1.0 X-Spam-Status: No, score=-9.4 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, 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 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8BIT X-Content-Filtered-By: Mailman/MimeDel 2.1.29 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: Mon, 13 Sep 2021 08:17:32 -0000 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? Richard.