From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2063) id B31603988429; Thu, 5 Aug 2021 08:45:26 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B31603988429 MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Kewen Lin To: gcc-cvs@gcc.gnu.org Subject: [gcc r12-2756] cfgloop: Make loops_list support an optional loop_p root X-Act-Checkin: gcc X-Git-Author: Kewen Lin X-Git-Refname: refs/heads/master X-Git-Oldrev: 4e3129b0caceec008a940aa5eada253cd0f0b3ec X-Git-Newrev: d0a5624bb40470cb0ee03fe86530118ca6de0b3a Message-Id: <20210805084526.B31603988429@sourceware.org> Date: Thu, 5 Aug 2021 08:45:26 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 05 Aug 2021 08:45:26 -0000 https://gcc.gnu.org/g:d0a5624bb40470cb0ee03fe86530118ca6de0b3a commit r12-2756-gd0a5624bb40470cb0ee03fe86530118ca6de0b3a Author: Kewen Lin Date: Sun Jul 25 20:52:08 2021 -0500 cfgloop: Make loops_list support an optional loop_p root This patch follows Richi's suggestion to add one optional argument class loop* root to loops_list's CTOR, it can provide the ability to construct a visiting list starting from the given class loop* ROOT rather than the default tree_root of loops_for_fn (FN), for visiting a subset of the loop tree. It unifies all orders of walkings into walk_loop_tree, but it still uses linear search for LI_ONLY_INNERMOST when looking at the whole loop tree since it has a more stable bound. gcc/ChangeLog: * cfgloop.h (loops_list::loops_list): Add one optional argument root and adjust accordingly, update loop tree walking and factor out to ... * cfgloop.c (loops_list::walk_loop_tree): ... this. New function. Diff: --- gcc/cfgloop.c | 66 ++++++++++++++++++++++++++++++++++++++ gcc/cfgloop.h | 100 +++++++++++++++++++++++----------------------------------- 2 files changed, 106 insertions(+), 60 deletions(-) diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index 6284ae292b6..2ba9918bfa2 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -2104,3 +2104,69 @@ mark_loop_for_removal (loop_p loop) loop->latch = NULL; loops_state_set (LOOPS_NEED_FIXUP); } + +/* Starting from loop tree ROOT, walk loop tree as the visiting + order specified by FLAGS. The supported visiting orders + are: + - LI_ONLY_INNERMOST + - LI_FROM_INNERMOST + - Preorder (if neither of above is specified) */ + +void +loops_list::walk_loop_tree (class loop *root, unsigned flags) +{ + bool only_innermost_p = flags & LI_ONLY_INNERMOST; + bool from_innermost_p = flags & LI_FROM_INNERMOST; + bool preorder_p = !(only_innermost_p || from_innermost_p); + + /* Early handle root without any inner loops, make later + processing simpler, that is all loops processed in the + following while loop are impossible to be root. */ + if (!root->inner) + { + if (flags & LI_INCLUDE_ROOT) + this->to_visit.quick_push (root->num); + return; + } + else if (preorder_p && flags & LI_INCLUDE_ROOT) + this->to_visit.quick_push (root->num); + + class loop *aloop; + for (aloop = root->inner; + aloop->inner != NULL; + aloop = aloop->inner) + { + if (preorder_p) + this->to_visit.quick_push (aloop->num); + continue; + } + + while (1) + { + gcc_assert (aloop != root); + if (from_innermost_p || aloop->inner == NULL) + this->to_visit.quick_push (aloop->num); + + if (aloop->next) + { + for (aloop = aloop->next; + aloop->inner != NULL; + aloop = aloop->inner) + { + if (preorder_p) + this->to_visit.quick_push (aloop->num); + continue; + } + } + else if (loop_outer (aloop) == root) + break; + else + aloop = loop_outer (aloop); + } + + /* When visiting from innermost, we need to consider root here + since the previous while loop doesn't handle it. */ + if (from_innermost_p && flags & LI_INCLUDE_ROOT) + this->to_visit.quick_push (root->num); +} + diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index 885632bbbed..0f71a6bf18f 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 the tree_root of + 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, class loop *root = nullptr); template class Iter { @@ -750,6 +752,10 @@ public: } private: + /* Walk loop tree starting from ROOT as the visiting order specified + by FLAGS. */ + void walk_loop_tree (class loop *root, unsigned flags); + /* The function we are visiting. */ function *fn; @@ -782,76 +788,50 @@ 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, class loop *root) { - class loop *aloop; - unsigned i; - int mn; + struct loops *loops = loops_for_fn (fn); + gcc_assert (!root || loops); + + /* Check mutually exclusive flags should not co-exist. */ + unsigned checked_flags = LI_ONLY_INNERMOST | LI_FROM_INNERMOST; + gcc_assert ((flags & checked_flags) != checked_flags); this->fn = fn; - if (!loops_for_fn (fn)) + if (!loops) return; + class loop *tree_root = root ? root : loops->tree_root; + this->to_visit.reserve_exact (number_of_loops (fn)); - mn = (flags & LI_INCLUDE_ROOT) ? 0 : 1; - if (flags & LI_ONLY_INNERMOST) + /* When root is tree_root of loops_for_fn (fn) and the visiting + order is LI_ONLY_INNERMOST, we would like to use linear + search here since it has a more stable bound than the + walk_loop_tree. */ + if (flags & LI_ONLY_INNERMOST && tree_root == loops->tree_root) { - for (i = 0; vec_safe_iterate (loops_for_fn (fn)->larray, i, &aloop); i++) - if (aloop != NULL - && aloop->inner == NULL - && aloop->num >= mn) - 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) + gcc_assert (tree_root->num == 0); + if (tree_root->inner == NULL) { - 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)) - break; - else - aloop = loop_outer (aloop); + if (flags & LI_INCLUDE_ROOT) + this->to_visit.quick_push (0); + + return; } + + class loop *aloop; + unsigned int i; + for (i = 1; vec_safe_iterate (loops->larray, i, &aloop); i++) + if (aloop != NULL && aloop->inner == NULL) + this->to_visit.quick_push (aloop->num); } else - { - /* Push the loops to LI->TO_VISIT in preorder. */ - aloop = loops_for_fn (fn)->tree_root; - while (1) - { - 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) - aloop = loop_outer (aloop); - if (aloop == NULL) - break; - aloop = aloop->next; - } - } - } + walk_loop_tree (tree_root, flags); } /* The properties of the target. */