From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1011) id A13663858D1E; Tue, 19 Jul 2022 22:10:51 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A13663858D1E MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Andrew Macleod To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-1758] Remove recursion from range_from_dom. X-Act-Checkin: gcc X-Git-Author: Andrew MacLeod X-Git-Refname: refs/heads/master X-Git-Oldrev: f838d15641d256e21ffc126c3277b290ed743928 X-Git-Newrev: b0cc57cd76f511f29cab233654249817312ec2a6 Message-Id: <20220719221051.A13663858D1E@sourceware.org> Date: Tue, 19 Jul 2022 22:10:51 +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: Tue, 19 Jul 2022 22:10:51 -0000 https://gcc.gnu.org/g:b0cc57cd76f511f29cab233654249817312ec2a6 commit r13-1758-gb0cc57cd76f511f29cab233654249817312ec2a6 Author: Andrew MacLeod Date: Fri Jul 15 09:35:29 2022 -0400 Remove recursion from range_from_dom. Avoid calling range_of_dom recursively by putting all nodes to be calculated on the worklist, and figure out which kind they are when removed from the list. * gimple-range-cache.cc (ranger_cache::resolve_dom): New. (ranger_cache::range_from_dom): Put all nodes to be calculated in the worklist and resolve after the dom walk. * gimple-range-cache.h (resolve_dom): New prototype. Diff: --- gcc/gimple-range-cache.cc | 84 ++++++++++++++++++++++++++--------------------- gcc/gimple-range-cache.h | 1 + 2 files changed, 48 insertions(+), 37 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index da7b8055d42..20dd5ead3bc 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -1312,6 +1312,38 @@ ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb) fprintf (dump_file, " Propagation update done.\n"); } +// Resolve the range of BB if the dominators range is R by calculating incoming +// edges to this block. All lead back to the dominator so should be cheap. +// The range for BB is set and returned in R. + +void +ranger_cache::resolve_dom (vrange &r, tree name, basic_block bb) +{ + basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name)); + basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb); + + // if it doesn't already have a value, store the incoming range. + if (!m_on_entry.bb_range_p (name, dom_bb) && def_bb != dom_bb) + { + // If the range can't be store, don't try to accumulate + // the range in PREV_BB due to excessive recalculations. + if (!m_on_entry.set_bb_range (name, dom_bb, r)) + return; + } + // With the dominator set, we should be able to cheaply query + // each incoming edge now and accumulate the results. + r.set_undefined (); + edge e; + edge_iterator ei; + Value_Range er (TREE_TYPE (name)); + FOR_EACH_EDGE (e, ei, bb->preds) + { + edge_range (er, e, name, RFD_READ_ONLY); + r.union_ (er); + } + // Set the cache in PREV_BB so it is not calculated again. + m_on_entry.set_bb_range (name, bb, r); +} // Get the range of NAME from dominators of BB and return it in R. Search the // dominator tree based on MODE. @@ -1341,7 +1373,7 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb, // Default value is global range. get_global_range (r, name); - // Search until a value is found, pushing outgoing edges encountered. + // Search until a value is found, pushing blocks which may need calculating. for (bb = get_immediate_dominator (CDI_DOMINATORS, start_bb); bb; prev_bb = bb, bb = get_immediate_dominator (CDI_DOMINATORS, bb)) @@ -1351,40 +1383,7 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb, // This block has an outgoing range. if (m_gori.has_edge_range_p (name, bb)) - { - // Only outgoing ranges to single_pred blocks are dominated by - // outgoing edge ranges, so those can be simply adjusted on the fly. - edge e = find_edge (bb, prev_bb); - if (e && single_pred_p (prev_bb)) - m_workback.quick_push (prev_bb); - else if (mode == RFD_FILL) - { - // Multiple incoming edges, so recursively satisfy this block - // if it doesn't already have a value, and store the range. - if (!m_on_entry.bb_range_p (name, bb) && def_bb != bb) - { - // If the dominator has not been set, look it up. - range_from_dom (r, name, bb, RFD_FILL); - // If the range can't be store, don't try to accumulate - // the range in PREV_BB due to excessive recalculations. - if (!m_on_entry.set_bb_range (name, bb, r)) - break; - } - // With the dominator set, we should be able to cheaply query - // each incoming edge now and accumulate the results. - r.set_undefined (); - edge_iterator ei; - Value_Range er (TREE_TYPE (name)); - FOR_EACH_EDGE (e, ei, prev_bb->preds) - { - edge_range (er, e, name, RFD_READ_ONLY); - r.union_ (er); - } - // Set the cache in PREV_BB so it is not calculated again. - m_on_entry.set_bb_range (name, prev_bb, r); - break; - } - } + m_workback.quick_push (prev_bb); if (def_bb == bb) break; @@ -1403,14 +1402,25 @@ ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb, fprintf (dump_file, " at function top\n"); } - // Now process any outgoing edges that we seen along the way. + // Now process any blocks wit incoming edges that nay have adjustemnts. while (m_workback.length () > start_limit) { int_range_max er; prev_bb = m_workback.pop (); + if (!single_pred_p (prev_bb)) + { + // Non single pred means we need to cache a vsalue in the dominator + // so we can cheaply calculate incoming edges to this block, and + // then store the resulting value. If processing mode is not + // RFD_FILL, then the cache cant be stored to, so don't try. + // Otherwise this becomes a quadratic timed calculation. + if (mode == RFD_FILL) + resolve_dom (r, name, prev_bb); + continue; + } + edge e = single_pred_edge (prev_bb); bb = e->src; - if (m_gori.outgoing_edge_range_p (er, e, name, *this)) { r.intersect (er); diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 0341192c9cb..45053b5873a 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -107,6 +107,7 @@ private: RFD_FILL // Scan DOM tree, updating important nodes. }; bool range_from_dom (vrange &r, tree name, basic_block bb, enum rfd_mode); + void resolve_dom (vrange &r, tree name, basic_block bb); void range_of_def (vrange &r, tree name, basic_block bb = NULL); void entry_range (vrange &r, tree expr, basic_block bb, enum rfd_mode); void exit_range (vrange &r, tree expr, basic_block bb, enum rfd_mode);