From patchwork Fri Jul 23 08:41:30 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: "Kewen.Lin" X-Patchwork-Id: 1509036 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=ZMV5u2Am; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4GWN9F1GHlz9sRR for ; Fri, 23 Jul 2021 18:42:08 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2C0013853C2E for ; Fri, 23 Jul 2021 08:42:05 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2C0013853C2E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1627029725; bh=vs6OTB+JgDQq1LwdAhqYF1YFf2W6q3YClEbU0QPZbUg=; h=Subject:To:References:Date:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=ZMV5u2AmYYSOD0PfHuqz4SazeUNXEr1HpvtCkZpTKZHEvM9lwTZKt3RHIZnfEZzPW dBDbOZc3p7KiNHxBmSD/i03EFG1xxHbIAxOI3QfAtBntyWrm+0C9wUUrJCk8CFAT4F PaaInSwnc/wc83Hj5x2GDFgVxgezebt5rLJeHgzQ= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx0a-001b2d01.pphosted.com (mx0b-001b2d01.pphosted.com [148.163.158.5]) by sourceware.org (Postfix) with ESMTPS id EC0EC3853C1C for ; Fri, 23 Jul 2021 08:41:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org EC0EC3853C1C Received: from pps.filterd (m0098416.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.0.43/8.16.0.43) with SMTP id 16N8cIGZ153177; Fri, 23 Jul 2021 04:41:40 -0400 Received: from pps.reinject (localhost [127.0.0.1]) by mx0b-001b2d01.pphosted.com with ESMTP id 39ysah1s5r-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 23 Jul 2021 04:41:40 -0400 Received: from m0098416.ppops.net (m0098416.ppops.net [127.0.0.1]) by pps.reinject (8.16.0.43/8.16.0.43) with SMTP id 16N8coIK156065; Fri, 23 Jul 2021 04:41:40 -0400 Received: from ppma03fra.de.ibm.com (6b.4a.5195.ip4.static.sl-reverse.com [149.81.74.107]) by mx0b-001b2d01.pphosted.com with ESMTP id 39ysah1s4y-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 23 Jul 2021 04:41:39 -0400 Received: from pps.filterd (ppma03fra.de.ibm.com [127.0.0.1]) by ppma03fra.de.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 16N8Y49e007197; Fri, 23 Jul 2021 08:41:38 GMT Received: from b06cxnps3075.portsmouth.uk.ibm.com (d06relay10.portsmouth.uk.ibm.com [9.149.109.195]) by ppma03fra.de.ibm.com with ESMTP id 39upu89sga-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 23 Jul 2021 08:41:37 +0000 Received: from d06av22.portsmouth.uk.ibm.com (d06av22.portsmouth.uk.ibm.com [9.149.105.58]) by b06cxnps3075.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 16N8fZeD36897106 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 23 Jul 2021 08:41:35 GMT Received: from d06av22.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 73F8C4C050; Fri, 23 Jul 2021 08:41:35 +0000 (GMT) Received: from d06av22.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 0800A4C044; Fri, 23 Jul 2021 08:41:32 +0000 (GMT) Received: from KewenLins-MacBook-Pro.local (unknown [9.200.59.223]) by d06av22.portsmouth.uk.ibm.com (Postfix) with ESMTP; Fri, 23 Jul 2021 08:41:31 +0000 (GMT) Subject: [PATCH] Make loops_list support an optional loop_p root To: Richard Biener References: <0a8b77ba-1d54-1eff-b54d-d2cb1e769e09@linux.ibm.com> Message-ID: <61ac669c-7293-f53a-20c7-158b5a813cee@linux.ibm.com> Date: Fri, 23 Jul 2021 16:41:30 +0800 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) Gecko/20100101 Thunderbird/78.10.0 MIME-Version: 1.0 In-Reply-To: Content-Language: en-US X-TM-AS-GCONF: 00 X-Proofpoint-ORIG-GUID: kcqxlUpkcRD1ub3Bcmo2NYePH3oaA9T- X-Proofpoint-GUID: b9IB0oKCQeAQ-fTT8JnEUshczh5O9cj1 X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.391, 18.0.790 definitions=2021-07-23_04:2021-07-23, 2021-07-23 signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 priorityscore=1501 clxscore=1015 mlxscore=0 malwarescore=0 phishscore=0 bulkscore=0 spamscore=0 impostorscore=0 suspectscore=0 mlxlogscore=999 lowpriorityscore=0 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2104190000 definitions=main-2107230049 X-Spam-Status: No, score=-11.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_MSPIKE_H2, 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-Patchwork-Original-From: "Kewen.Lin via Gcc-patches" From: "Kewen.Lin" Reply-To: "Kewen.Lin" Cc: Jakub Jelinek , Jonathan Wakely , Segher Boessenkool , Richard Sandiford , Bill Schmidt , GCC Patches , Trevor Saunders Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" on 2021/7/22 下午8:56, Richard Biener wrote: > On Tue, Jul 20, 2021 at 4:37 > PM Kewen.Lin wrote: >> >> Hi, >> >> This v2 has addressed some review comments/suggestions: >> >> - Use "!=" instead of "<" in function operator!= (const Iter &rhs) >> - Add new CTOR loops_list (struct loops *loops, unsigned flags) >> to support loop hierarchy tree rather than just a function, >> and adjust to use loops* accordingly. > > I actually meant struct loop *, not struct loops * ;) At the point > we pondered to make loop invariant motion work on single > loop nests we gave up not only but also because it iterates > over the loop nest but all the iterators only ever can process > all loops, not say, all loops inside a specific 'loop' (and > including that 'loop' if LI_INCLUDE_ROOT). So the > CTOR would take the 'root' of the loop tree as argument. > > I see that doesn't trivially fit how loops_list works, at least > not for LI_ONLY_INNERMOST. But I guess FROM_INNERMOST > could be adjusted to do ONLY_INNERMOST as well? > Thanks for the clarification! I just realized that the previous version with struct loops* is problematic, all traversal is still bounded with outer_loop == NULL. I think what you expect is to respect the given loop_p root boundary. Since we just record the loops' nums, I think we still need the function* fn? So I add one optional argument loop_p root and update the visiting codes accordingly. Before this change, the previous visiting uses the outer_loop == NULL as the termination condition, it perfectly includes the root itself, but with this given root, we have to use it as the termination condition to avoid to iterate onto its possible existing next. For LI_ONLY_INNERMOST, I was thinking whether we can use the code like: struct loops *fn_loops = loops_for_fn (fn)->larray; for (i = 0; vec_safe_iterate (fn_loops, i, &aloop); i++) if (aloop != NULL && aloop->inner == NULL && flow_loop_nested_p (tree_root, aloop)) this->to_visit.quick_push (aloop->num); it has the stable bound, but if the given root only has several child loops, it can be much worse if there are many loops in fn. It seems impossible to predict the given root loop hierarchy size, maybe we can still use the original linear searching for the case loops_for_fn (fn) == root? But since this visiting seems not so performance critical, I chose to share the code originally used for FROM_INNERMOST, hope it can have better readability and maintainability. Bootstrapped and regtested on powerpc64le-linux-gnu P9, x86_64-redhat-linux and aarch64-linux-gnu, also bootstrapped on ppc64le P9 with bootstrap-O3 config. Does the attached patch meet what you expect? BR, Kewen ----- gcc/ChangeLog: * cfgloop.h (loops_list::loops_list): Add one optional argument root and adjust accordingly. diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index 741df44ea51..f7148df1758 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -669,13 +669,15 @@ as_const (T &t) } /* A list for visiting loops, which contains the loop numbers instead of - the loop pointers. The scope is restricted in function FN and the - visiting order is specified by FLAGS. */ + the loop pointers. If the loop ROOT is offered (non-null), the visiting + will start from it, otherwise it would start from loops_for_fn (FN) + instead. The scope is restricted in function FN and the visiting order + is specified by FLAGS. */ class loops_list { public: - loops_list (function *fn, unsigned flags); + loops_list (function *fn, unsigned flags, loop_p root = nullptr); template class Iter { @@ -782,71 +784,94 @@ loops_list::Iter::fill_curr_loop () } /* Set up the loops list to visit according to the specified - function scope FN and iterating order FLAGS. */ + function scope FN and iterating order FLAGS. If ROOT is + not null, the visiting would start from it, otherwise it + will start from tree_root of loops_for_fn (FN). */ -inline loops_list::loops_list (function *fn, unsigned flags) +inline loops_list::loops_list (function *fn, unsigned flags, loop_p root) { class loop *aloop; - unsigned i; int mn; + struct loops *loops = loops_for_fn (fn); + gcc_assert (!root || loops); + this->fn = fn; - if (!loops_for_fn (fn)) + if (!loops) return; + loop_p tree_root = root ? root : loops->tree_root; + this->to_visit.reserve_exact (number_of_loops (fn)); - mn = (flags & LI_INCLUDE_ROOT) ? 0 : 1; + mn = (flags & LI_INCLUDE_ROOT) ? -1 : tree_root->num; - if (flags & LI_ONLY_INNERMOST) - { - for (i = 0; vec_safe_iterate (loops_for_fn (fn)->larray, i, &aloop); i++) - if (aloop != NULL - && aloop->inner == NULL - && aloop->num >= mn) + /* The helper function for LI_FROM_INNERMOST and LI_ONLY_INNERMOST + visiting, ONLY_PUSH_INNERMOST_P indicates whether only push + the innermost loop, it's true for LI_ONLY_INNERMOST visiting + while false for LI_FROM_INNERMOST visiting. */ + auto visit_from_innermost = [&] (bool only_push_innermost_p) + { + /* Push the loops to LI->TO_VISIT in postorder. */ + + /* Early handle tree_root without any inner loops, make later + processing simpler, that is the while loop can only care + about loops which aren't possible to be tree_root. */ + if (!tree_root->inner) + { + if (tree_root->num != mn) + this->to_visit.quick_push (tree_root->num); + return; + } + + for (aloop = tree_root; + aloop->inner != NULL; + aloop = aloop->inner) + continue; + + while (1) + { + gcc_assert (aloop != tree_root); + if (!only_push_innermost_p || aloop->inner == NULL) this->to_visit.quick_push (aloop->num); - } - else if (flags & LI_FROM_INNERMOST) - { - /* Push the loops to LI->TO_VISIT in postorder. */ - for (aloop = loops_for_fn (fn)->tree_root; - aloop->inner != NULL; - aloop = aloop->inner) - continue; - while (1) - { - if (aloop->num >= mn) - this->to_visit.quick_push (aloop->num); + if (aloop->next) + { + for (aloop = aloop->next; + aloop->inner != NULL; + aloop = aloop->inner) + continue; + } + else if (loop_outer (aloop) == tree_root) + break; + else + aloop = loop_outer (aloop); + } + + /* Reconsider tree_root since the previous loop doesn't handle it. */ + if (!only_push_innermost_p && tree_root->num != mn) + this->to_visit.quick_push (tree_root->num); + }; - if (aloop->next) - { - for (aloop = aloop->next; - aloop->inner != NULL; - aloop = aloop->inner) - continue; - } - else if (!loop_outer (aloop)) - break; - else - aloop = loop_outer (aloop); - } - } + if (flags & LI_ONLY_INNERMOST) + visit_from_innermost (true); + else if (flags & LI_FROM_INNERMOST) + visit_from_innermost (false); else { /* Push the loops to LI->TO_VISIT in preorder. */ - aloop = loops_for_fn (fn)->tree_root; + aloop = tree_root; while (1) { - if (aloop->num >= mn) + if (aloop->num != mn) this->to_visit.quick_push (aloop->num); if (aloop->inner != NULL) aloop = aloop->inner; else { - while (aloop != NULL && aloop->next == NULL) + while (aloop != tree_root && aloop->next == NULL) aloop = loop_outer (aloop); - if (aloop == NULL) + if (aloop == tree_root) break; aloop = aloop->next; }